Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 206
Текст из файла (страница 206)
Поскольку мы предположили, что задача В имеет допустимое решение, из леммы 29.11 следует, что задача В, имеет оптимальное решение с равным 0 целевым значением. Так как все канонические формы эквивалентны, в конечном базисном решении задачи В, должно выполняться ко = О„и после удаления из данной задачи переменной хс мы получим каноническую форму, базисное решение которой допустимо в задаче В. Эта каноническая форма возвращается в строке 15. Основная теорема линейного программирования Данная глава завершается демонстрацией корректности работы процедуры Я!МР1.ЕХ. Произвольная задача линейного программирования или неразрешима, или неограничена, или имеет оптимальное решение с конечным целевым значением, и в каждом случае процедура Я~мах работает правильно.
Теорема 29.13 (Основная теорема линейного программирования) Для любой задачи линейного программирования Е, представленной в стандарт- ной форме, возможен только один из следующих вариантов: При вызове процедуры Р~чот в строке 8 е = О. Если переписать неравен- ства (29.107), чтобы включить коэффициенты а,о, 934 Часть ГИ. Иэбраниые темы !. задача имеет оптимальное решение с конечным целевым значением; 2. задача является неразрешимой; 3. задача является неограниченной.
Если задача Ь является неразрешимой, процедура Я1МРеех возвращает сообщение "задача неразрешима". Если задача Ь является неограниченной, процедура Я1МРЕЕХ возвращает сообщение "задача неограниченная". В противном случае процедура Я1МИ.ЕХ возвращает оптимальное решение с конечным целевым значением. Двказавевльсвева. Согласно лемме 29.12, если задача линейного программирования Ь неразрешима, процедура Б1МРеех возвращает сообщение "задача неразрешима". Теперь предположим, что задача Ь разрешима.
В соответствии с леммой 29.12 процедура 1мгтгле1ге-51МРеех возвращает каноническую форму, базисное решение которой допустимо. Тогда согласно лемме 29.7 процедура Я1МРеех нли возвращает сообщение "задача неограниченная", или завершается возвращением допустимого решения. Если она завершается и возвращает конечное решение, то это решение является оптимальным согласно теореме 29.10. Если же процедура Е1МРЕЕХ возвращает сообщение "задача неограниченная'*, то задача Ь является неограниченной согласно лемме 29.2.
Поскольку процедура 81мРеех всегда завершается одним из перечисленных способов, доказательство завершено. Упражнения 29.5.1 Напишите подробный псевдокод реализации строк 5 и 14 процедуры 1141т1ле1ееЯ1МРЕЕХ. 29.5.2 Покажите, что при выполнении процедурой 1м1т1Аиге-Бгмтеех основного цикла процедуры Я1МРеех никогда не возвращается сообщение "задача неограниченная". 2Р.5.3 Предположим, что дана задача линейного программирования Ь в стандартной форме и что для обеих задач, прямой и двойственной, базисные решения, связанные с начальными каноническими формами, являются допустимыми.
Покажите, что оптимальное целевое значение задачи Х, равно О. 29.5.4 Предположим, что в задачу линейного программирования разрешено включать строгие неравенства. Покажите, что в зтом случае основная теорема линейного программирования не выполняется. Геена 29.
г1инейное нрограииироеание 955 29.5.5 Решите следующую задачу линейного программирования с помощью процедуры 81МРЕЕХ: х~ + Зхз х1 — ха < 8 максимизировать при условиях ( — 3 — Х1 — Хз — х1+ 4хз ( 2 х1 хз > О. 29.5.6 Решите следующую задачу линейного программирования с помощью процедуры 81МРЕЕХ: х1 — 2хз максимизировать при условиях х~+ — 2х1— Х1, 29.5. 7 Решите следующую задачу линейного программирования с помо1цью процедуры 81МРЕЕХ: максимизировать х1 + Зхз при условиях -Х1 + ХЗ < — 1 < — 3 — — хг — х1+ 4хз < 2 Х1 хг > О.
29.5.а Решите задачу линейного программирования 129.6)-(29.10). 29.5.9 Рассмотрим задачу линейного программирования Р с одной переменной х>0, где г, а и 1 представляют собой произвольный действительные числа. Пусть О— двойственная к Р задача. При каких значениях г, а, и 1 можно утверждать, что: максимизировать 1х при условиях гх<е 2хз < 4 бхз < -12 ха< 1 хз > О. 93б Часть 912 Избранные темы 1. обе задачи, Р и Р, имеют оптимальные решения с конечными целевыми значениями; 2. Р является разрешимой, а Р— неразрешимой; 3. Р является разрешимой, а Р— неразрешимой; 4. ни одна из задач Р и Р не является разрешимой. Задачи 29.1. Разрешимость линейных неравенств Пусть задано множество пз линейных неравенств с и переменными х„хз,..., х„.
В задаче о разрешимости системы линейных неравенств требуется ответить, существует ли набор значений переменных, удовлепюряющий одновременно всем неравенствам. зь Покажите, что для решения задачи о разрешимости системы линейных неравенств можно использовать алгоритм решения задачи линейного программирования.
Число переменных и ограничений, используемых в задаче линейного программирования, должно полиномиально зависеть от и и т. б. Покажите, что алгоритм решения задачи о разрешимости системы линейных неравенств можно использовать для решения задачи линейного программирования. Число переменных и линейных неравенств, используемых в задаче о разрешимости системы линейных неравенств, должно полиномиально зависеть от числа переменных и и числа ограничений зп задачи линейного программирования.
29.2. Донолняющая нежесткость Дополняющая нежесткость (сошр!ешепгагу з!ас)спезз) характеризует связь между значениями переменных прямой задачи и ограничениями двойственной задачи, а также между значениями переменных двойственной задачи и ограничениями прямой задачи. Пусть х — допустимое решение прямой задачи линейного программирования (29.1б) — (29.18), а у — допустимое решение двойственной задачи (29.83)-(29.85). Принцип дополняющей нежесткости гласит, что следующие условия являются необходимыми и достаточными условиями оптимальности х иу: а,у,=с,илих,=О для9=1,2,...,п оцх, = 6, илн у, = О для г = 1, 2,..., т з=1 ьь Убедитесь, что принцип дополняющей нежесткости справедлив для задачи линейного программирования (29.53) — (29.57). 937 Глони 29.
Линейное лрогроммировонив о. Докажите, что принцип дополняющей нежесткости справедлив для любой прямой и соответствующей ей двойственной задачи. в. Докажите, что допустимое решение х прямой задачи линейного программирования (29.16)-(29.18) является оптимальным тогда н только тогда, когда существуют значения у = (уыуз,...,у ), такие, что 1. у является допустимым решением двойственной задачи линейного программирования (29.83)-(29.85); 2. 2 „1 а;, у, = с; для всех 2, таких, что х.
> 0; 3. у, = 0 для всех з, таких, что 2"" обх, < 6,. 29.3. Целочисленное линейное нрограмиирование Задача целочисленного линейного нрограммирования представляет собой задачу линейного программирования с дополнительным ограничением, состоящим в том, что переменные х должны принимать целые значения. В упр. 34.5.3 показано, что даже определение того, имеет ли задача целочисленного линейного программирования допустимые решения, является ХР-сложной задачей; зто значит, что вряд ли существует полиномиапьный по времени алгоритм решения данной задачи.
а. Покажите, что для задач целочисленного линейного программирования справедлива слабая двойственность (лемма 29.8). й. Покажите, что двойственность (теорема 29.10) не всегда присуща задачам целочисленного линейного программирования. в. Пусть задана прямая задача линейного программирования в стандартной форме и пусть Р— оптимальное целевое значение прямой задачи, 13 — оптимальное целевое значение ее двойственной задачи, 1Р— оптимальное целевое значение целочисленной версии прямой задачи (т.е. прямой задачи с дополнительным ограничением, состоящим в том, что переменные принимают только целые значения), а Ш вЂ” оптимальное целевое значение целочисленной версии двойственной задачи.
Исходя из предположения о том, что и прямая, н двойственная целочисленные задачи разрешимы и ограниченны, покажите, что 1Р<Р=13<1Рг 29.4. Лемма Фаркаша Пусть А — матрица размером гп х и, а с — и-мерный вектор. Лемма Фаркаша (Гагказ) гласит, что разрешима только одна из систем Ах < 0 стх>0 язв Часть Нц Избранные темы А у=с у>0, где х — и-мерный вектор, а у — т-мерный вектор.
Докажите эту лемму. 29.5. Циркуляция с миициалькой стоимостью В этой задаче рассматривается вариант задачи потока минимальной стоимости из раздела 29.2, в которой не заданы ня целевое значение потока, ни исток и сток. Как и ранее, имеются транспортная сеть и стоимости ребер а(ц, о). Поток допустйм, если он удовлетворяет ограничению пропускной способности в каждом ребре и сохранению потока в каждой вершине. Цель заключается в поиске среди всех допустимых потоков того, который обладает минимальной стоимостью. Эта задача называется задачей поиска циркуляции минимальной стоимости. зь Сформулируйте задачу поиска циркуляции минимальной стоимости в виде задачи линейного программирования. б.
Предположим, что для всех ребер (и,о) Е Е значения стоимости а(ц,е) > О. Опишите оптимальное решение задачи поиска циркуляции минимальной стоимости. а Сформулируйте задачу поиска максимального потока в виде задачи линейного программирования для задачи поиска циркуляции минимальной стоимости. То есть для заданного экземпляра задачи о максимальном потоке С = Я Е) с истоком а, стоком г и пропускными способностями ребер с разработайте задачу поиска циркуляции минимальной стоимости, задав (возможно, другую) сеть С' = (Г, Е') с пропускными способностями ребер с' и стоимостями ребер а', такую, что можно получить решение задачи о максимальном потоке из решения задачи поиска циркуляции минимальной стоимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
