МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Предположение о возможности описать зависимости между управляемыми переменными с помощью линейных функций далёко не всегда адекватно природе моделируемого объекта. Попытки учесть нелинейные факторы приводят к формулировке более общих и сложных оптимизационных задач. Изучение методов их решения составляет предмет научной области, получившей названия нелинейного программирования.
Общая задача нелинейного программирования (ЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f (x1, х2 ,..., хп) на множестве D, определяемом системой ограничений равенств и неравенств:
gi (x1, х2 ,..., хп)= 0, i=1: r,
f(x) ® max, D = { x Î R n, }(1)
gi (x1, х2 ,..., хп)<= 0, i=r+ 1: m
где хотя бы одна из функций f или gi является нелинейной. По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f).
Как и в ЗЛП, вектор х* =(x1*, x2*,..., xn*) Î D называется допустимым планом, а если для любого x Î D выполняется неравенство f(x*)>f(x), то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.
|
|
С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, a gi(x)<=0 как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП
Задача (1) является весьма общей. Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:
g(x) = 0 ó{ g(x)>=0; -g(x) <=0 }
либо, добавив фиктивные переменные у, к системе уравнений:
g(x)>=0 ó { g(x) – y2 = 0 }.
Перечисленные свойства ЗНП существенно усложняют процесс их решения по сравнению с задачами линейного программирования.
Градиентные методы решения задач
нелинейного программирования.
Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка, в которой Ñ f(x) = 0 и которая в соответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.
Пусть f(x)=f(x1 , x2 ,..., xn) — дифференцируемая функция, заданная на Rn, а х(q)=(х1(q), х2(q),..., хn(q)) – некоторая текущая точка. Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х(1) перемещаться в направлении вектора Ñ f(x(1)), то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1). Следовательно, для точки
|
|
x(2) = x(1)+ lÑ f(x(1)), (l>0),
лежащей в такой окрестности, справедливо неравенство f(х(1))<=f(x(2)). Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).
Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага l в рекуррентной формуле
x(q) = x(q)+ lÑ f(x(q)),
задающей последовательность точек, стремящихся к точке максимума. Как уже говорилось выше, если x(q) — нестационарная точка (т. е. |Ñ f(x(q)) |>0), то при движении в направлении Ñ f(x(q)) функция f(x) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится.
Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) x( 0 ) , не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*.
В зависимости от способа выбора шага l различают различные варианты градиентного метода.
Процедура «Поиск решения» в MS Excel содержит две разновидности градиентного метода – Метод Ньютона и метод спряженных градиентов.