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

 Метод штучних змінних

 

Нехай обмеження мають вигляд .

Якщо b_i≥0, то вільні вектори, які утворюють одиничну підматрицю, утворюють початковий базис, а змінні, які відповідають їм – початковий базисний розв’язок.

В загальному випадку, коли ряд нерівностей має знак > або = наприклад, , то для приведення їх до канонічної форми рівностей вільні змінні необхідно відняти. Тоді розширена форма задачі має вигляд:

(2.9)

Вільні змінні {x_n+1, x_n+2,…,x_n+m} вже не можна використовувати в якості початкового базису, так як вони менше нуля. Тому в рівняння (2.9) додатково вводять штучні змінні x_n+m+1, x_n+m+2,…,x_n+m+k. Ці змінні не мають нічого спільного з реальною задачею і повинні бути виведені із базису. Для того, щоб гарантувати виведення цих змінних із базису їм приписують дуже великі за величиною від’ємні коефіцієнти (-М) для задач максимізації, де М>>с_i. При розв’язуванні задач на мінімум штучні змінні вводять в цільову функцію з великими за величиною додатніми коефіцієнтами (+М). Знаки штучних змінних, які вводяться в обмеження повинні співпадати зі знаками відповідних вільних членів. Штучні змінні утворюють початковий базисний розв’язок. Застосувавши симплекс-метод виводять із базису всі штучні змінні.