Алгоритмы - построение и анализ (1021735), страница 184
Текст из файла (страница 184)
Если а[, = О, вызов процедуры Рвот приведет к ошибке (деление на 0), однако, как будет показано в ходе доказательства лемм 29.2 и 29.12, данная процедура вызывается толью тогда, когда а[, ф О. Рассмотрим, как процедура Р[чот действует на значения переменных базисного решения.
Лемма 29.1. Рассмотрим вызов процедуры Рвот(/Ч,В,А, Ь,с, [[,1,е) при ам ф ф О. Пусть в результате вызова возвращаются значения (1Ч, В, А, 6, с, [[), и пусть х обозначает базисное решение после выполнения вызова. Тогда 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) следует, что Ь; также должно быть неотрицательным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
