Динамическое программирование. Задача о нахождении минимальных затрат при строительстве транспортных артерий. - презентация

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

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

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

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

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

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

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

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

9 рассматриваем 4х этапный процесс методом прямой прогонки. СРЕДСТВА ПРЕДПРИЯТИЯ

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

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

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

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

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