Метод Гомори решения задач целочисленного программирования

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

Общая задача линейного целочисленного программирования:

Найти такое решение , при котором линейная функция

(1)

принимает максимальное или минимальное значение при ограничениях , (2)

, (3) - целые числа (4).

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

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

1. оно должно быть линейным;

2. должно отсекать найденный оптимальный нецелочисленный план;

3. не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

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

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

Одним из методов правильного отсечения является метод Гомори.

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

так, что оптимальным решением задачи (1)-(3) является , в котором, например нецелая компонента. В этом случае неравенство

(6)

сформированное по уравнению системы (5), обладает всеми свойствами правильного отсечения.

Алгоритм метода Гомори:

1. Симплексным методом решить задачу (1)-(3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (1)-(4). Если первая задача (1)-(3) неразрешима (то есть если она не имеет конечного оптимума или если ее условия противоречивы), то и вторая задача (1)-(4) также неразрешима.

2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (5) сформировать правильное отсечение (6).

3. Неравенство (6) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение (7) и включить его в систему ограничений (2).

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

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

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