«Анализ и проектирование алгоритма симплекс-метода для решения задач линейного программирования.»

Целевая функция. Что можно сказать о линейной форме (ЦФ)? Это функция двух переменных x₁ и x2, её образ в трёхмерном пространстве – плоскость, проходящая через начало координат. Найдём частные производные ЦФ по х_j

Так как частная производная по переменной х_j представляет наибольшую скорость изменения функции Q в направлении этой оси, то вектор C= <c₁, c₂> - это вектор наибольшего изменения ЦФ, вектор градиентного направления. Если значения Q зафиксировать Q =Q₁ = const , то уравнение ЦФ превращается в уравнение прямой c₁x₁ + c₂x₂= Q₁= const плоскости х₁О х₂
В трёхмерном пространстве это плоскость параллельная х₁О х₂  на высоте Q₁, в каждой точке <x1, x2, Q_1>  которой значение ЦФ постоянно и равно Q₁. . На плоскости Q этой прямой соответствует линия параллельная плоскости х₁О х₂, которую называют линией уровня (плотницкий уровень) функции c₁x₁ + c₂x₂ . Изменяя Q, получим семейство линий уровня параллельных друг другу. Требованию задачи – поиску экстремума Q соответствует смещение точки по поверхности функции Q в направлении вектора C= <c₁, c₂> от начала координат.
Ограничения ЗЛП не позволяют аргументам ЦФ Q(x1, x2) выходить за пределы многоугольной допустимой области. Другими словами, надо найти точку на плоскости Q наиболее удалённую от плоскости х₁О х₂ и проекция которой на х₁О х₂ лежит в области допустимых решений. Координаты x*₁, x*₂ найденной точки и определяют оптимальный план ЗЛП. Покажем, что семейство линий уровня (изолиний) перпендикулярно C, т. е. перпендикулярно прямой х₂ =с₂х₁/c₁. Из векторного анализа известно, что все линии уровня ЦФ Q перпендикулярны вектору градиенту ЦФ, вычисленному в некоторой точке

Таким образом, перемещаясь вдоль вектора C или по прямой х₂ =с₂х₁/c₁, легко построить линию уровня (она перпендикулярна х₂ = с₂х₁/c₁ ) и вычислить значение ЦФ Q для этой линии. Экстремум Q, очевидно, будет достигаться в положении касания линией уровня (её проекцией) границы множества допустимых решений. Такое касание может быть трёх типов: в вершине, по ребру, по грани многогранника. Этим типам касания соответствуют: единственное решение в вершине и бесконечное множество решений в других случаях. Область допустимых решений. Рассмотрим случаи ограниченной и неограниченной области допустимых решений. В последнем случае поиск экстремума Q может приводить к отсутствию решения, так как extr Q → ±∞ или существует опорная прямая линия, касающаяся неограниченного многогранника, и тогда решение существует.