Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 54
Текст из файла (страница 54)
Для Л= 1 ) ††'1 ) = (а1) (.Х) Г1Л и ~ — ) = 1. Подставляя в уравнение (8) выражение для х иэ (41), ПОЛУЧИЛ1 г = (ао)+ 'Я (аг) ( — х,') — (ае+ ~ а1( — х; ')) = — )е — ~ ~1 ( — х). (9) Полученное уравнение есть не что иное, как отсечение Гоыори, полученное в $13.1. Для Л) 1 имеем ~ — ~ =0') и уравнение (8)~ Г1- . Ь.~= ' приобретает вид 14.1. ПОЛНОСТЬЮ ЦВЛОЧИСЛЕННЫИ АЛГОРИТМ зоз Ш а г 2.
Выбрать )о > О (правило выбора будет описано дальше) и написать внизу таблицы дополнительную строку Эта строка выбирается в качестве ведущей. Ш а г 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1. Донаеательстео конечности. Доказательство конечности проводится в предположении, что существует нижняя граница хо целевой функции хо.
Использование двойственного симплекс- метода гарантирует выполнение условия со1 ~ оо1+1 о о Если аоо уменьшается, то уменьшается па целое число, поскольку все числа остаются целыми, и, следовательно, через конечное число шагов аоо станет меньше хо. Если алгоритм бесконечен, то аоо Дол1кно оставатьсЯ неизменным ДлЯ всех 1 > 8о. РассмотРим тогда компоненту ам столбца ао.
Если а,о уменьшается, то на целое число. Когда а1о становится отрицательным, первая строка доля1па быть выбрана в качестве производящей. Если а11 > О для всех у, то задача неразрешима. Если же аы ( О для некоторого у, то в дополнительной строке 1'=! ~'„" ) +о ) (О и ~~ — н1= — 1 по крайней мере для одного у. (ПоследА нее гарантируется правилом выбора Х.) Итерация с выбранной ведущей строкой строго увеличит ам. Поскольку а' Р-а'+', а1+о' должно уменьшиться, что противоречит предполо1кению о неизменности Соо для 1'- оо.
Поэтому а,о (если алгоритм бесконечен) должно стать постоянным для всех е>о„где о1>оо. Аналогичные рассуждения мохоно провести и для второй, третьей и т. д. компонент вектора ао. Таким образом, после конечного числа шагов все аоо (1 = 1, ..., п+ т) станут неотрицательными целыми. ° Теперь опишем правило выбора Х в шаге 2 полностью целочисленного алгоритма. Пусть производящая строка имеет вид х=ао+ Я аз( — х;) и дополнительная строка е = ( ~ ) т ~~~~ ( ~ 1 ( — хт). 304 14. полнОстью целочисленный АВГОРитм Для любого аз(0 всегда моягно выбрать Л достаточно большим, чтобы [ —.' 1 = — 1.
Согласно лексикографическому двойственнок1у А 1 симплекс-методу, ведущий столбец а, выбирается по правилу ! — а,~=пик~ — ау~ (ау(0). Поскольку [а,!Л)== — 1 и [аг/Л) — отрицательные целые, т. е. — 1, — 2, ..., — рн имеем а, а1 аг (11) Таким образом, а, должен быть лексикографнчески мипимальным столбцом.
Последнее означает, что среди всевозможных столбцов (с а,г ( 0) ведущий столбец должен быть лексикографически минимальным вне зависимости от того, какое значение Л выбирается. Теперь рассмотрим дза значения Л, при каждом из которых выполпЯетсЯ Условие [а,(Л1) = — 1 и [а,/Лз) = — 1. Столбец ае изменяется следующим образом: Следовательно, чем меньн1е Л, тем сильнее лексикографически уменьшится нулевой столбец.
Значение Л следует выбирать так, чтобы, во-первых, ведущий элемент стал равным — 1 н, во-вторых, чтобы Л давало максимальное уменьшение столбцу ае. Правило формулируется следующим образом. Ш а г О. Пусть строка с номером о является производящей. Ш а г 1. Пусть а, — лексикографически минимальный столбец среди столбцов с агу ( О.
Шаг 2. Для каждого а„(0 пусть р; — наибольшее целое, такое, что а~ (— аг ру Шаг 3. Пусть ~ 11[=[гн а Л1= — — ' (стРока и — ЛРО- изводящая). Тогда а1 8 ~ [ ф [ 1) Минимум берется в лексикографическом смысле.— Прим, иерее. 44.!. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕНИЫИ АЛГОРИТМ 305 Ш а г 4. Полон«ить Л = шах Л! для а„г(0. ! Правило выбора Л, описанное выше, позволяет сделать ведущий элемент равным — 1, при этом будет сохраняться двойственная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться.
Следует заметить, что отсечопие Гомори не является самым «сильным» возможным неравенством. Оно так!Ее мо»кет быть «сильнее» или «слабее» самого производящего неравенства. Например, пусть производящей строкой будет х = — 4 — 3 ( — х,) — 5 ( — х»). (12) Если использовать Л = 2, получим отсечение г = — — 2 — 2 ( — х!) — 3 ( — х») )~ О. (13) Для Л = 3 имеем г =, —,2 — 1 ( — х,) — 2 ( — х») ) О. Для Л =- 4 г = — 1 — 1 ( — х,) — 2 ( — х») ~ )О. (14) (15) х.=а + ,'~~ а/( — х!)+,~„а,'( — х!).
(18) а <О а4>0 / Чем больше воличина Л, тем меньше абсолютная величина коэффициентов отсечения. Естествеш»о, что мы хотели бы иметь абсолютную величину [а»/Л) большой, а абсолютные величины [а//Л)— малыми. Если значение Л (полученное по приведенному выше правилу) может быть увеличено так, чтобы значения [а4/Л[ и [а»/Л[ не изменялись, то используется большее значение для Л. Тем самым по возможности уменьшится абсолютная величина [а//Л[ для некоторых /, и отсечение станет сильнее.
Например, пусть целевая функция имеет вид 'х, = 20 — х, — 2хг — Зх, — х„ и производящая строка х = — 20 + ( — 7) ( — х,) + ( — 8) ( — х») + ( — 15) ( — х») + 18 ( — х4). 20 т,хт Как видно, неравенство (14) сильнее, чем (12), (12) сильнее, чем (13), а (13) силы!ее, чем (15). Другое замечание касается того, что если величина Л, получаемая указанным выше способом, может быть увеличена так, чтобы [а»/Л] и [а4/Л) (а/ ) 0) оставались без изменения, то отсечение Гомори можно усилить, несмотря па то, что нулевой столбец уменьшится па ту же величину. Выпишем производящую строку 1О. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ Используя описанную выше процедуру выбора )о, получим Х = 7.
Соответствующее отсечение г =- — 3 + х, + 2х, + Зхо — 2хо «~ О. Если использовать Х = 9 вместо Л = 7, получим отсечение го = — 3+х,+х,+2хо — 2хо«0, являющееся более'сильным (см. (214!). Интересная особенность полностью целочисленного алгоритма состоит в том, что для его использования пе обязательно требовать целпкисленности всех апп Пусть задача целочисленного программирования имеет вид максимизировать хо — — аоо — Х суху при условиях х„т1 = ам — ~~„' амху > 0 (1= 1, ..., т), У=1 ' ху>0 (у=1, ° ., и), где аоо и су — целые, а,о н аы могут быть произвольными действительными числами, Таблица 14.1 содержит в первых и + 1 строках только целые числа. Таблица Уб.у Х1 ХО .
Х» Х1 Хо *»+1 Выпнупем произвольную производящую строку (опуская обозначение строки) х = ао+ ~~ ау ( — ху). Вне зависимости от того, являются ли ао и а. целыми или действительными, коэффициенты отсечения ~ 1О ~ ) С~~ ~ ау ~ ( 14,1. ПОЛПОСТЬЮ ЦЕЛОЧИОЛЕННЫИ АЛГОРИТМ ЗОУ Полноотью целочисленный алгоритм Цинличеений алгоритм В исходной таблице агу могут быть действительныыи (ае — долгкны быть целыми) В походкой таблице все агт цело- чнслекные Если ам †цел и исходной таблице, то ам остается целыи в и по- следующих аг ж 0(глоб)) в текущей таблице. На протяжении всех вычислений используется дзойетиенный симп- лекс-метод Для получепзя оптимума ЛП используется прямой или двойственный симплекс-метод. Затем используетоя двойстиенвый симплекс-метод СтрОКао ИядЕКСОМ1(1 тз О) СтаНОВИтея производящей, если а;о — отрица- тельное Строка с индексом 1 становится производящей, если а;о †нецел Ведущей строкой является Ведущей строкой является = — 1.— ~ 6 ( — *,') 0<(о<(, 0<Уу<т т= ~ " ~+ Я " 1( — т') ао<0, аглл0 Ведущий е-й столбец всегда лекси- когрзфкчески минимален с агу <О.
Ок определяется до того, клк отсе- чение получено Ведущий юй столбец определяется из условия т — а,< — а; уе /1 для всех 1 Если требуется сохрлнвть целочкс леэность таблицы, то добавляется одно неравенство. Одновременно можно добавлять не- сколько дополнительных неравенств, после чего использовать двойствен- ный симплекс-кетод всегда целые, а ведущий элемепт равен — 1.
В результате итерации с таким ведущим элементом первые и + 1 строк таблицы останутся целочисленными. Заметим, что переменная з — неотрицательная целая, В силу приведенных рассуждений доказательство конечности в данном случае мало чем отличается от описанного выше. Когда в пулевом столбце аео (1 = 1,..., и) становятся неотрицательными целыыи, а остальные элементы нулевого столбца — неотрицательными, то получается оптимальное решение. В последних главах были обсуждены два алгоритма целочисленного программирования, первый из которых называется циклическиы алгоритмом (Х = 1), а второй — полностью целочислепным (л, ) 1). В приведенной нитке таблице перечислены различия этих алгоритмов.
зов !З. ПОЛНОСТЬЮ ЦЕЛОЧНСЛЯННЫИ АЛГОРИТМ 14.2. Пример Пусть требуется найти майсимум хо =- — 10х, — 14хз — 21хз при условиях 2х,+ 8х, —,' 9х,+ 2хз+ 7хз > 14, 11хз -р 9хз > 121 бх, ! Зх,>10, х, х,, хз >0 (целые). табл. 14.2, где первый столбец лексико- н все элементы пронэводящей строки— Задачу моя1но свести в графически минимален отрицательны. Таблица И.г 1 — х, — хз — хз хо х$ хз хз л — 11ровзаодяшая строка хз А.= 7!2 14 г14л р,=1, 10« —, р,=-~ — 1О'~=.1, лз 2 2 7 7 7.,= — =.2, 2з= — =2, 2з= — =' —, Лз Кз , Кз 7т 7 7,=шах(2, 2, — ) = —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
