Презентация на тему: МЕТОДЫ ОПТИМИЗАЦИИ

МЕТОДЫ ОПТИМИЗАЦИИ
Динамическое программирование
Введение
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
Формулировка задачи динамического программирования
Пример
Математическая запись
Принцип оптимальности Беллмана
Алгоритм решения задач динамического программирования
Алгоритм решения задач динамического программирования
Экономические приложения
Общая постановка задачи динамического программирования
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
Принцип оптимальности
Уравнение Беллмана.
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
Экономические задачи
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
МЕТОДЫ ОПТИМИЗАЦИИ
1/52
Средняя оценка: 4.0/5 (всего оценок: 46)
Код скопирован в буфер обмена
Скачать (614 Кб)
1

Первый слайд презентации: МЕТОДЫ ОПТИМИЗАЦИИ

Кафедра математических методов в экономике

Изображение слайда
2

Слайд 2: Динамическое программирование

Введение Формулировка задачи динамического программирования Принцип оптимальности Беллмана Алгоритм решения задач динамического программирования Экономические приложения задач динамического программирования

Изображение слайда
3

Слайд 3: Введение

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

Изображение слайда
4

Слайд 4

Возникновение этого метода связывают с именем американского ученого Р. Беллмана, который в начале 50-х годов ХХ века применил к ряду конкретных задач прием, названный впоследствии принципом оптимальности. Основной областью приложения последнего являются многошаговые процессы, т. е. процессы, развивающиеся во времени, что дало основание назвать новый метод оптимизации динамическим. Указанием на динамичность этот метод отличался от линейного и математического программирования, исходная постановка основных задач которых имела статический характер.

Изображение слайда
5

Слайд 5

Трудно дать четкое определение динамическому программированию. Укажем лишь на три характерные его особенности. Кроме принципа оптимальности, основного приема исследования, большую роль в аппарате динамического программирования играет идея погружения конкретной задачи оптимизации в семейство аналогичных задач. Третьей его особенностью, выделяющей его среди других методов оптимизации, является форма конечного результата. Применение принципа оптимальности и принципа погружения в многошаговых, дискретных процессах приводят к рекуррентно-функциональным уравнениям относительно оптимального значения критерия качества. Полученные уравнения позволяют последовательно выписать оптимальные управления для исходной задачи. Выигрыш здесь состоит в том, что задача вычисления управления для всего процесса разбивается на ряд более простых задач вычисления управления для отдельных этапов процесса. Главным недостатком метода является «проклятие размерности» – его сложность катастрофически возрастает с увеличением размерности задачи.

Изображение слайда
6

Слайд 6: Формулировка задачи динамического программирования

Дано: множество состояний в том числе начальное и конечное множество возможных переходов из одного состояния в другое с каждым переходом связывается числовой параметр интерпретируется как затраты, выгода, расстояние, время и т.п. Найти: оптимальную последовательность переходов ( путь ) из начального состояния в конечное максимум или минимум суммы числовых параметров предполагается, что хотя бы один путь из начального состояния в конечное существует

Изображение слайда
7

Слайд 7: Пример

0 18 1 2 3 5 7 6 8 10 12 11 13 4 14 15 16 9 17 3 8 5 4 4 7 4 12 7 6 9 1 1 4 2 16 0 7 9 10 8 5 5 11 12 9 3 8 4 -2 4 4

Изображение слайда
8

Слайд 8: Математическая запись

1, если путь проходит через дугу ( i, j ) 0, если не проходит или такой дуги нет Например, расстояние между пунктами i и j, км {(1,2), (1,3), (2,4), (2,5), (3,5)…} единственность искомого пути: в каждую вершину можно прийти только из одной вершины (или вообще нельзя) если искомый путь пришёл в вершину k, то он должен из неё выйти (если только она не конечная) Условие целочисленности переменных Между вершинами i и j нет дуги. сумма числовых значений ( eg. расстояний) по всему пути

Изображение слайда
9

Слайд 9: Принцип оптимальности Беллмана

Если вершины A и B лежат на оптимальном пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B. Следствие Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A Продолжения неоптимальных путей к предшествующим вершинам можно не просчитывать: они никогда не дадут оптимального пути к A Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования

Изображение слайда
10

Слайд 10: Алгоритм решения задач динамического программирования

0 18 1 2 3 5 7 6 8 10 12 11 13 4 14 15 16 9 17 3 8 5 4 4 7 4 12 7 6 9 1 1 4 2 16 0 7 9 10 8 5 5 11 12 9 3 8 4 -2 4 4 0 3 11 15 15 19 35 5 9 4 18 14 18 28 23 34 4 27 37 45 максимум

Изображение слайда
11

Слайд 11: Алгоритм решения задач динамического программирования

0 18 1 2 3 5 7 6 8 10 12 11 13 4 14 15 16 9 17 3 8 5 4 4 7 4 12 7 6 9 1 1 4 2 16 0 7 9 10 8 5 5 11 12 9 3 8 4 -2 4 4 0 4 5 11 3 7 11 15 17 15 16 13 4 19 16 11 12 12 14 23 минимум

Изображение слайда
12

Слайд 12: Экономические приложения

Изображение слайда
13

Слайд 13: Общая постановка задачи динамического программирования

Изображение слайда
14

Слайд 14

Изображение слайда
15

Слайд 15

Изображение слайда
16

Слайд 16

Изображение слайда
17

Слайд 17

Изображение слайда
18

Слайд 18: Принцип оптимальности

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

Изображение слайда
19

Слайд 19: Уравнение Беллмана

Изображение слайда
20

Слайд 20

Изображение слайда
21

Слайд 21

Изображение слайда
22

Слайд 22

Изображение слайда
23

Слайд 23

Изображение слайда
24

Слайд 24

Изображение слайда
25

Слайд 25

Изображение слайда
26

Слайд 26

Изображение слайда
27

Слайд 27

Изображение слайда
28

Слайд 28

Изображение слайда
29

Слайд 29

Изображение слайда
30

Слайд 30: Экономические задачи

Изображение слайда
31

Слайд 31

Изображение слайда
32

Слайд 32

Изображение слайда
33

Слайд 33

Изображение слайда
34

Слайд 34

Изображение слайда
35

Слайд 35

Изображение слайда
36

Слайд 36

Изображение слайда
37

Слайд 37

Изображение слайда
38

Слайд 38

Изображение слайда
39

Слайд 39

Изображение слайда
40

Слайд 40

Изображение слайда
41

Слайд 41

Изображение слайда
42

Слайд 42

Изображение слайда
43

Слайд 43

Изображение слайда
44

Слайд 44

Изображение слайда
45

Слайд 45

Изображение слайда
46

Слайд 46

Изображение слайда
47

Слайд 47

Изображение слайда
48

Слайд 48

Изображение слайда
49

Слайд 49

Изображение слайда
50

Слайд 50

Изображение слайда
51

Слайд 51

Изображение слайда
52

Последний слайд презентации: МЕТОДЫ ОПТИМИЗАЦИИ

Изображение слайда