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

Необходимое условие применения данного алгоритма: целочисленность всех коэффициентов и правых частей ограничений. Например, пусть ограничение имеет вид:

.

 В таком виде использовать неравенство в дробном алгоритме метода Гомори нельзя. Умножим все элементы неравенства на 6. Тогда неравенство примет следующий вид:

6 x ₁ + 2 x ₂ £ 39

и в данной форме оно используется при решении задачи.

На первом шаге метода решается задача линейного программирования (ЗЛП) без условия целочисленности. Если значения оптимальных переменных - целочисленные, то это и есть решение задачи. В противном случае вводится дополнительное ограничение (отсекающая плоскость) и решается новая ЗЛП. Данная процедура повторяется до тех пор, пока оптимум не станет целочисленным.

Пусть оптимальная симплекс-таблица ЗЛП без условия целочисленности имеет следующий вид:

 

 

БП	х1	...	х i	...	xm	w1	...	wj	...	wn	Р
z	0	...	0	...	0	k1	...	kj	...	kn	b 0
x1	1	...	0	...	0	a 11	...	a 1j	...	a 1n	b 1
...	...	....	...	...	...	...	...	...	...	...	...
xi	0	...	1	...	0	a i1	...	a ij	...	a in	b i
...	...	....	...	...	...	...	...	...	...	...	...
xm	1	...	0	...	0	a m1	...	a mj	...	a mn	b m

 

Здесь x_i = 1,..., m - базисные переменные; w_j = 1,...,n - небазисные переменные.

Каждую строку симплекс-таблицы с нецелым значением b _i. будем называть производящей строкой. Связанное с этой строкой уравнение будем называть производящим уравнением.

Запишем x_i - уравнение этой таблицы с нецелым значением x_i = b _i (производящее уравнение):

.

Разрешим уравнение относительно x_i :

                                                      

Обозначим:

b _i = [ b _i ] + f_i,

a _ij = [ a _ij ] + f_ij ,

где [а] - это наибольшее целое, удовлетворяющее условию [а] £ а. Например для а = 4 /3:

[а] = [4/3] = 1 - целая часть числа,

f = a - [ a ] = 4/3 - [4/3] = 1/3 - дробная часть числа.

Для а = - 4 /3:

[а] = [ - 4/3] = -2 - целая часть числа,

f = a - [ a ] = - 4/3 - [ - 4/3] = 2 /3 - дробная часть числа.

Таким образом:

0 < f_i < 1; 0 £ f_ij < 1.

Подставим введенные соотношения  для коэффициентов b _i и a _ij в уравнение x_i -ой строки:

f_i - å f_ij w_j = x_i - [ b _i ] + å [ a _ij ] w_j .

По условию целочисленности задачи переменные x_i и w_j должны быть целыми. Значит правая часть этого соотношения - целая величина, поэтому и левая тоже есть целая величина. По определению f_ij ³ 0, w_j > 0. Следовательно

å f_ij w_j ³ 0.

Тогда

f_i - å f_ij w_j £ f_i < 1

или

f_i - å f_ij w_j £ 0.

Это условие и формирует отсекающую плоскость Гомори. Его можно переписать в виде:

S_i = å f_ij  w_j - f_i , где S_i ³ 0.

Приведем это неравенство к стандартной форме:

S_i - å f_ij  w_j = -f_i, где S_i ³ 0.

Это условие будет включаться в оптимальную симплекс таблицу, полученную при решении ЗЛП без условия целочисленности. При включении этого условия в симплекс-таблицу на текущем оптимальном решении переменная S_i = -f_i < 0, так как все w_j = 0. Это означает, что новое ограничение на текущем решении не выполняется (недопустимое решение). Поэтому необходимо решать эту задачу двойственным симплекс-методом после включения отсечения Гомори в таблицу /2/. Если полученное в результате решение окажется целочисленным, то задача решена. Если нет - то надо построить следующее отсечение Гомори.

Название "дробный алгоритм" связано с тем, что все коэффициенты отсечения Гомори - дробные числа 0 < f_i < 1; 0 £ f_ij < 1.

Пример:

           max z = 7x₁ + 9x₂

                 -x₁ + 3x₂ £ 6

                 7x₁ + x₂ £ 35

                   x_i ³ 0 - целые

Решаем задачу без условия целочисленности. Получаем следующую оптимальную симплекс-таблицу:

 

БП	х1	х2	х3	х4	Решение
z	0	0	28/11	15/11	63
х2	0	1	7/22	1/22	7/2
х1	1	0	-1/22	3/22	9/2

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

f₁ = [ х₁ ] = 1/2; f₂ = [ х ₂ ] = f₂ = 1/2.

Выберем переменную x₂ и связанную с ней строку в качестве производящей. Уравнение, связанное с переменной x₂  имеет вид:

x₂  + 7/22 x₃ + 1/22 x₄ = 7/2.

Составим отсечение Гомори:

S_i - å f_ij w_j = -f_i,

где f₂₃ = 7/22; f₂₄ = 1/22. Таким образом, получаем следующее уравнение:

S_i - 7/22 x₃ -1/22 x₄ = -1/2.

Включаем это отсечение в симплекс-таблицу. Новая таблица имеет вид:

 

БП	х1	x 2	x3	x4	S1	Реш.
z	0	0	28/11	15/11	0	63
x 2	0	1	7/22	1/22	0	7/2
x 1	1	0	-1/22	3/22	0	9/2
S 1	0	0	-7/22	-1/22	1	-1/2

Двойственным симплекс-методом находим оптимальное решение задачи (за 1 итерацию):

 

БП	х1	x 2	x3	x4	S1	Реш.
z	0	0	0	1	8	59
x 2	0	1	0	0	1	3
x 1	1	0	0	1 /7	-1/7	32/7
x 3	0	0	1	1/7	-22/7	11/4

Для переменной х₁ нарушается условие целочисленности. В качестве производящей выбирается связанная с х₁ строка. Ей соответствует уравнение:

х₁ + 1/7х₄ - 1/7S₁  = 32/7.

Дробные части коэффициентов равны:

f₁₄ = 1/7; f_1S = 6/7; f₁ = 4/7.

Значит уравнение для отсечения Гомори имеет вид:

S₂ - 1/7x₄ - 6/7S₁ = - 4/7

Включаем это отсечение в симплекс-таблицу. Новая таблица имеет вид:

БП	x 1	x 2	x3	x4	S1	S2	Реш.
z	0	0	0	1	8	0	59
x2	0	1	0	0	1	0	3
x1	1	0	0	1/7	-1/7	0	32/7
x3	0	0	1	1/7	-22/7	0	11/7
S 2	0	0	0	-1/7	-6/7	1	-4/7

Двойственным симплекс-методом находим оптимальное решение задачи (за 1 итерацию):

БП	x 1	x 2	x3	x4	S1	S2	Реш.
z	0	0	0	0	2	7	55
x2	0	1	0	0	1	0	3
x1	1	0	0	0	-1	1	4
x3	0	0	1	0	-4	1	1
x 4	0	0	0	1	6	-7	4

Целочисленность переменных достигнута. Следовательно, данная таблица содержит решение задачи: z = 55, x ₁ = 4, x ₂ =3.