Аналітичне подання методу Гомори

Гомори запропонував простий спосіб правильного відсікання. Припустимо, що в результаті застосування симплекс-методу при розв’язанні З.Л.П.вийшов оптимальний план x^o=(в ₁₀; в ₂₀;... в_mo; 0; _, 0),де в _ko – не ціле.

Можна довести, що

(5.3)

воно має всі властивості правильного перетинання, де дробова частина числа, ,а -ціла частина числа. Наприклад,

- ціла частина числа це найближче ціле число ліворуч від нього.

Дробова частина завжди позитивна.

Для розв’язання З.Ц.П.використовуємо наступний алгоритм:

П1.Розв’язуємо симплекс- методом З.Л.П..

Якщо всі компоненти оптимального плану цілі, то це розв’язання З.Ц.П. Якщо З.Л.П. не має розв’язання, то і З.Ц.П. не має розв’язання.

Якщо є нецілі компоненти оптимального плану З.Л.П.,то переходимо до пункту 2.

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

П3.Нерівність (5.3) уведенням ненегативної целочисленной перемінної перетворюємо в еквівалентне рівняння і включаємо до симплекс- таблиці з нецілочисловим оптимальним планом.

П4.Отриману З.Л.П. з доданим рядком розв’язуємо симплексом-методом. Якщо одержимо оптимальний план цілочисловий, то З.Ц.П. розв’язана, якщо ні, то переходимо знову до пункту 2.

Якщо З.Ц.П. має розв’язання, то після кінцевого числа кроків оптимальний цілочисловий план буде знайдений. Якщо ж у процесі розв’язання з'явиться рядок з нецілим вільним числом в _k і цілими іншими коефіцієнтами в рядку, то відповідне рівняння не має розв’язання в цілих числах, тобто З.Ц.П. не має розв’язання.

Покажемо застосування методу Гомори на прикладі.

Приклад 5.1

Розв’язання.

Приведемо З.Л.П. до канонічного вигляду, помноживши перше рівняння на –1.

Тому що в рівняннях обмежень відсутні базисні змінні, то введемо штучні базисні змінні , і розв’яжемо М-задачу.

		с		-1	-5	-3	М	М
хб	сб	xi	x1	x2	х3	х4	x5	х6	Q
х5	М		-1						7/3
x6	М				-1				6/3
без М			-2
с М									Dj
х5	М		-5/3	5/3	10/3			-1/3	1,5
х4	-3		2/3	1/3	-1/3			1/3
без М		-6	-4					-1
с М			-5/3	5/3	10/3			-4/3
x3	-5	1,5	-0,5	0,5			0,3	-0,1
х4	-3	2,5	0,5	0,5			0,1	0,3
без М	f	-15	-1	-3			-1,8	-0,4	Dj
с М							-1	-1

Тому що , то отриманий план З.Л.П: не цілочисловий. Застосуємо метод Гомори і знайдемо розв’язання З.Ц.П.

Складемо правильне відсікання

Тому що , те для побудови відсікання можна взяти будь-як рядок, наприклад, другий.

Одержимо

Додамо це обмеження новим рядком у симплекс-таблицю.

				-1	-5	-3
х5	с5	xi	x1	x2	X3	X4	X5
x3	-5	1,5	-0,5	0,5
х4	-3	2,5	0,5	0,5				0,5
х5		-0,5	-0,5	-0,5
f	=	-1,5	-1	-3
x3	-5						-1
х4	-3
x1							-2
f	=	-14		-2			-2	Dj

Тому що Dj , то отриманий план: , оптимальний, цілочисловий,

Зауваження. Якщо розв’язуєть З.Ц.П. на максимум функціі мети f, тоді штучні базисні перемінні додаються в функцію цілі з коефіцієнтами – М.

Запитання з теми

1.Постановка задачі цілочислового програмування. (З.Ц.П.).

2. Математична модель З.Ц.П..

3.Зв'язок розв’язання З.Ц.П. з розв’язанням З.Л.П..

4. Спосіби розв’язання З.Ц.П..

5. Розв’язання З.Ц.П. методами «відсікання», поняття «правильного» відсікання.

6. Геометрична ілюстрація методу «відсікання».

7. Метод Гомори, побудова «правильного» відсікання.

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

Завдання для контрольної та самостійної робіт

Розв’язати задачу цілочислового програмування, задану в матричной формі

= * Х

А * х =

Х 0, цілочисловий.

Матриця системи обмежень А, права частина системи обмежень,вектор , вектор з функції мети z для кожного варіанта завдань надані в таблиці 6.

Дані для розв’язання задачі цілочіслового програмування.

Таблиця 6.