5.7. Алгоритм методу Гоморі

1. Розв'язуємо задачу симплекс-методом, не враховуючи умову цілочисельності змінних. Якщо оптимальний план містить всі цілочислові компоненти, то розв'язання задачі припиняємо.

2. Якщо оптимальний план містить хоча б одну не цілочислову компоненту , то для відповідного рядка оптимальної симплекс-таблиці складаємо додаткове обмеження. Якщо дробових компонент декілька, вибираємо з них ту, яка має найбільшу дробову частку.

Позначимо через і цілі частини і , а через і ─ дробові частини .

Визначення. Цілою частиною числа називається найбільше ціле число, яке не перевищує і позначається .

Дробовою частиною числа називається число .

Таким чином, та

Наприклад,

Отже, додаткове обмеження Гоморі або відсікання Гоморі має вигляд:

де ─ додаткова змінна, яка ввійде в базис.

3. Використовуючи двоїстий симплекс-метод, знаходимо розв'язок задачі з додатковим обмеження. Якщо цей розв'язок задовольняє критерію оптимальності і містить всі цілочислові компоненти, то розв'язання задачі припиняємо.

4. Якщо оптимальний план містить хоча б одну не цілочислову компоненту, то складаємо ще одне додаткове обмеження. Ітераційний процес приєднання відтинань продовжуємо до отримання оптимального плану задачі або встановлення, що задача розв'язку немає.

5.8. Приклад

Цільова функція

при обмеженнях

- цілі.

Симплекс-методом знаходимо оптимальний план задачі, не враховуючи вимоги цілочисельності змінних. Для цього зведемо її до канонічної форми веденням додаткових змінних:

Складаємо симплекс-таблицю (табл. 10)

Таблиця 10

І	Базис		Сбаз		А0		С1=8		С2=16		С3=0		С4=0		С5=0
							А1		А2		А3		А4		А5
1	А3		0		800		80		70		1		0		0
2	А4		0		80		5		10		0		1		0
3	А5		0		75		3		1 0		0		0		1
m+1					0		-8		-16		0		0		0
1	А3		0		275		59		0		1		0		-7/10
2	А4		0		5		2		0		0		1		-1
3	А2		16		7,5		3/10		1		0		0		1/10
m+1					120		-32/10		0		0		0		16/10
1	А3		0		255/2		0		0		1		-59/2		576/20
2	А1	8		5/2		1		0		0		1/2		-1/2
3	А2	16		135/20		0		1		0		-3/20		5/20
m+1				128		0		0		0		32/20		0

Визначимо Х = як початковий опорний план. Перевіримо цей план на оптимальність. З табл.10 видно, що в (m+1) рядку всі А_j 0, критерій оптимальності виконується. Оптимальний план задачі має вид Х_опт = (5/2; 135/20; 255/2; 0; 0).

Цей план містить дробові компоненти і тому не задовольняє умові цілочисельності задачі.

Оскільки у компоненти дробова частина більше ніж у та , то для неї складаємо додаткове обмеження Гоморі. З останньої симплекс-таблиці 10 маємо:

Дописуємо це обмеження в таблицю і отримуємо табл. 11.

Таблиця 11

І	Базис	Сбаз	А0	С1=8	С2=16	С3=0	С4=0	С5=0	С6=0
				А1	А2	А3	А4	А5	А6
1	А3	0	255/2	0	0	1	-59/2	526/20	0
2	А1	8	5/2	1	0	0	1/2	-1/2	0
3	А2	16	135/20	0	1	0	-3/20	5/20	0
4	А6	0	-15/20	0	0	0	-17/20	- 5/20	1
m+1			128	0	0	0	32/20	0	0

Оскільки в стовпчику А₀ є від'ємна компонента - 15/20, то опорний план Х=(x₁=5/2; x₂=135/20; x₃=255/2; x₄=0; x₅=0; x₆= -15/20) є псевдопланом і згідно з двоїстим симплекс-методом вектор А₆, виводимо з базису, а на його місце вводимо в базис вектор А₅ згідно з мінімумом відношення

Перераховуємо елементи симплекс-таблиці (табл.12), використовуючи елемент -5/20 як розв'язувальний елемент.

Таблиця 12

І	Базис	Сбаз	А0	С1= 8	С2=16	С3=0	С4=0	С5=0	С6=0
				А1	А2	А3	А4	А5	А6
1	А3	0	41	0	0	1	-127,4	0	115,2
2	А1	8	4	1	0	0	22/10	0	-2
3	А2	16	6	0	1	0	-1	0	1
4	А6	0	3	0	0	0	17/15	0	0
m+1			128	0	0	0	32/20	0	0

3 таблиці 12 бачимо, що початкова задача цілочислового програмування має оптимальний план: Х_опт=

На цьому плані значення цільової функції дорівнює F_max=128.