Динамическое программирование. (Семинар 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Спасибо за внимание!


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

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

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

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

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


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

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