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

117 чел.

Лабораторная работа 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.

 


 

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

18861. Европейский классицизм 20.97 KB
  Европейский классицизм. Настало время и высокий мистицизм готики пройдя через испытания ренессанса уступает место новым идеям основанным на традициях древних демократий. Стремление к имперскому величию и демократическим идеалам трансформировалась в ретроспекцию п
18862. Уильям Моррис и «Движение искусств и ремёсел» 26.64 KB
  Уильям Моррис и Движение искусств и ремёсел. Движение искусств и ремёсел Arts Crafts английское художественное движение викторианской эпохи кон. 19 в. участники которого занимались ручной выработкой предметов декоративноприкладного искусства стремясь к сближению
18863. Микеланджело Буонарроти (Michelangelo Buonarroti; иначе Микеланьоло ди Лодовико ди Лионардо ди Буонаррото Симони) 24.74 KB
  Микеланджело Буонарроти Michelangelo Buonarroti; иначе Микеланьоло ди Лодовико ди Лионардо ди Буонаррото Симони 1475-1564 итальянский скульптор живописец архитектор и поэт. В искусстве Микеланджело с огромной выразительной силой воплотились как глубоко человечные полные героиче
18864. Русское барокко. Окно в Европу 29.03 KB
  Русское барокко. Окно в Европу. Барокко стиль зародившийся в конце XVI в. в Италии в Европе был распространен до начала XVIII в. в Латинской Америке отчасти в Северной Америки и Азии в XVII XVIII вв. Основополагающая черта синтетичность. Искусство барокко отличается динами
18865. Немецкое Возрождение. А.Дюрер, Г.Гольбейн 24.43 KB
  Немецкое Возрождение. А.Дюрер Г.Гольбейн. Развитие немецких городов запаздывало даже по отношению к Нидерландам и немецкий Ренессанс сформировался в сравнении с итальянским на целое столетие позже. На примере творчества многих художников XV в. можно проследить как фор
18866. Скандинавская традиция Алвар Аалто 22.6 KB
  Скандинавская традиция Алвар Аалто. Годы жизни: 1898-1976 Основная информация: Выдающийся финский архитектор. Представитель функционализма близкого органической архитектуре. Его постройки общественные промышленные сооружения жилые дома церкви и выставочные павиль
18867. Русская архитектура Х-ХVII 23.49 KB
  Русская архитектура ХХVII. Крестовокупольный храм архитектурный тип христианского храма сформировавшийся в Византии и в странах христианского востока в V VIII вв. Стал господствующим в архитектуре Византии с IX века и был принят христианскими странами православно...
18868. Стиль барокко в живописи и скульптуре. Дж. Лоренцо Бернини, Питер Пауль Рубенс 30.3 KB
  Стиль барокко в живописи и скульптуре. Дж. Лоренцо Бернини Питер Пауль Рубенс. Лоренцо Бернини итальянский архитектор и скульптор. Его скульптурам присущи текучая стремительность движения сочетание религиозной аффектации с экзальтированной чувственностью €œЭк...
18869. Ле Корбюзье Шарль Эдуар (6.10.1887— 27.8. 1965) 20.12 KB
  Ле Корбюзье Шарль Эдуар 6.10.1887 27.8. 1965 Французский архитектор и теоретик архитектуры создатель архитектуры интернационального стиля а так же живописец в живописи разработал теорию пуризма и писатель публицист. Учился и работал у архитекторов: Йозефа Хофмана Огюс...