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

128 чел.

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

 


 

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

1694. Особенности молекулярной биологии и генетики 300.92 KB
  Уровни организации жизни. Фундаментальные свойства живой материи. Самовоспроизведение (репродукция). Наследственность и изменчивость. Индивидуальное развитие организмов. Центральная догма молекулярной биологии. Универсальные способы передачи биологической информации.
1695. Теория стандартизации 1.29 MB
  Ответственность за несоответствие продукции требованиям технических регламентов. Информационное обеспечение технического регулирования. Методические основы стандартизации. Системы стандартизации Российской Федерации. Применение документов по стандартизации.
1696. Построение экспертных систем на основе байесовских сетей доверия Исследование характеристик СПДС 153.12 KB
  При выполнении лабораторной работы была обучена байесовская сеть. Были получены значения состояний узлов близкие к исходным. Так же хороший результат был получен при обучении сети на основе выборки с 25% пропусков.
1697. Правове регулювання транспортних послуг в туризмі та міжнародних подорожах 32.37 KB
  Правове регулювання послуг морського транспорту у сфері туризму і міжнародних подорожей. Правові форми реалізації послуг залізничного транспорту у сфері туризму і міжнародних подорожей.
1698. Автоматизація технологічних процесів 34.69 KB
  Автоматизація виробництва – це процес в розвитку машинного виробництва, при якому функції керування та контролю, раніше виконувані людиною, перекладаються на прилади і автоматичне обладнання.
1699. Свободное падение тел. Движение тела, брошенного вертикально вверх. 37.5 KB
  Свободным падением называется такое движение тела, когда на него действует только сила тяжести.
1700. Применение мер пресечения 49.25 KB
  Меры пресечения как меры уголовно-процессуального принуждения. Основания и порядок применения мер пресечения. Виды мер пресечения в уголовном процессе
1701. Социально-педагогическая адаптация личности 50.08 KB
  Сущность понятия психологическая аккультурация. Значение межкультурных контактов для адаптации. Рассмотреть U – образная кривая адаптации В. Оберга и W - кривая адаптации. Факторы, влияющие на процесс адаптации к новой культурной среде. Программы преодоления культурно шока.
1702. Сучасні проблеми і тенденції соціально-економічного розвитку України 25.17 KB
  Стан справ в економіці України залишається вкрай складним. Українська економіка змушена долати наслідки планово-розподільної системи господарювання.