Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 186
Текст из файла (страница 186)
Однако еще не доказано, что она действительно находит оптимальное решение задачи линейного программирования. Чтобы сделать это, введем новое мощное понятие — двойственность (дуальность) задач линейного нрограммирования (1шеаг-ргойгаппшп8 дна!1!у). Двойственность — очень важное свойство. В задачах оптимизации определение двойственной задачи практически всегда сопровождается открытием алгоритма с полиномиальным временем выполнения.
Двойственность также является очень мощным средством при доказательстве того, что решение действительно является оптимальным. Предположим, например, что в некой задаче максимального потока мы нашли поток ) величиной 1)'!. Как выяснить, является ли г максимальным потоком? Согласно теореме 26.7, если мы сможем найти разрез, значение которого также равно !7"!, то ) действительно является максимальным потоком. Это пример двойственности: для задачи максимизации определяется связанная с ней задача минимизации, причем такая, что эти две задачи имеют одно и то же оптимальное значение. Опишем, как для заданной задачи линейного программирования, в юторой требуется максимизировать целевую функцию, сформулировать двойственную (дпа1) задачу линейного программирования, в которой целевую функцию требуется минимизировать и оптимальное значение юторой идентично оптимальному значению исходной задачи.
Прн работе с двойственными задачами исходная задача называется прямой (рпша!). Для задачи линейного программирования в стандартной форме, такой как (29.16)-(29.18), определим двойственную задачу следующим образом: 909 ную уравнениями (29.56)-(29.60). Двойственная ей задача выглядит следующим образом: Минимизировать 30уз + 24уз + Збуз прн условиях (29.89) В теореме 29.10 мы покажем, что оптимальное значение двойственной задачи линейного программирования всегда равно оптимальному значению прямой задачи. Более того, симплекс-алгоритм неявно решает одновременно обе задачи, прямую и двойственную, тем самым обеспечивая доказательство оптимальности. Начнем с доказательства слабой двойственности (иеа1с сйи11гу), которая состоит в утверждении, что любое допустимое решение прямой задачи линейного программирования имеет целевое значение, не превышающее целевого значения любого допустимого решения двойственной задачи линейного программирования. Лемма 29.8 (Слабая двойственность задач линейного программирования).
Пусть х — некое допустимое решение прямой задачи линейного программи- рования (29.16) — (29.18), а у — некое допустимое решение двойственной задачи (29.86)-(29.88). Тогда ,'~ схд< ~> 5;у;. 5=1 в=1 Докизаюивльсгиво. Следствие 29.9. Пусть х — некоторое допустимое решение прямой задачи ли- нейного программирования (А, 5, с), и пусть у — некоторое допустимое решение соответствующей двойственной задачи. Если схд= ,'~ ЬУ;, то х и у являются оптимальными решениями прямой и двойственной задач соот- ветственно.
Глава 29. Линейное программирование уг+ 2уз+ 4уз ) 3 уг + 2уз + уз > 1 Зу~ + буг + 2уз ) 2 Ум Уз Уз ~ 0 И в ш т и т сух.< ) ~~) а;у; х = ) ~2 аих. У,<~) 5;у;, 5=1 5=1 в=1 ~=1 где первое неравенство следует из (29.87), а второе — из (29.17). (29.90) (29.91) (29.92) (29.93) Часть ЧП.
Избранные темы 910 Доказательслгво. Согласно лемме 29.8, целевое значение допустимого решения прямой задачи не превышает целевого значения допустимого решения двойственной задачи. Прямая задача является задачей максимизации, а двойственная — задачей минимизации. Поэтому если допустимые решения х и у имеют одинаковое целевое значение, ни одно из них невозможно улучшить.
Прежде чем доказать, что всегда существует решение двойственной задачи, целевое значение которого равно целевому значению оптимального решения прямой задачи, покажем, как найти такое решение. При решении задачи линейного программирования (29.56)-(29.60) с помощью симплекс-алгоритма в результате последней итерации была получена каноническая форма (29.75) — (29.78), в которой В = 11,2,4), М = 13,5,6). Как будет показано ниже, базисное решение, связанное с этой последней канонической формой, является оптимальным решением задачи линейного программирования; таким образом, оптимальное решение задачи (29.56)-(29.60) — (хз, хз, хз) = (8, 4, 0) с целевым значением 28.
Мы также покажем, что можно легко получить оптимальное решение двойственной задачи: оптимальные значения двойственных переменных противоположны коэффициентам целевой функции прямой задачи. Более строго, предположим, что последняя каноническая форма прямой задачи имеет вид: з=ю +~сх1 .2 1еФ х; =5; — ~~> а'; х для(иВ. урн Тогда оптимальное решение двойственной задачи можно найти следующим образом: — с'„+; если (п+1) Е Ф, Д1 = 0 в противном случае. (29.94) Таким образом, оптимальным решением двойственной задачи линейного программирования (29.89)-(29.93) является р1 = 0 (поскольку и+1 = 4 Е В), уз = -с~а —— = 1/б и уз = -с~а —— 2/3.
Вычисляя значение целевой функции двойственной задачи (29.89), получаем целевое значение (30 0)+(24 (1/6))+(36 (2/3)) = 28; это подтверждает, что целевое значение прямой задачи действительно равно целевому значению двойственной задачи. Используя эти вычисления и лемму 29.8, получаем доказательство, что оптимальное целевое значение прямой задачи линейного программирования равно 28. Теперь покажем, что в общем случае оптимальное решение двойственной задачи и доказательство оптимальности решения прямой задачи можно получить таким способом. Глава 29.
Линейное программирование 911 Теорема 29.10 (Двойственность задач линейного программирования). Предположим, что процедура 8!ми.их возвращает значения х = (хм ха,..., хи) для прямой задачи линейного программирования (А, 6, с). Пусть Ж и  — множества небазисных и базисных переменных окончательной канонической формы, с'— ее коэффициенты, а у = (уз, рз,..., у,„) определяется уравнением (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 и = о + г, с'ху + г ( — у;) Ь; — г абху — — (в соответствии с (29.32)) уьц Теперь мы покажем, что решение у, заданное формулой (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. Предположим, у нас есть задача линейного программирования, не приведенная к стандартной форме. Можно получать двойственную задачу в два этапа: сначала привести исходную задачу к стандартной форме, а затем формулировать двойственную. Однако было бы удобно иметь возможность сразу формулировать двойственную задачу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
