Решебник_МО

Следует отметить, что множители Лагранжа используют также в качестве вспомогательного средства и при решении специальными методами задач других классов с ограничениями типа равенств, например, в вариационном исчислении и динамическом программировании.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1.Что называют градиентом функции?

2.Что называют антиградиентом функции?

3.Верно ли, что модуль (величина) градиента характеризует скорость возрастания функции?

4.Какие условия существования экстремума целевой функции при отсутствии ограничений на ее параметры вам известны?

5.Какие условия существования экстремума целевой функции с параметрическими ограничениями вам известны?

6.Как формируется функция Лагранжа?

7.Для каких задач оптимизации составляется функция Лагранжа?

8.Какое число неопределенных множителей Лагранжа может быть в задаче условной оптимизации, если число переменных в составе оптимизируемой функции равно 8:

а) не более 7;

b)не более 8;

c)любое количество.

9.Для решения задачи условной оптимизации методом неопределенных множителей Лагранжа обязательно:

а) знание аналитического выражения оптимизируемой функции;

b)наличие ограничений только в виде равенств;

c)линейность ограничений.

10.Выберете функцию Лагранжа для задачи

f (x) 12 ax12 12 bx22 extr (a 0, b 0) , (x) x13 x23 1 0 :

а) F(x, ) 12 ax12 12 bx22 (x13 x23 1) ; b) F(x, ) x13 x23 1 ( 12 ax12 12 bx22 );

32

c)F(x, ) x13 12 bx22 ( 12 ax12 x23 1);

d)F(x, ) 12 ax12 x23 (x13 12 bx22 1) ;

e)F(x, ) 12 ax12 12 bx22 1 (x13 x23 ) .

11.Какие условия существования экстремума целевой функции при

наличии ограничений равенством вам известны?

12.Какие условия существования экстремума целевой функции при наличии ограничений-неравенств вам известны?

13.Сформулируйте алгоритм решения общей задачи математического программирования.

14.Какую задачу оптимизации называют двойственной к исходной?

15.Как составляется двойственная задача?

16.Что является седловой точкой функции Лагранжа?

17.На что указывает неопределённый множитель Лагранжа λj?

18.Назовите недостатки-ограничения аналитических методов оптимизации.

УПРАЖНЕНИЯ

1.Найдите экстремум функции f (x) 5x12 10x1x2 x22 6x1 3x2 и исследуйте его на максимум и минимум.

2.Найдите стороны прямоугольника максимальной площади, вписанного в круг х2+y2=r2.

3.Найдите размеры прямоугольного параллелепипеда наибольшего объема с гранями, параллельными координатным плоскостям,

6.Найдите максимальное значение функции f=x–у при условии

х2+у2<1; х+у=1.

33

13.Найдите максимальное и минимальное значения функции f=х2+у в области G, заданной неравенствами 2x2 y2 5; x 2y 3.

16.(Задача Аполлония) Проведите из данной точки к данному эллипсу отрезок минимальной длины.

17.(Задача Штейнера) Найти такую точку на плоскости, чтобы сумма расстояний от нее до трех заданных точек была минимальной.

34

ОДНОМЕРНЫЙ ПОИСК

Аналитические методы оптимизации позволяют решать широкий класс задач, однако они обладают и рядом существенных недостатков-ограничений, основными из них являются следующие:

1.Как целевая функция решаемой задачи, так и все функции ограничения должны быть непрерывными функциями, частные производные которых также являются непрерывными функциями.

2.В общем случае количество задач, решаемых методом Лагранжа,

нелинейной системы уравнений.

3.Целевая функция и все ограничения должны быть заданы в аналитическом виде.

Это достаточно серьезные ограничения, поэтому усилия математиков были направлены на разработку таких методов решения экстремальных задач, для реализации которых достаточно иметь возможность определять значение целевой и ограничивающей функций в произвольной точке из области их задания любым способом, т.е. не только вычислять, но и измерять значения целевой функции, если она отражает какой-либо физический процесс.

Наиболее разработанными методами нелинейного программирования являются методы одномерного поиска.

В методах одномерной оптимизации рассматривается отрезок X=[a,b], содержащий искомое решение x*. Такой отрезок называется отрезком неопределенности, или отрезком локализации. Относительно целевой функции f(x) часто предполагается, что она унимодальная.

Функция f(x) называется унимодальной на отрезке X=[a,b], если существует такая точка x*X, что f(x1)>f(x2) или f(x1)<f(x2), где x1<x2<x*, x1,x2 X. Если ограничиваться рассмотрением лишь непрерывных функций f(x), то свойство унимодальности функции попросту означает наличие у нее единственного локального максимума (минимума) и этот максимум (минимум) достигается в точке x*.

В ряде методов относительно целевой функции f(x) предполагается, что она выпуклая на X.

35

