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

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

Однако данный метод является наглядным, поэтому рассмотрим его подробно.

Итак, для рассматриваемого случая математическая модель задачи имеет вид:

(10)

(11)

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

Каждое из неравенств (11) системы ограничений геометрически определяет полуплоскость соответственно с граничными прямыми. Если система неравенств (11) совместна, область ее решения есть множество точек, принадлежащих всем этим полуплоскостям. При таких условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины строят линию уровня , где – некоторая постоянная. Очевидно, это прямая, являющаяся множеством точек, в которой функция F принимает значение, равное h. Меняя величину h, получим семейство параллельных прямых. Каждую из этих прямых называют линией уровня (линией равных значений функции). Выберем линию уровня, проходящую через многоугольник решений. Очевидно, при переходе от одной линии уровня к другой значение функции F изменяется. Нужное направление движения исходной линии уровня можно установить следующим образом. Из геометрии известно, что коэффициенты при переменных в уравнении прямой служат координатами вектора , перпендикулярного прямой. Если передвигать прямую в направлении вектора , то значение будет наиболее быстро возрастать. Передвигаем прямую F=0 в направлении вектора до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план задачи.

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

Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице. Здесь же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием.

 

Вид сырья	Нормы расхода сырья (кг) на одно изделие	Общее количество сырья (кг)
А	В
I
II
III
Прибыль от реализации одного изделия (ден. ед.)

 

Требуется составить такой план выпуска изделий, при котором прибыль предприятия от реализации всех изделий является максимальной.

Решение. Пусть и – количество изделий вида А и В соответственно, которые планируют для производства. Система ограничений на сырье каждого вида имеет вид:

Общая прибыль от реализации изделий, т.е. целевая функция имеет вид:

Найдем решение задачи, используя ее геометрическую интерпретацию.

Определим многоугольник решений.

Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенства заменим на знаки точных равенств и построим соответствующие прямые (рис. 5.6):

Пересечение полученных полуплоскостей определяет многоугольник решений задачи. На рис. 6 это многоугольник 0АВСД. Строим вектор и линию уровня F=0.

 

 

Перемещая линию уровня в направлении вектора , видим, что последней общей точкой является точка В. Найдем ее координаты, как точки пересечения прямых II и III:

откуда ^*= 12, ^*= 18.

Следовательно, если предприятие изготавливает 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную:

ден.ед.

Приведем основные этапы геометрического метода решения задачи линейного программирования:

- строят прямые, уравнения которых получают заменой знаков неравенств на знаки точных равенств;

- находят полуплоскости, определяемые каждым из ограничений задачи;

- находят многоугольник решений;

- строят вектор ;

- строят линию уровня F=c₁x₁+c₂x₂=h, проходящую через многоугольник решений;

- перемещают прямую в направлении вектора и находят точки, в которых F принимает максимальное значение;

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

При этом возможны следующие случаи:

- оптимальное решение единственно. Прямая F_max имеет единственную общую точку (В) с многоугольником допустимых решений (рис. 6);

- максимальное значение целевая функция принимает в точке А, а минимальное – в точке В, т.е. прямая F дважды становится опорной по отношению к многоугольнику решений (рис. 7);

- оптимальных решений бесконечное множество. Прямая F_max совпадает с одной из сторон, ограничивающих многоугольник (рис. 8). В этом случае каждая точка отрезка АВ является оптимальным решением;

- оптимального решения не существует по причине неограниченности функции цели (9);

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

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

- оптимальное решение, если оно существует, лежит не внутри, а на границе области допустимых решений;

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

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

- решение, лежащее в одной из вершин области допустимых решений, является опорным решением (или базисным), а сама вершина – опорной точкой;

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