'

Динамическое программирование

Понравилась презентация – покажи это...





Слайд 0

Динамическое программирование


Слайд 1

Задача о нахождении минимальных затрат при строительстве транспортных артерий.


Слайд 2

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


Слайд 3

Пример 1 Решение методом обратной прогонки (графическое):


Слайд 4

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


Слайд 5

Метод прямой прогонки Оптимальное распределение ресурсов


Слайд 6

Пусть имеется некоторое количество ресурса в объеме (х) которое необходимо распределить между n различными объектами так чтобы получить суммарную эффективность, которая зависит от выбранного способа распределения.


Слайд 7

Пример 2 Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на 4х предприятиях принадлежащих фирме. Для расширения производства выделяются средства в объеме 100у.е. с дискретностью 20у.е. Прирост выпуска продукции зависит от выделенной суммы и представлены в таблице. Найти оптимальное распределение средств обеспечивающее максимальный прирост выпуска.


Слайд 8

рассматриваем 4х этапный процесс методом прямой прогонки.


Слайд 9

Все средства вкладываем в 1е предприятие.


Слайд 10

Все средства вкладываем в 1е два предприятия.


Слайд 11

Все средства вкладываем в 1е три предприятия


Слайд 12

Все средства вкладываем в 4е предприятие.


Слайд 13

Выписываем распределение двигаясь в обратном направлении. 4-40у.е. 3-20у.е. 2-40у.е. 1-0у.е.


×

HTML:





Ссылка: