ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ДВУМЯ ПЕРЕМЕННЫМИ
Рассмотрим задачу линейного программирования с двумя переменными и ограничениями только в виде неравенств (стандартная форма задачи):
Ищем оптимальное значение целевой функции
(4)
с ограничениями
, (5)
и условиями неотрицательности
. (6)
Решение задачи начинается с нахождения ОДР задачи, т.е. решения системы (5),(6).
Каждое из неравенств (5)-(6) геометрически определяет полуплоскость с граничными условиями
(7)
Чтобы определить, какая именно полуплоскость, удовлетворяет неравенству
(8)
достаточно проверить условие (8) для некоторой точки, например для начала координат О(0;0) (если ).
Рассмотрим пример задачи об использовании ресурсов:
Построим ОДР данной задачи.
Построим полуплоскость, определяемую неравенством:
.
Построим границу полуплоскости – прямую
Прямая строится по двум точкам:
x1 | ||
x2 |
Поскольку начало координат О(0;0) удовлетворяет неравенству : , то выбрана нижняя полуплоскость.
Аналогично построим и полуплоскость .
Условия неотрицательности выделяют только первую четверть плоскости.
Область пересечения всех полуплоскостей определяет область допустимых решений (ОДР) и является выпуклым четырехугольником ABCO:
В общем случае, если система (5)-(6) имеет решение, то она выделяет выпуклую многоугольную область, которая называется многоугольником решений. Стороны этого многоугольника лежат на прямых (7).
Областью допустимых решений может быть:
− выпуклый многоугольник;
− выпуклая многоугольная неограниченная область.
Второй этап состоит в построении линий уровней целевой функции.
Линии уровней целевой функции (4) представляют собой семейство прямых
, (9)
которые перпендикулярны вектору
.
Вектор указывает направление наискорейшего возрастания целевой функции, а противоположный вектор – направление убывания целевой функции.
В одной и той же системе координат изобразим область допустимых решений и линии уровня целевой функции.
Задача определения максимума (минимума) целевой функции сводится к нахождению в ОДР точки, через которую проходит прямая из семейства (9) и которая соответствует наибольшему (наименьшему) значению . Возможны следующие случаи:
а)
Максимум целевой функции достигается в точке A, минимум – в точке B.
б)
Максимум целевой функции достигается в любой точке отрезка, минимум – в точке B.
в)
Максимум целевой функции недостижим, минимум – в точке B.