logo
теория

Симплекс-таблица. Получение первого опорного решения. Последовательность оптимизации симплекс методом.

При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные xn+1, xn+2, ..., xn+m

Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b1, b2, ..., bm. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении (). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты aij при переменных системы ограничений.

Среди универсальных методов решения задач линейного программирования наиболее распространенным является симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения рассмотренного выше метода Жордана - Гаусса для системы линейных уравнений канонической формы, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи. В оптимальном плане при решении задачи на максимум все оценки в строке zj – cj должны быть положительными. При решении на минимум – отрицательными.