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

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

· на первом этапе строим область допустимых решений, соответствующую системе ограничений. Для этого приравниваем их левые и правые части, и определяем направления расположения допустимых значений искомых переменных в соответствии со знаками неравенств;

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

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

Пример

Дана целевая функция

с системой ограничений

Найти оптимальные значения  и .

1 этап

Строим область допустимых решений (ОДР).

Для формирования ОДР необходимо в системе координат  построить линии, соответствующие ограничениям, приравнивая их левые и правые части, и определить направления расположения допустимых значений искомых переменных в соответствии со знаками неравенств (рис. 7.1).

Рис. 7.1 Графическая иллюстрация решения задачи линейного

программирования

Вычисления для построения первых двух ограничений:

;

0

5

10

0

;

0

6

6

4

Направления допустимости значений переменных  и  в соответствии с первыми двумя ограничениями – «вниз – влево».


В соответствии с третьим ограничением значения переменной  должны находиться выше оси , а в соответствии с четвертым ограничением значения переменной  должны находиться правее оси . Следует иметь в виду, что границы ОДР в область допустимых решений входят. Это объясняется тем, что в ограничениях применяются знаки неравенств «меньше – равно» и «больше – равно».

2 этап

Окончательно определяем оптимальные значения переменных  и .

Для этого необходимо сначала построить произвольную прямую для целевой функции, приравняв ее выражение к любому числу так, чтобы эта прямая располагалась в пределах выбранного масштаба рисунка. Приравняем выражение целевой функции, например, к числу «16» и построим соответствующую прямую линию:

0

8

8

4

После этого необходимо построить прямую линию, параллельную данной прямой так, чтобы она коснулась границы ОДР. Координаты точки касания этой прямой с границей ОДР будут оптимальными значениями переменных  и .

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

;

.

Решим эту систему уравнений:

.

Подставим это значение  во второе уравнение:

,

т.е.

.

При этом максимальное значение целевой функции равно:

.