Симплексный метод решения задачи

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

• 1) не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный;
• 2) множество всех допустимых решений (планов) задачи линейного программирования выпукло;
• 3) целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек;
• 4) каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метода с естественным базисом

Для применения этого метода ЗЛП должна быть сформулирована в канонической форме (2.12)-(2.14), причем матрица системы уравнений должна содержать единичную подматрицу размером т x т. В этом случае очевиден начальный опорный план (неотрицательное базисное решение).

Для определенности предположим, что первые т векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден ;

Проверка на оптимальность опорного плана проходит с помощью критерия (признака) оптимальности, переход к другому опорному плану — с помощью преобразований Жордана — Гаусса и с использованием признака оптимальности.

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

Признак оптимальности заключается в следующих двух теоремах.

Теорема 2.3. Если для некоторого вектора, не входящего в базис, выполняется условие.

(2.22).

то можно получить новый опорный план, для которого значение целевой функции будет больше исходного; при этом могут быть два случая:

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

Теорема 2.4. Если для всех векторов выполняется условие.

то полученный опорный план является оптимальным.

На основании признака оптимальности в базис вводится вектор A_r,, давший минимальную отрицательную величину симплекс-разности:

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А_р который дает минимальное положительное оценочное отношение.

(2.23).

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

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

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

Следует заметить, что зацикливание в симплекс-методе может иметь место также и в случае так называемого вырождения. При т ограничениях ЗЛП значения т базисных переменных, как правило, положительны, а значения остальных п — т свободных переменных всегда равны нулю. Однако возможно равенство нулю одной или нескольких базисных переменных; такой план называется вырожденным.

Вычисляемые по формуле (2.22) величины ?_j называются симплексными разностями, или оценками, соответствующих переменных.

Так как в основе симплекс-метода лежит метод Жордана — Гаусса для системы линейных уравнений канонической формы ЗЛП, то при расчетах рекомендуется визуально проверять выполнение вытекающих из этого признаков: столбцы базисных векторов в симплексных таблицах имеют вид соответствующих столбцов единичной матрицы, а оценки базисных переменных всегда равны нулю.

Строка А_r называется направляющей, столбец А_к и элемент a_rk — направляющими (последний называют также разрешающим элементом и в сиплекс-таблицах выделяют рамкой).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам.

(2.24).

а элементы любой другой i-й строки пересчитываются по формулам.

(2.25).

В соответствии с (2.24) и (2.25) значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам.

Таким образом, пересчет симплексных таблиц по формулам (2.24) и (2.25) проводится с помощью двух вычислительных процедур.

Процедура 1. Элементы вновь вводимой строки получаются путем деления элементов выводимой строки предыдущей таблицы на разрешающий (выделенный рамкой) элемент.

Процедура 2. Элементы других строк рассчитываются на базе преобразований Жордана — Гаусса, при этом целесообразно использовать так называемое правило прямоугольного треугольника. Суть этого правила заключается в том, что для расчета некоторого элемента новой таблицы (кроме элементов вновь вводимой строки) нужно выделить три числа:

• 1) соответствующий элемент (т.е. стоящий на том же месте) предыдущей таблицы;
• 2) элемент этой же строки предыдущей таблицы, стоящий в направляющем столбце;
• 3) элемент вновь введенной строки новой таблицы, стоящий в том же столбце, что и определяемый элемент. По своему расположению в таблицах эти три числа образуют прямоугольный треугольник, и для определения искомого элемента нужно из первого числа (стоящего в вершине прямого угла) вычесть произведение двух других чисел (стоящих в вершинах острых углов).

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

Рассмотрим алгоритм симплекс-метода на конкретной задаче.

Пример 2.7. Для производства продукции типа П, и П₂ предприятие использует два вида сырья: С, и С₂ Данные об условиях производства продукции приведены в табл. 2.1.

Таблица 2.1

Данные об условиях производства

Составить план производства по критерию «максимум прибыли» .

Решение. Введем необходимые обозначения. Обозначим объем производства продукции П₁ через х₁, продукции П₂ через х₂. Таким образом, формально (математически) план производства (производственная программа) — это вектор . С учетом введенных обозначений математическая модель задачи по критерию «максимум прибыли» имеет вид.

при ограничениях.

Приведем эту ЗЛП к каноническому виду, введя дополнительные переменные х₃ и х₄:

или.

КЗЛП имеет необходимое число единичных столбцов, т. е. обладает очевидным начальным опорным планом (0, 0, 300, 150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах (табл. 2.2).

В исходной симплекс-таблице с номером 0 строка оценок определяется по приведенной выше формуле (2.22):

Исходный опорный план (0, 0, 300, 150) не является оптимальным, так как среди оценок ?_j имеются отрицательные. Переход к новому опорному плану осуществим, введя в базис вектор А₂, имеющий минимальную отрицательную оценку. Определяем вектор, выходящий из базиса:

т.е. вектор А₃ следует вывести из базиса. Разрешающим элементом является а₁₂ = 3 (выделен рамкой). Переход к следующей симплекс-таблице осуществляем с помощью преобразований Жордана — Гаусса, при этом рекомендуется пользоваться двумя описанными выше вычислительными процедурами симплексного метода, включая правило прямоугольного треугольника.

Таблица 2.2

Решение ЗЛП в симплекс-таблицах

Второй опорный план (0, 100, 0, 50) не оптимальный; переход к следующему опорному плану осуществим, вводя в базис вектор A₁ и выводя вектор А₄.

В симплекс-таблице II получен оптимальный опорный план, поскольку все симплекс-разности (оценки) Оптимальные значения переменных равны: (основные переменные), (дополнительные переменные).

Максимальное значение целевой функции равно 375.

Таким образом, в рассмотренной задаче об оптимальном использовании ограниченных ресурсов, оптимальная производственная программа состоит в выпуске 75 ед. продукции первого вида и 75 ед. продукции второго вида. С этой программой связана максимальная прибыль от реализации готовой продукции — 375 у.е.