26

Тема 4. Цілочисельні задачі та методи їх розв’язування

4.1. Постановка задачі цілочисельного лінійного проґрамування (цлп), її інтерпретація та основні підходи до розв’язування

Структурні особливості задач цілочисельного лінійного проґрамування служать основою для розробки ефективних алґоритмів розв’язування деяких задач. В загальному випадку цілочисельні задачі є NP-повними, тобто ефективних алґоритмів їх розв’язування не існує.

Для розв’язування цілочисельних задач застосовуються методи, що належать до однієї з наступних груп.

Методи відсічень. Ідея відсічень належить Ґоморі. Методи цієї ґрупи призначені для розв’язування лінійних змішаних (як з неперервними, так і з цілочисельними змінними) задач і будуються таким чином, щоб в процесі розв’язування відтинались частини області припустимих розв’язків, що не містять оптимуму до того моменту, поки не буде знайдений цілочисельний оптимальний розв’язок. Спочатку розв’язується задача з послабленими обмеженнями (без врахування цілочисельності), надалі на кожній ітерації вводиться додаткове обмеження, що враховує вимоги цілочисельності, і таким чином многогранник припустимих розв’язків тнеться до того часу, поки отриманий розв’язок не стане цілочисельним. Методи цієї групи різняться в основному способом формування додаткових обмежень.

Комбінаторні методи. Комбінаторні методи побудовані на використанні ідеї неповного перебору з відтинанням на кожному кроці підмножин області припустимих розв’язків, в яких ґарантовано не знаходиться оптимальний розв’язок. В методах цієї групи в більшості випадків використовуються процедури пошуку по дереву розв’язків.

Еврістичні методи. Методи цієї групи будуються на правдоподібних припущеннях або використовують ідеї алґоритмів розв’язування простіших задач і не дозволяють ґарантовано отримати оптимальний розв’язок, хоча в середньому отримувані розв’язки будуть близькими до оптимальних. Широко розповсюдженим прийомом є синтез правил пріоритетів (як в задачі про наплечник), починаючи від лексикоґрафічного впорядкування та простих правил пріоритетів до деревовидних структур гнучких ієрархічних пріоритетів.

4.2. Метод Ґоморі для розв’язування лінійних задач змішаного проґамування

Метод Гоморі належить до методів відсічень і застосовується до розв’язування лінійних задач наступного типу:

,

на деякі (або на всі) змінні накладена умова цілочисельності.

Схема алґоритму методу Ґоморі.

Крок 1. Використовуючи будь-який з варіантів симплекс-методу, знаходимо оптимальний розв’язок задачі без врахування умов цілочисельності. Якщо задача не має розв’язку — стоп. Якщо для отриманого розв’язку виконуються умови цілочисельності, то стоп — знайдений оптимальний розв’язок задачі.

Крок 2. Укладаємо додаткове обмеження для змінної, яка в біжучому оптимальному розв’язку має максимальну дробову частину та повинна бути цілочисельною згідно до умови задачі.

Крок 3. За допомогою двоїстого симплекс-методу знаходимо оптимальний розв’язок задачі з додатковими обмеженнями.

Крок 4. Якщо для отриманого розв’язку виконуються умови цілочисельності, то стоп — знайдений оптимальний розв’язок задачі. Якщо розв’язок задачі відсутній — стоп. В іншому випадку переходимо до 2.

Розглянемо детальніше, яким чином формується додаткове обмеження задачі та чим викликане застосування на наступних кроках двоїстого симплекс-методу. За визначенням дробовою частиною числа A — f(A) вважатимемо найменше невід’ємне число B таке, що різниця A-B буде цілою: f(2.2)=0.2  (2.2-0.2=2); f(-2.2)=0.8  -2.2-0.8=3.

Додаткове обмеження формується на основі рядка біжучої симплекс-таблиці, в якому знаходиться змінна з максимальною дробовою частиною з числа тих, які за умовою задачі повинні бути цілочисельними. Нехай цей рядок має вигляд — множина індексів змінних біжучої бази, які повинні бути цілими згідно до умови задачі і які ними не є, — кількість базових змінних на біжучому кроці методу Ґоморі (внаслідок формування додаткових обмежень під час розв’язування задачі кількість обмежень та змінних в задачі зростатимуть). Додаткове, -е обмеження матиме в початковій формі вигляд , де — дробова частина . Значення коефіцієнтів розраховуються за наступною схемою залежно від того, чи відповідне значення згідно до умови задачі повинно бути цілим, чи ні, а також від співвідношень між значеннями коефіцієнтів обраного рядка симплекс-таблиці та значеннями їх дробових частин.

Отримане обмеження необхідно відобразити в наступній симплекс-таблиці. При приведенні до канонічної форми отримаємо обмеження , і перемноживши ліву і праву частини на (-1) відразу введемо змінну до бази, порушивши при цьому для нього умову припустимості.

Внаслідок цього для розв’язування задачі лінійного програмування на наступних кроках застосовуємо двоїстий симплекс-метод.

Приклад 1. Розв’язати задачу:

— цілі.

Приведемо задачу до канонічної форми

.

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

На кроці 1 розв’язуємо задачу за допомогою звичайного симплекс-методу.

xb	cb	P0	1	4	0	0
			P1	P2	P3	P4
x3	0	19/3	2	1	1	0	19/3
x4	0	4	1	3	0	1	4/3
Q	=	0	-1	-4	0	0
x3	0	5	5/3	0	1	-1/3
x2	4	4/3	1/3	1	0	1/3	
Q	=	16/3	1/3	0	0	4/3

В останній симплекс-таблиці обираємо останній рядок, що відповідає x₂ і розраховуємо відповідні значення коефіцієнтів додаткового обмеження.

Формуємо додаткове обмеження:

		b2	x1	x2	x3	x4
x2		4/3	1/3	1	0	1/3	
		f(b2)=1/3	ціле	ціле	неціле	неціле
			f(a21)<=f(b2)	f(a22)<=f(b2)	a23>=0	a24>=0
			1/3<=1/3	0<=1/3	0>=0	1/3>=0
			f(a21)=1/3	f(a22)=0	a23=0	a24=1/3

1/3x1	+0x2	+0x3	+1/3x4		>=1/3
x1	+0x2	+0x3	+x4		>=1
x1	+0x2	+0x3	+x4	-x5	=1
- x1	-0x2	-0x3	-x4	+x5	=-1

Переходимо до наступного кроку — доповнюємо симплекс-таблицю новим обмеженням — рядком та базовою змінною — стовпчиком і розв’язуємо задачу за допомогою двоїстого симплекс-методу.

xb	cb	P0	1	4	0	0	0
			P1	P2	P3	P4	P5
x3	0	5	5/3	0	1	-1/3	0
x2	4	4/3	1/3	1	0	1/3	0
x5	0	-1	-1	0	0	-1	1
Q	=	16/3	1/3	0	0	4/3	0
x3	0	10/3	0	0	1	-2	5/3
x2	4	1	0	1	0	0	1/3
x1	1	1	1	0	0	1	-1
Q	=	5	0	0	0	1	1/3

Отримано оптимальний розв’язок задачі. Стоп.

Геометрично процес розв’язування представлено нижче.