Поиск по сайту

Решение задач линейного программирования графическим методом online

Задание. Решить графическим методом следующие задачи линейного программирования. Найти max и min функции F при ограничениях:
F = 9x1+6x2 → max.
6x1+15x2≤30(1)
18x1+9x2≤36(2)
x1≥0(3)
x2≥0(4)

Решение.

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

Рисунок 1 - Решение задач линейного программирования графическим методом

Границы области допустимых решений

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рисунок 2 - Решение задач линейного программирования графическим методом

Рассмотрим целевую функцию задачи F = 9x1+6x2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 9x1+6x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Рисунок 3 - Пример решения графическим методом

Равный масштаб

Рисунок 4 - Линейное программирование. Графический метод

Область допустимых решений представляет собой многоугольник.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
6x1+15x2≤30
18x1+9x2≤36

Решив систему уравнений, получим: x1 = 1.25, x2 = 1.5
Откуда найдем максимальное значение целевой функции:
F(X) = 9*1.25 + 6*1.5 = 20.25