Динамическое программирование. (Семинар 3) презентация

Содержание

Задача динамического программирования Рассмотрим динамическую систему, которая последовательно за n шагов переходит из состояния в состояние Промежуточные состояния определяют состояния системы после i-го шага. Как

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

Слайд 2Задача динамического программирования
Рассмотрим динамическую систему, которая последовательно за n шагов переходит

из состояния в состояние
Промежуточные состояния определяют состояния системы после i-го шага. Как правило, состояния системы определяются несколькими числами, поэтому предполагается, что являются векторами, т.е.

Слайд 3Переход системы из состояния в состояние

определяется параметрами (управлениями) при помощи уравнения состояний

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

Слайд 4Задача состоит в том, чтобы найти набор управлений

, оптимизирующий (далее предполагается, что решается задача на максимум):

Процесс решения разбивается на n шагов.
Введём функцию:


- эта функция характеризует эффективность перехода от состояния к .

Слайд 5
Последовательно оптимизируем


По формулам, называемым уравнениями Беллмана

Слайд 6






находим максимальное решение задачи.

Слайд 7Задача о распределении средств между предприятиями
Процесс решения задачи начинается с оптимизации

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

Слайд 8Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют

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

Задача 1

Слайд 9В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить

оптимальный план распределения средств и найти максимальную прибыль, если
n = 4, а

Задача 1

Слайд 10Решение:
Динамической системой являются два предприятия, состояния которых определяются вложенными

в них средствами, а управления на i-м году являются средствами , переданные k-й отраслью.
Так как возвращённые средства распределяются полностью, то имеет место условие
т.е. и фактически задача одномерна.

Слайд 11Далее будем считать, что управление на i-м году определяется числами

, т.е. средствами, выделенными первой отрасли.
В силу того же условия уравнения состояний имеют вид:


А прибыль на i-м году равна:


Слайд 12Решение задачи начинается с оптимизации функции

:



Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому:
при


Слайд 13Далее,


при



при

Слайд 14

при





Таким образом, поскольку на каждом шаге
,то средства каждый год вкладываются в первую отрасль:
у.е.
у.е.
у.е.

Слайд 15




Максимальная прибыль равна
у.е.
Полученные результаты можно записать в виде таблицы, в которой по годам указано распределение средств:


Слайд 16Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют

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

Задача 2

Слайд 17В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить

оптимальный план распределения средств и найти максимальную прибыль, если
n = 4, а

Задача 2

Слайд 18Решение:
Динамической системой являются два предприятия, состояния которых определяются вложенными

в них средствами, а управления на i-м году являются средствами , переданные k-й отраслью.
Так как возвращённые средства распределяются полностью, то имеет место условие
т.е. и фактически задача одномерна.

Слайд 19Далее будем считать, что управление на i-м году определяется числами

, т.е. средствами, выделенными первой отрасли.
В силу того же условия уравнения состояний имеют вид:


А прибыль на i-м году равна:


Слайд 20Решение задачи начинается с оптимизации функции

:



Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому:
при


Слайд 21Далее,


при



при

Слайд 22

при





Таким образом на первом шаге , т.е. средства в четвёртом периоде вкладываются только в первую отрасль, а на последующих шагах средства вкладываются только во вторую отрасль, т.к.
у.е.
у.е.
у.е.

Слайд 23




Максимальная прибыль равна
у.е.
Полученные результаты можно записать в виде таблицы, в которой по годам указано распределение средств:


Слайд 24Рассмотрим теперь задачи о распределении средств между несколькими предприятиями на один

год.

Слайд 25Планируется работа n предприятий на один год. Начальные средства равны

тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .

Задача 3

Слайд 26Задача 3
Определить оптимальный план распределения средств и найти максимальную прибыль, если

, n = 3, а функции заданы в виде таблицы:

Слайд 27Решение:
Шагом задачи будем считать выделение средств очередному предприятию, а переменные управления

ui (i = 1, 2, 3) – средства, выделеные i-му предпритятию.
Таким образом, получаем следующую задачу оптимизации:

Слайд 28Состояние sk определяется количеством оставшихся после k шагов средств (средств, вкладываемых

в инвестиции на k–м шаге в предприятия с k-го по n-й).
Уравнения состояний:

Слайд 29 1 этап. Условная оптимизация
1-й шаг: для получения максимума прибыли с

последнего предприятия, вложим в него все средства:
,

u3

s3

Слайд 30 1 этап. Условная оптимизация
2-й шаг: определим оптимальную стратегию инвестирования во

2-е и 3-е предприятия. При этом уравнение Беллмана:


u2

s2

Слайд 31 1 этап. Условная оптимизация
3-й шаг: определим оптимальную стратегию инвестирования в

1-е, 2-е и 3-е предприятия. При этом уравнение Беллмана:


u1

