Симплексный метод решения задач линейного программирования
Трудно переоценить важность задач линейного программирования для современной экономики и промышленности. Однако графический метод, хотя и обладает простотой, не может использоваться в прикладных целях из-за его ограниченности. Поэтому популярным стал симплексный метод, позволяющий решать задачи любой сложности и размерности.
Истоки симплексного метода и его суть
Симплекс-метод решения задач линейного программирования был разработан американским математиком Джорджем Данцигом. Также большой вклад в его развитие внесли ученые Кун и Таккер, более известные своими разработками в области нелинейного программирования.
Суть симплексного метода состоит в следующем: необходимо максимизировать (соответственно минимизировать) некий критерий при наложенных линейных ограничениях. Этим критерием может выступать валовой доход от реализации продукции, совокупные операционные расходы на производство товаров и так далее.
При этом на переменные, влияющие на значение критерия, накладываются линейные ограничения в виде уравнений или неравенств. По существу, симплекс-метод – это усовершенствованный графический методрешения задач ЛП в многомерном пространстве.
Подобно тому, как графический метод ищет оптимум в вершинах многоугольника, в симплексном методе оптимум ищется в вершинах n-мерного многогранника, называемого симплексом (см. на рисунке условное изображение симплекса; красным показан путь из опорной точки к точке оптимума).
Алгоритм симплекс-метода
Последовательность действий можно описать следующим образом:
- путем преобразований система ограничений приводится к необходимой, так называемой базисной, форме;
- находится так называемое опорное решение, служащее «точкой отсчета»;
- последовательно перебираются вершины симплекса. Если в данной точке значение критерия больше (или меньше) предыдущего, то процесс продолжается. Когда значение критерия уже нельзя улучшить, значит, решение найдено.
То есть, смысл симплексного метода следующий: все линейные неравенства, которым в многомерном пространстве соответствуют полуплоскости, ограничивают некий симплекс. При этом уравнению, описывающему оптимизируемый критерий, соответствует гиперплоскость. Теперь нужно просто найти ту вершину симплекса, одновременно принадлежащую этой гиперплоскости, координаты которой максимизируют (минимизируют) критерий. Следовательно, выбирается базисная вершина и по ней мы передвигаемся от одной вершины к другой, пока не найдем точку оптимума.
Практический пример применения симплексного метода
Решим симплексным методом задачу. Максимизируем функцию $$L=X+Z \rightarrow \max$$ при ограничениях $$ \left\{ \begin{array}{l} Y-X+Z=1,\\ X-2Z+T=2. \end{array} \right. $$ У нас есть четыре переменные – $X, Y, Z, T$ – причем критерий зависит лишь от двух переменных. Примем $Т$ и $Y$ за базисные переменные и выразим их через остальные две свободные переменные. Получим:
$$L=X+Z \rightarrow \max,$$ $$ \left\{ \begin{array}{l} Y=1+X-Z,\\ T=2-X+2Z. \end{array} \right. $$При $X$ и $Z$ равных нулю, базисные переменные равны $Y=1, T=2$. Значение критерия $L=0$. Значит, точка $(1,0,0,2)$ является базисным решением. Начнем перебор вершин симплекса. Увеличить критерий можно увеличив $Z$ до единицы. Тогда при $Z=1, X=0$ базисные переменные примут значения $Y=0, T=4$. Новое допустимое решение – это точка $(0,0,1,4)$, критерий равен $L=1$.
Теперь выразим $Z$ и $T$ через $Y$ и $X$:
$$L=1-Y+2X \rightarrow \max,$$ $$ \left\{ \begin{array}{l} Z=1-Y+Z,\\ T=4-2Y+X. \end{array} \right. $$Увеличить $L$ можно только увеличив $X$. Однако $X$ можно увеличивать бесконечно, исходня из системы уравнений. Следовательно, критерий $L$ будет принимать неограниченно большие значения, решения задачи симплекс-методом не существует. В этом случае говорят, что имеет случай бесконечного симплекса.
Другие примеры решения задач линейного программирования вы найдете в разделе: Задачи линейного программирования с решениями (десятки примеров!).
Дополнительно:
