И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 39
Текст из файла (страница 39)
111. Если пРи некотоРом (еС(1: т! выполнЯетсЯ Уеь «О, то прекратить вычисления (в этом случае задача 0 не имеет допустимых решений); если при всех (Е (1.* т) выполняется у~с О, то положить х*= (хь ..., х„) и прекратить вычисления (т. е. в этом случае вектор (хь хм ..., х„) является оптимальным решением о о о задачи О). Теорема 2'. Пусть выполняется предположение 2'. Если для всех доспиипочно больших значений М М-задача имеет оптимальное решение, то алеоритм 2' либо устанавливает недопустимость задачи О, либо находит оптимальное ее решение, а если при тех же условиях М-задача неразрешима, то неразрешима и задача О.
3. Свмнлеве-метод решенно вырожденной ванонвчеевой аадачв лввейното нротрмммвроаавва В этом пункте приводится симплекс-метод решения вырожденной задачи О, для которой выполняются условия (1), (й), (111) предположения О. Если применить алгоритм 1 для решения вырожденной задачи О, то возможно зацикливание процесса решения задачи (т. е. возвращение к уже пройденному базису бесконечное число раз), так как на шаге Х алгоритма 1 в вырожденном случае существует, вообще говоря, больше чем один номер г, для которого достигается минимальное отношение Ое = г,о/г„,. Симплекс-метод для решения вырожденной задачи линейного программирования включает в себя специальное правило выбора выводимого вектора из базиса, которое гарантирует от зацикливания процесса решения задачи. 199 Алгоритм 3 1 — 1Х (шаги 1 — 1Х такие, как и в алгоритме 1).
Х. Вычислить отношение г»о/гм для тех /о, для которых г». ) О и обозначить минимальное из этих отношений через О,. Х1. Положить / = О. ХП. Положить Ооо = О,. Х1И. Вычислить индексы г,, г„..., гц такие, что г,,о/г„= г,,о/г„= ° ° = г, о/г., = О',. в ''' ц о о. Х1Ч. Если 1! — — 1, то вместо вектора а" ввести в базис вектор а' (х. е. положить 1,, = в) и перейти к шагу Х1Х; если 1! ) 1, то перейти к шагу ХЧ.
ХЧ. Вычислить О~+' = ш!п (г„ц+н/г,„, гон+и/г„„..., г,, ц+н/г,, 4. Х'Ч1. Положить г, = г„г, = гм .... и = г» . ХЧП. Среди множества индексов (г„г, ..., гг! ) найти индексы г„г„..., гц+„для которых гну+и/гои = гон+и/гге = ° ° ° г, ц+и/г,, = О~о+~ ° г,.+, с/+~ ХЧП1. Положить / =/+ 1 и перейти к шагу Х1Ч. Х1Х. При каждом / Е П . и) вычислить О/ = гав/го~. ХХ.
Положить г»~ — — гм, й * 1, ..., «ц / = 1, ..., и. ХХ1. Вычислить координаты векторов а', а', ..., а" в новом базисе: при й4 г г»! = гм О/г»» / ~ О~ 1, ~ и; й=1, ..., г,— 1, г»+1, ..., т! при Ф г» г»у Оп /=О, 1, ..., и. ХХП. Перейти к новому опорному решению х' = (х~ь ..., х„'). хо ~г»о, Й~1, ..., т, остальные координаты вектора х' равны нулю. ХХП1. Перейти к шагу П1. Теорема 3. Если вы«олнены условия (1), (И), (йг) предположения О, «ю через конечное число итераций процесс решения задачи О алгорит- мом 3 закончится либо на шаге ЛГ (находшпся оптимальное решение задачи О, равное опорному х' = (х1, ..., х„)), либо на шаге !//1 (ус- танавливается, что оп«шмального решения задачи О нет).
Замечание 3. На практике алгоритм 3 используется редко, по. скольку он требует значительно больше времени для решения задачи линейного программирования по сравнению с алгоритмом 1, а зацикливание процесса решения вырожденной задачи алгорнтмом 1 маловероятно.
Если же прн решении задачи О алгоритмом 1 произошло зацикливание на некотором опорном решении, то следует использовать алгоритм 3 для получения нового опорного решения н дальше продолжать решенне задачи О с помощью алгоритма 1. 4. Модифииироииииый еииииеие-метод Во многих случаях модифицированный симплекс-метод (нлн метод обратной матрицы) более экономный в вычислениях, чем обычный (особенно это проявляется, если число уравнений-ограничений т существенно меньше размерности пространства и).
На каждой итерации в модифицированном алгоритме вычисляется матрица, обратная к базисной, что сводятся к вычислению по основным формулам т векторов размерности т (напомннм, что в основном снмплекс-методе на каждой итерации по основным формулам вычисляется л — т + 1 вектор). Модифицированный симплекс-метод применяется для решения невырожденных н вырожденных канонических задач линейного программирования.
Алгоритм 4 Н а ч а л о. 1. Найти исходное опорное решение х' = (х~!, хз, ... ..., х„') задачи О н базис а', а!з, ..., а~ этого опорного решения. В общем случае для нахождения исходного опорного решения н соответствующего ему базиса используют алгоритм . 2 нлн алгоритм 2'. 11. Вычислить матрицу В ' = фз!)~о=='з',",,',", обратную к походной базисной матрице В. 111.
Положить гзо = х), й = 1, 2, .... т. Основной ц н кл. 1Ч. Положить со„= (ссо сз„..., сз ). Ч. Вычислить вектор — 1 Ь = сбззВ Ч1. Для каждого /Е [1: и! вычислить оценку й! — — Ьа! — сл 1= 1, ..., и. Ч11. Если все й! ~ О (1 = 1, ..., и), то положить х* = х' и прекратнть вычисления (т. е. в этом случае опорное решение х' оптимально); если прн некотором 1 С [1: л! выполняется й; ( О, то перейти к шагу Ч1П.
А!11. Выбрать по заранее оговоренному правилу индекс зЕ ~ [1: и! такой, чтобы Л, ( О. 1Х. Вычислить вектор-столбец т — ! з (гьо гз„..., г,) =В а. 201 Х. Если при всех й Р П: и) выполняется гм( О, то прекратить вычисления (в этом случае целевая функция (с, х) не ограничена (сверху) на допустимом множестве Х); иначе перейти к шагу Х1. Х1. Вычислить отношение гоо/го, для всех я ~11: т), для которых гм ) О и обозначить минимальное из этих отношений через О,.
Х!1. Найти индекс г ~ [1: т) такой, что г„) О и г о/г„= йм Х111. Положить рм = ~,н й = 1, ..., и; / = 1, ..., и, и гоо =. =гоо,/о=1, ...,т. Х1Ч. Перейти к новому базису а'*, ..., а', который получается заменой вектора а ~ в предыдущем базисе вектором а' (т. е. положить !~ 8). ХЧ. Вычислить по основным формулам матрицу В = (Рм)ь.~,::;,, обратную к новой базисной матрице Он = 5н / гпо / = 1, ..., и; ро/=()о/ — (ра/г,.)гм, й=1, ..., т; /=1, ..., т; й~г.
ХЧ1. Вычислить по основным формулам новые значения базисных координат опорного решения гю = гю/г„; гм=гоо — (гюй„)гм, й=1, 2, ..., г — 1, г+1, ..., т. ХЧ11. Перейти к новому опорному решению х' = (х(, ..., х„')' 1 хо ~ гоо~ й 1~ ° \ и\ -остальные координаты вектора х' равны нулю.
ХЧП1. Перейти к шагу 1Ч. Теорема 4. Если выполнены предположения 0 и задача 0 нееырожденная, то процесс решения задачи О алгоршпмом 4 через конечное число итераций закончшпся либо на шаге Ч// (находится оптимальное решение задачи 0), либо на шаге Х (устанаелиеается, что оптимального решения задачи 0 нет). Замечание 4. На практике алгоритм 4 применяется также для решения вырожденной задачи линейного программирования, для которой выполняются условия (1), (й), (И) предположения О. В этом случае теоретически возможно зацикливание процесса решения задачи О алгоритмом 4.
Если при решении задачи О алгоритмом 4 на некотором опорном решении все-таки произойдет зацикливание, то (аналогично пункту 3) необходимо включить в алгоритм 4 специальное правило выбора выводимого вектора из базиса, гарантирующее от зацикливания. Замечание 4'. Если на шаге ХЧ алгоритма 4 матрицу В ' вычислить по формуле В ' = 1),В ', где В ' — матрица, обратная к 202 базисной на предыдущей итерации, а Р, имеет вид 1 ... 0 — гы/г„О ... 0 0 ... 1 — г, 1„/г,.О ... 0 0...0 1/г„0...0 0 ... 0 — гл~.гл/ггз 1 ° ° ° 0 Р Г 0 ...
0 — г„,/г„О ... 1 то такой модифицированный симплекс-метод называется мультипликатиеньам. Для записи матрицы Р, достаточно знать т + 1 чисел: число г и числа — гы/гсм ..., 1/гом ..., — г /гьм Если обозначить через Р, матрицу Р, в Й-й итерации мультипликативного алгоритма и за исходную базисную выбрать единичную матрицу /, то обратная к базисной в й-й итерации будет вычисляться по формуле Из этой формулы видно, что для вычисления матрицы В ~ в Ьй итерации мультипликативного алгоритма требуется знать (т+ 1)Й чисел, что на начальной стадии вычислений приводит к экономии оперативной памяти ЭВМ.
4.2. Двойственный симплехсс-метод Двойственной (сопряженной) к задаче 1.0 (см. 2 4.1, задача 0) называется задача О. 3 а дача О. Найти агдш[п(а', у) для заданного вектора а' аеУ и множества У, заданного соотношениями К=(у[А у>е, уЕВ ) Предположения О. (4) — ранг матрицы А равен т; (14) — и ) '= т; (111) — задача 1.0 разрешима. 1. Основной алгоритм Определение /.
Почти допустимым опорным решением задачи 1.0 называется вектор х = (х„х„..., х„), удовлетворяющий уравнению Ах = а', причем векторй а/, соответствующие ненулевым координатам вектора х, линейно-независимы. 203 Библиографические ухамтлия. Прн написании параграфа использованы работы [414, 415, 4!6, 226, 1141, дополнительные сведения о симплекс-методе и его вариантах, о построении исходного опорного решения и его базиса, о решении вырожденных задач можно найти в работах [414, 415, 416, 411, 78, 65, 11, 187, 21, 45, 199, 348 641. Определение 2. Базисом почти допустимого опорного решения х задачи 1.0 называется любой упорядоченный набор из т линейно- независимых векторов аг, содержащий все векторы аг, соответствующие ненулевым координатам вектора х.
Практический интерес представляет почти допустимое опорное решение и его базис, для которых справедливо Л~ ~ О, / = 1, ..., а. В 1415) такое решение называется псевдопланом задачи 1.О, а базис — псевдобазисом задачи 1.О. В алгоритме 1 на каждой итерации осуществляется переход от одного базиса задачи 0 к другому (или, что тоже самое, от одного псевдобазиса задачи 1.0 к другому). Определение 3. Допустимое решение у двойственной задачи 0 называется опорным, если среди условий А у ~ с, которые оно т г обращает в равенства, имеется т линейно-независимых условий. Определение 4. Базисом опорного решения двойственной задачи 0 называется произвольная система из т линейно-независимых векторов а', ..., а прямой задачи, для которых (у, а'~)=с~, з=1, ..., т. Определение 5.
Опорное решение у двойственной задачи 0 называется невырожденным, если для любого вектора аГ, не входящего в его базис, (у, а~) ) с;. Определение 6. Двойственная задача О, все опорные решения которой являются невырожденными, называется невырожденной. Двойственный симплекс-метод (или метод последовательного уточнения оценок) решения задачи 1.0 по своей сути — зто применение обычного симплекс-метода к двойственной задаче О, дополненное построением на каждой итерации п-мерного вектора х, являющегося почти допустимым опорным решением задачи 1.0 (отсюда происходит название метода). Двойственный симплекс-метод заключается в таком последовательном переходе от одного почти допустимого решения х к другому, что через конечное число переходов либо получим оптимальное решение задачи 1.О, либо установим, что задача 1.0 не имеет допустимых решений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
