Особливості алгоритму методу штучного базису

Справедлива наступнатеорема.

1. Якщо оптимальному рішенні М-завдання все штучні змінні рівні 0, то відповідні значення інших змінних дають оптимальне рішення вихідної задачі;
2. якщо в оптимальному рішенні М-завдання хоча б одна штучна змінна відмінна від 0, то вихідне завдання не має рішення (через несумісність системи обмежень);
3. якщо М-завдання немає рішення через необмеженості цільової функції, те й вихідне завдання рішення немає.

Особливості алгоритму методу штучного базису

1. Виду того, що початкове опорне рішення розширеної ЗЛП містить штучні змінні, що входять до цільової функції з коефіцієнтами -М (max) або +М (min), оцінка розкладів векторів умов Δj = CбXj -cj складається з двох доданків Δj = Δ'j + Δ''j(M). Т.к. М – велике, то першому етапі розрахунку перебування векторів, введених у базис, використовується лише доданок Δ'j( M).
2. Вектори, що відповідають штучним змінним, які виводяться з базису опорного рішення, виключаються із розгляду.
3. Після того, як всі вектори, відповідні штучним змінним, виключені з базису, розрахунок продовжується звичайним симплексним методом з використанням оцінок Δj, не залежать від М.
4. Перехід від рішення розширеної ЗЛП до рішення вихідної ЗЛП здійснюється за допомогою зазначених раніше зауважень.

Приклад. Знайти рішення наступного завдання. Z(X)=x1+x2+4x3→maxxj≥0 (j=1,2,3) Наведемо завдання до канонічного виду:xj ≥ 0 (j=1,2,3,4,5,6)

Z(X)=x1+x2+4x3+0x4+0x5+0x6-Mx7→max У перших двох рівняннях містяться базисні змінні x4 і x5 (це додаткові змінні), а в третьому базисна зміннавідсутня, тому введемо штучну змінну x7, яка і буде базисною. Вирішуємо М-завдання. Складемо симплексну таблицю:

---