Алгоритмы - построение и анализ (1021735), страница 188
Текст из файла (страница 188)
В строках 1 — 3 неявно проверяется базисное решение исходной канонической формы задачи Т, в которой?у = 11, 2,..., п) В = 1п + 1, и + 2,..., и + гп), х! = Ь; для всех 1 Е В и х = 0 для всех 7' Е Ю. (Создание данной канонической формы не требует дополнительных усилий, поскольку значения А, Ь и с в стандартной и канонической формах одинаковы.) Если это базисное решение допустимо, те. х! > 0 для всех ! е !ч 0 В, то возвращается данная каноническая форма. В противном случае в строке 4 формируется вспомогательная задача линейного программирования Т„„, так, как это описано в лемме 29.11. В строке 5 мы также присваиваем ! индекс наибольшего по модулю отрицательного значения Ь;, но переиндексация выполняется после преобразования к каноническому виду.
Поскольку начальное базисное решение задачи Т, недопустимо, начальное базисное решение канонической формы Т„также не будет допустимым. Поэтому в строке 7 выполняется вызов процедуры Р!чу, в котором вводимой переменной является хо, а выводимой хь Немного позже мы покажем, что базисное решение, полученное в результате этого вызова процедуры Р!чот, будет допустимым. Имея каноническую форму, базисное решение которой является допустимым, мы можем (строка 9) повторно вызывать процедуру Р!чот до тех пор, пока не будет найдено окон- Глава 29. Линейное программирование 917 Максимизировать при условиях (29. 112) — хо 2х) — хг — хо ( 2 х) — 5хз — хо < — 4 х),хз,хо ~ э0 (29.113) (29.114) Согласно лемме 29.11, если оптимальное целевое значение этой вспомогательной задачи равно О, то исходная задача имеет допустимое решение.
Если же оптимальное целевое значение вспомогательной задачи отрицательно, то исходная задача не имеет допустимых решений. Запишем вспомогательную задачу в канонической форме: — хо хз = 2 — 2х)+ хз+хо хя = — 4 — х) + бхз+ хо Пока что базисное решение, в котором хя = — 4, не является допустимым решением данной вспомогательной задачи. Однако с помощью единственного вызова процедуры Р)чот мы можем превратить эту каноническую форму в такую, базисное решение которой будет допустимым. Согласно строке 7, мы выбираем в качестве вводимой переменной хо. Согласно строке 1, в качестве выводимой переменной выбирается х4, базисная переменная, которая в базисном решении имеет наибольшее по абсолютной величине отрицательное значение.
После заме- чательное решение вспомогательной задачи линейного программирования. Если проверка в строке 10 показывает, что найдено оптимальное решение задачи Т„„ с равным 0 целевым значением, тогда в строке 11 для задачи Ь создается каноническая форма, базисное решение которой является допустимым. Для этого из ограничений удаляются все члены с хо и восстанавливается исходная целевая функция задачи .5. Исходная целевая функция может содержать как базисные, так и небазисные переменные.
Поэтому все вхождения базисных переменных в целевой функции нужно заменить правыми частями соответствующих ограничений. Если же в строке 10 обнаруживается, что исходная задача линейного программирования неразрешима, то сообщение об этом возвращается в строке 12. Теперь покажем, как работает процедура 1)ч)т)Аихн Б)мгьнх на примере задачи линейного программирования (29.105Н29.108). Эта задача будет разрешимой, если нам удастся найти неотрицательные значения х) и хз, удовлетворяющие неравенствам (29.106) и (29.107). Используя лемму 29.11, сформулируем вспомогательную задачу: Часть ЧП. Избранные темы 918 щения получаем следующую каноническую форму: з = — 4 — х1+ 5хз — х4 хо = 4+ х1 — 5хз + х4 хз = 6 — х1 — 4хз + х4 Связанное с ней базисное решение (хо,хыхз,хз,х4) = (4,0,0,6,0) является допустимым.
Теперь повторно вызываем процедуру Р1чот до тех пор, пока не получим оптимальное решение задачи Е,„. В данном случае после одного вызова Р1чОт с вводимой переменной хз и выводимой переменной хо получаем: ХО Х1 Х4 — — + — +— 5 5 5 4хо 9х1 х4 + — — — +— 5 5 5 Зта каноническая форма является окончательным решением вспомогательной задачи.
Поскольку в данном решении хо = О, можно сделать вывод, что исходная задача разрешима. Более того, поскольку хо = О, ее можно просто удалить из множества ограничений. Затем можно использовать исходную целевую функцию, в которой сделаны соответствующие подстановки, чтобы она содержала только небазисные переменные. В нашем примере целевая функция имеет вид /4 хо х1 х41 2х1 — хз = 2х1 — ~ — — — + — + — ( 15 5 5 51 После подстановки хо = 0 и соответствующих упрощений получаем целевую функцию, записанную как 4 9х1 х4 + 5 5 5' и каноническую форму: 4 9х1 х4 + хг = хз = + 5 5 Зта каноническая форма имеет допустимое базисное решение, и ее можно возвратить процедуре 51ми.нх. Докажем формально корректность процедуры 1н1т1Аыги 91мгьнх.
4 хз = 5 14 хз =— 5 5 5 14 5 5 5 х1 х4 + — +— 5 5 9х1 х4 Глава 29. Линейное программирование 919 Лемма 29.12. Если задача линейного программирования Б не имеет допустимых решений, то процедура !мт1лш2и Я!мгьвх возвращает сообщение "неразрешима". В противном случае процедура возвращает корректную каноническую форму базисное решение которой является допустимым. Доказательство.
Сначала предположим, что задача линейного программирования Т не имеет допустимых решений. Тогда, согласно лемме 29,11, оптимальное целевое значение задачи Б„„„, заданной формулами (29.109Н29.111), является ненулевым, а поскольку яо подчиняется ограничению неотрицательности, опти. мальное решение должно иметь отрицательное целевое значение. Более того, это целевое значение должно быть конечным, так как решение, в котором х, = 0 для г = 1, 2,..., п и хо = )ш)п™ з 1Ь,Ц, является допустимым и имеет целевое значение — )ш)п™ з (Ь,Ц.
Следовательно, в строке 9 процедуры 1мт!яигв Б1ми.лх будет найдено решение с отрицательным целевым значением. Пусть Гл — базисное решение, связанное с окончательной канонической формой. Мы не можем получить хо = О, поскольку тогда задача Б „„имела бы целевое значение О, а это противоречит факту, что целевое значение отрицательно. Таким образом, проверка в строке 10 приведет к тому, что в строке !2 будет возвращено сообщение "неразрешима".
Теперь предположим, что задача линейного программирования Т, имеет допустимое решение. Из упражнения 29.3-3 мы знаем, что если Ь, > 0 для ! = = 1, 2,..., т, то базисное решение, связанное с начальной канонической формой, является допустимым. В этом случае в строках 2-3 будет возвращена каноническая форма, связанная с исходной задачей.
(Для преобразования стандартной формы в каноническую не требуется много усилий, поскольку А, Ь и с одинаковы и в той, и в другой форме.) Для завершения доказательства рассмотрим случай, когда задача разрешима, но в строке 3 каноническая форма не возвращается. Докажем, что в этом случае в строках 4 — 9 выполняется поиск допустимого решения задачи Б„„„с целевым значением, равным О.
Согласно строкам 1-2, в данном случае Ь <О, Ь| < Ь; для всех ! б В. (29.115) В строке 7 выполняется одна операция замещения, в процессе которой из базиса выводится переменная х~ (вспомним, что ! = п + lс), стоящая в левой части уравнения с минимальным Ьо и вводится дополнительная переменная хо. Покажем, что после такого замещения все элементы Ь являются неотрицательными, и, следовательно, данное базисное решение задачи Т „я является допустимым. Часть ЧП.
Избранные темы 920 Обозначим через х базисное решение после вызова процедуры Р~чот, и пусть Ь и  — значения, возвращенные процедурой Р~чот. Из леммы 29.1 следует, что Ь, — а;,Ь, если 1 е  — 1е), х;= з Ь~/а~е если 1 = е. (29.116) При вызове процедуры Рвот в строке 7 е = 0 и, в соответствии с (29.110), аю = аге = -1 дла всех (Е В. (29.117) (Заметим, что а;о — это коэффициент при хо в выражении (29.110), а не проти- воположное ему значение, поскольку задача Т „„находится в стандартной, а не канонической форме.) Поскольку 1 е В, то аге = — 1. Таким образом, Ь~/аге > 0 и, следовательно, х, > О.
Для остальных базисных переменных получаем: х;=Ь,— аеЬе= (согласно (29.! 16)) (в соответствии со строкой 2 процедуры Рвот) (из (29.117) и аге = — 1) (из неравенства (29.115)) . = Ь; — аде (Ь|/а~е) = =Ь,— Ь,> >О Основная теорема линейного программирования Мы завершим данную главу демонстрацией корректности работы процедуры 81мРьех. Произвольная задача линейного программирования или неразрешима, или неограниченна, или имеет оптимальное решение с конечным целевым значением, и в каждом случае процедура Б1МР1.ЕХ будет работать правильно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
