матриці.
При переважній числі обмежень типу В«нерівністьВ» може бути використаний метод змінного базису .
Метод заснований на тому, що базисна матриця може бути представлена ​​у вигляді
В
Зворотний до неї має вигляд
В
При відносно невеликих розмірах матриці інша частина матриці може не зберігатися.
Таким підходом вдається вирішити завдання з десятками мільйонів рядків обмежень (наприклад, з теорії ігор).
Двоїстий симплекс-метод
Для реалізації двоїстого методу необхідно перейти від завдання на мінімум до задачі на максимум (або навпаки) шляхом транспонування матриці коефіцієнтів. При переході від завдання на мінімум цільова функція набуде вигляду:
В
при обмеженнях
.
Теорема подвійності . Якщо з пари двоїстих задач одна має оптимальним планом, то й інша має рішення, причому екстремальні значення лінійних функцій цих завдань рівні.
Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення.
