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

181 чел.

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

 


 

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

29003. Логический уровень базовой ИТ: назначение, структура и состав 40 KB
  Описание в виде моделей: Модель предметной области общая модель управления модель решаемых задач модель организации информационных процессов кот. разделяется на модель обработки модель обмена модель накопления и модель представлении знаний. Модель обработки включает: формализацию описание процедур: организации вычислительных процессов преобразование данных отражение данных. Модель обмена включает в себя формальное описание процедур выполняемых в компьютерной сети.
29004. Физический уровень базовой ИТ: назначение, структура, состав 33.5 KB
  Каждая подсистема содержит аппаратные и программные компоненты. Аппаратные компоненты ЭВМ различных классов. Программные компоненты производят обработку данных представляет собой алгоритм реализующий преобразование и отображение данных прикладное программное обеспечение. Аппаратные компоненты устройства и узлы для реализации компьютерной сети модемы коммутаторы маршрутизаторы.
29005. ИТ обработки данных: назначение, структура, функционирование 30 KB
  ИТ обработки данных предназначен для решения хорошо структурированных задач задачи кот. Сбор данных. Обработка данных.
29006. ИТ управления: назначение, структура, функционирование 30 KB
  Здесь входные данные преобразуются к формату и виду пригодного для анализа. БД содержит 2 части: данные по операциям накапливаются в процессе функционирования организации. Виды отчётов: суммирующий отчёт данные объединены в отдельные группы и представляют собой вид суммирующих итогов сравнительные отчёты содержат данные из различных источников классифицированные по признакам для сравнения чрезвычайные отчёты формируются по запросу менеджера по его согласию.
29007. Расчёт фундаментов по второй группе предельных состояний. Определение границ условного фундамента при расчёте осадок свайных фундаментов 34 KB
  Определение границ условного фундамента при расчёте осадок свайных фундаментов. Расчёт оснований свайных фундаментов по второй группе предельных состояний по деформациям производится исходя из условия: s≤su 1 где s конечная стабилизированная осадка свайного фундамента определённая расчётом; su предельное значение осадки устанавливаемое соответствующими нормативными документами или требованиями проекта. В настоящее время в большинстве случаев свайный фундамент при расчёте его осадки s рассматривается как условный массивный...
29008. Определение осадки свайного фундамента методом послойного суммирования. Порядок расчёта 31.5 KB
  Определение осадки свайного фундамента методом послойного суммирования.1 а нагрузка передаваемая на грунт основания принимается равномерно распределённой интенсивностью: 1 где N0II расчётная нагрузка от веса здания или сооружения на уровне верхнего обреза фундамента; NcII NpII NгII вес соответственно свай ростверка и грунта в объёме уловного фундамента авсd; Ау=by·ly площадь подошвы условно гофундамента. Найденное значение pII не должнопревышать расчётное сопротивление грунта основания R на уровне нижних концов свай...
29009. Опускные колодцы. Условия применения, конструктивная схема и последовательность устройства. Классификация опускных колодцев по материалу, по форме в плане и по способу устройства стен 41.5 KB
  Опускные колодцы. Опускные колодцы могут быть выполнены из дерева каменной или кирпичной кладки бетона железобетона металла. Наибольшее распространение в современной практике строительства получили железобетонные колодцы. По форме в плане опускные колодцы могут быть круглыми квадратными прямоугольной или смешанной формы с внутренними перегородками и без них рис.
29010. Кессоны. Условия применения, конструктивная схема, последовательность производства работ 35 KB
  При залегании прочных грунтов на значительной глубине когда устройство фундаментов в открытых котлованах становится трудновыполнимым и экономически невыгодным а применение свай не обеспечивает необходимой несущей способности прибегают к устройству фундаментов глубокого заложения. Необходимость устройства фундаментов глубокого заложения может быть вызвана и особенностями самого сооружения например когда оно должно быть опущено на большую глубину заглубленные и подземные сооружения. Одним из видов фундаментов глубокого заложения наряду с...
29011. Возведение заглубленных и подземных сооружений методом "стена в грунте". Технология устройства. Монолитный и сборный варианты 66.5 KB
  Возведение заглубленных и подземных сооружений методом стена в грунте . Способ стена в грунте предназначен для устройства фундаментов и заглубленных в грунт сооружений различного назначения. Способ заключается в том что сначала по контуру будущего сооружения в грунте отрывается узкая глубокая траншея которая затем заполняется бетонной смесью или сборными железобетонными элементами. Способ стена в грунте используется при возведении фундаментов под тяжёлые здания и.