2.3. Компромиссы Парето

Пусть решается задача

Рассмотрим две точки х\ х" є D. Если выполняются неравенства

говорить, что точка х' предпочтительнее, чем х". Если для некоторой точки х° є D не существует более предпочтительных точек, то будем называть ^° эф­фективным, или Парето-оптимальным, решением многокритериальной за­дачи (2.8). Множество, включающее все эффективные решения, обозначает­ся Р (D) и называется множеством Парето для векторного отображения /:£>->Ля,/ = (/і,...,/*> Очевидно, P(D)czDczRn. Образ множества P(D) в пространстве критериев Rk обозначается P(f). Множество P(f) = f(P(D)) на­зывается множеством эффективных оценок [47].

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

Точка х' є D называется слабо эффективным решением задачи (2.8), если не су­ществует такой точки хп є D, для которой выполняются строгие неравенства fi(x") < fi(x' ),і є [1:4]. Иначе говоря, решение называется слабо эффективным, если оно не может быть улучшено сразу по всем критериям. Множество слабо эффективных решений будет обозначаться через S (D). Очевидно, P(D) с S(D). Аналогично полагаем 5(/)=/(5(D))

Упражнение. Докажите включение P(D) с S(D).

Введение понятия слабо эффективного решения вызвано тем, что в процессе оп­тимизации часто получаются именно эти решения, обычно представляющие с точки зрения практики меньший интерес, чем эффективные решения. С другой стороны, понятие слабо эффективного решения может играть важную роль при выборе набора «существенных» критериев [47]. Действительно, нетрудно дока­зать, что решение, которое слабо эффективно по сокращенному набору критери­ев, будет слабо эффективным и по расширенному набору.

Упражнение. Докажите, что этот вывод несправедлив для эффективных реше­ний. Приведите «опровергающий» пример.

Поэтому после построения полного набора критериев следует выделить именно слабо эффективные решения, среди которых будут находиться и искомые реше­ния, эффективные по окончательному (может быть, сокращенному) набору. На рис. 2.1 P(f) = [b,c]; S(f) = [a,b]<u[b,c]<u[c,d], Данное замечание оказывается важным при первоначальной формализации реальной задачи и выборе рацио­нального набора критериев оптимальности. Обычно вначале приходится «на всякий случай» учитывать большее число частных целевых функционалов, чем это в действительности окажется необходимым.

Схемы построения эффективных и слабо эффективных решений могут быть ос­нованы на следующих теоремах.

Теорема 2.1. Пусть заданы произвольные а{ > 0, і є [1:4], тогда решение задачи

mina.Yf; - f;) -> max

(2.10)

