Какой оптимальный план, если при решении ЗЛП на max линии уровня при движении в направлении градиента Q выходит из множества допустимых планов в точке пересечения приямых 3x1+x2=6 и -2х1+х2=1
Линия уровня функции
Напомним, что линией уровня функции называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение. Градиентом функции f(x) называется вектор
Δf(x) = df,…, df
dx1 dxn
указывающий направление наиболее быстрого возрастания функции, и, стало быть, ориентированный перпендикулярно линиям уровня.
Для линейной функции двух переменных линия уровня представляет собой прямую, перпендикулярную вектору с, который служит градиентом данной функции. Следовательно, если линия уровня определяется уравнением f(x)=c1x1+ c2x2 =const, то этот вектоp имеет вид
и указывает направление возрастания функции.
Таким образом, с геометрической точки зрения задача максимизации сводится к определению такой точки области D, через которую проходит линия уровня, соответствующая наибольшему из возможных значений. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной вектору с) до тех пор, пока не достигнем такой точки области допустимых планов D, из которой смещение в направлении вектора с было бы невозможно. Такой метод решения получил название графического. Заметим, что решение задачи поиска минимума линейной функции осуществляется аналогично, с той лишь разницей, что движение по линиям уровня должно производиться в направлении, обратном градиенту целевой функции, т. е. по вектору (-с) .
На рис. 1.1 изображен некоторый частный случай, для которого решение ЗЛП достигается в угловой точке х* = (0, 6) области D. Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.
Рисунок (а) иллюстрирует ситуацию неограниченности целевой функции f(x)=cx на множестве D, т. е. сколько бы мы ни перемещались по линиям уровня в направлении вектора с, ее значение будет возрастать.
В случае, изображенном на рисунке (b), линия уровня, соответствующая максимальному значению f(x), касается грани множества D, и, соответственно, все точки, лежащие на этой грани, являются оптимальными планами.
Во всех рассмотренных иллюстрациях допустимые планы ЗЛП представлялись в виде некоторого многогранного выпуклого множества на плоскости. Такое их представление в литературе получило название первой геометрической интерпретации задачи линейного программирования
⇢