Ваулина В. А.,
УрГЭУ
Пример решения задачи линейного программирования
графическим методом
Линейное программирование - это раздел математики, в котором
рассматриваются методы решения экстремальных задач с линейным
функционалом и линейными ограничениями.
Существуют два наиболее распространенных способа решения задач
линейного
программирования: графический
метод и симплекс-метод.
Графический метод существенно нагляднее и обычно проще для понимания
решения. Также этот метод позволяет практически одновременно найти
решение на минимум и максимум.
Основные шаги по решению ЗПЛ графическим методом следующие:
построить область допустимых решений задачи (выпуклый многоугольник),
который определяется как пересечение полуплоскостей, соответствующих
неравенствам задачи, построить линию уровня целевой функции, и, наконец,
двигать линию уровня в нужном направлении, пока не достигнем крайней
точки области - оптимальной точки (или множества).
В отличие от графического метода, симплексный метод практически не
имеет ограничений на задачу, может быть любое количество переменных и
т.п. При решении задачи симплексным методом вычисления ведутся в
таблицах. Решение задачи данным методом дает не только оптимальное
решение, но и решение двойственной задачи, остатки ресурсов и т.п.
Рассмотрим
решение
задачи
линейного
программирования
графическим методом.
Для производства столов и стульев мебельная фабрика использует три
вида древесины. Норма затрат для каждого вида древесины на один стол составляет 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.
На примере данной задачи мы рассмотрели решение задачи линейного
программирования графическим методом. Этот метод наглядно показывает
область дополнительных решений и нахождение оптимальной точки.
Руководитель: Кныш А.А.
Отзывы:
Авторизуйтесь, чтобы оставить отзыв