Ваулина В. А., УрГЭУ Пример решения задачи линейного программирования графическим методом Линейное программирование - это раздел математики, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями. Существуют два наиболее распространенных способа решения задач линейного программирования: графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания решения. Также этот метод позволяет практически одновременно найти решение на минимум и максимум. Основные шаги по решению ЗПЛ графическим методом следующие: построить область допустимых решений задачи (выпуклый многоугольник), который определяется как пересечение полуплоскостей, соответствующих неравенствам задачи, построить линию уровня целевой функции, и, наконец, двигать линию уровня в нужном направлении, пока не достигнем крайней точки области - оптимальной точки (или множества). В отличие от графического метода, симплексный метод практически не имеет ограничений на задачу, может быть любое количество переменных и т.п. При решении задачи симплексным методом вычисления ведутся в таблицах. Решение задачи данным методом дает не только оптимальное решение, но и решение двойственной задачи, остатки ресурсов и т.п. Рассмотрим решение задачи линейного программирования графическим методом. Для производства столов и стульев мебельная фабрика использует три вида древесины. Норма затрат для каждого вида древесины на один стол составляет 1; 2; 5; на один стул – 1; 5; 2. Запасы древесины – 150; 600; 600. Прибыль от реализации одного стола – 200р, одного стула – 100р. Составить оптимальный план производства, обеспечивающий максимальную прибыль. Решение. Составим математическую модель задачи. Пусть Х - столы, У - стулья, I,II,III – виды древесины соответственно. I II III Прибыль X 1 2 5 200 Y 1 5 2 100 150 600 600 Общий запас Составим неравенства по полученной таблице: { x 1+ x2 ≤150, 2 x 1+5 x 2 ≤600, 5 x 1 +2 x 2 ≤600, x1,2 ≥ 0. } F ( x )=200 x 1+100 x 2 → max Применим описанные выше шаги решения. Построим область допустимых решений. Рассмотрим целевую функцию задачи F = 200x1+100x2 → max и построим вектор-градиент, составленный из коэффициентов целевой функции. Так как нас интересует максимальное решение, то опорную прямую двигаем прямую до последнего касания обозначенной области. Получаем оптимальную точку D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых: x1+x2=150 5x1+2x2=600 Решив систему уравнений, получим: x1 = 100, x2 = 50 Откуда найдем максимальное значение целевой функции: F(X) = 25000. На примере данной задачи мы рассмотрели решение задачи линейного программирования графическим методом. Этот метод наглядно показывает область дополнительных решений и нахождение оптимальной точки. Руководитель: Кныш А.А.