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

1. Поняття про метод штучного базису.

2. Двоїстий симплексний метод.

1. Вибір початкової канонічної форми дає змогу формалізувати відшукання оптимального розв’язку за симплекс-таблицями. Канонічна форма задачі легко будується, коли система обмежень виглядає так, як це було в задачі про використання ресурсів:

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

Нехай озлп з ор

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

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

(1)

До неї додаємо штучну форму (2)

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

Справедливим є такий критерій сумісності системи обмежень в області невід’ємних значень.

Теорема 1. Для того щоб система обмежень мала хоча б один допустимий розв’язок, необхідно і достатньо, щоб на розв’язках (1)

.

З теореми випливає такий наслідок.

Наслідок 1. Якщо оптимальний план задачі (1)-(2) містить хоча б одну штучну невідому , то вихідна задача не має розв’язку, оскільки вона не є сумісною в області невід’ємних значень.

Теорема 1 дає практично крім факту існування допустимого плану і метод його відшукання. Зазвичай, знайдений допустимий план є завжди опорним. На прикладі розглянемо методику пошуку опорного плану за методом штучного базису.

Приклад 1.

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

Розв’язування. Вводимо штучні невідомі u₁ і u₂

штучну форму

і заповнюємо початкову таблицю

Номер ітерації	Номер рядка	Базисні невідомі	Опорний розв’язок
	0		34	7	-1	3	4
	1		18	4	-2	1	3
	2		16	3	1	2	1
	3	z	0	-2	1	-3	1

Зробимо декілька зауважень:

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

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

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

Номер ітерації	Номер рядка	Базисні невідомі	Опорний план
	0		34	7	-1	2	4
	1		18	(4)	-2	1	3
	2		16	3	1	2	1
	3	z	0	-2	1	-3	1
	0		5/2	0	5/2	5/4	-5/4
	1		9/2	1	-1/2	1/4	3/4
	2		5/2	0	(5/2)	5/4	-5/4
	3	z	9	0	0	-5/2	5/2
	0		0	0	0	0	0
	1		5	1	0	1/2	1/2
	2		1	0	1	1/2	-1/2
	3	z	9	0	0	-5/2	5/2

У нульовому рядку другої ітерації немає вже додатних чисел, тому план Х^=(5,1,0,0,0,0) є оптимальним для задачі (3), а план Х=(5,1,0,0) - опорним для вихідної задачі. Тепер розв’язуємо вихідну задачу. Виписуємо ще раз таблицю другої ітерації, де у нульовому рядку будуть елементи форми z (3-й рядок таблиці). Результати операції подані у новій таблиці.

Номер ітерації	Номер рядка	Базисні невідомі	Опорний план
	0	z	9	0	0	-5/2	5/2
	1		5	1	0	1/2	1/2
	2		1	0	1	(1/2)	-1/2
	0	z	14	0	5	0	0
	1		4	1	-1	0	1
	2		2	0	2	1	-1

План Х=(4,0,2,0) є оптимальним, z_max = 14.

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

Завдання 6

Симплексним методом, використовуючи метод штучного базису, знайти оптимальний план задачі за умовою завдання 1.

Контрольні запитання:

1. Наведіть приклад задачі, яка не має опорного плану. Чому?

2. Яка стандартна форма для задачі, що розв’язується штучним базисом?

3. Що таке штучна форма? Як її сформувати?

4. Яка система обмежень називається сумісною?

Сформулюйте критерій сумісності системи обмежень в області невід’ємних значень.