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

1. ОИКС ИАТЭ НИЯУ МИФИ

Яцало Борис Иванович
Boris Yatsalo
[email protected]
[www.decerns.com]
2021

2.

МЕТОДЫ ОПТИМАЛЬНОГО
УПРАВЛЕНИЯ
Л-1
Экстремумы функций

3. Оптимальные Решения Примеры Классических Задач

1. Построить прямоугольник максимальной
площади с заданным периметром (частная задача, см. 4.1)
2. (Задача Эвклида) В треугольник вписать
параллелограмм максимальной площади
3. В плоскости треугольника найти точку, сумма
расстояний от которой до вершин треугольника
минимальна

4. Оптимальные Решения: Примеры Классических Задач

4.1 (Изопериметрическая задача)
Какую максимальную площадь можно
охватить замкнутой кривой заданной
длины ?
4.2 (Задача Дидоны) Дана веревка длины L.
Какую максимальную площадь
(у прибрежной зоны- вдоль прямой) можно
охватить данной веревкой ?

5. Оптимальные Решения: Примеры Классических Задач

5. (З. о Брахистохроне)
Даны точки А и В на разной высоте. По
какой кривой, соединяющей эти точки, шар
спустится за минимальное время (под
действием только силы тяжести)

6. Оптимальные Решения: Примеры Классических Задач

6. (З. об Оптимальном проектировании)
Коробка изготавливается из листов размера
a*b. Для этого из углов вырезают квадраты
x*x и сгибают вдоль линий.
Как делать вырезы так, чтоб получить
коробку максимального обЪема ?

7. Задача о перевозках (транспортная задача)

7. Имеется m пунктов производства (поставки) некоторого
однородного продукта и n пунктов его потребления. Для
каждого пункта производства i=1,…,m, и каждого пункта его
потребления j=1,…,n, заданы:
ai – объем производства в пункте i;
bj – объем потребления в пункте j;
сij – затраты на перевозку 1цы продукта от пункта производства
i до пункта потребления j.
(потребление не превышает производства).
Задача: Составить план перевозок:
- не выводящий за пределы производства,
- полностью обеспечивающий всех потребителей,
- дающий минимум суммарных затрат на перевозку

8. Задача о бродячем торговце (задача коммивояжера)

8. Имеется n+1 город;
сij – матрица расстояния между городами (i -j)
Выезжая из исходного города, коммивояжер
должен побывать во всех остальных городах
ровно 1 раз и вернуться в исходный город.
Составить оптимальный маршрут…
(по времени, стоимости, расстоянию)

9. Задачи Оптимального Управления

9. (простейшая задача о быстродействии )
(движение управляемой тележки)
Масса тележки m, в точке x0, скорость- v0.
Внешняя сила (тяга) – u, текущая координата –
x(t), задаются физические ограничения на тягу.
Задача: как за минимальное время, с учетом всех
ограничений на управление (скорость,
ускорение) достичь точки x0 и остановиться
(достичь с нулевой скоростью)

10. Непрерывные Функции

Дана ф-я f(x), x D
одномерная ф-я:
f :D ;
D
D
многомерная ф-я
x=(x1,…,xn ) ф-ия f(x)=f(x1,…,xn ) в D
n
Непрерывная ф-я: если при x x0 lim f(x)=f(x0),
тогда ф-я непрерывна в т. x0
Ф-я f(x) непрерывна в области D, if она
непрерывна в каждой точке x D

11. Непрерывные Функции

Дана ф-я f(x), x D
одномерная ф-я:
f :D ;
D
D
многомерная ф-я
x=(x1,…,xn ) ф-ия f(x)=f(x1,…,xn ) в D
n
Непрерывная ф-я: если при x x0 lim f(x)=f(x0),
тогда ф-я непрерывна в т. x0
Ф-я f(x) непрерывна в области D, if она
непрерывна в каждой точке x D

12. Непрерывные Функции

D=[a,b] – отрезок, - замкнутое множество
(=содержит все свои предельные очки)
D=(a,b) – интервал.
Свойства:
Th. (Больцано-Коши о промежуточном значении)
Если непрерывная ф-я принимает на отрезке
знаечния разных знаков, то найдется точка, в
которой ф-я =0.
Th (Вейерштрасса о максим и миним значениях)
Непрерывная на отрезке ф-я ограничена и есть
точки, где ф-я принимает максим и миним
значения.

13. Свойства непрерывных функций

Тh. (Вейерштрасса)
Непрерывная ф-я f(x1,…,xn) ,
заданная на компакте K , достигает
на этом компакте своего максимума
и минимума.

14. Дифференцируемые ф-ии

