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

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

(20)

за умов

, (21)

(). (22)

де (), та серед векторів

; , …,

нема одиничних.

Визначення 13. Задача, що полягає у визначенні максимального значення функції

(23)

за умов

, (24)

(), (25)

де - досить велике позитивне число, конкретне значення якого як правило не задається, називається розширеною задачею по відношенню до задачі (20)-(22).

Розширена задача має опорний план

,

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

Теорема 8. Якщо в оптимальному плані розширеної задачі (23)-(25) значення штучних змінних , то є оптимальним планом задачі (20)-(22).

Розширена задача (23)-(25) розв’язується звичайним симплекс-методом, але користуються модифікованою таблицею, що містить на один рядок більше. При цьому до -го заносять коефіцієнти при , а до -го рядка – складові, що не містять . Ітераційний процес за -гим рядком ведуть до тих пір, поки:

1) або всі штучні вектори не будуть виключені з базису;

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

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

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

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

Отже, процес пошуку розв’язку задачі (20)-(22) методом штучного базису містить наступні етапи:

1. Складають розширену задачу (23)-(25).

2. Знаходять опорний план розширеної задачі.

3. За допомогою обчислень симплекс-методу виключають штучні вектори з базису. В результаті або знаходять опорний план початкової задачі (20)-(22), або встановлюють її нерозв’язність.

4. Використовуючи знайдений опорний план задачі (20)-(22), або знаходять симплекс-методом оптимальний план початкової задачі, або встановлюють її нерозв’язність.

Дата добавления: 2014-01-13