И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 49
Текст из файла (страница 49)
Если при некотором значении параметра Л коэффициенты ~заложения вектора Ь = Ь' + ЛЬ' (здесь Ь' = (Ь|~, ..., Ьь ), Ь' = (Ь, ..., Ь')) по векторам базиса сопряженной задачи неотрицательны, то этот базис является оптимальным базисом задачи 2 для данного Л. Определение 2. Полная совокупность значений параметра Л, при которых базис оптимален, называется множеством оптимальности этого базиса. Приведенный ниже алгоритм разбивает вещественную ось Л на участки, на каждом из которых вычисляется оптимальный базис, ие изменяющийся с изменением Л, а также выделяет область (если она существует), в которой ограничения задачи 2 несовместны. Алгоритм основан на применении двойственного симплекс-метода для решения задачи 2 при одном или нескольких значениях параметра Л. Алгоритм 2 применяется в невырожденном и вырожденном случаях.
В вырожденном случае теоретически возможно зацикливание. Если зацикливание произойдет, то необходимо применять специаль. ное правило, гарантирующее от зацикливания в двойственном симплекс-методе. Алгориьпм 2 Н а ч ал о. 1. Выбрать произвольное число Л,. П Положить ! = О, Основной цикл. П1. Положить Л=Л,. |17 Положить й = О. Применить к решению задачи 2 двойствен. ный симплекс-метод. э з-мь 287 ХХХП. Если на предыдущих итерациях был дан анализ задачи ! для Л ( Ль+ь то прекратить вычисления; иначе положить ! = ! .! 1 и перейти к шагу 111. Теорема 7.
Если выполнены предположения 1, то в невырожденном случае алгоритм 1 за конечное число итераций разбивает веи4гь: поенную ось Л на области, в которых задача ! или неразрешима гвследствие неограниченности целевой функции), или имеет апти мальное решение !'причем известны оптимальный базис и оптималь. ное опорное решение). Если в результате находится оптимальное решение задачи 2 и его базис (обозначить оптимальное решение через (х, (Л,), х, (Л,), ... ..., х„(Л,)), его базис через а", ..., асм, оценки через >Л„1 = 1, ..., л, а коэффйциенты разложения векторов ас (1 = 1, ..., и) по базисным векторам через ги, 1 = 1, ..., т, 1 1, ..., а), то перейти к шагу Ч; если в результате выявится несовместность условий (4.57) и (4.58) при Л = Л„то перейти к шагу ХХХ1.
В этом случае, в соответствии с признаком несовместимости (см. шаг Ч1 алгоритма 1, 8 4.2) существует такое 1, Е П: т), что гс,о ( 0 и при всех 1 Р П: а) гс,с,'~: О, где гсо, 1 = 1, ..., т — коэффициенты разложения вектора Ь' + Л, Ь' через базисные векторы а", ... ...; а.м сопряженной задачи. Ч. Решить систему уравнений Ь'- ~а'сх (Л,) с ! относительно х;, (Л,). ! Ч1.
Решить систему уравнений Ь'=* ~а схс! (Лс) ь-! относительно х~~, (Л,). ЧП. Положить гсо = хс, (Лс)' гсо = хс,(Лс)> 1 1> "° т Ч111. Вычислить — оо, если все гсо~(0> (1=1> ..., т), Л„= шах ( — гсоугсо), если существует гсо) О. (4.881 >)о)о !Х. Вычислить значение Л по правилу + оо, если все а!о~О, Л Снсн ( — гас«/г«СО), ЕСЛИ СущЕСтВуЕт гСО( О, (4.ОО) >)ос« здесь 1= 1, ..., т. Х. Выдать на печать: «Множество оптимальности базиса а'*, а', ..., а состоит из всех значений Л, удовлетворяющих условию 3.«( Л ( Лоо и перейти к шагу Х1.
Х1. Если Ло- — — оо и Л„+со, то прекратить вычисления; иначе перейти к шагу ХП. 258 ХП. Если й = О, то положить -с, с а >и сс>о. > 1)с =Ъ 1= 1 .. ° а> )~>>=)~о гсс = гц> 1 1,...,т; )=1,...,п; г)о =гссо> гсо=г)о, 1=1, ..., и, и перейти к шагу ХП1; иначе перейти к шагу Х1П. ХП1. Если А = +со, то перейти к шагу ХХ1; иначе вычислить индекс г Е (1: и) такой, что г — Ыгю = )!о', г.о (О. Х1Ч. Вычислить индекс з Е (1: а) такой, что — Ыг,.
= ш1п ( — Ьсlг,с). (4.6() о„(о гсс' = гсС вЂ” (г>С1г») гс>, 1 — 1, ... > пс 1=1, ...,г — 1,г+1, ...,т, при 1= г гсс = г>с(гг» 1 = 1> ° ° ° > ХЧП1. Вычислить оценки (4.62) (4.6з) Ьс — — Ьс — (г,с!г„)Л» 1'= 1, ..., п. Х1Х. Вычислить величины гссо и 4, 1 = 1, ..., и, по фоРмулам: гсо = гсо — (г,'о/г„) гс„1= 1, ..., г — 1, г+ 1, ..., ! -! г>о = г>о(гл (4.64) основным (4.65) 2 2 > гм = гсо — ( ю(г„) гс„1 = 1, ..., г — 1, г + 1, ..., т; (4 66 2 2 гю = гю!гю 259 ХЧ.
Положить гц=гц, 1=1, ...,и; )=О, 1, ...,и; сос = Лс, 1 = 1, ..., и; ! 1 2 2 гм = гсо, гсо = гкь 1 = 1, ..., т. ХЧ1. Перейти к новому базису а', ..., ас, который получается заменой вектора а" в предыдущем базисе вектором а' ( т. е. положить с, =6). ХЧП.
Вычислить координаты всех векторов а', ..., а" в новом базисе по основным формулам: при 1Ф г ХХ. Положить й = й + 1 и перейти к шагу Ч1П. ХХ1. Если Л, — оо, то прекратить вычисления; иначе положить й = О и перейти к шагу ХХП. ХХП. Перейти к исходному оптимальному базису, исходным оценкам, исходным коэффициентам разложения, т. е. положить ~>о ~»> а' =а' а'>=а", ..., а'"=а > 1=1 ° ° ° > и Л«=Ло' гп=гл, 1=1, ..., и; 1=1, ...,и; з)о=о)о, з)о=2)о> 1=1, ..., и. ХХП1.
Вычислить индекс г Е П: и) такой, что — г,'о/г', Л„и г,':» О. ХХ1Ч. Вычислить индекс о Е П: п1, удовлетворяющий условию (4.61). ХХЧ. Положить зл=зя> 1=1, ..., и, 1=1, . ° ., и; Ь~ — — Ьп 1=1, ..., и; ! ! о 2 зоо=яоо, зсо=зсо> 1=1, ..., и. ХХЧ1. Перейти к новому базису, который получается заменой вектора а о предыдущего базиса вектором а' (т. е.положить 1, = о). ХХЧП. Вычислить величины Йп>1=1, ..., и; 1=1... °, 6> Ьп 1=1, ..., л; г,'и 1=1, ..., и; г,'и 1=1, ..., и, соответственно по (4.62) — (4.66). ХХЧП1. Вычислить значения Ло+~ и Ло+, по (4.69) и (4.60) соответственно.
Выдать на печать: «Множество оптимальности базиса а", а *, ..., а' состоит из всех аначений Л, удовлетворяющих условию Ло+~ ( Л ( Хд+,». ХХ1Х. Если Ло.ь~ — — — оо, то прекратить вычисления; иначе перейти к шагу ХХХ. ХХХ. Положить й = й + 1 и перейти к шагу ХХП1. ХХХ!. Вычислить величины а~в, 4, 1 = 1, ..., и, по тем правилам, что и на шагах Ч, Ч1, ЧП.
ХХХП. Если ф = О, то выдать на печать: «Ограничения эа. дачи 2 несовместнмйе при всех Л Е ( — оо, оо)» и прекратить вычисления; иначе перейти к шагу ХХХП1. ХХХ111. Вычислить 1 /2 Лг+! = — (гйе' гг,е). Если гг,е) О, то выдать на печать: «Ограничения задачи 2 несовместимйе при всех Л < Зц~.!» и перейти к шагу ХХХ1Ч для аиат лиза задачи при Л ) Лг,ь, если гйе < О, то выдать на печать: «Ограничения задачи 2 несовместимйе при всех Л ) Л,+!» и перейти к шагу ХХХЧ для анализа задачи при Л < Лг+ь ХХХ1Ч. Если на предыдущих итерациях был дан анализ задачи 2 для Л ~ Лг+ь то прекратить вычисления; иначе положить ! = ! + 1 и перейти к шагу НЕ ХХХЧ.
Если на предыдущих итерациях был дан анализ задачи 2 для Л< Лг+и то прекратить вычисления; иначе положить ! = 1+ 1 и перейти к шагу Н1. Теорема 2. Если выполнены предположения 2, то в невырожденном случае алгоритм 2 эа конечное число итераций разбивает веи4ественную ось Л на области, в которых или задача 2 имеет опти. 'мальный базис и оптимальное решение, или ограничения задачи 2 несовместимы. Бнблиогратйнегскне укаэоння. При написании параграфа испольаовались работы [88, 226[ и др. Дополнительные сведения о методах параметрического программирования можно найти в работах [310, 311, 190, 477, 478, 554, 4751.
4.10. Опорные методы 3 ада ч а О. Найти агатах (с, х) для заданного вектора са как Е В" и заданного множества Х(й (х(Ах= ае х~О, хЕВ"). Предположения О. (г) — ранг матрицы А равен т; (аг) — т:= < и; (И) — задача О имеет допустимые решения. Опорные методы занимают промежуточное положение между конечными и итерационными методами решения задач линейного программирования.
Вместо понятий «опорное решение» и-«базис опорного решения» используются их обобщения — «допустимое решение» и «опора». В приводимых алгоритмах процесс решения задачи можно вести или до получения оптимального решения, или остановить на и-оптимальном решении, отклонение которого от оптимального по целевой функции не превосходит заданной величины г.-» О. Начиная с некоторого номера итерации опорного метода совпадают с итерациями симплекс-метода.
достоинством опорных методов является то, что они позволяют аффективно использовать хоРошие начальные приближения, интуицию и опыт специалистов. Другими достоинствами является более простое отыскание начального опоРного плана по сравнению с отысканием опорного решения и его базиса. 261 Определение 1. Совокупность векторов а'*, ..., а'м называется опорой задачи О, если уравнение ~~ а'ех! = О (а', ! = 1, ..., п,— 3 ! столбцы матрицы А) имеет только нулевое решение х! = О, з = 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}
