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

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

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

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

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

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

.

Таблица 1

Если решение получилось целочисленное, то вычисления прекращаются.

Если, предположим, что — дробное, то:

• — если все — целые, то задача не имеет целочисленного решения;
• — если существует дробный, то к системе ограничений добавляется дополнительное ограничение (отсечение Гомори).
• 3. Построение отсечения Гомори.

Предварительно заметим, что любое действительное число можно представить в виде суммы двух его частей:

.

где — целая часть числа (); - дробная часть числа .

Согласно данному алгоритму среди нецелочисленных компонент оптимального решения необходимо выбрать компоненту с максимальной дробной частью и сформировать правильное отсечение в виде неравенства:

.

Неравенство необходимо преобразовать в равенство, введением дополнительной неотрицательной переменной:

.

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

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