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

В частично целочисленных задачах требование целочисленности накладывается не на все переменные, а на одну или некоторые из них.

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

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

целочисленной должна быть только переменная x_k.

Таблица 1- симплекс-таблица для задачи ЛП

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

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

∑α_kiw_i+v_k=β_k. (2)

Выделим в β_k целую и дробную часть и преобразуем (2) к виду

v_k-[β_k]={β_k}-∑α_kiw_i (3)

Если значение v_k = β_k оказалось дробным, то можно сказать, что интервал [β_k]<v_k<[β_k ]+1 не содержит допустимых целочисленных компонентов решения. Тогда для целочисленной переменной v_k должно выполняться одно из двух неравенств: либо v_k≤[β_k], либо v_k≥ [β_k ] + 1. Левая часть выражения (3) должна быть целой.

Рассмотрим условия, при которых правая часть (3) будет принимать целое значение.

Если v_k≤[β_k ], то из (3) для α_ki≥ 0 следует, что

{β_k}-∑α_kiw_i≤0 или ∑α_kiw_i≥{β_k} (4)

Если v_k≥[β_k] + 1, то v_k - [β_k ] ≥ 1, и из (3) для α_ki≤0 следует, что

{β_k}-∑α_kiw_i≥1 или ∑α_kiw_i≤{β_k} -1 (5)

Умножим обе части неравенства (5) на

{βk}	<0
{βk}-1

, тогда

{βk}	·∑αkiwi≥{βk} (6)
{βk}-1

Так как соотношения (4) и (6) не могут выполняться одновременно, их можно объединить в одно ограничение вида

(7)

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

Пример 1.. Найти оптимальное решение F(x) = 6x₁ + 8x₂ + x₃ + 2x₄ (min) :

x_i≥0, i= 1,4; x₁-целое

Процедура решения задачи с отброшенным условием целочисленности для x₁ иллюстрируется симплекс-таблицами 2 – 4. Получено оптимальное, но не целочисленное решение.

Дополнительное ограничение составляем по строке, соответствующей переменной x₁ табл. 4, на основании выражения (7).

(8)

После преобразования (8), умножения его на (-1) и введения дополнительной переменной х₇ получим дополнительное ограничение в виде

(9)

Табл. 5 соответствует расширенной задаче и получена добавлением к табл. 4 ограничения (9). Выполняя симплекс-преобразования, переходим к табл. 6, которая соответствует оптимальному решению с целым значением x₁:

Таблица 2 - симплекс-таблица для задачи ЛП

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

Таблица 3 - симплекс-таблица для задачи ЛП

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

Таблица 4 - симплекс-таблица для задачи ЛП

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

Таблица 5 - симплекс-таблица для задачи ЛП

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

Таблица 6 - симплекс-таблица для задачи ЛП

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