4.2. Метод ОТСЕКАющих ПЛОСКОСТЕЙ
Метод отсекающих плоскостей впервые разработан Р. Гомори в 1957-1958 гг. для задач линейного цілочисельного программирование (ЛЦП) [18; 27].
Для группы методов отсечения плоскостей характерна так называемая 'регуляризация' задачи, состоящая в погружении исходной несвязанной области допустимых решений (дискретных точек) в объемлющую ее непрерывную выпуклую область, т.е. во временном отбрасывании условий дискретности. Затем к получившейся регулярной задаче применяются стандартные методы оптимизации.
Если полученное в результате решение удовлетворяет отброшенному условию дискретности, то задача решена. В противном случае необходимо продолжить процесс решения.
Для задачи ЛЦП соответствующая идея 'регуляризации', положенная в основу метода отсекающих плоскостей, высказана Г. Данцигом.
Допустим необходимо решить задачу ЛЦП:
минимизировать 
(4.2.1)
при условиях
, (4.2.2)
, (4.2.3)
- целые числа, 
. (4.2.4)
Отбросив на определенное время условие целочисленности (4.2.4), найдем оптимальное решение. Если окажется, что он удовлетворяет также и условию целочисленности, то это решение является искомым. В противном случае нужно сформировать дополнительное ограничение, которому заведомо удовлетворяет любой целочисленный план, но не удовлетворяет найденный оптимальный нецелочисленный план. Такое ограничение называют 'правильным отсечением'. Геометрически правильное отсечение означает гиперплоскость, отсекающую от выпуклого многогранника соответствующей задачи ЛП некоторый многогранник, содержащий все целочисленные решения исходной задачи.
Далее к исходной системе ограничений задачи добавляют правильное отсечение и описанный процесс решения продолжают аналогично. Если правильное отсечение сформировано удовлетворительно, то можно полагать, что через несколько итераций будeт найдено решение задачи ЛЦП либо будет зафиксирована несовместность ее условий.
Рассмотрим задачу ЛП (4.2.1) - (4.2.3) в предположении, что все {aij}, {bi}, {cj} - целые числа и m < n.
Пусть {А1, А2, ., Аm} - линейно независимые векторы ограничений, образующие базис системы {А1, А2, ., Аn}. Очевидно, матрица Ax= { А1, А2, ., Аm} - не вырождена, и поэтому существует обратная к ней 
.
Умножив ограничения задачи 
на , получим
(4.2.5)
Это соотношение в развернутой форме записи имеет вид
Откуда
(4.2.6)
где 
- базисная переменная; 
- ее значение.
Соотношение (4.2.6) справедливо для любого решения, в том числе и оптимального.
Подставляя выражение (4.2.6) в (4.2.1), получим
(4.2.7)
Решим задачу ЛП (4.2.1) - (4.2.3) симплекс-методом или двойственным симплекс-методом. Допустим, что оптимальным оказался базис {А1, А2, ., Аm}. Элементы последней симплекс-таблицы обозначим через xij, причем 
, а столбец свободных членов - через [ ], 
.
Выберем один из них, например и, начиная с i-й строки, составим соотношения для дополнительного ограничения (правильного отсечения).
Обозначим через [xij] целую часть, а через gij = xij - [xij] - дробную часть числа xij, причем xij ³ [xij]. Очевидно, 0 ≤ gij < 1.
Пусть x = [xi] - некоторый оптимальный план задачи (4.2.1) - (4.2.3). Его компоненты связаны уравнением (4.2.6). Подставим xij = [xij] + gij в (4.2.6) и после несложных преобразований получим
(4.2.8)
Соотношение (4.2.8) справедливо для любого плана решаемой задачи. Допустим, что x - целочисленный план. Тогда, учитывая целочисленность левой части (4.2.8), получим 
,
где ξ - целое число, а 0 £ 
< 1, 0 £ gij < 1.
Теперь возможны два случая:
а) x ³ 1; б) x £ 0.
В первом случае, если допустить, что x ³ 1, то 
, откуда ³ 1, а это противоречит условию 0 £ < 1. Поэтому принимаем x £ 0, т.е. справедливо неравенство
(4.2.9)
Нецелочисленный план x не удовлетворяет неравенству (4.2.9), поскольку > 0, а левая часть неравенства (4.2.9) равна нулю, так как = 0, для всех небазисных компонент j = m +1, m +2, ., n... В то же время любой целочисленный план удовлетворяет (4.2.9) как строгому равенству, так как = 0 для всех i.
Итак, ограничение (4.2.9) является правильным отсечением. Его записывают в эквивалентной форме
(4.2.10)
или
(4.2.11)
и добавляют к исходной системе линейных ограничений задачи.
Переменные новой задачи таковы: {x1, x2, ., xn+1}... Ее условия уже разрешены относительно базисных переменных плана x = {x1, x2, ., xm} и новой переменной xn+1, и, следовательно, имеем псевдоплан с базисными компонентами:
xi= xi0, ; xn+1 = -gi0.
Симплекс-таблица данного псевдоплана образуется дописыванием к таблице, отвечающей найденному оптимальному плану x, строки с элементами
(4.2.12);
Одновременно к таблице добавляют единичный вектор Аn+1 такой, что 
.
К этому плану применяют двойственный симплекс-метод. На первой итерации из базиса обязательно выводят вектор, отвечающий переменной xn+1, так как в столбце ai0 таблицы имеется один отрицательный элемент xn+1 = - < 0.
Будем называть большой итерацией метода отсекающих плоскостей совокупность итераций алгоритма двойственного симплекс-метода, приводящих от псевдоплана с дробными компонентами к следующему оптимальному плану (не обязательно целочисленному).
В зависимости от исхода большой итерации различают следующие три случая:
1) в столбце 
все - целые числа, причем ³ 0. Это условие определяет оптимальность найденного плана;
2) получен новый план, где все ³ 0, но не все - целые числа. Тогда необходимо сформировать новое правильное отсечение и перейти к очередной большой итерации;
3) получен некоторый промежуточный псевдоплан, где имеется элемент < 0 такой, что xij ³ 0 для всех j = 1, 2, ., n... Это признак неразрешимости задачи.
Переменные 
, вводимые в задачу в начале каждой новой итерации, называются дополнительными, а переменные xj, 
- основными. Если дополнительная переменная является небазисной для некоторого промежуточного псевдоплана, то уравнение = 0 входит в совокупность соотношений, определяющих этот псевдоплан. Как только переменная снова становится базисной (т.е. вводится в базис), ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвечающие переменной , в соответствующей симплекс-таблице (и во всех следующих) вычеркивают.
С геометрической точки зрения это правило можно обосновать так. Если псевдоплан оказывается внутри полупространства ³ 0, то дополнительное ограничение, определяемое гиперплоскостью = 0, становится несущественным и потому опускается.
Сделаем некоторые замечания относительно метода Гомори.
1. Двойственный симплекс-метод является основой метода отсекающих плоскостей Гомори, так как он позволяет учитывать новые ограничения (правильные отсечения) в процессе решения задачи и переходить от текущего псевдоплана к новому оптимальному плану.
2. При определенных условиях можно гарантировать конечность алгоритма Гомори.
Достаточные условия конечности алгоритма установлены в следующей теореме [18].
Теорема 4.2. Если целевая функция задачи 
ограничена сверху и снизу на множестве решений, причем множество оптимальных решений представляет собой выпуклый многогранник, правильное отсечение образуется по строке таблицы с нецелочисленной компонентой , имеющей минимальный номер, а индекс вектора, вводимого в базис, определяют по величине 
, то алгоритм Гомори является конечным, т.е. за конечное число итераций приведет к случаю 1) или 3).
3. Правильное отсечение можно формировать и по индексной строке. Пусть на k-й итерации элементы индексной строки таковы: 
, причем 
- не целое число.
Обозначим через g0j дробную часть элемента 
: 
=
- [ ]. В этом случае правильное отсечение записывается так:
(4.2.13)
4. В отличие от обычной задачи ЛП задача целочисленного программирования требует большого объема вычислений даже при малых m и n. Количество итераций существенно зависит от того, насколько удачно сформированы правильные отсечения.
5. В результате постоянного улучшения базового алгоритма метода Гомори были разработаны новые алгоритмы отсекающих плоскостей (второй и третий алгоритмы Гомори [12; 27]), которые используют более эффективные правильные отсечения.
Пример 4.2. Решить методом Гомори следующую задачу:
максимизировать 
при ограничениях
£ 7;
£ 5;
≥ 0;
- целые числа.
Для данной задачи оптимальный нецелочисленный план найден двойственным симплекс-методом (см. пример 2.9). Здесь это решение приведено в таблице 4.1.
Таблица 4.1.
|
¯ |
|||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
||
|
1 |
x1 |
40/9 |
1 |
0 |
0 |
5/9 |
1/9 |
0 |
|
|
0 |
x3 |
1 |
0 |
0 |
1 |
-6 |
1 |
0 |
|
|
1 |
x2 |
23/9 |
0 |
1 |
0 |
4/9 |
-1/9 |
0 |
|
|
D |
7 |
0 |
0 |
0 |
1 |
0 |
0 |
||
|
|
x6 |
-4/9 |
0 |
0 |
0 |
-5/9 |
-1/9 |
1 |
Образуем правильное отсечение по строке 
(i = 1):
Допишем строку 
и столбец к табл.4.1. Направляющая строка 
, направляющий столбец 
. Выполнив одну итерацию (шаг) двойственного симплекс-метода, приходим к табл.4.2.
Таблица 4.2.
|
¯ |
|||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
||
|
1 |
x1 |
4 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
|
0 |
x3 |
-3 |
0 |
0 |
1 |
-11 |
0 |
9 |
|
1 |
x2 |
3 |
0 |
1 |
0 |
1 |
0 |
-1 |
|
|
x5 |
4 |
0 |
0 |
0 |
5 |
1 |
-9 |
||
|
D |
7 |
0 |
0 |
0 |
1 |
0 |
0 |
Находим в столбце 
отрицательную компоненту 
= -3 < 0 и определяем направляющую строку 
. Направляющий столбец 
. Выполнив итерацию двойственного симплекс-метода, приходим к табл.4.3. Так как в этой таблице все элементы 
³ 0, то первая большая итерация метода Гомори закончена, и найден новый оптимальный, но нецелочисленный план. Поэтому формируем правильное отсечение по индексной строке.
Таблица 4.3.
|
¯ |
||||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
||
|
1 |
x1 |
4 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
0 |
x4 |
3/11 |
0 |
0 |
-1/11 |
1 |
0 |
-9/11 |
0 |
|
|
1 |
x2 |
30/11 |
0 |
1 |
1/11 |
0 |
0 |
-2/11 |
0 |
|
|
x5 |
29/11 |
0 |
0 |
5/11 |
0 |
1 |
-54/11 |
0 |
||
|
D |
74/11 |
0 |
0 |
1/11 |
0 |
0 |
9/11 |
0 |
||
|
|
x7 |
-8/11 |
0 |
0 |
-1/11 |
0 |
0 |
-9/11 |
1 |
|
|
θ |
1 |
1 |
Дописываем к табл.4.3 снизу строку 
- слева - столбец . Выбрав направляющий элемент 
= -1/11 и выполнив очередную итерацию, получаем табл.4.4.
Таблица 4.4
|
¯ |
||||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
||
|
1 |
x1 |
4 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
0 |
x4 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
-1 |
|
|
1 |
x2 |
2 |
0 |
1 |
0 |
0 |
0 |
-1 |
1 |
|
|
|
x5 |
-1 |
0 |
0 |
0 |
0 |
1 |
-9 |
5 |
|
|
x3 |
8 |
0 |
0 |
1 |
0 |
0 |
9 |
-11 |
||
|
D |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Так как в столбце имеется отрицательный элемент 
= -1, то выполним следующую итерацию с направляющим элементом 
= -9. Вектор должен быть снова введен в базис, но так как переменная 
была использована для формирования предыдущего отсечения, то это позволяет после соответствующей итерации двойственного симплекс-метода вычеркнуть (или опустить) строку и столбец в следующей табл.4.5.
Закончилась вторая большая итерация. Так как в столбце имеются дробные компоненты, то формируем следующее новое правильное отсечение (строка 
), по строке . Направляющий элемент 
= -1/9. Выполнив очередную итерацию, получим табл.4.6.
Анализируя табл.4.6, находим направляющий элемент 
= -11. Вектор нужно снова ввести в базис. При этом в соответствии с приведенным выше правилом строку и столбец в следующей табл. 4.7 опускают.
Таблица 4.5
|
¯ |
||||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A7 |
A8 |
||
|
1 |
x1 |
35/9 |
1 |
0 |
0 |
0 |
1/9 |
5/9 |
0 |
|
|
0 |
x4 |
1 |
0 |
0 |
0 |
1 |
-1 |
-1 |
0 |
|
|
1 |
x2 |
19/9 |
0 |
1 |
0 |
0 |
-1/9 |
4/9 |
0 |
|
|
x3 |
6 |
0 |
0 |
1 |
0 |
1 |
-6 |
0 |
||
|
D |
6 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
||
|
|
x8 |
-8/9 |
0 |
0 |
0 |
0 |
-1/9 |
-5/9 |
1 |
|
|
θ |
0 |
9/5 |
Таблица 4.6
|
¯ |
||||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A7 |
A8 |
||
|
1 |
x1 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
x4 |
1 |
0 |
0 |
0 |
1 |
0 |
-1 |
0 |
|
|
1 |
x2 |
3 |
0 |
1 |
0 |
0 |
0 |
1 |
-1 |
|
|
|
x3 |
-1 |
0 |
0 |
1 |
0 |
0 |
-11 |
9 |
|
|
x5 |
6 |
0 |
0 |
0 |
0 |
1 |
5 |
-9 |
||
|
D |
6 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Таблица 4.7
|
¯ |
||||||||||
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A8 |
A9 |
||
|
1 |
x1 |
3 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
0 |
x4 |
12/11 |
0 |
0 |
-1/11 |
1 |
0 |
-9/11 |
0 |
|
|
1 |
x2 |
32/11 |
0 |
1 |
1/11 |
0 |
0 |
-2/11 |
0 |
|
|
x5 |
83/11 |
0 |
0 |
5/11 |
0 |
1 |
-54/11 |
0 |
||
|
D |
65/11 |
0 |
0 |
1/11 |
0 |
0 |
9/11 |
0 |
||
|
|
x9 |
-10/11 |
0 |
0 |
-1/11 |
0 |
0 |
-9/11 |
1 |
Так как полученный план в табл.4.7 еще нецелочисленный, то формируем новое правильное отсечение по индексной строке, дописывая к табл.4.7 строку и столбец 
. Направляющий элемент 
= -1/11.
Таблица 4.8
|
ci |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
||
|
Bx |
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A8 |
A9 |
|
|
1 |
x1 |
3 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
x4 |
2 |
0 |
0 |
0 |
1 |
0 |
0 |
-1 |
|
1 |
x2 |
2 |
0 |
1 |
0 |
0 |
0 |
-1 |
1 |
|
x5 |
3 |
0 |
0 |
0 |
0 |
1 |
-9 |
5 |
|
|
x3 |
10 |
0 |
0 |
1 |
0 |
0 |
9 |
-11 |
|
|
D |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Выполнив одну итерацию двойственного симплекс-метода, приходим к табл.4.8, где получен искомый целочисленный план: 
= 3, 
= 2; 
= 10, 
= 2, 
= 3 - свободные переменные. Целевая функция 
= ( + ) = 5.
