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

Пусть дана следующая задача:

max {F(x)=∑c_ix_i|∑a_jix_i{≤=≥}b_j, j = 1,m, x_i≥0 и и целые для всех i = 1,n}, (1)

Таблица 1.

Здесь для удобства через v_j( j = 1,m) обозначены базисные переменные в оптимальном решении задачи, а через w_i (i = 1,n) – небазисные переменные.

Для любой j-й строки симплекс-таблицы справедливо равенство

∑α_jiw_i+v_j=β_j (2)

Представим величины β_j и a_ji следующим образом:

β_j = [β_j] + {β_j}, α_ji=[α_ji] + {α_ji}, (3)

Подставим (3) в (2)

∑([α_ji]+{α_ji})w_i + v_j= [β_j] + {β_j} (4)

v_j-[β_j]+∑[α_ji]w_i= {β_j} - {α_ji}w_i (5)

Так как переменные v_j и w_i должны быть целыми, левая часть (5) также целая, следовательно, правая часть уравнения (5) может принимать только целые значения. Для того чтобы правая часть была целой, необходимо выполнение неравенства

{β_j} - ∑{α_ji}w_i≤0 или ∑{α_ji}w_i≥{β_j}, j = 1,m (6)

Выражение (6) представляет дополнительное линейное ограничение, или отсечение Гомори, которое определяет гиперплоскость, отсекающую нецелочисленные решения задачи вместе с частью ОДЗП и сохраняющую при этом все целые решения. Дополнительное ограничение составляется по той строке, переменной v_j которой соответствует наибольшая дробная часть. Признаком отсутствия целочисленного решения служит наличие в таблице хотя бы одной строки с дробным свободным членом и целыми остальными коэффициентами. Задача (1) с добавлением ограничения (6) называется расширенной. Соответствующее ей решение не является допустимым, поэтому вначале находим допустимое базисное решение, а затем переходим к процедуре оптимизации.

Пример 1. Найти оптимальное целочисленное решение:

F(x)=x₁+5x₂ (max);

x₁+x₂≤7;

-2x₁+x₂≤2;

x₁≤4;

x_1,2≥0 и целые

Процедура решения задачи с отброшенными целочисленными условиями иллюстрируется симплекс-таблицами 1 – 3.

Таблица 1

Таблица 2

Таблица 3

Оптимальное решение является дробным:

x*₁=5/3; x*₂=16/3; x₃=0; x₄=0; x₅=7/3; F_max=85/3.

Графическая интерпретация решения представлена на рис. 1.

Рис 1.- Графическая интерпретация примера для алгоритма Гомори

Дополнительное ограничение составляем по строке, соответствующей переменной x₁ в табл. 3, так как у нее наибольшая дробная часть: {x₁}=2/3

На основании (6) получаем

{1/3}x₃+{-1/3}x₄≥{5/3} или 1/3 x₃+2/3 x₄≥2/3 (7)

Приведем (7) к виду равенства, вводя дополнительную переменную x₆ и одновременно умножая на (-1). Тогда

-1/3 x₃-2/3 x₄+x₆=-2/3 (8)

С учетом (8) симплекс-таблица расширенной задачи представлена табл. 4. Осуществляя оптимизацию, найдем, что оптимальное целочисленное решение определяется по табл. 5: x*₁=2; x*₂=5; F_max= 27.

Таблица 4

Таблица 5

При нахождении оптимального целочисленного решения всегда происходит проигрыш в величине экстремального значения функции-цели.

Для построения дополнительного ограничения на рис. 1 необходимо выразить переменные x₃ и x₄ через x₁ и x₂ .

Из табл. 1 следует, что x₁ + x₂ + x₃ = 7 и - 2x₁ + x₂ + x₄ = 2 , тогда x₃ = 7 - x₁ - x₂, а x₄ = 2 + 2x₁ - x₂ . Подставляя эти выражения в (8), получим - 3x₁ + 3x₂≤9.

Дополнительное ограничение отсекает заштрихованную часть ОДЗП вместе с точкой х* и образует новую вершину x*_o с координатами [2,5], которая соответствует оптимальному целочисленному решению.