22:33
Методика решения многокритериальных задач

Задача линейной многокритериальной максимизации

   Сформулируем задачу линейной многокритериальной максимизации с двумя переменными и двумя целевыми функциями.

  Пусть на плоскости  задано множество  (Рис. 1) и в каждой точке этого множества определены две непрерывные функции L1=f1(x1, x2)  и  L2=f2(x1, x2) . Необходимо найти значения переменных, при которых указанные функции принимают наибольшие значения. Формулировку задачи максимизации с двумя целевыми функциями можно записать более компактно:

f1(x1, x2) → max

f2(x1, x2) max

при ограничениях:

(x1, x2) ϵ

 

Алгоритм решения многокритериальной задачи:

1) Изобразим на плоскости  все точки, координаты которых удовлетворяют условиям L1=f1(x1, x2)  и  L2=f2(x1, x2)  и (x1, x2) ϵ . Полученное множество обозначим через  (рис. 2).

 

    Из рис. 2 видно, что (L1)max— наибольшее значение  — L1  и (L2)max— наибольшее значение  — L2, достигаются в разных точках. При этом ((L1)max,(L2)max) .

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

  1. Метод (последовательных) уступок.
  2. Метод идеальной точки (пример).

В рассматриваемом случае множество Парето составлено из допустимых точек задачи, которые не могут быть перемещены в пределах допустимого множества с улучшением сразу по двум критериям: улучшение значения одного критерия влечет ухудшение значения другого.

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

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

Замечание. Задачу максимизации можно путем умножения целевой функции на (–1) преобразовать в задачу минимизации, решаемую при тех же самых ограничениях. Это связано с наличием следующего свойства: функция достигает наибольшего значения в тех точках, в которых функция f принимает наименьшее значение, и наоборот. Это означает, что условия [f → min] и [(- f )  → max] равносильны. Следовательно, поменяв знак целевой функции на противоположный, любую двухкритериальную задачу можно свести к задаче максимизации с двумя целевыми функциями.

 

Категория: Линейное программирование | Просмотров: 4974 | Добавил: Admin | Теги: ОР и ОДР, симплекс метод, транспортная задача, линейное програмирование | Рейтинг: 5.0/1
Всего комментариев: 0
avatar