при любых фиксированных t{ есть слабо эффективный вектор. Наоборот, любой слабо эффективный вектор может быть получен как решение задачи (2.10) при некоторых а, > 0 и £. > /,(#), г є [1:4], xeD.


h t

Рис. 2.1. Эффективные и слабо эффективные оценки задачи fj -> min, / = 1,2

Доказательство. Пусть есть решение задачи (2.10) и существует є D такой, что /;(#' ) < fi(x°), і є [1:4]. Тогда min а - /,(#' )) > mmai(tl; - /,(^°)), что противоречит свойству д^. Наоборот, пусть .г0 є 5(D); тогда, согласно условию теоремы, ti - fi(x°) > 0. Примем а• = 1 / (ti -/>(х°)) и покажем, что

maxmina;.^. -/f(x)) = тіпа'^ґ, -/f(*°)) = l. (2.11)

Из x° є 5(D) следует, что для любого х' gD найдется хотя бы один номер і0, для которого fio(x')> Д

Но тогда и mina-(^ -/,(#')) < 1, что означает выполнение (2.11), так как х' — любой элемент D. Теорема доказана.

Замечание 1. Обратное утверждение теоремы 1 справедливо в следующей фор­мулировке: любой слабо эффективный вектор аР может быть получен как реше­ние задачи (2.10) при ti > /, (#),

a,->0,£a,. =1. (2.12)

Действительно, если х = arg max<p(;t), то х = arg max fi<p(x), если р > 0. Пола-
гая <р(х) = шіпа?(ґ,- -/.), х° = arg maxmina?(£, -/.), Р = -?   , получим, что

Замечание 2. Из доказательства второй части теоремы 1 следует, что для любого слабо эффективного вектора хР могут быть выбраны такие а, > 0, для которых он получается как решение задачи (2.10), причем

Теорема 2.2. Пусть а, >0, і є [l:k]; D' — произвольное подмножество Д содер­жащее хотя бы один эффективный вектор, тогда решение задачи

есть эффективный вектор.

Доказательство. Пусть хР есть решение задачи (2.14) и существует х' є D' такой, что fi(x' ) < fi(x°), а для і = і0 имеем Д (х' ) < Д (*°). Тогда

Іа1./1.(^)<Іа1/1.(^0), і=і i=i

что противоречит свойству вектора хР.

Замечание. Обратное утверждение без дополнительных предположений невер­но. Существуют эффективные векторы, не являющиеся решением задачи (2.14).

Теорема 2.3. Пусть Та — непустое множество решений задачи (2.10). Тогда су­ществует вектор х* єTa, являющийся эффективным.

Доказательство. Допустим, что существует такой і'єД что/х(х')< fx(x°)y

і є [1: А], где xQ — произвольный элемент множества Та. Тогда mina,^ - /,(#')) ^ > min a, (£, -fi(x°)) = max min a. (tt - f\ (x)), то есть x' є Ta и, следовательно,

і           xeD     і      г / \

вне множества Та не может существовать решений х\ для которых fi (х') < < fi(x°), і є [1: А]. Теорема доказана.

Следствие. Если множество Та содержит единственный вектор, то он эффек­тивен.

По схеме теоремы 1 могут быть получены все слабо эффективные решения, если вектор a =(a1,..., ak) пробегает все множество векторов (2.12). Напротив, вы­числительная схема (2.14) позволяет получать только эффективные решения, но не все. А. Джоффриону принадлежит идея выделения эффективных точек из множества S(D)y построенного согласно (2.10) с помощью процедуры (2.14). Справедливо следующее утверждение [18].

Теорема 2.4. Пусть а, > 0, і є [1: А], тогда решение задачи

есть эффективный вектор. Наоборот, любой эффективный вектор х° может быть получен как решение задачи (2.15) при некоторых а, > 0 и £f > /,(#)> г є [i:k].

Доказательство. Первое утверждение теоремы есть следствие теорем 2, 3. Дей­ствительно, согласно теореме 3 множество Та будет содержать эффективный век­тор, а согласно теореме 2 решение задачи (2.14) на множестве D' - Та при любых а, >0, в том числе и при а,. =1, является эффективным вектором.

Докажем обратное утверждение. Пусть хР — эффективный вектор. Он будет и слабо эффективным, поэтому, согласно теореме 1, при а = а' он получается как решение задачи (2.10) в составе множества Та, с выполнением соотноше­ний (2.13). Пусть х' є Та, и £/,(*' )< ).

і=і і=і

Тогда существует по крайней мере один і = і0 такой, что Д (х') < Д (х°). Но то­гда, согласно (2.13), мы получили бы

Ч(К -Д (f » > <(К -Д <*0)) = maxnuna;.(t,. -/,(*)),

что противоречит свойству х° еТа,. Следовательно, хР есть решение зада­чи (2.15). Теорема доказана.

Доказанные теоремы позволяют понять сущность методов максиминной, мини­максной и линейной сверток, обсуждавшихся в 2.2. Становится ясной роль весо­вых коэффициентов, параметризующих множество слабо эффективных реше­ний. С точки зрения приложений, представляет интерес соотношение (2.13), позволяющее в случае выпуклых границ множества достижимости f(D) вы­бирать весовые коэффициенты, исходя из требуемых соотношений между окон­чательными значениями критериальных выходных параметров. Для более по­дробного и наглядного изложения методов и принципов многокритериальной оптимизации мы отсылаем читателя к учебнику [74].

Метод главного критерия также может быть проинтерпретирован помощью по­нятия эффективного решения. Справедливы следующие утверждения.

Теорема 2.5. Решение*задачи

где множество

D'={^eD|/f(^)<^,ie[2:*]}        (2.17)
не пусто, есть слабо эффективный вектор.

Доказательство. Пусть хР есть решение задачи (2.16) и существует х' є D такой, что

Мх>)<Мх°Це[Щ        (2.18)

Тогда х' £ £>', так как в противном случае это противоречило бы свойству fi(x°) £fi(x) для х eD\ Следовательно, x' eD', и поэтому существует такой і = /0, для которого Д (#') >   , что противоречит (2.18).

Теорема 2.6. Пусть Tt — непустое множество решений задачи (2.16). Тогда су­ществует вектор х* eTt, являющийся эффективным.

Доказательство. Пусть существует х' є Д для которого       ) < /{(х°), і є [tk],

где х° — произвольный элемёнт множества Tt. Тогда Jtr'eD', причем, по предпо­ложению,  fx(x')<fx (х°)  и,   следовательно,  fx (xf ) = fx(x0),   так   как л:0 = e arg min f{(x\ Таким образом, х' eTt, и вне множества Tt не может существовать решений х\ для которых       ) <       ), і є [1: А]. Теорема доказана. Следствие. Если решение задачи (2.16) единственно, то оно эффективно.

Теорема 2.7. Любой эффективный вектор может быть получен как решение за­дачи (2.16) при некоторых tif і є \2:k\

Доказательство. Пусть х° є P{D)\ примем £f = /{(х°), і є [2:&] и покажем, что

/Дх0)==тіп/Д;О>*є£>'. (2.19)

Пусть   х' eD';   тогда   /, (х') < /f (#0), і є [2: &].   Если   предположить, что ) < /іС*° )> то это будет противоречить эффективности вектора хР, следова­тельно, fx(x') > fx(x°), что эквивалентно (2.19).

Из доказанных теорем следует, что в качестве «главного» может быть выбран любой критерий. Независимо от этого выбора любое эффективное решение мо­жет быть получено как решение задачи (2.16) при соответствующем назначе­нии

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

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


Авторы: 239 А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

Книги: 268 А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я