Функция f(x) называется выпуклой на Х=[a,b], если для любых x1,x2 X и всех , 0 1 справедливо соотношение: f(x1+(1–)x2)f(x1)+(1–)f(x2). Если при любых x1,x2 X неравенство будет строгим, то функция f(x) называется строго выпуклой.

Непрерывная строго выпуклая функция является унимодальной. Однако не всякая унимодальная функция является выпуклой или непрерывной.

Функция f(x) имеет локальный минимум в точке х0, если существует некоторая положительная величина , такая, что если |xi–x0|<, то f(xi) f(x0), т.е. если существует окрестность точки х0, такая, что для всех значений хi из этой окрестности f(xi) > f(x0). Функция f(x) имеет глобальный минимум в точке x0, если для всех хi справедливо неравенство f(xi) f(x0).

КРИТЕРИЙ ЭФФЕКТИВНОСТИ ПОИСКА

Пусть необходимо найти максимум унимодальной функции одной переменной f(х), заданной на единичном отрезке и не имеющей на ней горизонтальных участков. Функция f(x) может не быть гладкой функцией, она может иметь изгибы и даже разрывы первого рода. Будем считать, что имеется возможность без всяких ошибок определять значения f(x) в любой точке 0x 1 (проводить «измерение» в точке x0). Для поиска максимума f(x) будем использовать результаты измерений в заданном количестве точек х.

Ясно, что результат одного измерения не позволяет сделать никакого суждения о положении максимума. Совсем иное дело, когда имеем результаты двух измерений f(x1), f(x2), причем x1<x2. В этом случае могут встретиться три ситуации (рис. 1):

Рис. 1. Возможные результаты проведения двух измерений

36

0,3 х1 х2 х3 = 0,8. Не трудно видеть, что min max (х2,1–х2) = 0,5, при х2 = 0,5.

Таким образом, оптимальной стратегией будет всякая пассивная стратегия (х1, х2, х3), для которой х2 = 0,5 и х3–х1 ≤ 0,5,

которая дает L*3 = 0,5.

Из сравнения примеров проведения экспериментов в 2–х и 3–х точках следует, что добавление третьего эксперимента, требующего дополнительных средств и усилий в случае пассивного поиска, мало

использование нечетного числа экспериментов целесообразно лишь при большой погрешности измерений . Эффективность процесса поиска можно оценить отношением (L0/Ln).

ПАССИВНЫЙ ПОИСК

Стратегии пассивного поиска применяются когда нельзя реализовать последовательную процедуру. Такая ситуация возникает, напримет, при управлении доменным или любым химическим процессом, когда нет времени на последовательный анализ, а делается одновременный параллельный замер нужных параметров. При этом необходимо определить новые значения управляющих параметров, которые обеспечили бы оптимальную близость к экстремуму.

Из рассмотренных примеров можно сделать вывод, что существенное сокращение интервала неопределенности может дать лишь пара измерений. И если пара измерений сократила его почти в два раза, то k пар измерений может сократить этот интервал в (k+1)-раз (без учета ). Для этого достаточно все пары расположить равномерно на единичном интервале, причем расстояние между экспериментами одной пары должно составлять .

С учетом величина L2k окажется несколько больше, чем

[1/(к+1)]. Найдем величину L2k . Точка предпоследнего эксперимента

х2k-1 должна быть расположена на расстоянии х2k-1 от

начала интервала исследования, а длина последнего возможного интервала, содержащего точку х2k , есть величина интервала

39

L2k–1 = 1–х2k–1. Потребуем, чтобы L2k–1 = L2k , т.е. 1–х2k–1 = 1– (k L2k –

– ) = 1–k L2k + = L2k . Отсюда имеем: 1+ = L2k (1+k) и L2k = (1+ )\(1+k).

Такая стратегия поиска называется поиском однородными парами. План проведения эксперимента методом однородных пар показан на рис. 4.

Рис, 4, План проведения поиска однородными парами

Точность такого процесса определяется количеством выбранных точек n, т.е. количеством измерений функции f(x), называемых для краткости экспериментами, и характеризуется интервалом неопределенности Ln, полученным после проведения всех

n экспериментов и равным Ln = L2k ≈ 2L0/(n+l).

Эффективность процесса поиска можно оценить отношением

(L0/Ln) = (n+1)/2.

Простейшим методом одномерного пассивного поиска является обычный перебор значений минимизируемой функции f(x) в конечном числе точек хj (j = l,…,n), равномерно распределенных на интервале [a,b], с выбором наименьшего значения f(x*) = min f(xj).

Значение x*j , в силу свойства унимодальности, может быть приближенно принято за искомое оптимальное значение.

ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК

Пусть необходимо найти минимум унимодальной функции f(x) на интервале [a,b]. Равномерное распределение всех экспериментов на интервале поиска [a,b] не является наилучшим. Если результаты каждого измерения использовать при выборе точки следующего

40