2015-04-01
2884
Графический метод решения ЗЛП
Графическим методом можно решать задачи, заданные в неканоническом виде с двумя переменными или сводящиеся к ним. Рассмотрим задачу следующего вида: найти экстремум функции
при ограничениях:
х 1>0, х 2>0.
Надо построить область допустимых решений системы ограничений. При этом возможны случаи:
1) область допустимых решений - пустое множество;
2) область допустимых решений - единственная точка;
3) область допустимых решений - выпуклый многоугольник;
4) область допустимых решений - выпуклая неограниченная область.
В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.
Во втором случае - это единственное решение и будет оптимальным решением.
В третьем случае, чтобы найти оптимальное решение задачи, можно найти координаты всех угловых точек многоугольника, вычислить значения целевой функции во всех угловых точках. Наибольшее из этих значений и будет максимальным значением целевой функции, а наименьшее - минимальным, а координаты соответствующей угловой точки - оптимальным решением.
|
|
|
Существует другой способ, который позволяет графически сразу найти угловую точку, соответствующую оптимальному решению.
Пусть с 0 - некоторое число. Прямая 
является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное с 0. Вектор - градиент целевой функции
перпендикулярен к линиям уровня и показывает направление, в котором эта функция возрастает с наибольшей скоростью. Выбирая из линий уровня, проходящих через область допустимых решений, наиболее удаленную в направлениях вектора 
(в случае минимизации - в противоположном направлении), определим угловую точку, в которой целевая функция принимает максимальное (минимальное) значение.
Если экстремум достигается в двух угловых точках, то, по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка, соединяющего эти точки:
, 
.
В четвертом случае, когда область допустимых решений системы ограничений задачи неограниченная выпуклая область, оптимальное решение находится аналогично описанному выше. В данном случае оптимальное решение может совпадать с одной угловой точкой, с двумя угловыми точками и оптимальное решение может и не существовать из-за неограниченности целевой функции сверху в задаче на максимум или снизу в задаче на минимум.
Пример 1. Решить графически следующую задачу:
,
х 1 >0, х 2 >0.
Построим область допустимых решений системы ограничений:
Х 2
30 А
В
С
D Х 1
40 50 80
l 2 l 1
l 3
Областью допустимых решений системы ограничений является выпуклый пятиугольник ОАВCD.
|
|
|
Построим вектор 
и линию уровня, перпендикулярную вектору 
. Наибольшее значение целевая функция достигает в угловой точке В. Найдем координаты точки В, для этого решим систему из уравнений первой и второй прямой.
Решая систему, получим: 
, 
.
Пример 2. Найти наибольшее и наименьшее значения функции
при ограничениях:
х 1+ х 2 > 8,
-5 х 1+2 х 2 < 10,
х 1-3 х 2 < 0,
х 1 >0, х 2 >0
Построим ОДР.
Областью допустимых решений системы ограничений является выпуклая многоугольная неограниченная область. Наименьшее значение целевой функции достигается в угловой точке А, а наибольшее значение функции найти нельзя, так как функция не ограничена сверху, т.е. max L = ∞.
Найдем координаты точки А, для этого решим систему из уравнений первой и третьей прямой:
х 1+ х 2 = 8,
х 1-3 х 2 =0
х 1 = 6, 
х 2 = 2.
т.е. 
.
