Обзор методов решения задач линейного программирования
Стремительное проникновение математических методов во все сферы жизни, в том числе и в экономику, требует прочного знания математики и ее основных разделов. Поэтому на сегодняшний день решение задач линейного программирования является важным элементом в подготовке экономистов.
Возникновение линейного программирования
Линейное программирование возникло в начале прошлого века трудами советского математика Леонида Канторовича. Крупный вклад в развитие этого направления внес также американец Джордж Данциг, разработавший универсальный симплекс-метод решения задач линейного программирования.
Линейное программирование применяется в следующих типах задач:
- разработка рационального плана использования сырья – оптимальный раскрой ткани, стальных и деревянных листов и т.д.
- оптимальное размещение производственных мощностей
- составление оптимального плана по перевозкам грузов
- составление рациона питания для птицы, скота и т.д.
Способы решения задач линейного программирования
Кратко расскажем о постановке задачи. Формируется какой-либо критерий оптимальности – например расходы на производство или прибыль от продаж и т.д. Составляются линейные уравнения, связывающие оптимизируемый критерий с влияющими переменными (расход электроэнергии, валовой доход и т.д.) и вводят линейные ограничения. Дело в том, что ресурсы не бесконечны, а значит нужно оптимизировать показатель с учетом ограничений. По сути, нужно добиться минимальных расходов или максимальной прибыли и т.д., учитывая при этом ограниченность ресурсов. Это и есть задача линейного программирования. Ограничения и уравнения должны быть в первой степени, то есть квадратов и кубов не должно быть, иначе это задача нелинейного программирования.
Перейдем к решению задачи линейного программирования – разберем простой и понятный графический способ. Проводятся прямые линии, уравнения которых задаются ограничениями. В результате получится многоугольник, в одной из вершин которого критерий оптимальности достигнет максимума (минимума). Координаты всех вершин по очереди подставляются в уравнение, описывающее оптимизируемый критерий. Самое большое (маленькое) значение и будет оптимумом.
Практический пример применения графического метода
Пусть введена линейная функция $Y=3X+4Z$ при этом переменные подчиняются следующим ограничениям: $$ \left\{ \begin{array}{l} 0 \le X \le 6,\\ 0 \le Z \le 4. \end{array} \right. $$
Найдем значения $X$ и $Z$, при которых $Y$ будет максимальным. Строим математическую модель: $$Y=3X+4Z \rightarrow \max,$$ $$ \left\{ \begin{array}{l} 0 \le X \le 6,\\ 0 \le Z \le 4. \end{array} \right. $$ Рисуем прямую линию $3X+4Z=0$ или $Z=-3/4 X$. Параллельным переносом в направлении градиента этой функции $n=(3,4)$ к правой верхней вершине полученного прямоугольника допустимых решений мы получим точку $(6,4)$. В этой точке функция $Y$ имеет максимальное значение, равное $Y_{max}=34$.
Другие более подробные примеры по разным темам собраны на странице: Задачи линейного программирования с решениями онлайн.
Дополнительно:
