Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Обычно в ограничения задачи (1) включаются а. тривиальные соотношения х} = —( —xj) (у = 1 , а задача в матричной

форме принимает вид

исходной таблицы. Задачу целочисленного программирования также можно записать в виде табл. 13.1.

Причины представления переменных в виде (—а^), (—х 2 ) , . . .

. . ., (—хп) — чисто исторические, но это стало обычной прак­ тикой в целочисленном программировании. Будем использовать а; (/ = 0 , 1 , . . ., га) для обозначения у-го столбца текущей таб­ лицы и a-ij (i = 0 , 1 , . . ., га + гаг; у — 0 , 1 , . . ., га) для обозна­

чения элемента i-й строки и у-го столбца таблицы. Предполагается, что все atj в исходной таблице целые. Следовательно, все слабые переменные xn+t, . . ., х п + т должны быть также неотрицатель­ ными целыми числами.

При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори [79]. Вначале задача целочислен­ ного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма ai0 ^ 0 (г = 1, . . .

. . ., га + гаг) и a0j ^ 0 (у = 1, . . ., га). (Для получения исходного двойственного допустимого решения введем дополнительное огра­ ничение xn+m+i = М — Xt — х 2 — . . . — хп 0, где М — до­ статочно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если ai0 ^ 0 и целые для всех г, то получено опти­

мальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если ai0 ^ 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е. ai0 < 0 для

г = га + гаг + 1. Затем используется двойственный симплексметод с целью сделать все ai0 ^ 0. Если ai0 получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока гаго (г = 1 , . . ., га, . . ., га + гаг) не станут все целыми и неотрица­

тельными.

Если после введения дополнительного ограничения текущая таблица перестает быть прямо допустимой, то текущее решение, представляющее собой вершину многогранника решений, не удо­ влетворяет этому дополнительному ограничению. Другими сло­ вами, дополнительное ограничение отсекает часть пространства решений. Если дополнительные ограничения не отсекают ни одной целочисленной точки пространства решений исходной задачи, то, вполне вероятно, после введения достаточного числа допол­ нительных ограничений вершины суженного множества решений будут целочисленными. Тогда, используя симплекс-метод, можно получить оптимальное целочисленное решение. Трудность состоит в систематическом получении дополнительных ограничений и дока­ зательстве конечности алгоритма.

Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таб­

где х° — вектор-столбец с га + гаг + 1 компонентами, А0 — матри­ ца размера (п + гаг + 1 ) X (га + 1 ) и (—х£) — вектор с компо­ нентами (1 , —Xj, . . ., —хп), представляющими собой текущие

небазисные переменные, взятые со знаком минус. Если в матрице А а0} > 0 '(/ = 1, . . ., га), а00 = 0 (mod 1) Д и ai0 > 0 (г = = 1 , . . ., га + гаг) — целые неотрицательные числа, то получено

оптимальное решение целочисленной задачи. Если aiQ не все целые, введем дополнительное ограничение. Рассмотрим такое уравнение из (3), в котором яго нецелое. Опуская индексы строки, имеем

где Xj в правой части — текущие небазисные переменные и а0 — нецелое. Поскольку требуется, чтобы х было целым, или х =

х) Символ (= ) означает «сравнимость». Два числа сравнимы по модулю 1, если они отличаются друг от друга на целое число.— П.ри,м. перее.

== 0 (mod 1 ), правая часть уравнения (4) также должна удовле­

творять условию

Это условие должно выполняться при любом допустимом цело­ численном решении. Поскольку требуется, чтобы Xj были целыми, можно алгебраически складывать с (5) отношения 0 == xj и также О = 1 J), тогда (5) примет вид

Всоотношении (7) / 0 — константа, меньшая единицы, и поскольку

^0 и Xj ^ 0, левая часть всегда положительна. Так как (7) — отношение сравнения по модулю 1 , левая часть может принимать

только значения вида / 0, /о + 1 » . . ., т. е.

Неравенство (8 ) можно представить в виде уравнения с помощью

введения неотрицательной целочисленной слабой переменной

Это уравнение можно приписать внизу таблицы и использовать

вкачестве ведущей строки. Таким образом, переменная s войдет

вбазис с отрицательным значением (—/ 0). После итерации слабая переменная s станет небазисной с нулевым значением. Ведущая строка превратится в тождество s = (—1 ) (—s) и может быть

исключена. Будем называть переменную s в уравнении (9) слабой переменной Гомори. Ниже будет обсуждено, что произойдет, если сохранять все дополнительные строки, соответствующие слабым

переменным Гомори.

Дадим доказательство конечности алгоритма. Доказательство будет проведено в предположении, что известна некоторая нижняя граница значения х0, т. е. если существует целочисленное решение, то оно больше, чем наперед заданная величина М (М может'быть достаточно большой по абсолютной величине отрицательной кон­ стантой). Такое предположение не слишком обременительно' и всегда выполняется, если выпуклое множество, определяемое условиями (2), ограничено. Сначала изложим сам алгоритм.

III а г 1. Решить задачу целочисленного программирования так, как если бы это была линейная программа, т. е. с помощью

Э Алгебраическое сложение отношений 0 = xj и 0 = 1 с (5) соответ­ ствует вращению и перемещению гиперплоскости, из которой было полу­ чено условие (5),

прямого или двойственного симплекс-метода. Если получено оптимальное решение задачи линейного программирования, то

а 1о > 0 (i = 1, . . т + п) и aoj > 0 (/ = 1, . . п). Требуется также, чтобы а* > 0 (у = 1 , . . ., п).

Ш а г 2. Если ai0 — все целые, то задача решена, и решение получено без использования дополнительных ограничений. В про­

тивном случае пусть а\о — первая нецелочисленная компонента в а01. Тогда l-я строка называется производящей строкой. Записать внизу таблицы уравнение

Уравнение (10) называется отсечением Гомори. Проделать шаг двойственного симплекс-метода, используя в качестве ведущей строки отсечение Гомори (10). При этом таблица останется двой­

ai0 на некотором шаге остается отрицательным, следующий шаг двойственного метода производится без введения отсечения Гомо­ ри. (Если а00 становится отрицательным, нулевая строка не выби­ рается в качестве производящей. Если а00 становится нецелым,

следует выбрать нулевую строку в качестве производящей.) Изменение элементов ац (i = 0, 1, . . ., п + т\ / = 0, . . .

. . ., п) в таблице за одну итерацию называется циклом. Для

является то, что а00 остается равным фиксированному значению, большему нижней границы, в то время как некоторое ai0 неогра­ ниченно уменьшается. Чтобы увидеть, как преодолеваются эти трудности, необходимо в деталях рассмотреть шаги итерации.

При доказательстве будет показано, что либо после конечного числа шагов все компоненты 0 -го столбца становятся неотрица­

тельными целыми, либо не существует целого решения. Если а00 остается постоянным для всех t ^ £„, то а*0 должно быть целым.

Предположим, что а$0—нецелое. Пусть а[0 —«оо+ /оо> гДе поо—

целое и 0 < /*, -< 1. Тогда 0-я строка становится производящей

итребуется ввести дополнительное ограничение

*= - / $ , - 2 / o i ( - 4 ) .

19 т. Х у