Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 205
Текст из файла (страница 205)
В строках 1-3 неявно проверяется базисное решение исходной канонической формы задачи Е, задаваемой г"е' = (1, 2,..., и), В = (и+ 1, и+ 2,..., и + т), й; = 6; для всех г б Вид = О для всех 9 Е М. (Создание данной канонической формы не требует дополнительных усилий, поскольку значения А, Ь и с в стандартной и канонической формах одинаювы.) Если в строке 2 выясняется, что это базисное решение допустимо, т.е.
й, > 0 для всех 1 Е Г1г 0 В, то в строке 3 возвращается данная каноническая форма. В противном случае в строке 4 формируется вспомогательная задача линейного программирования Е „так, как описано в лемме 29.11. Поскольку начальное базисное решение задачи Е недопустимо, начальное базисное решение канонической формы /аии также не может быть допустимым. Чтобы найти базисное допустимое решение, мы выполняем единственную операцию замещения. В строке 6 в качестве индекса базисной переменной, которая будет выводимой в этой операции замещения, выбирается 1 = п + 19. Поскольку базисными переменными являются к„ем кнвз,..., х„в., выводимая переменная х~ является переменной с наиболее отрицательным значением.
В строке 8 выполняется соответствующий вызов процедуры Р1чот, в котором вводимой переменной является ко, а выводимой — хь Немного позже мы покажем, что базисное реше- вовек, мм 930 Часть РИ. Избранные теаы (29.! 09) максимизировать — хо при условиях 2х1 — хг — хо ( 2 (29.110) (29.111) х! — бхг Х1 Хг|ХО хо < — 4 ) О.
Согласно лемме 29.11, если оптимальное целевое значение этой вспомогательной задачи равно нулю, исходная задача имеет допустимое решение. Если же оптимальное целевое значение вспомогательной задачи отрицательно, то исходная задача не имеет допустимых решений. Запишем вспомогательную задачу в канонической форме: х= — хо хз = 2 — 2х! + хг + хо Х4 = -4 — х1 + 5хг + хо Пока что базисное решение, в котором х4 = — 4, не является допустимым решением данной вспомогательной задачи. Однако с помощью единственного вызова процедуры Р1чот эту каноническую форму можно превратить в такую, базисное решение которой будет допустимым. Согласно строке 8 мы выбираем в качестве ние, полученное в результате этого вызова процедуры Р1чот, будет допустимым.
Имея каноническую форму, базисное решение которой является допустимым, мы можем (строка 10) многократно вызывать процедуру Р1чот до тех пор, пока ие будет найдено окончательное решение вспомогательной задачи линейного программирования. Если проверка в строке 11 показывает, что найдено оптимальное решение задачи Г„„, с целевым значением, равным нулю, то в строках 12-14 для задачи Ь создается каноническая форма, базисное решение которой является допустимым.
Для этого сначала в строках 12-13 обрабатывается вырожденный случай, когда хо может оставаться базисной переменной со значением хо = О. В этом случае мы выполняем шаг замещения для удаления хо из базисных переменных, использУЯ длЯ вводимой пеРеменной любое е Е М, такое, что аое Эб О. Новое базисное решение остается допустимым; вырожденное замещение не изменяет значение ни одной из переменных.
Затем из ограничений удаляются все члены с хо и восстанавливается исходная целевая функция задачи Ь. Исходная целевая функция может содержать как базисные, так и небазисные переменные. Поэтому все вхождения базисных переменных в целевой функции заменяются правыми частями соответствующих ограничений. Затем в строке 15 возвращается эта модифицированная каноническая форма.
Если же в строке 11 обнаруживается, что исходная задача линейного программирования неразрешима, то сообщение об этом возвращается в строке 16. Теперь покажем, как работает процедура 1ы1т1яы2е-81мРьех, на примере задачи линейного программирования (29.102)-(29.105). Эта задача будет разрешимой, если удастся найти неотрицательные значения х1 и хг, удовлетворяющие неравенствам (29.103) и (29.104). Используя лемму 29.11, сформулируем вспомогательную задачу линейного программирования: 931 Глава ля Линейное нрограмиирование вводимой переменной хо. В строке 6 в качестве выводимой переменной выбира- ется х4 — базисная переменная, которая в базисном решении имеет наибольшее по абсолкпной величине отрицательное значение. После замещения получаем следующую каноническую форму: х = -4 — х1 + бхай — хй хо = 4 + х1 — 5хз + х4 хз = 6 — х1 — 4хз + х4 Связанное с ней базисное решение (хо, хм хз, хз, ххя) = (4, О, О, 6, О) является допустимым.
Теперь мы многократно вызываем процедуру Р1уот — до тех пор„пока не получим оптимальное решение задачи Ь,„,. В данном случае после одного вызова Р~уот с вводимой переменной хз и выводимой переменной хо получаем — хс 4 хо х1 х4 + + 5 5 9х1 х4 + 5 5 хг = 5 5 14 4хо + 5 5 г4 хо х1 х41 2х1 — хз = 2х1 — ~- — — + — + — ) ~5 5 5 5) Присвоив хс = О и упростив, получаем целевую функцию 4 9х| хй 5 5 5 и каноническую форму 4 9х1 х4 л + 5 5 5 4 х1 х4 хз = — + — +— 5 5 5 14 9х1 ха хз= — — — + —. 5 5 5 Эта каноническая форма имеет допустимое базисное решение, и ее можно возвратить процедуре 61мрьнх. Докажем формально корректность процедуры 1м1т1Ашге-61ми.ех. Эта каноническая форма является окончательным решением вспомогательной задачи. Поскольку в данном решении хо = О, можно сделать вывод, что исходная задача разрешима.
Более того, поскольку хо = О, эту переменную можно просто удалить из множества ограничений. Затем следует восстановить исходную целевую функцию, в которой сделаны соответствующие подстановки, чтобы она содержала только небазисные переменные. В нашем примере целевая функция приобретает вид 9зз Часть р!!. Избранные тены Лемма 29Л2 Если задача линейного программирования Ь не имеет допустимых решений, то процедура 1х!т!Ае!ее-Б!мреех возвращает сообщение "задача неразрешима". В противном случае процедура возвращает корректную каноническую форму, базисное решение которой является допустимым.
Двкаэашельсшво. Сначала предположим, что задача линейного программирования Ь не имеет допустимых решений. Тогда согласно лемме 29.11 оптимальное целевое значение задачи Х„, заданной формулами (29.106К29.108), является ненулевым, а поскольку хо подчиняется ограничению неотрицательности, оптимальное целевое значение должно иметь отрицательное целевое значение.
Кроме того, это целевое значение должно быть конечным, так как решение, в котором х; = 0 для 1 = 1,2,...,п и хо = )ш)п™ 1(6;)(, является допустимым и имеет целевое значение — (ш)п™, 16,)!. Следовательно, в строке 10 процедуры 1!ч!т!АЫЕе-8!мРеех будет найдено решение с неположительным целевым значением. Пусть х — базисное решение, связанное с окончательной канонической формой.
Мы не можем получить хо = О, поскольку тогда задача В, имела бы нулевое целевое значение, а это противоречит тому факту, что целевое значение отрицательно. Таким образом, проверка в строке 11 приведет к тому, что в строке 16 будет возвращено сообщение "задача неразрешима*'. Теперь предположим, что задача линейного программирования Ь имеет допустимое решение. Из упр. 29.3.4 мы знаем, что если 6, > 0 для з = 1, 2,..., пз, то базисное решение, связанное с начальной канонической формой, является допустимым. В этом случае в строках 2 и 3 будет возвращена каноническая форма, связанная с исходной задачей. (Для преобразования стандартной формы в каноническую не требуется много усилий, поскольку А, 6 и с одинаковы и в той, и в другой формах.) Для завершения доказательства рассмотрим случай, когда задача разрешима, но каноническая форма не возвращается в строке 3.
Докажем, что в этом случае в строках 4-10 выполняется поиск допустимого решения задачи Ь, с нулевым целевым значением. Согласно строкам 1 и 2 в данном случае и Ьь < 6, для каждого з е В. 129.112) В строке 8 выполняется одна операция замещения, в процессе которой из базиса выводится переменная х~ (вспомним, что 1 = и + )с, так что 6~ < 0), стоящая в левой части уравнения с минимальным 6ь и вводится дополнительная переменная хо. Покажем, что после такого замещения все элементы 6 являются неотрицательными и, следовательно, данное базисное решение задачи Ь„, является допустимым. Обозначим через х базисное решение после вызова процедуры Р!чот, и пусть 6 и В представляют собой значения, возвращенные процедурой Глава 29.
Линейное программирование 933 Рвот. Из леммы 29.1 следует, что Ь, — а„Ь,, если 1 Š — (е), Хг Ь|/ам, если 1 = е . (29.113) аобу < Ь, для(=1,2,...,тл, у=о (29.114) то имеем а,о = аее = — 1 для каждого 1 Е В (29.115) (Заметим, что аю — это коэффициент при хс в выражении (29.114), а не противоположное ему значение, поскольку задача В,„„находится в стандартной, а не канонической форме.) Поскольку 1 ~ В, мы также имеем ам = — 1.
Таким образом, Ь~/ам > 0 и, следовательно, х, > О. Для остальных базисных переменных получаем: й, = Ь; — аеЬе Ье оее(Ь1/гче) (согласио (29. 113)) (согласно строке 3 процедуры Р1чот) (согласно (29.115) и ам = — 1) (согласно (29. 112)), =Ь; — Ь >О откуда вытекает, что теперь все базисные переменные неотрицательны. Следовательно, базисное решение, полученное в результате вызова процедуры Р1чот в строке 8, является допустимым. Следующей выполняется строка 10, которая решает задачу Т,ии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