s1

Слайд 32 2 этап. Безусловная оптимизация
1-й шаг: максимальный доход при инвестировании 4

тыс. у.е. между 3 предприятиями составляет:
При этом 1-му предприятию нужно выделить
тыс. у.е.

2-й шаг: Определим величину оставшихся денежных средств, приходящегося на долю
2-го и 3-го предприятий:
тыс. у.е.

Слайд 33 2 этап. Безусловная оптимизация
По данным 2-й таблицы оптимальный вариант распределения

денежных средств в размере 4 тыс. у.е. между 2-м и 3-м предприятиями составляет:
При этом 2-му предприятию нужно выделить
тыс. у.е.
3-й шаг: Определим величину оставшихся денежных средств, приходящегося на долю
3-го предприятия:
тыс. у.е.

Слайд 34 2 этап. Безусловная оптимизация
По данным 1-й таблицы оптимальный вариант распределения

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

Слайд 35Планируется работа n предприятий на один год. Начальные средства равны

тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .

Задача 4

Слайд 36Задача 4
Определить оптимальный план распределения средств и найти максимальную прибыль, если

, n = 3, а функции заданы в виде таблицы:

Слайд 37Решение:
Шагом задачи будем считать выделение средств очередному предприятию, а переменные управления

ui (i = 1, 2, 3) – средства, выделеные i-му предпритятию.
Таким образом, получаем следующую задачу оптимизации:

