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

189 чел.

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

 


 

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

5701. Бухгалтерський облік. Загальна теорія 348.5 KB
  Тема 1. Господарський облік, його суть і характеристика Мета лекції – сформувати систему знань про поняття та суть бухгалтерського обліку. План 1.1. Поняття та суть бухгалтерського обліку. Користувачі бухгалтерської інформації. Бухгалтерський о...
5702. Философия. Лекционный курс. Предварительное определение предмета философии 431.84 KB
  Введение в предмет философского знания 1.Предварительное определение предмета философии Философия –переводится с греческого на русский как любовь к мудрости. По преданию этот термин возник благодаря Пифагору...
5703. Методологічні засади статистики 134.5 KB
  Методологічні засади статистики План Загальне уявлення про статистику та короткі відомості із її історії Предмет статистики Основні категорії статистики Організація і завдання статистики Загальне уявлення про статистику та ко...
5704. Поняття, предмет, метод, система і функції конституційного права 103.5 KB
  Поняття, предмет, метод, система і функції конституційного права Для нормального життя люди постійно повинні їсти, пити, мати одяг, взуття, задовольняти свої духовні потреби. Тільки на цій основі вони можуть брати участь у виробництві. При цьому слі...
5705. Поняття професійної етики та її категорії 56.5 KB
  Поняття професійної етики та її категорії План Поняття про етику як науку. Основні категорії етики. Мораль як суспільне явище. Поняття про етикет та професійну етику. Етичний бізнес - це чесність, порядність, повага до п...
5706. Редагування текстів в MS Word 40.5 KB
  Редагування текстів Автозаміна Автозаміна - це автоматичне виправлення помилок і неправильних слів. Крім того, автозаміна дає змогу за допомогою кількох символів вставити великий текстовий фрагмент. Для настроювання механізму автозаміни потрібн...
5707. Інтернет як джерело банківської, фінансової і підприємницької інформації 131 KB
  Інтернет як джерело банківської, фінансової і підприємницької інформації Банківська і підприємницька інформація як підсистеми економічної інформації 1. Загальна характеристика дисципліни, її місце в системі підготовки бакалаврів зі спеціал...
5708. Педагогіка вищої школи як наука 74 KB
  Педагогіка вищої школи як наука План Предмет, категорії та основні завдання педагогіки вищої школи. Місце педагогіки вищої школи в системі педагогічних наук та її зв’язок з іншими науками. Сучасні методологічні аспекти педагог...
5709. Программирование на языках среднего уровня С/С++ 689 KB
  Предисловие Настоящий конспект лекций посвящен программированию на языках среднего уровня С/С++, в нем рассмотрен объектно-ориентированный подход программирования. Условно конспект лекций можно разделить на две части: первая часть посвящена основным...