Лекция: Графическое решение задачи линейного программирования.
Графический способ решения задачи линейного программирования целесообразно использовать для:
· решения задач с двумя переменными, когда ограничения выражены неравенствами;
· решение задач со многими переменными при условии, что в их канонической записи содержится не более двух переменных.
Запишем задачу линейного программирования с двумя переменными :
целевая функция:
(3.34)
ограничения:
(3.35)
(3.36)
Каждое из неравенств (3.35) – (3.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми;;;. В том случае, если система неравенств (3.35) – (3.36) совместна, область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых решений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений с заменой знаков неравенств на знаки равенств.
Областью допустимых решений системы неравенств (3.35) – (3.36) может быть:
· выпуклый многоугольник;
· выпуклая многоугольная неограниченная область;
· пустая область;
· луч;
· отрезок;
· единственная точка.
Целевая функция (3.34) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определённое значение .
Вектор с координатами и, перпендикулярный этим прямым, указывает направление наискорейшего возрастания, а противоположный вектор – направление убывания .
Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (3.35) – (3.36) и семейство параллельных прямых (3.34), то задача определения максимума функции сведётся к нахождению в допустимой области точки, через которую проходит прямая из семейства, и которая соответствует наибольшему значению параметра .
Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение.
Для определения данной вершины построим линию уровня, проходящую через начало координат и перпендикулярную вектору, и буде передвигать её в направлении вектора до тех пор, пока она не коснётся последней крайней (угловой) точки многоугольника решений. координаты указанной точки и определяют оптимальный план данной задачи.
Заканчивая рассмотрение геометрической интерпретации задачи (3.34) – (3.36), отмечу, что при нахождении её решения могут встретится случаи, изображенные на рис. 3.1 – 3.4.
Рис. 3.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 3.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.
|
Рис. 3.1. Оптимум Рис. 3.2. Оптимум Функция Z Функция Z достижим в точке А достигается в любой точке [AB]
Рис. 3.3. Оптимум Рис. 3.4. Область допустимых
Функция Z недостижим решений – пустая область
На рис. 3.3 изображен случай, когда максимум недостижим, а на рис. 3.4 – случай, когда система ограничений задачи несовместна. Отмечу, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения её максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора, а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении её минимального значения.
Для практического решения задачи линейного программирования (3.34) – (3.36) на основе её геометрической интерпретации необходимо следующее:
1. Построить прямые, уравнения которых получается в результате замены в ограничениях (3.34) – (3.36) знаков неравенств на знаки равенств.
2. Найти полуплоскости, определяемые каждым из ограничений задачи.
3. Определить многоугольник решений.
4. Построить вектор .
5. Построить прямую, проходящую через начало координат и перпендикулярную вектору .
6. Передвигать прямую в направлении вектора, в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции в этой точке.