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

 

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

Пусть требуется найти максимальное значение функции

(1)

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

(2)

,

где ; ; – заданные числа.

Введем на плоскости прямоугольную систему координат . Каждое неравенство задает полуплоскость с границей .

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

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

Допустим, что область допустимых решений системы ограничений (2) — четырехугольник АВСD (рис. 3).

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

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

Прямая, уравнение которой получено из целевой функции задачи при равенстве ее постоянной величине, т.е. прямая , называется линией уровня целевой функции.

Известно, что коэффициенты при переменных в уравнении прямой на плоскости являются координатами вектора нормали к этой прямой: . Следовательно, нормальный вектор всех линий уровня .

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

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

 

Теорема. Значения целевой функции в точках линии уровня увеличиваются, если линию уровня перемещать параллельно начальному положению в направлении вектора нормали, и убывают при перемещении в противоположном направлении.

 

Таким образом, алгоритм решения задачи линейного программирования с двумя переменными графическим методом такой:

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

2. Строится вектор с точкой приложения в начале координат.

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

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находится максимум или минимум функции.

В зависимости от вида области допустимых решений и целевой функции возможны следующие случаи:

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

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

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

Пример. Решить ЗЛП графическим методом.

или

, . , .

Решение

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

Прямые и строим по двум точкам:

 

 

 

 

 

Прямая разбивает плоскость на две полуплоскости – одна – выше прямой, другая – ниже прямой:

 

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

 

Прямая также разбивает плоскость на две полуплоскости:

 

 

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

Одновременно обоими неравенствами задается область четырехугольника :

Учитывая, что и , получаем

 

Таким образом, Область допустимых решений — многоугольник ОАВСDЕ:

2. Для линии уровня строим нормальный вектор :

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

4. Так как задача на максимум, то перемещаем линию уровня в направлении вектора до положения опорной прямой. В данном случае это прямая, проходящая через точку С. Точка С является точкой пересечения прямых и , поэтому ее координаты удовлетворяют уравнениям этих прямых

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

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: