Метод отсечений

Метод заключается в преобразовании невыпуклого множества целочисленной задачи в выпуклое целочисленное путем отсечения от выпуклого множества непрерывной задачи частей, не содержащих целочисленных точек. Тогда использование методов ЛП гарантирует получение оптимального целочисленного решения (при разрешимости задачи). Строится выпуклая оболочка допустимого множества целочисленной задачи. Выпуклой оболочкой невыпуклого множества Q называется наименьшее выпуклое множество, содержащее Q.

Гомори предложил итерационную процедуру, по которой на каждой итерации отсекается часть множества непрерывной задачи (НЗ), не содержащая целочисленных решений, но включающая оптимальное решение НЗ.

1-ый алгоритм Гомори:

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

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

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

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

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

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

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

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

9. Конец.

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

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

Алгоритм находит целочисленное решение только на последней итерации.