Сентябрь 23

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

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

\[Z = 2500 х_1 + 3500 х_2 \to \max \]

\[\left\{ {\begin{array}{}
{3{x_1} + 10{x_2} \le 330}\\
{16{x_1} + 4{x_2} \le 400}\\
{6{x_1} + 6{x_2} \le 240}\\
{{x_1} \ge 0}\\
{{x_2} \ge 12}
\end{array}} \right.\]

Решение задачи начинается с построения области допустимых решений. При этом возможны следующие случаи:

  1. Область допустимых решений – пустое множество. В этом случае решения нет из-за несовместимости ограничений.
  2. Область допустимых решений  – единственная точка. Тогда она и является оптимальным решением.
  3. Область допустимых решений – выпуклая неограниченная область. В таком случае решение может не существовать, если нет ограничений сверху при задаче на максимум, или снизу при задаче на минимум, а может находится в одной из угловых точек.
  4. Область допустимых значений – выпуклый многоугольник. В этом случае можно найти координаты всех угловых точек, вычислить в них значение и выбрать оптимальное.

Однако существует иной способ. Пусть \(c_0\) – некоторое число. Прямая \(c_1x_1+c_2x_2=c_0\) является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное \(c_0\). Вектор – градиент целевой функции:

\[ \bar{c}= grad\;L(\bar{x})=\left(\frac{\partial L}{\partial x_1}; \frac{\partial L}{\partial x_2}\right)=(c_1,c_2) \]

перпендикулярен линиям уровня и показывает направление, в котором функция возрастает с наибольшей скоростью. Выбирая из линий уровня, проходящих через область допустимых значений, наиболее удаленную в направлении вектора \(\bar{c}\) (в случае минимизации – в противоположном направлении), определяем угловую точку, в котором целевая функция принимает максимальное (минимальное) значение. Если экстремум достигается сразу в двух смежных угловых точках, то по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка соединяющие эти точки.

Алгоритм графического метода

  1. Построить область допустимых значений
  2. Построить вектор градиент \(\bar{c}=(c_1,c_2) \)
  3. Построить семейство линий уровня перпендикулярных вектору \(\bar{c}\), проходящую через область допустимых решений.
  4. Выбрать линию уровня, проходящую через область допустимых решений наиболее удаленную в направлении вектора \(\bar{c}=(c_1,c_2) \)  (в задаче на максимум, при решении задачи на минимум – в противоположном направлении). Определить угловые точки области, через которые они проходят.
  5. Найти координаты точек экстремума и значения целевой функции в этих точках

Решение задачи представлено на рисунке:

Решение задачи ЛП графическим методом




Опубликовано 23.09.2016 Тушавин В.А. в категории "Прикладные методы оптимизации