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

Часто в ЗЛП

(14.1)

за обмежень

(14.2)

потрібно одержати розв’язок у якому деякі або всі компоненти мають бути цілими числами. Для цього використовують метод ланцюгів і границь. Схема розв’язання ЗЛП у цілих числах ЦЗЛП полягає в наступному:

1. Розв’язуємо ЗЛП (14.1), (14.2) за допомогою симплекс-методу (або будь-яким іншим методом) без умови цілочисельності змінних. Якщо змінні – цілі числа, то задачу можна вважати розв’язаною. Нехай змінна x_k набула не цілого значення x_k=α_k , α_k має дробову складову.

2. Розв’язуємо дві задачі:

a) (14.1), (14.2) за умови ;

b) (14.1), (14.2) за умови ,

де значок означає цілу частину числа, що в ньому міститься.

3. У випадку цілих розв’язків задач a) і b) порівнюємо одержані значення функцій L. Більше з них – оптимальне значенням , а змінні, за яких воно досягається, – розв’язок задачі.

4. Якщо ж знайдеться таке x_l, що не відповідає умові цілочисельності, тоді повторюємо виконання п.2, замінивши x_k на x_l. Таку процедуру повторюємо доти, доки всі потрібні змінні не стануть цілими.

Приклад. Розв’язати ЗЛП в цілих числах:

(14.3)

(14.4)

Розв’язування. Виконуємо п. 1 відповідно до симплекс-процедури розподілу:

	b	x1	x2			b	x1	y1
y1					x2
y2					y2

	b	y2	y1
	-12	-1
х2
х1

Розв’язок досягається при . Будемо виділяти клітинки таблиці з базовим елементом. Оскільки, х₁ та х₂ не цілі числа, переходимо до виконання п. 2.

Використовуючи симплекс-метод, розв’язуємо нову задачу:

	b	x1	x2			b	x1	y1
y1					x2
y2					y2
y3	-4		-1		y3

Оскільки в рядку, де стоїть від’ємний елемент, немає від’ємних чисел, задача розв’язку не має, допустима область порожня. Це означає те, що при х₂≥4 розв’язку даної задачі не існує. Розв’яжемо задачу (13.3), (13.4) за додаткової умови . Тут і далі значок означає цілу частину числа, що стоїть у дужках. Отримаємо:

	b	x1	x2			b	x1	y3
y1					y1
y2					y2
y3					x2

	b	y2	y3
y1
x1
x2

Розв’язок задачі досягається при . Оскільки містить дробову частину, то знову розв’язуємо дві задачі:

а) (14.3), (14.4) за умови

б) (14.3), (14.4) за умови

Розв’язуємо задачу а):

	b	x1	x2			b	x1	y4
y1					x2
y2					y2
y3					y3
y4					x2

	b	y3	y4
	-11	-2	-3
y1		-1	-4
y2		-2	-3
x1
x2

Відповідь: .

Розв’язуємо задачу б):

	b	x1	x2			b	y3	x2
						-4
y1					x2
y2					y2
y3	-2	-1			x1		-1
y4					y4

	b	y3	y2
	-12	-6	-1
y1
x2
x1
y4

Відповідь: .

Задача знову розпадається на дві:

а) (14.3), (14.4),

б) (14.3), (14.4), .

Розв’язуємо задачу а):

	b	x1	x2			b	y3	x2
						-4
y1					x2
y2					y2
y3	-2	-1			x1		-1
y4					y4

	b	y3	y4			b	y2	y4
	-10		-3			-12	-1
y1			-4		y1
y2			-3		y3
x1		-1			x1
x2	-2				x2

Відповідь: .

Розв’яжемо задачу б):

	b	x1	x2			b	x1	y4
						-9
y1					y1
y2					y2
y3	-2	-1			y3	-2	-1
y4	-3		-1		x2

	b	y1	y4
	-9	-2
x1
y2		-2	-5
y3	-2
x2			-1

Відповідь: задача розв’язку не має. Область порожня. Порівнюючи всі розглянуті випадки, одержимо

Аналіз всіх можливих варіантів методу ланцюгів і границь дає можливість зобразити їх наступною схемою (рис. 2).

рис. 2

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

Розв’язати задачі 1-32 у цілих числах або довести, що вони не мають розв’язку.