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

164 чел.

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

 


 

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

77731. Технологии флэш-памяти 130.5 KB
  Итак флэш-память. Вообще изобретателем считается Intel представившая в 1988 году флэш-память с архитектурой NOR. Годом позже Toshib разработала архитектуру NND которая и сегодня используется наряду с той же NOR в микросхемах флэш.
77733. Внешние запоминающие устройства (ВЗУ) и их интерфейсы 3.5 MB
  В этих устройствах могут быть реализованы различные физические принципы хранения информации магнитный оптический магнитооптический электронный в любых их сочетаниях. Устройства внешней памяти оперируют блоками информации но никак не байтами или словами как например оперативная память. Процедуры обмена с устройствами внешней памяти привязаны к типу устройства его контроллеру и способу подключения устройства к системе интерфейсу.
77735. Интерфейс НГМД 2.29 MB
  Интерфейс НГМД Интерфейс накопителей на гибких магнитных дисках НГМД является сугубо специфическим по нему передаются не байты команд и данных а сигналы управления приводом и не декодированные сырые битовые потоки данных чтения-записи. Основные функции по управлению НГМД а также по кодированию-декодированию данных выполняет контроллер расположенный на системной плате1. Все функции необходимые для использования НГМД в качестве устройств хранения данных реализованы сервисами BIOS INT 13h и ОС. Контроллер 2 FDC АТ поддерживает два...
77736. Интерфейс ATA 205 KB
  После введения в 2003 году стандарта Seril T Последовательный T традиционный T стали именовать Prllel T имея в виду способ передачи данных по 40 жильному кабелю. Это вдвое увеличивает скорость передачи данных по интерфейсу. Также введена проверка на четность CRC что повышает надёжность передачи информации. 1й регистр с адресом 0 является 16 разрядный и используется для передачи данных между диском и контроллером.
77737. Подключение жестких дисков ATA к компьютеру 112 KB
  Неправильное подключение разъемов кабеля к жесткому диску или системной плате не ведет с необходимостью к повреждению электроники диска или платы жесткий диск просто не распознается и не инициализируется BIOS. Включить компьютер и войти в SetupBIOS программу настройки BIOS бапзовой системы вводавывода нажав комбинацию клавиш высвечиваемую на экране компьютера во время его загрузки обычно клавиша Del. Сконфигурировать или убкдится в правильной конфигурации установленный жесткий диск задав параметры Type Cylinder Heds Sectors и...
77738. Интерфейс Serial ATA 278.5 KB
  Часто среди обоснований перехода на новый стандарт в статьях называют ограниченную скорость передачи параллельного интерфейса в 133 мбайт с но это ограничение конкретной его версии а не его вида вообще а у Seril T не намного и больше 150 Мбайт с. Основные причины ввода Seril T. Их решением стал новый последовательный интерфейс АТА Seril T1 пришедший на смену параллельному интерфейсу физических накопителей.
77739. Диски и контроллеры SAS 1.93 MB
  SS может использовать и большой набор разновидностей RID. Такие гиганты как dptec или LSI Logic в своих продуктах предлагают расширенный набор функций для расширения миграции создания гнёзд и других возможностей в том числе касающихся распределённых массивов RID по нескольким контроллерам и приводам. Но SS это больше нежели интерфейс следующего поколения для профессиональных жёстких дисков хотя он идеально подходит для построения простых и сложных RIDмассивов на базе одного или нескольких RIDконтроллеров. Вместе с мощными...