Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 188
Текст из файла (страница 188)
Докажем, что в этом случае в строках 4 — 9 выполняется поиск допустимого решения задачи Б„„„с целевым значением, равным О. Согласно строкам 1-2, в данном случае Ь <О, Ь| < Ь; для всех ! б В. (29.115) В строке 7 выполняется одна операция замещения, в процессе которой из базиса выводится переменная х~ (вспомним, что ! = п + lс), стоящая в левой части уравнения с минимальным Ьо и вводится дополнительная переменная хо.
Покажем, что после такого замещения все элементы Ь являются неотрицательными, и, следовательно, данное базисное решение задачи Т „я является допустимым. Часть ЧП. Избранные темы 920 Обозначим через х базисное решение после вызова процедуры Р~чот, и пусть Ь и  — значения, возвращенные процедурой Р~чот.
Из леммы 29.1 следует, что Ь, — а;,Ь, если 1 е  — 1е), х;= з Ь~/а~е если 1 = е. (29.116) При вызове процедуры Рвот в строке 7 е = 0 и, в соответствии с (29.110), аю = а;* — — -1 для всех 1 е В. (29.117) (Заметим, что а;о — это коэффициент при хо в выражении (29.110), а не проти- воположное ему значение, поскольку задача Т „„находится в стандартной, а не канонической форме.) Поскольку 1 е В, то аге = — 1. Таким образом, Ь~/аге > 0 и, следовательно, х, > О. Для остальных базисных переменных получаем: х;=Ь,— аеЬе= (согласно (29.! 16)) (в соответствии со строкой 2 процедуры Рвот) (из (29.117) и аге = — 1) (из неравенства (29.115)) .
= Ь; — аде (Ь|/а~е) = =ь,— ь,> >О Основная теорема линейного программирования Мы завершим данную главу демонстрацией корректности работы процедуры 81мРьех. Произвольная задача линейного программирования или неразрешима, или неограниченна, или имеет оптимальное решение с конечным целевым значением, и в каждом случае процедура Б1МР1.ЕХ будет работать правильно. Теорема 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].
Во многих других книгах подробно линейное программирование рассматривается наряду с другими вопросами (см., например, Пападимитриу (Рарайш1пбои), Штейглиц (Бге18! 1гг) [2371 и Ахуя (АЬц)а), Магнанти (Майпапй), Орлин (Ог1ш) [7)). Изложение в данной главе построено на подходе, предложенном Чваталом (СЬча~а!). Глава 29. Линейное программирование 925 Симплекс-алгоритм для задач линейного программирования был открыт Данцигом (О. Оапийй) в 1947 году. Немного позже было обнаружено, что множество задач из различных областей деятельности можно сформулировать в виде задач линейного программирования и решить с помошью симплекс-алгоритма. Осознание этого факта привело к стремительному росту использования линейного программирования и его алгоритмов.
Различные варианты симплекс-алгоритма остаются наиболее популярными методами решения задач линейного программирования. Эта история описана во многих работах, например, в примечаниях к [62] и [171]. Эллипсоидный алгоритм, предложенный Л. Г. Хачияном в 1979 году, явился первым алгоритмом решения задач линейного программирования с полиномиальным временем выполнения. Он был основан на более ранних работах Н.З. Шора, Д.Б. Юдина и А.С. Немировского.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
