4. Целочисленное линейное программирование - метод отсечений Гомори

Целочисленное линейное программирование (сокращенно ЦЛП) занимается задачами линейного программирования с целочис­ленными переменными, общая задача формулируется следующим образом: найти тах{сх|Ах ≤ b; х - целочисленный}. ЦЛП мож­ет рассматриваться так же, как поиск точки решетки, принад­лежащей многограннику или как решение системы линейных уравнений с целыми неотрицательными переменными. Иными словами, в ЦЛП рассматриваются совместные ограничения -неотрицательность и целочисленность.

Источник:
Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т.2: Пер с англ. - М.: Мир, 1991. - 342с., ил.
Раздел Целочисленное линейное программирование

4.1. Отсечения

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

Далее описывается метод отсечений Гомори, дающий алгоритм решения задач целочисленного линейного программирования.  Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП (целочисленной задачи линейного программирования) в канонической форме. Описываемая ниже версия алгоритма предназначена для решения полностью целочисленных задач, т.е. таких, у которых все параметры a_ij, c_j, b_i – целые.

4.2. Описание алгоритма.

Приведем обобщенную схе­му алгоритма Гомори. Структурно он делится на так называе­мые большие итерации. Каждая большая итерация содержит этапы:

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

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

3.            Построение для найденной компоненты условия отсечения.     
Исходя из уравнения по данной строке x_r=P0_r - a_r,1*x₁ - …  - a_r,n*x_n  в систему ограничений добавляем неравенство, в котором коэффициенты будут дробными частями коэффициентов данного уравнения:    
{P0_r} –{ a_r,1}*x₁ - …  -{ a_r,n}*x_n ≤ 0.   
Переводим к каноническому виду добавляя новую переменную x_n+1, получим:
{P0_r} –{ a_r,1}*x₁ - …  - {a_r,n}*x_n+x_n+1 = 0      
И соответственно добавляем в симплекс-таблицу новый базисный вектор по новой переменной x_n+1.

4.            Переход на начало следующей большой итерации.

Замечание:

При добавлении в симплекс-таблицу нового базисного вектора по новой переменной x_n+1 мы получаем недопустимое (отрицательное) решение. Для того, чтобы избавиться от недопустимого решения выбираем столбец замещения так, чтобы строкой замещения стала новая добавленная строка по переменной x_n+1. Продолжаем пересчет симплекс-таблицы. Если снова получаем дробное решение, то еще вводим дополнительный базисный вектор, и так до получения целочисленного решения. Но следует заметить, что если область допустимых решений очень мала, то она может и не содержать целых значений, это необходимо проверить графически. Если область допустимых решений не содержит целочисленного решения, то в применении метода Гомори нет необходимости, целого решения не будет!

Источник:
Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2002. - 208 с.: ил. - (Серия "Краткий курс").
Раздел 4.2 Метод Гомори