станты у5>0,0<Я<1. Для коэффициента а = р проверяется выполнение условия
Л+аЛ )</(/).(9.2)
Если оно выполнено, то полагается аа, Если нет, то производится дробление шага, т.е. принимается а = Яу5 и вновь проверяется выполнение условия (9.2). Процесс дробления, т.е. умножения текущего значения а на Я, продолжается до тех пор, пока условие 9.2 не окажется выполненным. Этот процесс не может быть бесконечным, поскольку
h - направление убывания. Первое а , при котором условие выполнено и принимается за .
Приведем пример использования метода наискорейшего спуска.
Пример. Используя метод наискорейшего спуска, решить следующую задачу безусловной оптимизации для функции
/(1,2) = --(1~3)2-(х2-2)2
max/(xi,X2)
(xi,X2)6i?2.
Решение. В качестве начальной точки выберем =(1Л). Вычислим градиент функции / (xi,X2) = (-2(xi -3), -2(2 -2)) , а также его значение в начальной точке / (1,1) = (4,2). Далее мы должны выбрать значение шага «о таким образом, чтобы достигался максимум функции
/(«о) = ЛОЛ) + 60(4,2)) = /(1 + 4аоЛ + 2ао) = = -(-2 + 4ао)-(-1 + 2ао)1
Данную задачу легко решить, приравнивая нулю первую производную приведенной функции, /(«о) = 0- именно: -8(-2 + 4ао)- 4(-1 + 2ао) = О, откуда ао = 0,5 .
Тогда XI = (1,1) + 0,5(4,2) = (3,2), а / (3,2) = (0,0). В этом случае реализация алгоритма завершается. Как несложно показать, в силу того что функция /(xi,X2) является вогнутой, найденная точка является решением задачи безусловной оптимизации.
9.4. Графический метод решения задач нелинейного программирования для функций двух переменных
Рассмотрим задачу нелинейного про-
Наиболее существенное
граммирования, содержащую только две переменные, записанную в виде
отличие задачи нелинейного программирования от линейных задач, заключается в том, что оптималь- тах/(х) ное решение может находиться как на границе допустимого множества, так и являться его внутренней точкой.
gAx)<b, x = (xx,X2)eR.
Как уже отмечалось, функция fix) называется целевой функцией, а неравенства g.(x)<6,, i = l,...,m называются ограничениями задачи.
Множество точек, удовлетворяющих ограничениям задачи, называется допустимым множеством задачи.
Решить задачу нелинейного программирования графически - значит найти такую точку из допустимого множества, через которую проходит линия уровня f{xi,X2) = C, имеющая максимальное значение величины
С из всех линий уровня, проходящих через допустимые точки задачи. Как и в случае задач линейного программирования, для задач нелинейного программирования, содержащих только две переменные, возможна графическая интерпретация.
Наиболее существенное отличие задачи нелинейного программирования от линейных задач заключается в том, что оптимальное решение может находиться как на границе допустимого множества, так и являться его внутренней точкой.
Этапы графического решения задач нелинейного программирования можно сформулировать следующим образом.
Этап!. На плоскости наносятся геометрические места точек, соответствующих каждому уравнению из ограничений задачи g/(x) = fe/,
/= 1, Tw. Строится допустимое множество задачи. Если допустимое множество задачи пусто, то задача не имеет решения.
Этап 2. Строятся линии уровня целевой функции /(xi,X2) = C при
различных значениях параметра С. 248
Этап 3. Определяется направление возрастания (для задачи максимизации) или убывания (для задачи минимизации) линий уровня целевой функции.
Этап 4. Определяется точка допустимого множества, через которую проходит линия уровня с максимальным (для задачи максимизации) или минимальным (для задачи минимизации) значением параметра С. Если целевая функция не ограничена сверху (для задачи максимизации) или не ограничена снизу (для задачи минимизации) на допустимом множестве, то задача не имеет решения.
Этап 5. Для найденной точки определяют ее координаты
X* =(x*i,x*2)Gi? и значение целевой функции в данной точке /(/i,/2)-
Пример. Решить следующую задачу нелинейного программирования, используя геометрическую интерпретацию
+ Х2 шах
XI + Х2 < 1, 2x1 + 2 - 2, xf-X2<0.
(9.4)
Решение. Построим линии, соответствующие ограничениям задачи (9.4), рассмотренным как равенства (рис. 9.2).