Графическим методом можно решать задачи линейного программирования с двумя переменными. Рассмотрим решение ранее приведенной задачи.
\[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.\]
Решение задачи начинается с построения области допустимых решений. При этом возможны следующие случаи:
- Область допустимых решений — пустое множество. В этом случае решения нет из-за несовместимости ограничений.
- Область допустимых решений — единственная точка. Тогда она и является оптимальным решением.
- Область допустимых решений — выпуклая неограниченная область. В таком случае решение может не существовать, если нет ограничений сверху при задаче на максимум, или снизу при задаче на минимум, а может находится в одной из угловых точек.
- Область допустимых значений — выпуклый многоугольник. В этом случае можно найти координаты всех угловых точек, вычислить в них значение и выбрать оптимальное.
Однако существует иной способ. Пусть \(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}\) (в случае минимизации — в противоположном направлении), определяем угловую точку, в котором целевая функция принимает максимальное (минимальное) значение. Если экстремум достигается сразу в двух смежных угловых точках, то по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка соединяющие эти точки.
Алгоритм графического метода
- Построить область допустимых значений
- Построить вектор градиент \(\bar{c}=(c_1,c_2) \)
- Построить семейство линий уровня перпендикулярных вектору \(\bar{c}\), проходящую через область допустимых решений.
- Выбрать линию уровня, проходящую через область допустимых решений наиболее удаленную в направлении вектора \(\bar{c}=(c_1,c_2) \) (в задаче на максимум, при решении задачи на минимум — в противоположном направлении). Определить угловые точки области, через которые они проходят.
- Найти координаты точек экстремума и значения целевой функции в этих точках
Решение задачи представлено на рисунке:
