Многокритериальное целевое программирование
- Автор метода
- Charnes, A. and Cooper, W. W.
- Год
- 1961
- Тип
- Mathematical programming / multi-criteria optimization
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Многокритериальное целевое программирование (MOGP) — это метод математического программирования, который одновременно преследует несколько целевых показателей, минимизируя взвешенные отклонения от каждой цели.
Основанный на оригинальной структуре целевого программирования Чарнса и Купера (1961), MOGP расширяет ее для работы с множественными конкурирующими целями, что делает его незаменимым в исследовании операций, проектировании цепочек поставок, распределении ресурсов и анализе политики, где лица, принимающие решения, должны одновременно удовлетворить — или приблизиться к удовлетворению — множеству противоречивых требований.
Интуиция метода
Представьте себе менеджера, которому необходимо одновременно достичь целевого показателя прибыли, оставаться в рамках углеродного бюджета и удерживать сверхурочную работу сотрудников ниже установленного предела. Чистая оптимизация может оптимизировать только одну цель за раз, а рассмотрение остальных как жестких ограничений может привести к неосуществимости. Целевое программирование переформулирует каждую цель как «цель» и минимизирует расстояние, на которое решение не достигает (или превышает) каждую цель. Многокритериальный вариант взвешивает эти отклонения по всем целям и находит наилучший осуществимый компромисс — подобно поиску точки в ландшафте, которая находится ближе всего к нескольким вершинам одновременно.
История
Целевое программирование было введено Чарнсом и Купером в 1961 году как расширение линейного программирования для обработки множественных целей через целевые уровни. Иджири (1965) формализовал лексикографический вариант, а Ли (1972) консолидировал метод для приложений в науке управления. Многокритериальная (векторная) формулировка стала заметной благодаря работе Тамиза, Джонса и Ромеро в 1990-х годах, и сегодня MOGP является стандартным инструментом в учебных программах по исследованию операций и прикладной оптимизации.
Когда применять
Используйте MOGP, когда задача принятия решений включает в себя множественные, количественно измеримые, возможно, противоречивые цели, и когда лица, принимающие решения, могут выразить целевые уровни для каждой из них. Он особенно подходит для распределения ресурсов, выбора портфеля, планирования производства и экологической политики, где необходимо поддерживать осуществимость при преследовании нескольких целей. Предпочитайте MOGP чистой многокритериальной оптимизации, когда заинтересованные стороны думают в терминах «целей, которых нужно достичь», а не «критериев, которые нужно максимизировать». НЕ используйте его, когда цели не могут быть выражены в виде количественных целевых показателей, когда задача по своей сути нелинейна и решатели недоступны, когда кардинальные веса невозможно обосновать, или когда требуется строгий анализ Парето-фронта (без привязки к целям).
Ограничения и замечания
- Целевые (аспирационные) уровни и веса должны быть получены от лиц, принимающих решения, что может быть субъективным и политически спорным.
- Решение чувствительно к выбранным весам; различные схемы взвешивания могут давать существенно разные результаты.
- Стандартное линейное GP предполагает выпуклость; невыпуклые или комбинаторные задачи требуют специализированных решателей и могут стать вычислительно интенсивными.
- Не гарантирует Парето-оптимальности — решение GP может быть доминируемым, если цели и веса указаны некорректно.
- Несоизмеримые шкалы целей требуют нормализации, что может внести дополнительные субъективные выборы.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Естественно обрабатывает множественные противоречивые цели в рамках одной, решаемой оптимизационной модели.
- Гибкие функции достижения — взвешенные, лексикографические или min-max варианты — учитывают различные структуры предпочтений заинтересованных сторон.
- Представляет одно рекомендуемое решение вместо большого Парето-множества, упрощая коммуникацию с лицами, принимающими решения.
- Может быть расширен до целочисленных, бинарных или нелинейных формулировок, охватывая широкий спектр реальных задач.
- Анализ чувствительности весов и целевых уровней является прямолинейным, выявляя устойчивость решения к изменениям предпочтений.
Применение
- Проектирование сети цепочки поставок с балансировкой целевых показателей затрат, уровня обслуживания и углеродного следа.
- Распределение ресурсов больницы с одновременным достижением целей по укомплектованию штатов, загрузке коек и бюджету.
- Сельскохозяйственное планирование, оптимизирующее урожайность, использование воды и экономическую отдачу при фиксированных ограничениях на землю.
- Выбор финансового портфеля, удовлетворяющего целевым уровням доходности, риска и ликвидности.
- Моделирование энергетической политики, учитывающее компромиссы между мощностью возобновляемых источников, надежностью сети и затратами на инвестиции.
- Составление расписания университетских курсов с учетом нагрузки преподавателей, вместимости аудиторий и целей предпочтений студентов.
Как это работает
Как это работает
Определите все K целей и установите целевые уровни g_k для каждого критерия f_k(x). Цели могут отражать целевые показатели прибыли, предельные значения затрат, экологические квоты или требования к уровню обслуживания. Определите, являются ли нежелательными перевыполнение, недовыполнение или оба типа отклонений для каждой цели.
Введите неотрицательные переменные отклонений d_k^+ (перевыполнение) и d_k^- (недовыполнение) для каждой цели k, так чтобы f_k(x) + d_k^- - d_k^+ = g_k. Эти переменные количественно определяют, насколько решение отклоняется от каждого целевого уровня.
Формула
d_k^+ = \max(f_k(x) - g_k, 0), \quad d_k^- = \max(g_k - f_k(x), 0)
Постройте функцию достижения (целевую) как взвешенную сумму переменных отклонений: min Z = sum_k (w_k^+ * d_k^+ + w_k^- * d_k^-). Веса w_k отражают относительную важность достижения каждой цели. В качестве альтернативы, лексикографический порядок приоритетов может заменить веса для структур строгих приоритетов.
Формула
\min \; Z = \sum_{k=1}^{K} (w_k^+ d_k^+ + w_k^- d_k^-)Решите полученную линейную (или нелинейную) задачу с помощью стандартных решателей. Корректируйте целевые уровни и веса на основе анализа чувствительности или обратной связи от заинтересованных сторон и решайте повторно, чтобы исследовать пространство решений и понять компромиссы между целями.
Проанализируйте окончательные значения отклонений, чтобы определить, какие цели полностью достигнуты (d_k^+ = d_k^- = 0), а какие включают остаточные отклонения. Представьте Парето-эфронт или профиль достижения лицам, принимающим решения, для окончательного выбора и обоснования.
Частые ошибки
- Установка нереалистичных целевых уровней может сделать все цели одновременно недостижимыми, что приведет к большим отклонениям для каждой цели и неинформативному решению.
- Игнорирование различия между нежелательным перевыполнением и нежелательным недовыполнением (например, рассмотрение избыточной прибыли как проблемы) приводит к некорректно заданным штрафам за отклонения.
- Объединение целей с очень разными единицами или порядками величины без нормализации приводит к тому, что функция достижения доминируется численно большими целями.
- Рассмотрение вывода GP как окончательного ответа без анализа чувствительности несет риск упущения влияния неопределенности весов на выбранное решение.
Часто задаваемые вопросы
Чем MOGP отличается от стандартной многокритериальной оптимизации?
Стандартная многокритериальная оптимизация ищет полный Парето-фронт без фиксации целей, тогда как MOGP привязывает каждый критерий к конкретному целевому уровню и минимизирует отклонения от этих уровней, выдавая одно компромиссное решение, соответствующее заявленным целям.
В чем разница между взвешенным и лексикографическим целевым программированием?
Взвешенное GP объединяет все переменные отклонений в одну взвешенную сумму, находя компромисс между целями. Лексикографическое GP упорядочивает цели по строгим уровням приоритетов и последовательно оптимизирует каждый уровень, никогда не жертвуя целью более высокого приоритета ради цели более низкого.
Может ли MOGP обрабатывать нелинейные целевые функции?
Да, но с увеличением вычислительных затрат. Нелинейное MOGP требует нелинейных решателей, и выпуклость больше не гарантируется, поэтому глобальная оптимальность может быть не обеспечена. Линеаризация или кусочно-линейные аппроксимации являются распространенными решениями.
Как следует определять веса целей?
Веса должны отражать предпочтения лиц, принимающих решения, и могут быть получены путем прямого оценивания, парного сравнения (AHP) или анализа чувствительности методом проб и ошибок. Прозрачность в отношении выбора весов имеет решающее значение для принятия заинтересованными сторонами.
Является ли решение целевого программирования всегда Парето-оптимальным?
Не обязательно. Решение взвешенного GP может быть слабо Парето-оптимальным, но не строго таковым, особенно если некоторые веса равны нулю. Рекомендуется использовать положительные веса для всех отклонений и проверять наличие доминируемых решений.
Похожие методы
Источники
Charnes, A., Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. Wiley, New York.
ISBN: 978-0471148258Скопировано.Jones, D., Tamiz, M. (2010). Practical Goal Programming. Springer, New York.
Открыть ссылку DOIСкопировано.