Модели динамического программирования. Системный анализ и ИСО

1. Дисциплина «Системный анализ и ИСО» Рекомендации по выполнению лабораторной работы №5 Тема «МОДЕЛИ ДИНАМИЧЕСКОГО

ПРОГРАММИРОВАНИЯ »
Вопросы:
особенности задач динамического программирования (ДП),
общая постановка задачи ДП, принципы ДП,
основное функциональное уравнение ДП,
вычислительная процедура метода ДП .

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

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

3.

4
4
2
1
5
6
7
5
8
3
6
3
2
4
5
2
8
7
8
6
3
2
7
6
9
Рисунок – Транспортная сеть
10

4.

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

5.

Подготовительный этап
Таблица – Группировка пунктов сети
К I группе отнесём пункт 1, ко II группе - пункты, в которые
можно попасть непосредственно из пунктов I группы, к III группе пункты, в которые можно попасть непосредственно из пунктов II
группы и так далее.
Формирование наиболее экономного маршрута может быть
реализовано за четыре шага:
на первом шаге транспорт перемещается из пункта 1 в какой-то пункт
группы II,
на втором шаге – из пункта группы II в пункт группы III и так далее.
Если затраты минимальны при перевозке единицы груза, то они
будут минимальны и при перевозке любого количества груза.

6.

Этап условной оптимизации
от четвёртого шага к первому
i=4
Таблица 1 – Результаты вычислений для четвёртого шага

7.

i=3
Таблица 2 – Результаты вычислений для третьего шага

8.

i=1
Таблица 4 – Результаты вычислений для первого шага

9.

Этап безусловной оптимизации
От первого шага к четвёртому. Последовательно анализируем
таблицы 4,3,2,1.
Таблица 1. Из пункта 1 (состояние C1) транспорт с грузом следует
направить по маршруту (1, 3), так как управлению (1, 3)
соответствуют минимальные затраты F1, в пункт 3 (состояние C3).
Таблица 2. Из пункта 3 – по маршруту (3, 5) в пункт 5.
Таблица 3. Из пункта 5 – по маршруту (5, 7) в пункт 7.
Таблица 4. Из пункта 7 – по маршруту (7, 10) в пункт 10.
(На сети маршрут показать жирной линией)
Вывод. Оптимальную схему доставки груза из пункта
отправления 1 в пункт назначения 10 обеспечивает наиболее
экономный маршрут, который пролегает через пункты 1, 3, 5, 7, 10.
При этом транспортные расходы минимизируются и составят 13
денежных единиц на единицу груза.