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

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

Рассмотрим случай двух переменных:

(5)

Дадим геометрическую интерпретацию элементов этой задачи.

Каждое из ограничений (6), (7) задаёт на плоскости x₁Ox₂ некоторую полуплоскость. Полуплоскость – выпуклое множество. Напомним, что выпуклым называют множество, которое вместе с любыми своими точками x₁ и x₂ содержит и все точки отрезка [ x₁; x₂ ]. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений (ОДР) задачи есть выпуклое множество.

Возможны ситуации, когда область допустимых решений ЗЛП:

- выпуклый многоугольник;

- неограниченная выпуклая многоугольная область;

- единственная точка;

- прямая линия;

- луч;

- отрезок;

- пустое множество.

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

Пусть ОДР задачи ЛП – непустое множество.

Выберем произвольное значение целевой функции , получим . Это уравнение прямой линии. В точках прямой целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве  параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции. Найдем частные производные целевой функции по x₁ и x₂: .

Частная производная функции показывает скорость её возрастания вдоль данной оси. с₁ и с₂ – скорости возрастания  соответственно вдоль осей Ox₁ и Ox₂. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор указывает направление наискорейшего убывания целевой функции Его называют антиградиентом.

Вектор  перпендикулярен к прямой  семейства .

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

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

2. Строится вектор .

3. Проводится произвольная линия, перпендикулярная к вектору .

4. При решении задачи на максимум перемещается линия уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении.

В случае задачи на минимум линия уровня перемещается в антиградиентном направлении.

5. Определяется оптимальный план  и экстремальное значение целевой функции .

Возможны следующие случаи:

- оптимальный план единственный;

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

- целевая функция неограниченна;

- область допустимых решений состоит из единственной точки, где целевая функция достигает одновременно и максимального и минимального значения;

- задача не имеет решения: ОДР – пустое множество, т.е. система ограничений задачи несовместна.

Пример. Пусть предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами 3-х видов С, D и E в объёмах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и даны в таблице 1. Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В- 50 млн. руб. Требуется найти объёмы производства изделий, обеспечивающие максимальную прибыль.

Таблица 1

Решение. Построим математическую модель задачи.

- количество деталей A,

 - количество деталей B,

Ограничения будут иметь вид:

Решение сформулированной задачи найдем, используя геометрическую интерпретацию. Определим сначала многоугольник решений, для чего систему ограничений-неравенств запишем в виде уравнений и пронумеруем их:

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

Чтобы построить первую прямую, найдем точки её пересечения с осями координат: при x₁ = 0, х₂ = 75, а при х₂ = 0, x₁ = 25. Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку 0(0,0) и подставим ее координаты в неравенство — оно удовлетворяется. Так как точка 0(0,0) лежит левее первой прямой, то и полуплоскость будет находиться левее прямой 24 х₁ + 8 х₂ = 600. На рис. 1 расположение полуплоскости относительно первой прямой отмечено стрелками.

Рис. 1

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенствам. Точки, удовлетворяющие ограничениям х₁, ³ 0, х₂ ³ 0, находятся в первом квадранте.

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

Любая точка многоугольника решений удовлетворяет системе ограничений задачи и, следовательно, является ее решением. Это говорит о том, что данная задача линейной оптимизации имеет множество допустимых решений, т.е. многовариантна. Нам же необходимо найти решение, обеспечивающее максимальную прибыль.

Приравняем функцию к нулю и построим соответствующую прямую. Вектор-градиент прямой функции 40 х₁ + 50 х₂ = 0 имеет координаты . Изобразим вектор на графике и построим прямую перпендикулярно этому вектору (рис. 1). Перемещая прямую функции параллельно самой себе в направлении вектора, увидим, что последней точкой многоугольника решений, которую пересечет прямая функции, является угловая точка В. Следовательно, в точке В функция достигает максимального значения.

Координаты точки В найдем, решая систему уравнений, прямые которых пересекаются в данной точке:

Решив эту систему, получим, что х₁ = 17,14; х₂ = 23, 57. Следовательно, если предприятие изготовит изделия в найденных объемах, то получит максимальную прибыль, равную

Z_max = 40×17,14 + 50×23,57 = 1 864,1(млн. руб.).