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

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

Пусть задача линейного программирования задана в двумерном пространстве:

(1)

при ограничениях

(2)

Областью допустимых решений задачи может быть либо выпуклый многогранник, либо выпуклая многоугольная неограниченная область, либо единственная точка. Уравнение задачи (1) определяет на плоскости семейство параллельных прямых, каждой из которых отвечает определенное значениефункции . Вектор , перпендикулярный к этим прямым, указывает направление скорейшего возрастания функции , а противопо-ложный вектор – направление скорейшего убывания.

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

Из рисунка следует, что прямая дважды становится опорной к многоугольнику решений.

Решение задачи линейного программирования можно проводить в такой последовательности:

Рис. 1

1) записываем уравнения граничных прямых и строим их на плоскости;

2) определяем полуплоскости, соответствующие исходным ограничениям-неравенств. Для этого берем произвольную точку, лежащую по ту или иную сторону от граничной прямой, и ее координаты подставляем в левую часть ограничения-неравенства. Если оно удовлетворяется, то искомой будет полуплоскость, которая содержит выбранную точку; если не удовлетворяется, то искомой будет полуплоскость, которой данная точка не принадлежит;

3) выделяем область допустимых решений задачи, как общую часть полуплоскостей, соответствующих исходным неравенствам;

4) строим вектор и перпендикулярно к нему одну из прямых семейства , например, ;

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

6) определяем координаты точки С (точки А), решив систему линейных уравнений прямых, пересекающихся в этой точке, и находим экстремальное значение .

Пример 1. Найти графически минимальное и максимальное значения функции при заданных ограничениях:

где .