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

Решение задачи линейного программирования (ЛП) графическим методом достигается реализацией следующего алгоритма:

1. Привести задачу к каноническому виду. Убедится, что число свободных переменных не превышает двух. Выразить m базисных переменных через две свободные переменные (в качестве свободных взять переменные, которые присутствуют в целевой функции);

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

3. Провести прямую линию, соответствующую целевой функции. Она проходит перпендикулярно вектору, координаты которого составлены из коэффициентов при переменных в выражении для целевой функции;

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

5. Найти координаты полученной крайней точки, решив систему уравнений прямых, на пересечении которых она находится.

Например, необходимо найти при следующих ограничениях:

. (5.1)

Для этого приведем задачу к каноническому виду:

. (5.2)

Решаем задачу линейного программирования, в которой n = 5 – количество переменных, m = 3 – количество базисных переменных, n – m = 2 – количество свободных переменных. Если число свободных переменных равно двум, то можно дать графическую интерпретацию задачи (рис. 5.1).

Рисунок 5.1 – Решение задачи МП графическим методом

Выберем в качестве свободных переменных x ₁ и x₂, и выразим базисные переменные через свободные.

. (5.3)

Каждое из полученных уравнений представляет собой уравнение гиперплоскости в двухмерном пространстве.

. (5.4)

Проведем линию перпендикулярно вектору, который можно построить по коэффициентам при x₁ и x₂. Направление вектора указывает направление возрастания целевой функции (При поиске минимума прямую перемещаем в направлении, обратном направлению вектора). Тогда:

. (5.5)