Методы отсечения. Метод Гомори

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

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

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

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

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

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

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

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

	х2

Рисунок 11.1- Графическое представление существа методов отсечения

Таким образом, если наложить требование целочисленности, то допустимое множество решений вырождается в совокупность точек (рисунок 17.1) и уже в общем случае не является выпуклым.

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

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

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

Одна из наиболее часто используемых процедур решения задачи линейного целочисленно­го программирования (17.1)-(17.4), предложенная Р.Е. Гомори, основана на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Пусть задача линейного (нецелочисленного) программирования (17.1)-(17.3) име­ет конечный оптимум и на последнем шаге ее решения сим­плексным методом получены следующие уравнения, выра­жающие основные переменные x₁, x₂, …, x_j,.., x_mчерез неос­новные переменные x_m+1, x_m+2, …, x_m+i, …., x_nоптимального решения

,

,

……………………………., (17.5)

,

…………………………….

так, что оптимальным решением задачи (17.1)-(17.3) является

X* = (β ₁, β ₂, …, β _i, …, β _m, 0, 0, …, 0), в котором, например β _i – нецелая компонента.

В этом случае можно доказать, что неравенство

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

Примечание 1 В неравенстве (17.6) символ { }, означает дробную часть числа. Целой частью числа а называется наибольшее целое число [а], не превосходящее а, а дробной частью числа - число {а}, равное разности между этим числом и его целой частью, т.е. {а} = а - [а].

Например, для , [ а ]= 2, {а}= ;

для , [ а ]= -3 (обратите внимание, не (-2), а (-3)),

{а}= ;

Для решения задачи целочисленного линейного программиро­вания (17.1)-(17.4) методом Гомори используется следующая методика

1. Симплексным методом решить задачу (1.1)-(17.3) (нецелочисленную) без учета условия целочисленности. Если все компоненты оптимального плана получились целые, то он является оптимальным и для задачи целочис­ленного программирования (17.1)-(17.4).

Если первая задача (17.1)­- (17.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (17.1)-(17.4) также неразре­шима.

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

3. Неравенство (17.6) введением дополнительной неотрицатель­ной целочисленной переменной преобразовать в равносильное уравнение

(17.7)

и включить его в систему ограничений (17.2).

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

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

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

Примечания. 1. Если β _i – дробное число, а все α _ij - целые числа – задача линейного программирования целочисленного решения не имеет.

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