Многокритериальные задачи; метод последовательных уступок

ЛЕКЦИЯ 8. Многокритериальные задачи (продолжение) Метод последовательных уступок Другой способ носит название метода последовательных уступок. В этом методе критерии нумеруются в порядке убывания важности. Пусть критерии f1 , f 2 ,..., f K записаны в порядке уменьшения их важности. Тогда должны быть выполнены следующие действия. 1-й шаг. Решается однокритериальная задача по 1-му критерию: z1*  max f1 ( X ) . XD 2-й шаг. Назначается разумная с инженерной точки зрения уступка z1 , составляется и решается новая задача оптимизации по 2-му критерию: z 2*  max X D f1  X  z1*  z1 f2 (X ) . 3-й шаг. Назначается уступка для 2-го критерия z 2 , составляется и решается задача оптимизации по 3-му критерию: z 3*  max X D f1  X  z1*  z1 f 2  X  z *2  z 2 f3 ( X ) . Процесс назначения уступок по каждому критерию и решения однокритериальных задач продолжается, пока не дойдем до последнего K -го шага. K -й шаг. Назначается уступка для ( K  1)-го критерия z K 1 , состав- ляется и решается задача оптимизации по последнему K -му критерию: 10 z K*  max X D f1  X  z1*  z1 f 2  X  z *2  z 2 .... f K 1  X  z *K 1  z K 1 fK (X ) . Основной недостаток методов, использующих ограничения на критерии, состоит в субъективности выбора контрольных показателей и в субъективности выбора уступок. При использовании метода последовательных уступок следует помнить, что уступки могут быть несоизмеримы между собой, поэтому надо предварительно организовать нормировку критериев. Кроме того, в общем случае уже со 2-го шага решение может оказаться не оптимальным по Парето. Пример 5. Рассмотрим сначала однокритериальную задачу, заключающуюся в максимизации общей прибыли от реализации готовой продукции. На лесоперерабатывающем предприятии установлено три группы оборудования (строгальные, фрезерные и шлифовальные станки). На этих станках производится два типа продукция: шкафы и столы. Известны нормы затрат машинного времени, эффективный фонд времени станков, прибыль от реализации единицы продукции (таблица 2). Таблица 2 Станки Строгальные Фрезерные Шлифовальные Прибыль, ден.ед. Затраты машинного времени на обработку одного изделия, час Шкаф Стол 4 3 2 1 2 3 8 7 Фонд времени станков, час 144 64 120 Определить количество изделий каждого вида, которое необходимо изготовить на предприятии с целью получения наибольшей общей прибыли от реализации готовой продукции. 11 Количество шкафов и столов, которое необходимо изготовить на предприятии, обозначим соответственно через x1 и x2 . Общая прибыль от их изготовления выражается функцией z  8 x1  7 x 2 . (*) Определим фактическую загрузку по каждой группе оборудования. Она будет равна 4 x1  3 x 2 – для строгальных станков, 2 x1  x 2 – для фрезерных станков, 2 x1  3 x 2 – для шлифовальных станков. Коэффициенты при неизвестных обозначают здесь нормы затрат машинного времени на обработку одного шкафа и одного стола соответственно. Ресурсы машинного времени ограниченны. Следовательно, загрузка по каждой группе оборудования не должна превышать имеющихся ресурсов машинного времени. Математически это означает, что 4 x1  3x 2  144  2 x1  x 2  64 . 2 x  3x  120 2  1 (**) Ограничительные условия для решения данной задачи мы получили в виде системы линейных неравенств (**). Очевидно, что неизвестные задачи являются целыми числами и удовлетворяют условиям x1  0 , x 2  0 . (***) Таким образом, математическая модель задачи состоит в максимизации целевой функции (*) при условиях, что неизвестные x1 и x 2 удовлетворяют системе ограничений (**) и неравенствам (***). Согласно оптимальному плану предприятие должно изготовить 12 шкафов и 32 стола, и наибольшая прибыль составит 320 ден.ед. 12 Дополнительно предположим, что предприятие заинтересовано в эффективном использовании оборудования. При этом известны цены за 1 час простоя оборудования каждого вида: для строгальных станков – 3 ден.ед., для фрезерных станков – 9 ден.ед., для шлифовальных станков – 2 ден.ед. Требуется составить задачу оптимизации с двумя критериями и решить ее методом уступок. Обозначим через z 2 суммарные издержки предприятия за простой оборудования. Поскольку время простоя равно 144  (4 x1  3x 2 ) – для строгальных станков, 64  (2 x1  x2 ) – для фрезерных станков, 120  (2 x1  3x 2 ) – для шлифовальных станков, то суммарные издержки равны z 2  3144  4 x1  3x 2   964  2 x1  x 2   2120  2 x1  3x 2  , или z 2  34 x1  24 x 2  1248  min . (4) Система ограничений (**), (***) при этом не изменяется: 4 x1  3x 2  144  2 x1  x 2  64 , 2 x  3x  120 2  1 (5) x1  0 , x 2  0 . (6) Задача оптимизации по второму критерию (4) – (6) решается в Excel с использованием средства «Поиск решения». Исходные данные и результаты оптимизации показаны на рисунке 5. 13 Рисунок 5 – Исходные данные и результаты решения задачи (4) – (6) Отметим, что целевая функция (4) содержит свободный член, поэтому в ячейку D6 помещается одна из формул таблицы 3. Таблица 3 = B6*B4+C6*C4+1248 или =СУММПРОИЗВ(B6:C6;B4:C4)+1248 На рисунке 5 представлен оптимальный план выпуска мебели по критерию минимизации издержек за простой оборудования: предприятие должно изготовить 24 шкафа и 16 столов. При этом минимальные издержки составят z 2,min  48 ден.ед. Как видим, этот план существенно отличается от оптимального плана по критерию общей прибыли. Решим теперь задачу с двумя критериями методом уступок. Для первого критерия z назначим уступку z  8 , и в математическую модель (4) – (6) добавим еще одно ограничение z  320  8  312 . Тогда получим новую задачу оптимизации по второму критерию: z 2  34 x1  24 x 2  1248  min (7) при ограничениях 14 4 x1  3x 2  144 2 x  x  64  1 2 ,  2 x  3 x  120 2  1 8 x1  7 x2  312 (8) x1  0 , x 2  0 . (9) Организация исходных данных задачи (7) – (9) на листе Excel приведена на рисунке 6. Рисунок 6 – Исходные данные и результаты решения задачи МКО В результате получен компромиссный план выпуска мебели, состоящий в изготовлении 18 шкафов и 24 столов. Издержки за простой оборудования составят z 2  60 ден.ед., а общая прибыль предприятия будет равна z  312 ден.ед. 15 Методы целевого программирования Название этой группы методов связано с тем, что ЛПР задает определенные цели f1 , f 2 ,..., f K для каждого критерия. Задача МКО в этом случае преобразуется в задачу минимизации суммы отклонений с некоторым показателем p :  K z    wk f k  X   f k  k 1 1 p p   min (при XD),  (10) где wk – некоторые весовые коэффициенты, характеризующие важность того или иного критерия. Задачу (10) можно конкретизировать в зависимости от значений параметра p и заданных целей. В частности, при p  2 и wk  1 получим задачу минимизации суммы квадратов отклонений: z   f k  X   f k* K 2 k 1  min (при XD), в которой минимизируется евклидово расстояние от множества достижимости F до «абсолютного максимума» f *   f1* , f 2* ,..., f l *  в пространстве критериев. Здесь f k*  max f k  X  . X D Осложнения, обусловленные несоизмеримостью величин f k  X   f k* , можно преодолеть с помощью нормировки критериев, рас- сматривая следующую задачу оптимизации:  f k  X   f k*  z   f k* k 1   K 2     min (при XD).  (11) Пример 6. Методом целевого программирования решить задачу МКО из примера 3. 19 В условиях примера 3 имеем f1*  2 , f 2*  1, поэтому задача (11) принимает вид z x1  22 x2  12 4  1  min при условиях  x1  2 x 2  2 .  x  , x   1 2 При постоянном значении z линии уровня целевой функции x1  22 x 2  12   1 представляют собой эллипсы с центром в точке z2 2 z 2 M 2; 1 и полуосями a  2 z и b  z . Необходимо найти минимальное значение z , для которого соответствующий эллипс будет иметь общие точки с областью D. На рисунке 7 показано графическое решение данной задачи. Рисунок 7 – Решение задачи методом целевого программирования   Оптимальной является точка X *  1; 1 . 2 20 Методы гарантированного результата Рассматриваются методы, которые дают наилучший результат даже для самого наименьшего из критериев, а именно, компромиссное решение находится путем решения следующей задачи оптимизации: z  min f k  X   max при X  D . k 1, 2 ,..., K Это есть максиминная задача. С учетом нормировки критериев методы гарантированного результата образуют наиболее перспективное направление в решении задач МКО. Для нормированных критериев k ( X )  fk (X ) fk * , где f k*  max f k ( X ) , X D максиминная задача формулируется в виде: z  min k  X   max (при X  D ). k 1, 2 ,..., K (12) Остановимся на рассмотрении двух случаев, когда критерии равнозначны и неравнозначны (с заданным приоритетом). Равнозначные критерии Задача (12) эквивалентна задаче z    max (13) при условиях   k  X , k  1,2,..., K .  X  D  (14) Задача (13) – (14) называется  -задачей. Она имеет линейную целевую функцию и m  K ограничений. Если все функции f k и g i линейны, то  -задача относится к линейному программированию. В этом случае доказано, что оптимальное решение X *  -задачи оптимально по Парето. 21 Пример 7. Требуется решить задачу из примера 3 методом гарантированного результата с равнозначными критериями. Составим  -задачу: z    max при условиях x1     2   x . 2   x1  2 x2  2   x1  0, x 2  0,   0   Оптимальное решение этой задачи есть X *  1; 1 , *  1 . 2 2 Критерии с заданным приоритетом Рассмотрим только два критерия f1  X  и f 2  X  , и пусть 1  X  и 2  X  – соответствующие нормированные критерии. Разобьем допустимую область на две части D  D1  D2 так, что в области D1 выполняется неравенство 1  X   2  X  , то есть первый критерий имеет приоритет над вторым, а в области D2 выполняется неравенство 1  X   2  X  , то есть второй критерий имеет приоритет над первым. Для числовой характеристики приоритета вводится коэффициент связи p  X  : 1  X   p X 2  X  , который показывает, во сколько раз относительная оценка 1  X  больше  2  X  . Если X * – оптимальная точка для равнозначных критериев, то pX *   1 . Если X 1* – точка оптимума по первому критерию, то 1 X 1*   1 , 2 X 1*   1 , то есть X 1*  D1 , и значит pX 1*   1 . Аналогично, если X 2* – точка оптимума по второму критерию, то 1 X 2*   1 ,  2 X 2*   1 , и значит pX 2*   1 . 22 Предположим, что первый критерий имеет приоритет над вторым. Тогда коэффициент p  X  необходимо задать в интервале 1; p X 1*  , а затем составить и решить  -задачу, включив в систему ограничений равенство 1  X   p X 2  X  . В результате получим точку X * , которая будет принадлежать множеству D1 , где первый критерий имеет приоритет над вторым. Доказано, что для выпуклых задач МКО точка X * , являющаяся решением  -задачи, единственная и оптимальна по Парето. Пример 8. Требуется решить задачу из примера 3 методом гарантированного результата с неравнозначными критериями при условии, что первый критерий имеет приоритет над вторым. Так как pX 1*   X 1*  2; 0 , то 1 X 1*   1 , 2 X 1*   0 , следовательно, 1   . В интервале 1;   зададим коэффициент связи p X   2 . Тогда 1  X   22  X  , или x1  2 x2 . 2 Составим  -задачу: z    max при условиях x1     2    x 2  x 1 .   2 x2 2   x1  2 x 2  2  x  0, x  0,   0 2  1  23 В результате решения задачи получим оптимальное решение   X *  4 ; 1 , *  1 . 3 3 3 Недостаток рассмотренного метода состоит в субъективности задания коэффициента связи p  X  . Решение задачи МКО методом гарантированного результата, как правило, проходит следующие этапы. 1. Разработка математической модели системы на основе заданных целей и ограничений; при этом часто используется мнение экспертов. 2. Предварительный анализ системы отдельно по каждому крите- рию; используются методы и программные средства оптимизации с одним критерием. 3. Нормировка критериев. 4. Решение задачи МКО при равнозначных критериях. 5. Задание приоритетов критериев и решение задачи МКО с назна- ченными приоритетами. 24