где (ry – неотрицательный остаток от деления нацело y на ). В частности, . Поэтому если , то и r = 1. Если , то и r = 0.
Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (12). Рассмотрим некоторое уравнение в t – таблице (опуская индекс строки) с a0
|
где x – соответствующая компонента вектора , а - текущие небазисные переменные. Можно выразить x, a0 и aj, используя введенное выше представление (14):
|
|
Подставив выражения (16) и (17) в (15) и переставив члены, получим:
|
Поскольку , и на переменные x и наложено требование неотрицательности, левая часть уравнения (18) всегда неотрицательна. Рассмотрим выражение в правой части, заключенное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требованию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т.е.:
|
Целочисленная слабая переменная s является неотрицательной. Действительно, если бы s было отрицательным, т.е. принимало бы значения -1, -2, …, то умножение на сделало бы всю правую часть уравнения (18) отрицательной, в то время как левая часть неотрицательна.
Рассмотрим два случая и . Для и . Подставляя в уравнение (19) выражение для x из (15), получим:
|
Полученное уравнение есть не что иное как отсечение Гомори. Для имеем и уравнение (19) приобретает вид:
|
Уравнение (21) должно выполняться для любого целочисленного решения задачи (12). Заметим, что если a0 в уравнении (21). Потому уравнение (21) может использоваться в качестве ведущей строки в симплекс-методе. В частности, всегда можно выбрать достаточно большим, так чтобы ведущий элемент в строке (21) стал равным –1, что позволит сохранить целочисленность таблицы. Выбор соответствующего будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве начального необходимо взять двойственно допустимое решение, которое можно получить добавлением ограничения xn+m+1=M – x1 - - … - xn 0, где M – достаточно большая константа, и проведением одной итерации с добавленной строкой и с лексикографически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов:
Шаг 0. Начать с двойственно допустимой матрицы A0 в уравнении (13), элементы которой – целые числа (матрица A0 может содержать и нецелые элементы, об этом см. [2], стр. 306).
Шаг 1. Среди строк с ai0i00 (i=1, …, n+m), то задача решена.)
Шаг 2. Выбрать (правило выбора будет описано дальше) и написать внизу таблицы дополнительную строку
Эта строка выбирается в качестве ведущей.
Шаг 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1.
Доказательство конечности алгоритма см. [2], стр. 303-304.
Правило выбора формулируется следующим образом.
Шаг 0. Пусть строка с номером v является производящей.
Шаг 1. Пусть - лексикографически минимальный столбец среди столбцов с avj
Шаг 2. Для каждого avj - наибольшее целое, такое, что (лексикографически меньше).
Шаг 3. Пусть , а (строка v - производящая). Тогда
.
Шаг 4. Положить для avj
Правило выбора , описанное выше, позволяет сделать ведущий элемент равным –1, при этом сохраняется двойственная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться.
Подробнее об алгоритме можно прочитать в [2], стр. 300.
2.2.2 Прямой алгоритм целочисленного программированияТермин “прямой”, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно “улучшаемых” решений. Каждой из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности. Одним из вероятных достоинств алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.
Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом, равным –1. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы.
Оказывается, можно аналогично модифицировать симплекс-метод таким образом, чтобы получить алгоритм, который сохраняет прямую допустимость и целочисленность таблиц. Для описания вычислительной процедуры рассмотрим следующую задачу целочисленного программирования:
максимизировать
|
при условиях
,
(целые) (k=1,…,n),
где a0j, aij и ai0 – целые числа и ai00.
|
где J – множество индексов небазисных переменных в (22), sk – новая (базисная) слабая переменная и - неопределенная (временно) положительная константа.
Заметим, что если положить = avs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,
Это означает, что прямая допустимость таблицы сохраниться, если использовать отсечение (23) в качестве ведущей строки. Во-вторых, , т.е. ведущий элемент равен 1 (если отсечение используется как ведущая строка). Легко удостовериться (путем исследования формул изменения базисных переменных), что преобразование симплексной таблицы с единичным ведущим элементом сохраняет целочисленность элементов симплексной таблицы.