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

139 чел.

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

 


 

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

81777. Символизм как литературное направление. Анализ стихотворения одного из поэтов-символистов 47.33 KB
  Бальмонта Ю. В поэтических формулах Бальмонта Сологуба Гиппиус Мережковского отрицается истинность реального мира объявляемого лишь комплексом ощущений творцахудожника: . Бальмонта М. В 90х годах вышли сборники его стихотворений: Под северным небом 1894 В безбрежности 1895 Тишина 1897; в 900е годы в период творческого взлета Бальмонта Горящие здания 1900 Будем как солнце 1903 Только любовь 1903.
81778. Образ метели в произведениях отечественной литературы 32.93 KB
  Все ее действие развертывается на фоне разгулявшихся природных стихий: Ветер ветер На всем божьем свете Ветер хлесткий гуляет свищет и зол и рад Разыгралась чтойто вьюга ох пурга какая спасе Вьюга долгим смехом Заливается в снегах Очевидно что образы ветра метели романтичны и имеют символический смысл. Ветер ветер На ногах не стоит человек. Ветер ветер На всем Божьем свете. Во второй строфе напор стихии как бы смягчается ее действия становятся не гневны а почти нежны и появляются уменьшительноласкательные...
81779. Наука и философия. Статус научной философии 28.69 KB
  Многолетний спор философии и науки о том в чем больше нуждается общество в философии или науке и какова их действительная взаимосвязь породил множество точек зрения обилие возможных трактовок и интерпретаций этой проблемы. Остановимся на основных тезисах раскрывающих суть соотношения философии и науки: Специальные науки служат отдельным конкретным потребностям общества: технике экономике искусству врачевания искусству обучения законодательству и др. Частные науки ограничиваются отдельными частями мира. Философия задумывается о...
81780. Функции науки. Роль науки в современном образовании и формировании личности 28.41 KB
  Роль науки в современном образовании и формировании личности. Проблема связанная с классификацией функций науки до сих пор остается спорной отчасти потому что последняя развивалась возлагая на себя новые и новые функции отчасти в силу того что выступая в роли социокультурного феномена она начинает больше заботиться не об объективной и безличностной закономерности а о коэволюционном вписывании в мир всех достижений научнотехнического прогресса. В качестве особой и приоритетной проблемы выделяют вопрос о социальных функциях науки...
81781. Преднаука и наука. Генезис науки и проблема периодизации её истории 31.74 KB
  Генезис науки и проблема периодизации её истории. Исследуя историю любого материального или духовного явления в том числе и науки следует иметь в виду что это сложный диалектический поступательный процесс появления различий включающий в себя ряд качественно своеобразных этапов фаз и т. Применяя сказанное о периодизации к истории науки следует прежде всего подчеркнуть следующее. Вопрос о периодизации истории науки и ее критериях по сей день является дискуссионным и активно обсуждается в отечественной и зарубежной литературе.
81783. Средневековая наука. Организация науки в средневековых университетах 33.78 KB
  Первый из них факультет свободных искусств trium был наиболее многочисленным и считался подготовительным для трех других факультетов: медицинского юридического и теологического самого малочисленного но обучение на котором было самым продолжительным. Таким образом Парижский университет оказался в плену противоречивых тенденций: превратиться в центр беспристрастных исследований связанных с изучением античного наследия но всегда стоящих перед опасностью впасть в инакомыслие либо подчинить исследование религиозным целям и тем самым...
81784. Формирование опытной науки в новоевропейской культуре 31.1 KB
  Изменяется роль человека в мире. Происходит постепенная смена мировоззренческой ориентации: для человека значимым становится посюсторонний мир автономным универсальным и самодостаточным становится индивид. Отсюда и характерное для эпохи Возрождения стремление познать принципы функционирования механизмов приборов устройств и самого человека.
81785. Наука в собственном смысле слова: классическая наука, неклассическая и постклассическая 30.52 KB
  Таким образом основные стороны бытия науки это вопервых сложный противоречивый процесс получения нового знания; вовторых результат этого процесса т. объединение полученных знаний в целостную развивающуюся органическую систему а не простое их суммирование; втретьих социальный институт со всей своей инфраструктурой: организация науки научные учреждения и т.; этос нравственность науки профессиональные объединения ученых ресурсы финансы научное оборудование система научной информации различного рода коммуникации ученых и т....