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

183 чел.

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

 


 

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

48498. КРИМИНОЛОГИЯ 172 KB
  Криминология изучает преступность виды преступности преступления; их причины иные виды их взаимосвязей с различными явлениями и процессами; результативность принимавшихся мер по борьбе с преступностью. Предмет это закономерности: преступности во всех ее проявлениях детерминации и причинности преступности подверженности преступности различным воздействиям. Преступность в различных ее проявлениях включает: преступление или индивидуальное преступное поведение; отдельные виды преступности выделяемые по объекту посягательств...
48499. Курс молодого избирателя 128.5 KB
  И в первую очередь с помощью продвижения идей местного самоуправления в среде старшеклассников. Идея формирование опыта самоуправления деятельности человека. Основное предназначение ученического самоуправления удовлетворять потребности учащихся направленные прежде всего на защиту их гражданских прав и интересов участие в решении реальных проблем школы. Смысл ученического самоуправления заключается не в управлении одних детей другими а в обучении всех детей основам демократических отношений в обществе в обучении их управлять собой...
48500. СТРАТЕГИЧЕСКИЙ МАРКЕТИНГ. КОНСПЕКТ ЛЕКЦИЙ 329 KB
  Стратегический маркетинг представляет собой постоянный и систематический анализ потребностей рынка выводящий на разработку эффективных товаров предназначенных для конкретных групп покупателей и обладающих особыми свойствами отличающими их от товаровконкурентов и таким образом создающими изготовителю устойчивое конкурентное преимущество. Роль стратегического маркетинга прослеживать эволюцию заданного рынка и выявлять различные существующие либо потенциальные рынки или их сегменты на основе анализа потребностей нуждающихся в...
48501. Логика: язык, основные логические законы 657 KB
  Понятия Понятие как форма мышления. Отношения между понятиями. Понятие как форма мышления Обратить внимание на соотношение понятия и слова синонимы омонимы. Неточные молодой человек лысый человек и неясные человек понятия.
48502. КУРС ВИЩОЇ МАТЕМАТИКИ 2.83 MB
  КУРС ВИЩОЇ МАТЕМАТИКИ ЧАСТИНА 2 2005 Диференціальне числення функції однієї змінної. Похідна функції її геометричний і фізичний зміст. Похідної функції fx у точці х = х0 називається границя відносини приросту функції в цій точці до приросту аргументу якщо він існує. Тоді тангенс кута нахилу січної МР до графіка функції.
48503. УЧЕБНАЯ РАДИО- ЭЛЕКТРОМОНТАЖНАЯ ПРАКТИКА 13.68 MB
  В процессе подготовки будущие специалисты должны получить определённую квалификацию, практические навыки. Особенно важно иметь хорошую практическую подготовку для специалиста, который, овладев теоретическими знаниями, должен уметь выполнить ту или иную конкретную работу.
48504. Методика профессионального обучения как наука и учебная дисциплина 416.77 KB
  Методика профессионального обучения как наука и учебная дисциплина. обучения как научной области педагогических знаний. обучения и методической терминологии. обучения с другими науками и перспективы ее развития.
48505. МУНИЦИПАЛЬНОЕ ПРАВО РОССИИ 63.5 KB
  Понятие и признаки местного самоуправления. Аспекты анализа местного самоуправления: основа конституционного строя форма народовластия вид деятельности граждан право человека и гражданина право населения как территориального коллектива. Вопросы местного значения и государственные задачи. Полномочия органов местного самоуправления и государственные полномочия.