f :D ;
x D
Дана ф-я f(x),
Ф-я f(x), определенная в D,
называется дифференцируемой в т. a,
если
f ( x h) f ( x) A( x)h ( x, h),
где ( x, h) o(h)
При этом:
D
df ( x) A( x)h f' ( x)dx называют дифференциалом
df ( x)
A( x) f' ( x)
производная
dx
f ( x h) f ( x )
f' ( x) lim
(h x)
h
h 0

15. Дифференцируемые ф-ии

x D
f :D ;
С(X) – множ-во непрерывных в области X функций,
D(X) – дифференцируемые в X функции,
Обозначения:
частое обозначение f Ck(X) :
существует k производных, и k-ая производная
непрерывна
D

16. Частные производные

Дана ф-я f(x),
f(x)=f(x1,…,xn ) в D
Частные производные:
f ( x, y ) f ( x, y )
;
,
x
y
2 f ( x, y ) 2 f ( x, y ) 3 f ( x, y )
;
;
2
3
x
x y
x
'
x
f ( x, y );
''
xx
f ( x, y )
f (...)
f ( x1 , x2 ,..., xn )
xi
n

17. Экстремумы

n
Пусть
D
Рассмотрим классические методы оптимизации,
сводящиеся к нахождению оптимума
ф-ии f(x1,…,xn) в D.
Дана ф-я f : D ;
Def. Точка x0 назыв т. глобального максимума
(в D), если для всех x D выполняется нер-во
f ( x) f ( x0 )

18. локальный экстремум

Пусть
D
f :D ;D
n
n
Def. Точка x0 назыв т. локального максимума
ф-ии f(x) (в области D),
если существует окрестность т. x0 , U(x0 ), такая, что
для всех
x U ( x0 )( D)
выполняется нер-во
f ( x) f ( x0 )
Примеры (лок и глоб экстремумов)

19. Базовая теорема

Пусть D
Th (Ферма). Если x0 - т. локального экстремума
дифференцируемой ф-ии f(x) в откр. Области D,
f ( x ) 0
тогда
Пусть St(f)={x: f’(x)=0} – множ-во стационарных точек.
Тогда: точки экстремума содержатся в множ-ве
стационарных точек (обратное не верно).
Пусть D=[a, b] – отрезок на прямой.
f задана на прямой, тогда точки глобального экстремума
содержатся в множ-ве критических точек
Kr ( f ) St ( f ) {a, b}

20. Базовая теорема

Пусть
f :D ;D
n
т.е., f = f(x1,…,xn).
Th (обобщение). Если x0 - т. локального экстремума
0 ) 0
дифференцируемой ф-ии f(x1,…,xn), тогда f (x
Здесь:
f(x)
f(x)
f (x) (
,...,
) grad f ( x ) f ( x )
x1
xn
(опрератор набла)

21. Глобальный экстремум

Правило. Точки глобального экстремума
содержатся в множестве ее критических точек:
где D - граница области D.
Kr ( f ) St ( f ) D

22. Линии уровня

Графический метод нахождения экстремумов на
примере n=2.
Линии уровня функции f(x,y):
(min f≤ c ≤max f)
Lc {( x, y) : f ( x, y) c}
Через каждую точку плоскости М(x0,y0) (входящую в
область определения фу-ии) проходит только одна
линия уровня: f(x,y)= f(x0,y0)
1. Графический метод нахожд. экстремумов ф-ий на
основе нахождения линий уровня. (рис с.30,31, ВР).
2. Использование градиента функции: Направление
градиента совпадает с направлением наибольшей
скорости роста фу-и в каждой точке. Он
перпендикулярен линии уровня.

23. Нахождение Экстремумов

Примеры задач
f opt (max, min)
1. y=f(x) extr (sup / max; inf / min )
2. f(x,y) extr
3. f(x,y)=C extr (анализ линий уровня)

24. Условный экстремум

Метод Лагранжа нахождения усл. экстремумов
функций в заданной области.
Задача: Пусть f : D ; D n , f = f(x1,…,xn).
f→opt (max/min) при условии, что x=(x1,…,xn)
удовлетворяют системе ограничений
g1 ( x ) 0,
...
gm ( x) 0
(предполагается, что фу-ии f и gi являются
ф-ями класса C1 в области определения

25. Оптимизация при наличии ограничений

Метод решения: функция Лагранжа:
L( x1 ,..., xn , 1 ,..., m ) f ( x1,..., xn ) 1g1 ( x1,..., xn ) ... m gm ( x1,..., xn )
Или (в более компактном виде):
L( x, ) f ( x ) 1 g1 ( x ) ... m gm ( x)
f ( x ) ( λ, g), λ = ( 1 ,..., m ), g ( g1 ,..., gm ).
Правило нахождения экстремумов:
Точка условного экстремума является стационарной
точкой фу-ии Лагранжа,т.е.:
L
L
0, i 1,..., n;
0, j 1,..., m.
xi
j