Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 204
Текст из файла (страница 204)
Согласно следствию 29.9, если удастся найти допустимые решения х и у, которые удовлетворяют уравнению (29.92), то х и у должны быть оптимальными решениями прямой и двойственной задач. Покажем, что решения й и р, описанные в формулировке теоремы, удовлетворяют уравнению (29.92). Предположим, что мы решаем прямую задачу линейного программирования (29.!б)-(29.18) с помощью процедуры 81мгых.
В ходе работы алгоритма строится последовательность канонических форм, пока он не завершится, предоставив окончательную каноническую форму с целевой функцией ге о+) сх 3 Е 1'з' (29.93) Поскольку процедура 81мгькх завершается с предоставлением решения, то со- гласно условию в строке 3 мы знаем, что с' < О для всех 16 )н (29.94) Если мы определим с'=О длявсехзеВ, то уравнение (29.93) можно переписать как (29.95) (поскольку с' = О, если 1 Е В) В базисном решении х, связанном с конечной канонической формой, х = О для всех 1 б Л, а г = о'. Поскольку все канонические формы эквивалентны, при вычислении значения исходной целевой функции для решения х мы должны с+1 сх 1йзз зз+~~ сх +~> сзхз зен зеп и+та с + ~ с.х (так как Л11В = (1,2,...,п+ пз)) . (29.96) Глава гд Линейное наограммироеание получить то же самое целевое значение: и Е- = с;хз —— 5=1 (29.97) (29.98) Теперь покажем, что решение у, заданное формулой (29.91), является допустимым решением двойственной задачи и его целевое значение 2," 1 Ь,у; равно 2,"и1с„х,.
Из уравнения (29.97) следует, что значения целевых функций первой и последней канонических форм, вычисленные для х, равны. В общем случае из эквивалентности всех канонических форм вытекает, что для любого набора ЗНаЧЕНИй Х = (Х1, ХЗ,..., Хи) СПРаВЕДЛИВО РаВЕНСтВО и+иг с х. = и + ~~1 сух.. СЛЕдОВатЕЛЬНО, дпя ЛЮбОГО НабОра ЗНаЧЕНИй Х = (Х1, Хт,..., Хи) ИМЕЕМ ~ ~сх 1=и+1 ~~> Сги+,Х„+1 = 6'+ (согласно (29.91) и (29.95)) и ~с,'х + и ~с'х + 5=1 и с'х + 5=1 ~с.ху+ ,1'=1 и С1Х 5=1 и'+ ~~ 'с,'х, хи1 и~+ ~ сух + ~~> Их уа1е 1йВ и'+ ~(с' О) + ~ ~(О х ) УйФ 1йВ иг ,~ ( у1)х ег=1 и1 и ( — уе) Ье — "~ ае х, (согласно (29.32)) 1=1 1=1 иг иг и Ьгуг+ ~~~ (а1ух ) уг 1=1 1=1 1=1 9еб Часть егг'. Избсынные тены и иг п т о'+ ~~г с,'х — ЯЬу, + ) ~~ (а;,у,) х г=1 «=1 з=1 г=1 < и~ — ~~ Ьгу, + ~~г сг + ~> аоу, хб, г=1 г'=1 г, г=1 так что и т и т сухз — — о' — ~~~ Ь,у; + ~~г с' + ) аоу, х . (29.99) з=! г 1 1=1 г=1 Применив лемму 29.3 к уравнению (29.99), получаем гг — ~~г Ь~у, = О, г=1 с +~ а,у,=с (29.100) (29.101) для з = 1, 2,..., и .
с;=с + р аггрл гни 1 т агб йг г=1 что удовлетворяет ограничениям (29.84) двойственной задачи. Наконец, посколь- ку с' < 0 для всех з е Ф 1.1 В, то, задав у в соответствии с уравнением (29.91), получим, что все у, > О, так что ограничения неотрицательности также удовле- творены. Итак, мы показали, что если данная задача линейного программирования разрешима, процедура 1н|т!лшхе-81мгых возвращает допустимое решение и процедура 81М9ЬНХ завершается, не выдав сообщение "задача неограниченная", то возвращенное решение является оптимальным. Мы также показали, как строится оптимальное решение двойственной задачи линейного программирования.
Упражнения 29.4.1 Сформулируйте двойственную задачу для задачи, приведенной в упр. 29.3.5. Согласно уравнению (29.100) 2„,", Ь;у, = о', следовательно, целевое значение двойственной задачи (~ ™, Ь;у;) равно целевому значению прямой задачи (с'). Осталось показать, что р является допустимым решением двойственной задачи. Из (29.94) и (29.95) следует, что с' < 0 для всех 9 = 1, 2,..., п + т. Позтому для любого 9 = 1, 2,..., и из (29.101) следует, что Глава 79.
Линейное лрограииирование 977 29.4.2 Предположим, имеется задача линейного программирования, не приведенная к стандартной форме. Можно получать двойственную задачу в два этапа: сначала привести исходную задачу к стандартной форме, а затем сформулировать двойственную. Однако было бы удобно иметь возможность сразу формулировать двойственную задачу. Объясните, каким образом, имея произвольную задачу линейного программирования, можно получить двойственную задачу непосредственно. 29.4.3 Запишите двойственную задачу для задачи поиска максимального потока, заданной уравнениями (29.47Н29.50). Объясните, как интерпретировать эту формулировку в качестве задачи минимального разреза.
29.4.4 Запишите двойственную задачу для задачи потока с минимальной стоимостью, заданной уравнениями (29.51)-(29.52). Объясните, как интерпретировать полученную задачу в терминах графов и потоков. 29.4.5 Покажите, что задача, двойственная к двойственной задаче линейного програм- мирования, является прямой задачей. 29.4.6 Какой результат из главы 26 можно интерпретировать как слабую двойственность для задачи поиска максимального потока? 29.5.
Начальное базисное допустимое решение В этом разделе мы покажем, как проверить, является ли задача линейного программирования разрешимой, и как в случае положительного ответа получить каноническую форму, базисное решение которой является допустимым. В заключение мы докажем основную теорему линейного программирования, в которой утверждается, что процедура Ягмрг.ех всегда дает правильный результат. Поиск начального решения В разделе 29.3 предполагалось, что у нас есть некая процедура 1м1т~лшгв31мрт.нх, которая определяет, имеет ли задача линейного программирования допустимые решения, и в случае положительного ответа возвраШает каноническую форму, имеющую допустимое базисное решение.
Опишем данную процедуру. Даже если задача линейного программирования является разрешимой, начальное базисное решение может оказаться недопустимым. Рассмотрим, например, 92В Часть 9И, Избранные темы следующую задачу линейного программирования: (29.102) максимизировать 2х1 — хз при условиях 2х1 — хз < 2 х1 — бхз < -4 (29.103) (29.104) (29.105) х1 хз > О. Если преобразовать эту задачу в каноническую форму, базисным решением будет х1 = О, хз = О. Это решение нарушает ограничение (29.104) и, следовательно, не является допустимым. Таким образом, процедура 11ч1т1яихн-81мгьлх не может сразу возвратить эту очевидную каноническую форму.
Чтобы определить, существуют ли допустимые решения заданной задачи линейного программирования, можно сформулировать вспомогательную задачу линейного программирования (аих11шгу 11пеаг ргойгаш). Для этой вспомогательной задачи мы сможем (причем достаточно легко) найти каноническую форму, базисное решение которой является допустимым. Более того, решение этой вспомогательной задачи линейного программирования позволит определить, является ли исходная задача разрешимой, и, если является, обеспечит допустимое решение, которым можно инициализировать процедуру 81М9ЬЕХ. Лемма 29. 11 Пусть Ь представляет собой задачу линейного программирования в стандартной форме, заданную уравнениями (29.16К29.18), а Ь,„, — следующую задачу ли- нейного программирования с п + 1 переменными: (29.106) (29.107) максимизировать при условиях -хс о11 хз — хо ( 6; для 1 = 1, 2,..., пт 1=1 хб > 0 для 9 = О, 1...
п . (29.108) Задача Ь разрешима тогда н только тогда, когда оптимальное целевое значение задачи Е, равно нулю. Теперь опишем стратегию поиска начального базисного допустимого решения задачи линейного программирования Е, заданной в стандартной форме; Доказательство. Предположим, что Ь имеет допустимое решение х = (х1, хз,..., х„). Тогда решение хо = 0 в комбинации с х является допустимым решением задачи Т„„с целевым значением, равным О. Поскольку в Т„„, присутствует ограничение хс > О, а цель состоит в максимизации — хс, это решение должно быть оптимальным решением Т, „.
И обратно, предположим, что оптимальное целевое значение задачи Ь,нз равно нулю. Тогда хе = О, и значения остальных переменных х удовлетворяют ограничениям Т. 929 Глава г9, Линейное программирование 1х1т!А шее-Я!м9еех (А, 6, с) 1 Пусть й является индексом минимального Ь, 2 Ы Ьь ) 0 // Допустимо ли начальное базисное решение? 3 гегнгп((1,2,...,п),(о+1,и+2,...,п+т),А,Ь,с,О) 4 Образуем Ен путем добавления — ко к левой части каждого ограничения и задаем целевую функцию -хо 5 Пусть (1й, В, А, 6, с, 9) представляет собой результирующую каноническую форму для г нии 6 1= и+)е 7 // /н~ имеет п+ 1 небазисную и т базисных переменных 8 (/лг, В, А, Ь, с, о) = Р1уот(Ж, В, А, Ь, с, 9,1, 0) 9 // Базисное решение является допустимым для /„„, 10 Выполняем итерации цикла згй11е в строках 3 — 12 процедуры 81мреех, пока не будет найдено оптимальное решение задачи /, 11 1т" в оптимальном решении Е, йа = 0 12 Ы йо является базисной переменной 13 выполнить одно (вырожденное) замещение, чтобы сделать ее небазисной 14 В оюнчательной канонической форме для Е, удалить из ограничений хо и восстановить исходную целевую функцию Е, но заменить в этой целевой функции каждую базисную переменную правой частью связанного с ней ограничения !5 гегпгп полученную окончательную каноническую форму 16 е1зе геангп "задача неразрешима" Процедура!191т1Аыхе-Б~мреех работает следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
