Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 184
Текст из файла (страница 184)
Лемма 29.1. Рассмотрим вызов процедуры Рвот(/Ч,В,А, Ь,с, [[,1,е) при ам ф ф О. Пусть в результате вызова возвращаются значения (1Ч, В, А, б, с, [[), и пусть х обозначает базисное решение после выполнения вызова. Тогда 1. х =Одлявсех[Е1Ч. хе = 6[/а[е. 3. х; = Ь[ — агеЬ для всех ге  — (е).
Доказав[власа[во. Первое утверждение верно, поскольку в базисном решении все небазисные переменные задаются равными О. Если мы приравняем 0 все небазисные переменные в ограничении х[ = 6, — р а,ух ч уем то получим, что х; = Ь; для всех у е В. Посюльку е е В, то, согласно строке 2 процедуры Р[чот, получаем хе = бе = Ь[/а[е~ что доказывает второе утверждение.
Аналогично, используя строку 8 для всех г Š — (е), получаем х; = Ь[ = Ь[ — а;,Ь„ что доказывает третье утверждение. Глава 29. Линейное программирование 899 Формальный еимилекс-алгоритм Теперь мы готовы формализовать симплекс-алгоритм, который уже продемонстрировали на примере. Этот пример был очень удачным, однако нам еще необходимо ответить на следующие вопросы. ° Как определить, что задача линейного программирования является разрешимой? ° Что делать, если задача линейного программирования является разрешимой, однаю начальное базисное решение не является допустимым? ° Как определить, что задача линейного программирования является неограниченной? ° Как выбирать вводимую и выводимую переменные? В разделе 29.5 мы покажем, как определить, является ли задача разрешимой и, в случае положительного ответа, как найти каноническую форму, в которой начальное базисное решение является допустимым.
На данном этапе предположим, что у нас есть процедура 1н1т1Аиге 81МРеех(А, Ь, с), которая получает на входе задачу линейного программирования в стандартной форме, т.е. матрицу А = (а; ) размером т х и, т-мерный вектор Ь = (Ь,) и и-мерный вектор с = (с,). Если задача неразрешима, процедура возвращает соответствующее сообщение и завершается. В противном случае она возвращает каноническую форму, начальное базисное решение юторой является допустимым.
Процедура 81МРеех получает на входе задачу линейного программирования в стандартной форме, описанной выше. Она возвращает и-мерный вектор х = = (х ), юторый является оптимальным решением задачи линейного программирования, заданной формулами (29.19Н29.21). 81МР1.ЕХ(А, Ь, с) 1 (Лг, В, А, Ь, с, о) — 1н!т!Атее 81мРеех(А, Ь, с) 2 зч1п1е (пока) с > О для некоторого индекса 7' Е Л1 3 бо выбрать индекс е Е Лг, для которого с, > О 4 1ог (для) каждого индекса 1 Е В 5 бе11а >О 6 11зеп Ь1 — Ь;/а;, 7 е1зе Ь; — оо 8 Выбираем индекс 1 Е В, который минимизирует Ь1 9 11Ь1 = со 1О 1пеп гегпгп "Задача неограниченна" 11 е1ве (Л1, В, А, Ь, с, и) — Р1чот(Ж, В, А, Ь, с, о,1, е) 12 1ог 1 — 1 1о п 13 оо 111 Е В 14 11геп х; - Ь; Часть Ч11.
Избранные темы 900 15 е!зе т! — 0 16 ге!пгп (хызз,...,т„) Процедура Я!мрьнх работает следующим образом. В строке 1 выполняется вызов упомянутой выше процедуры 1н1т1Аы2в Б!ми.нх(А, ь, с), которая или определяет, что предложенная задача неразрешима, или возвращает каноническую форму, базисное решение юторой является допустимым. Главная часть алгоритма содержится в цикле ч ййе в строках 2-11. Если все юэффициенты целевой функции отрицательны, цикл чЫ!е завершается. В противном случае в строке 3 мы выбираем в качестве вводимой переменной некоторую переменную х„коэффициент при которой в целевой функции положителен. Хотя в качестве вводимой можно выбирать любую такую переменную, предполагается, что используется некое предварительно заданное детерминистичесюе правило. Затем, в строках 4-8, производится проверка каждого ограничения и выбирается то, которое более всего лимитирует величину увеличения х„не приводящего к нарушению ограничений неотрицательности; базисная переменная, связанная с этим ограничением, выбирается в качестве хь Если таких переменных несколько, можно выбрать любую из них, однако предполагается, что и здесь мы используем некое предварительно заданное детерминистическое правило.
Если ни одно из ограничений не лимитирует возможность увеличения вводимой переменной, алгоритм выдает сообщение "неограниченна" (строка !0). В противном случае, в строке 11 роли вводимой и выводимой переменных меняются путем вызова описанной выше процедуры Р!уот(М, В, А, Ь, с, и,1, е). В строках 12-15 вычисляется решение для переменных хы хз,..., х„исходной задачи линейного программирования путем присваивания всем небазисным переменным значения О, а всем базисным переменным х! соответствующих значений Ь;. В теореме 29.10 мы покажем, что зто решение является оптимальным решением задачи линейного программирования. Наконец, в строке 1б возвращаются эти вычисленные значения переменных исходной задачи линейного программирования. Чтобы показать, что процедура 8!ми.нх работает юрректно, сначала покажем, что если процедуре задано начальное допустимое значение и она завершилась, то при этом или возвращается допустимое решение, или сообщается, что данная задача является неограниченной.
Затем покажем, что процедура 8!мр!.нх завершается; и наконец, в разделе 29.4 покажем„что возвращенное решение является оптимальным. Лемма 29.2. Пусть задана задача линейного программирования (А, Ь, с); предположим, что вызываемая в строке ! процедура 1н1т!Ашхн 81мрьнх возвращает каноническую форму, базисное решение которой является допустимым. Тогда процедура 8!мР1.ех в строке 16 возвращает решение, которое является допустимым решением этой задачи линейного программирования. Если процедура 8!мг~.ех Глава 29. Линейное программирование 901 возвращает в строке 10 сообщение "неограниченна", данная задача линейного программирования является неограниченной. ,1!оказалгельслгво. Докажем следующий тройной инвариант цикла.
В начале каж- дой итерации цикла и 'пйе в строках 2-11 1. имеющаяся каноническая форма эквивалентна канонической форме, полученной в результате вызова процедуры 1н!т!АБО 31МРеех, 2. Ь; > 0 для всех аЕ В, 3. базисное решение, связанное с данной канонической формой, является допустимым. Инициализация. Эквивалентность канонических форм для первой итерации очевидна. В формулировке леммы предполагается, что вызов процедуры 1н1- т!Аыее 8!ми.ех в строке 1 процедуры 01мееех возвращает каноническую форму, базисное решение которой является допустимым.
Следовательно, третье утверждение справедливо. Далее, поскольку в базисном решении каждой базисной переменной х; присваивается значение Ь1, а допустимость базисного решения предполагает неотрицательность всех базисных переменных х,, то Ь; > О. Таким образом, второе утверждение ннварианта также справедливо. Сохранение. Покажем, что данный инвариант цикла сохраняется при условии, что в строке 10 не выполняется оператор ге1пгп. Случай выполнения строки 10 мы рассмотрим при обсуждении завершения цикла. Каждая итерация цикла вЬПе меняет ролями некоторую базисную и небазисную переменные. При этом выполняются только операции решения уравнений и подстановки одного уравнения в другое, следовательно, новая каноническая форма эквивалентна канонической форме предыдущей итерации, которая, согласно инварианту цикла, эквивалентна исходной канонической форме. Теперь покажем, что сохраняется вторая часть инварианта цикла.
Предположим, что в начале каждой итерации цикла и 11Пе Ь; > О для всех г Е В, и покажем, что эти неравенства остаются верными после вызова процедуры Р11гот в строке 11. Поскольку изменения в переменные Ь; и множество В вносятся только в этой строке, достаточно показать, что она сохраняет данную часть инварианта. Пусть Ьо а; и В обозначают значения перед вызовом процедуры Р1чот, а Ь; — значения, возвращаемые процедурой Р11гот. Во-первых, заметим, что Ь, > О, поскольку Ь; > 0 согласно инварианту цикла, а1, > 0 согласно строке 5 процедуры 91мееех, а Ь, = Ь!/а1, согласно строке 2 процедуры Р1чОТ.
902 Часть Ч11. Избранные темы Для остальных индексов г е  — Щ мы имеем Ь, = Ь; — ав6, = (согласно строке 8 процедуры Р~чот) = Ь; — ам (6|/ом) (согласно строке 2 процедуры Р~чот) . Нам необходимо рассмотреть два случая: а;, > 0 и ам < О. Если а,, > О, то поскольку 1 выбирается так, что (29.80) Ь|/ам < Ь;/ам для всех 1Е В, получаем Ьв = Ь| — Оае (Ь!/ам) ~ ЭЬз — ам (Ьь/сйм) = Ьв — Ьз = О, где первое равенство следует из уравнения (29.79), а неравенство — из неравенства (29.80). Таким образом, Ь; > О. Если же ам < О, то поскольку все ам, 6; и 6| неотрицательны, из уравнения (29.79) следует, что Ь; также должно быть неотрицательным. Теперь докажем, что это базисное решение является допустимым, т.е.
что все переменные имеют неотрицательные значения. Небазисные переменные устанавливаются равными 0 и, следовательно, являются неотрицательными. Каждая базисная переменная задается уравнением х,=Ь; — ,'~ а; х. уем В базисном решении х; = Ьь Используя вторую часть инварианта цикла, можно сделать вывод, что все базисные переменные х; неотрицательны. Завершение. Цикл жййе может завершиться одним из двух способов. Если его завершение связано с выполнением условия в строке 2, то текущее базисное решение является допустимым и это решение возвращается строкой 16.
Второй способ завершения связан с возвращением сообщения "неограниченна" строкой 10. В этом случае в каждой итерации цикла аког (строки 4-7) при выполнении строки 5 оказывается, что ам < О. Пусть х — базисное решение, связанное с канонической формой в начале итерации, на которой возвращается сообщение "неограниченна". Рассмотрим решение х, определяемое как если г = е, если г Е Ф вЂ” (е), если г е В. 6; — ~ уе~табхз Покажем, что данное решение является допустимым, т.е. все переменные являются неотрицательными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
