И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 50
Текст из файла (страница 50)
Определение 2. Пару (х, А,„), состоящую из допустимого решензя х и опоры Амо называют опорным планом. Через А обозначена матрица, состоящая из столбцов а", , а . Отличие опорного плана от опорного решения и его базиса состоит в том, что неопорные компоненты х„1 Е У, опорного плана не обязательно равны нулю. Определение 3.
Опорный план (х, А,„] называют нееырожденным, если все его опорные компоненты х!„..., х! положительные. м 1. Прпмоп опорпыа меток Алгоритм 1 Н а ч а л о. 1. Найти невырожденный опорный план (х, А,„) задачи О х = (х, ..., х„), А,„(а', ..., а'м). П. Выбрать число е Π— точность вычисления максимума целевой функции задачи О.
П1. Вычислить матрицу А,„', обратную исходной опорной матрице. 1Ч. Найти коэффициенты разложения г!и ! = 1, ..., и, 1 = 1, ... ..., и по опоре Аео векторов аl, 1 = 1, ..., п (т. е. найти числа г!и такие, что аI= ~, а ее„), по формулам т г (гп, ..., х„!) = А,„(аи, ..., а !), (4, !! .6!! 1=1, ..., п, 1чь!„е=1, ..., и; еи = О при Б=,Д1; хи,=1 при э=1, а=1, ..., и; 1 1, ..., и. Основной цикл. т'. Положить Роо (1„..., ! ), Р, = Р~~,У 262 Ч1. Разбить множество индексов У„на два непересекающихся подмножества У„+ и У„О СЛЕдующим Образом: индекс / Р У„входит в 7„+ тогда и только тогда, когда х! > О; индекс 1 Е а„входит в а„О тогда и только тогда, когда х = О.
ЧП. Вычислить оценки Лп / = 1, ..., п, по формулам Л,= Хс!4г4! — с,, 1=1, ..., и; /Ф(4, 1=1, ..., л4; 4 ! Л!=О, 1 ОО, 1=1...,, л!. ЧП1. Если выполняются условия Л! = О при 1ЕО,+, Лг,'~О О пРи 1Е Гоко. то положить х'= х и прекратить вычисления (в этом случае допус- тимое решение х является оптимальным); иначе перейти к шагу 1Х. 1Х. Если выполняются условия Л! «О при 1=1, ..., и; ~, Л;х!(е, /=1 то положить хк = х и прекратить вычисления (в этом случае до- пустимое решение х является е-оптимальным или субоптимальным решением); иначе перейти к шагу Х. (Допустимое решение х' на- зывается з-оптимальным (субоптимальным) решением, если (с, х*)— (с, х') ( е). л Х. Если существует индекс 1 Е П: п) такой, что Л !( О и г!! ~; ( О при всех ! Е П: 4п), то прекратить вычисления (в этом случае целевая функция задачи О не ограничена сверху на множестве Х); иначе перейти к шагу Х1.
Х1. Найти оценку Л!„на которой достигается максимум в вы- ражении !пах (шах ! Л! ), и!ах ( — Л!)). к)О к О ! ! ХП. Если Ль ( О, то перейтн к шагу ХШ; если Лн > О, то перейти к шагу ХЧП1. ХП1. Вычислить параметр ОО = ппп (х4,й4ь) км )О 4~4~е и найти индекс г Е П: т! такой, что х4,1 „, = Е„х,ь>о. Х!Ч. Положить х!=х;, 1=1, ..., и; хп —— г4~, 4=1, ..., !и, 1=1, ..., и. ХЧ. Перейти к новому опорному плану (х, А,„) по следующим правилам: х~ =х~ — О,гг/, при й 1, ..., и; х,=х» при /Ф/и й=1, ..., и; /-и/';, ха = ха + О; 1, = /, (остальные опорные индексы не меняют своих значений). ХЧ1. Найти коэффициенты разложения гя, / = 1, ..., т, / = 1...
..., а, векторов а/, / = 1, ..., а, по новой опоре А,„: го=го — (г,/г~/,/г»п), /чь», /= 1, ..., и; /=1, ..., а, г»! = га/ггь. ХЧП. Перейти к шагу Ч. ХЧП1. Вычислить параметр О' = ппп ( — х~ /гд/,). »м,сО 1<1<и Х1Х. Найти индекс» ~11: и) такой, что О; = — х~ /г„;, г,/< ( О. ХХ.
Вычислить параметр О =- ппп (О', ха). ХХ1, Положить х/=ха /=1, ..., а; гп=гп, 1=1, ..., т; / 1, ..., а. Х Х11. Если О, = Оз4=ха, то перейти к шагу ХХ П!, если О, = х/, или Оо = х;„то перейти к шагу ХХЧ1. ХХП1. Перейти к новому опорному плану (х, А,„) по следующим правилам: х; =х; +О,гх/, при /г=!, ..., и; х~ —— х, при /~/„, /»=1, ..., т; ха =х,.— О,; /» = /, (остальные опорные индексы 1„..., /, ь /, ьь... не меняют своих значений). ХХ1Ч.
Вычислить коэффициенты разложения гп, 1 =' 1, ..., и, 1 = 1, ..., а, векторов а/,/ = 1, ..., а по новой опоре А,„по формулам (4.6у). ХХЧ. Перейти к шагу Ч. ХХЧ1. Перейти к новому опорному плану (х, А,п) по следующим правилам: х! =х! +х),гаь при А=1, ..., тп; х!, = О; х! — — х! пРи )~юа, А=1, ..., т; 1Ф1„ опорные индексы не меняют своих значений (а значит, не меняются числа г!!, ! = 1, ..., т, 1 = 1, ", и). ХХЧП. Перейти к шагу Ч.
Теорема 1. Если выполнены предположения О и задача О невырождена, то процесс решения задачи О алгоритмом 1 через конечное число итераций закончится либо на шаге Утт!' (находится оптимальное решение х* задачи О), либо на шаге 1Х (находится е-оптимальное регаение задачи О), либо на шаге Х (устанавливается неограниченность целевой функции задачи О на допустимом множестве Х). 2. Метод обратиой матрицы В прямом опорном методе на каждой итерации запоминается и х т чисел гц, ! = 1, ..., т, 1 = 1, ..., п, что требует значительной оперативной памяти ЭВМ. В методе обратной матрицы вместо чисел гц запоминается матрица А,„' размера т ',с гп, обратная к опорной матрице, что зкономит оперативную память ЭВМ. Алгоритм ь Н а ч а л о.
1. Найти невырожденный опорный план (х, А,„) задачи О: х=(х„..., х„), А п=(а', ..., а ). ! И. Выбрать число з ) Π— точность вычисления максимума целевой функции задачи О. 111. Вычислить матрицу А,„' Л(и!е)~!=~!,';,";, обратную к исходной опорной. Основной цикл. 1Ч.
Положить со„=(с!„..., с! ), от А„„' = (и', ..., и'") = ои (здесь и', ..., й' — столбцы; от, ..., о — стропи). Ч. Вычислить вектор Ь = (Ь„..., Ь„): Ь = соезАоп ° Ч1. Вычислить оценки Л,, 1 = 1, ..., и, по правилам й!=Ьа! — сь 1'-нем А=1, ..., т; Л!=О, )=са, й=1, ..., т. ЧИ. Если выполняются условия Ьг —— 0 при всех х!)О; Ь! 3:0 при всех х! — — О, то положить х* = х и прекратить вычисления (в этом случае допус- тимое решение х является оптимальным); иначе перейти к ша- гу ЧП1. ЧП1. Если выполняются условия Ь! в О при 1 = 1, ..., л; г ~, Ь!х! (е, у=! то положить хг = х и прекратить вычисления (в этом случае допус- тимое решение х является е-оптимальным); иначе перейти к ша- гу 1Х.
!Х. Положить 1 = 1. Х. Если Л, ( О, то вычислить числа хи = о'а' 1= 1 ш и перейти к шагу Х1; иначе перейти к шагу ХП. Х1. Если при всех 1 = 1, ..., гн выполняется неравенство хна, : ' О, то прекратить вычисления (в этом случае целевая функция задачи 0 иеограничеиа сверху на допустимом множестве Х); иначе перейти к шагу ХП. ХП. Если Г ~ и, то положить 1 = 1+ 1 и перейти к шагу Х; иначе перейти к шагу ХП1. ХП1. Найти индекс )ОЕ П: и), имеющий оценку Лл, при ко- торой обеспечивается максимум выражению шах (шах ( Л! (, шах ( — Ь!)).
«!)О «О Х!Ч. Если Ь;, ( О, то перейти к шагу ХЧ, если Лл) О, то перейти к шагу ХХ1. ХЧ. Вычислить величины хгл = о'аО>, 1 = 1...,, лО. ХЧ1. Вычислить параметр О, = гп! и (х;„ЙОЬ) гг )О и найти индекс г Р (1: лО) такой, что Е,=х,,1х,л, х,в)О. ХЧП. Положить х; им = исм. ГДЕ иО = (им, иОм ..., 1 1» ° ° л> 1=1, ..., гп, т и О). ХЧ1П. Перейти к новому опорному плану (х, А,„) по следующим правилам: х~,=х~ — Я,г»и при й=1, ...; т; х,=х~ при /~1», й=1, ..., т, 1ы1,; хи =х,,+О,; 1, = /, (остальные опорные индексы не меняют своих значений). Х1Х. Вычислить матрицу А,„' Ь (иц))»' ~",,,"„', обратную новой опорной матрице, по формулам и»» = иц» — й»ги/,/г./„1 = 1, ..., г — 1, г+ 1, ..., т; й=1, ...,т; и„» =* й,»/г,/., й = 1, ..., т.
ХХ. Перейти к шагу 1Ч. ХХ1. Вычислить величины гц, о'аь, 1=1, ..., т. ХХП. Вычислить параметр О; пнп ( — х» /г»/,) м»/ <» 1ч»<~и и найти индекс г ~ [1: т1 такой, что 8' — х~,/г,/„г,/, ~ О. ХХП1. Вычислить параметр О, = ппп(8», х/,). ХХ1Ч. Положить х/ х/, /=1, ...,п; йм=им, 1 1...,, т; й=1, ..., т.
ХХЧ. Если 8» 8» д хь, то перейти к шагу ХХЧ1, если 8» = х/ или О» — — х/, то перейти к шагу ХХ1Х. ХХЧ1. Перейти к новому опорному плану (х, А,„) по следующим правилам: х~„=х~,+О,г»ь при Й=1, ..., т; х;=х при /чь/», й 1, ..., т, /ть/ хи=хи — О,; 1~ =/о (остальные опорные индексы 1„..., 1, „1,+,, ..., 1 не меняют своих значений). ХХЧП. Вычислить матрицу А,„' Й(ии)г=~'"..'." обуатнУю не вой опорной матрице, по (4.68). ХХЧП1. Перейти к шагу [Ч. ХХ!Х. Перейти к новому опорному плану (х, А,„) по следующим правилам: х! =х,,+хигаь при й=[, ..., т; х/=х; при /4:!», /е=[, ..., т, /~/'е; хи = 0 (опорные индексы г„..., !, не меняют своих значений, а значит, не меняется матрица А,„').
ХХХ. Перейти к шагу 1У. Теорема М. Если выполнены предположения О и задача О невырождена,.то решение задачи О алгоритмом 2 через конечное число итераций закончится либо на шаге Ч/1 (находится оптимальное решение х* задачи О), либо на шаге [/11! (находится в-оптимальное решение задачи О), либо на шаге Х1 (устанавливается неограниченность целевой функции задачи О на допустимом множестве Х). Замечание 1. Если в алгоритме 2 (на шагах Х1Х и ХХЧ11) матрицу А,,', обратную новой опорной, вычислять по формуле А,„' = Р,А„', где А,,' Ь (й!а)1.=.!",-", — матрица, обратная естаройа опорной матрице, и 0...0 Π— г1!./г% 0 ... 1 — г, ! !,/г,/,0 ... 0 О...
О 1/г!, 0...0 0 ... 0 — гг-г-!,г',/гг!,0 ... 0 !0...0 — г,,/г!,0...! то такой метод решения задачи называется мультипликативным. Для записи матрицы Р, достаточно знать т + 1 чисел, т. е. число г и числа, которые стоят в г-м столбце. Если обозначить матрицу Р, в й-й итерации через Рце а за исходную опору в алгоритме 2 выбрать единичную матрицу 1, то обратная к опорной в й-й итерации будет определяться по формуле Аоп = Рг 1-!гг ! ° ° ° Рг,/. Отсюда следует, что для определения матрицы А,„' в й-й итерации требуется знать (т + 1) .х й чисел, что на начальных стадиях мультипликативного алгоритма приводит к экономии оперативной памяти ЭВМ.
Библиографиеескгге указания. Параграф написан иа осиоваиив работы [591. В указаииой работе приведены также различные модификации прямых опориыв методов, двойственные опорные методы, безопориые методы, комбииироваииые методы. Гав»в $ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО И СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ 5.1. Методы проекции градиента 1. Обаооа алрарати или (Ч)о (в») х» — ох) ) р„ ппп 1, то 1х» — кх )о ($.$) где 0<в,<т < Я "; ео>0, и перейти к шагу ЧП1. Ч1П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
