Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 23

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 23)

[312] Пусть Ω-многогранный конус, определенныйматрицей B,Ω = {z∈Em | Bz ≤ Ο P }.PПусть H(q)∈E и H(q) = BJ(q).Тогда эффективные (оптимальные по Парето) решения для векторногопоказателя H(q) точно совпадают с Ω-оптимальными решениями для векторного показателя J(q) на множестве Q:H,QΩJ = QΠт.е. конус определяет часть множества Парето-решений.Следствие 3.1. Из утверждения 3.4 следует, что(3.14)JQΩJ = QΠпри B = E,(3.15)т.е. «прямоугольный» конус доминирования определяет все множествоПарето-решений.Из определения 3.15 следует слабая оптимальность по конусу.Определение 3.16 [213].

Решение J* = J(q*) называется слабо оптимальным по конусу Ω с матрицей B = [p×m] в критериальном пространствеEm векторного показателя J, если не существует такого q∈Q, для которогосправедлива система неравенствB(J(q) – J(q*)) < Ο P .(3.16)Из (3.15) и утверждения 3.4 следует, что слабая оптимальность по конусу Ω эквивалентна слабой оптимальности по Парето [206] в критериальном пространстве EP показателя H = BJ.На основе подхода Куна–Таккера–Мукая [363] и с учетом известнойтеоремы Да Канхи–Поллака–Джоффриона [206] в [213, 230] сформулированы необходимые условия слабой оптимальности по конусу.Утверждение 3.5.

Пусть q* – оптимальное решение по конусу доминирования Ω относительно целевого вектора J и множества Q, заданного ввиде108Стабильные эффективные решения и компромиссы. Часть IQ = {q∈Er | G(q) ≤ 0},где G(q) = {g i (q)≤0, i = 1, s g ; Cq ≤ b, C = [s c , r], b = (s c ×1), q L ≤ q ≤ q H }.Функционал ΨT = [ J T , GsT ] дифференцируем по Фреше в точке q*, где s– множество индексов ограничений G, активных в точке q*.Тогда является совместной система уравнений ∂Ψ(q* )  TB=γ 0,=A A0 ∂q γ ≥ 0, γ = (μ, ν ), dim μ = p, μ ≠ 0,B=[ p × m] , E =[ s × s ].0;Edim ν = s;(3.17)Следствие 3.2. Так как множество слабо оптимальных по конусу решений содержит в себе множество оптимальных по конусу решений, тоусловие (3.17) является также необходимым условием оптимальности поконусу.Следствие 3.3.

Как следует из (3.14), (3.15), при B = E условие (3.17)превращается в необходимое условие Парето-оптимальности q*.3.2.3.Об алгоритмах вычисления конусов доминированияВ [47, 213, 230] сформировано несколько вариантов вычисления конусов доминирования в рамках задач векторной оптимизации, в которыхучитываются:• требование проектировщика о допустимых взаимных локальных изменениях показателей;• равномерное улучшение компонент векторного показателя;• неопределенность весовых коэффициентов компонент векторного показателя.Все данные алгоритмы имеют универсальный характер на классе задачи прикладную ценность.Третий вариант оптимально учитывает условия неопределенности, егоконструкция и приложения даны в работе [213].Второй вариант используется, например, для построения модифицированной арбитражной схемы в условиях обязательных соглашений (см.

главу 6).Первый вариант вычисления конуса как функции матрицы коэффициентов замещения рассматривается далее, как основной при формированииалгоритмического обеспечения Ω-оптимизации.Глава 3. Стабильные и эффективные оптимальные решения109Данный алгоритм является обобщением известного алгоритма Джоффриона [97], общий смысл которого рассмотрен в 3.2.1 и имеет следующуюструктуру:Ша г 1. Формирование множества K = {1 ≤ k 1 ≤ k 2 ≤...≤ k p ≤ m} индексов компонент векторного показателя, изменение величин которых намечено контролировать.Ша г 2.

