Алгоритмы - построение и анализ (1021735), страница 187
Текст из файла (страница 187)
Пусть Ж и  — множества небазисных и базисных переменных окончательной канонической формы, с'— ее коэффициенты, а у = (уз, рз,..., у,„) определяется уравнением (29.94). Тоша х — оптимальное решение прямой задачи линейного программирования, у— оптимальное решение двойственной задачи и с й = ~~ 6 у;.
(29.95) г=з Доказаигельсгяао. Согласно следствию 29.9, если нам удастся найти допустимые решения х и у, которые удовлетворяют уравнению (29.95), то х и у должны быть оптимальными решениями прямой и двойственной задач. Покажем, что решения х и у, описанные в формулировке теоремы, удовлетворяют уравнению (29.95). Предположим, что мы решаем прямую задачу линейного программирования (29.16)-(29.18) с помощью процедуры Б~мрьнх. В ходе работы алгоритма строится последовательность канонических форм, пока он не завершится, предоставив окончательную каноническую форму с целевой функцией а = и'+ ~~~ с'х .. уеи (29.96) Поскольку процедура Б~м~.их завершается с предоставлением решения, то, со- гласно условию в строке 2,мы знаем, что с' < О для всех 7'Е № (29.97) Если мы определим с~ = О для всех 1 е В, (29.98) то уравнение (29.96) можно переписать так: с+ р сху —— уек с'+ ~~~ с';ху+ ,'> с'х1 = (поскольку с' = О для з Е В) уеФ уен и+т с + ,'~ с'.х (поскольку йг 0 В = (1, 2,..., п + т) ) (29.99) В базисном решении х, связанном с конечной канонической формой, й.
= О для всех з Е № и я = и'. Поскольку все канонические формы эквивалентны, Часть ЧП. Избранные темы 912 при вычислении значения исходной целевой функции для решения х мы должны получить то же самое целевое значение, т.е. и+т ,'> ох о + ~1 1=1 о'+ ~~ те гг о'+ ~~ /— с.х 1 (29.100) г- %» сх + г сх 1ЕВ (с'- 0) + ,'~ (О х.) = ха В (29.
101) Š— Е г % ~ сх =о+~ сх. Следовательно, для любого набора значений х мы имеем: и Е сх ~~> с'х 1=1 и и+а ,'> с' х + ,'> с' х 1=1 у=и+1 и пь с'х + ,'> сиьчхи+; —— 1=1 1=1 с'ху+ ~Г ( — у;) х„+; —— =и+ / (в соответствии с (29.94)) и и1 и = о + г,с1ху + г ( — у;) Ь; — г абху — — (в соответствии с (29.32)) уьп 1=1 уьц Теперь мы покажем, что решение у, заданное формулой (29.94), является допустимым решением двойственной задачи и его целевое значение 2„, Ь;у; равно 2 ", суху. Из уравнения (29.100) следует, что значения целевых функций первой и последней канонических форм, вычисленные для х, равны.
В общем случае, эквивалентность всех канонических форм подразумевает, что для любого набора значений х = (хы хз,...,х„) справедливо равенство Глава 29. Линейное программирование 913 так что >> »> >> »> с х = о> — ~~~Ьуз +~~~ сс + ~1 а; у; х >=1 3=1 >=1 (29.102) Применяя лемму 29.3 к уравнению (29.102), получаем о' — ~~1 Ь уг = О, >=1 »> > с; + р а; у; = с; (29.103) для 3 = 1,2,...,п.
(29.104) Из уравнения (29.103) следует, что 2„™ Ьгу; = о>, поэтому целевое значение двойственной задачи (~ ~ Ь,у;) равно целевому значению прямой задачи (о'). Осталось показать, что у является допустимым решением двойственной задачи. Из (29.97) и (29.98) следует, что с' < 0 для всех 3 = 1, 2,..., и + т. Поэтому для любого г = 1, 2,..., т из (29.104) вытекает, что > су = су + ~ абу> < ~ об>у>з что удовлетворяет ограничениям (29.87) двойственной задачи.
Наконец, поскольку с' < 0 для всех 7' Е 1»'О В, то, задав у в соответствии с уравнением (29.94), мы получим, что все у; > О, так что ограничения неотрицательности также удовлетворены. И Итак, мы показали, что если данная задача линейного программирования разрешима, процедура 1л11т!А1.1ее 81мРьех возвращает допустимое решение и процедура 81мРеех завершается, не выдав сообщение "неограниченна", то возвра1ценное решение является оптимальным. Мы также показали, как строится опп1мальное решение двойственной задачи линейного программирования. о'+ ~ с'ху— 3=1 о +~> ох 3=1 о — Е Ь*у* »> »> >> ,'> Ь,уг+ ~~ ~~1 (а; х )у1 = >=1 Ь,уг+ ~1 >> (абу;) х 1=1 3=1 >=1 » »> + ~) с'; + ~~1 абуг ху, 914 Часть Ч11. Избранные темы Упражнения 29.4-1.
Сформулируйте двойственную задачу для задачи, приведенной в упражнении 29.3-4. 29.4-2. Предположим, у нас есть задача линейного программирования, не приведенная к стандартной форме. Можно получать двойственную задачу в два этапа: сначала привести исходную задачу к стандартной форме, а затем формулировать двойственную. Однако было бы удобно иметь возможность сразу формулировать двойственную задачу. Объясните, каким образом, имея произвольную задачу линейного программирования, можно получить двойственную задачу непосредственно. 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.вх работает следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
