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

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

При бóльшем числе переменных необходимо применение алгебраического аппарата.

Общий метод решения ЗЛП называется симплексным (или симплекс-методом).

Идея симплекс-метода

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

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

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

Итак, симплексный метод предполагает:

1. умение находить начальное опорное решение;

2. наличие признака оптимальности опорного решения;

3. умение переходить к лучшему (или, по крайней мере, не худшему) опорному решению.

Геометрическая интерпретация идеи симплекс-метода

x₂

П усть имеется задача на отыскание минимального значения целевой функции

.

На рисунке изображён многоугольник её решений.

Допустим, что найдено первоначальное опорное решение, соответствующее угловой точке . Тогда прямая проходит через точку , и имеет значение .

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

x₁

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

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

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

Алгоритм симплекс-метода

1. Нахождение первоначального опорного решения

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

(1)

(2) . (3)

Положим, что все уравнения системы (2) являются линейно независимыми.

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

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

Свободным переменным можно придавать какие угодно значения, не нарушая условий (2) и (3).

Если свободные переменные приравнять к нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (2) будет являться опорным решением ЗЛП.

Пример.

1) Приводим данную задачу к ОЗЛП.

.

2) Разделим переменные на базисные и свободные.

Количество базисных переменных равно числу уравнений в системе ограничений:

Количество свободных переменных:

Выберем в качестве базисных переменных те дополнительные переменные, которые добавили к неравенствам, чтобы получить равенства:

.

Т.к. каждая из этих переменных входит в одно из уравнений системы ограничений с коэффициентом, равным 1, а во все остальные уравнения – с коэффициентом, равным 0, то они легко выражаются через переменные и .

3) Выразим базисные переменные и целевую функцию через свободные переменные.

4) Полагаем свободные переменные, равными нулю.

тогда

Так как то полученное решение является опорным (на графике – точка  ).