И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 45
Текст из файла (страница 45)
ХЧП1. Найти козффициенты г»п й 1, ..., т; / 1, ..., л, разложения векторов а», „а" по векторам нового базиса: а) если г = т + 1 (если базиа не изменилея), то положить г»; г',, й 1,...,т; 1=!»...,л; » а) если г = т + 1 (базис не изменился), то положить Ьс пРи 1-ь в; Ьс —— — Ас при 1= е; б) если г(т+ 1 (базис изменился), то вычислить величины уп 1 = 1, ..., и по основным формулам ус —— у',.
— (г,',.1г;,) у',, 1 1, ..., и, и положить Лс —— ( — 1)'сус, 1= 1, ..., и, где чс = О, если хс — — с»с, и ос — — 1, если хс = рс, Заранее известно, что Лс = О, если 1Р 7-,. Поэтому вычисле. ниЯ Лс следУет пРоводить длЯ 1 с1 Р-,, т.
е. когДа или хс а, или хс = рс. ХХ1. Перейти к шагу Ч1. Теорема1. Если выполнены предположения О, то в нееырожденном случае процесс решения задачи 0 алгоритмом ! через конечное число итераций закончится либо на шаге У1 (находипсся оптимальное решение задачи 0), либо на шаге У11 (устанавливается, что функция цели задачи 0 неогран ичена на допустимом множеспме Х). Алгоритм 1 может применяться также для решения вырожденных задач линейного программирования с двусторонними ограничениями. Только при возникновении цикла следует использовать специальное правило вывода вектора из базиса, исключающее зацикливание.
2. Правило выбора иидекеа г(оиределвкицего вектор и г, с выводииыа вз балиев) длл вродотвращеиив зациклвваиив Если прн использовании алгоритма 1 для решения задачи линейного программирования в вырожденном случае возникло зацикливание, то на шаге Х П или Х 1Ч алгоритма следует применить следующую процедуру выбора индекса г, гарантирующую от зацикливания. Алгоритм 2 Н а ч а л о. 1. Вычислить линейно-независимую систему векторов ис», й = 1, ..., т, исс = с а» при гнс(рс, »' — а'» при г»о = рс .
П. Вычислить у»с, 1с = 1, ..., т; 1 = 1, ..., т,— коэффициенты разложения векторов св», й = 1, ..., т, по базису а', ..., ак, т. е. 233. такие, что ш!= Х ума'», )=1, ..., пг. ь 1 1И. Положить у„+! ! = О, ( = 1, 2, ..., оз. Ос но в н о й пи кл. 1Ч. Если х, = а„то перейти к шагу Ч; если х, = ()„то перейти к шагу Х; Ч. Найти множество б„состоящее из тех индексов й, на которых Оа = гп!и гьо — ть *ытьо гы 1кьм к+! Ч1. Положить )ь = О. Ч11. Если б„состоит из одного элемента, то приняты равным этому элементу и прекратить вычисления; иначе (если 6» состоит более чем из одного элемента) перейти к шагу Ч111. Ч11!.
Найти множество 6»+ь состоящее из индексов й Е 6», на которых ппп (уь +1/г~,). 1Х. Положить )ь = р + 1 и перейти к шагу ЧП. Х. Найти множество б,, состоящее из индексов й, на которых ть — еао Ео= пйп зм»о гзз ьяьк и+! Х1. Положить )ь = О. Х11. Если 6» состоит из одного элемента, то приняты равным этому элементу и прекратить вычисления; иначе (если 6» состоит более чем из одного элемента) перейти к шагу Х111.
Х111. Найти множество 6».ьы состоящее из индексов и Е б„, на которых достигается шах (уь».ь~/гз,). аео» Х1Ч. Положить )ь = )ь + 1 и перейти к шагу Х11. Теорема 2. Алгоритм 2 генерирует конечную последовательность множеств ба, бм ..., 6„! ( т, такую, что бг содержит единспюенный элемент, который принимается за г. Библиографические указания. При написании параграфа использовались ра боты [4!4, 4!5, 4!б). »34 4 7. Моднфикациа симплекс-метода длл решении общей аадачи линейного программировалил л 3 а д а ч а 1.
Найти аги шах ~~ с/х/ для заданного вектора м / 1 с = (с„с„..., с„) при ограничениях л а//х/ — — Ь!, ! = 1, ..., р! ! а»х/ ~ Ь!, 1 = р + 1, ..., т! ! х/,,в0, 1=4+1, ..., и. (4.зз) рьзо) (4.з!> а!,/, а/,ь ... а!,/ а!,/, а!,/, ... а!,/ А, 4)! св! /, а! /, .. . а!,!, г матрицы А с! (а!/)1й!~,'."."," такую, что: а) столбцы матрицы А, содержат все столбцы матрицы А, для которых компонента х/ положительна в х или не ограничена требованием неотрицательности, 1, 1 для 1 = 1, 2, ..., д; б) строки матрицы А, образованы условиями (4.30) и некоторы- ми из условий (4.31), причем все такие ограничения-неравенства удовлетворяются допустимым решением х как строгие равенства, !! = А для Ь = 1, .", Р Подматрица А„порождаемая опорным решением х, называет- ся его базисом.
Определение 2. Опорное решение х задачи 1 е базисом А„ назы- вается невырожденным, если х/,)О при! = 4+ 1, у+2, ..., е; О ~ а!/х/~Ь! при (чЕ*1„(й 1, ..., з). / ! С одной стороны, задача 1 может быть решена методамн, приве- дениь1ми выше, если предварительно свести ее к каноническому виду с п + т — (р + д) неотрицательными переменными и т — о условиями равенствами, с другой — существует ряд классов задач линейного программирования (например, двойственные задачи при Предпололсепол 1.
(Ф) — уравнения (4.30) линейно-независимы; (И) — векторыа/ (а», аз, ..., а„/), 1 1, ..., // — линейно-нег зависимы; (!г!) — задача 1 имеет допустимое решение. Определение 1. Допустимое решение х = (х„..., х„) задачи 1 называется опорным, если оно порождает неособенную йвадратиую подматрицу т ( и — т), которые выгоднее решать в их естестве!)аой записи. Ниже приводится модификация симплекс-метода для!решения задачи 1 в естественной записи.
В начальной стадии алгоритма требуется иметь опорное решение и его базис, а также необходимо вычислять матрицу, обратную к исходной базиснрй. На каждой итерации алгоритма опорное решение проверяется на оптимальность; если оно не оптимально, то осуществляется переход к новому опорному решению н новому базису (лучшему от предыдущего, т.
е. дающему большее значение целевой функции). В невырожденном случае за конечное число итераций находится оптимальное решение х", либо устанавливается неограниченность линейной формы на допустимом множестве решений. В вырожденном случае теоретически может возникнуть зацикливание, тогда необходимо применять специальное правило, гарантирующее от зацикливания. Алгвршим 1 Н а ч а л о. 1. Найти исходное опорное решение х = (х„... ..., х„) задачи 1 и его базис А„образованный элементами, стоящими на пересечении строк и столбцов матрицы А с номерами !„..., !, и 1„..., 1„соответственно. 11. Вычислить матрицу А, ' = (бм)~!=,!'С",, обратную к матрице А„.
Ос н о в н о й ц и к л. 111. Вычислить числа !Ч. Вычислить величины 'Ь! — — ~, а! !Лг — сн 1 = 1, ..., и. г=! Ч. Если выполняются неравенства Л, »О, я=р+1, ..., з; Ь!~О, /=1, ..., и, то положить ха = х и прекратить вычисления (в этом случае опорное решение х является оптимальным решением задачи 1); иначе положить А„= А„(для этого надо положить 1, = /!, 1 = 1, ..., з; 7„= = !'„Й = 1, ..., з); х = х; р!г — — рм; 1 = 1, ..., з; й = 1, ..., з и перейти к шагу Ч1: Ч1.
Среди величин Л», й = р + 1, ..., з, и Ьп 1 = 1, ..., и, найти наименьшую. Если наименьшей величиной оказалось б„г Е р(1: п1, то перейти к шагу Н1, а если Л„(р [(р + 1) ! з), то перейти к шагу ХХ1. 711. Вычислить величины г!г = с ~ Рсга!г~ 1 1э ° ' е Ф ! 236 ЧП1. Вычислить параметр ~ ! ~ ~ | ~ С ~ ~ ~ ~ ° ~ ~ ~ | ! ~ ~! ш!и (х;,(г!,), если существует з!,) О, 1) и; ~„>о е'. = с,. ,со, если г!,(О для 1=д+1, ..., з. 1Х. Вычислить параметр Во по формуле гп(п( — !Ъ!о!6!), если существует 6! (О, ! В(1 ! л!); в = ° ! (4.зз) оо, если 6!;>О, !'=1, ..., л!, где Ь' Ь! — т~~~асгх!ч ! = 1, ..., пг; (з ! 1 т! 6, = ~~ а!!,г!, — я!. !' = 1, ..., и!. 1=! Х.
Вычислить параметр В, по формуле Е, = ш(п (В'„ В,). Если Е, = оо, то прекратить вычисления (в этом случае целевая функция задачи 1 неограничена на допустимом множестве); если В,!( оо, то перейти к шагу Х1. Х[. Вычислить новое опорное решение х (х„..., х„) по формуле х = х — Е,Ь, где Ь = (Ьг, ..., Ь„) — вектор, определяемый по правилу г!„если 1=1!, 1 1, ..., з; Ь.= — 1, если 1=г; ! О, в остальных случаях.
ХП. Если Е,= Ез, то перейти к шагу ХП1, если Е, = Ез, то перейти к шагу ХЧП. ХП1. Вычислить индекс ч р 1(о + 1) . з) такой, что В!!=ху!,Йчк зчг~е (4.34) Х!!!. Перейти к новому базису А„который получается из старого базиса А„путем замены его т-столбца столбцом (а!зч а!,„..., ас!,)" (т. е. положить 1, г). ХЧ. Вычислить матрицу А, ' = (р!»)! !,",",,,', обратную, новой ба- зисной матрице по правилам 1 Р!» — Ро»г!.—, /Ф т1 оуг р!» = — /=т, г, ' ~!»+ 6»з!,/а для 1, й = 1, ..., з; — 6»/ао зюг/ао 1/ао для 1=а+1, й= 1, ..., з; для 1 1, ..., а, й = з+ 1; для 1 й а+1, где 6» и а, вычисляются, соответственно, по формулам в 6» ~; а»/йт» й=1, ..., з; т ао — — а — ~~~ со„/ гт,. 7 где/=1,..., зи/о=1,...,з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
