XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 6
Текст из файла (страница 6)
На первый взгляд простейшим выходом из сложившейся ситуации является сведение некорректной задачи многокритеризльной оптимизации (1.2) к соответствующей задаче математического программирования путем выделения из множества скалярных целевых функций (Л,(Х))„м, одной основной и использования остальных для формирования дополнительных ограничений, накладываемых на множество С допустимых решений (т.е. путем выделения из множества скалярных критериев одного основного критерия оптимальности и перевода остальных критериев в разряд ограничений). Трудоемкость и проблематичность корректной реализации обсуждаемого подхода в общем случае связана как с трудностями выбора одной основной целевой функции Л(Х) из множества скалярных целевых функций (Л(Х))~™ „так и с обоснованным назначением верхних границ (Ло> ., Л-цо> Л+цо, ", Х о) для скалярных критериев, переводимых в ограничении: Л(Х) < Ло, ~' б (1, ..., 1 — 1, г+1, ..., т).
Перейдем к рассмотрению иных подходов к решению задач многокритеризльной оптимизации. Будем говорить, что допустимое решение Х> Е С задачи многокритериальной оптимизации (1.2) является ст«рово более «ред«онтительным, чем допустимое решение Хг б С, и писать Х1 ~- Хг, если г(Х1) < < 1'(Хг). Последнее неравенство означает, что Л(Х>) < Л,(Хг), и = 1, т, причем среди этих т неравенств есть хотя бы одно строгое. Допустимые решения Хм Хг б С задачи многокри- териальной оптимизации (1.2) будем называть энвиввлентными решениями и писать Х1 Хг, если г"(Х1) = ЦХг). Отметим, что: а) в общем случае из Х1 ° Хг не следует Х, = Х б) если допустимое решение Х1 является строго более предпочтительным, чем допустимое решение Хг, а допустимое решение Хг является строго более предпочтительным, чем допустимое решение Хз, то допустимое решение Х> является строго более предпочтительным, чем допустимое решение Хз, т.е.
((Х1 'г- Хг) д (Хг е- Хз)) =е (Х~ >- Хз); в) если Х1 и Хг — эквивалентные решения, Хг и Хз — также эквивалентные решения, то Х> и Хз будут эквивалентными решениями, т.е. ((Х, ° Хг) д (Хг Хз)) ~ (Х, - Хз). Пусть теперь множество возможных значений векторной целевой функции г в задаче многокритеризльиой оптимизации (1.2), порождаемое множеством С допустимых решений. Для удобства графических иллюстраций полагаем, что т = 2, и произвольным образом выбираем допустимое решение Хо б .%С, которому соответствует значе- .
1~ 1 У1Хо1 т У21Х01 "ние ~(Хо) = (Л(Хо) гг(Хо)) целе- гг вой функции 1'(Х) = (Л(Х) 1г(Х)) (рис. 1.3). Пусть Й' — заштрихованная на рис. 1.3 часть множества О у 1т 1 у>1 о1 у1 Й и С = г (Й ) — соответствувпцее подмножество множества Ь 38 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИИ допустимых решений. На рис. 1.3 видно, что г'(Х ) (г'(Хо) Х Е С . Х ~-Хо, Х' ЕС)СС. Продолжая эти рассуждения, приходим к выводу, что из множества Й, определяемого согласно (1.3), можно выделить подмножество Й", которое обладает очень ценными свойства- ми: 1) для допустимых решений из множества С'=1 '(Й ) СС (1.4) в множестве С допустимых решений задачи многокритериальной оптимизации (1.2) уже нет строго более предпочтительных допустимых решений; 2) допустимые решения из множества С' либо эквивалентны, либо несопоставимы в смысле строгой предпочтительности.
Множество й' обычно называют множеством Паретпо или множеством компромисса. На рис. 1.4 множество й' выделено жирной линией и представляет собой дугу АСВ, которая является частью границы Г1) множества й. При перемеще- А нии точки С от точки А до точки В значения скалярного критерия Г1 увеличиваются, а значения скаи11и~г1~ю) ------ лярного критерия )г уменьшаются. Таким образом, уменьшение значе- О п11пу (Х ) У1 ний одного из скалярных критериев может быть достигнуто лишь хао 1 Рис.
1.4 Таким образом, любое допустимое решение из множества С1 С С является строго более предпочтительным, чем допустимое решение Хо Е С, т.е. 1.2. Об одном аспекте мпогокритериааьной оптимиэаипп 39 ценой увеличения значений другого. Аналогичная картина наблюдается и в общем случае, так как любые допустимые решения Х1, Хг Е С" либо эквивалентны, и для них Г'(Х1) = = Г(Хг), либо несопоставимы, т.е.
для пар координат Д(Х1), Д(Хг), И= 1, т, векторов Г(Х1), Г(Хг) имеют место хотя бы два из следующих трех соотношений: Г) (Х1) > 1)(Хг), Т" (Х1) = =Л(Х,), У„(Х,) < Гп(Х,). Подмножество С' множества С допустимых решений, определяемое согласно (1.4), можно считать обобщенным решенаем задача мнояократераальног2 оптимизации (1.2). Это обобщенное решение в общем случае может состоять более чем из одного элемента, и тогда, лицо, принимающее решения ", сталкивается с проблемой выбора одного допустимого решения из некоторого множества эквивалентных и несопоставимых решений. Естественно, что решение задачи многокритериальной оптимизации следует искать среди элементов обобщенного решения. Чтобы выбрать один из элементов обобщенного решения, нужно использовать дополнительную информацию.
Остановимся на том, каким образом можно задействовать дополнительную информацию. Ранжировка критериев. Дополнительная информация, помогающая в выборе решения, может ~остоять в том, что скалярные целевые функции ЯХ), й = 1, т, в задаче векторной оптимизации (1.1) упорядочены в соответствии с их значимостью. В этом случае номер целевой функции отражает раня (приоритет) соответствующего скаллрнояо «ритерая. Пусть й' — множество Парето для задачи векторной оптимизации (1.1) и номер скалярной целевой функции ~а(Х), где к = 1, т, соответствует ее рангу. Процедуру выбора единственного решения из подмножества С' множества С допустимых решений, определяемого согласно (1.4), начнем с использования критерия первого ранга. Полагаем 41 = щ)в 21(Х), С; = ~1 1(о1)1) С', ХЕС' рь = пнп ~ь(Х) ХЕО' д„, 1= ппп 1,„г(Х), ХЕО' в множестве С'.
Если пз-1 (Х) -+ ш1п ХеО' (Х) — ~ ппп. Хая Рис. 1.6 40 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ т.е. С1 содержит все допустимые решения из С', которые минимизируют в С' целевую функцию первого ранга. Далее переходим к целевой функции второго ранга и полагаем дг = ш1п ~г(Х) Сг =1г (дг) ПС1 хеО( т.е.
множество С' содержит все допустимые решения из С, которые минимизируют в С1 целевую функцию второго ранга, и т.д. Переходим к целевой функции (т — 1)-го ранга и полагаем т.е. множество С' 1 содержит все допустимые решения из С', которые минимизируют в С* г критерий (т — 1)-го ранга. Так как С' с С* С ... С С* С С*, то для завершения процедуры решения задачи (1.1) многокритериальной оптимизации в условиях ранжировки критериев осталось решить задачу математического программирования На рис. 1.5 эта процедура иллю- стрируется для случая т = 2. Мноч жество Парето выделено жирной линией и состоит из отрезка АВ и дуги АС. Множеству С1 соответствует часть множества ПареРис.
1Л то, состоящая из отрезка АВ, и на втором шаге мы приходим в точку А, которая соответствует оптимальному (в смысле рассматриваемой процедуры) решению. Из проведенных рассуждений и рис. 1.5 следует, что для реализуемости предложенной процедуры решения задачи многокритериальной оптимизации подмножеству С' множества С допустимых решений должно соответствовать подмножество 1.2. Об одном аспекте многокритериельной оптимизации 41 множества Парето, состоящее более чем из одного элемента. Так как в общем случае это условие может не выполняться (см. рис. 1А), то на практике для решения задачи многокритериальной оптимизации чаще используют метод, известный как метод момпромиссов.
Предположим, что для скалярной целевой функции (ь(Х) назначена дозгустимал устрезма 5л > О, которая определяет величину допустимого отклонения значения критерия и-го ранга от его минимального значения на множестве С' (см. (1.4)). Очевидно, что для каждого й= 1, т — 1 уступка бл определяет некоторое подмножество С(бл) = (Х Е С'.
~л(Х) ( рл+ бе) то для нахождения оптимального (в смысле рассматриваемой процедуры) решения нам осталось лишь решить задачу мате- матического программирования: Эхо показано на рис. 1.6 при тее 2. Решение двухкритериальной задачи соответствует точке С множества Парето, выделенного жирной линией. При т > 2 множество д может о1свзаться пустым. В этом случае Уступки выбраны неудачно и необ1недима их коррекция. 42 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ 1.3. 06 одном аспекте многокритериаа,ной оптимизации 43 Завершая описание этого подхода к решению задачи многокритеризльной оптимизации, отметим, что его практическая реализация связана по крайней мере с двумя принципиальными трудностями: 1) необходимостью ранжирования скалярных критериев; 2) назначением уступок и их коррекцией.
Обе операции формально не определяются и выполняются экспертным путем. Обращение к экспертам неизбежно при решении задач многокритериальной оптимизации, так как необходима дополнительная информация, позволяющая ввести отношение предпочтения на подмножестве с" множества О допустимых решений, которое соответствует множеству Парето й' С й. К сожалению, процедуры ранжирования скалярных критериев и определения уступок по ним не всегда просты для экспертов.
Поэтому применение рассмотренного подхода, как правило, ограничивают лишь теми ситуациями, в которых эксперты могут квалифицированно преодолеть обе отмеченные т руд иост и. П р ниц и п справедливой абсолютной уступ к н. Согласно этому принципу, справедливым является такой компромисс, при котором суммарный абсолютный уровень повышения одного или нескольких скалярных критериев не превосходит суммарного абсолютного уровня снижения других критериев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
