Теорема 2

Якщо для всіх векторів P_j, виконується умова

Δ_j≥0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j≤0, (j=1,2,3…..n) (для задачі на мінімум),

то опорний план Х^*=((х₁)^*, (х₂)^*,......... (х_n)^*) є оптимальним.

Якщо після побудови симплекс-таблиці виявилось, що виконуються умови Т.1 (пункт а)), або Т.2 розв’язання задачі припиняється. Якщо виконуються умови Т.1 (пункт б)), то потрібно перейти до нового оптимального опорного плану, побудувавши наступну симплексну таблицю. Для переходу до нового опорного плану треба один вектор вивести з базису і на його місце ввести новий вектор, який не належить базису. У базис вводять вектор, якому відповідає найбільша за абсолютною величиною від’ємна оцінка Δ_j. Нехай існує така оцінка в k- му стовпці, тобто max| Δ_j | = Δ_k.

Δ_j≤0

Тоді вектор Р_к вводимо у новий базис. Для знаходження вектора Р_r, який необхідно вивести, обчислюють співвідношення

Q= min(b_i/a_ik) (i=1,2…..m),

мінімальне значення якого досягається при i=r. Елемент a_rk називається розв’язувальним.

Рядок Р_r і стовпець Р_к на перетині яких знаходиться розв ’ язувальний елемент a_rk, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса.

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

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

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

У цільовій функції задачі ЛП штучні змінні мають коефіцієнт - М (f(x)→max) або +М (f(x)→min), де під М ми розуміємо досить велике додатне число.

При розв’язанні цієї задачі симплекс-методом оцінки Δ_j будуть залежити від М. Для порівняння оцінок, треба пам’ятати, що М – достатньо велике додатне число, тому із базису будуть виключатися у першу чергу штучні вектори.

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

Якщо оптимальний розв’язок М – задачі містить штучні змінні або М – задача нерозв’язна, то початкова задача також нерозв’язна.