Условия Куна-Таккера для условной оптимизации


Условия оптимальности для задачи выпуклого программирования (1.30) называются условиями Куна — Таккера и эквивалентны утверждению, что при движении в любом возможном направлении S из точки х* критерий оптимальности Q(x) не может быть уменьшен. Геометрическая интерпретация условий Куна—Таккера имеет следующий смысл: в точке х*∈D , являющейся оптимальным решением задачи выпуклого программирования (1.30), градиент выпуклой функции Q (х) является линейной комбинацией градиентов активных ограничений gi (х) = bi, i∈J, взятых с положительными коэффициентами ui* > 0. Условие (1.78) называется условием дополняющей нежесткости и означает, что если некоторое из. неравенств является в точке х*∈D неактивным ограничением, то оно должно входить в условия Куна—Таккера с множителем ui*, равным нулю, а для активных ограничений множители ui* должны быть положительными.

В задаче многокритериальной оптимизации (1.47)—(1.49) приходится рассматривать в качестве критерия оптимальности совокупность непрерывно дифференцируемых функций Qi*(х), i = 1, 2,…, s. В детерминированном случае выбор любого значения х∈D приводит к вполне определенным значениям векторного критерия Q (х) = (Q1 (х)…,
Qs(х)). В связи с чем допустимой области D можно поставить в соответствие некоторое множество

DQ = (Q = (Q1, Q2,…, Qs)| Qi = Qi (x), i = 1, 2, …, s; x∈D},

являющееся отображением области D в s-мерное пространство Rs и называемое областью критериев. На рис. 1.11 показаны допустимая область D и соответствующая ей область критериев DQ для задачи векторной оптимизации {min (- 5х1 — Зх2 + 36);
min (- 6x1 + x2 + 23)}.

Будем говорить, что векторный критерий Qk = Q (kk) — (Q1k), …. Qs (xk)) = (Q1k, Q2k,…, Qsk) удовлетворяет принципу доминирования относительно векторного критерия Ql = (Q1l)( …
…. Qsl)) = (Q1l, Q2l,…, Qsl), если Qlk ≤ Qil для всех i = 1,2, …, s и хотя бы для одного j выполняется строгое неравенство Qlk < Qil.



Рис. 1.11. Допустимая область D(а) и соответствующая ей область критериев DQ (б) для задачи векторной оптимизации: min (-x11 — 3x2+36); min (-6x1+x2+23)

В случае доминирования при переходе от векторного критерия Ql к критерию Qk ничего не будет проиграно ни по одному из частных критериев Qik, но в отношении j-го частного критерия точно будет получен выигрыш. Множество критериев Q, для которых справедлив принцип доминирования, образует подмножество Dc⊆DQ⊂Rs, называемое областью согласия. В области согласия Dc нет противоречия между частными критериями оптимальности, так как каждая точка х∈Dc может быть изменена таким образом, что будут одновременно уменьшены все частные критерии оптимальности. Если область критериев Dq состоит только из области согласия Dc, то существует единственная точка х*∈D, в которой все частные критерии согласованы между собой в том смысле, что при движении к точке х* все компоненты Qi(х), i =1, 2, …, s, одновременно уменьшаются (рис. 1.12, а). При этом значения частных критериев оптимальности достигают минимума в одной и той же точке х*, т. е. хk* = х* для всех
k = 1, 2, …, s (рис. 1.12, б).



Рис.1.12 Область критериев DQ состоящая только из области согласия (а) и соответствующие ей критериев оптимальности Q1(x) и Q2(x) (б)

Однако рассмотренная ситуация на практике встречается очень редко. Наиболее типичным является случай, когда минимум по каждому из частных критериев оптимальности достигается в различных точках хk*∈D, k= 1, 2, …, s, в которых компоненты векторного критерия Q = (Q1,…, Qs) являются противоречивыми в том смысле, что

Qik*) ≥ Qii*), i ∈I1 и хотя бы для одного j Q j (xk*) > Qj (xi*), (1.80)

а для других:

Qr (xk*) ≤ Qr (xi*), r ∈I2 и хотя бы для одного t Qtk*) < Qii*).

Здесь I1∪I2= (1, 2, …, s); I1≠∅; I2≠∅ и для каждого множества индексов I1, I2 имеется хотя бы одно неравенство, которое является строгим.

При выполнении системы неравенств (1.80) уменьшение по одному из частных критериев приводит к увеличению по другим частным критериям. Такие точки х°∈D, в которых не выполняется принцип доминирования относительно любой точки х∈D, называются эффективными точками. Другими словами, точка х°∈D является эффективной точкой, если не существует ни одной точки х∈D такой, что

Qi (х) ≤ Qi (х°) для всех i = 1, 2, …, s,

а хотя бы для одного j это неравенство строгое

Qj (х) < Qj (х°). (1.81)

В связи с тем, что в эффективных точках векторный критерий оптимальности Q является неуменьшаемым одновременно по совокупности всех частных критериев, эти точки также называются неулучшаемыми решениями или решениями, оптимальными по Парето.

Из определения эффективной точки (1.81) следует, что она может быть не единственной. Множество критериев Q, соответствующих множеству всех эффективных точек, называется областью компромиссов (переговорным множеством) D⊆DQ⊂Rs (рис. 1.11,6), а само множество эффективных точек — областью решений, оптимальных по Парето (рис. 1.11, а).

Оптимальность по Парето означает, что нельзя дальше уменьшать значение одного из частных критериев, не увеличивая при этом хотя бы одного из остальных. Противное означало бы, что можно уменьшать некоторые частные критерии оптимальности Qi (х) без увеличения других критериев, а это противоречит определению эффективной точки (1.81). Таким образом, в области компромиссов Dk не выполняется принцип доминирования, а частные критерии являются противоречивыми. Это и приводит к необходимости введения компромисса между частными критериями оптимальности для того, чтобы решить, какой из векторов Qk или Ql, принадлежащих области компромиссов Dk, считать предпочтительнее (лучше). С наличием такой ситуации и связано название области Dk как области компромиссов.

Из введенных определений следует, что область критериев Dq можно разделить на область согласия Dq и область компромиссов Dq, которые удовлетворяют следующим условиям:

DQ = Dc∪Dk; Dc∩Dk = ∅

Решения, представляющие интерес для задачи векторной оптимизации, находятся в области компромиссов Dk, так как любое решение, принадлежащее области согласия Dc, может быть одновременно уменьшено по всем частным критериям и, следовательно, не приведет к противоречию и необходимости выбора компромисса. В связи о этим под оптимально-компромиссным решением будем понимать одну из эффективных точек х°∈D, которая является предпочтительной о точки зрения лица, принимающего решения. Такое определение оптимально-компромиссного решения позволяет разделить решение задачи векторной оптимизации (1.47)—(1.49) на два этапа: определение эффективных точек х°, удовлетворяющих одному из рассмотренных выше условий оптимальности, и выбор среди нескольких эффективных точек оптимально-компромиссного решения, наиболее предпочтительного с точки зрения лица, принимающего решение.


Комментарии запрещены.




Статистика