Пример 7.1. Выведем условие отсечения для задачи

L= 2 x ₁ +x ₂ ® max;

15 x ₁ + 30 x ₂ £ 96;

" x_j ³ 0, int.

Приводим неравенство к каноническому виду

15 x ₁ + 30 x ₂ + x ₃ = 96

и решаем непрерывную задачу симплекс-методом. Получаем оптимальную симплекс-таблицу

Базис	А0	А1	А2	А3
А1
D

Графическое решение показано на рис. 7.4.

Записываем уравнение (7.3) по переменной x ₁:

x ₁ + 2 x ₂ + x ₃ = .

Дробную часть кроме свободного члена имеет только коэффициент при x₃. Следуя (7.7), получаем условие отсечения

x ₃ ³ или x ₃ ³ 6.

Очевидно, что в оптимальном решении НЗ оно не выполняется (х ₃ ^*= 0). Условие отсечения можно записать и через основные переменные. Так как х ₃ = 96-15 х ₁ - 30 х ₂, то 96-15 х ₁ - 30 х ₂ ³ 6и окончательно имеем х ₁ + 2 х ₂ £ 6. Граница по этому ограничению показана на рис. 7.4 пунктирной линией. Легко убедиться, что все вершины усеченного множества целочисленные. ▲

При многих нецелых переменных возникает вопрос выбора переменной, по которой следует строить отсечение. Строгого обоснования выбора не имеется. На основе экспериментальных данных рекомендуется брать переменную с наибольшей дробной частью. Второй вопрос относится к способу учета очередного условия отсечения: его можно добавить к условиям исходной задачи и решать задачу заново или после добавления продолжить симплекс-преобразования с полученного оптимального решения, которое стало недопустимым. В алгоритме Гомори применяется второй вариант как более экономичный.

Перед добавлением условие отсечения приводится к равенству:

. (7.8)

Так как небазисные переменные равны нулю, то новая дополнительная переменная . Поэтому рекомендуется для последующего решения применять двойственный симплекс-метод.

Таким образом, согласно 1-му алгоритму Гомори необходимо выполнить следующие действия.

1. Преобразовать условия задачи так, чтобы все коэффициенты стали целыми.

2. Решить исходную задачу без учета целочисленности (НЗ) одним из методов линейного программирования. Если непрерывная задача неразрешима, то зафиксировать неразрешимость исходной задачи и перейти на 9.

3. Проверить решение на целочисленность: если решение целочисленное, то зафиксировать получение оптимального решения и перейти на 9.

4. Если не все переменные целые, то из оптимальной таблицы выбрать переменную с наибольшей дробной частью.

5. Выписать из симплекс-таблицы строку с выбранной базисной переменной.

6. Выделить дробные части коэффициентов в полученном уравнении и записать условие отсечения согласно (7.7).

7. Привести условие отсечения к равенству (7.8), умножить его на –1 и добавить полученную строку к оптимальной симплекс-таблице. При этом размерность базиса увеличивается на единицу. В качестве недостающей базисной переменной принимается дополнительная переменная из новой строки.

8. Решить расширенную задачу двойственным симплекс-методом. Если задача разрешима, перейти на 3. Иначе зафиксировать неразрешимость целочисленной задачи.

9. Конец.

Гомори доказал сходимость этого алгоритма.

Примечание. Как следует из алгоритма, на каждой итерации увеличивается размер таблицы (число условий) на единицу. Для ограничения размера используется такой прием. Как только дополнительная переменная какого-либо условия отсечения снова становится базисной (но уже положительной!), строка с ней удаляется из таблицы. Если велся столбец этой переменной, то он тоже удаляется. Подобное исключение не отразится на решении, так как условие удаляется после того, как становится неактивным. В результате число строк не превысит

Пример 7.2. Применим приведенный алгоритм к задаче

L=2x₁+x₂®max;

2x₁+x₂ ³ 7,5;

12x₁+7x₂£ 55;

5x₁+2x₂+х₅£ 18;

x_1, x₂³ 0, целые.

Умножаем 1-е неравенство на 2 и приводим все условия к равенствам:

