Симплекс-метод Лекции 6, 7

Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает при условии, что задача имеет оптимальный план и каждый опорный план является невырожденным. Этот переход возможен, если известен какой-либо опорный план.

В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка m Тогда очевиден первоначальный опорный план( неотрицательное базисное решение системы ограничений КЗЛП).

Рассмотрим задачу, для которой это возможно. Пусть требуется найти максимальное значение функции при условиях Здесь -заданные постоянные числа, причем

Перепишем ЗЛП в векторной форме: найти максимум функции при условиях Здесь

Так как, то по определению опорного плана, где последние компоненты вектора равны нулю, является опорным планом Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным.

План, при котором целевая функция ЗЛП принимает свое максимальное (минимальное ) значение, называется оптимальным Этот план определяется системой единичных векторов, которые образуют базис m-векторного пространства. Проверка на оптимальность опорного плана происходит с помощью критерия оптимальности.

Признак оптимальности. 1)Опорный план ЗЛП является оптимальным, если для любого.

2)Если для некоторого j=k и среди чисел нет положительных, т.е., то целевая функция ЗЛП не ограничена на множестве ее планов, т.е. ЗЛП не имеет решения, так как нет конечного оптимума.

3)Если же для некоторого k выполняется условие, но среди чисел есть положительные, т.е. не все, то можно получить новый опорный план, для которого значения целевой функции. На основании признака оптимальности делаем вывод о целесообразности перехода к новому опорному плану.

Симплекс-таблица

В столбце Сб записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса. В столбце -положительные компоненты исходного опорного плана, в нем же в результате вычислений получают положительные компоненты оптимального плана. Первые m строк заполняют по исходным данным задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора - значение

Здесь, т.е. Значение После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки. Может иметь место один из 3-х случаев.

1) Все Тогда составленный план оптимален. 2) для некоторого j и все соответствующие этому j. Тогда целевая функция неограничена. 3) для некоторых индексов j и для каждого такого j по крайней мере одно из чисел положительно. Здесь можно перейти к новому опорному плану.

Этот переход осуществляется исключением из базиса какого-нибудь из векторов и включением в него другого. В базис вводим вектор, давший минимальную отрицательную величину симплекс-разности

Из базиса выводится вектор, который дает наименьшее положительное оценочное отношение для всех, т.е. минимум достигается при i=r. Число называется разрешающим элементом.

Строка называется разрешающей строкой, элементы этой строки в новой симплекс-таблице вычисляются по методу Жордана-Гаусса, т.е. по формулам:

Элементы i-й строки –по формулам

Значение нового опорного плана считают по формулам Значение целевой функции при переходе от одного опорного плана к другому, улучшенному, изменяется по формуле

Процесс решения продолжаем до получения оптимального плана либо до установления неограниченности ЦФ. Если среди оценок оптимального плана нулевые только оценки, соответствующие базисным векторам, то оптимальный план единствен. Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что опорный план не единствен.

Алгоритм применения симплекс- метода 1)Находят опорный план. 2)Составляют симплекс-таблицу. 3)Выясняют, имеется ли хотя бы одна отрицательная оценка. Если нет, то найденный опорный план оптимален. Если же есть отрицательные оценки, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.

4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом, а направляющая строка минимальным числом Q. 5)Определяют положительные компоненты нового опорного плана. Составляется новая таблица. 6)Проверяют найденный опорный план на оптимальность.

Пример. Решить симплекс-методом ЗЛП

Решение. Приведем задачу к каноническому виду, введя новые переменные В целевую функцию эти переменные войдут с нулевыми коэффициентами:

Из коэффициентов при неизвестных и свободных членов составим векторы Единичные векторы образуют единичную подматрицу и составляют базис первоначального плана. Свободные неизвестные приравниваются к нулю. Получаем первоначальный опорный план: Х= (0;0;350;240;150).

Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере Для заполнения последней строки таблицы сразу вычислим симплекс-разности Для этого поочередно умножаем столбец Сб на соответствующие элементы каждого столбца

Составим теперь нулевую симплексную таблицу

Таблица 0.

Определяем разрешающий элемент симплексной таблицы. Т.к. имеется 2 отрицательные оценки, то выбираем ту, что дает максимальную по абсолютной величине отрицательную оценку, т. е Это означает, что в базис включается вектор, а исключается из базиса тот вектор, которому соответствует.

Разрешающим элементом является. Значение целевой функции в следующей симплекс-таблице будет равно:

Элементы направляющей строки в новой таблице вычисляем, деля эту строку на ведущий элемент(в том числе и клетку в столбце план):

Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1- ю строку на (-0,5) и прибавляя ее ко 2-й, а затем на(-1) и прибавляя к 3-й, обнулив таким образом элементы 2-го выделенного (разрешающего) столбца, или по формулам треугольника

Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по формулам треугольника)

Аналогично рассчитываем элементы 3- й строки. Значения нового опорного плана рассчитываем по формулам: После чего заполняем таблицу 1.

Таблица 1.

Проверим план на оптимальность. Вычислим симплекс-разности.

В первом столбце матрицы имеется отрицательная оценка. План не оптимален, но его можно улучшить, включив в базис вектор. Найдем минимальное оценочное отношение:

Выводится из базиса вектор, которому соответствует минимальное оценочное отношение 70. Переходим к следующему опорному плану. Вводим в базис вектор, делим разрешающую строку на разрешающий элемент и заполняем 3-ю строку таблицы 2. После чего методом Жордана-Гаусса домножаем эту строку на (-0,286) и прибавляем к первой, затем домножим эту строку на (-1,857) и прибавляем ко второй.

Таблица 2

Вычисляем симплекс-разности. План оптимален. Значение целевой функции