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

Графическим методом целесообразно решать ЗЛП, содержащие не более двух переменных.

Алгоритм графического метода рассмотрим применительно к задаче:

3x₁ + 2x₂ (2.50)

при

x₁ + 2x₂ 6 (а)

2x₁ + x₂ 8 (б)

Р = x₁+0, 8x₂ 5 (в) (2.51)

-x₁ + x₂ 1 (г)

x₂ 2 (д)

x₁ 0, x₂ 0 (е)

Шаг 1. Строим область допустимых решений (2.51) – область Р, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каждое из неравенств (а)–(д) системы ограничений (2.51) задачи геометрически определяет полуплоскость соответственно с граничными прямыми:

x₁ + 2x₂ = 6 (а)

2x₁ + x₂= 8 (б)

x₁+0, 8x₂= 5 (в)

-x₁ + x₂= 1 (г)

x₂= 2 (д)

Условия неотрицательности переменных (е) ограничивают область допустимых решений первым квадратом. Области, в которых выполняются соответствующие ограничения (2.51) в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных (рис. 2.1).

Рис. 2.1

Если система неравенств (2.51) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям.

Полученная таким образом область допустимых решений Р – планов ЗЛП (см. рис. 2.1) есть многоугольник ABCDEF – замкнутое, ограниченное, выпуклое множество с шестью крайними, или угловыми, точками: A, B, C, D, E, F.

Шаг 2. Строим вектор-градиент линейной функции , указывающий направления возрастания функции .

Шаг 3. Строим прямую с₁x₁ + c₂x₂ = const – линию уровня функции , перпендикулярную вектору-градиенту :

3x₁ + 2x₂ = const (рис.2.2).

Рис. 2.2

Шаг 4. В случае максимизации передвигают прямую 3x₁ + 2x₂ = const в направлении вектора до тех пор, пока она не покинет область Р. Крайняя точка (определение 2.12) (или точки) области, в которой линия уровня покидает допустимую область, и является решением задачи (рис. 2.3).

Рис. 2.3

Крайняя точка С – точка максимума , С = лежит на пересечении прямых (а) и (б). Для определения ее координат решим систему уравнений:

x₁ + 2x₂ = 6

2x₁ + x₂ = 8.

Откуда x^*₁ = 10/3; x^*₂ = 4/3 или = (10/3; 4/3).

Подставляя значения x^*₁ и x^*₂ в функцию , найдем

max = = 3 ^. 10/3 + 2 ^. 4/3 = 38/3.

Замечания.

1. В случае минимизации прямую c₁x₁ + c₂x₂ = const надо перемещать в направлении (- ), противоположном .

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

Пример 2.5. Графическим способом решить ЗЛП

max (2x₁ + x₂)

при

x₁ - x₂ 2 (1)

x₁ + 3x₂ 3 (2)

7x₁ - x₂ 2 (3)

x_{1, 2} 0. (4)

Шаг 1. Строим область Р (рис. 2.4). Она является неограниченной.

Шаг 2. Строим вектор .

Шаг 3. Строим линию уровня функции = 2x₁ + x₂ = const.

Шаг 4. Передвигая линию уровня в направлении вектора , убеждаемся в неограниченном возрастании функции , то есть .

Рис. 2.4

Пример 2.6. Решить графическим методом ЗЛП. Найти

x₁ + 3x₂

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

2x₁ + 3x₂ 6 (1)

x₁ + 2x₂ 5 (2)

x₁ 4 (3)

0 x₂ 3 (4)

Рис. 2.5

Из рис. 2.5 видно, что область допустимых решений пуста (Р= ).

Задача не имеет решения.