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

176 чел.

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

 


 

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

86045. Анализ и оценка управления оборотными активами предприятия на примере ГУП «Кореневский экспериментальный завод» 166.85 KB
  Управление оборотными активами занимает особое место в системе предприятия. Теоретические и практические разработки системы управления оборотными активами относятся в основном к предприятиям, работающих в относительно стабильной и предсказуемой экономической среде, в то время как проблемы управления...
86046. Бухгалтерский учет финансовых результатов на примере ООО «БУЛГАРНЕФТЕПРОДУКТ» 639.2 KB
  При этом в современных условиях хозяйствования в число важнейших объектов учетного наблюдения выдвигается собственный капитал образующийся в результате получения организацией прибыли. Рост прибыли создает финансовую основу для самофинансирования деятельности предприятия осуществление расширенного воспроизводства...
86047. Розробка елементів інформаційної системи формування місцевих бюджетів (на прикладі м. Краснодон) 4.03 MB
  Метою даної дипломної роботи є пошук заходів, спрямованих на рішення проблем формування місцевих бюджетів України і сприятливих більш ефективному здійсненню бюджетного процесу і формуванню фінансової незалежності органа місцевого самоврядування.
86048. Разработка автоматизированной подсистемы планирования на примере ОП ш. им. М.П.Баракова 913 KB
  Совершенствование форм и методов управления происходит на основе достижений научно-технического прогресса, дальнейшего развития информатики, занимающейся изучением законов, методов и способов накопления, обработки и передачи информации с помощью электронных вычислительных машин и других технических средств.
86049. Рекламная деятельность ЧП «Эверест» 499.5 KB
  Поэтому очень важно выбрать наиболее подходящие виды рекламы формы ее подачи и способы доведения ее к потребителю другие маркетинговые мероприятия. Мы уже касались этого вопроса если говорили о классификации рекламы. Этих наиболее распространенный и пока что наиболее доступный из средств рекламы в Украине преимущества которой определяются несколькими факторами: газеты и журналы читает значительное количество людей; газета дает возможность быстро донести рекламу к потенциальному покупателю; не только сама реклама а и изменения текста...
86050. Изготовлении детали «Вал червячный» 2.92 MB
  Также разработано нестандартное контрольное приспособление для измерения биений базовых поверхностей детали. Также в дипломном проекте рассмотрены вопросы касающиеся обеспечения безопасности жизнедеятельности и охраны труда при изготовлении детали.
86051. Исследование деятельности государственного финансового органа по контролю за финансовыми операциями проходящими через банковские и иные кредитные учреждения 865 KB
  Обмен денег на купюры иного достоинства пли другую валюту. Перевод наличных денег в денежные инструменты. Множественный перевод денег на счета других фирм. Банковская система страны наиболее уязвима к использованию ее для целей отмывания денег.
86052. Правовое регулирование подготовки дела к судебному разбирательству 377 KB
  Изменения затронули и стадию подготовки дела к судебному разбирательству. Причинами произведенных нововведений в правовой регламентации рассматриваемой стадии служат положения общей концепции судебной реформы, опыт зарубежных стран, демонстрировавший возможность завершения гражданского дела без вынесения...