3.3. Знаходження невід’ємних розв’язків системи рівнянь

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

Приклад 2.6. Розглянемо систему:

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

Таблиця 4.1

						1
0	1	–1	0	1	0	–2
0	2	–1	0	0	–1	–1
0	–1	2	1	3	0	–3

Зробимо три кроки жорданових перетворень.

						1						1
		1	0	–1	0	2			0	1	1	–1
	0	1	0	–2	–1	3			0	2	1	–3
	0	1	1	4	0	–5		0	1	6	1	–8

Таблиця 4.2

				1
		1	1	–1
		2	1	–3
		–6	–1	8

Пояснимо останню таблицю. Як зазначалося у п. 2.5, вільні змінні повинні дорівнювати нулю, щоб ми знаходилися весь час у вершинах многогранника. Отже, базисні змінні вважаємо рівними вільним членам. У табл. 4.2 маємо такий розв’язок: ; .

Невід’ємні розв’язки – це такі розв’язки, коли невід’ємними є вільні члени, бо вільні змінні дорівнюють нулю. Згідно з властивостями жорданових перетворень (п. 3.1) змінити знак у рядку (в т.ч. знак вільного члена) можна за допомогою додатного ведучого елементу. У табл. 4.2 є чотири таких елементи: у першому рядку „1” і „1”, у другому „2” і „1”. Якому віддати перевагу, щоб, змінивши знак у одному рядку, не одержати від’ємне значення вільного члена у другому рядку? Для систематичного прямування до невід’ємного розв’язку слід застосовувати правило 1.

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

Здійснимо це на табл. 4.2.

З відношень: найменшим є останнє. Тому робимо перетворення і складаємо таблицю 4.3.

Таблиця 4.3

			1					1
	1	1	–1			–1	1	2
	2	1	–3			–2	1	3
	–6	–1	8			–4	–1	5

Табл. 4.3 дає один з варіантів невід’ємних розв’язків: .

Примітки: 1. Для одержання невід’ємних розв’язків може бути потрібно виконати 2, 3... кроки перетворень з додержанням правила 1.

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

Обґрунтування правила 1. Нехай у -му рядку є від’ємний вільний член і додатний елемент .

У рядку є від’ємний вільний член і додатний елемент (див. фрагмент таблиці, який наведений нижче ).

.

Нехай справджується нерівність , з якої слідує: .

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

Знайдемо нове значення вільного члена :

.

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

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