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

125 чел.

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

 


 

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

76812. Двенадцатиперстная кишка 181.15 KB
  Голотопическая проекция кишки приходится на эпигастральную и околопупочную области. Строение стенки Слизистая оболочка с подслизистой основой образует циркулярные складки во всех отделах кишки. Топография кишки Двенадцатиперстная кишка располагается большей своей частью забрюшинно у задней брюшной стенки на уровне ХII грудного III поясничного позвонков проецируется на эпигастральную и околопупочную области.
76813. Брыжеечная часть тонкой кишки (тощая и подвздошная), строение, стенки, кровоснабжение, иннервация 185.11 KB
  Брыжеечная часть называется по наличию у тощей и подвздошной кишки брыжейки которая представляет собой двойной листок брюшины косо прикрепляющийся к задней брюшной стенке по линии слева направо от второго поясничного позвонка к правому...
76814. Толстая кишка 189.72 KB
  Железы кишки выделяют мало ферментов всасывание ограничивается изза отсутствия кишечных ворсинок. Отличительные анатомические признаки: продольные ленты – tenie coli: брыжеечная сальниковая свободная tenie mesocilic tenie omentlis tenie liber сформированные длинными гладкомышечными пучками; гаустры hustre coli поперечные вздутия с поперечными бороздами между ними образованные за счет перераспределения продольных и круговых мышц; сальниковые отростки ppendicis epiploice до 45 см длиной в виде пальцевидных выростов...
76815. Слепая кишка: строение, отношение к брюшине. Топография червеобразного отростка, кровоснабжение, иннервация 184.72 KB
  В ней присутствуют все отличительные признаки толстой кишки: продольные ленты и гаустры сальниковые привески и другие признаки толстой кишки. В просвет кишки с медиальной стороны открывается илеоцекальное отверстие в виде горизонтальной щели ограниченной верхней и нижней полулунными складками слизистой которые по углам сходятся и образуют уздечку. Всё вместе взятое складки уздечка мышца составляют илеоцекальный клапан Баугиниеву заслонку vlv ileoceclis регулирующий порционное продвижение пищевой массы из тонкой кишки в толстую....
76816. Прямая кишка 183.75 KB
  На положение и фиксацию кишки значительное влияние оказывает крестцовокопчиковое искривление нижняя часть которого служит своеобразной опорой. Начало кишки находится на уровне третьего крестцового позвонка и левого подвздошнокрестцового сустава. На положение и размеры кишки особенно влияют сигмовидная кишка и матка мышцы и клетчатка тазового дна и промежности. С прямой кишки брюшина переходит на органы малого таза расположенные перед кишкой образуя у мужчин ректовезикальное углубление – excvtio rectovesiclis а у женщин ...
76817. Печень, ее развитие, строение, топография, кровоснабжение и иннервация, региональные лимфатические узлы 186.78 KB
  Печень – hepr развивается из первичного эпителия энтодермы эмбриональной первичной кишки. Из переднего возникает печень из заднего желчный пузырь. Развивающаяся печень врастает между листками вентральной брыжейки сохраняя связь с кишкой благодаря растущему холедоху.
76818. Желчный пузырь. Выводные протоки желчного пузыря и печени. Кровоснабжение и иннервация желчного пузыр 184.91 KB
  Выводные протоки желчного пузыря и печени. Желчный пузырь – vesic felle biliris seu cholecystis прирастает к висцеральной поверхности правой доли печени в одноименной ямке что лежит в передней половине правой сагиттальной борозды. Дно fundus vesic felle есть слепо расширенный конец выступающий из под нижнего края печени на уровне сращения VIIIIХ реберных хрящей справа. Тело – corpus vesic felle сужается по направлению к воротам печени и плавно сливается с шейкой над которой нередко нависает в виде своеобразного кармана прилежащая...
76819. Поджелудочная железа, развитие, топография, строение, выводные протоки, внутрисекреторная часть, кровоснабжение, иннервация, региональные лимфатические узлы 185.67 KB
  Внутрисекреторная эндокринная часть железы создаёт инсулин глюкагон соматостатин липокаин и другие гормоны для обменных процессов и роста во всем организме. Развитие железы осуществляется из переднего и заднего выростов эпителия первичной кишки в месте образования дуоденум. Аномалия развития добавочные дольки железы. Масса органа 80 г длина 1418 см ширина 9 см толщина 23 см внутрисекреторная часть составляет 12 от массы железы.
76820. Верхний этаж брюшной полости 180.02 KB
  Брюшина верхнего этажа с диафрагмы переходит на выпуклую диафрагмальную поверхность печени образуя серповидную венечную и треугольные связки которые отграничивают внебрюшинное поле печени прирастающее к диафрагме. В последней в направлении справа налево располагается холедох воротная вена собственная артерия печени. Желудок брюшина покрывает интраперитонеально переходя на него с печени по малому сальнику. Париетальная брюшина в верхнем этаже образует три сумки: печеночную для правой и квадратной долей печени преджелудочную для...