Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 185
Текст из файла (страница 185)
Небазисные переменные, отличные от х„равны Глава 29. Линейное программирование 903 О, а значение х, положительно, следовательно, все небазисные переменные неотрицательны. Все базисные переменные вычисляются по формуле х; = Ь; — ~) а; ху — — Ь, — а;,х,.
уелг В соответствии с инвариантом цикла Ь; > О, кроме того, агь ( О и х, = = оо > О; следовательно, х; > О. Теперь покажем, что целевое значение этого решения х является неограниченным. Целевое значение равно е — о + Х~) суху — ю + свхв уелг Поскольку с, > О (согласно строке 3) и х, = оо, целевое значение бесконечно, следовательно, задача линейного программирования неограниченна ° На каждой итерации процедура 81МР1.ЕХ, помимо множеств ду и В, поддерживает А, Ь, с и о.
Хотя сохранение в явном виде значений А, Ь, с и и существенно для эффективной реализации симплкекс-алгоритма, оно не является необходимым. Иными словами, каноническая форма уникальным образом определяется множествами базисных и небазисных переменных. Прежде чем доказывать это утверждение, докажем полезную алгебраическую лемму. Лемма 29.3. Пусть 1 — множество индексов. Пусть для каждого гЕ1 сн и Д вЂ” действительные числа, а х, — действительная переменная. Пусть также у — некоторое действительное число. Предположим, что для любых х, выполняется следующее условие: ,'> азх; = у+ ~> Дхз .
(29.81) ег зеу Тогда а; = Д для всех г Е1, а у = О. Доказаюельсюиво. Поскольку уравнение (29.81) выполняется для любых значений ха можно выбрать для них определенные значения, чтобы сделать заключения об а, )3 и у. Выбрав х; = О для всех г Е 1, можно сделать вывод, что у = О. Теперь выберем произвольный индекс 1 Е 1 и зададим х, = 1 и хь = О для всех й ~ ф г'. В таком случае должно выполняться равенство он = Д. Поскольку индекс г выбирался из множества 1 произвольным образом, можно заключить, что сн = Д для всех 1 Е 1. Теперь покажем, что каноническая форма любой задачи линейного программирования уникальным образом определяется множеством базисных переменных.
Часть Ч11. Избранные темы Лемма 29.4. Пусть (А,Ь, с) — задача линейного программирования в стандарт- ной форме. Задание множества базисных переменных В однозначно определяет соответствующую каноническую форму. Доказаиюельсиюво. Будем проводить доказательство от противного. Предположим, что существуют две канонические формы с одинаковым множеством базисных переменных В. Эти канонические формы должны также иметь одинаковые множества небазисных переменных М = 11,2,..., п+ т) — В.
Запишем первую каноническую форму как г=ц+ ~> сх, уеи х, = 6; — ~~> ауху для 4 Е В, зев (29.82) (29.83) а вторую — как з = и'+ ~> с'х, уеФ х; = Ь; — ~ а,' ху для 4 Е В. зебр (29.84) (29.85) О = (Ь вЂ” Ь',) — ~~~ (аΠ— а; ') х для з Е В, уем или, что эквивалентно, ~> аух„= (6; — Ь',) + ~) а', х для (Е В. уеФ уеФ Теперь для всех ю' е В применим лемму 29.3, где си = ачь Д = а'; и 3 = 6; — Ь',. Поскольку оч = Д, то а; = а'," для всех з Е М, и поскольку .у = О, то Ь; = Ь';.
Таким образом, в этих двух канонических формах матрицы А и А' и векторы Ь и 6' идентичны. С помощью аналогичных рассуждений в упражнении 29.3-1 показывается, что в этом случае также с = с' и ц = ц', следовательно, рассматриваемые канонические формы идентичны. И Осталось показать, что процедура Б~мгьнх заканчивается и, когда она завершается, возвращаемое решение является оптимальным. Вопрос оптимальности рассматривается в разделе 29.4.
Обсудим завершение процедуры. Рассмотрим систему уравнений, образованную путем вычитания каждого уравнения строки (29.85) из соответствующего уравнения строки (29.83). Полученная система имеет вид Глава 29. Линейное программирование 905 Завершение хг+хг+ха Х4 = 8 — хг — хг х5 = Предположим, что в качестве вводимой переменной выбрана переменная хм а в качестве выводимой х4.
После замещения получим следующую задачу: а=8 х1 = 8 — хг + ХЗ вЂ” Х4 Х4 х5 = хг — хз В данном случае единственная возможность замещения — когда вводимой пе- ременной является хз, а выводимой переменной х5. Поскольку Ь5 = О, после замещения целевое значение 8 останется неизменным: 3 = 8+ хг — х4 — хз х1 = 8 — хг — Х4 ха= хг х5 Целевое значение осталось неизменным, но представление задачи изменилось.
К счастью, если мы продолжим замещение, выбрав в качестве вводимой пере- менной хг, а в качестве выводимой хг, целевое значение увеличится и симплекс- алгоритм может продолжить свою работу. В приведенном в начале данного раздела примере каждая итерация симплекс-алгоритма увеличивала целевое значение, связанное с базисным решением. В упражнении 29.3-2 предлагается показать, что ни одна итерация процедуры 81мгеех не может уменьшить целевое значение, связанное с базисным решением. К сожалению, может оказаться, что итерация оставляет целевое значение неизменным. Это явление называется вырожденнюстью (бейепегасу), и мы сейчас рассмотрим его более подробно. Целевое значение изменяется в строке ! 3 процедуры Р!ч0т в результате присваивания  — и+ с,Ь . Поскольку вызов процедуры Р~чот в процедуре Б~мрьех происходит только при с, ) О, целевое значение может остаться неизменным (т.е., б = о) только в том случае, когда Ь, будет равно О.
Это значение вычисляется как Ь, — Ь~/4Ч, В СтроКе 2 процедуры Рьмот. Поскольку процедура Р~чот вызывается только при ам 54 О, то для того, чтобы Ь, было равно О и, как следствие, целевое значение осталось неизменным, должно выполняться условие Ь~ = О. Такая ситуация действительно может возникнуть. Рассмотрим следующую задачу линейного программирования: Часть Ч1!. Избранные темы 906 Покажем, что вырожденность является единственным возможным препятствием для окончания симплекс-алгоритма.
Вспомним о наших предположениях, что процедура 8!ми.ех выбирает индексы е и ! (в строках 3 и 8 соответственно) согласно неюму детерминистическому правилу. Мы говорим, что процедура 81мРЬЕХ заииклилась, если канонические формы на двух различных итерациях идентичны; в этом случае, поскольку данная процедура является детерминистическим алгоритмом, она бесконечно будет перебирать одну и ту же последовательность канонических форм. Лемма 29.5.
Если процедура 81МР1.ех не может завершиться более чем за ("+ ) итераций, она зацикливается. Доказатнельсюнво. Согласно лемме 29.4, множество базисных переменных В однозначным образом определяет каноническую форму. Всего имеется и + т переменных, а !В~ = тл, так что существует ("+ ) способов выбрать В. Следовательно, всего имеется ("~~ ) различных канонических форм. Поэтому, если процедура 81М~.ЕХ совершает более чем ("~ ~) итераций, она должна зациклиться.
Зацикливание теоретически возможно, но встречается чрезвычайно редю. Его можно избежать путем несколько более аккуратного выбора вводимых и выводимых переменных. Один из способов состоит в подаче на вход слабого возмущения, что приводит к невозможности получить два решения с одинаковым целевым значением. Второй способ состоит в лексикографичесюм разрыве связей, а третий— в разрыве связей путем выбора переменной с наименьшим индексом. Последняя стратегия известна как аревало Бленда (В!аль'з гп!е). Мы не будем приводить доказательств, что эти стратегии позволяют избежать зацикливания.
Лемма 29.6. Если в строках 3 и 8 процедуры 81МРьЕХ выполняется выбор переменной с наименьшим индексом, процедура 81мРьех должна завершиться. ° Данный раздел мы закончим следующей леммой. Лемма 29.7. Если процедура 1ы1т1ль1ге 81МРьех возвращает каноническую форму, базисное решение юторой является допустимым, то процедура 81МРЬЕХ или выдает сообщение о неограниченности решения задачи линейного программирования, или завершается, предоставляя допустимое решение, не более чем за ("~™) итераций.
Доказательство. В леммах 29.2 и 29.6 показано, что если процедура 1ы1т1А1.- 1Ее 81мРьех возвращает каноническую форму, базисное решение которой является допустимым, то процедура 81мРьех или выдает сообщение о неограниченности решения задачи линейного программирования, или завершается, предоставляя допустимое решение. Используя лемму 29.5, методом от противного приходим Глава 29.
Линейное программирование 907 к заключению, что если процедура 81мрьнх завершается предоставлением допу- стимого решения, то зто происходит не более чем за ("+~) итераций. Упражнения 29.3-1. Завершите доказательство леммы 29А, показав, что с = с' и о = »>. 29.3-2. Покажите, что значение и никогда не уменьшается в результате вызова процедуры Р1чот в строке 11 процелуры 81ми.нх. 29.3-3. Предположим, что мы преобразовали задачу линейного программирования (А, Ь, с) из стандартной формы в каноническую. Покажите, что базисное решение является допустимым тогда и толью тогда, югда Ь; ) 0 для г = 1,2,..., т. 29.3-4.
Решите следуюшую задачу линейного программирования, используя процедуру ймрьнх: Максимизировать 18х1 + 12.5хз при условиях х1 + хг < 20 < 12 хз < 16 хм ха ) 0 29.3-5. Решите следующую задачу линейного программирования, используя процедуру 81ми.нх: Максимизировать — 5х| — Зхз при условиях хз — хз < 1 2хг + хз < 2 хыхз ) 0 29.3-б. Решите следующую задачу линейного программирования, используя процедуру Б~мрых: Минимизировать х1 + хз + хз при условиях 2х1+ 7.5хз+ Зхз ~ 10000 20х1 + бхз + 10хз ~ 30000 х1> хз>хз ~1 Часть ЧП.
Избранные темы 29.4 Двойственность (29.86) Минимизировать при условиях а,уу; > с) для ) = 1, 2,..., и, Е (29.87) у; ) О для(=1,2,...,гп. (29.88) Чтобы получить двойственную задачу, мы изменили максимизацию на минимизацию, поменяли роли коэффициентов правых частей и целевой функции и заменили неравенства "меньше или равно" на "больше или равно". С каждым из гп ограничений прямой задачи в двойственной задаче связана переменная уь а с каждым из п ограничений двойственной задачи связана переменная прямой задачи к . Например, рассмотрим задачу линейного программирования, задан- Мы доказали, что при определенных предположениях процедура Я!мРг.ех завершается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
