4.6.4. Алгоритм симплексного метода

Рис.4.6.4.1. Алгоритм симплексного метода.

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

1 этап. Выбор начального плана:

1. Произвольно выбираются свободные переменные СП k: X₁, X₂, …,X_k, и тогда X_k+1…X_n – базисные переменные.

2. Выражается целевая функция W=f₁₁(X₁…X_k) через свободные переменные.

3. Выражаются базисные переменные через свободные переменные БП=f₂₁(СП₁) или БП=f₂₁(Х₁…Х_k).

4. Полагаются: СП₁=0 (X₁=0,…X_k=0).

5. Поскольку определена зависимость БП=f₂₁(СП₁) и W=f₁₁(СП₁), то определяются конкретные значения W₁ и БП₁ для начального плана.

2 этап. Оценка оптимального плана осуществляется на основе выражения:

+св.член или +const (1)

Для оценки плана на оптимальность необходимо проанализировать знаки всех коэффициентов уравнения (1), и если все знаки положительны, то этот план является оптимальным.

3 этап. Выбор очередного плана

1. Выбирается новый i-ый набор свободных и базисных переменных, который не совпадает с предыдущими наборами (планами)(путем замены 1-ой СП на соответственно 1 БП)

2. Выражается W_i=f_1i(СП_i).

3. Выражаются БП_i=f_2i(СП_i).

4. Полагаются СП_i=0.

5. Определяются конкретные значения базисных переменных и краевой функции для i-ого плана БП_i и W_i.

6. Осуществляется переход на блок 2.

Рассмотрим реализацию симплекс-метода на примере.

4.6.5 Пример поиска оптимального плана

Исходная постановка задачи линейного программирования.

Дано:

1. ;

2. ;

3. ;

n=6, m=4, k=2.

Формулировка задачи:

Необходимо найти такие положительные значения X₃,…,X₆, которые удовлетворяют системе ограничений (2) и обращают в минимум критерий эффективности.

Первый план

Выбираем тогда X_3,X₄,X₅,X₆ БП выбрав СП, БП, выразим критерий эффективности и ограничения, (W и БП) через СП:

1. W₍₁₎= –7X₁–5X₂=0.

2. .

3. Х₁≥0,…,Х₆≥0.

Полагаем выбранные СП равными 0 и определяем БП и W:

X₁=X₂=0, X₃=19, X₄=13, X₅=15, X₆=18, W₍₁₎=0.

Поскольку в уравнении W₍₁₎=f(СП) есть отрицательные знаки коэффициентов, то первый план не оптимален. Следовательно, переходим к новому набору СП. Если проанализировать вид целевой функции, то убедимся в том, что, увеличивая X₁ и X₂ можно достичь меньших значений критерий эффективности. Если, например, увеличивать одну из свободных переменных, например, X₂, то, анализируя уравнения для базисных переменных БП=f(СП) (2), можно убедиться в том, что X₂ можно увеличивать до определенного предела, а именно до тех пор, пока хотя бы одна из БП не станет отрицательной. В данном случае наиболее быстро приближается к опасной зоне, т.е. к зоне отрицательных значений, при возрастании Х_2, базисная переменная БП Х₅, следовательно, производим замену: из БП убираем Х₂ и на её место включаем Х₅.

Второй план:

Х₁, Х₅ → СП; Х₂, Х₃, Х₄, Х₆→БП, выражаем W и БП через СП.

1) W₍₂₎= –25–7 X₁+X₅.

2).

3) Х₁≥0,…,Х₆≥0.

Полагаем Х₁=0, Х₅=0, и определяем W₍₂₎ и БП₂ , и получаем для 2-го плана:

X₁=X₅=0, X₃=4, X₄=8, X₂=5, x₆=18, W₍₂₎= -25.

Значения W₍₂₎ стало меньше, по сравнению с 1-ым планом, но второй план также не оптимален, т.к. один из коэффициентов в уравнении W₍₂₎=f(СП) отрицателен.

Третий план.

Проводим анализ- какая БП быстрее приближается к опасной зоне при увеличении Х₁ так как знак при Х₁ отрицательный. Наиболее быстро приближается к зоне отрицательного значения БП Х₃.

Поэтому исключаем из СП Х₁, а вводим в состав СП – Х₃.

Х₃, Х₅ → СП; Х_1, Х₂, Х₄, Х₅ → БП, выражаем W и БП через СП:

1) W₍₃₎= –39+Х₁-Х₅.

2).

Полагаем Х₃=Х₅=0, и находим Х₁=2, Х₂=5, Х₄=4, Х₆=12; W₍₃₎= -39; значения W₍₃₎ меньше чем W₍₂₎, но план 3 также не оптимален, т.к. в уравнении (1) W₍₃₎= -39+(7/2)Х₃ - (11/6)Х₅

есть отрицательные коэффициенты.

Четвёртый план. Т.к отрицательный коэффициент в ЦФ W₍₃₎ при Х₅ то ее выводим из состава СП, а взамен вводим Х₄, как переменную, наиболее быстро приближающуюся к 0, при увеличении Х₅.

Х₃, Х₄→СП; Х₁, Х₂, Х₅, Х₆→БП.

1. W₍₃₎= 50 +Х₃+₄.

2. .

Х₃=Х₄=0, Х₁=5, Х₂=3, Х₅=6, Х₆=3; W₍₄₎= –50; т.к. в уравнении (1) все коэффициенты положительны, то W₍₄₎=W_min.

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