Презентация Динамическое программирование. (Семинар 3) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Динамическое программирование. (Семинар 3) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 101 слайд. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:101 слайд
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:938.15 kB
- Просмотров:57
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Динамическое программирование
Семинар 3:
№2 слайд
Содержание слайда: Задача динамического программирования
Рассмотрим динамическую систему, которая последовательно за n шагов переходит из состояния в состояние
Промежуточные состояния определяют состояния системы после i-го шага. Как правило, состояния системы определяются несколькими числами, поэтому предполагается, что являются векторами, т.е.
№3 слайд
Содержание слайда: Переход системы из состояния в состояние определяется параметрами (управлениями) при помощи уравнения состояний
Переход системы из состояния в состояние определяется параметрами (управлениями) при помощи уравнения состояний
Эффективность каждого шага оценивается функциями .
Таким образом, эффективность всего процесса характеризуется суммой
№4 слайд
Содержание слайда: Задача состоит в том, чтобы найти набор управлений , оптимизирующий (далее предполагается, что решается задача на максимум):
Задача состоит в том, чтобы найти набор управлений , оптимизирующий (далее предполагается, что решается задача на максимум):
Процесс решения разбивается на n шагов.
Введём функцию:
- эта функция характеризует эффективность перехода от состояния к .
№5 слайд
Содержание слайда: Последовательно оптимизируем
По формулам, называемым уравнениями Беллмана
№6 слайд
Содержание слайда: находим максимальное решение задачи.
№7 слайд
Содержание слайда: Задача о распределении средств между предприятиями
Процесс решения задачи начинается с оптимизации последнего шага, что называется обратным ходом вычислений и свойственно многим задачам динамического программирования.
Рассмотрим теперь несколько задач о распределении средств между предприятиями на несколько лет.
№8 слайд
Содержание слайда: Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере .
Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере .
Аналогично, для второй отрасли прибыль составляет , а возврат
№9 слайд
Содержание слайда: В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если
В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если
n = 4, а
№10 слайд
Содержание слайда:
№11 слайд
Содержание слайда: Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли.
Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли.
В силу того же условия уравнения состояний имеют вид:
А прибыль на i-м году равна:
№12 слайд
Содержание слайда: Решение задачи начинается с оптимизации функции :
Решение задачи начинается с оптимизации функции :
Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому:
при
№13 слайд
Содержание слайда:
№14 слайд
Содержание слайда:
№15 слайд
Содержание слайда:
№16 слайд
Содержание слайда: Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере .
Планируется работа двух отраслей промышленности на n лет. Начальные ресурсы составляют у.е. Средства x, вложенные в первую отрасль в начале года, дают в конце года прибыль и возвращаются в размере .
Аналогично, для второй отрасли прибыль составляет , а возврат
№17 слайд
Содержание слайда: В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если
В конце каждого года возвращённые средства полностью распределяются между предприятиями. Определить оптимальный план распределения средств и найти максимальную прибыль, если
n = 4, а
№18 слайд
Содержание слайда:
№19 слайд
Содержание слайда: Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли.
Далее будем считать, что управление на i-м году определяется числами , т.е. средствами, выделенными первой отрасли.
В силу того же условия уравнения состояний имеют вид:
А прибыль на i-м году равна:
№20 слайд
Содержание слайда: Решение задачи начинается с оптимизации функции :
Решение задачи начинается с оптимизации функции :
Для вычисления максимума заметим, что требуется найти максимум линейной функции на отрезке, поэтому:
при
№21 слайд
Содержание слайда:
№22 слайд
Содержание слайда:
№23 слайд
Содержание слайда:
№24 слайд
Содержание слайда:
№25 слайд
Содержание слайда: Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .
Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .
№26 слайд
Содержание слайда:
№27 слайд
Содержание слайда:
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда:
№30 слайд
Содержание слайда:
№31 слайд
Содержание слайда:
№32 слайд
Содержание слайда:
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда:
№35 слайд
Содержание слайда: Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .
Планируется работа n предприятий на один год. Начальные средства равны тыс. у.е. При этом x тыс. у.е., вложенные в k-е предприятие в начале года, дают в конце года прибыль .
№36 слайд
Содержание слайда:
№37 слайд
Содержание слайда:
№38 слайд
Содержание слайда:
№39 слайд
Содержание слайда:
№40 слайд
Содержание слайда:
№41 слайд
Содержание слайда:
№42 слайд
Содержание слайда:
№43 слайд
Содержание слайда:
№44 слайд
Содержание слайда:
№45 слайд
Содержание слайда: Методы оптимизации
Функция спроса D(p) определяет спрос (количество купленного товара) при цене p за единицу продукции.
Функция предложения S(p) задает количество товара, которое поставщик может предложить по рыночной цене p.
№46 слайд
Содержание слайда: Методы оптимизации
Говорят, что рынок находится в равновесии, если покупатели могут купить столько товара, сколько им необходимо, а продавец может реализовать весь товар, который он намерен продать.
Равновесная цена р0 товара на рынке находится из условия S(р0) = D(р0), а количество q0 проданного товара q0 = D(р0).
№47 слайд
Содержание слайда: Предположим, что на продукцию компании вводится (дополнительный) фиксированный налог t на каждую единицу реализованного товара.
Предположим, что на продукцию компании вводится (дополнительный) фиксированный налог t на каждую единицу реализованного товара.
Если ставка налога достаточно велика, то производство товара будет невыгодно, и это приведет его к остановке.
Возникает вопрос о такой ставке налога, чтобы итоговый сбор был максимальным.
№48 слайд
Содержание слайда: Пусть доход от продажи (выручка):
Пусть доход от продажи (выручка):
а затраты на выпуск продукта в зависимости от количества q:
Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор.
Как уменьшится количество выпускаемой продукции?
№49 слайд
Содержание слайда:
№50 слайд
Содержание слайда:
№51 слайд
Содержание слайда:
№52 слайд
Содержание слайда:
№53 слайд
Содержание слайда:
№54 слайд
Содержание слайда: Пусть доход от продажи (выручка):
Пусть доход от продажи (выручка):
а затраты на выпуск продукта в зависимости от количества q:
Найти величину налога t на каждую единицу продукта, чтобы налог T=tq от всей реализуемой продукции был максимальным, и весь налоговый сбор.
Как уменьшится количество выпускаемой продукции?
№55 слайд
Содержание слайда:
№56 слайд
Содержание слайда:
№57 слайд
Содержание слайда:
№58 слайд
Содержание слайда:
№59 слайд
Содержание слайда:
№60 слайд
Содержание слайда: Для товаров X1 и X2 известны функции спроса:
Для товаров X1 и X2 известны функции спроса:
Фирма-монополист имеет функцию издержек:
Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план.
№61 слайд
Содержание слайда:
№62 слайд
Содержание слайда:
№63 слайд
Содержание слайда:
№64 слайд
Содержание слайда: Для товаров X1 и X2 известны функции спроса:
Для товаров X1 и X2 известны функции спроса:
Фирма-монополист имеет функцию издержек:
Вычислите максимальную прибыль фирмы в этих условиях и найдите соответствующий производственный план.
№65 слайд
Содержание слайда:
№66 слайд
Содержание слайда:
№67 слайд
Содержание слайда:
№68 слайд
Содержание слайда:
№69 слайд
Содержание слайда: Задачи многокритериальной оптимизации
Задача вида:
где i > 1, - допустимое множество;
fi(x) – гладкие функции на D, называется задачей многокритериальной оптимизации.
Область допустимых решений D задается системой уравнений и неравенств.
№70 слайд
Содержание слайда: Пусть X и Y – два допустимых решения. Говорят, что X доминирует Y, если для всех
Пусть 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 на две полуплоскости.
Каждая из этих линий разбивает плоскость XOY на две полуплоскости.
Пусть Пi – полуплоскости, содержащие вектор градиента целевой функции fi, а их пересечение
3. Перемещая данную область П по границе допустимого множества D, находим те точки границы, которые являются единственными точками пересечения областей П и D.
Данные точки - оптимальные по Парето, а множество всех таких точек – Парето-эффективная граница.
№74 слайд
Содержание слайда: Найти Парето-эффективную границу задачи:
Найти Парето-эффективную границу задачи:
№75 слайд
Содержание слайда:
№76 слайд
Содержание слайда:
№77 слайд
Содержание слайда:
№78 слайд
Содержание слайда:
№79 слайд
Содержание слайда: Найти Парето-эффективную границу задачи:
Найти Парето-эффективную границу задачи:
№80 слайд
Содержание слайда:
№81 слайд
Содержание слайда:
№82 слайд
Содержание слайда:
№83 слайд
Содержание слайда:
№84 слайд
Содержание слайда: Метод идеальной точки
Метод идеальной точки является геометрическим методом для многокритериальных задач.
№85 слайд
Содержание слайда: Решить задачу многокритериальной оптимизации методом идеальной точки:
Решить задачу многокритериальной оптимизации методом идеальной точки:
№86 слайд
Содержание слайда:
№87 слайд
Содержание слайда:
№88 слайд
Содержание слайда:
№89 слайд
Содержание слайда:
№90 слайд
Содержание слайда:
№91 слайд
Содержание слайда:
№92 слайд
Содержание слайда:
№93 слайд
Содержание слайда: Решить задачу многокритериальной оптимизации методом идеальной точки:
Решить задачу многокритериальной оптимизации методом идеальной точки:
№94 слайд
Содержание слайда:
№95 слайд
Содержание слайда:
№96 слайд
Содержание слайда:
№97 слайд
Содержание слайда:
№98 слайд
Содержание слайда:
№99 слайд
Содержание слайда:
№100 слайд
Содержание слайда:
№101 слайд
Содержание слайда: Спасибо за внимание!
Скачать все slide презентации Динамическое программирование. (Семинар 3) одним архивом:
