Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 202
Текст из файла (страница 202)
Предположим, что в начале каждой итерации цикла тепйе для всех с е В выполняется соотношение 6, > О, и покажем, что эти неравенства остаются верными после вызова процедуры Рсчот в строке 12. Поскольку изменения в переменные Ь, и множество В вносятся только в этой строке, достаточно показать, что она сохраняет данную часть инварианта. Пусть Ьс, ас н В обозначают значения перед вызовом процедуры Рсчот, а Ь, — значения, возвращаемые процедурой Р! чот. Во-первых, заметим, что Ь, > О, поскольку Ьс > О согласно инварианту цикла, ас, > О согласно строкам 6 и 9 процедуры эсмгьнх, а Ь, = Ьс/ас, согласно строке 3 процедуры Рсчот.
Для остальных индексов с е  — Я имеем 9!5 Глана гя Пинейное ноограиннроеание Теперь докажем, что это базисное решение является допустимым, т.е. что все переменные имеют неотрицательные значения. Небазисные переменные устанавливаются равными нулю и, следовательно, являются неотрицательными. Каждая базисная переменная х; задается уравнением х;=6; — ~~~ а,х ген В базисном решении х, = Ьь Используя вторую часть инварианта цикла, мож- но сделать вывод, что все базисные переменные х, неотрицательны. Завершение. Цикл невйе может завершиться одним из двух способов. Если его завершение связано с выполнением условия в строке 3, то текущее базисное решение является допустимым и это решение возвращается строкой 17.
Второй способ завершения связан с возвращением сообщения "задача неограниченная" строкой 11. В этом случае в каждой итерации цикла Гвг (строки 5-8) при выполнении строки б оказывается, что ем < О. Рассмотрим решение х, определяемое следующим образом: 00, если)= е, О, если 1 Е М вЂ” 1е), 6; — т,т абхг, если 1 б В . Покажем, что данное решение является допустимым, т.е. что все переменные являются неотрицательными. Небазисные переменные, отличные от х„равны нулю, а значение х, = 00 > О, следовательно, все небазисные переменные неотрицательны. Для каждой базисной переменной х, имеем х; = Ь; — ~~~ а„ху уегг = Ь, — ае,хе Из инварианта цикла вытекает, что Ь, > О, и мы имеем гце < О и х, = 00 > О. Таким образом, х, > О.
Теперь покажем, что целевое значение этого решения х является неограниченным. Из уравнения (29.42) целевое значение равно г = о+ ~сзху зев — о + сехе Поскольку с, > О (согласно строке 4 процедуры 81МРЫХ) и х, = 00, целевое значение бесконечно, а значит, задача линейного программирования неограниченная.
9!б Часть РИ. Избранные тены Остается показать, что процедура 81МИ.ВХ завершается и что после ее завершения возвращаемое решение является оптимальным. Оптимальность будет рассмотрена в разделе 29.4. Сейчас же мы рассмотрим завершение процедуры. Завершение В приведенном в начале данного раздела примере каждая итерация симплекс-алгорнтма увеличивала целевое значение, связанное с базисным решением. В упр.
29.3.2 предлагается показать, что ни одна итерация процедуры 81мвьвх не может уменьшить целевое значение, связанное с базисным решением. К сожалению, может оказаться, что итерация оставляет целевое значение неизменным. Это явление называется выраждеиноетвю, и сейчас мы рассмотрим его более подробно. Целевое значение изменяется в строке 14 процедуры Р1чот в результате присваивания В = с+с,Ь,. Поскольку вызов процедуры Р[ЧОт в процедуре 81МИ.ВХ происходит только при с, > О, целевое значение может остаться неизменным (т.е. В = с) только в том случае, когда Ь, будет равно нулю. Это значение вычисляется как Ь, = Ь~/ам в строке 3 процедуры Р1чот. Поскольку процедура Р[чот вызывается только при ам ,-б О, для того, чтобы Ь, было равно нулю н, как следствие, целевое значение осталось неизменным, должно выполняться условие Ь| = О.
Такая ситуация действительно может возникнуть. Рассмотрим следуквцую задачу линейного программирования: Э = Х1 + Х2 + Хэ х4 = 8 — хг — хэ хг — хз. Предположим, что в качестве вводимой переменной выбрана переменная хп а в качестве выводимой — х4. После замещения получим следующую задачу: 2=8 +хз — х4 хз=8 — хг — х4 Х5 = Х2 — ХЗ .
В этой ситуации единственная возможность замещения — когда вводимой переменной является хэ, а выводимой переменной — хб. Поскольку Ьз = О, после замещения целевое значение 8 останется неизменным: г = 8 + хэ — х4 — хз Х1 = 8 — Хэ — Х4 ХЗ = Х2 — Х5 Целевое значение осталось неизменным, но представление задачи изменилось. К счастью, если мы продолжим замещение, выбрав в качестве вводимой переменной хэ, а в качестве выводимой — хм целевое значение увеличится (до 16) и симплекс-алгоритм сможет продолжить свою работу. Глава 29. Линейное врограммирование 977 Вырожленность является единственным возможным препятствием для окончания симплекс-алгоритма, так как может привести к явлению, именуемому зацикливанием, когда канонические формы на двух разных итерациях одинаковы.
Из-за вырожденности процедура б~мрьвх может выбирать последовательность замещающих операций, которые оставляют целевое значение неизменным, но при этом повторяют последовательность из одних и тех же канонических форм. Поскольку алгоритм Б~мрых детерминированный, в случае зацикливания он бесконечно проходит по одной и той же последовательности канонических форм, никогда не заканчивая свою работу. Зацикливание — единственная причина, по которой процедура Б!МРеех может не завершить свою работу.
Чтобы показать это, сначала разработаем некоторую дополнительную технику. На каждой итерации процедура 81МРЬВХ в дополнение к множествам Х и В поддерживает А, 6, с и е. Хотя для эффективной реализации симплекс-алгоритма требуется явная поддержка А, 6, с и о, можно обойтись и без нее. Другими словами, множества базисных и небазисных переменных достаточно для того, чтобы единственным образом определить каноническую форму.
Перед тем как доказать этот факт, докажем одну полезную алгебраическую лемму. Лемма 29З Пусть 1 представляет собой множество индексов и пусть для каждого 7 Е 1 а и )7 — действительные числа, ах — действительная переменная. Пусть также 7— некоторое действительное число. Предположим, что для любых х выполняется следующее условие: (29.78) 7Е7 Тогда о = ДЗ для каждого 7 Е 1, и 7 = О. Доказашельслюво.
Поскольку уравнение (29.78) выполняется для любых значений х, можно выбрать для них определенные значения, чтобы сделать заключения об о, ~3 и у. Выбрав х = О для всех 7' Е 1, можно сделать вывод, что 7 = О. Теперь выберем произвольный индекс 7' Е 1 и зададим ху — — 1 и хь = О для всех к ~ 7. В таком случае должно выполняться равенство а = ~3 . Поскольку индекс 7 выбирался из множества 1 произвольным образом, можно заключить, что ае = )31 для всех 7' ~ 1. Конкретная задача линейного программирования может иметь много различных канонических форм; вспомним, что любая каноническая форма имеет то же самое множество допустимых и оптимальных решений, что и исходная задача.
Теперь покажем, что каноническая форма любой задачи линейного программирования уникальным образом определяется множеством базисных переменных, т.е, что с заданным набором базисных переменных связана единственная каноническая форма (с однозначно определяемым множеством коэффициентов в правой части). Часть 9?Ь Иэбранные тены 9?а Лемма 29.4 Пусть (А, 6, с) представляет собой задачу линейного программирования в стан- дартной форме.
Задание множества базисных переменных В однозначно опреде- ляет соответствующую каноническую форму. 2=С+~~ СХ ?еи х;=6; — ~~~ а;х дляеЕВ ?ЕУ (29.?9) (29.80) а вторую как 2=С + Схэ э эеФ х,=Ь; — ~~~ а, х? длягеВ зем (29.81) (29.82) Рассмотрим систему уравнений, образованную путем вычитания каждого уравнения строки (29.82) из соответствующего уравнения строки (29.80). Полученная система имеет вид 0 = (6; — 6~) — Я(а, — а~ )х.
для ! Е В тек или, что эквивалентно, абхэ=(6,— Ь;)+ ) а,"х дла!бВ. эеМ ?ем Теперь для всех ( е В применим лемму 29,3, где а = аб, Д = а';, т = 6; — 6;' и 1 = Ю. Поскольку сн, = !3;э имеем а; = а,' для всех ! б М, а поскольку у = О, то Ь; = 6',. Таким образом, в этих двух канонических формах матрицы А и А' и векторы 6 и Ь' идентичны.
С помощью аналогичных рассуждений в упр. 29.3.1 показано, что в этом случае также справедливо с = с' и с = и', следовательно, рассматриваемые канонические формы должны быть идентичны. Теперь можно показать, что зацикливание — единственная возможная причина, по которой процедура 8!мр!.нх может не завершиться. Доказательство. Будем проводить доказательство от противного. Предположим, что существуют две различные канонические формы с одинаковым множеством базисных переменных В. Эти канонические формы должны также иметь одинаковые множества небазисных переменных )н' = !1,2,..., и+ т) — В. Запишем первую каноническую форму как Глава 29.
Линейное нрвгриммирование 919 Лемма 29.5 Если процедура Б!М9ЬЕХ не завершается не более чем за ("+™) итераций, она зацикливается. Доказаллельство. Согласно лемме 29.4 множество базисных переменных В однозначно определяет каноническую форму. Всего имеется и + т переменных, а ~В~ = т, так что существует не более чем ("+~) способов выбрать В. Следовательно, всего имеется не более чем ("+ ) различных канонических форм.
Поэтому, если процедура Б|М9ЬНХ совершает более чем ("+ ) итераций, она должна зациклиться. Зацикливание теоретически возможно, но встречается чрезвычайно редко. Его можно избежать путем несколько более аккуратного выбора вводимых и выводимых переменных. Один из способов состоит в подаче на вход слабого возмущения, что приводит к невозможности получить два решения с одинаковым целевым значением. Второй способ заключается в том, чтобы всегда выбирать переменную с наименьшим индексом. Эта стратегия известна как правило Бленда 1В1апй'з гп1е). Мы не будем приводить доказательства, что эти стратегии позволяют избежать зацикливания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
