Графический метод решения задачи ЛП

Решим задачу (12) графическим методом. Для этого построим многогранник допустимых планов задачи (в данном двухмерном случае это многоугольник). Уравнения границ МДП получаются из 4-х последних строк (12) заменой в них знаков неравенства на “=”:

(13)

Это уравнения прямых, причём два последних – осей Оу и Ох. Построим эти прямые, пользуясь тем, что любую прямую можно провести, если известны две её различные точки. Одна из этих точек может быть получена как пересечение с осью Оу (при этом надо положить х =0 и найти у), а другая - как пересечение с осью Ох (при этом надо положить у =0 и найти х). Проиллюстрируем это на примере первого уравнения прямой в (13):

Точка пересечения с осью Ох имеет координаты (х, 0)Þ4 х+ 6×0=2400Þ х =²⁴⁰⁰/₄=600.

Точка пересечения с осью Оу имеет координаты (0,у)Þ4×0 + 6 у =2400Þ у =²⁴⁰⁰/₆=400.

Таким образом, первая прямая проходит через точки (600,0) и (0,400).

Произведя аналогичные вычисления для оставшихся двух прямых из (13) и проведя необходимые графические построения, получим МДП, изображённый на рис.3 (он заключён между прямыми всех ограничений). Для проверки совместности всех ограничений достаточно взять любую точку внутри МДП (например (100,100)) и подставить её координаты в ограничения (12). Если все они выполнились (знак неравенства верен), то ограничения совместны и МДП построен правильно. В нашем случае получаются следующие неравенства:

4×100+6×100=1000£2400,

2×100+1×100=300£800,

1×100+3×100=400£900,

100³0; 100³0.

Так как все они являются верными числовыми неравенствами, то МДП на рис.3 получен верно.

найдём теперь оптимальный план методом линий постоянного уровня. Для этого построим линию постоянного уровня (как было отмечено выше в разделе описания способов решения задачи ЛП, все линии постоянного уровня данной задачи – параллельные прямые, а значит, достаточно построить одну). Представленная на рис.3 линия постоянного уровня проведена через точку пересечения прямой третьего ограничения с осью Ох с координатами (900,0). Значение целевой функции в этой точке равно 900×5+0×5=4500. Это и есть значение L₀ в уравнении линии постоянного уровня. Само уравнение принимает вид 5 х +5 у =4500. Для построения прямой достаточно найти точку её пересечения с осью Оу: 5×0+5 у =4500Þ у =⁴⁵⁰⁰/₅=900. Т.о. координаты второй точки прямой постоянного уровня – (0,900). Через эти две точки она и проведена на рис.3. Так как все линии постоянного уровня параллельны, то сдвигая эту линию в направлении начала координат, можно получить любую другую линию постоянного уровня с значением L₀, меньшим 4500 (значение L₀ возрастает с удалением линии постоянного уровня вправо от начала координат, т.к. коэффициенты при х и у в данном случае положительны). Передвигая таким образом линию постоянного уровня, можно найти точку опорного плана на максимизацию, в которой она коснётся МДП. На рис.3 это точка с координатами (300,200). В ней и находится искомый оптимальный план, дающий максимальную прибыль в задаче (12). Эта точка действительно является оптимальной потому, что линии постоянного уровня целевой функции, проходящие выше неё, не имеют общих точек с МДП, содержащим допустимые планы задачи (12). Проходящие же ниже неё линии постоянного уровня имеют меньшие значения L₀, о чём свидетельствует и тот факт, что они пересекают МДП не только в граничных, но и во внутренних точках, а оптимальные планы, как отмечалось выше, достигаются в задаче ЛП только в граничных точках.

Теперь найдём оптимальный план градиентным методом. Вектор градиента , как отмечалось выше, в случае двумерной задачи линейного программирования имеет координаты (с₁,с₂), и в задаче (12) – (5,5). На рис.3 изображён, из соображений масштаба, вектор 100grad(L)=(500,500). Видно, что наиболее удалённой от начала координат в направлении этого вектора оказывается уже найденная выше вершина (300,200) – она и есть решение. Для проверки этого достаточно через неё провести прямую, перпендикулярную вектору градиента – эта прямая будет линией постоянного уровня, пересекающей МДП в крайней точке, а сама эта точка – опорным планом на максимизацию.