Skip to content
Назад к результатам поиска

Многокритериальное линейное программирование (МКЛП)

Автор метода
Steuer, R. E.; Charnes, A.; Cooper, W. W.
Год
1955–1986
Тип
Mathematical optimization / vector optimization
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Многокритериальное линейное программирование (МКЛП) расширяет классическое линейное программирование, позволяя одновременно обрабатывать несколько конфликтующих линейных целевых функций в допустимой области, определяемой линейными ограничениями.

Вместо единственного оптимального решения МКЛП строит Парето-эффективную границу, из которой лицо, принимающее решения, выбирает предпочтительный компромисс. Оно является основополагающим в исследовании операций и науке управления для задач распределения ресурсов, планирования и проектирования с конкурирующими целями.

Интуиция метода

В обычном линейном программировании минимизируется одна стоимость или максимизируется одна прибыль, но реальные решения почти всегда включают несколько конкурирующих целей — минимизировать стоимость при максимизации уровня обслуживания и минимизации выбросов. МКЛП признает, что ни одно решение не является наилучшим по всем целям одновременно. Оно отображает полную границу недоминируемых (Парето-эффективных) решений, где улучшение одной цели неизбежно ухудшит другую. Затем лицо, принимающее решения, использует информацию о предпочтениях — веса, уровни притязаний или интерактивные запросы — для выбора окончательного решения из этой границы, делая компромиссы явными, а не скрытыми внутри составного показателя.

История

Теоретические основы многокритериального линейного программирования восходят к работам Чарнса и Купера 1950-х годов по целевому программированию и Купманса по эффективному производству. Учебник Штойера 1986 года систематизировал эту область, обобщив методы взвешенной суммы, эпсилон-ограничений и интерактивные методы, которые остаются стандартными и сегодня. МКЛП в настоящее время является основной темой в учебных программах по исследованию операций по всему миру.

Когда применять

Используйте МКЛП, когда задача имеет несколько конкурирующих линейных целей и линейных ограничений, данные являются непрерывными и точно известными (или могут рассматриваться как детерминированные), и лицу, принимающему решения, необходимо явно понимать компромиссы, а не принимать предварительно агрегированный показатель. Типичные области применения включают производственное планирование, распределение портфеля, маршрутизацию транспорта и бюджетирование государственных ресурсов. НЕ используйте, когда цели или ограничения нелинейны (вместо этого используйте многокритериальное нелинейное программирование или метаэвристики), когда данные дискретны или бинарны (используйте многокритериальное целочисленное программирование), когда количество целей превышает пять или шесть (эффективная граница становится вычислительно громоздкой), или когда лицо, принимающее решения, не желает участвовать в итеративном выявлении предпочтений.

Ограничения и замечания

  • Ограничено линейными целевыми функциями и линейными ограничениями; реальные задачи часто нелинейны.
  • Эффективная граница может содержать экспоненциально много крайних точек в более высоких измерениях, что делает исчерпывающий перебор непрактичным.
  • Требует точных числовых данных; неопределенность или нечеткость в коэффициентах не обрабатывается изначально.
  • Интерактивные методы сильно зависят от доступности лица, принимающего решения, и его способности последовательно выражать предпочтения.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Строит полную Парето-эффективную границу, предоставляя лицам, принимающим решения, полную картину компромиссов.
  • Вычислительно разрешимо для задач умеренного размера с помощью симплекс-методов.
  • Гарантирует математическую оптимальность каждой точки на эффективной границе.
  • Хорошо поддерживается зрелым программным обеспечением (CPLEX, Gurobi, альтернативы с открытым исходным кодом).
  • Компромиссы делаются явными, а не сводятся к непрозрачному составному индексу.

Применение

  • Планирование производства, балансирующее затраты, пропускную способность и использование ресурсов.
  • Оптимизация портфеля, учитывающая доходность, риск и ликвидность.
  • Проектирование транспортных и логистических сетей с конкурирующими целями по стоимости и обслуживанию.
  • Планирование энергетических систем, минимизирующее затраты при соблюдении целевых показателей по выбросам и надежности.
  • Распределение ресурсов здравоохранения, балансирующее справедливость, эффективность и бюджетные ограничения.
  • Экологический менеджмент, одновременно оптимизирующий экономические и экологические показатели.

