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

1. Строится область допустимых решений (из системы ограничений).

2. Строится вектор с точкой приложения в начале координат.

3. Перпендикулярно вектору проводится одна из линий уровня, например, линия уровня, соответствующая уравнению c₁x₁+c₂x₂=0.

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться max или min функции.

В зависимости от вида ОДР и целевой функции Z(X) задача может иметь единственное решение, представленное на рис. 1а, бесконечное множество решений – рис. 1б или не иметь ни одного оптимального решения – рис. 1в.

На рис. 1а линия уровня дважды становится опорной по отношению к ОДР. Минимальное значение целевой функции линия уровня обеспечивает в точке А, а максимальное - в точке С. На рис. 1б минимальное значение целевая функция принимает на опорной прямой, совпадающей с одной из сторон многоугольника. На рис. 1в ОДР не ограничена в сторону увеличения значений целевой функции. Значит, целевая функция максимального значения не имеет.

Рисунок 1 - График построения целевой функции и области допустимых значений

Пример. Решить задачу линейного программирования графическим способом Z (X) = 2x₁ + 4x₂ ® max.

Решение:

 

 

1. Построим на плоскости X₁OX₂ граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе): -2x₁ + 3x₂ = 12 ® l₁, x₁ +x₂ = 9 ® l₂, 3x₁ – x₂ = 12 ® l₃, x₁ = 0 ® l₄,

x₂ =0 ® l₅.

Область допустимых решений определяется многоугольником ОАВСД, представленным на рис. 2.

 

 

 

Рисунок 2 - Построение ОДЗ

 

2. Для линии уровня 2x₁ + 4x₂ = c (const) строим нормальный вектор n (2,4).

3. Перпендикулярно вектору n построим линию уровня, проходящую через начало координат (2x₁ + 4x₂ = 0 ).

1. Перемещаем линию уровня параллельно самой себе в направлении вектора n (т.к. задача на нахождение max целевой функции) до опорной прямой. В данном случае опорной прямой является прямая, проходящая через т.В. Точка В получается при пересечении двух граничных прямых l₁ и l₂. Для определения координат точки В решаем систему уравнений

 

Получаем: x₁ = 3 , x₂ = 6. Это и будет оптимальное решение данной задачи, которому соответствует максимальное значение целевой функции

Z_max (X) = 2×3 + 4×6 = 30.