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