§ 2. Построение отсечений для выпуклых и некоторых невыпуклых задач

2.1. Пусть выпуклое замкнутое множество. Тогда в качестве плоскости, отсекающей точку от естественно взять одну из плоскостей, разделяющих

Так как — опорный план (вершина многогранника которому соответствует некоторый набор небазисных переменных небазисная для плана неравенство можно, разумеется, переписать и в небазисных переменных

2.2. Пусть невыпуклое замкнутое множество, причем дополнение до пространства выпуклое множество Надо «отсечь» от точку причем опорный план многогранника — небазисная переменная для плана Обозначим замыкание множества через — это также выпуклое множество.

Рассмотрим разложение переменных по небазисным переменным

Здесь

Рассмотрим конус задаваемый условием (2.2) и условием неотрицательности небазисных переменных (2.3)

Вершиной конуса является точка (или, что то же самое, ). Ребро конуса К задается условиями (2.2), (2.3) и дополнительным условием

Найдем точку пересечения ребра с общей границей множеств Точка Через точки йроведем плоскость

Вершина конуса и удовлетворяет условию

Каждую точку X конуса удовлетворяющую условию

можно представить в виде выпуклой линейной комбинации точек и точки X, а так как то

Итак, вершина X конуса К и все его точки X, удовлетворяющие условию (2.5), принадлежат множеству причем все точки X (в том числе вершина X) конуса К, удовлетворяющие (2.5) как строгому неравенству, принадлежат но не принадлежат общей границе так что для них

Следовательно, доказана следующая

Теорема 2.1. Пусть: 1) - вершина многогранника - небазисная переменная, соответствующая замкнутое множество. 3) дополнение до выпуклое множество. 5) точка пересечения ребра многогранника с общей границей множеств (см. выше).

Тогда отсечение (отсекающее X от можно записать в виде

Замечание 2.1, Если множество не ограничено и некоторое ребро не пересекается с общей границей то следует положить (условно)

Геометрическая иллюстрация отсечения (при условиях теоремы 2.1) дана на рис. 8.2.1.

2.3. Отсечения (2.1) (для выпуклого и (2.6) — (2.7) (для невыпуклого можно применить непосредственно при использовании, например, второго алгоритма Гомори. Если же для решения вспомогательных задач пользоваться первым или третьим алгоритмом Гомори, то непосредственному применению этих отсечений мешает то обстоятельство, что переменная (из (2.1) и на планах задачи не обязана быть целочисленной. Обойти эту трудность помогает теорема 2.1 из гл. 7, основываясь на которой можно всегда по отсечению

построить отсечение

Рис. 8.2.1.

Здесь

Для первого алгоритма Гомори этого достаточно, т. е. при построении можно взять любое К. Для третьего же алгоритма Гомори мало добиться целочисленности всех коэффициентов отсечения, надо еще, чтобы направляющий элемент был равен Это делается так же, как при обычном применении третьего алгоритма Гомори (более подробное изложение дано в § 3).