4.2. Знаходження допустимого розв’язку

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

Примітки. 1. Елементи рядка обчислюються за загальними правилами жорданових перетворень.

2. Початкове значення функції чи записується в останній клітині рядка (у нашому випадку, коли ). Надалі у цій клітині автоматично з’являються наступні значення цільової функції.

3. Із рядка ведучі елементи не вибираються.

Робимо послідовні перетворення табл. 4.1. Із відношень від’ємних вільних членів до додатних елементів у їх рядках: вибираємо згідно з правилом 1 найменше; ведучий елемент обводимо кружком.

Після перетворення табл. 4.1 буде мати вигляд табл. 4.2

Таблиця 4.2

			1
	1	-1	5
	1	-2	6
	-1	-2	10
	0	1	-2
	-1	2	-2
-F	-20	10	-100

З табл. 4.2 видно, що ми знаходимося у точці: , , тобто в точці К. Автоматично прораховується значення цільової функції: , тобто . Оскільки ще залишилися від’ємні вільні члени, ми ще не знаходимося в допустимій області, як це видно з рис. 2.2 лекції 2.

У табл. 4.2 є вибір між відношеннями ; вибираємо за правилом 1 перше з них і формуємо нову табл. 4.3.

Таблиця 4.3

			1
	1	-1	3
	1	-2	2
	-1	-2	6
	0	1	2
	-1	2	2
-F	-20	10	-80

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

Точки області можна визначити й інакше, беручи перетин ліній, що відповідають , тобто ліній і .

Примітка. Як випливає з властивостей жорданових перетворень, змінити знак вільного члена можна тільки з допомогою додатного ведучого елементу.

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

4.3. Знаходження оптимального розв’язку

Розглянемо табл. 4.3 детальніше. Останній рядок таблиці дає розв’язок:

.

Змінні і є вільними і дорівнюють нулю, тому . Припустимо, що в базис ввели змінну . Вона стане додатною. Тоді величина збільшиться, тобто цільова функція погіршиться (нагадаємо, що за прийнятим нами стандартом функція мінімізується).

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

Отже, ознакою оптимальності плану є невід’ємність оцінок.

Прямуючи до оптимального плану, потрібно зробити оцінки додатними.

Із властивостей жорданових перетворень (п. 3.1) ясно, що змінити знак у стовпчику можна з допомогою від’ємного ведучого елемента. Але при цьому треба не вийти за межі допустимої області. Це досягається застосуванням правила 2.

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

Обґрунтування правила 2. Нехай у стовпчику з від’ємною оцінкою є два від’ємних елементи: і , вільні члени у цих рядках і відповідно.

Якщо має місце співвідношення , то, помноживши обидві частини нерівності на додатне число , одержимо: . Тоді за правилом 2 ведучим елементом вибираємо (див. фрагмент матриці).

Знак залишиться після перетворення додатним. Нове ж значення дорівнює:

;

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

Повертаємося до табл. 4.3.

Згідно з правилом 2 у табл. 4.3 беремо відношення більше з них , тому ведучим елементом беремо “-1” в рядку . Зробимо перетворення з урахуванням ділення всіх елементів “-1”, тобто зміни знаків всіх елементів:

Таблиця 4.4

			1
	-1	1	5
	-1	0	4
	1	-4	4
	0	1	2
	-1	2	2
-F	20	-30	-120

Знаходимося у точці , яка ще не є оптимальною, оскільки існує від’ємна оцінка „–30”. Знову застосуємо правило 2. Ведучий елемент “–4”. Зробимо перетворення і одержимо табл. 4.5.

Таблиця 4.5

			1
	-3/4	-1/4	6
	-1	0	4
	1/4	-1/4	1
	1/4	-1/4	3
	-1/2	-1/2	4
-F	25/2	15/2	-150

Ми знаходимося в точці . Оскільки всі оцінки додатні, план оптимальний. У цьому плані . Значення , тому оптимальне значення цільової функції .

Примітки. 1. Якщо в процесі пошуку допустимого плану виявиться, що у рядку, де вільний член від`ємний, немає додатних елементів, то задача не має допустимого плану. Економічне значення цього факту: система обмежень суперечлива, наприклад, для виконання заданого обсягу робіт не вистачає ресурсів.

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

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

Розглянемо приклад 5.1, де складена початкова симплекс-табл. 4.6. Поміняємо місцями нуль у другому рядку і змінну . Маємо таблицю 4.7

У табл. 4.7 стовпчик з верхнім нулем не несе ніякої інформації, і його з табл. 4.7 викреслюємо та отримуємо табл. 4.8:

Таблиця 4.6

			1
	-2	1	1
0	1	-2	5
	-1	3	-6
-F	-15	-10	0

Таблиця 4.7

	0		1
	-2	-3	11
	1	2	-5
	-1	1	-1
-F	-15	-40	75

Таблиця 4.8

		1
	-3	11
	2	-5
	1	-1
-F	-40	75

Подальші дії з табл. 5.8. виконуємо за описаними вище правилами.