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

Наиболее простым и наглядным методом решения ЗЛП является графический метод. Он применяется для решения ЗЛП с двумя переменными, заданными в неканонической форме, и многими переменными в канонической форме при условии, что они содержат не более двух свободных переменных.

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

Z = c₁x₁ + c₂x₂ +…+ c_nx_nmax (min), (1.1).

a₁x₁ + a₁₂x₂ + … + a_1nx_n b₁, (1.2).

…

a_m1x₁ + a_m2x₂ + … + a_mnx_n b_m ,

x_i0, j =. (1.3).

Каждое из неравенств системы ограничений (1.2) и (1.3) определяет на координатной плоскости x₁Оx₂ некоторую полуплоскость, а система неравенств в целом — пересечение соответствующих плоскостей:

a_i1x₁ + a_i2x₂ + … + a_inx_n + y_i = b_i, i = и х_j = 0, j = .

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

Любая внутренняя и граничная точка ОДР является решением задачи. Приравняем функцию (1.1) к нулю, тогда уравнение.

Z = c₁x₁ + c₂x₂ +…+ c_nx_n=0.

представляет собой полуплоскость, проходящую через начало координат и перпендикулярную вектору-градиенту (направляющему вектору) =(с₁, с₂,…, с_n). Направление вектора-градиента показывает направление возрастания функции. Поэтому, чтобы найти максимум функции, необходимо передвигать гиперплоскость в направлении вектора как можно дальше от начала координат, но чтобы она имела с ОДР хотя бы одну общую точку. Чтобы найти минимум функции, нужно определить ближайшую точку в ОДР от начала координат.