Алгоритмы - построение и анализ (1021735), страница 185
Текст из файла (страница 185)
Теперь докажем, что это базисное решение является допустимым, т.е. что все переменные имеют неотрицательные значения. Небазисные переменные устанавливаются равными 0 и, следовательно, являются неотрицательными. Каждая базисная переменная задается уравнением х,=Ь; — ,'~ а; х. уем В базисном решении х; = Ьь Используя вторую часть инварианта цикла, можно сделать вывод, что все базисные переменные х; неотрицательны. Завершение. Цикл жййе может завершиться одним из двух способов. Если его завершение связано с выполнением условия в строке 2, то текущее базисное решение является допустимым и это решение возвращается строкой 16. Второй способ завершения связан с возвращением сообщения "неограниченна" строкой 10. В этом случае в каждой итерации цикла аког (строки 4-7) при выполнении строки 5 оказывается, что ам < О.
Пусть х — базисное решение, связанное с канонической формой в начале итерации, на которой возвращается сообщение "неограниченна". Рассмотрим решение х, определяемое как если г = е, если г Е Ф вЂ” (е), если г е В. 6; — ~ уе~табхз Покажем, что данное решение является допустимым, т.е. все переменные являются неотрицательными. Небазисные переменные, отличные от х„равны Глава 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 Завершение х1 + хг + хз Х4 = 8 — Х1 — Х2 х5 = Предположим, что в качестве вводимой переменной выбрана переменная х1, а в качестве выводимой х4.
После замещения получим следующую задачу: 2=8 х1 = 8 — хг + ХЗ вЂ” Х4 Х4 Х5 = Х2 — ХЗ В данном случае единственная возможность замещения — когда вводимой пе- ременной является хз, а выводимой переменной х5. Поскольку Ь5 = О, после замещения целевое значение 8 останется неизменным: 2 = 8+ Хг — Х4 — Х5 х1 = 8 — хг — Х4 ХЗ= Х2 х5 Целевое значение осталось неизменным, но представление задачи изменилось.
К счастью, если мы продолжим замещение, выбрав в качестве вводимой пере- менной хг, а в качестве выводимой х1, целевое значение увеличится и симплекс- алгоритм может продолжить свою работу. В приведенном в начале данного раздела примере каждая итерация симплекс-алгоритма увеличивала целевое значение, связанное с базисным решением. В упражнении 29.3-2 предлагается показать, что ни одна итерация процедуры 81мгеех не может уменьшить целевое значение, связанное с базисным решением. К сожалению, может оказаться, что итерация оставляет целевое значение неизменным.
Это явление называется вырожденнюстью (бейепегасу), и мы сейчас рассмотрим его более подробно. Целевое значение изменяется в строке 13 процедуры Р1ч0т в результате присваивания  — и+ с,Ь . Поскольку вызов процедуры Р111От в процедуре 81ырьЕХ происходит только при с, ) О, целевое значение может остаться неизменным (т.е., б = о) только в том случае, когда Ь, будет равно О. Это значение вычисляется как Ь, — Ь1/а1, в строке 2 процедуры Р1уот.
Поскольку процедура Р1чот вызывается только при а1, 54 О, то для того, чтобы Ь, было равно О и, как следствие, целевое значение осталось неизменным, должно выполняться условие Ь1 = О. Такая ситуация действительно может возникнуть. Рассмотрим следующую задачу линейного программирования: Часть Ч1!. Избранные темы 906 Покажем, что вырожденность является единственным возможным препятствием для окончания симплекс-алгоритма. Вспомним о наших предположениях, что процедура 8!ми.ех выбирает индексы е и ! (в строках 3 и 8 соответственно) согласно неюму детерминистическому правилу. Мы говорим, что процедура 81мРЬЕХ заииклилась, если канонические формы на двух различных итерациях идентичны; в этом случае, поскольку данная процедура является детерминистическим алгоритмом, она бесконечно будет перебирать одну и ту же последовательность канонических форм.
Лемма 29.5. Если процедура 81МР1.ех не может завершиться более чем за ("+ ) итераций, она зацикливается. Доказатнельсюнво. Согласно лемме 29.4, множество базисных переменных В однозначным образом определяет каноническую форму. Всего имеется и + т переменных, а !В~ = тл, так что существует ("+ ) способов выбрать В.
Следовательно, всего имеется ("~~ ) различных канонических форм. Поэтому, если процедура 81М~.ЕХ совершает более чем ("~ ~) итераций, она должна зациклиться. Зацикливание теоретически возможно, но встречается чрезвычайно редю. Его можно избежать путем несколько более аккуратного выбора вводимых и выводимых переменных. Один из способов состоит в подаче на вход слабого возмущения, что приводит к невозможности получить два решения с одинаковым целевым значением. Второй способ состоит в лексикографичесюм разрыве связей, а третий— в разрыве связей путем выбора переменной с наименьшим индексом. Последняя стратегия известна как аревало Бленда (В!аль'з гп!е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
