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

 

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

Графическим методом можно решать задачи, заданные в неканоническом виде с двумя переменными или сводящиеся к ним. Рассмотрим задачу следующего вида: найти экстремум функции

при ограничениях:

х₁>0, х₂>0.

Надо построить область допустимых решений системы ограничений. При этом возможны случаи:

1) область допустимых решений - пустое множество;

2) область допустимых решений - единственная точка;

3) область допустимых решений - выпуклый многоугольник;

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

В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.

Во втором случае - это единственное решение и будет оптимальным решением.

В третьем случае, чтобы найти оптимальное решение задачи, можно найти координаты всех угловых точек многоугольника, вычислить значения целевой функции во всех угловых точках. Наибольшее из этих значений и будет максимальным значением целевой функции, а наименьшее - минимальным, а координаты соответствующей угловой точки - оптимальным решением.

Существует другой способ, который позволяет графически сразу найти угловую точку, соответствующую оптимальному решению.

Пусть с₀ - некоторое число. Прямая является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное с₀. Вектор - градиент целевой функции

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

Если экстремум достигается в двух угловых точках, то, по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка, соединяющего эти точки:

, .

В четвертом случае, когда область допустимых решений системы ограничений задачи неограниченная выпуклая область, оптимальное решение находится аналогично описанному выше. В данном случае оптимальное решение может совпадать с одной угловой точкой, с двумя угловыми точками и оптимальное решение может и не существовать из-за неограниченности целевой функции сверху в задаче на максимум или снизу в задаче на минимум.

Пример 1. Решить графически следующую задачу:

,

х₁ >0, х₂ >0.

 

Построим область допустимых решений системы ограничений:

Х₂

 

 

 

30 А

В

С

D Х₁

40 50 80

l₂ l₁

l₃

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

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

Решая систему, получим: , .

Пример 2.Найти наибольшее и наименьшее значения функции

при ограничениях:

х₁+х₂ > 8,

-5х₁+2х₂ < 10,

х₁-3х₂ < 0,

х₁ >0, х₂ >0

Построим ОДР.

Областью допустимых решений системы ограничений является выпуклая многоугольная неограниченная область. Наименьшее значение целевой функции достигается в угловой точке А, а наибольшее значение функции найти нельзя, так как функция не ограничена сверху, т.е. max L = ∞.

Найдем координаты точки А, для этого решим систему из уравнений первой и третьей прямой:

х₁+х₂ = 8,

х₁-3х₂ =0

х₁ = 6,

х₂ = 2.

т.е. .