2015-03-22
459
Приведенные выше этапы решения задач линейного программирования симплексным методом изложены в последовательности, отличающейся от реального алгоритма, но удобной с методической точки зрения. Фактически алгоритм и программа симплексного метода предусматривают другую последовательность.
На первом этапе осуществляется перевод базисных нулей в число свободных и базисные переменные выражаются через свободные переменные. Это реализуется с помощью преобразования симплекс-таблицы по единому алгоритму преобразования, включающему поиск разрешающего элемента, пересчет симплекс-таблицы и обмен в обозначениях базисных и свободных переменных, как это показано на рисунке.
На втором этапе ищется опорное (базисное) решение и с помощью преобразования симплекс-таблицы исключаются отрицательные элементы в столбце свободных членов, при этом проверяется совместность системы ограничений.
На третьем этапе производится преобразование симплекс-таблицы для поиска оптимального решения и это продолжается до тех пор, пока все коэффициенты в строке целевой функции не станут положительными. В случае невозможности этого преобразования, т. е. если в столбце над отрицательным коэффициентом целевой функции нет положительных элементов, то выдается сообщение о том, что оптимального решения в данной задаче не существует.
6. Исследование решения задач линейного
