8. Симплексний метод зі штучним базисом. Ознака оптимальності плану зі штучним базисом.

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

Ідея МШБ:

У відповідні обмеження канонічної форми ЗЛП вводяться штучні змінні, які дають необхідну кількість одиничних базисних векторів.

Штучні змінні вводяться функцією мети з коефіцієнтами +М (для задач на мин.),

-М(для задач на макс.), де М – дуже велике число. Визначені одиничні лінійно незалежні вектори утворюють базис, і змінні задачі, що відповідають їм, називаються базисними, а всі інші змінні – вільними.

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

В результаті одержуємо задачу, яка називається ЗЛП зі штучним базисом, до якої застосовується симплекс-метод.

Зв'язок між оптимальнім розв’язком ЗЛП і ЗЛП зі штучним базисом:

1. Якщо задача зі штучним базисом не має розв’язків, то по початкова ЗЛП не має оптимального розвязку.

2. Якщо задача зі штучним базисом має оптимальний розвязок і всі штучні змінні =0, то цей оптимальний розвязок буде оптимальним розв’язком початкової ЗЛП.

3. Якщо задача зі штучним базисом має оптимальний розвязок і хоча б одна штучна змінна>0, то початкова задача має оптимальний розвязок.