Алгоритмы - построение и анализ (1021735), страница 186
Текст из файла (страница 186)
Мы не будем приводить доказательств, что эти стратегии позволяют избежать зацикливания. Лемма 29.6. Если в строках 3 и 8 процедуры 81МРьЕХ выполняется выбор переменной с наименьшим индексом, процедура 81мРьех должна завершиться. ° Данный раздел мы закончим следующей леммой. Лемма 29.7. Если процедура 1ы1т1ль1ге 81МРьех возвращает каноническую форму, базисное решение юторой является допустимым, то процедура 81МРЬЕХ или выдает сообщение о неограниченности решения задачи линейного программирования, или завершается, предоставляя допустимое решение, не более чем за ("~™) итераций.
Доказательство. В леммах 29.2 и 29.6 показано, что если процедура 1ы1т1А1.- 1Ее 81мРьех возвращает каноническую форму, базисное решение которой является допустимым, то процедура 81мРьех или выдает сообщение о неограниченности решения задачи линейного программирования, или завершается, предоставляя допустимое решение. Используя лемму 29.5, методом от противного приходим Глава 29. Линейное программирование 907 к заключению, что если процедура 81мрьнх завершается предоставлением допу- стимого решения, то зто происходит не более чем за ("+~) итераций. Упражнения 29.3-1. Завершите доказательство леммы 29А, показав, что с = с' и о = »>. 29.3-2.
Покажите, что значение и никогда не уменьшается в результате вызова процедуры Р1чот в строке 11 процелуры 81ми.нх. 29.3-3. Предположим, что мы преобразовали задачу линейного программирования 1А, Ь, с) из стандартной формы в каноническую. Покажите, что базисное решение является допустимым тогда и толью тогда, югда Ь; ) 0 для г = 1,2,..., т. 29.3-4. Решите следуюшую задачу линейного программирования, используя процедуру ймрьнх: Максимизировать 18х1 + 12.5хз при условиях х1 + хг ( 20 < 12 хз < 16 хм ха ) 0 29.3-5.
Решите следующую задачу линейного программирования, используя процедуру 81ми.нх: Максимизировать — 5х| — Зхз при условиях хз — хз < 1 2хг+ хз » (2 хыхз ) 0 29.3-б. Решите следующую задачу линейного программирования, используя процедуру Б~мрых: Минимизировать х1 + хз + хз при условиях 2х1+ 7.5хз+ Зхз ~ 10000 20х1 + бхз + 10хз ~ 30000 х1> хз>хз ~1 Часть ЧП. Избранные темы 29.4 Двойственность (29.86) Минимизировать при условиях а,уу; > с) для ) = 1, 2,..., и, Е (29.87) у; ) О для(=1,2,...,гп.
(29.88) Чтобы получить двойственную задачу, мы изменили максимизацию на минимизацию, поменяли роли коэффициентов правых частей и целевой функции и заменили неравенства "меньше или равно" на "больше или равно". С каждым из гп ограничений прямой задачи в двойственной задаче связана переменная уь а с каждым из п ограничений двойственной задачи связана переменная прямой задачи к . Например, рассмотрим задачу линейного программирования, задан- Мы доказали, что при определенных предположениях процедура Я!мРг.ех завершается.
Однако еще не доказано, что она действительно находит оптимальное решение задачи линейного программирования. Чтобы сделать это, введем новое мощное понятие — двойственность (дуальность) задач линейного нрограммирования (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, с).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
