И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 48
Текст из файла (страница 48)
Алгоривсм о Н а ч а л о. 1. Выбрать произвольное начальное приближение (х'- у') Е В" х гд . 11. Выбрать произвольный параметр а ) О. 111. Положить й = О. 1Ч. Определитьфункции /дс (у), / = 1,..., и, и е, (д), $1, ... ..., т, соответственно, по правилам Ьс(у) = ~ассу! — сс, /= 1, ..., и, (у= (уд, ..., у )); с=! и е,(х) = — ~; ассхс+ Ьс, с = 1! ° ° ., пд, (х=(хд, ..., х„)).
с=! Ос н он но й ц и к л. Ч. Вычислить шаговый множитель рд, удовлетворяющий условиям теоремы 5. г г ,Ч1. Вычислить вектор уг (ус, ..., у ) по правилам у,' — ае, (х"), если е, (хсд) ( 0; у~(1 — аес(хсд)), если 0(ес(х") ~(1/а; уд О, если е,(х")) 1/а, здесь 1= 1, ..., пс. 251 Ч11. Вычислить следующее приближение х +' = (ха1+', ... х'„+') по правилам шах (х' — раЬг (уа), О), если Ьг(уа)(0," шах (х[а — Ра [Ь;(У') — а (Ь!(Уа))Я~, 0~, если 0< < Ь! (уа) < 1/а; !пах (х[а — ра[Ьг(уь) — Ьг(уа) + — „~, 0), если Ь,(у') ) ) 1/а, здесь[=1, ..., и. а ЧП1. Вычислить вектор ха = (хи ..., х~) по правилам х" — аЬг(уа), если Ьг(уг)<0; х" (1 — аЬг(уа)), если 0<Ьг(уа)<!/а; если Ьг(уа) ) 1/а, О, здесьу=[, ..., и. 1Х.
Вычислить следующее приближение у+ = (у,+, а+! «+! ..., у + ) по правнлам шах (у,' — раз, (х"), 0), если ее(ха) <О; шах ~УЯ вЂ” Ра[г, (х") — — (з, (ха)) ~, 0~, если 0 < е, (х") ~; < 1/а; шах (у,". — р„ [з,(ха) — з,(ха) + — 2а ], 0), если з, (х') ) ) 1/а, уа+! е 0<р„<р, 8=0,1, ...; [ппр„=О; [пп ~„'рг= со, г атее ь ° е=о то последовательности (хл)а=с и (уа)г" е, порождаемые алгоритмом б, при любом а ) 0 сходятся, соолгветственно, к Х* и Уе. Бнбяиографняеские указания. Пункт 1 написан на пснпваннн работ [4!6, 5351, пункт 2 — [30[1, пункт 3 — [363 — 3671. Прн напнсаннн пункта 4 использовалась работа [341, а пункта 5 — [821. Итеративные методы решения задач линейного программирования научалнсь также в [44, 88, 85, !66, 2[5, 333, 359, 53[, 456, 44[, 5[.
252 здесь[=1, ..., т. Х. Положить /г й+ 1 и перейти к шагу Ч. Теорема б. Пусть выполняется предположение б. Тогда суи[ествует такая константа р ) О, епо если шалавые множители р» в алгоритме б выбирать согласно условий 4.9. Методы параметрического программирования 1. Случай валичиа параметра в целевой фуипции Задача 1. Найти ага !пах ~. '(с'+)!сл!)х; для заданных чи- / ! сел с', с,'., 1 = 1, ..., и, при ограничениях Ах — ае. х~О, где Х вЂ” параметр.
Лредиоложения !. (1) — множество ограничений задачи 1 непусто; (11) — ранг матрицы А равен т; (111) — п ) т. Определение 1. Базис опорного решения задачи 1 оптимален для некоторого значения )!, если оценки Ь всех векторов а!, 1 = = 1, ..., и, относительно этого базиса, вычисленные при данном Х, неотрицательны. Полная совокупность значений параметра )!, при котором базис оптимален, называется множеством оптимальности этого базиса. Алгоритм, приведенный ниже, в невырожденном случае указывает (за конечное число итераций), при каких значениях )! ~ ( — оо, оо) задача 1 неразрешима и при каких — разрешима, причем в случае разрешимости вычисляется оптимальное решение и его базис.
Р этом алгоритме требуется решать задачу 1 симплекс-методом при одном или нескольких значениях параметра )!, при этом исходное решение и его базис вычисляются один раз. В случае вырожденности задачи линейного программирования в алгоритме 1 теоретически возможно зацикливание (тогда надо применять специальное правило, гарантирующее от зацикливания в симплекс-методе). Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное число Хе. 11.
Положить 1 = О. Основной цикл. 111. Положить)!.=аь 1Ч. Положить й = О. Применить к решению задачи 1 симплекс- метод (если 1) О, то исходное опорное решение и его базис для решения задачи 1 при )! = Х! известны из предыдущих итераций). Если задача 1 при Х = Х! разрешима, то перейти к шагу Ч (при этом считаются известными: оптимальный базис а', ..., а; оптимальное решение (х!, ..., х„); коэффициенты разложения векторов а', а', ..., а" пооптимальному базису, т. е.
числа г!;, 1 = О, 1,... ..., и; 1= 1, ..., т). Если задача 1 при Х = )!, не разрешима (т. е. целевая функция задачи 1 не ограничена), то перейти к шагу ХХЧ111 (в этом случае известны некоторое опорное решение задачи 1 и его базис а', ..., а', коэффициенты разложения г!;, и, кроме того, индекс 1, Е ~ [1: и) такой, что А;, ( О и при всех 1~ [1: т) выполняется х!й ( О). 253 Ь,'= Е ссгсс — с', 1=1, ..., и. (4.48) сс с' Ч1. Вычислить значение Л„по правилу — 00, ЕСЛИ ВСЕ ЬС(0; Л» = шах[ — Ьс/Ьс), в противном случае. Ьс>0 с Ч11.
Вычислить значение Л» по правилу + оо, если все Ь; »0; Л„= ппп [ — Ь()Ьс), в противном случае. (4 вв) Ь)<0 Ч1111 Выдать на печатьс «Множество оптимальности базиса а', ... ..., а ~ состоит из всех значений Л, удовлетворяющих условию Л»,:; ~ Л ~= Л»». ЕСЛИ Л, = 00 И Л» —— — 00, тО ПрЕКратИтЬ ВЫЧИСЛЕНИЯ; ИНаЧЕ ПЕ- рейти к шагу 1Х. 1Х. Если й = О, то положить -с„с, -с, с, -с с (4.49) ! Ь,( = Ь;, ! = 1, ..., и; Ьс» = Ьс, ! = ]э ..., и; ).0 — — ЛО, гсс = гсь ! = 1, ..., т; / = О, 1, ..., и, и перейти к шагу Х„иначе перейти к шагу Х. Х.
Если Л»= 00, то перейти к шагу ХЧ)11; иначе вычислить индекс з р [1 с и) такой, что 1 $, 2 Ь2 (4.5$) и перейти к шагу Х1. Х1. Если при каждом 1Р [1: т] выполняется гс, ( О, то выдать на печать: «линейная форма задачи ! для Л ) Л» неограничена в допустимой 'области» и перейти к шагу ХЧП1; иначе перейти к шагу Х11. Ч. Для каждого )Е [1: и] вычислить составляющие оценок Ьс векто(вов ас, ] = 1, ..., и, относительно оптимального базиса «2', ..., а ЗаДаЧИ 1 ПРИ Л = Лс Ь, = Ьс' + ЛсЬс! (4лв) 1 Ь; = ~, сс гсс — сс, ) = 1, ..., и; (4.4т) С-1 ХП. Вычислить индекс г ~ П .
т), удовлетворяющий условию г «/г„= пцп (гсоlгь), г„) О. (4.52) *с«»2 ХП1. Перейти к новому базису, который получается заменой вектора а ° в предыдущем базисе вектором а' (т. е. положить(, = = 2). Х1Ч. Положить гс;=г», 1=1, ..., т; 1=0, 1, ..., л; 1 1 2 2 Ьс Ьс Ьс Ьс 1 1 ХЧ. Вычислить координаты всех векторов а', а', ..., а" в новом базисе по основным формулам: при 1~г г» = гп — (г«с/г««) гси 1 = О, 1, ..., л; (4.53) 1=1,...,г — 1,г+1,...,т, при 1= г (4.55) (4.55) -с а'.=а', аь а'*, ..., а =а Ь'=Ь,', /=1, ..., и; Л,=Х,; Ьс'= Ф гсс гсс» ХХ.
Вычислить 1 1,...,т; 1=0,1,...,а. индекс з Е 11: а) такой, что 1 а, 2 — — =Х,; Ь)О. 52 ХХ1, Если при каждом 1Е П: т! выполняется га я', О, то выдать на печать: «Линейная форма задачи 1 для )с(Х~ неограничена в допустимой области», и прекратить вычисления; иначе перейти к шагу ХХП. ХХП. Вычислить индекс г Е П: т), удовлетворяющий условию (4.52). 255 гс/=г,с/г... /=О, 1, ..., и. (4.54) ХЧ1. Вычислить составляющие оценок Ьс векторов а/, 1 = 1, ... с, с, ..., и, относительно нового базиса а*, ..., а «и — 1 — г — 1 Ьс =Ь; — (г,ссг„)Ь„ /= 1, ..., а; Ь,'=Ь'; — (г„/г„)Ь'„ /=1, ..., а.
ХЧП. Положить й = й + ! и перейти к шагу Ч1. ХЧП1. Если )с« * — оо, то прекратить вычисления; иначе положить й = 0 и перейти к шагу Х1Х. Х1Х. Перейти к исходному оптимальному базису, исходным оценкам Ьс, Ьс н исходным коэффициентам разложения гсь т. е. положить ХХП1. Перейти к новому базису, который получается заменой вектора а ° в предыдущем базисе вектором а' (т.
е. положить с, = 2). ХХ1Ч. Положить гл=зсс, 1=1, ..., т; 1'=О, 1, ..., и; 1 1 2 2 Лс = Ьсч Л/ = Лс, 1 = 1, ..., и. 1 «з 1 !. С»Сс = Х сс,асс,— сс,, 2 «» 2 2 С»С. = 2» СС ЗН вЂ” СС 131 С С С т н 12 определены на шаге 1Ч). О, то выдать на печать: «Задача 1 неразрешиао)» и прекратить вычисления; иначе пере- (индексы со ! = 1, ..., ХХ1Х. Если с»2, = ма при всех с! Е ( — ао, йти к шагу ХХХ. ХХХ. Вычислить )«+! = — (лс,!ст';,). ! 2 Если Ьс ) О, то выдать на печать: «Задача 1 неразрешима при )2()!«+1» и перейти к шагу ХХХ! для анализа задачи при Х ~ «) с+!. Если 51 ( О, тэ выдать на печать: «Задача 1 неразрешима при )!»)!с+г» и перейти к шагу ХХХП для анализа задачи при )1( ( )!«» 1. ХХХ1.
Если на предыдущих итерациях был дан анализ задачи ! для Х ~ )!«» 1, то прекратить вычисления; иначе положить 1 = = 1+ 1 и перейти к шагу Ш. 256 ХХЧ. Вычислить величины гн, 1 = 1, ..., т, ! = О, 1, ..., и; Лс~„! = 1, ..., и; бс, 1 = 1, ..., и, соответственно, по (4.53) — (4.56). ХХЧ!.
Вычислить значения )!2+1 и Ц+1 по формулам (4.49) н (4.50). Выдать на печать: «Множество оптимальности базиса а', ., а состоит из всех значений Х, удовлетворяющих условию )„„1~1,(),„!». Если А»» ! —— — оо, то прекратить вычисления; иначе перейти н шагу ХХЧП. ХХЧП, Положить й = й + ! и перейти к шагу ХХ. ХХЧП1. Вычислить составляющие оценки Ь;,: 2.
Случай мялячяя параметра в правых частая огряаячеляй 3 а д а ч а 2. Найти аги |пах (с, х) для заданного вектора сЕ Е г1" при ограничениях я ~,аь;хь=Ь|!.+ЛЬ|, |=1, 2, ..., т; | (4.87) х; ь О, / = 1, 2, ..., и, (4.88) где Л вЂ” параметр. Предположения 2. (|) — целевая функция задачи 2 ограничена на допустимом множестве при всех Л; (й) — ранг матрицы А равен т; (Й!) — и ) т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
