Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 65
Текст из файла (страница 65)
Пусть 1=- Г 1ой М, 1, где М, определяется так же, как в теореме 13.5. Поскольку нас интересуют целые числа между О и Мю можно заменить каждую переменную х) на ~', „хп21, где переменные хл принимают теперь значения О и 1. Любое решение задачи ЦЛП в указанных пределах имеет единственное двоичное представление с не более чем 1 двоичными разрядами, и поэтому оно однозначно соответствует множеству переменных х)о Таким образом, исходная задача ЦЛП эквивалентна получаемой задаче НОЛП.
Кроме того, нетрудно понять, что если ~ — размер исходной ЦЛП, то размер этой НОЛП не превосходит 0(М)=0((з), Теорема доказана. ь) Однако мы скоро увидим, что, по всей вероятности, ии для одной пз этих задач не существует полиномиального алгоритма. Задачи 1а. Приведите контрпример, показывающий, что теорема, обратная к творе. ме 13,1, неверна. 2* (ЧП). Докажите теорему, обратную к теореме 13.2. 3 !ЧИ. Покажите, что если любая из матриц А, Аг, — А, (А)А) или (А)1) вполне унимодулярна, то все зги матрицы вполне унимодулярны. 4*. Покажите, что если существует полиномиальный алгоритм для задачи ЦЛП, то существует полиномиальный алгоритм для задачи смешанного ЦЛП.
(Указание: см. равд. 8.7.1.) 334 Гл. 73. Целочисленное линейное программирование 5. Покажите, что любую индивидуальную задачу о выполнимости можно за палиномиальное время преобразовать в эквивалентную индивидуальную задачу, в которой все дизъюнкты содержат более одного литерала 8. Обобщите случай А в примере 13.3, показав, как использовать целачислен. ные переменные для задания целевой функции, представленной иа рис. 13,3(б). 7.
Покажите, что отбрасывание случая г=О в уравнении 13.1(б) оправданно. 8. Покажите, что матрица ограничений в аадаче о потоке минимальной стоимости вполне унимодулярна 9. Рассмотрим задачу целочисленного линейного программирования игах е'х, Ах~Ь, х) 0 целочисленно, где А, Ь и с составлены из лоложиглельных целых чисел. Пусть ЛП вЂ” это задача линейного программирования, полученная отбрасыванием требования, чтобы х было целочисленным. Обозначим решенис задачи ЦЛП через х„, а решение задачи ЛП через ха. Покажите, что [ хг [ — допустимое решение задачи ЦЛП и его стон.
'Стл масть не может отличаться от оптимальной более чем иа ллг гсг. Комментарии и ссылки [Со[ СоИшап Е. О., Зг., еб. Сошри1ег апд ЯоЪ-5Ьор 5сЬейиИпй ТЬеогу. Ыегч Уог1г; лойп )НИеу 8 5опь, 1976 Формулировки ЗК взяты из работ [Ррг[ Рап(ий О. В., Рийгегьоп О. К., ЯоЬпьоп 5. М. 5о1и(юп о1 а 1.агйе 5са!е ТгачеИпй 5а)еяпап РгоЫеш, ОК, 2 (1954), 393 — 410. [МТХ[ М)Иег С. Е., Тис)гег А )Н., ЕешИп К.
А, 1п)ейег Ргойгапип!пй Рогши1аИоп апй ТгачеИпй 5а1еьшап РгоЫешь, Л АСМ, 7 (1960), 326 — 329 Теоремы 13.1 н 1гн2 получены в [НК) НоИшап А 3., Кгиьйа) 3. В. 1п1ейга) Воипйагу Ро)пи о( Сопчех Ро)уЬебга, рр, 223 — 246 !п Е!пеаг !пейиаИ1!еь апй Ке)а(еб 5уь(ешь, ей Н %. КцЬп апб А )Н Тис1гег. Ргнсе(оп, и. 7: РЦпсе1оп Оп)чегю1у Ргеьь, 1956 1Имеется перевод: Гофман А Дж., Краскал Дж.
Б. Целочисленные граничные точки выпуклых многогранников.— В сбл Линейные неравенства и смежные вопросы.— Мл ИЛ, 1959.[ См также [НО! Не!по!1 А. Р., Эг., Оап1г)8 О. В. !п1ейга) Ех!геше Ро)п1ь, 5)АМ Кеч., 10, Ыо. 3 (Зи(у !968), 371 — 372. Теорема 13.3 взята из [НТ[ НеИег 1., Топтрййпз С. В. Ап Ех1епьюп о1 а ТЬеогегп о) Оап(г)8'ь, рр. 247— 252 гп [йшеаг !пейна! гИеь апб Ке1а1еб 5уь(ешь, ед. Н. ЪН.
Кпйп апй А. гН, Тис1гег. Рггпсе1оп. (4. Лл Рипсе1оп Оп!чегьиу Ргеьь, !956. [Имеется перевод; Хехлер И., Томпкиис Ч. Б. Обобщение одной теоремы Данцига.— В сбл Линейные неравевства и смежные вопросы.— Мл ИЛ, 1959.[ (См. также добавление к этой статье Гофмана А Дж, и Гейла Д,) Другие характеризацин вполне унимодуляриости приведены в работах [Са) Сапноп Р СЬагас1ег)гаЦоп о1 То1аИу Цп!шайи)аг Ма(г)сеь, Ргос. Агпег. Марш 5ос., 16 (1965), !068 — 1073. [Рад[ РадЬегй М. %, А Н!о1е оп Гпе То1а) Цп!шайи)агку о1 Ма1Нсеь, О!ьсге!е Ма(Ь., 14, Ыо. 3 (МагсЬ 1976), 273 — 278.
Коагментариа и ссьики 335 Пример !3.3 взят из статьи [Оа) Оап1з!д О. В. Оп йе Б~дп!1!гипсе о1 Бо!ч!пд Ыпеаг Ргодгащщ!пд РгоЫегпз гч!16 Бове !п1ерег Ьгаг!аЫез, Есопогпе1г!са (1960), 30 — 44. Теоремы 13.4 и 13.5 — из статьи [Ра) Рарад!гп!!г!оп С. П, Оп йеСогпр!ех!1у о1 1п(едег Ргодгащгп!пд, ЗАСМ (1981), ч. 26, Ь(о. 4, 765 — 768. В литературе существует множество других доказательств подобных результатов см., например: [ВТ) Вогез(з 1., ТгеуЬ!6 1..
В. Воппбз оп РозВ!че 1п!едга! Бо1пбопз 1о Ыпеаг О!ор)зап1!пе Еепаыопз, Ргос. Агпег. Май. Бос., 55 (1976), 299 — 304. !4 Алгоритм отсекаюи4ей плоскости для задач целочисленного линейного программирования 14.1 Отсечение Гомори пни с'х, Ах =Ь, хзО целочисленно, (14. 1) где А, Ь и с целочисленны. Назовем соответствующую задачу ЛП без ограничений на целочисленность пип с'х, Ах=Ь, х)0 (14.2) ослаблением задачи ЦЛП (14.1). Мы видели, что определенные задачи ЦЛП, а именно те, которые отвечают вполне унимодулярным матрицам ограничений, ненамного труднее решить, чем соответствующие задачи ЛП.
В таких задачах оптимальное базисное допустимое решение соответствующей задачи ЛП заведомо целочисленно. А что делать, если нет такого удобного свойства? К сожалению, на этот вопрос нет простого огвета. Как мы увидим в дальнейшем, общая задача ЦЛП, по-видимому, трудна по существу, и для нее разработано большое число алгоритмов. Не. которые из этих алгоритмов особенно эффективны для определенных классов задач целочисленного линейного программирования, но можно без опаски утверждать, что не известно общего алгоритма, который хорошо работал бы на практике для больших задач (скажем, с несколькими десятками ограничений и переменных), тогда как задачи ЛП такого размера легко решаются о помощью симплекс- алгоритма. Общие алгоритмы для задачи ЦЛП распадаются на две категории (в некоторой степени пересекающиеся); алгоритмы отсека~пи(ей плоскости, являющиеся развитием симплекс-алгоритма, и переборные алгоритмы, основанные на разумном переборе всех возможных решений.
Эта глава посвя:цена описанию простого алгоритма отсе. кающей плоскости, относящегося к классу методов, полезных для задач среднего размера и интересных с теоретической точки зрения. Чтобы зафиксировать обозначения, рассмотрим задачу ЦЛП в стандартной форме. 14Л. Отсечение Гомера Предположим, мы решили ослабление задачи ЦЛП, например, с помощью симплекс-алгоритма и нашли базисное допустимое решение х". Конечно, в общем случае х" не целочисленно. Однако естественно попытаться получить решение исходной задачи ЦЛП, округляя координаты решения т* до ближайших целых чисел.
Рис. 14.1 показывает, почему такой подход не работает: в действительности около х* может вообще не быть допустимых точек. Читателю не устимое ожестао задачи ЦЛП ание мости Окрутлеииое Рис. !4.1, Гипотетическая задача ЦЛП с оптимумом хе и ее ослабление с оптимумом х'. составит труда построить двумерные примеры, в которых непрерывный и дискретный оптимумы отстоят как угодно далеко друг от друга как по расстоянию на плоскости, так и по стоимости.
Отметим два простых, но полезных факта, Первое; если непрерывный оптимум х* — решение задачи ЛП вЂ” оказывается целочисленным, то он решает соответствующую задачу ЦЛП. Второе: стоимость с(х*) непрерывного оптимума является нижней границей для с(х") — стоимости дискретного оптимума. Л1ьт подошли теперь к основной идее алгоритма отсекающей плоскости. Если к задаче ЦЛГ1 добавить ограничение, не исключающее целочисленных допустимых точек, то решение не изменяется. Поэтому наша стратегия будет состоять в добавлении к задаче ЦЛП именно таких линейных ограничений по очереди до тех пор, пока решение соответствующей задачи ЛП, являющейся ослаблением исходной задачи, не будет целочисленным.
Г!оскольку мы не исключаем целочисленных допустимых точек, это окончательное решение ослаб. ленной задачи ЦЛП с добавленными ограничениями будет решением Гл, И, Алгоритм оглсекоющей ллогксегли исходной задачи ЦЛП. Описанный процесс проиллюстрирован на рис. 14,2. На рис. 14.2(а) представлены исходная задача ЦЛП и непрерывный оптимум х". На рис. 14 2(б) добавлено линейное ограничение, не исключающее никаких целочисленных допустимых точек, называемое атсекающей плоскостью (или просто отсеченттеле). Убывание стоимости «в (а) (б) (а) Рис. )4.2. Идлюсграиия алгоритма отсекающей плоскости. а) Непрерывный оптимум «" б) Новое х' после одного отсечения.
в) Решение исходной задачи 1(ЛП после двух отсечений. При этом отрезается часть допустимого множества, однако не теряются никакие целочисленные точки. Новый непрерывный оптимум сдвигается. как показано на рисунке. На рис. 14.2(в) представлен результа~ добавления еще одной отсекающей плоскости; в результате непрерывный оптимум оказывается целочисленным, и эта точка является решением исходной задачи ЦЛП. Опишем алгебраический метод порождения отсечений, принадлежащий Гоутори [Оо!!. Пусть дана индивидуальная задача ЦЛП.
Будем решать задачу ЛП, являющуюся ослаблением исходной задачи, с помощью прямого симплекс-алгоритма, н результате чего получим оптимальное непрерывное базисное допустимое решение х, соответствующее базису Ю. Типичное уравнение в заключительной таблице имеет вид (14.3) ха(1+ Х угу«у= рт ~ев для некоторого 1, 0(1(тп. (Можно положить хн„,= — г, где г— стоимость.) Удобно ввести следующее обозначение. Определение 14.1. Для данного действительного числа у целая часть числа у, обозначаемая ( р ), определяется как наибольшее целое число т), такое, что с) у. Д Пример 14.1.
~ 2, 7 ~ = 2, ( — 8, 1 1 = — 9, ( 0 ) О. е4.д Отсечение Гоноре 339 Переменная х в (14.3) должна быть неотрицательной, позтому 2с ~ у, ) х ~ Х уе х . (14.4) 'ев ,ев Тогда из (14.3) получаем ха и>+ Х ( УО ) хе~ усе (14.5) В задаче ЦЛП, которую мы пытаемся решить, х должно быть целочисленным, поэтому левая часть в (14.5) целочисленна. Следовательно, не нарушая неравенства, можно заменить правую часть ее целой частью, что приводит к неравенству хв,о+ ~г ) и, ~х ~~ ум~. (14.
6) ,ее Вычитая (14.6) из (14.3), получаем ~З ~(ии — ( уе ~)х )дее — ( у,е~. еев (14. 7) Положим )О -— ЧΠ— (.УО), (=0, ..., т. (14.8) Число ~О называется дробной часепью числа уц и удовлетворяет неравенствам 0~)О<1, (14.9) В результате получаем ограничение ~ )Ох ))е„ /е в (14.10) называемое отсечением Гомори, соответствующим производящей строке Наш план состоит в добавлении отсечения Гомори (14.10) к нашей таблице. Для сохранения базисного решения умножим (14.10) на — 1 и добавим переменную недостатка з, в результате чего полу- чим Х ! сух/+ ее" ев (14.11) Следующая лемма описывает результат добавления отсечения (14.11) к оптимальной таблице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
