Раздел 6. Задачи скалярной оптимизации, линейные, нелинейные, дискретные

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

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

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

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

  1. решения задач с двумя переменными, когда ограничения выражены неравенствами;
  2. решение задач со многими переменными при условии, что в их канонической записи содержится не более двух переменных.

Запишем задачу линейного программирования с двумя переменными:

ограничения:

Каждое из неравенств (2) – (3) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми В том случае, если система неравенств (2) – (3) совместна, область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых решений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений с заменой знаков неравенств на знаки равенств.

Областью допустимых решений системы неравенств (2) – (3) может быть:

  1. выпуклый многоугольник;
  2. выпуклая многоугольная неограниченная область;
  3. пустая область;
  4. луч;
  5. отрезок;
  6. единственная точка.

Целевая функция (1) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определённое значение Z.

Вектор с координатами с1 и с2 , перпендикулярный этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор – направление убывания Z.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (2) – (3) и семейство параллельных прямых (1), то задача определения максимума функции Z сведётся к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const , и которая соответствует наибольшему значению параметра Z.

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

Для определения данной вершины построим линию уровня Z = c1x1 + c2x2 = 0 , проходящую через начало координат и перпендикулярную вектору , и будем передвигать её в направлении вектора до тех пор, пока она не коснётся последней крайней (угловой) точки многоугольника решений. координаты указанной точки и определяют оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации задачи (1) – (3), отмечу, что при нахождении её решения могут встретится случаи, изображенные на рис. 1 – 4.

Рис. 1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.

На рис. 3 изображен случай, когда максимум недостижим, а на рис. 4 – случай, когда система ограничений задачи несовместна. Отмечу, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения её максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора , а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении её минимального значения.

Для практического решения задачи линейного программирования (1) – (3) на основе её геометрической интерпретации необходимо следующее:

  1. Построить прямые, уравнения которых получается в результате замены в ограничениях (1) – (3) знаков неравенств на знаки равенств.
  2. Найти полуплоскости, определяемые каждым из ограничений задачи.
  3. Определить многоугольник решений.
  4. Построить вектор .
  5. Построить прямую Z = c1x1 + c2 x2 = 0 , проходящую через начало координат и перпендикулярную вектору .
  6. Передвигать прямуюZ = c1x1 + c2 x2 в направлении вектора , в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции в этой точке.

Предыдущая лекция  |  Следующая лекция