Методы Линейного Программирования

Возникновение линейного программирования

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

Линейное программирование применяется в следующих типах задач:

• разработка рационального плана использования сырья – оптимальный раскрой ткани, стальных и деревянных листов и т.д.
• оптимальное размещение производственных мощностей
• составление оптимального плана по перевозкам грузов
• составление рациона питания для птицы, скота и т.д.

Способы решения задач линейного программирования

Кратко расскажем о постановке задачи. Формируется какой-либо критерий оптимальности – например расходы на производство или прибыль от продаж и т.д. Составляются линейные уравнения, связывающие оптимизируемый критерий с влияющими переменными (расход электроэнергии, валовой доход и т.д.) и вводят линейные ограничения. Дело в том, что ресурсы не бесконечны, а значит нужно оптимизировать показатель с учетом ограничений. По сути, нужно добиться минимальных расходов или максимальной прибыли и т.д., учитывая при этом ограниченность ресурсов. Это и есть задача линейного программирования. Ограничения и уравнения должны быть в первой степени, то есть квадратов и кубов не должно быть, иначе это задача нелинейного программирования.

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

Практический пример применения графического метода

Пусть введена линейная функция $Y=3X+4Z$ при этом переменные подчиняются следующим ограничениям: $$ \left\{ \begin{array}{l} 0 \le X \le 6, \\ 0 \le Z \le 4. \end{array} \right. $$

• Языки Системного Программирования
• Модели Линейного Программирования
• Задачи Линейного Программирования
• Задачи Нелинейного Программирования
• Основы Визуального Программирования