є в обчисленні для всіх стовпців. Стовпець зі значенням <0 можна вводити в базис.
Часто вибирають мінімальне значення, але для цього потрібно перебрати всі стовпці.
Найчастіше вибирають значення, менше деякого заданого значення
Якщо такого стовпця не виявиться, за приймається максимальне знайдене абсолютне значення і відповідний стовпець вводиться в базис.
. Визначення виведеного. p align="justify"> Нехай - вводиться стовпець, відповідний змінної Базін план - це рішення системи Збільшуємо.
Помножимо зліва на, тобто
Тут - базисний план, - розкладання вводиться стовпці по базису.
Знаходимо максимальне значення, при якому всі значення не негативні. Якщо може бути взято як завгодно велике, рішення не обмежена. В іншому випадку один з елементів вийде на нульове значення. Виводимо відповідний стовпець з базису.
. Перерахунок опорного (базисного) плану. p align="justify"> Обчислюємо новий опорний план по вже наведеною формулою з знайденим значенням.
. Перераховуємо зворотну до базисної. p align="justify"> Нехай - виводиться стовпець.
Матриця B подана в вигляді
де - базисна матриця без виведеного шпальти.
Після заміни стовпця базисна матриця буде мати вигляд
Нам потрібно знайти матрицю, таку що
=> => =>
В
Звідки
Зауваження.
При перерахунку матриці накопичуються помилки округлення. Щоб уникнути отримання великих помилок час від часу матриця перераховується повністю. Цей процес називається В«повтореннямВ».
Мультиплікативний варіант симплекс-методу
У мультиплікативному варіанті матриця не зберігати, зберігаються лише множники
При вирішенні економічних завдань часто матриця обмежень розріджена, в такому випадку мультиплікативний варіант отримує додаткові переваги - можна зберігати мультиплікатори в стислому вигляді (не зберігати нулі).
5. Інші варіанти симплекс-методу
Щоб уникнути накопичення помилок округлення може використовуватися LU-розкладання ...
