Решение задач линейного программирования 3 (стр. 3 из 6)
Если в задаче на максимум коэффициенты целевой функции удовлетворяет условию:
в задаче на минимум:
, то базисный план, соответствующий симплексной таблице является оптимальным и решение ЗПП окончено. 
Допустим, что достаточное условие оптимальности не выполняется. В этом случае найдем максимальный по модулю, не удовлетворяющий условию оптимальности, коэффициент целевой функции. Соответствующую переменную назовем ведущей. Этот индекс обозначен через j*. Соответствующий столбец симплексной таблицы назовем ведущим.
2 этап: вычисление оптимально допустимого шага.
Из системы основных ограничений симплексной формы следует:
Из 
вытекает, что
(3.7)Очевидно, что соотношение (7) может нарушаться только в том случае, если
, поэтому для каждой базисной переменной 
: 
, то соответствующая базисная переменная ни при каком значении 
не обращается в ноль.Максимально допустимый шаг определим как минимум из чисел
. 
возможны 2 случая:
1.
Это означает, что шаг
может быть бесконечно большим. Соответственно значение целевой функции может неограниченно возрастать, если задача на максимум, или неограниченно убывать, если задача на минимум. С экономической точки зрения такая ситуация свидетельствует о несоответствии математической модели реальной экономической модели (неучтены или неправильно учтены ограничения задачи). Решение ЗПП при этом считается законченным.2.
(конечное число) 
называется ведущей или разрешающей переменной.3 этап: преобразование симплексной таблицы.
Как уже отмечалось в пункте 1,
должна выводиться из базиса, на ее место вводится переменная 
— небазисная.Нарисуем новую симплексную таблицу.
| б\н | b | | … | | … | |
| | | | … | R | … | r |
| | | | … | | … | |
| … | … | … | … | … | … | |
| | | | … | | … | |
| … | … | … | … | … | … | |
| | | | | |
(3.8) 
(3.9)
(3.10) 
(3.11)Правила:
1)
На место ведущего элемента в новой таблице записывается элемент, обратный ведущему.
2)
, 
Правило: новые элементы ведущей строки вычисляются по старым элементам делением последних на ведущий элемент, взятый с противоположным знаком.
i — номер произвольной строки.
3)
Элементы ведущего столбца получаются из старых элементов делением последних на ведущий элемент.
4)
, 
, 
| j | j* проекция | ||
| i | rij | … | rij* |
| … | … | … | |
| i* проекция | ri*j | … | ri*j* |
Новый элемент симплексной таблицы, не находящийся в ведущей строке или столбце, получается из старого, если вычесть из последнего произведение его проекций деленное на ведущий элемент.