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

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

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

(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) розширеної задачі. Нехай це рішення являє собою набір чисел

(41)

(40)

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

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

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

Дата добавления: 2014-12-07