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

112 чел.

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

 


 

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

42538. Побудова системи масового обслуговування з втратами та без очікування 23 KB
  Кількість обслуговуючих пристроїв – Кг де Кг – кількість голосних букв в Вашому прізвищі. Процедура розподілу потоків поміж обслуговуючими пристроями: Якщо Кп – парне, то – рівномірно на всі пристрої, якщо Кп – непарне, то спочатку спроба на перший пристрій, при занятості на другий і т.д.
42539. Понятие социального действия. Социальное взаимодействие 15.4 KB
  Социальное действие - действие человека (независимо от того, носит ли оно внешний или внутренний характер, сводится к невмешательству или к терпеливому принятию), которое по предполагаемому действующим лицом или действующими лицами смыслу соотносится с действием других людей или ориентируется на него
42540. Концепция общества. Общество как система 15.77 KB
  Социальная система - структурный элемент социальной реальности, определенное целостное образование, основными элементами которого являются люди, их связи и взаимодействия.
42541. Принципы типологии общества. Типы общества 16.21 KB
  Традиционное общество — это общество с аграрным укладом, малоподвижными структурами и способом социокультурной регуляции, основанном на традициях (традиционное общество). Поведение индивидов в нем строго контролируется, регламентируется обычаями и нормами традиционного поведения, устоявшимися социальными институтами
42542. Первині засоби пожежегасіння та дослідження якості вогнегасних речовин 37 KB
  В комплексі заходів спрямованих на ліквідацію пожежі що використовуються в системі протипожежного захисту важливе значення має вибір найбільш раціональних способів та засобів припинення горіння згідно зі СниП 2. Існують такі основні способи припинення горіння : Охолодження зони горіння або речовини що горять нижче певних температур. Ізоляція вогнища горіння від повітря. Хімічне гальмування інгібування швидкості реакцій окислення горіння у полум’ї.
42543. Імітаційна модель CALL-центру 29 KB
  Вихідні дані Кп – кількість букв у Вашому прізвищі 5. Кг – кількість голосних букв в Вашому прізвищі 2. Кприг кількість приголосних букв в Вашому прізвищі 3. Кількість операторів = Кп = 5 Обробка викликів надання відповіді користувачеві розподіляється за законом Паретто.
42544. КОНТРОЛЬ ПАРТИИ ИЗДЕЛИЙ, ВЫБОР ОРГАНИЗАЦИОННОЙ СТРУКТУРЫ 893.5 KB
  Бригады получают конкретное задание детально знакомятся с постановкой задачи разбивают ее на простейшие выясняют тип распределения контролируемого параметра и определяют его числовые вероятностные характеристики.
42545. Разработать Windows Forms приложение - программу-калькулятор дробей 44 KB
  не имеют общих делителей то дробь называется несократимой; любая дробь может быть представлена к несократимой если её числитель сократить на их наибольший общий делитель Hog наибольшее натуральное число на которое они оба делятся без остатка; две любые дроби b и c b считаются равными если d=bc; две несократимые дроби считаются равными если равны их числители и знаменатели =c и b=d. Умножение: W W'={U U'V V'} W=U d1V d2 и W'=U' d2V' d1 где d1=HogUV' и d2=HogU' V. Деление: W W'={U U' V...
42546. Утилиты ТСР/IP. Методические указания к лабораторной работе 139 KB
  Получение списка серверов имен для домена yndex. C: nslookup type=ns yndex.35 Nonuthorittive nswer: yndex.ru yndex.