4. Метод штучного базису

Рішення ЗЛП симплексними процедурами завжди починається з визначення якого-небудь опорного плану. У розглянутому раніше прикладі первісний опорний план виділявся за рахунок балансових змінних.

Геометрично це означає, що область припустимих планів  у такій ЗЛП примикає до початку координат. Однак такий випадок на практиці зустрічається рідко. У цьому зв'язку для виділення первісного опорного плану звертаються до методу штучного базису. Відмітимо, що метод штучного базису дозволяє не тільки виділити первісний опорний план, але й відповістити на запитання сумісності системи обмежень ЗЛП в області невід’ємних значень змінних. Нехай деяка ЗЛП представлена в одній зі своїх канонічних форм.

(29)

(30)

(31)

Задача (29) - (31) називається вихідною. На підставі вихідної складають так називану розширену задачу.

Припускаючи, що всі в кожне з обмежень (30) уводять по штучній змінній , кожна з яких задовольняє умові: . Далі визначають штучну лінійну форму f, що дорівнює сумі всіх введених штучних змінних.

Отже, у розширеній задачі буде змінних. Штучні змінні утворять базис, який називають штучним. Основні змінні на першому етапі рішення задачі будуть вільними. Розширена задача має вигляд:

(32)

(33)

(34)

(35)

Представимо розширену задачу (32) - (35) у вигляді, дозволеному щодо базисних змінних

(36)

(37)

(38)

(39)

Цілком очевидно, що в системі обмежень (38) змінні входять до складу вільних. Тоді за умови маємо

Виділення первісного опорного плану вихідної задачі за допомогою штучних змінних засновано на застосуванні наступних теорем.

Теорема 1.

Для того, щоб система обмежень (30) – (31) вихідної задачі мала припустимі розв’язки, необхідно й достатньо, щоб мінімум штучної лінійної форми (33) дорівнював нулю, тобто .

Доказ необхідності.

Нехай система обмежень-рівностей (30) вихідної задачі має припустимі плани. Наприклад, це наступний набір чисел

.

Тоді, підставляючи ці числа в систему обмежень (34) розширеної задачі, одержимо:

.

Очевидно, що .

Таким чином, якщо система обмежень має розв’язки, то виконується умова .

Доказ достатності.

Нехай мінімум штучної форми дорівнює нулю ( ). Ця умова відповідає деякому рішенню системи обмежень (34) розширеної задачі. Нехай це рішення являє собою набір чисел

(40)

(41)

Проаналізуємо набір чисел (40). Ясно, що такий набір буде задовольняти системі обмежень (34), а виходить, і системі обмежень (30). Із цього виходить, що вихідна система обмежень має, принаймні, одне припустиме рішення, що й необхідно було довести.

Теорема доводить існування припустимих рішень системи обмежень вихідної задачі. З існування припустимих розв’язків виходить існування опорних розв’язків.

Для одержання опорних розв’язків необхідно з розширеної задачі вивести штучний базис.

Теорема 2.

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

Доказ аналогічно доказу теореми 1.

Теорема 3.

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

Доказ аналогічно доказу теореми 1.

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

– перша фаза розв’язку задачі пов'язана з оптимізацією штучної лінійної форми f. На цьому етапі розв’язку виділяється первісний опорний план. Основна лінійна форма F при цьому поводиться пасивно. Особливість першої фази складається у виключенні із задачі штучних змінних за умови виконання прямо припустимості розв’язку ЗЛП.

– друга фаза розв’язку складається з оптимізації основної лінійної форми F, що на цьому етапі поводиться активно.

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

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

Приклад. Розв’язати задачу лінійного програмування

(42)

(43)

У

(44)

кожне обмеження-рівність введемо по однієї штучній змінній. Одержимо розширену задачу

(45)

(46)

Представимо розширену задачу (44)-(46) у вигляді, дозволеному щодо базисних змінних

(47)

(48)

(49)

Далі складемо первісну жорданову таблицю, додавши у звичайну таблицю ще один рядок – рядок штучної лінійної форми f.

	1	-х1	- х2	-х3	-х4	-х5
ξ1	2	1	–1	2	–2	–6
ξ2	5	1	2	–1	7	3	
ξ3	4	–1	1	1	–1	0
F	6	2	–1	3	–2	–10
f	11	1	2	2	4	–3

В першій фазі розв’язку задачі досліджуємо на opt типу min штучну лінійну форму f (на кожному кроці модифікованих жорданових виключень виводяться із задачі по одній штучній змінній, тому що вони не будуть брати участь в оптимізації лінійної форми F).

		1	-х2	-х3	-х4	-х5			1	-х3	-х4	-х5
	х1	2	–1	2	–2	–6		х1	9	3	3	–9
	ξ2	3	3	–3	9	9		х2	3	–3	9	–9	:(3)	
	ξ3	6	0	3	–3	–6		ξ3	18	9	–9	–18
	F	2	1	–1	1	2		F	3	0	–6	–3
	f	9	3	0	6	3		f	18	9	–9	–18

		1	-х3	-х4	-х5			1	-х4	-х5
	х1	3	1	1	–3		х1	3	6	–3
	х2	1	–1	3	–3		х2	9	6	–3	:(3) 
	ξ3	6	3	–3	–6		х3	6	–3	–6
	F	1	0	–2	–1		F	3	–6	–3
	f	6	3	–3	–6		f	0	0	0

		1	-х4	-х5
	х1	1	2	–1
	х2	3	2	–1
	х3	2	–1	–2
	F	1	–2	–1
	f	0	0	0

З останньої жорданової таблиці видно, що , отже, система обмежень вихідної ЗЛП сумісна. На лівому бордюрі сформувався базис змінних: х₁, х₂, х₃ – базисні, х₄, х₅ – вільні змінні. Рядок штучної лінійної форми, що складається з одних нулів, може бути виключений з розгляду.

Таблиця, у якій записаний первісний опорний план, має вигляд

	1	-х4	-х5
х1	1	2	–1
х2	3	2	–1
х3	2	–1	–2
F	1	–2	–1

У другій фазі рішення задачі активною стає рядок лінійної форми F. Аналіз первісного опорного плану показує, що цей план є оптимальним з погляду мінімуму лінійної форми (у рядку лінійної форми немає невід’ємних елементів, за винятком значення самої форми). Таким чином, остаточно маємо

.