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

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

Графический метод решения ЗЛП состоит из следующих этапов.

1. Строится область допустимых решений (ОДР) ЗЛП.

2. Строится вектор-градиент целевой функции (вектор, координатами которого являются частные производные функции) с приложением в начале координат – .

3. Линия уровня C₁x₁+C₂x₂ = а (а – постоянная величина) - прямая, перпендикулярная вектору–градиенту – передвигается в направлении этого вектора в случае максимизации f(x_1,x₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x_1,x₂).

4. Для нахождения ее координат достаточно решить систему из двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x_1,x₂), найденное в полученной точке, является максимальным.

При минимизации f(x_1,x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то целевая функция f(x_1,x₂) не ограничена на максимум (в задаче максимизации) или минимум (в задаче минимизации).

Если линия уровня параллельна какой-либо прямой из ограничений задачи, то оптимальное значение целевой функции будет достигаться в любой точке этой прямой.

Пример. Найти максимальное значение функции f=2x₁ + 3x₂ при условиях

Построим область допустимых значений:

1) первое ограничение x₁ + 3x₂ £ 18; прямая x₁ + 3x₂ = 18 пересекает оси координат в точках (0; 6) (18; 0); неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка(0; 0), 0 + 3*0 < 18 принадлежит полуплоскости);

2) второе ограничение 2 x₁ + x₂ £ 16: прямая 2x₁ + x₂ = 16 пересекает оси координат в точках (0; 16) (8; 0); неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка (0; 0), 2*0 + 0 <16 принадлежит полуплоскости);

3) неравенству x₂ £ 5 соответствует полуплоскость, содержащая прямую x₂ = 5 и лежащая ниже неё.

4) x₁ ³ 0 - правее ОX₂;

5) x₂ ³ 0 - выше ОX₁.

Вектор-градиент имеет координаты .

Построим линии уровня 2 x₁ + 3 x₂ = а. При а = 0 получим прямую 2x₁ + 3x₂ = 0, проходящую через начало координат, перпендикулярно вектору-градиенту. Так как задача на максимум, то передвигаем линию уровня в направлении градиента. Предельной точкой (последней из области допустимых решений, с которой соприкасается линия уровня) является точка С. Значит, в ней достигается максимум функции f (рис. 1).

Найдём её координаты. Для этого решим систему, составленную из уравнений прямых пересекающихся в точке С (I и II):

Таким образом, получим x₁ = 6, x₂ = 4, f_max = 2*6 + 3*4 = 24.