Построение прямоугольной матрицы A размером [p×m] с элементами a ij вида:j ki , ki ∈ K ; 1, = ∆J(3.18)aij = kij ≠ ki , − ∆J ,jгде ∆J ki – максимально допустимое ухудшение показателя J ki , соответствующее улучшению показателя J j на ∆J j (если значения других показателей при этом не изменяются). На величины ∆J ki , ∆J j , k i ∈K, j∈M,наложены ограничения, обусловленные постановкой задачи (3.7) в видезадачи минимизации:0 ≤ ∆J ki < ∞, ∆J j < 0.Ша г 3. Построение конуса доминирования в видеΩ = {z∈Em | Bz ≤ Ο P },(3.19)где B = A.

То есть конус Ω = Ω A , где Ω A – конус, натянутый на системувекторов(3.20){ai = [a i1 ,...,a im ]T, i = 1, p },составленных из строк матрицы A вида (3.18).Сформулируем следующееУтверждение 3.6 [213]. Пусть задана система предпочтений в формематрицы A вида (3.18). Тогда:1) конус доминирования Ω вида (3.19) является выпуклым, острым, многогранным;2) для любых i = 1, p ; j = 1, m вектор d∈Ω, координаты d l , l = 1, m которого вычисляются в видеl ki , ki ∈ K , dl , =(3.21)dl =l=j, −1, 0, l ≠ k , l ≠ j,iудовлетворяет условиюδl ≤ aij .(3.22)110Стабильные эффективные решения и компромиссы. Часть IЗамечание 3.1.

Геометрический смысл утверждения 3.6 состоит в том,что вектор d, определяемый в виде (3.21), для любых i = 1, p ; j = 1, m , характеризует направление, в котором улучшению ∆J j =1 показателя J jсоответствует изменение ∆J ki =δki показателя J ki . При этом, если другиепоказатели остаются неизменными, то ухудшение ∆J ki не может превысить величину a ij , если только d∈Ω. То есть конус Ω, построенный поправилу (3.18), (3.19), удовлетворяет требованиям проектировщика о допустимых взаимных локальных изменениях показателей.Замечание 3.2.

Гиперплоскость П, касательная к поверхности равныхзначений неявной функции полезности в методе Джоффриона, являетсячастным случаем конуса доминирования, построенного в соответствии с(3.18), (3.19). Касательной гиперплоскости с опорным показателем J i соответствует матрица A = WT, где компоненты W j вектора W представляют собой коэффициенты замещения, вычисленные по алгоритму Джоффриона.Замечание 3.3. В терминах конуса доминирования Ω, удовлетворяющего соотношениям (3.18), (3.19), можно интерпретировать информацию опредпочтениях проектировщика в методах векторной релаксации, обсуждавшихся в разделе 3.2.1 [213, 220, 230, 265, 363].

Если в (3.18) для всехi∈K, j∈M, j≠i положить a ij = 0, то полученный конус доминирования реализует требование одновременного неухудшения компонент векторногопоказателя J с номерами из множества K, сформированного на шаге 1 алгоритма. Значения компонент вектора J с номерами из множества (M\K)при этом контролироваться не будут. Условие K = M означает требованиеодновременного неухудшения всех компонент вектора J. В этом случаеконус доминирования Ω превращается в неположительный ортант E≤mкритериального пространства Em, что означает [213, 312, 428] совпадениепонятий Ω-оптимальности и Парето-оптимальности.Таким образом, вычисление конуса доминирования в виде (3.18), (3.19)дает возможность количественно учитывать более содержательную информацию о предпочтениях проектировщика по сравнению c методамиДжоффриона и векторной релаксации при решении задач (3.7).Второй вариант конструкции конуса доминирования изложен в главе 6,где он используется для формирования модифицированной арбитражнойсхемы в условиях обязательных соглашений.Третий вариант возникает, если появляется сложность точного назначения вектора весовых коэффициентов λ∈Λ, где Λ задана в форме (3.10)при свертке векторного показателя, но имеется интервальная информация:Глава 3.

Стабильные и эффективные оптимальные решения111Om ≤ λ L ≤ λ ≤ λ H ≤ 1m ; m(3.23)∑ λi =1,i=1TTгде λ L = [λ L1 ,...,λ Lm ] , λ H = [λ H1 ,...,λ Hm ] .Информацию вида (3.23) о векторе λ можно интерпретировать приm = 2 в виде конуса доминирования, где B = B(λ L , λ H ).В работе [213] формируется машинно-ориентированный алгоритм вычисления матрицы B конуса доминирования Ω, позволяющий решать задачу для любого m.Очевидно, что практически важным частным случаем (3.23) являетсяформирование матрицы B как пересечения наборов λ, удовлетворяющихограничениям (3.23) и имеющим вид λ11 , ... , λ1m (3.23а).B =  .............  .λ , ...

