Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 53
Текст из файла (страница 53)
Кроме того, выше было доказано, что неравенство (4) содержит только целочисленные коэффициенты, гл. сз, пикличзскии ллгогнтм 293 а в левой части неравенства (5) пет переменных, т. е. левая часть есть целое число. Таким образом, левая часть неравенства (5) есть неотрицательное целое число. Р в с.
13.4. Р в с. 13.3. Рассмотрев правую часть неравенства (5), можно увидеть, что коэффициенты при переменных представляют собой либо ~, ~ыаы, либо Х 1паы — 1ы. ЙУ 3ЕУ Рассмотрим особый случай, когда все коэффициенты исходной таблицы неотрицателькы. В этом случае ~3 ~~ыа~з — неотрицатель- РЗУ ное число, и, более того, (поскольку было доказано, что все коэффициенты долясны быть целыми) неотрицательное целое, т.
е. О, 1, 2,.... Коэффипиенты ~ ~пал,— ~;, могут содержать отри- зеу цательнУю часть ( — Тп) ( — 1( — Тм(О), следовательно, ~ ~Tпазд — ~м ) — 1. Поскольку левая часть. этого неравенства представляет собой коэффициент при некоторой переменной хю она должна быть целым числом. Поэтому вырахсепие ~ Тыла, — ~п есть неотрицательное целое, т. е.
О, 1, 2.... Проведенные рассуждения относились к первому дополнительному неравенству, однако это неравенство можно рассматривать как часть исходной задачи и тогда применить доказательство ко второму дополнительному неравенству и т. д. 13.1. СВОЙСТВА ДОПОЛНИТЕЛЬНЫХ НЕРАВЕНСТВ 299 На основании приведенных рассуждений можно сделать следующий вывод: если все коэффициенты в исходной таблице неотрицательные целые, то коэффициенты отсечений Гомори, выраженных через исходные пебазисные переменные, есть также неотрицательные целые числа. Пусть получено оптимальное решение линейной программы и 1т — небазисные переменные для текущего базиса.
Из условия двойственной допустимости следует, что в уравнении хо = а1В+ ~ по~ ( — 89) коэффициенты ао1~ )О. Кроме того, 1~ - О. Если рассмотреть от-пространство, как показано на рис. 13.3, то целевая функция является опорной гиперплоскостью положительного ортанта, достигающей ооаьсимума в начале координат (~у = 0). Любая точка внутри положительного ортанта соответствует положительным значениям Гп а значкт, уменьшает значение хо. Гиперплоскость 8= — 10+1 У 19=0 прн ~; ) 0 является гиперплоскостью, рассекающей положительный ортант на две части, одной из которых принадлежит начало координат. Эта гиперплоскость параллельна гиперплоскости о' = ~ ~;1П которая является опорной к положительному ортанту в начале координат.
Было показано, что о представляет собой целочисленную комбинацию исходных переменных: г=п'+п лохо= — 1о+ ~ Я;. (ба) Текущее решение 1; = 0 дает целочисленной форме и' + ~ л,х; нецелое значение — 1о. Поэтому опорная гиперплоскость г' = =- ~ ~ф; = 0 моноет быть перемещена внутрь положительного Ортанта. Можно взглянуть на отсекающую гиперплоскость и по-другому, рассмотрев пространство 8~ (у = 1,..., и) и г в качестве (и + 1)-й координаты, как показано на рис.
13.4. Тогда уравнение (ба) описывает гиперплоскость Н1 в пространстве о; Щ о. Уравнение О= — 1о+Х1А (бб) задает пересечение гиперплоскости Н1 с г = О. Гиперплоскость Но, являющаяся этим пересечением, отсекает начало координат в 1ппространстве. После того как отсечено начало координат, представляющее собой оптимальную вершину, вводится другая координатная система.
Эта система использует новые небазисные переменные в качестве координатных осей, а оптимальное ревтение задачи линейного программирования лежит в начале новых координат. ГЛАВА 14 ПОЛНОСТЫО ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ 14.1. Полностью целочисленный алгоритм (Гоморн 1801) хе= ею+ ~ аее ( — хт) при условиях х~ — — — 1( — х,)) О, х„= — 1( — х„)>0, х„ы = а„ы, е+ ~~~ а„+ь т ( — х~) >~ О, 1=~ п х т =а;м,з+ ~~~~ а„,„„т( — хт)>0.
1=~ Условия (1) могут быть записаны как х' = А' ( — х„'). (2) В настоящем параграфе будет описан другой алгоритм для рептения задач целочисленного программирования. Этот алгоритм назван полностью целочисленным, потому что если исходная таблица состоит из целочисленных элементов, то все таблицы, получающиеся в процессе работы алгоритма, содержат только целочисленные элеыентьь Подобпо двойственному симплекс-методу, алгоритм начинает работать с двойственно допустимой таблицы.
Если аю (1 = 1,..., и + т) — неотрицательные целые, то задача решена. Если для какой-нибудь строки аю ( О, то составляется новое уравнение и записывается внизу таблицы. Эта строка затем слунпгт ведущей. После етого используется двойственный симплекс-метод. Все элементы дополнительной строки должны быть целыми числами, а ведущий элемент равен — 1. Введенная таким образом ведущая строка сохранит таблицу целочисленной. Заметим, что в предыдущем алгоритме в качестве производящей строки выбиралась строка с пецелым а;,. В данном случае производящей строкой становится строка с отрицательным апг Пусть дана задача целочисленного линейного программирования: максимизировать 11.!.
ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ ЗО1 у=Я)+гю (3) где О ( гл с. ), (ГР— неотрицательный остаток от деления нацело у на ).). В частности, 1 = (1М Х + г. Поэтому если Х ) 1, то И!Л) =О иг — — 1. Коли 1=1, то (1/Х) =1 иг=-О. Так же как и ранее, вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (1).
Рассмотрим некоторое уравнение в л-таблице (опуская индекс строки) с аз~о: 1 х= аз+ ~~~~а~( — хл), (4) где х — соответствующая компонента вектора х, а х; — текущие 1 небазисные переменные. Можно выразить х, а, и а1, используя введенное вьине представление (3): х= х х1=х ([ —,'1Х+г) л а,=[ — ')Х+гз (у=О, 1, ..., Л). (5) (6) Подставив выражения (5) и (6) в (4) и переставив члены, получим лл П ~ глх!+гх=гл+Х([ Ал )+ ~~Р~ [+~( — х!)+ [ — ]( — х)) . (7) э=1 3=1 Поскольку г; ~ О, г ) )О и на переменные х и хл наложено требование неотрицательиости, левая часть уравнения (7) всегда неотрицательна.
Рассмотрим выражение в правой части, заключопное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требованию целочисленности. Поэтому все выражение в скобках доллкво быть целым. Обозначим его через г, т. е. г = [ — 1 + г, [ — 1 ( — х,'. ) + [ —, ) ( — х).
1=1 (6) Предположим, что для 1 = О (т. е. для исходной таблицы) все аы — целые и столбцы пт Ц = 1,..., и) — лексикографически положительны. Тогда все столбцы на протяжении вычислений остаются лексикографическн положитольными. Прежде чем наложить способ получения дополнительного Ограничения из производящей строки, введем новое представление чисел. Пусть Ы обозначает наибольшее целое число, не превосходящее х.
Для любого числа у (положнтельного или отрицательного) и положительного Х можно записать 302 11. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫИ АЛГОРИТМ в ~~~о~ ( т;~ Ге1~( (101 1=1 Уравнение (10) должно выполняться для любого допустимого целочисленного решения задачи (1). Заметим, что если аз ~ О, то [ае/Л) (0 в уравнении (10), Поэтому уравнение (10) может использоваться в качестве ведущей строки в двойственном симплекс-методе. В частности, всегда можно выбрать Л достаточно большим, так чтобы ведущий элемент (а 1Л) в строке (10) стал равным — 1, что позволит сохранить целочисленпость таблицы. Выбор соответствующего Л будет влиять на скорость сходиыостн алгоритма.
Прежде всего опишем сам алгоритм. В качестве начального необходимо взять двойственно допустимое решение, которое можно получить добавлением ограничения х„+ ч1 — — М вЂ” х, —... ... — х„)~ О, где М вЂ” достаточно большая константа, и проведением одной итерации с добавленной строкой и с лексикографически минимальным столбцом, взятыми в качестве ведущих Алгоритм состоит из следующих шагов.
Ш а г О. Начать с двойственно допустимой матрицы А' в уравпении (2), элементы которой — целые числа (как будет видно из дальнейшего, матрица А' может содержать и нецелые элементы). Ш а г 1. Среди строк с а1е (0 (1 = 1,..., и + т) выбрать строку с наименьшим значением 1; эта строка станет производящей. (Если аш ) 0 (1 = 1,..., и + т), то задача решена.у ') Если Х ) 1, то для получения отсечения (10) нз (4) требуется только неотрнцательность левов части уравнения (4). Следовательно, любая положвтельная авпейная комбинация строк таблицы может слупить провзводящей строкой.
Целочисленная слабая переменная г является неотрицательной. Действительно, если бы г было отрицательным, т. е. принимало значения — 1, — 2, ..., То умножение на Л (Л ) гз) сделало бы всю правую часть уравнения (7) отрицательной, в то время как левая часть пеотрицательна. Рассмотрим два случая Л= 1 и Л-» 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
