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

Для отримання системи в канонічному вигляді, що має допустимий базисний розв’язок, існує також і спеціальний метод. Спочатку задача ЛП зводиться до стандартної форми, у якій усі змінні додатні. Потім для кожного обмеження перевіряється існування відповідної базисної змінної. Якщо її немає, то вводиться нова штучна змінна, що відіграє роль базисної для даного обмеження. Після перевірки усіх обмежень отримується система у канонічному вигляді і з’являється можливість заповнити початкову симплексну таблицю. Оскільки введені змінні не мають відношення до суті задачі ЛП у вихідній постановці, то необхідно досягти перетворення в нуль штучних змінних. Це можна зробити за допомогою двохетапного симплекс-методу.

Етап 1. Розглядається штучна цільова функція, що дорівнює сумі штучних змінних, яка мінімізується за допомогою симплекс-методу. Іншими словами, здійснюється виключення штучних змінних. Якщо мінімальне значення допоміжної задачі дорівнює нулю, то всі штучні змінні перетворюються в нуль і отримується допустимий базисний розв’язок початкової задачі. Далі реалізується етап 2. Якщо мінімальне значення допоміжної задачі позитивне, то принаймні одна з штучних змінних також позитивна, що свідчить про суперечливість початкової задачі, і обчислення припиняються.

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