Решение и анализ задач ЛП графическим методом

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

(4.1)

Отметим, что, если в задаче линейного программирования имеется более двух переменных x₁, x₂,…,x_n,но (n-2) ограничений имеют вид равенства, а остальные вид неравенства, то и такая задача может быть сведена к двум переменным за счет исключения переменных с помощью системы равенств. Следовательно, графический метод может быть применен и к таким задачам.

Для геометрической интерпретации решения задачи задается координатная плоскость Оx₁,x₂, на которой каждая точка с координатами (x₁,x₂) представляет решение (допустимое или недопустимое) задачи с такими значениями переменных.

Каждое из неравенств задачи (4.1) моделируется на координатной плоскости Оx₁,x₂ некоторой полуплоскостью (рис. 4.1), а система неравенств в целом – общей частью соответствующих полуплоскостей, то есть пересечением их как множеств точек. Множество точек пересечения данных множеств (полуплоскостей) образует область допустимых решений. ОДР является выпуклой областью, т.е. если две точки А и В принадлежат этой ОДР, то и все точки отрезка АВ принадлежат ей. В зависимости от сочетания и видов ограничений ОДР графически может выглядеть выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, единственной точкой. Если ограничения задачи (4.1) несовместны, то ОДР - пустое множество.

Функция при заданном значении z(x)=z₀ моделируется на плоскости прямой линией, задаваемой уравнением . В каждой точке плоскости, принадлежащей данной прямой целевая функция имеет одно и то же значение равное z₀. При различных значениях правой части равенства, получаются параллельные прямые. соответствующие различным значениям правой части (уровням целевой функции) и называемые линиями уровня (Рис. 4.1).

Рис. 4.1. Геометрические интерпретации ограничений и ЦФ

Вектор C =(c₁,c₂)_, координатами которого являются коэффициенты функции , называется градиентом функции z(x). Градиент указывает направление наискорейшего возрастания функции и перпендикулярен к каждой из линий уровня (Рис. 4.1). Направление наискорейшего убывания ЦФ противоположно направлению вектораC.

Суть графического метода заключается в том, что в ОДР производится поиск оптимальной точки x_опт=(x_1опт, x_2опт). Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению уровня ЦФ. Оптимальное решение всегда находится на границе ОДР, например, в вершине многоугольника ОДР, оказавшейся последней через которую пройдет линия уровня, при её параллельном перемещении, моделирующем возрастание уровня ЦФ (Рис.4.1). При этом значение уровня будет равно z_max. Если сторона многоугольника ОДР, на которой расположена точка соответствующая оптимальному решению, параллельна линиям уровня, то оптимальное решение может находиться в любой точке этой стороны многоугольника ОДР.

При решении задачи ЛП возможны следующие множества решений.

Таблица 4.1.1

Дата добавления: 2015-07-15