4x₁+2x₂-x₃ ³ 15;

12x₁+7x₂+x₄ £ 55;

25x₁+10x₂+х₅£ 90.

Решаем непрерывную задачу симплекс-методом. В табл. 7.3 представлено решение НЗ (оптимальная таблица выделена двойной рамкой, строка оценок записана первой для удобства расширения таблицы).

Таблица 7.3

Решение содержит нецелые переменные. Наибольшую дробную часть имеет переменная x₃. Выписываем соответствующую ей строку:

x₃+ x₄+ x₅= .

Из нее получаем 1-е условие отсечения

x₄+ x₅ ³ ,

которое приводим к равенству

- x₄- x₅+x₆= - .

Это равенство добавляем к оптимальной симплекс-таблице решенной НЗ с включением в число базисных вектора А ₆ (табл.7.3). К расширенной таблице применяем двойственный метод (направляющей является новая строка, направляющий столбец находится по q). Полученное решение, которое называют оптимальным относительно первого отсечения, приведено в табл. 7.4 (см. часть в двойной рамке).

Базис А0 А1 А2 А3 А4 А5 А6 А7 D j 8, 2               А2           -   А3               А1       -     А5         -   А7 -           -

Таблица 7.4

Оно также является нецелочисленным. Новое отсечение строим по переменной х ₂, имеющей наибольшую дробную часть. Выписываем уравнение

х ₂ +х ₄ - х ₆ = ,

из которого следует условие отсечения

х ₆ ³

и затем равенство

х ₆- х ₇ = ,

добавляемое к последней симплекс-таблице (см. табл.7.4). Применяем двойственный симплекс-метод.

Полученное решение, оптимальное относительно второго отсечения, дано в табл. 7.5.

Таблица 7.5

Базис	А0	А1	А2	А3	А4	А5	А6	А7	А8
D j	8,0
А2								-
А3
А1					-
А5								-
А6								-
А8	-				-			-

Очевидно, что оно не удовлетворяет требованию целочисленности. Так как в базисное решение вернулась переменная x ₆, что означает строгое выполнение 1-го условия отсечения, соответствующие ей строка и столбец удаляются (отмечены выделением пунктирной полосой).

Теперь отсечение строим по переменной x ₁:

х ₁- х ₄ + х ₇ = Þ х ₄ + х ₇ ³ Þ х ₄ + х ₇ – х ₈ = .

Добавляем полученное уравнение отсечения к последней таблице (табл. 7.5) и, используя снова двойственный метод, находим оптимальное решение расширенной НЗ (табл. 7.6). Это решение целочисленное и, следовательно, оно является оптимальным для исходной целочисленной задачи. ▲

Из опыта применения рассмотренного алгоритма можно сделать некоторые выводы. Хотя Гомори теоретически доказал, что алгоритм сходится за конечное число шагов, оценки необходимого числа итераций не существует. К сожалению, скорость сходимости алгоритма очень низкая. Встречались примеры с 10-15 переменными, решение которых требовало более тысячи итераций. Попытка вводить отсечение сразу по нескольким переменным не дает ощутимого эффекта.

Отмечается зависимость скорости сходимости от формы и порядка записи условий задачи, существенное влияние ошибок округления. Неприятной стороной алгоритма является постоянное увеличение числа строк вплоть до числа переменных в канонической форме. Если задача разрешима, алгоритм находит целочисленное решение только на последней итерации. Поэтому в случае прерывания расчета не будет получено ни одного даже приемлемого решения.

Эффективность алгоритма повышается с уменьшением значений а_ij и b_i и заполненности матрицы условий А. Можно рекомендовать применение метода для задач небольшой размерности (до десятков переменных), когда значения а_ij и b_i невелики и в оптимальном решении непрерывной задачи большая часть переменных имеет целые значения. Алгоритм мало пригоден для решения комбинаторных задач в целочисленной постановке.

Для других вариантов построения условий отсечения сходимость построенных на них алгоритмов не доказана, а отмеченные недостатки в основном не устраняются. Эти замечания относятся и к алгоритму отсечения для частично целочисленных задач.

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