И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 44
Текст из файла (страница 44)
положить г, = р, 1, = тн). Отметим, что йрн переходе к новому базису меняется также козффнцнент линейной формы ор н точка к~'. с Г Г ХЧ1П. Вычислить по основным формулам матрицу В ', обратную к новой базисной матрице: Рн =Гауки 1 1. ° э т+з1 ри=5и — (В;Ж. )у 1.=1, ..., т+з; 1=1, ..., т+з; Х1Х.
Вычислить по основным формулам новые значения базнсных координат опорного решения г,-задачн: ую = у/с/укн1 Уес = Уес (Укс1ук ) уен й 1с ° ° ° ~ г — 1, г+ 1, °, т+ 3. ХХ. Положить г',е = увь я = 1, ..., т+ з, н перейти к шагу П1. Теорема 2. Если допустимое множество решении задачи 2 непусто, уравнения-ограничения задачи 2 линейно-независимы и целевая функция задачи 2 ограничена на допустимом множестве решений, то за конечное число итераций алгоритм 2 приводит к оптимальному решению задачи 2 (при етом предполагается, что если в вырожденном случае возникает зацикливание, то, по аналогии с пунктом 8 (р 4.1), применяется специальное правило выхода из цикла). а.
йтетон, всповъеуюиХий обобвХеивый гредвевтвый спуск 3 ада ч а 3. Найти агатах (с, х) для заданного вектора с Е к с Л" прн ограничениях с ле ссйх~(Ь~|, 1 = 1, ..., тб ны ае ~ а»(х(~ (Ьм я = 1, . ° °, и!»', ! ! х(~0, 1= 1, ..., п. Задача, двойственная к задаче 3, имеет вид. 3 ада ч а 3', Найти агдш(п(~„Ь!у!+ ~, Ь~»г») при огра(аг! г=! » ! ничениях (4.2з) ГИ~ бн т! ! х! а!;у,+ ~, а»;г»~сп 1= 1, ..., и; ! 1 » ! у, !. О, ! = 1, ..., т;, г » О, й = 1, ..., т„ здесь у = (ум ..., урн), г = (г», ..., гщ,). Предположения 3. (1) — задача 3 имеет оптимальное решение; (й) — система ограничений (4.27) и (4.28) вырезает в пространстве ограниченный многогранник Х!.
В приводимом ниже методе решение задачи 3' сводится к минимизации (методом обобщенного градиентного спуска) выпуклой кусочно-линейной функции 7 л <р* (у) (й шах (~', с(х(+ ~, у! ~Ь! — ~„'а!;х! '-! ! ! ! ! при простейших ограничениях у!»: О, ! = 1, ..., т,. На каждой итерации алгоритма требуется решать задачу линейного программирования с ограничениями (4.27) и (4.28). Метод обобщенного градиентного спуска удобно применять к таким задачам линейного программирования, двойственные к которым имеют блочную структуру.
Алгоритм Я Начало. 1. Положитьу» =(О, О, ..., О). И. Положить 1= 1. Основной цикл. П1. Положить у у'. 1Ч. Решить задачу линейного программирования: 7 и »!, / л найти зги (пах~~, с;х)+ ~, у,(Ь! — ~ а!~!х! х при ограничениях (4.27) и (4.28); обозначить ее решение через х* (у!), а через г (у!) — вектор оптимального решения двойственной задачи. Ч. Вычислить вектор й = (й!, ..., Ь',), ! ! 6| =Ь! — ~'а!)х)(у'), »=1, ..., т.
!=1 Ч1. Вычислить шаговый множитель р!. 'т1П. Вычислить вектор где и+ — оператор, оставляющий неотрицательные координаты без изменений и обращающий отрицательные координаты в нуль. Ч111. Положить 1 = 1+ 1 и перейти к шагу 111. Теорема Ю. Если выполняются предположения 3 и шиловые множители удовлетворяют условиям Ф р, ) О, ! = 1, 2, ...; р, -ь О; ~, р, = оо, ! г=! то последовательность (гр* (у))! ! сходится к оптимальному значению функции гр* (у) на множестве у ~ О, при етом пара векторов (у', е (у')) сходится к оптимальному решению двойспюенной задачи д'.
Библиографические указания. Пункты 1, 2 написаны на основании работ [88, 115, 4571, пункт 3 — на основании работы [3941. Дополнительные сведении о методах блочного программирования можно найти в работах [20, 52, 55, 458, 168 — 170, 166, 182, 211, 237, 258, 347, 353, 361, 495, 791. 4.6. Модификация симплекс-метода для решения задачи линейного программирования с двусторонними ограничениями 3 ада ч а О. Найти агатах 2„' с!х! для заданного вектора гех г=! с = (с„..., сч) и заданного множества ограничений Х~(к[Ах= Ь, а!(х!<[)п 1=1, ..., и; хб)!1"), где А — т ~с и-матрица; Ь вЂ” и-мерный вектор; а1, р1, 1 с И: п!— некоторые числа. Предположения О.
(г) — ранг матрицы А И(свг))! !,',"„","„= = (а', ..., а") равен т; (й) — и ) т; (гй) — множество ограничений Х непусто. Определение 1. Допустимое решение х = (х„..., х„) задачи О называется опорным, если система векторов а', соответствующих компонентам х1, для которых а! ( х! < [1Ь (4.29) линейно-независима. Определение 2. Система т линейно-независимых векторов, содержащая совокупность всех векторов, которым соответствуют компоненты х! опорного решения х, удовлетворяющие (4.29)! называется базисом опорного решения х. 229 Определение 8.
Опорное решение х задачи О называется невырожденным, если т его компонент удовлетворяют неравенствам (4.29). Задача О называется невырожденной, еслп все ее опорные решения невырожденные. Ниже приводится модифицированный симплекс-метод решения задачи линейного программирования с двусторонними ограничениями применительно к виду задачи О. Для начала работы алгоритма требуется иметь опорное решение и его базис. Метод приводит к решению задачи О (либо устанавливает неограниченность линейной формы на множестве Х) за число итераций, не превышающее !Ч = Сей" (эта оценка справедлива для невырожденной задачи О). Если алгоритм 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'Е Р„- Лг = О. 230 Ч. Вычислить оценки уь если !х!(х (~~', Ь,= -(; — ун если х, = ри где уг — — ~'„с!,гм — сн ! = 1, ..., п. А=! О с н о в н о й ц и к л. Ч1. Если все Л! ~ 0 (! = 1, ..., и), то положйть х*= х и прекратить вычисления (в этом случае опорное решениех является оптимальным решением задачи 0); иначе (т.
е. если при некотором ! Е П: п[ выполняется Л!( 0) перейти к ша- гу ЧП. Ч11. Если существует индекс ! Е П ! л! ~, Р-„для которого Л!( 0 и выполняется одно из условий(1) — при х! = а! для ам) 0 сю! — — юо, для гм( 0 р! — оо, (и) — при х! — ~~ для гм ) 0 = юю, для гм ( 0 !х!„— со, то прекратить вычисления (в этом случае функция цели задачи 0 неограничена на допустимом мно- жестве Х); иначе перейти к шагу Ч11. Ч1П. Найти индекс з~ П: а1 такой, что Л, = ш[п Ь; и полоГвнсп жить а~"'+! = а' (т.
е. получить расширенный базис а", ..., а~', !г4 т-~-! ) Индекс а принадлежит множеству П: л[ '~, У„- и определяет век- тор и', который может включаться в старый базис. В качестве з можно брать любой индекс, для которого Ь,( О. 1Х, Положить г„+!,, = — 1, х +!л = х, Х. Если х, = а„то положить т = 0 и перейти к шагу Х1; если х, = [3„то положить т = 1 и перейти к шагу Х1!1. Х1. Вычислить величины у„при таких й с П: (т + 1)1, что гать 0: сю! при гм ) 0; [1!, при гм(0 Х11. Вычислить параметр Ою преобразования опорного реше- ния х ююю дю = ппп г гю~!йю м !мю~ !!+! ю~ю Ъ.
обозначить через г индекс такой, что О, = ' и перейти ю!! к шагу ХЧ. В невырожденном случае индекс г определяется однозначно. В вырожденном случае в качестве г выбирается наименьший индекс, на котором достигается минимум. Если в вырожденном случае возникает зацикливание, то следует испольэовать правило, выводящее из цикла. 23! ХП1. Вычислить величины р» при й Е И . (т + 1)1, для которых гь~ 0; ю»»», если гм(0; 7» ~* ~~, если г», ) О. 'Х 1Ч.
Вычислить параметр О, преобразования опорного решения х по правилу 7»- г»ю О,= ппп г» »ю»» ~а»~ »+1 т» — г.ю что О, ' и перейти г„ обозначить через г индекс, такой, к шагу ХЧ (см. шаг ХП). ХЧ. Положить х'= х; гц — — г»ь у~ ун1 1,...,л;б»=йп)=1. ХЧ1. Вычислить новое опорное правилу й=1, ..., т, 1=!, ..., л; ... л, и перейти к шагу ХЧ!. решение х = (х„..., х„) по х~ — ( — 1)'О,г»ь если ! = 1»„й = 1, ..., т; «. + ( — ! )" О„если ! = з; х» = хю, если ! Я Р-„!Фз. б) если г ( т + 1 (т. е.
если базис изменился), то вычислить гм по основным формулам га = г ~lг»»» 1 = 1» . ° ° » л» г»» = 㻠— (г„уг)») г»», 1=1,...,л; й=!,...,г — !,г+1,...,т. Х1Х. Положить г»ю х... й = 1, ..., т. ХХ. Вычислить оценки Ьр 1= 1, ..., л, отвечающие новому базису~ ХЧП. Положиты„з, т. е. заменить в расширенном базисе а", ..., а», а'"+' значение вектора а ° значением вектора а' и перейти к новому базису а'*, ..., а, который получается из первых т векторов расширенного базиса (при переходе к новому базису старый базио не меняется, еели г = т + 1 и в старом базисе меняетоя значение одного вектора а », если г ( т + 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
