WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Министерство образования Российской Федерации РОСТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ С.В.Гусаков, Л.Н.Землянухина, А.Б.Зинченко, Г.Г.Мермельштейн, Л.И.Сантылова МЕТОДИЧЕСКИЕ УКАЗАНИЯ по курсу "Методы оптимизации" для студентов механико-математического факультета дневного и вечернего отделения ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И СМЕЖНЫЕ ВОПРОСЫ Часть 9 Ростов-на-Дону 2002 Методические указания рекомендованы к печати заседанием кафедры исследования операций механико-математического факультета РГУ : протокол № 10 от 4 июня 2002 г.

3 ОГЛАВЛЕНИЕ 12. Многокритериальная задача оптимизации (продолже- ние)………...…………………………………………………. 4 12.6 Ранжирование критериев………….………….……… 4 12.7. Метод последовательных уступок(компромиссов).. 6 12.8. Примеры решения многокритериальной задачи методом последовательных уступок…………….….. 7 12.9. Метод идеальной точки ……………………………... 15 12.10. Упражнения………………………………………….. 19 12.11. Индивидуальные задания…………………………… 21 Литература …………………………………………………... 24 4 12. МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА ОПТИМИЗАЦИИ (продолжение) В части 8 методических указаний была рассмотрена основная концепция решения многокритериальной задачи - сведение ее к однокритериальной задаче путем построения линейной свертки или свертки Гермейера. Такой подход позволял в определенных случаях свести многокритериальную задачу к однопараметрической задаче линейного программирования с параметром в целевой функции и найти все множество Парето. В данной части предлагается ознакомиться с иными подходами:

1. методом, основанном на ранжировании критериев и позволяющем найти лексикографически оптимальное решение;

2. методом последовательных уступок, в котором величина уступки является мерой отклонения приоритета частных критериев от жесткого лексикографического и использование которого в ряде случаев сводит многокритериальную задачу к однопараметрической линейной задаче с параметром в правых частях ограничений;

3. методом идеальной точки, результат использования которого существенно зависит от выбираемой метрики.

12.6. Ранжирование критериев Пусть все критерии можно ранжировать (строго упорядочить) по важности так, что при последовательном рассмотрении критериев вначале используется первый (наиболее важный с точки зрения ЛПР) критерий, затем второй и т.д. Это позволяет на множестве допустимых решений задать лексикографическое отношение предпочтения.

Определение 5. Допустимое решение x лексикографически предпочтительнее допустимого решения x,если выполняется одно из условий:

1) f1(x) > f1(x), (4) 2) i fi+1(x) j j Если fi(x) = fi(x) для всех i=1,…,m, то допустимые решения x,x лексикографически эквивалентны.

Определение 6. Допустимое решение x лексикографически оптимальное, если не существует допустимого решения x, для которого выполняется условие (4).

Найти лексикографически оптимальное решение многокритериальной задачи можно, решив следующую последовательность задач:

* 1) найти maxf1(x) = f1 в области x X;

* 2) найти max f2(x) = f2 в области, задаваемой условиями * x X; f1(x) = f1 ; (5) ……………………………………………………………….

* m) найти max fm(x) = fm в области, задаваемой условиями x X; fi(x) = fi*, i =1,m -1;

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

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

12.7. Метод последовательных уступок (компромиссов) Здесь так же, как и в предыдущем подходе, вначале производится качественный анализ относительной важности критериев. На основании такого анализа критерии нумеруются в порядке убывания важности.

Ищем максимальное значение первого критерия f1 ( x ) f1* на всем множестве допустимых решений. Затем назначаем величину «допустимого» снижения (уступки) 1 критерия f1 ( x ) и определяем наибольшее * значение второго критерия f ( x ) f при условии, что значение первого 2 критерия должно быть не меньше, чем - 1. Затем назначаем величину f1* «допустимого» снижения (уступки) 2 критерия f ( x ) и определяем * наибольшее значение третьего критерия f = f ( x ) при условии, что f 3 * значение второго критерия должно быть не меньше, чем - 2 и т. д.

f При этом оптимальным решением многокритериальной задачи считается всякое решение последней из задач последовательности:

* в области 1) найти maxf1(x) = f1 x X;

* в области, задаваемой условиями 2) найти max f2(x) = f* x X; f1(x) f1 - 1; (6) ……………………………………………………………….

* m) найти max fm(x) = fm в области, задаваемой условиями x X; fi(x) fi* - i, i = 1, m -1;