, λ mm  m13.2.4.Алгоритмическое обеспечение задачи оптимизациипо конусу (Ω-оптимизация)Предполагается, что конус доминирования Ω задан в виде (3.19) и фиксирован. Для простоты обозначений будем предполагать, что компонентыпоказателя потерь J и компоненты вектора параметров q образуют единыекоалиции интересов и действия соответственно. Поэтому задачу (3.7)можно записать в виде (J – вектор потерь):(3.24)определить min{J (q ) | R, Ω} ,q∈Qгде J (q)∈E , q∈E , R = { 1, r }. Область Q определяется, например, какmr(3.25)Q = {q∈Er | q L ≤ q ≤ q H , Cq ≤ b},C = [s×r], b = [s×1].Для формирования алгоритма поиска Ω-оптимального решения в задаче (3.24) в [213] видоизменяется известный алгоритм векторной релаксации [265] с учетом конуса доминирования (3.19).

Вычислительная процедура представляется в виде последовательности следующих этапов [213].Выбор направления спуска внутри конуса доминирования. Как следуетиз [213, 312, 428], условие доминирования решения J ′′ над решением J ′относительно конуса Ω с матрицей B записывается в видеB∆J ≤ O,(3.26)′′′где ∆ J = J – J .112Стабильные эффективные решения и компромиссы.

Часть IИспользование соотношения (3.26) в качестве условия спуска в алгоритме векторной релаксации позволяет сформулировать задачу выборанаправления спуска внутри конуса доминирования в виде:z;определить max(а ) [ dT , z ]∈D  ∂J (q ) (б ) B  d + ZP ≤ OP ;  ∂q (3.27)D :  A a d ≤ O Sa ;(в ) (г)  d K ≤ 1,где (3.27б) – условие d∈Ω; (3.27в) – условие того, что вектор d направленвовнутрь области допустимых значений параметров Q вида (3.25);A a = [s a ×r] – матрица линейных ограничений (как общего вида, так и тривиальных), активных в точке q; ||⋅|| K – условие нормировки.Постановка задачи выбора направления вида (3.27) является более общей по сравнению с постановками [265, 363], которые могут быть получены из (3.27) как ее частные случаи.

Для этого матрицу B конуса доминирования Ω необходимо задать с помощью первого алгоритма в виде функциикоэффициентов замещения.Для получения условий останова при решении задачи (3.27) сформулировано утверждение:Утверждение 3.7 [213]. Пусть в точке q выполнены условия регулярности [220]: существует такая точка q*∈Er, что справедлива система неравенств A a q*>O (матрица A a определена в (3.27)).

Тогда:• точка q удовлетворяет необходимым условиям слабой оптимальностипо конусу Ω тогда и только тогда, когда оптимальное значение целевойфункции z в задаче (3.27) равно 0;• если z > 0, то решение d задачи (3.27) принадлежит конусу доминирования Ω Q , построенному в пространстве параметров Er.Необходимо отметить, что решение задачи (3.27) зависит от условийнормировки (3.27г). В вычислительной практике, как правило, используются [18, 110] следующие виды нормировки:(3.28а)при K = ∞|d i |≤1, i = 1, r ,при K = 2dTd ≤ 1.(3.28б)В результате получаем задачу линейного программирования вида:Глава 3. Стабильные и эффективные оптимальные решения113(а )   ∂J ( q)  (б ) B (d − G) + Z P ≤ O P ;  ∂q (3.29)D :  A a (d − G) ≤ O Sa ;(в ) i 1, r ; z ≥ 0,(г)  0 ≤ d i ≤ 2,=где G – вспомогательный вектор, с помощью которого осуществляется переход от переменной d к неотрицательной вспомогательной переменнойd , необходимой для решения задачи (3.27):(3.30)d= d + G .Для решения задачи (3.29) используется симплекс-метод.Более точное решение задачи (3.27), улучшающее сходимость алгоритма Ω-оптимизации в целом, можно получить, учитывая условия нормировки вида (3.28б).

Характеристики

Список файлов книги