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

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

400 х₁+500 х₂ = 14 100, (1).

х₁ = 19, (2).

х₂ = 17, (3).

х₁ = 0, (4).

х₂ = 0. (5).

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями. Точки, удовлетворяющие ограничениям х₁ 0, х₂ 0, находятся в первом квадранте.

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: при х₁ = 0, х₂ = 28,2, а при х₂ = 0, х₁ = 35,25. Дале определяем, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку О (0,0) и подставим ее координаты в неравенство — оно удовлетворяется. Так как точка О (0,0) лежит левее первой прямой, то и полуплоскость будет находится левее прямой 400 х₁+500 х₂ = 14 100. На рисунке 2.1 расположение полуплоскости относительно первой прямой отмечено стрелками.

Прямые 2-я и 3-я параллельны координатным осям. Точка О (0,0) лежит левее прямой х₁ = 19 и ниже прямой х₂ = 17. Расположение полуплоскостей также отмечено стрелками на рисунке 2.1.

Множество точек, удовлетворяющих всем ограничениям одновременно, является областью допустимых решений (ОДР) системы ограничений. На графике (рис. 2.1) это многоугольник ОАВС.

Любая точка многоугольника решений удовлетворяет системе ограничений задачи и, следовательно, является ее решением. Это говорит о том, что данная задача имеет множество допустимых решений, т. е. многовариантна. Необходимо найти решение, обеспечивающее максимальную грузоподъемность при покупке автомашин.

Приравняем функцию к нулю и построим соответствующую прямую. Вектор-градиент прямой 3х₁+5х₂ = 0 имеет координаты = (3;5). Изобразим вектор на графике и построим прямую перпендикулярно этому вектору. Перемещая прямую функции параллельно самой себе в направлении вектора, увидим, что последней точкой многоугольника решений, которую пересечет прямая функции, является угловая точка В с координатами (14;17). Следовательно, в точке В функция достигает максимального значения. Чтобы достичь этого значения грузоподъемности, предприятию необходимо приобрести 14 трехтонных грузовиков и 17 пятитонных.