И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 46
Текст из файла (страница 46)
ХЧ1. Перейти к шагу П1. ХЧП. Вычислить индекс р Е И ! т) такой, что Оо = — Ь!»!/6».6»(О; 1» чь !», й 1 ° ..., ю ХЧ1П. Перейти к новому базису А„, который получается путем окаймления базиса А, строкой (а»!» а»/„..., а»/,, а»~) т. и столбцом (а!,„а!,„..., а! „а„,); положить о,+! = р, /,+! = г и перейти к шагу Х1Х. Х1Х. Вычислить матрицу А,' = (11!»)! !,"..".~~~!, обратную новой базисной матрице по правилам ХХ. Положить з = з+ 1 и перейти к шагу Ш.
ХХ1. Найти параметр 0о из условия оо, если 6!'~О, !' 1, ..., т; ппп ( — Ь!'!/6'~), если существует бои(О; о(о<о ! <!~ив = 6, — ~ а!;х, ! = 1, ..., по; ю ! 1 5 6! = ~а!/„~т!, 1=1, ..., л!. т ! (4.361 ХХ11. Найти параметр Оо из условия шш (х~„ф~г). если существует йт~ ) О, 7) д, а„~>а О', =,>, ео, если рт»(0, у=ай+1, ..., з. ХХ1П. Вычислить параметр О, по формуле О,-ппп(О», О»). Если О, = со, то прекратить вычисления (в этом случае целевая функция задачи 1 неограничена на допустимом множестве); если О»( со, то перейти к шагу ХХ1Ч. ХХ1Ч. Вычислить новое опорное решение х = (х„..., х„) по формуле (4.36) ()ц — ф,ф~ф,~), если 1(т, Й(!; ~»!.ь» — (6„»б»~, ~/(), ), если 1 зт, й(!; Рь»+~ (Рт,»+4н/Ры), если !~т, /»~!; Рю+ь»+» — (р»»+Фь+ьЯы) если 1~ ч, /»,и !, 1=1,..., з — 1,й 1,...,з — 1.
ХХ1Х. Положить з = з — 1 и перейти к'шагу П!. ХХХ. Вычислить индекс (» р (1 ~ л»! такой, что Оо — Ь~"~/6~"~, б~ю(0; йФ(», й = 1, ..., 3 239 х=х — О,й, где й = (Ь„..., Ь„) — вектор, определяемый по правилу Рл, если !'= !и 1= 1, ..., $, Ь,= 10, в остальных случаях. ХХЧ.
Если О,= О»ч то перейти к шагу ХХЧ1, если О, = О» то перейти к шагу ХХХ. ХХЧ1. Вычислить индекс т Е [(д + 1) ~ з) такой, что О;-(х,,/О„), Р„,~о. Если задача 1 невырожденная, то индекс ч определяется одно- значно. В вырожденном случае можно выбрать любой индекс т, на котором достигается минимум в (4.36). ХХН11. Перейти к новому базису А„, который получается из старого базиса А, путем удаления его !-й строки и т-го столбца, (т. е. положить !,=!„. !ч-~ =!~ ь !т=!т+и ° ! ~ =!в' 1,=1„..., !с ~ -— Г~ и /с =ы+и .", ! ь»,. где !'и !» != 1, ..., з, й = 1, ..., з определяют старый базис А„).
ХХЧП1. Вычислить матрицу А, ' = (~ц)~~~",.",.',Й~', обратную к но- вой базисной матрице по правилам Если задача 1 невырожденная, то индекс р определяется однозначно. В случае вырожденной задачи можно выбратр любой инденс р, на котором достигается минимум в (4.35). ХХХ1. Вычислить величины б»= «~~ансс()с», й 1 ° ° °, и с с ХХХП.
Перейти к новому базису А„который получается из старого базиса А, путем замены его 1-й строки строкой (а„сч аш„, ..., а„; ) (т. е. положить 1, = р). ХХХП1. Вычислить матрицу А, ' = ((Зс»)~с=с",.",.,",', обратную но- вой базисной матрице по правилам 1 ° бс» — (рссб 1Ь" '), й ть 1; ()сс/б~~, й = 1, ХХХ1Ч.
Перейти к шагу П1. Теорема 1. Если выполнены предположения 1, то в невырожден- ном случае процесс решения задачи 1 алгоритмом 1 через конечное число итераций закончится либо на шаге )с (находится оптималь- ное решение х* задачи 1), либо на одном из шагов Х или ХХ1!1 (устанавливается, что функция цели задачи 1 неограничена на до- пустимом множестве решений). Библммра4ическне указания. Параграф написан на сснсвеннн работ К14, 415, 4161. 4.8. Итеративные методы Итеративные методы представляют собой последовательность однообразных по процедуре выполнения итераций, которые приводят в пределе к оптимальному решению задачи.
Их применение целесообразно в тех случаях, когда требуется достаточно быстро получить грубое решение задачи, а также при решении задач большого размера. Итеративные методы более помехоустойчивы, чем конечные методы линейного программирования. 1. Итеретнвныа метод Петшннонснсте 3 ад а ч а 1. Найти зги шах (с, х) для заданного вектора сЕ с 11" при ограничениях ср,(х) Й (а, х) — а~с ~ О, 'с = 1, 2, ..., сп; сР +с(х)йк,=(ес, х)~О, 1 — 1, 2, ..., п„(п, (п), -с где а — с-й вектор-строка матрицы А задачи 1.О; ес — и-мерный единичный вектор с единицей иа 1-и месте. 240 с о Если положить а + = е, а .~~ = О, 1 = 1, 2, ..., п„то ограничения (4,67) задачи 1 можно переписать в следующей эквивалентной форме: ф,(х)~~(а', х) — а~~О, 1= 1, 2, ..., т+п~ (4.за) В отличие от 'рассмотренных метод Петшиковского не является конечным.
Решение задачи 1 получается лишь в пределе. В методе Петшиковского задача 1 с ограничениями (4.38) приводится к задаче безусловной максимизации выпуклой экстремальной функции ~и+л, д„(х) ~ (с, х) + '" ~„б, (х) (ср, (х)1', где О, если ~р,(х) ) О, 6,(х) = — 1, если щ (х) ( О. Для решения задачи безусловной оптимизации применяетсв градиентный метод, который при достаточно больших )х дает хорошее приближенное решение задачи 1.
Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе с я". П, Выбрать параметр р ) О. 1П. Положить й = О. Ос н о в н о й ц и кл. 1Ч. Вычислить величины ()~=<р;(хг), 1 1, 2, ..., т+а,. Ч. Вычислить градиент функции у, в точке х = х" б$+Ю~ Чд„(х') = с+ р ~ б,(хг)))~а'. ю-~ Ч1. Вычислить величины Ь"=(а', Чдз(х')), 1=1, 2, ..., т+л,. ЧП. Для всех (Е [1: (т+ и,)), для которых $~~чь О, вычислить отношения 81 = — р1/$~" н расположить их в порядке возрас- тания ЧШ. Определить функцию ь(9)~ — й„(х" + ОЧд,(х")) = (с, Чй (хг))+ гИ+Л, +р ~ 6,( +ОЧИ„(х"))У;+ВРР. 1Х. Найти индекс 1Е (1: з), при котором выполни!отея нера- венства ДВ',,))О; ДВ'„+,)~О. Х. Вычислить шаговый множитель р, = к(е)) е~,„— дв~„,) в~)1иец) — дв~„,)). Х1. Вычислить следующее приближение х"+' = х'+ РРЫн (х') ХП.
Положить й = й + 1 и перейти к шагу 17. 7норема 1. Последовательность (ха) т",=с, порожденная алгоршп- иом 1, при любом хоЕ В" и !ь ) О обладает тем свойством, ипо !!шйт(ха, Х„) = О, едеՄ— множество, на котором достигается максимум функции 4н' йт (х, у) — расстояние от точки х к множеству )'.
Теорема 1'. Для любого е ) О существует такое ро ) О, что при любом р ) ро неравенстпво с(,(х, Х*)(е вьтолняется для любого х ~ Х„, где Х* — множество решений задачи 1. Из теорем 1 и 1' следует, что при достаточно больших значениях А и р точка х", полученная с помощью алгоритма 1, достаточно хо- рошо приближает решение задачи 1. 2. Иторатнаный метод, использующий модифициронаииую функцию Лагранжа 3 ад а ч а 2. Найти агд ппп (с, х) для заданного вектора об тех ~ В" н заданного множества Х~(х(Ах=а', х~О, х~В"), гдеас Е В"; А — матрица размера т х п. Предположение 3. Множество Х' решений задачи 2 непусто. Приводимый ниже алгоритм основан на построении модифицированной функции Лагранжа и требует на каждой итерации решать задачу минимизации квадратичной функции.
Этот метод дает решение задачи 2 за конечное число итераций к„ зависящее от величины коэффициентов штрафа и от выбора начального приближения двойственной переменной (при этом предполагается, что задача минимизации квадратичной функции решается за конечное число итераций). Алгоритм 2 Н а ч а л о.
1. Выбрать произвольное начальное приближение двойственной переменной у' Е В . П. Выбрать произвольную последовательность штрафных коэффициентовй (а»)»-е, а») О, Ь = О, 1, .... П1. Пол жить Ь = О. О с н о в ц о й ц и к л. 17. Определить модифицированную функцию Лагранжа ф(х, у, 'а»)й(с, х)+(у, а' — Ах)++((Ах — ал(». Ч. Вычислить приближение х»~ О основной переменной из условия ф(х», у», а») ш!пф(х, у», а»). «~е Ч1. Вычислить следующее приближение двойственной переменной у»+~ = у»+ сс (ае — Ах»).
ЧП. Положить Ь = Ь + 1 и перейти к шагу 1Ч, Теорема 2. Если выполняется предположение 2 и последовательность штрафных коэффициентов (а»)Г е такова, что а» э и» О„ Ь = О, 1, ..., то алгоритм 2 конечен, т. е. найдется «шкой номер Ь,, что х"'Е Х', у'Е )'*, где Х', )«е — множество седловых точек функции Лагранжа ~р(х, у) ~(с, х)+ (у, ае — Ах). Число Ь, тем меньше, чем меньше отношение р (у', )«е)lа. В частности, для всякого у' найдется а такое, чгпо при а, ) и алгоритм 2 закончится за одну шперацию, т. е. будет х' е Хе, у' с У е (здесь р (х, У) = 1п1 1 х — у 1).
гег Замечание 2. Важной проблемой в алгоритме 2 является выбор последовательности штрафных коэффициентов аы Ь О, 1, .... Увеличение х» выгодно с точки зрения уменьшения числа итераций. Однако при больших значениях а» трудно решать задачу минимизации функции ф (х, у», а»). Поэтому приемлемое значение а» следует выбирать в процессе вычислений. 3. Итера»вез»ей метод Федон»вне Э а дача 3. Найти агйш(п 2,' у,Ь~~ для заданного вектора «»У1 1 Ь' (Ь~|, ..., Ье) и заданного множества 1'й ~у~у, + 2',у,Ь(=О, 1= 1, ..., т; 1 1 а, ~(у,~~сс+, 1 1, ..., и; у~в"~. Если отобразить точки у = (у„..., у„) пространства Й" в точки х = (х„..., х, «) пространства «1 ~' по правилу «О «о ! «йо! Ь« й«« 6« (4.39) + у« ь «р«о « то образом и-мерного «параллелепипеда» о= (у!а, (у,(а«о, 1= 1, ..., и) будет выпуклый многогранник т в пространстве 11 +'.
Тогда метод решения задачи 3 сводится к отысканию минимального числа Х, для которого 1«е Е т, где е = (1, О, ..., 0) р Н +' (мннимальное значение Х обозначим через Хо). Приводимый ниже алгоритм определяет за конечное число итераций приближенное решение х вспомогательной задачи и ему соответствующее приближенное решение у задачи 3 (точность приближенного решения х задается константой 6,). Объем вычислений существенно зависит от выбора параметров алгоритма (о методике выбора этих параметров см. (363, 364, 365, 366, 367]).
На каждой основной итерации алгоритма 3 используется заданное число «малых» итераций любого выбранного алгоритма квадратичного программирования. Алгоритм 8 Н а ч а л о. 1. Выбрать вектор уЕ1«+' такой, что (у, е) = = 1 (здесь е = (1, О, ..., 0)). 11. Положить а« = (Р««» й«..., Ь«), 1 = 1, ..., п; е=(О, Ьи ...,Ь). П1. Задать число 1) 0 — количество «малых» итераций ре. щения вспомогательной задачи квадратичного программирования (обычно 1Р (10, 20)). 1Ч. Задать константы 6 р (О, 1), е ) О, «Мо (О ( «(о ( 1) о)о > О 6о > О, що > О.
Основ но й ц и кл. Ч. Вычислить величины «р, = (а', д), « = 1, ..., и. Ч1. Вычислить величины а,, если «р«~0, а«= + а«, если «р,(0, 1= 1, ..., и. Ч!!. Вычислить вектор 6 х= с+ ~~ а,а'. 1 ЧП1. Вычислить значение ~,(д) = (х, д). Отметим, что точка х — решение задачи пп!п(х, д) = 1,(у), кем прн этом 1, (д) дает точную оценку снизу для Л*: ~, (д) ( Л*.
1Х. Найти подмножество индексов У, (У, с: (1, ..., и)) по пра- вилу !4.40) 1 е И„если ! <р, ! ~ (а ) а' (о, где норма ! г(а определяется как расстояние точки г от прямой Ле ( — со - Л ( со), отсчитываемое в плоскости 6, проходящей через г ортогонально вектору у, н вычисляется по правилу )г(~ =1г — (г, д) е!. (4.4!) Х. Вычислить точку х=с+ ~, "а,а'. МУв ХЧ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