Очевидно, что если все i = 0, то метод уступок находит только лексикографически оптимальные решения, которые доставляют первому по важности критерию наибольшее на Х значение. В другом крайнем случае, когда величины уступок очень велики, решения, получаемые по этому методу, доставляют последнему по важности критерию наибольшее на Х значение. Поэтому величины уступок можно рассматривать как своеобразную меру отклонения приоритета частных критериев от жесткого лексикографического.



Метод последовательных уступок не всегда приводит к получению только эффективных точек, но среди получаемых этим методом точек всегда существует хотя бы одна эффективная. Это следует из следующих утверждений [2].

n Утверждение 3. Если XR - множество замкнутое и ограниченное, а функции fi(x) непрерывны, то решением m-й задачи из (6) является, по крайней мере, одна эффективная точка.

Утверждение 4. Если x - единственная (с точностью до эквивалентности) точка, являющаяся решением m-й задачи из (6), то она эффективна.

12.8. Примеры решения многокритериальной задачи методом последовательных уступок Пример 9. Решить методом последовательных уступок многокритериальную задачу из примера 3.

f1(x)=7x1 +2x3-x4+x5 max, f2(x)=x1-5x2-4x3+x4 max при ограничениях -x1 +x2 +x3 =2 ;

3x1 -x2 +x4 =3 ;

5x1+2x2 +x3+x4 +x5=11;

xi 0 для i=1,2,...,5.

Упорядочим критерии согласно их нумерации, то есть будем в начале работать с критерием f1 ( x ), а затем с критерием f ( x ).

При решении примера 3 методом искусственного базиса была получена симплекс-таблица (см. табл.3). Возьмем ее в качестве начальной, вычислив относительные оценки для функции f = f1 ( x ). Получим таблицу 10. Таблица 11 определяет точку, доставляющую функции f1* f1 ( x ) наибольшее значение, равное 16.

Таблица 10. Таблица 11.

7 cв х1 x2 x4 xx3 -1 1 2 x3 1/3 2/3 -x4 3 -1 3 x1 1/3 -1/3 x5 3 2 6 x5 -1 3 f1 -9 5 7 f1 3 2 Далее переходим к решению задачи f2(x)=x1-5x2-4x3+x4 max при ограничениях исходной задачи, к которым добавлено новое * ограничение f1(x) f1 - :

-x1 + x2 + x3 =2, 3x1 - x2 +x4 =3, (7) 5x1+2x2 + x3+x4 +x5 =11, 7x1 +2x3 -x4 +x5 16-, xi0 для i=1,2,...,5.

Новое ограничение преобразуем в равенство и заменим переменные x1, x3, x5, используя таблицу 11, выражениями x1=1/3x2 -1/3x4 +1, x3=-2/3x2 -1/3x4 +3, x5=-3x2 +x4 +3.

В результате этих преобразований дополнительно введенное ограничение примет вид -2x2 -x4+x6 = -16+. Итак, получили задачу параметрического программирования с параметром в правой части ограничений.

В качестве начальной таблицы для задачи (7) можно использовать таблицу 12, которая получена из таблицы 11 в результате пополнения ее еще одной строкой и пересчета строки относительных оценок. Решим задачу (7) для произвольного параметра 0. Для этого столбец правых частей ограничений в таблице 12 представим в виде двух столбцов z, z:

zi0=zi+zi. При выборе главной строки в таблице 12 следует использовать значения из столбца z. Полученная далее таблица 13 является оптимальной при =0 и при всех значениях, удовлетворяющих условиям 3+(-1/9) 0, 1+(-1/9) 0, 3+1/3 0, 0+1/3 0.

Из этой системы неравенств получаем 0 9. При любом фиксированном значении параметра из отрезка [0,9] единственным решением задачи является точка x*=(1+(-1/9), 0, 3+(-1/9), 0+1/3, 3+1/3). А тогда, на основании утверждения 5 эта точка принадлежит множеству Парето.

Таблица 12. Таблица 13.

1 -св x4 x2 x6 xz z z z -x3 1/3 2/3 3 0 x3 -1/9 4/9 3 -1/x1 1/3 -1/3 1 0 x1 -1/9 -5/9 1 -1/x5 -1 3 3 0 x5 1/3 11/3 3 1/x6 3 2 0 1 x4 1/3 2/3 0 1/f2 -2 2 -11 0 f2 2/3 10/3 -11 2/При > 9 таблица 13 не является оптимальной, и нужно выполнить шаг двойственного симплекс-метода с главным элементом, стоящим на пересечение второй строки и первого или второго столбцов. Получим таблицу 14, из которой видно, что при > 9 решениями являются точки, доставляющие функции f2(x) значение –5. Таблица 14 определяет опорное ~ решение x =(0,0,2,3,6).

