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

133 чел.

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

 


 

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

73392. Звуки Р, Р’, буквы Рр. Чтение слов и предложений с буквой р. Работа с детской книгой. Украинская народная сказка «Рукавичка» 633.94 KB
  Цель: учить правильно артикулировать звуки Р, Р’, читать слоги, слова и предложения с буквой Рр; формировать навыки правильного слогового, выразительного и сознательного чтения; совершенствовать навыки звукового, звуко-буквенного анализа слов.
73393. Оформлювальна графіка. Створення логотипу 855.57 KB
  Мета. Узагальнити та розширити знання учнів про поняття графіка ознайомити з походженням та значенням поняття логотип. Практичне завдання Виготовлення логотипу. У майстерні графіків з’являються на світ ілюстрації плакати листівки етикеткипоштові марки емблеми обгортк...
73395. Инновационная деятельность предприятия ФГУП «Гос. НИИ ОЧБ» ФМБА России 508.5 KB
  Основная цель инновационного проекта - обоснование экономической целесообразности объема и сроков проведения вложений, включая необходимую документацию, разрабатываемую в соответствии с принятыми стандартами (нормами и правилами), а также описание практических действий по осуществлению инвестиций (бизнес - план).
73396. ДОСЛІДЖЕННЯ АСОРТИМЕНТУ ДЕКОРАТИВНИХ РОСЛИН В ОЗЕЛЕНЕННІ М. ХАРКОВА 456 KB
  Вивчити елементи озеленення м. Харкова, створені з використанням клумбових декоративних рослин. Вивчити наявний асортимент клумбових рослин, та можливості його поповнення за рахунок рослин, які добре пристосовані до екологічних умов нашої території і доречні для вирощування в рокаріях...
73397. Differences in the articulation basis of English, Russian and Kazakh 157.01 KB
  Human speech is the result of highly complicated series of events. The formation of the concept takes place at the linguistic level that is in the brain of the speaker: this stage may be called psychological. The message formed within the brain is transmitted along the nervous system to the speech organs.
73398. Дослідження гетеро структури GaAs, AlGaAs, їх фізико-хімічні та оптичні параметри 800.6 KB
  Концентрація домішок у шарі може бути вище, ніж у підкладці, що забезпечує можливість одержання багатоомних шарів на низькоомних підкладках. Для проведення епітаксіального нарощування необхідно створити умови для конденсації атомів речовини, що осаджується, на поверхні підкладки.
73399. Організація радіаційного контролю виробничого персоналу на хлібопекарського виробництва у надзвичайних ситуаціях 96 KB
  Основними джерелами опромінення населення України як і в інших країнах світу є техногеннопідсилені діяльністю людини природні джерела. Середньорічна ефективна доза опромінення населення цими джерелами в Україні становить понад 6 мЗв.
73400. Информационно-коммуникативные технологии как средство расширения потенциального словаря учащихся на старшем этапе обучения в школе 118.41 KB
  Информационно-коммуникативные технологии как средство расширения потенциального словаря учащихся на уроках английского языка на старшем этапе обучения в школе. Повышение эффективности обучения школьников является одной из важнейших задач в методике преподавания...