Слайд 38Состояние sk определяется количеством оставшихся после k шагов средств (средств, вкладываемых

в инвестиции на k–м шаге в предприятия с k-го по n-й.
Уравнения состояний:

Слайд 39 1 этап. Условная оптимизация
1-й шаг: для получения максимума прибыли с

последнего предприятия, вложим в него все средства:
,

u3

s3

Слайд 40 1 этап. Условная оптимизация
2-й шаг: определим оптимальную стратегию инвестирования во

2-е и 3-е предприятия. При этом уравнение Беллмана:


u2

s2

Слайд 41 1 этап. Условная оптимизация
3-й шаг: определим оптимальную стратегию инвестирования в

1-е, 2-е и 3-е предприятия. При этом уравнение Беллмана:


u1

s1

Слайд 42 2 этап. Безусловная оптимизация
1-й шаг: максимальный доход при инвестировании 4

тыс. у.е. между 3 предприятиями составляет:
При этом 1-му предприятию нужно выделить
тыс. у.е.

2-й шаг: Определим величину оставшихся денежных средств, приходящегося на долю
2-го и 3-го предприятий:
тыс. у.е.

Слайд 43 2 этап. Безусловная оптимизация
По данным 2-й таблицы оптимальный вариант распределения

денежных средств в размере 4 тыс. у.е. между 2-м и 3-м предприятиями составляет:
При этом 2-му предприятию нужно выделить
тыс. у.е.
3-й шаг: Определим величину оставшихся денежных средств, приходящегося на долю
3-го предприятия:
тыс. у.е.

Слайд 44 2 этап. Безусловная оптимизация
По данным 1-й таблицы оптимальный вариант распределения

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

Слайд 45Методы оптимизации
Функция спроса D(p) определяет спрос (количество купленного товара) при цене

p за единицу продукции.
Функция предложения S(p) задает количество товара, которое поставщик может предложить по рыночной цене p.

Слайд 46Методы оптимизации
Говорят, что рынок находится в равновесии, если покупатели могут купить

столько товара, сколько им необходимо, а продавец может реализовать весь товар, который он намерен продать.
Равновесная цена р0 товара на рынке находится из условия S(р0) = D(р0), а количество q0 проданного товара q0 = D(р0).

Слайд 47Предположим, что на продукцию компании вводится (дополнительный) фиксированный налог t на

каждую единицу реализованного товара.
Если ставка налога достаточно велика, то производство товара будет невыгодно, и это приведет его к остановке.
Возникает вопрос о такой ставке налога, чтобы итоговый сбор был максимальным.

1. Оптимизация налогообложения

Слайд 48 Пусть доход от продажи (выручка):

а затраты на выпуск продукта

в зависимости от количества q:

Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор.
Как уменьшится количество выпускаемой продукции?

Задача 5


Слайд 49Решение:
Найдем объем производства без учета дополнительного налога.
Найдем функцию прибыли:


Из ее

производной
находим, что максимум прибыли достигается при объеме производства:


Слайд 50По причине введения дополнительного налога доход производителя уменьшится на величину Т

= tq и составит

а его прибыль



Слайд 51В результате компания исходит из того, чтобы при реализации товара получить

максимальную прибыль.
Решим уравнение:


Общая налоговая выплата составит:

Слайд 52Вычислим максимум функции Т = T(t).
Из условия T’(t) = 0 следует,

что

т.е.
Точка является точкой максимума функции T(t). При этом весь налоговый сбор:

Слайд 53Объем производства:

Таким образом, введение дополнительного налога уменьшает объем производства в 2

раза (с 6 до 3 ед. продукции).

Ответ:

Слайд 54 Пусть доход от продажи (выручка):

а затраты на выпуск продукта

в зависимости от количества q:

Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор.
Как уменьшится количество выпускаемой продукции?

Задача 6


Слайд 55Решение:
Найдем объем производства без учета дополнительного налога.
Найдем функцию прибыли:


Из ее

производной
находим, что максимум прибыли достигается при объеме производства:


Слайд 56По причине введения дополнительного налога доход производителя уменьшится на величину Т

= tq и и составит

а его прибыль



Слайд 57В результате компания исходит из того, чтобы при реализации товара получить

максимальную прибыль.
Решим уравнение:


Общая налоговая выплата составит:

Слайд 58Вычислим максимум функции Т = T(t).
Из условия T’(t) = 0 следует,

что

т.е.
Точка является точкой максимума функции T(t). При этом весь налоговый сбор:

Слайд 59Объем производства:

Таким образом, введение дополнительного налога уменьшает объем производства в 2

раза (с 9 до 4,5 ед. продукции).

Ответ:

Слайд 60 Для товаров X1 и X2 известны функции спроса:


Фирма-монополист имеет функцию издержек:


Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план.

Задача 7


2. Оптимизация прибыли

Слайд 61Решение:
Найдем цены товаров X1 и X2 :


Последовательно находим общую выручку:



Прибыль:





Слайд 62Критические точки функции найдем из

системы:


Решением системы является точка (5;4).
Найдем матрицу вторых производных G(П) функции , которая не зависит от точки:

Слайд 63имеет угловые миноры

Поэтому точка (5;4) в силу выпуклости функции

прибыли, является точкой ее глобального максимума и


Ответ:


Слайд 64 Для товаров X1 и X2 известны функции спроса:


Фирма-монополист имеет функцию издержек:


Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план.

Задача 8


Слайд 65Решение:
Найдем цены товаров X1 и X2 :


Последовательно находим общую выручку:



Прибыль:





Слайд 66Критические точки функции найдем из

системы:


Решением системы является точка:


Найдем матрицу вторых производных G(П) функции , которая не зависит от точки:

Слайд 67имеет угловые миноры


Поэтому точка

в силу выпуклости функции прибыли, является точкой ее глобального максимума и





Слайд 68

Ответ:


Слайд 69Задачи многокритериальной оптимизации
Задача вида:


где i > 1,

- допустимое множество;
fi(x) – гладкие функции на D, называется задачей многокритериальной оптимизации.
Область допустимых решений D задается системой уравнений и неравенств.

Слайд 70Пусть X и Y – два допустимых решения. Говорят, что X

доминирует Y, если для всех
i = 1, 2, …, n выполняется неравенство
fi(X) ≥ fi(Y) и найдется такое k, что fk(X) > fk(Y).
Решение Z называется недоминируемым (эффективным), если нет решения X, которое бы доминировало Z.

Слайд 71Множество эффективных (недоминируемых) решений называется множеством Парето.
Геометрическое изображение множества Парето называется

Парето-эффективной границей (Парето-оптимальной границей).
В задаче многокритериальной оптимизации наилучшее решение следует искать в множестве Парето.

Слайд 72Алгоритм построения Парето-эффективной границы:
1. Строим допустимое множество D, заданное системой ограничений

как пересечение полуплоскостей, соответствующих каждому неравенству, входящему в эту систему.
2. Для каждой функции
строим линию уровня как прямую, перпендикулярную соответствующему вектору нормали .

Слайд 73Каждая из этих линий разбивает плоскость XOY на две полуплоскости.
Пусть Пi

– полуплоскости, содержащие вектор градиента целевой функции fi, а их пересечение

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

Слайд 74 Найти Парето-эффективную границу задачи:





Задача 9


Слайд 75Решение:
По условию задачи область допустимых решений задана системой неравенств:




Построим данную область:


Слайд 76

В качестве допустимого множества получаем область ОАВСD с угловыми точками О(0;0),

А(0;4), В(3;4), С(5;2), D(5;0).




x2

x2 = 4

x1 + x 2 = 7


Для функций f1 и f2 построим линии уровня (f1 = const,
f2 = const) как прямые, перпендикулярные соответствующим векторам нормали



Слайд 77

Каждая из этих линий уровня разбивает плоскость XOY на две полуплоскости.


Рассмотрим те из них, которые содержат соответствующий вектор нормали.




x2

x2 = 4

x1 + x 2 = 7


Пусть

Перемещаем область П по границе множества D.



Слайд 78

x2
x2 = 4
x1 + x 2 = 7

Парето-эффективной границей будет отрезок

[BC]: множество точек


Ответ:



[BC] - Парето-эффективная граница; множество точек





Слайд 79 Найти Парето-эффективную границу задачи:





Задача 10


Слайд 80Решение:
По условию задачи область допустимых решений задана системой неравенств:




Построим данную область:


Слайд 81


В качестве допустимого множества получаем область ОАВС с угловыми точками О(0;0),

А(0;4), В(2;3), С(3;0).


x2

x1 +2 x 2 = 8

Для функций f1 и f2 построим линии уровня (f1 = const,
f2 = const) как прямые, перпендикулярные соответствующим векторам нормали



3x1 + x 2 = 9

Слайд 82


x2
x1 +2 x 2 = 8
3x1 + x 2 = 9
Каждая

из этих линий уровня разбивает плоскость XOY на две полуплоскости.
Рассмотрим те из них, которые содержат соответствующий вектор нормали.




Пусть

Перемещаем область П по границе множества D.



Слайд 83


x2
x1 +2 x 2 = 8
3x1 + x 2 = 9
Парето-эффективной

границей будет отрезок [OС]: множество точек


Ответ:



[OС] - Парето-эффективная граница; множество точек





Слайд 84Метод идеальной точки
Метод идеальной точки является геометрическим методом для многокритериальных задач.

Слайд 85 Решить задачу многокритериальной оптимизации методом идеальной точки:





Задача 11


Слайд 86Решение:
По условию задачи область допустимых решений задана системой неравенств:





Построим данную область:


Слайд 87В качестве допустимого множества получаем область ОАВСDЕ с угловыми точками О(0;0),

А(0;3), В(2;5), С(5;5), D(8;2), Е(8;0).



x2

x2 = 5

x1 + x 2 = 10

- x1 + x 2 = 3

Е

Введем линейное преобразование f:
, определенное критериями f1 и f2:


Слайд 88При этом:








f2
f(E)
f(D)
I
m
n
P

Слайд 89f2
f(E)
f(D)
I
m
n
P
По причине линейности f строим образ области D под действием преобразования

f на плоскости (f1; f2) –
шестиугольник с
вершинами f(О), f(А),
f(В), f(С), f(D), f(E).








Идеальная точка – I с координатами (f1.max; f2.max), которая не пренадлежит образу D.

Слайд 90f2
f(E)
f(D)
I
m
n
P
Компромиссной точкой является т. Р, принадлежащая D и ближайшая к I

– основание перпендикуляра, опущенного из I на отрезок, соединяющий
точки f(С) и f(D).









Найдем уравнение прямой m, проходящей через две данные точки, затем уравнение прямой n и получим координаты
точки Р как

Слайд 91Уравнение прямой m:


Уравнение нормали:

Уравнение прямой n:










f2
f(E)
f(D)
I
m
n
P

Слайд 92Решим систему уравнений:




Найдем компромиссную точку как прообраз Р:



Ответ:











Слайд 93 Решить задачу многокритериальной оптимизации методом идеальной точки:





Задача 12


Слайд 94Решение:
По условию задачи область допустимых решений задана системой неравенств:





Построим данную область:


Слайд 95В качестве допустимого множества получаем область ОАВСD с угловыми точками О(0;0),

А(0;7), В(2;7), С(5;4), D(5;0).



x2

x1 + x 2 = 9

x 2 = 7

Введем линейное преобразование f:
, определенное критериями f1 и f2:


Слайд 96При этом:








f2
f(D)
I
m
n
P

Слайд 97f2
f(D)
I
m
n
P
По причине линейности f строим образ области D под действием преобразования

f на плоскости (f1; f2) –
пятиугольник с
вершинами f(О), f(А),
f(В), f(С), f(D).








Идеальная точка – I с координатами (f1.max; f2.max), которая не пренадлежит образу D.

Слайд 98f2
f(D)
I
m
n
P
Компромиссной точкой является т. Р, принадлежащая D и ближайшая к I

– основание перпендикуляра,
опущенного из I на
отрезок, соединяющий
точки f(В) и f(С).








Найдем уравнение прямой m, проходящей через две данные точки, затем уравнение прямой n и получим координаты
точки Р как

Слайд 99f2
f(D)
I
m
n
P
Уравнение прямой m:


Уравнение нормали:

Уравнение прямой n:










Слайд 100Решим систему уравнений:




Найдем компромиссную точку как прообраз Р:



Ответ:











Слайд 101Спасибо за внимание!

Похожие презентации

Задание 11: текстовые задачи 440
Функции. Виды функций и их графики 675
Параллельный перенос 338
Аттестационная работа. Методическая разработка на тему Симметрия 244
Построение сечений многогранника 392
фрактали. Рекурсивна процедура отримання фрактальних кривих 623

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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

Для правообладателей

Яндекс.Метрика