Таблица 14.

x1 xz z x3 -1 1 2 x6 -9 5 -9 x5 3 2 6 x4 3 -1 3 f2 6 0 -5 Найдем эти решения. Выберем главным столбец с 0-оценкой. В зависимости от главной строкой будет первая или вторая строка.

Если (-9+)/5 > 2, то главной строкой будет выбрана первая. А значит, ~ ~ следующей будет таблица 15. Она определяет опорное решение x = (0,2, 0,5, 2), если –19+0. Итак, если 19, то оптимальными решениями являются все точки выпуклой комбинации ~ x x x***= (1-)~ +~ =(0, 2, 2-2, 3+2, 6-4), где [0,1].

Таблица 15.

x1 xz z x2 -1 1 2 x6 -4 -5 -19 x5 5 -2 2 x4 2 1 5 f2 6 0 -5 Если (-9+ )/5 2, то главной строкой будет выбрана 2-я. А значит, следующей после таблицы 14 будет таблица 16. Таблица 16 определяет ~ ~ ~ решение x =(0, (-9+)/5, (19-)/5, (6+)/5, (48-2)/5), если –19+0. Итак, если 9<19, оптимальными решениями будут все точки выпуклой комбинации ~ ~ x x x** =(1-)~ +~ =(0;(-9+)/5;2-(-9+)/5;3+(-9+)/5;6-2(9+)/5), где [0,1].

В случае, когда оптимальное решение не единственно, не обязательно все эти решения являются эффективными точками, но среди них всегда есть хотя бы одна эффективная. Чтобы выделить из найденных оптимальных решений эффективные, сравним в этих точках значения критериев. Так как все эти решения получены при максимизации функции f2(x), то относительно второго критерия эти точки эквивалентны. Найдем значения функции f1(x):

f1( x***)=2(2-2)-( 3+2)+ 6-4=7-10, где [0,1] и 19;

f1( x** )=2(2-(-9+)/5)-(3+(-9+)/5)+6-2(-9+)/5= =7+((-9+)/5)(-2-1-2)= 7- (-9+), где [0,1] и 9<19.

x x x При =0 получаем x***=~ и x** =~ и, значит, f1( x***)

Таблица 16.

x1 xz z x3 4/5 -1/5 19/5 -1/x2 -9/5 1/5 -9/5 1/x5 33/5 -2/5 48/5 -2/x4 6/5 1/5 6/5 1/0 -5 f2 Окончательный результат формулируется следующим образом. В качестве решения многокритериальной задачи будут получены :





1) при 0 9 точка из множества Парето (эффективная точка) x*=(1+(-1/9), 0, 3+(-1/9), 0+1/3, 3+1/3), ~ 2) при 19 эффективная точка x =(0,0,2,3,6) и точки, не принадлежащие множеству Парето, но слабо эффективные, ~ x x x***= (1-)~ +~ =(0, 2, 2-2, 3+2, 6-4), где (0,1], ~ 3) при 9<19 эффективная точка x =(0,0,2,3,6) и точки, не принадлежащие ~ ~ x x множеству Парето, но слабо эффективные, x** =(1-)~ +~ = = (0;(-9+)/5;2-(-9+)/5;3+(-9+)/5;6-2(-9+)/5), где (0,1].

g Пример 10. Методом последовательных уступок найти решение задачи примера 2, считая, что критерии упорядочены по важности в последовательности {f2,f1}, и 2 =1.

Первая задача из последовательности (6) в данном случае имеет вид:

f2(x)=4x1 -x2 max, при ограничениях -x1 +x2 1, x1 +x2 3, x1 -2x2 0, x1 4, x2 3.

Решение этой задачи можно найти графически. Из рисунка 14 видно, что максимум критерия f2(x) на множестве X достигается в вершине * x5=(4,2) и =f2(x5)=14.

f Пример 10. Методом последовательных уступок найти решение задачи примера 2, считая, что критерии упорядочены по важности в последовательности {f2,f1}, и 2 =1.

Первая задача из последовательности (6) в данном случае имеет вид:

f2(x)=4x1 -x2 max, при ограничениях -x1 +x2 1, x1 +x2 3, x1 -2x2 0, x1 4, x2 3.

Решение этой задачи можно найти графически. Из рисунка 14 видно, что максимум критерия f2(x) на множестве X достигается в вершине x5=(4,2) * и =f2(x5)=14.

f Графическое решение примера Рис.14.

* Добавим к ограничениям задачи условие f2 - и сформулируем f вторую задачу последовательности (6):

