42070

Решение задачи динамического программирования

Лабораторная работа

Информатика, кибернетика и программирование

Требуется перевезти груз из пункта 1 в пункт 10 с минимальными затратами на перевозку. Сетевой график дорог Стоимость перевозки груза из пункта s s=129 в пункт j j=2310 представлена в таблице Маршрут Расстояние Маршрут Расстояние 12 4 27 13 11 37 14 3 47 4 25 3 58 9 35 1 68 45 4 78 7 26 4 59 8 36 6 69 5 46 6 79 12 810 5 910 3 Все множество вершин пунктов разбивается на подмножества: . На первом этапе принимается решение через какой пункт принадлежащий второму подмножеству везти груз из пункта 1. На...

Русский

2013-10-27

659.5 KB

110 чел.

Лабораторная работа 4_1. Решение задачи динамического программирования.

Цель работы – изучить методы решения задачи динамического программирования и их реализацию в табличном процессоре MS Excel.

Краткие теоретические сведения

Метод динамического программирования позволяет одну задачу со многими неизвестными заменить последовательно решаемыми задачами с меньшим числом переменных. Процесс решения разбивается на шаги, осуществляемые от конца к началу. Процедура нахождения оптимального управления (решения) основывается на анализе рекуррентного соотношения Беллмана

     (1)

где  - решение, выбранное на l-ом шаге;  - состояние системы на l-ом шаге; Rl – непосредственный эффект, достигаемый на l-ом шаге; fn-l – оптимальное значение эффекта, достигаемое за n-l шагов; n - количество шагов (этапов).

Последовательность шагов:

  1.  Записать уравнение для последнего состояния процесса .
  2.  Найти  из дискретного набора его значений при фиксированных Sn-1 и Un.
  3.  При условии, что , и , после первого шага будет известно решение Un и соответствующее значение функции .
  4.  Уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При  оно имеет вид

 (2)

  1.   Найти условно-оптимальное решение на основе выражения (2)
  2.  Если l=0, расчет закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l0, перейти к выполнению п.4.
  3.  Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.

Пример. Требуется перевезти груз из пункта 1 в пункт 10 с минимальными затратами на перевозку. Сеть дорог изображена на рис.1.

    

Рис.1. Сетевой график дорог

Стоимость перевозки груза из пункта s (s=1,2,…9) в пункт j (j=2,3,…10) представлена в таблице

Маршрут

Расстояние

Маршрут

Расстояние

1-2

4

2-7

-

1-3

11

3-7

-

1-4

3

4-7

4

2-5

3

5-8

9

3-5

1

6-8

-

4-5

4

7-8

7

2-6

4

5-9

8

3-6

6

6-9

5

4-6

6

7-9

12

8-10

5

9-10

3

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

Введем обозначения:

n – номер шага (n=1,2,3,4);

fn(s) – минимальные затраты на перевозку груза от пункта s до конечного пункта, если до него осталось n шагов;

jn(s) – номер пункта, через который нужно ехать из пункта s, чтобы достичь fn(s);

csj – стоимость перевозки груза из пункта s в пункт j.

В приведенной ниже схеме исходные данные сформированы так, что все дуги, входящие в любую из вершин, записаны одним блоком: 2-5; 3-5; 4-5. В несуществующие связи между пунктами приписаны большие расстояния (в данном случае 1000).

Рис.2. Заполнение рабочего листа исходными данными.

Последовательность заполнения ячеек рабочего листа MS Excel соответствующими формулами приведена на следующих двух рисунках.

Рис.2. Вид рабочего листа для значений n=1,2.

Рис.3. Вид рабочего листа для значений n=3,4.

Результаты работы представлены на следующем рисунке. Из них видно, что  минимальное расстояние из пункта 1 в пункт 10 найдено при , а оптимальный маршрут проходит чрез вершины 1-2-6-9-10.


Контрольные упражнения. Варианты.

Найти путь минимальной длины между начальной и конечной вершинами сети  

1.

3.

4.

5.

 


 

А также другие работы, которые могут Вас заинтересовать

5130. Морфология, физиология и патология опорно-двигательного аппарата 104 KB
  Морфология, физиология и патология опорно-двигательного аппарата Цель: сформировать умение оценивать состояние ОДА. Вопросы для самоподготовки:. Строение скелета головы, туловища и конечностей. Общие сведения о мышцах. Их строение. ...
5131. Внутриутробное развитие организма. ВПР. Закономерности роста и развития организма 52.5 KB
  Внутриутробное развитие организма. ВПР. Закономерности роста и развития организма Цель: сформировать умение визуально выделять патологические изменения и различать ВПР. Вопросы для самоподготовки: Организм как единое целое. Понятие о био...
5132. Генетика микроорганизмов. Генотипическая изменчивость 474.5 KB
  Генетика микроорганизмов До 40-х гг. 20 в. считалось, что, поскольку у микроорганизмов нет ядерного аппарата и мейоза, на них не распространяются законы Менделя и хромосомная теория наследственности. С начала 40-х гг. микроорганизмы становятся объек...
5133. Латинский язык и основы терминологии 450 KB
  Тема: Латинский алфавит. Правила чтения. Ударение. Задание 1. Прочтите следующие термины, обратите внимание на произношение букв и буквосочтаний: а) apex верхушка crista гребень tuber бугор sulcus борозда canalis канал tuberculum бугорок fissu...
5134. Общая патология клетки. Повреждение клетки 120 KB
  Общая патология клетки. Повреждение клетки: Нарушение функционирования клетки, которое сохраняется после удаления повреждающего агента Генетически детерминированные или приобретенные изменения метаболизма, физико-химических параметров, к...
5135. Кадровая политика на предприятии 71.5 KB
  Создание конкурентоспособного предприятия всегда связано с людьми, которые работают на предприятии. Организация возможностей фирмы заключена в новых методах управления и зависит от конкретных людей, знаний, компетенции, квалификации, дисциплины, мот...
5136. Формы расчетов, применяемые при осуществлении внешнеэкономической деятельности 24.59 KB
  Формы расчетов, применяемые при осуществлении внешнеэкономической деятельности Внешнеэкономическая деятельность неразрывно связана с необходимостью определения форм расчетов. Под формами расчетов понимаются сложившиеся в международном коммерческом о...
5137. Принципы формирования кадровой политики. Кадровая политика и стратегия управления персоналом 59.5 KB
  Принципы формирования кадровой политики. Кадровая политика и стратегия управления персоналом Кадровая политика – главное направление в работе с кадрами, набор основополагающих принципов, которые реализуются кадровой службой предприятия. В этом ...
5138. Структура механизмов. Классификация кинематических пар 330.69 KB
  Структура механизмов. Классификация кинематических пар Кинематические пары (КП) классифицируются по следующим признакам: 1) по виду места контакта (места связи) поверхностей звеньев: - низшие, в которых контакт звеньев осуществляется по плоскости ил...