5.2 Способ построения отсечений

Свойство метода отсечения быть или не быть конечным ре­шающим образом зависит от способа получения отсечений. При­ведем схему построения дополнительных ограничений, которая используется в излагаемых далее алгоритмах Гомори. В ее опи­сании посредством []г\ обозначается целая часть числа /г, т.е. наи­большее целое, не превосходящее /г.

Пусть линейная функция

принимает целые неотрицательные значения на множестве допу­стимых решений задачи (5.1)-(5.4) и К ф 0. Если К — целое, то неотрицательности £ не требуется. Тогда для любого ж, явля­ющегося допустимым решением задачи (5.1)-(5.4), имеют место следующие соотношения:

 

(5.5)

з

-\-J2j №3X3 = /гб?о,

 

 

(5.6)

з

 

(5.7)

з

 

 

3

Наконец, если

и = амо]-н^)-£ан-]-н^)

ж

(5.9)

з

то

и > 0 (5.10)

и целое.

 

Приведем некоторые пояснения к вышесказанному. При пере­ходе от (5.5') к (5.6) используется неотрицательность х^ и £. При этом в случае \К\ = К знак £ не имеет значения, так как первые слагаемые в (5.5') и (5.6) совпадают. Неравенство (5.8) получено из (5.7) путем исключения £ с использованием (5.5). Неравенство (5.10) эквивалентно (5.8). По поводу (5.11) достаточно заметить, что и представляет собой разность двух целых чисел, а именно, левой и правой части неравенства (5.7).

Таким образом, добавление условий (5.9)—(5.11) к ограничени­ям задачи (5.1)-(5.4) порождает задачу ЦЛП того же вида и экви­валентную исходной. К новой задаче ЦЛП, в свою очередь, может быть применен тот же самый способ порождения дополнительных ограничений. Построение указанных ограничений должно быть конкретизировано так, чтобы можно было получить в конечном счете задачу ЦЛП, ЛП-релаксация которой имела бы целочислен­ное оптимальное базисное решение (при условии, что исходная задача ЦЛП разрешима).

Решение возникающих в ходе такого процесса ЛП-релаксаций целесообразно проводить двойственным симплекс-методом. Это связано с тем, что очередная задача ЛП получается путем до­бавления некоторого ограничения после того как будет найде­но оптимальное решение предыдущей задачи. В этой ситуации не возникает каких-либо затруднений с нахождением начального двойственно допустимого базиса для новой задачи. При этом с целью обеспечения конечности процесса решения каждой из ЛП-релаксаций и, в конце концов, самой задачи ЦЛП нам придет­ся воспользоваться лексикографическим вариантом двойственно­го симплекс-метода.