Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 203
Текст из файла (страница 203)
Лемма 29.6 Если в строках 4 и 9 процедуры Б~мрьнх всегда выполняется выбор переменной с наименьшим индексом, процедура Б1мрьех должна завершиться. Мы завершим данный раздел следующей леммой. Лемма 29. 7 Если процедура 1м1т|лшгн-Бьп'ьнх возвраглает каноническую форму, базисное решение которой является допустимым, то процедура Б ~ми.нх или выдает сообщение о неограниченности задачи линейного программирования, или завершается возвратом допустимого решения не более чем за ("+ ) итераций. Доказаллельсшво.
В леммах 29.2 и 29.б показано, что если процедура 1ьпт~лшхн-Б~мр~.нх возвращает каноническую форму, базисное решение которой является допустимым, то процедура Б~мрых либо выдает сообщение о неограниченности задачи линейного программирования, либо завершается, предоставляя допустимое решение. Используя обращение леммы 29.5, приходим к заключению, что если процедура Б~ми.нх завершается предоставлением допустимого решения, то это происходит не более чем за ("+ ) итераций. Упражнения 29.3Л Завершите доказательство леммы 29.4, показав, что с = с' и с = и'. 920 Часть Рй.
Избранныетены 29.3.2 Покажите, что значение с никогда ие уменьшается в результате вызова процедуры Р!ЧОт в строке 12 процедуры Я!МИ.ЕХ. 29.3.3 Докажите, что каноническая форма, переданная процедуре Р!чот, эквивалентна возвращаемой ею. 29.3.4 Предположим, что мы преобразовали задачу линейного программирования (А, 5, с) из стандартной формы в каноническую. Покажите, что базисное решение является допустимым тогда и только тогда, когда 51 > 0 для 1 = 1, 2,..., пз. 29.3.5 Решите следующую задачу линейного программирования, используя процедуру $1МР1.ЕХ: Х1 хг Х1, Хг 29.3.б Решите следующую задачу линейного программирования, используя процедуру Я!МР1.ЕХ: 2х1 + хг < 2 хг,хг > О. 29.3.
1 Решите следующую задачу линейного программирования, используя процедуру 81МРЕЕХ: минимизировать х1 + хг + хз при условиях 2х1 + 7.5хг + Зхз > 10000 20х1 + 5хг + 10хз > 30000 Х1, Х2, ХЗ > О. 29.3.а В доказательстве леммы 29.5 мы доказали, что имеется не более (™+") способов выбора множества В базисных переменных. Приведите пример задачи линейного максимизировать 18Х1 + 12.5хг при условиях Х1 + Х2 максимизировать 5х1 — Зх2 при условиях х! — х2 < 1 < 20 < 12 < 16 > О. Глава г9. Линейное нрагралел|иравание 9г! программирования, в которой юличество способов выбора множества В базис- ных переменных строго меньше ( „). 29.4.
Двойственность ~ Ьуз 1=1 (29.83) минимюировать при условиях т Е а1 р1 ) с для 7' = 1, 2,..., и, 1=1 у1 >О для1=1,2,...,т. (29.84) (29.85) Чтобы получить двойственную задачу, мы изменили максимизацию на минимизацию, поменяли роли козффициентов правых частей и целевой функции и заменили неравенства "меньше или равно" неравенствами *'больше или равно'*. С каждым из т ограничений прямой задачи в двойственной задаче связана переменная у1, а с каждым из и ограничений двойственной задачи связана переменная прямой задачи х . Например, рассмотрим задачу линейного программирования, заданную уравнениями (29.53)-(29.57). Двойственная ей задача имеет следую- Мы доказали, что при определенных предположениях процедура 81мш.вх завершается. Однаю еще не доказано, что она действительно находит оптимальное решение задачи линейного программирования.
Чтобы сделать это, введем новое мощное понятие — двойственность (дуальность) задач линейного лрограммироваиия (!1пеаг-ргойгаппп!л8 дпа!1гу). Двойственность позволяет доказать, что решение действительно оптимальное. С примерам двойственности мы встречались в главе 26, в теореме 26.6 о максимальном потоке и минимальном разрезе. Предположим, например, что в неюторой задаче поиска максимального потока мы нашли поток г" величиной ~У~.
Как выяснить, является ли г" максимальным потоком? Согласно теореме о максимальном потоке и минимальном разрезе, если можно найти разрез, значение которого также равно ф, то тем самым подтверждается, что Г действительно является максимальным потоком. Это пример двойственности: для задачи максимизации определяется связанная с ней задача минимизации, причем такая, что зти две задачи имеют одинаковые целевые значения. Опишем, как для заданной задачи линейного программирования, в которой требуется максимизировать целевую функцию, сформулировать двойственную (в!па!) задачу линейного программирования, в которой целевую функцию требуется минимизировать и оптимальное значение которой идентично оптимальному значению исходной задачи.
При работе с двойственными задачами исходная задача называется ирамой (рйша!). Для прямой задачи линейного программирования в стандартной форме, такой как (29.16Н29.18), определим двойственную задачу следующим образом: Часть «7Х Избранные темы шнй вид: минимизировать ЗОуз + 24уг + Збуз при условиях (29.8б) у«+ 2уг + у«+ 2уг + Зу«+ буг + Умуг Уз В теореме 29.10 мы покажем, что оптимальное значение двойственной задачи линейного программирования всегда равно оптимальному значению прямой задачи. Более того, симплекс-алгоритм неявно решает одновременно обе задачи, прямую и двойственную, тем самым обеспечивая доказательство оптимальности.
Начнем с демонстрации слабой двойственности («ясак бцайзу), которая состоит в утверждении, что любое допустимое решение прямой задачи линейного программирования имеет целевое значение, не превышающее целевого значения любого допустимого решения двойственной задачи линейного программирования. Лемма 29.В ~Слабая двойственность задач линейного программирования) Пусть х представляет собой произвольное допустимое решение прямой задачи линейного программирования (29.16)-(29.18), а у — любое допустимое решение дуальной задачи линейного программирования (29.83»-(29.85). Тогда н т сх.<~~ бу; з=1 «=1 Доказательство.
с.х з=1 (согласно (29.84)) т <~ Ьзу, (согласно (29.17)) Следствие 29. 9 Пусть х является допустимым решением прямой задачи линейного программирования (А, («, с), а у — допустимым решением соответствуюшей двойственной задачи. Если с,х = ~» («зу;, з=1 «=1 4уз >3 Уз >1 2уз >2 > О. <~~ ~~> а;у, х з=« «=1 «и ( н = ~~) ~~ а;.х у, «=1 з=1 (29.87) (29.88) (29.89) (29.90) 9еа Глана 79.
Линейное нроераииироеание то х и у являются оптимальными решениями прямой и двойственной задач соот- ветственно. Доказавеельсяево. Согласно лемме 29.8 целевое значение допустимого решения прямой задачи не превышает целевого значения допустимого решения двойственной задачи. Прямая задача является задачей максимизации, а двойственная — задачей минимизации. Поэтому, если допустимые решения х и у имеют одинаковые целевые значения, ни одно из ник невозможно улучшить.
Прежде чем доказывать, что всегда существует решение двойственной задачи, целевое значение которого равно целевому значению оптимального решения прямой задачи, покажем, как найти такое решение. При решении задачи линейного программирования (29.53)-(29.57) с помощью симплекс-алгоритма последняя итерация дает каноническую форму (29.72)-(29.75) с целевым значением г = 28 — хз/6 — хз/6 — 2хе/3, В = (1, 2, 4) и Тй = (3, 5, 6). Как будет показано ниже, базисное решение, связанное с этой последней канонической формой, является оптимальным решением задачи линейного программирования; таким образом, оптимальным решением задачи (29.53)-(29.57) является (хы хз, хз) = (8, 4, 0) с целевым значением (3 8) + (1 4) + (2 О) = 28.
Как мы также покажем ниже, можно легко получить оптимальное решение двойственной задачи: оптимапьные значения двойственных переменных противоположны коэффициентам целевой функции прямой задачи. Более строго, предположим, что последняя каноническая форма прямой задачи имеет вид я=с+~ сх зев х, = 5, — ~~~ а~.х для ( е В або Тогда оптимальное решение двойственной задачи можно найти следукицим образом: — с'„+,, если (п + г) е Тй, У1 = 0 в противном случае . Таким образом, оптимальным решением двойственной задачи линейного программирования (29.86)-(29.90) является у1 = 0 (поскольку и + 1 = 4 е В), ра = — с~~ — — 1/6 и 17з = — са — — 2/3.
Вычисляя значение целевой функции двойственной задачи (29.86), получаем целевое значение (30 0) + (24 (1/6)) + (36 (2/3) ) = 28; это подтверждает, что целевое значение прямой задачи действительно равно целевому значению двойственной задачи. Используя эти вычисления и лемму 29.8, получаем доказательство, что оптимальное целевое значение прямой задачи линейного программирования равно 28. Теперь покажем, что этот подход применим в общем случае: таким образом можно найти оптимальное решение двойственной задачи и одновременно доказать оптимальность решения прямой задачи. Часть еи.
Избранные тены Теорема 29.1д (Двойственность задач линейного программирования) Предположим, что процедура 81ми.пх возвращает значения х = (х1, хз,..., х„) для прямой задачи линейного программирования (А, б, с). Пусть )з' и  — множества небазисных и базисных переменных окончательной канонической формы, с' — ее коэффициенты, а у = (у1, уз,..., у ) определяется уравнением (29.91). Тогда х — оптимальное решение прямой задачи линейного программирования, у — оптимальное решение двойственной задачи и и т сзх, = ) б1у, 1=1 с=1 (29.92) Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
