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

151 чел.

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

 


 

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

41753. Организация управления ЭВМ 120.47 KB
  Область стека зарезервированная для системных программ устанавливается в БУП а адрес возврата записывается в стек. Наконец инициализируется область стека пользователя записью туда стартового адреса и номера карты памяти содержащей коды программы. Модуль 1 PROCEDURE иницпроцесспольз адресбуп стартовыйадрес приоритет адрес объем карта кодсобытня картапрограммы объемданных бл данных картадаин встатьвочередь очередьвсехпроцессов адресбуп приоритет ■ приоритет[адресбуп] SET системныйфлагпроцесса ТО...
41756. Исследование частотных характеристик разомкнутых линейных САУ и изучение соединений звеньев 461.14 KB
  Для последовательного соединения W1 W2 W3: в одной системе координат построить ЛАЧХ каждого из звеньев и ЛАЧХ всей системы; определить наклоны низкочастотной и высокочастотной асимптот ЛАЧХ; в одной системе координат построить ФЧХ каждого из звеньев и ФЧХ всей системы; 2. Для параллельного соединения W1 W2 W3: построить ЛАЧХ и ФЧХ; определить наклоны низкочастотной и высокочастотной асимптот ЛАЧХ; 3. Для соединения W1 W2 W3 приведенного ниже: произвести эквивалентные преобразования структурной схемы с целью получить систему...
41757. Определение группы соединений обмоток трехфазного трансформатора 160.23 KB
  Трансформатор представляет собой электромагнитный аппарат предназначенный для преобразования посредством электромагнитной индукции переменного тока одного напряжения в переменный ток другого напряжения той же частоты. В двухобмоточном трансформаторе различают обмотку высокого напряжения ВН и обмотку низкого напряжения НН. В однофазных трансформаторах они обозначаются буквами А Х у обмоток высокого напряжения а х  обмоток низкого напряжения. В трехфазных трансформаторах начала и концы фазных обмоток высокого напряжения...
41758. Построение графиков функций. Изучение графических возможностей пакета MS Excel 362.94 KB
  Приобретение навыков построения графика функции на плоскости средствами пакета. Построить график функции см. В ячейку В1 вводится значение функции вычисляемое по формуле =1^213^1 3. Для построения графика функции лучше выбрать точечную диаграмму со значениями соединенными сглаживающими линиями без маркеров.
41759. Работа менеджера с электронной записной книжкой Microsoft OneNote 2010 73.27 KB
  В отличие от бумажных систем текстовых редакторов приложений электронной почты и других офисных программ OneNote позволяет собирать и упорядочивать текстовые заметки рисунки цифровой рукописный текст аудио и видеозаписи и другие материалы в одной цифровой записной книжке на компьютере. OneNote может повысить эффективность работы поскольку вся нужная информация находится под рукой а время которое приходится тратить на поиск сведений в сообщениях электронной почты бумажных записных книжках папках и распечатках сокращается. OneNote...
41760. ОПРЕДЕЛЕНИЕ РЕЖИМА НАПРЯЖЕНИЯ СЕЛЬСКОЙ РАДИАЛЬНОЙ СЕТИ И ВЫБОР НАДБАВОК У ТРАНСФОРМАТОРОВ 65.17 KB
  Замкнутой называют электрическую сеть магистральные линии которой получают питание не менее чем с двух сторон. Расчетная схема линии с двухсторонним питанием Рис. Схема трёхфазной распределительной линии с двухсторонним питанием а и её однофазная модель переменного тока б Рис. Результаты опыта при номинальном режиме работы линии Условия опыта 1.
41761. Исследование протокола FTP (File Transfer Protocol) 272.9 KB
  Получить практические навыки в использовании протокола FTP File Trnsfer Protocol. Провести сеансы работы с FTPсервером в активном и пассивном режимах используя Windows Commnder. Провести сеансы работы с FTPсервером в активном и пассивном режимах с помощью стандартного FTPклиента Windows.