§ 1.5. Алгоритм симплексного методу. Таблична реалізація. Приклад

У попередньому параграфі наведені властивості ЗЛП, які дозволяють чітко описати послідовність дій (алгоритм) при розв’язуванні задачі.

Ми вважали, що задача задана в канонічній формі. Тому при розв’язуванні ЗЛП насамперед здійснюється підготовча робота.

Загальна схема (алгоритм) може бути описаний так:

Крок 1. З метою визначення початкового базисного плану перейти від ЗЗЛП до відповідної КЗЛП. (Методи побудови КЗЛП ми розглянемо в наступному параграфі). Якщо відповідної КЗЛП не існує, то множина допустимих планів заданої ЗЛП порожня і розв’язування завершено (розв’язку не існує).

Крок 2. Обчислити відносні оцінки для небазисних змінних . (Відносні оцінки базисних змінних дорівнюють нулю). Перейти до кроку 3.

Крок 3. Здійснити процедуру тестування отриманого базисного плану на оптимальність. Якщо всі , перейти до кроку 5. Якщо існує такий номер , що і у відповідній КЗЛП при всіх , то цільова функція задачі необмежена знизу і розв’язування завершено (розв’язку задачі не існує). Якщо ж для кожної з від’ємних оцінок існують строго більші нуля, перейти до кроку 4.

Крок 4. Здійснити перехід до базисного плану з меншим значенням цільової функції. Серед небазисних змінних треба вибрати змінну , а серед базисних – змінну так, щоб при введенні у множину базисних змінних замість змінної цільова функція зменшилась на якомога більше число. Згідно з (1.4.11), номери та бажано вибирати так, щоб добуток був мінімальним.

Найчастіше номер вибирають за правилом

,

а після вибору номер знаходять згідно з (1.4.13).

Визначивши провідний елемент , будують нову КЗЛП відповідно за (1.4.9), (1.4.10) і визначають тим самим новий базисний план, після чого необхідно перейти до кроку 2.

Крок 5. Згідно з отриманою КЗЛП, для заданої початкової задачі виписують оптимальний план КЗЛП і підраховують відповідне значення цільової функції. Розв’язування ЗЛП завершено.

Оскыльки кількість базисних (опорних) планів задачі скінченна, то, відповідно до виписаного алгоритму, процес розв’язування завершиться після скінченного числа використання кроку 4. Практика показує, що це число використань кроку 4 в середньому дорівнює кількості непрямих обмежень в ЗЛП, тобто числу .

Ми вважаємо, що ЗЛП не вироджена, тобто всі її базисні плани є невиродженими.

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

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

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

Ітерація № 1:

баз.	баз.		...		...			...		...
			...		...			...		...
		1	...	0	...	0		...		...
		0	...	0	...	0		...		...
...	...	...	...	...	...	...	...	...	...	...	...	...	...
		0	...	1	...	0		...		...
...	...	...	...	...	...	...	...	...	...	...	...	...	...
		0	...	0	...	1		...		...
		0	...	0	...	0		...		...

При побудові таблиці вважалося, що базисними змінними є , а небазисними – , а також, що

і

.

Провідний елемент в таблиці обведено. – значення цільової функції на плані

.

Згідно зі сказаним, в множину базисних змінних потрібно ввести змінну і вивести із числа базисних змінну .

Нова таблиця (ітерація № 2) будується після обчислень , відповідно до формул (1.4.9), (1.4.10). Важливо зазначити, що ці обчислення ведуться за так званою “схемою прямокутника”.

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

або

Згідно з формулами (1.4.9), треба замінити числом , яке отримується при відніманні від добутку , поділеного на . Аналогічно обчислюється .

При і отримуються після ділення -го рядка на .

, всі інші .

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

Нова таблиця матиме вигляд

Ітерація № 2:

баз.	баз.		...		...			...		...
			...		...			...		...
		1	...		...	0		...	0	...
		0	...		...	0		...	0	...
...	...	...	...	...	...	...	...	...	...	...	...	...	...
		0	...		...	0		...	1	...
...	...	...	...	...	...	...	...	...	...	...	...	...	...
		0	...		...	1		...	0	...
		0	...		...	0		...	0	...

Нову таблицю, як правило, розміщають зразу ж після попередньої, опускаючи заголовний рядок. Як тільки в останньому оціночному рядку всі стануть невід’ємними, процес розв’язування завершується (крок 5).

Завершення процесу побудови таблиць відбувається також на кроці 3, якщо для деякого оцінка від’ємна і всі .

Розв’яжемо простий приклад, побудувавши всі необхідні симплексні таблиці.

,

, , .

Канонічною формою задачі є задача (1.4.4). Базисними змінними є змінні та . Ця задача вже розглядалася в попередньому параграфі. Там же були проведені і розрахунки, необхідні при побудові перших двох симплексних таблиць.

Зараз ми продовжимо розв’язування задачі, побудувавши всі необхідні таблиці.

№ ітер.	баз.	баз.	-2	-1	-7	0	0			Зауваження
1		0	1	2	3	1	0	4		вивести
		0	-1	-4	10	0	1	7		ввести
			-2	-1	-7	0	0		0
2		0			0	1				вивести
		-7			1	0				ввести
					0	0
3		-1		1	0					вивести
		-7		0	1				15	ввести
				0	0
4		-2	1		0
		-7	0		1
			0		0

Всі оцінки невід’ємні.

Отже, відповідна канонічна задача розв’язана. Її розв’язок – , де

,

.

Тепер легко виписати розв’язок початкової заданої задачі, відкинувши додатково введені збалансовуючі змінні та і вернувшись до цільової функції .

У результаті отримуємо

, .

Зробимо одне істотне зауваження. На другій ітерації ми вводили в множину базисних змінних і виводили згідно із кроком 4 алгоритму, бо . На наступній ітерації замість введено в базис . Якби проводився на другій ітерації аналіз добутків , то зразу на цій ітерації замість до базисних була б введена змінна , бо .