И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 40
Текст из файла (страница 40)
Оптимальному решению ха задачи 1.0 соответствует оптимальное решение у' задачи О, причем оптимальные значения прямой и двойственной задач совпадают. Оптимальное решение двойственной задачи определяется по формуле у'=(сп, сче ..., с~ )В ', где  — базисная матрица оптимального опорного решения задачи 1.0; 1» ..., 1 — индексы базисных векторов. Для начала работы алгоритма необходимо иметь опорное решение у = (у„ ..., у ) сопряженной (двойственной) задачи и его базис а', ..., а', на основании которых вычисляется исходное почти 204 допустимое опорное решение с неотрицательными оценками по правилу: в начале находят коэффициенты разложения г»о, 1 = 1, ..., т, вектора а' по базису а', ..., а; далее составляют вектор х =* (х, х„ ...,х„), 1-я компонента хй (1 = 1, ..., т) которого равна гм, ос. тальные компоненты вектора х равны нулю. Алгоритмы отыскания опорного решения сопряженной задачи и его базиса приведены в пункте 2.
Алгоритм 1 применяют для вырожденной н невырожденной задачи 1.0. Если при использовании алгоритма к решению задачи 1.0 в вырожденном случае возникает зацикливание, то в алгоритме 1 необходимо применять процедуру, гарантирующую от зацикливания. Алгоритм у Н а ч а л о. 1. Найти почти допустимое опорное решение х = = (х„х„..., х„) задачи 1.0 (с неотрицательными оценками Лп 1 =. = 1, 2, ..., л) и базис а', а', ..., а' этого почти допустимого опорного решения. П.
Вычислить матрицу В ', обратную к исходной базисной мат. рице В, состоящей из столбцов а', а'*, ..., а' . 1П. Разложить по исходному базису а', а', ..., а' векторы а', а', а*, ..., а" (т. е. найти числа г»п й = 1, 2, ..., т; 1 = О, !, ..., л, т такие, что а» = 2, г»~а'», 1' = О, 1, ..., л), по формулам » ! г»»=хи го»=хоп . ° 1 Апо=х» ~ т т (гп, гоп..., г ~) = В (ап, аоп ..., а;), 1= 1, ..., л. Отметим, что заранее известно разложение по исходному базису базисных векторов а'», й = 1, ..., и: га = О при й~1, га = 1 при й = 1, й = 1, ..., и; 1=1, ..., т. 1Ч. Вычислить для каждого 1' Е П: л! оценку Ь~ — — 2,' с»»г»1 — сл »-1 Ос н о в но й ц и к л. Ч.
Если для всех й Р И: т] выполняется неравенство г»о~ О, то положить х'= х и прекратить вычисления (т. е. в этом случае почти допустимое опорное решение х оптимально); иначе перейти к шагу Ч1. Ч1. Если существует такое й р [1: т], что г»о ( О и при всех / Е [1: л] выполняется г»~,=о О, то прекратить вычисления (в этом 205 случае задача 1.0 не имеет допустимых решений); иначе перейти к шагу ЧП.
ЧП, Выбрать (по заранее оговоренному правилу) индекс г Е ч 11: т) такой, чтобы г,о ( О. ЧП1. Вычислить отношения Л /г,/ для всех тех 1 б (1: п), для которых г„( 0 и обозначить минимальное по абсолютной величине из этих отношений через О, (напомним, что Л, ~ О, 1~ (1: и)). 1Х. Найти индекс зС [1: и) такой, что г (О и — Л,/г„= О,. Для невырожденной задачи 1.0 индекс з определяется однозначно. В вырожденном случае минимальное отношение В, может достигаться для нескольких индексов 1 ~ (1: и). Поэтому на практике в качестве з выбирается наименьший индекс 1, для которого достигается минимальное отношение.
Теоретически в вырожденном случае необходимо применять процедуру выбора з, гарантирующую от зацикливания (см. пункт 3). Х. Положить гз/=ге/, я=1, ..., т; / 1, ..., п и Х/ — — Лп /=1, ..., и. Х1. Перейти к новому базису а', а', ..., а, который получается заменой вектора а" в предыдущем базисе вектором а' (т. е. 1=з). ХП. Вычислить координаты векторов аь, а', ..., а" в новом базисе: гм = гз/ — (гн/гр~) гм, 1 = О, 1, ..., п; й=1, ...,г — 1,г+1, ...,т. г„=г„/г„, /=О, 1, ..., п. ХП1. Вычислить по основным формулам оценки Лр / ~ (1: п), отвечающие новому базису Л~ — — Ь~ — (г,//г„) Ь„, 1 = 1, ..., п.
Х1Ч. Перейти к новому почти допустимому опорному решению х =(х„х„..., х„); х~„гиь й = 1, 2, ..., т, остальные координаты вектора х равны нулю. ХЧ. Перейти к шагу Н. Теорема 1. Если выполнены предположения 0 и задача 0 невырож- денная, то процесс решения задачи 1.0 с помощью алгоритма 1 за- кончится через конечное число итераций, либо на шаге У (в этом случае находится апти льнов решение задачи 1.0), либо на шаге У/ (в этом случае устанавливается, что задача 1.0 не имеет допус- тимых решений).
Замечание 1. Так как число итераций, необходимых для реше- ния задачи линейною программирования, определяется в основном 206 количеством непрямых ограничений, то двойственный симплекс- метод целесообразно применять, когда число непрямых ограниче- т!ий существенно превосходит число переменных. 2. Методм отыеиаиви походного опорвого ро!пеппи еопрюиевиев та дачи у =(о, ..., о, у„о, ..., 0), где у, ~~а шах (с)/а!!). !~/~л Вектор у' удовлетворяет ограничениям задачи 0 и поэтому является допустимым решением задачи О.
Предположение 2'. (!) — ранг матрицы А равен т; (11) — и) ) п4; ((и) — допустимое множество сопряженной задачи 0 непусто. Алгориизм 2 1. Найти вектор у'= (у!, ут, ..., у ) — допустимое решение сопряженной задачи 0 такое, что ~,а!!у!)сп 1= 1, ..., н,; ! 1 - (4.6) ! ! П. Найти число г — количество линейно-независимых условий в (4.5). Если г = и!, то прекратить вычисления (т.
е. у' — опорное решение задачи О, а векторы а!ь ..., а!», определяемые линейно- независимыми условиями, составляют базис этого опорного решения); иначе перейти к шагу П1. П1. Выразить из системы равенств (4.4) л. апу! = с( ! ! (4.6) )=па+1, ..., п, 207 В подпункте 2' дается метод отыскания опорного решения сопряженной задачи 0 при условии, что известно произвольное допустимое решение задачи О.
В 2" на основании метода, приведенного в 2', рассматривается алгоритм, позволяющий найти оптимальное решение сопряженной задачи (а значит, и прямой) без предварительного вычисления допустимого решения сопряженной задачи. 2'. Метод отыскания опорного решения сопряженной задачи по известному допустимому решению. Предварительно укажем класа задач, в которых определение допустимого решения не представляет труда. Пусть в задаче 1.0 одна и та же компонента а!ь 1 = 1, ...
..., л, всех векторов а), 1= 1, ..., и, положительна. Построить вектор , у.)= ~ 8!у!+У. с- +! 1, ..., л!, то перейти к шагу Х1П; ина- у!(у~+! Ч1. Если Ь!= О, ! = г + че перейти к шагу ЧП. ЧП. Вычислить я )4(= Х а!Аз 1= 1* е л! г+! Ч111. Если р (. О, 1 = 1, ..., л„то прекратить вычисления (в этом случае линейная форма задачи О не ограничена снизу на допустимом множестве); иначе перейти к шагу 1Х. 1Х. Вычислить Л! — — ~, а!(у! — с(, ( = 1, ..., л,. ! 1+1 Х. Вычислить (4.9) О, = ш)п(Ь(l(4;). я,.>о Х1.
Перейти к новому допустимому решению у"= (уь " у») по правилам у,. = у'. — О,(!„! = г + 1, ..., у!, ", у, находят через у,+„..., у по (4.1). Х11. Вычислить индекс й с (1: л,) такой, что В,=(Д,(р,), р,~о, и прекратить вычисления. В этом случае построено новое допустимое решение у", которое обращает в равенства г + ! линейно-независимых условий из 208 г переменных у, ..., у, через остальные переменные: у(= Е !(!!у!+!тп /= 1в ° ° ° е г.
(4.7) ! г+! 1Ч. Заменить переменные у„ ! = 1, ..., г, в неравенствах т Ха!;у!)сп 1= 1, ..., лм ! их выражениями из (4,1) и получить систему неравенств относительно у.+ь " У ш ауу,~сн 1=1 ° ° ° ° "1 (4.8) с= +! Ч. Подставить в линейную форму (с4, у) задачи О значения переменных у„..., у, из (4.7) и получить линейную функцию у! переменных у,+!, ..., у системы ограничений задачи О, т. е. г линейно-независимых условий из системы (4.5) ч"ауУ;=си /=и1+1, ..., и, !=! и линейно-независимое от системы (4.5) условие из (4.4) ~; асчу; = с„й ~ 11: и!1.
ХП1. Вычислить величины Л!., / = 1, ..., и, по (4.9). Х1Ч. Вычислить величину О, по правилу пп1п (Л!/а,'+! ), если среди а,',, 1= 1, ..., и„ а,+!,;>О ИМЕЮтея ПОЛОжИтЕЛЬНЫЕ ВЕЛИЧИНЫ; — ппп ( — Л/а,'+!.), если а,'+,.(О для 1= 1, ..., и,. аг+! <О ХЧ. Перейти к новому допустимому решению у"= (у„..., у ) по правилам: у! = у,'., ! = г + 2, ..., и; У!-!-! У~+! О уь ..., у, находят через у,+!, ..., у по формуле (4.7). ХЧ1. Вычислить индекс й С (1: и,! такой, что ЕО=Л,Ъ; „ и прекратить вычисления (см. шаг ХП). Теперь можно применить алгоритм 2 к допустимому решению у (т.
е. сделать еще одну итерацию) и получить допустимое решение у", которое превращает в равенства г + 2 линейно-независимых ограничений задачи О и т. д. Не более чем за т — г' итераций будет получено опорное решение сопряженной задачи О (здесь г'— число линейно-независимых условий-равенств для у'). 2 . Метод отыскания оптимального решения сопряженной задачи без предварительного вычисления допустимого решения. Алгоритм 2' 1.
Выбрать достаточно большое число )) ) О (р больше любого числа, с которым его приходится по ходу решения сравнивать). П. Составить расширенную сопряженную задачу: (О!.+х !.,) ° ° -- 1=! а УО + Х ссуу, ~ сп / = 1. .. и; с=! УО>О (Прямой расширенной задачей является задача 1.0 (с переменными х„х„..., х„), в которой к ограничениям Ах = ао, х ~ 0 добавлены ограйичения х,+ хо+," + хе= й' хо ~ )О).
! П. Вычислить у,' = шах (с„..., с„, О). 1Ч. Составить вектор у' = (у,, о, ..., 0), и+1 являющийся допустимым решением расширенной сопряженной задачи. Ч. Отправляясь от допустимого решения у' с помощью метода, приведенного в подпункте 2', вычислить опорное решение расширенной сопряженной задачи, его базис и почти допустимое опорное решение расширенной прямой задачи.
ЧЕ Решить прямую расширенную задачу двойственным симплекс-методом и получить векторы: х* = (хо, х!, ..., х,) — оптимальное решение прямой расширенной задачи; у* = (уо,у!, ... ..., у ) — оптимальное решение расширенной сопряженной задачи. ЧП. Если уо — — О, то уе= (у!, ..., у') — оптимальное решение сопряженной задачи О, а х* = (х!, ..., х„) — оптимальное решение задачи 1,0. Если уо ) О, то сопряженная задача 0 и прямая задача 1.0 неразрешимы. Алгоритм 2' за конечное число итераций находит оптимальное решение прямой задачи 1.0 и двойственной задачи 0 без предварительного вычисления допустимого решения сопряженной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
