Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 187
Текст из файла (страница 187)
Объясните, каким образом, имея произвольную задачу линейного программирования, можно получить двойственную задачу непосредственно. 29.4-3. Запишите двойственную задачу для задачи максимального потока, заданной уравнениями (29.47)-(29.50). Объясните, как эта формулировка интерпретируется в качестве задачи минимального разреза. 29.4-4. Запишите двойственную задачу для задачи потока с минимальными затратами, заданной уравнениями (29.51)-(29.55).Обьясните, как интерпретировать полученную задачу с помощью графов и потоков. 29.4-5.
Покажите, что задача, двойственная к двойственной задаче линейного программирования, является прямой задачей. 29.4-6. Какой результат из главы 26 можно интерпретировать как слабую двойственность для задачи максимального потока? 29.5 Начальное базисное допустимое решение В данном разделе мы сначала покажем, как проверить, является ли задача линейного программирования разрешимой, и как в случае положительного ответа получить каноническую форму, базисное решение которой является допустимым. В заключение мы докажем основную теорему линейного программирования, в которой утверждается, что процедура В|ми.вх всегда дает правильный результат.
Поиск начального решения В разделе 29.3 предполагалось, что у нас есть некая процедура 1ьптмшгв Б!мгьех, которая определяет, имеет ли задача линейного программирования допустимые решения, и в случае положительного ответа возвращает каноническую форму, имеющую допустимое базисное решение. Опишем данную процедуру. Даже если задача линейного программирования является разрешимой, начальное базисное решение может оказаться недопустимым. Рассмотрим, например, Глава 29. Линейное программирование 915 следующую задачу: Максимизировать 2хз — хз при условиях 2х~ — хз < 2 (29. 105) (29.106) (29.107) (29.108) хд — бхз < — 4 хд,хз ) 0 Если преобразовать эту задачу в каноническую форму, базисным решением будет хз = О, хз = О. Это решение нарушает ограничение (29.107) и, следовательно, не является допустимым.
Таким образом, процедура 1мт~Аиге Б~МР1дх не может сразу возвратить эту очевидную каноническую форму. На первый взгляд, вообще неясно, имеет ли данная задача допустимые решения. Чтобы определить, существуют ли они, можно сформулировать вспомогательную задачу лилейного программирования (аих111агу 1шеаг ргойгаш). Для этой вспомогательной задачи мы сможем (причем достаточно легко) найти каноническую форму, базисное решение которой является допустимым. Более того, решение этой вспомогательной задачи линейного программирования позволит определить, является ли исходная задача разрешимой, и если да, то обеспечит допустимое решение, которым можно инициализировать процедуру 3!мРьех.
Лемма 29.11. Пусть 1 — задача линейного программирования в стандартной фор- ме, заданная уравнениями (29.16)-(29.18)„а Ь,„з — следующая задача линейного программирования с и+ 1 переменными: (29. 109) Максимизировать — хо при условиях ч Е абхз — хо < Ь; з=з (29.110) для 1 = 1, 2,..., т, для 2 = 0,1,...,и. (29.111) хз ~)0 Доказательство. Предположим, что Ь имеет допустимое решение х = (хм хз, ..., х„). Тогда решение хо = 0 в комбинации с х является допустимым решением задачи Ь „с целевым значением, равным О. Поскольку в Ь,ч присугствует ограничение хо > О, а цель состоит в максимизации — хо, это решение должно быть оптимальным решением Ь„чг. И обратно, предположим, что оптимальное целевое значение задачи Ьсчг равно О. Тогда хо = 0 и значения остальных переменных х удовлетворяют ограничениям Е.
В Задача Ь разрешима тогда и только тогда, когда оптимальное целевое значение задачи Ь „равно О. 916 Часть Ч!!. Избранные темы Теперь опишем стратегию поиска начального базисного допустимого решения задачи линейного программирования Ь, заданной в стандартной форме: 1ьлт!лили Б!ми.вх(А, Ь, с) 1 Пусть й — индекс минимального коэффициента Ь; 2 !Т Ьь > 0 ~> Допустимо ли начальное базисное решение? 3 гпеп ге!пгп Я1,2,..., п), (п+ 1, и+ 2,..., и+ т), А, Ь, с, 0) 4 Образуем Т,„„путем добавления -хо к левой части каждого уравнения и задаем целевую функцию равной — хо 5 Пусть (Ж, В, А, Ь, с, о) — результирующая каноническая форма задачи Ь,„, 1 -и+!с 6 с» Т ~»»»( содержит и + 1 небазисную переменную с и тп базисных переменных 7 (Ф, В, А, Ь, с, и) — Р!Чот(Ж, В, А, Ь, с, и, 1, 0) 8 с Данное базисное решение является допустимым для Т, „„ 9 Проводим итерации цикла зтЫ!е, описанного в строках 2-11 процедуры Б!мг!.нх, пока не будет найдено оптимальное решение Т, „„ 10 !Т в базисном решении хо = 0 11 гпеп ге1пгп конечную каноническую форму без переменной хо и с исходной целевой функцией 12 е!зе ге1пгп "задача неразрешима" Процедура !мт!лиги Б!мг1.их работает следующим образом.
В строках 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, в качестве выводимой переменной выбирается хя, базисная переменная, которая в базисном решении имеет наибольшее по абсолютной величине отрицательное значение. После заме- чательное решение вспомогательной задачи линейного программирования. Если проверка в строке 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 каноническая форма не возвращается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
