1.4. Анализ классическими методами задачи линейного программирования
Основные вычислительные проблемы решения задач линейного программирования состоят в определении границы множества допустимых решений и вычислении значений целевой функции в точках границы с тем, чтобы найти оптимальное решение.
При анализе задачи линейного программирования первым шагом может быть попытка применить для отыскания решения классические методы математического анализа и линейной алгебры.
Как известно, при нахождении максимума на отрезке [а, Ь] дифференцируемой функции / (х) одной переменной необходимо вначале вычислить первую производную fix), затем найти все решения xi,..., х, уравнения f(x)=0, далее вычислить все значения/"(xi),...,/"(х,), Да), Дй) и выбрать из них набольшее. Уже в этом простейшем случае могут возникнуть трудности, например, с разрешимостью уравнения f(x)= О, или может оказаться, что число решений этого уравнения очень велико и тогда возникает вопрос, каким образом наиболее эффективно организовать перебор. Если же речь идет о функции нескольких переменных, то положение еще более осложняется. Пусть X = (xi,...,Xr,) есть некоторая точка п-мерного пространства аХ- замкнутое подмножество этого пространства иДх)- функция п переменных, заданная на множестве X. Требуется найти максимум дифференцируемой функции Дх) на множестве X. Попытаемся использовать для решения этой задачи методы классического анализа. Рассмотрим множество точек х(9) 77-мерного пространства, координаты которого имеют вид:
Xl(Q) = Xi + Х2(е) = Х2" + 051, ...,
x„{Q) = x„ + Qs„iQ>0).
Геометрически множество таких точек представляет собой луч с началом в точке (xi,...,x„), направление которого совпадает с вектором (1,..., Sn). Будем считать, что
Зафиксировав направление s = {si, 52,..., s) и увеличивая число 9, начиная с нуля, можно рассмотреть изменение функции Дх1(9), Х2(9), ....,Хг(9)). Локальное поведение функции Дх) вдоль направления s будет определяться производной по О в точке 0=0. Учитывая, что при 22
- о
0 = 0 значение х(0)= х", вычисляя производную функции fix), используя правило дифференцирования сложной функции:
/;(х,(0),Х2(0),...,х„(0)) =
дх0X2ох
ЙХ ЙХ28х
Величина
йх:дх2дх
называется производнойДх) в точке х по направлению s = (su..., Sn).
Вектор (----) называется градиентом функции/х) в точ-
ке и обозначается gradx). Используя понятие скалярного произведения из линейной алгебры получим, что:
/(/) = (grad/(/),s).
где в правой части равенства записано скалярное произведение вектора s и вектора grad/x).
Далее один из основных фактов математического анализа состоит в том, что значение функции У(х)=У(х1,..., х,) в окрестности точки (xi,..., Хг) растет быстрее всего, если в качестве направления выбрать градиент функции Дх) в точке х. Если в точке х достигается локальный максимум функции Дх), то в этой точке нет направления, вдоль которого функция возрастает. Поэтому необходимым условием максимума функции Дх) во внутренней точке х множества X является равенство градиента grad f (х) нулевому вектору. Обращаем внимание, что все предыдущие рассуждения корректны лишь для случая, когда х является внутренней точкой, т.е. когда из точки х можно хотя бы немного сдвинуться по любому направлению, не выходя за пределы множествах
Окончательно по аналогии с функцией одной переменной получим: для нахождения максимума функции/х) на множестве X надо найти все
решения х = (х i,..., х„)(/ = 1,..., системы уравнений= О
/= 1, далее вычислить значения Дл:),..., Дх*) и все значения Дх) на границе множества затем выбрать среди них максимальное.
Из сказанного видно, как усложняется решение задачи для случая функции многих переменных: даже если удается получить все решения уравнения grad Дх)= О и найти внутренние локальные максимумы функции Дх), надо еще вычислить и все максимумы на границе множествах Учитывая, что при п > 1 граница множества X (за исключением самых простых случаев) состоит из бесконечного числа точек, общего рецепта отыскания всех экстремальных значений функции Дх) на границе нет. В частном случае, если все ограничения в задаче носят характер равенств, может быть использован метод множителей Лагранжа, но и здесь вычислительные проблемы остаются.
Проанализируем стандартную задачу линейного программирования. Градиент целевой функции равен (ci,..., сД и если не все Cj равны нулю, то у функции Дх) нет локальных максимумов на внутренних точках множествах.
Следовательно, основные вычислительные проблемы решения задач линейного программирования состоят в определении границы множества X, которая в явном виде нам не задана, и организации вычислений значений целевой функции с\ х„, +...+, с„х„ на границе множествах, чтобы найти оптимальное решение.