Симплексный метод решения злп
Использование графического метода (когда оптимальное решение находится с помощью геометрических построений) возможно только при решении ЗЛП с двумя переменными.
При бóльшем числе переменных необходимо применение алгебраического аппарата.
Общий метод решения ЗЛП называется симплексным (или симплекс-методом).
Идея симплекс-метода
При решении ЗЛП графическим методом было отмечено, что оптимальному решению всегда соответствует одна из угловых точек многоугольника (многогранника) решений. Именно этот результат и положен в основу симплекс-метода.
Однако исследовать все вершины многогранника решений (опорные решения) очень сложно. Отсюда естественно стремление найти такой способ перехода от данной вершины к другой, при котором значение целевой функции будет меньше (задача на минимум) или больше (задача на максимум), чем в предыдущем случае.
Переходы от одной угловой точки к другой необходимо осуществлять до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Итак, симплексный метод предполагает:
умение находить начальное опорное решение;
наличие признака оптимальности опорного решения;
умение переходить к лучшему (или, по крайней мере, не худшему) опорному решению.
Геометрическая интерпретация идеи симплекс-метода
x2
П усть имеется задача на отыскание минимального значения целевой функции
.
На рисунке изображён многоугольник её решений.
Допустим, что найдено первоначальное опорное решение, соответствующее угловой точке . Тогда прямая проходит через точку , и имеет значение .
Следующий шаг симплекс-метода обеспечивает переход в точку , где целевая функция принимает значение .
x1
Симплексный метод обеспечивает движение по соседним угловым точкам многоугольника решений, связанным с уменьшением (увеличением) значения целевой функции.
Две угловые точки называются соседними, если они расположены на одном ребре многоугольника решений.
Алгоритм симплекс-метода
Нахождение первоначального опорного решения
Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных , удовлетворяющие условиям-равенствам и обращающие в минимум линейную функцию этих переменных.
(1)
(2) . (3)
Положим, что все уравнения системы (2) являются линейно независимыми.
Равенства называются линейно независимыми, если никакое из них нельзя получить из других путём умножения на какие-то коэффициенты и суммирования, т.е. никакое из них не является следствием остальных.
В линейной алгебре доказывается, что систему из независимых равенств с переменными всегда можно разрешить относительно каких-то переменных (называемых базисными) и выразить их через остальные переменных (называемых свободными).
Свободным переменным можно придавать какие угодно значения, не нарушая условий (2) и (3).
Если свободные переменные приравнять к нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (2) будет являться опорным решением ЗЛП.
Пример.
1) Приводим данную задачу к ОЗЛП.
.
2) Разделим переменные на базисные и свободные.
Количество базисных переменных равно числу уравнений в системе ограничений:
Количество свободных переменных:
Выберем в качестве базисных переменных те дополнительные переменные, которые добавили к неравенствам, чтобы получить равенства:
.
Т.к. каждая из этих переменных входит в одно из уравнений системы ограничений с коэффициентом, равным 1, а во все остальные уравнения – с коэффициентом, равным 0, то они легко выражаются через переменные и .
3) Выразим базисные переменные и целевую функцию через свободные переменные.
4) Полагаем свободные переменные, равными нулю.
тогда
Так как то полученное решение является опорным (на графике – точка ).