Геометрическая интерпретация ЗЛП

Множество допустимых решений ЗЛП образует выпуклый многогранник. Каждая вершина этого многогранника определяет опорный план (допустимое базисное решение). Графическим методом можно решать ЗЛП с двумя переменными. Решение задачи:

1) начинают с построения области допустимых решений.

2) Затем строят вектор-градиент целевой функции. Вектор-градиент целевой функции = (с₁;с₂)

перпендикулярен линиям уровня L_i=c₁x₁+c₂x₂=const и показывает направление, в котором эта функция возрастает с наибольшей скоростью.

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

а б

Дата добавления: 2014-01-07