Алгоритмы - построение и анализ (1021735), страница 189
Текст из файла (страница 189)
Теорема 29.13 (Основная теорема линейного программирования). Для любой задачи линейного программирования Т,, заданной в стандартной форме, возможен только один из следующих вариантов: Это означает, что теперь все базисные переменные неотрицательны. Следовательно, базисное решение, полученное в результате вызова процедуры Р1чот в строке 7, является допустимым. Следующей выполняется строка 9 и решается задача 7„. Поскольку мы предположили, что задача Т, имеет допустимое решение, согласно лемме 29.11, задача Т,„„имеет оптимальное решение с равным 0 целевым значением. Так как все канонические формы эквивалентны, в конечном базисном решении задачи Т „„хо = О, и после удаления из данной задачи переменной хо мы получим каноническую форму, базисное решение которой допустимо в задаче Т,.
Эта каноническая форма возвращается в строке 10. а Глава 29. Линейное программирование 921 1. задача имеет оптимальное решение с конечным целевым значением; 2. задача является неразрешимой; 3. задача является неограниченной. Если задача Ь является неразрешимой, процедура Я[мгьех возвращает сообщение "неразрешима". Если задача Т, является неограниченной, процедура Я~мг~.ех возвращает сообщение "неограниченна".
В противном случае процедура З~мг~.ех возвращает оптимальное решение с конечным целевым значением. Доказагнельслгво. Согласно лемме 29.12, если задача линейного программирования Т, неразрешима, процедура 81мгьех возвращает сообщение "неразрешима". Теперь предположим, что задача Ь разрешима. В соответствии с леммой 29.12, процедура 1ьнт!Атее 8!мв1.ех возвращает каноническую форму, базисное решение которой допустимо.
Тогда, согласно лемме 29.7, процедура Я[мгьех илн возвращает сообщение "неограниченна", или завершается возвращением допустимого решения. Если она завершается и возвращает конечное решение, то это решение является оптимальным согласно теореме 29.10. Если же процедура Б~мй.ех возвращает сообщение "неограниченна", то задача Ь является неограниченной согласно лемме 29.2.
Поскольку процедура Б~мгьех всегда завершается одним из перечисленных способов, доказательство завершено. И Упражнения 29.5-1. Напишите подробный псевдокод программы для реализации строк 5 и 11 процелуры 1ьлт1млю З~мгьех. 29.5-2. Покажите, что при выполнении процедурой 1н1т1Аш2е Я~мееех основного цикла процедуры 31М~Ч.ЕХ никогда не возвращается сообщение "неограниченна". 29.5-3. Предположим, что нам дана задача линейного программирования в стандартной форме Ь, и для обеих задач, прямой и двойственной, базисные решения, связанные с начальными каноническими формами, являются допустимыми.
Покажите, что оптимальное целевое значение задачи Ь равно О. 29.5-4. Предположим, что в задачу линейного программирования разрешено включать строгие неравенства. Покажите, что в этом случае основная теорема линейного программирования не выполняется. 29.5-5. Решите следующую задачу линейного программирования с помощью пРопеДУРы Б1МИ.ЕХ: Часть Ч11. Избранные темы 922 Максимизировать ж1 + Зхз при условиях х1 + хз < 1 — 2х1 — 2хз < — 6 — х1+ 4хз < 2 хд,хз Э 0 29.5-6.
Решите задачу линейного программирования (29.б)-(29.10). 29.5-7. Рассмотрим задачу линейного программирования с одной переменной, которую назовем Р: Максимизировать ~х при условиях гх < в х)0 где г, з, г — произвольные действительные числа. Пусть 27 — задача, двойственная Р. При каких значениях т, в, и ~ можно утверждать, что: а) обе задачи Р и Р имеют оптимальные решения с конечными целевыми значениями; б) является разрешимой, а Р— неразрешимой; в) является разрешимой, а Р— неразрешимой; г) ни одна из задач Р и Р не является разрешимой. Задачи 29-1. Разрешимость линейных неравенств Пусть задано множество т линейных неравенств с п переменными хы хз, ..., х„.
В задаче о разрешимости линейных неравенств требуется ответить, существует ли набор значений переменных, удовлетворяющий одновременно всем неравенствам. а) Покажите, что для решения задачи о разрешимости системы линейных неравенств можно использовать алгоритм решения задачи линейного программирования. Число переменных и ограничений, используемых в задаче линейного программирования, должно полиномиально зависеть от и и гп. Глава 29. Линейное программирование 923 б) Покажите, что алгоритм решения задачи о разрешимости системы линейных неравенств можно использовать для решения задачи линейного программирования. Число переменных и линейных неравенств, используемых в задаче о разрешимости системы линейных неравенств, должно полиномиально зависеть от числа переменных и и числа ограничений т задачи линейного программирования.
29-2. Дополняющая нежесткость (сошр!ешепгагу з1асКпеаа) Дополняющая нежесткость характеризует связь между значениями переменных прямой задачи и ограничениями двойственной задачи, а также между значениями переменных двойственной задачи и ограничениями прямой задачи. Пусть х — допустимое решение прямой задачи линейного программирования (29.16К29.18), а у — допустимое решение двойственной задачи (29.86)-(29.88). Принцип дополняющей нежесткости гласит, что следующие условия являются необходимыми и достаточными условиями оптимальности х и у: т Е а,"у; = с или х = 0 для 1 = 1, 2,..., п 1=1 и раух. = 61 или у; = 0 для(=1,2,...,т. 1=1 а) Убедитесь, что принцип дополняющей нежесткости справедлив для задачи линейного программирования (29.56)-(29.60).
б) Докажите, что принцип дополняющей нежесткости справедлив для любой прямой и соответствующей ей двойственной задачи. в) Докажите, что допустимое решение х прямой задачи линейного программирования (29.16)-(29.18) является оптимальным тогда и только тогда, когда существуют значения у = (у1, уз, ., у ), такие что: 1) у является допустимым решением двойственной задачи линейного программирования (29.86)-(29.88), 2) 2 ~ а; у; = с, когда х.
> О, и 3) у,=О,когда~" а,х (Ь,. 29-3. Целочисленное линейное программирование Задача иелочисленного линеиного программирования — это задача линейного программированиясдополнительнымограничением,состоящим в том, что переменные х должны принимать целые значения. В упражнении 34.5-3 показывается, что даже определение того, имеет ли задача Часть Ч11. Избранные темы 924 целочисленного линейного программирования допустимые решения, является ХР-полной задачей; это значит, что вряд ли существует полиномиальный по времени алгоритм решения данной задачи. а) Покажите, что для задач целочисленного линейного программирования характерна слабая двойственность (лемма 29.8).
б) Покажите, что задачи целочисленного линейного программирования не всегда характеризуются двойственностью (описанной в теореме 29.10). в) Пусть задана прямая задача линейного программирования в стандартной форме, и пусть Р— оптимальное целевое значение прямой задачи, Р— оптимальное целевое значение ее двойственной задачи, 1Р— оптимальное целевое значение целочисленной версии прямой задачи (т.е. прямой задачи с тем дополнительным ограничением, что переменные принимают целые значения), а 1Р— оптимальное целевое значение целочисленной версии двойственной задачи. Исходя из предположения, что и прямая, и двойственная целочисленные задачи разрешимы и ограниченны, покажите, что 1Р < Р = Р < 1Р.
29-4. Лемма Фаркаша Пусть А — матрица размером т х и, а с — п-мерный вектор. Лемма Фаркаша (Раг)саз) гласит, что разрешима только одна из систем Ах < О, с х>0 ,4ту = с, р>0, где х — п-мерный вектор, а у — пз-мерный вектор. Докажите эту лемму. Заключительные замечания В данной главе мы только приступили к изучению обширной области линейного программирования. Множество книг посвящено исключительно линейному программированию. Среди них Чватал (СЬча~а1) [62), Гасе (Оавз) [1111, Карлов (Каг1ой) [17Ц, Шрайвер (БсЬг1)чег) [266) и Вандербей (Чапс1егЬе1) [304]. Во многих других книгах подробно линейное программирование рассматривается наряду с другими вопросами (см., например, Пападимитриу (Рарайш)ибоя), Штейглиц (Бге18! 1гг) [2371 и Ахуя (АЬц)а), Магнанти (Майпапй), Орлин (Ог1ш) [7)).
Изложение в данной главе построено на подходе, предложенном Чваталом (СЬча~а!). Глава 29. Линейное программирование 925 Симплекс-алгоритм для задач линейного программирования был открыт Данцигом (О. Оапийй) в 1947 году. Немного позже было обнаружено, что множество задач из различных областей деятельности можно сформулировать в виде задач линейного программирования и решить с помошью симплекс-алгоритма. Осознание этого факта привело к стремительному росту использования линейного программирования и его алгоритмов. Различные варианты симплекс-алгоритма остаются наиболее популярными методами решения задач линейного программирования. Эта история описана во многих работах, например, в примечаниях к [62] и [171].
Эллипсоидный алгоритм, предложенный Л. Г. Хачияном в 1979 году, явился первым алгоритмом решения задач линейного программирования с полиномиальным временем выполнения. Он был основан на более ранних работах Н.З. Шора, Д.Б. Юдина и А.С. Немировского. Использование эллипсоидного алгоритма для решения разнообразных задач комбинаторной оптимизации описано в работе Гретшеля (ОгбгзсЬе!), Ловаса (Еочазх) и Шрайвера [134].
Однако на сегодняшний день эллипсоидный алгоритм в практическом применении не может конкурировать с симплекс-алгоритмом. В работе Кармаркара (Каггпагкаг) [172] содержится описание предложенного им алгоритма внутренней точки. Многие его последователи разработали свои алгоритмы внутренней точки. Хороший обзор этих алгоритмов можно найти в статье Гольдфарба (Оо!б(агЬ) и Тодда (То<Ы) [122] и в книге Е (Уе) [319].
Анализ симплекс-алгоритма относится к сфере активных исследований. Кли (К1ее) и Минти (Мш1у) построили пример, в котором симплекс-алгоритм выполняет 2" — 1 итераций. На практике симплекс-алгоритм работает очень эффективно, и многие исследователи пытались найти теоретическое обоснование этому эмпирическому наблюдению. Исследования, начатые Боргвардтом (Вогнан!!) и продолженные многими другими, показывают, что при определенных вероятностных предположениях об исходных данных симплекс-алгоритм сходится за ожидаемое полиномиальное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
