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

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

max {F(x)=∑cixi|∑ajixi{≤=≥}bj, j = 1,m, xi≥0 и и целые для всех i = 1,n}, (1)

в результате решения которой с отброшенными условиями целочисленности получена оптимальная симплекс-таблица (табл. 1) и оптимальное нецелочисленное решение

 

Таблица 1.

базисные переменные Свободные члены Небазисные переменные
w1 w2 ... wn
v1 β1 α11 α12 ... α1n
v2 β2 α21 α22 ... α2n
. . . . . .
vm βm αm1 αm2 ... αmn
F β c1 c2 ... cn

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

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

∑αjiwi+vjj (2)

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

βj = [βj] + {βj}, αji=[αji] + {αji}, (3)

где выражение в [ ] означает наибольшее целое число, не превышающее исходное, а выражение в {} – дробную положительную часть числа, например

пример представления числа

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

∑([αji]+{αji})wi + vj= [βj] + {βj} (4)

и преобразуем (4) следующим образом:

vj-[βj]+∑[αji]wi= {βj} - {αji}wi (5)

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

j} - ∑{αji}wi≤0 или ∑{αji}wi≥{βj}, j = 1,m (6)

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

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

F(x)=x1+5x2 (max);

x1+x2≤7;

-2x1+x2≤2;

x1≤4;

x1,2≥0 и целые

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

Таблица 1

базисные переменные Свободные члены Небазисные переменные
x1 x2
x3 5 1 1
x4 3 2 -1
x5 -2 -1 0.5
F 0 3 2

Таблица 2

базисные переменные Свободные члены Небазисные переменные
x1 x4
x3 5 3 -1
x2 2 -2 1
x5 4 1 0
F 10 -11 5

Таблица 3

базисные переменные Свободные члены Небазисные переменные
x3 x4
x1 5/3 1/3 -1/3
x2 16/3 2/3 1/3
x5 7/3 -1/3 1/3
F 85/3 11/3 4/3

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

x*1=5/3; x*2=16/3; x3=0; x4=0; x5=7/3; Fmax=85/3.

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

графическая интерпретация метода к примеру для алгоритма Гомори

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

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

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

{1/3}x3+{-1/3}x4≥{5/3} или 1/3 x3+2/3 x4≥2/3 (7)

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

-1/3 x3-2/3 x4+x6=-2/3 (8)

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

Таблица 4

базисные переменные Свободные члены Небазисные переменные
x3 x4
x1 5/3 1/3 -1/3
x2 16/3 2/3 1/3
x5 7/3 -1/3 1/3
x6 -2/3 -1/3 -2/3
F 85/3 11/3 4/3

Таблица 5

базисные переменные Свободные члены Небазисные переменные
x3 x6
x1 2 1/2 -1/2
x2 5 1/2 1/2
x5 2 -1/2 1/2
x4 1 -1/2 -3/2
F 27 3 2

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

Для построения дополнительного ограничения на рис. 1 необходимо выразить переменные x3 и x4 через x1 и x2 .

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

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

ДОБАВИТЬ КОММЕНТАРИЙ