Как это работает

Как это работает

1

Сформулируйте k линейных целевых функций f1(x) до fk(x) и допустимую область X, определяемую линейными ограничениями-неравенствами и равенствами (Ax <= b, x >= 0). Определите, какие цели должны быть минимизированы, а какие максимизированы. Убедитесь, что все целевые функции и ограничения линейны относительно переменных решения.

Формула
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

Сгенерируйте набор Парето-эффективных (недоминируемых) решений. Общие подходы включают метод взвешенной суммы (изменение весов по симплексу), метод эпсилон-ограничений (оптимизация одной цели при ограничении других) и метод Чебышева. Каждый подход отслеживает часть или всю эффективную границу.

3

Примените технику скаляризации для преобразования векторной задачи в последовательность одноцелевых задач ЛП. В подходе взвешенной суммы решите min sum(wi * fi(x)) для систематически варьируемых весовых векторов. Запишите каждую эффективную крайнюю точку пространства целей.

Формула
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

Соберите эффективные крайние точки и соединяющие их ребра для характеристики границы Парето. Проанализируйте диапазон каждой цели по всей границе, чтобы понять величину компромиссов. Представьте границу лицу, принимающему решения, в виде таблиц или би-целевых графиков.

5

Привлеките лицо, принимающее решения, для выбора предпочтительного решения из эффективного множества. Интерактивные методы (STEM, NIMBUS) чередуют представление решений и запрос лицу, принимающему решения, выразить предпочтения, сходясь к окончательному выбору, который наилучшим образом отражает его приоритеты.

Частые ошибки

  • Использование фиксированных весов в скаляризации взвешенной суммы и сообщение только об одном решении скрывает границу и противоречит цели МКЛП.
  • Путаница Парето-эффективности с оптимальностью: каждая точка на границе эффективна, но ни одна не является глобально «лучшей» без информации о предпочтениях.
  • Пренебрежение проверкой ограниченности допустимой области; неограниченная задача не дает конечного эффективного множества.
  • Рассмотрение МКЛП как «черного ящика» без привлечения лица, принимающего решения, к выбору приводит к произвольным окончательным решениям.
  • Применение МКЛП к задачам, по своей сути являющимся целочисленными, без перехода к многокритериальному целочисленному программированию, что приводит к решениям, нарушающим целочисленность.

Часто задаваемые вопросы

Чем МКЛП отличается от целевого программирования?

Целевое программирование — это частный случай или вариант: оно преобразует каждую цель в уровень притязаний, а затем минимизирует отклонения от этих целевых значений, давая единственное решение. МКЛП в своей общей форме стремится охарактеризовать полную эффективную границу без предварительного указания целевых уровней, предоставляя лицу, принимающему решения, большую гибкость.

Может ли МКЛП обрабатывать более двух целей?

Да, но Парето-граница становится труднее для визуализации при более чем двух или трех целях, а количество эффективных крайних точек может расти экспоненциально. Интерактивные методы и методы репрезентативных подмножеств рекомендуются для четырех и более целей.

Что, если мои данные неопределенны?

Стандартное МКЛП предполагает детерминированные коэффициенты. Неопределенность может быть учтена путем расширения до стохастического многокритериального линейного программирования (ограничения по вероятности, сценарные подходы) или робастной многокритериальной оптимизации, которые являются отдельными методами.

Является ли МКЛП тем же, что и многокритериальная оптимизация?

МКЛП — это частный случай многокритериальной оптимизации, где все цели и ограничения линейны. Многокритериальная оптимизация — это более широкая область, которая также включает нелинейные, целочисленные и комбинаторные варианты.

Какой метод скаляризации мне следует использовать?

Метод взвешенной суммы прост, но пропускает невыпуклые части границы. Метод эпсилон-ограничений может восстановить полную границу даже для невыпуклых областей и обычно предпочтителен для тщательного анализа. Интерактивные методы лучше всего подходят, когда возможно участие лица, принимающего решения.

Похожие методы

Источники

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    ISBN: 9780471888468
    Скопировано.
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

    Открыть ссылку на публикацию
    Скопировано.