f1=-x1+3x2 max, -x1 +x2 1, x1 +x2 3, x1 -2x2 0, 4x1 -x2 13, x1 4, x2 3.

Ее решением (рис.14) будет вершина x4=(4,3) и = f1(x4)=5. Так как опf1* тимальное решение последней задачи единственно, то в силу утверждения 5, x4 принадлежит множеству Парето.

Отметим, что при [0,1] методом последовательных уступок будет найдена одна из точек отрезка [x4,x5], а при >1, одна из точек отрезка [x3,x4]. Все эти точки и только они принадлежит множеству Парето.

g 12.9. Метод идеальной точки Предположим, что X ограниченное замкнутое множество, тогда все задачи fi* = max fi(x) (i =1,m) имеют решения. Полученную точку xX * * * f* = (f1,f2,...,fm) назовем идеальной [5], так как ни по одному критерию нельзя получить большее значение. Обычно идеальная точка не принадлежит множеству F. Если она все-таки принадлежит множеству F, то * * * именно точка f* = (f1,f2,...,fm) будет решением многокритериальной задачи в пространстве критериев Rm. Введем понятие расстояния между двумя точками (a,b) в пространстве Rm :

1/ s m сs(a,b) = ai - bi s.

i= При s=1 получаем m с1(a,b) = ai - bi.

i=При s=2 имеем обычное евклидово расстояние m с2(a,b) = (a - bi)2.

i i=И наконец, при s= получим равномерную (нормальную) метрику с (a, b) = max ai - bi.

i Теперь решение многокритериальной задачи можно свести к решению обычной однокритериальной задачи оптимизации * с(f (x),f ) min (8) xX Связь между решениями задачи (8) и эффективными точками устанавливает следующее утверждение.

Утверждение 5. Для всякого s[1,) любое решение задачи (8) является эффективной точкой, то есть множество оптимальных решений задачи (8) вложено во множество Парето.

Для линейных многокритериальных задач удобнее использовать m метрику с1(a,b) = ai - bi, так как получаемая при этом i=однокритериальная задача тоже оказывается линейной задачей следующего вида:

m = - (x) min f i xX i=Пример 11. Найти решение следующей двухкритериальной задачи методом идеальной точки:

f1(x)=7x1 +2x3-x4+x5 max f2(x)=x1-5x2-4x3+x4 max при ограничениях -x1 +x2 +x3 =2, 3x1 -x2 +x4 =3, 5x1+2x2 +x3+x4 +x5=11, xi 0 для i=1,2,...,5.

Если использовать метрику при s=1, то метод идеальной точки требует решения следующей однокритериальной задачи (x) = -f1 (x)-f2 (x) = -8x1+3x2+4x3-x5 min или, что эквивалентно, • =8x1-3x2-4x3+x5 max при ограничениях -x1 +x2 +x3 =2, 3x1 -x2 +x4 =3, 5x1+2x2 +x3+x4 +x5=11, xi 0 для i=1,2,...,5.

Для нахождения первого опорного решения применим метод искусственного базиса. Вспомогательная задача имеет вид F= -(w1+w2) max ;

-x1 +x2 +x3 + w1 = 2, 3x1 -x2 +x4 + w2 = 3, 5x1+2x2 +x3+x4 +x5 =11, xi0 для i=1,2,...,5,w1,w20.

Оптимальное решение этой задачи определяется найденной ранее таблицей 3 из примера 2. Добавим в эту таблицу строку оценок, отвечающую целевой функции • Таблица 17. Таблица 18.

x1 x2 x4 xx3 -1 1 2 x3 1/3 2/3 x4 3 -1 3 x1 1/3 -1/3 x5 3 2 6 x5 -1 3 • -3 5 2 • 1 4 Итак, получено оптимальное решение многокритериальной задачи в виде точки (1,0,3,0,3), обозначаемой в примере 2 как x2, и принадлежащей множеству Парето. Очевидно, что из двух вершин множества F, являющихся эффективными значениями, выбрана более близкая к идеальной точке в смысле принятой метрики.

g Пример 12. Используя равномерную метрику, методом идеальной точки найдем решение следующей двухкритериальной задачи (см. пример 2):

f1=-x1+3x2 max f2=4x1 -x2 max при ограничениях -x1 +x2 1, x1 +x2 3, x1 -2x2 0, x1 4, x2 3.

* Так как для данной задачи f1* =7, f =14, то соответствующая однокритериальная задача в пространстве критериев имеет вид:

(f ) = max{7 - f1 ; 14 - f2 }min.

fF Графическое решение этой задачи представлено на рис.15.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.