АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Глава 2. Динамическое программирование

Читайте также:
  1. I. ГЛАВА ПАРНЫХ СТРОФ
  2. II. Глава о духовной практике
  3. III. Глава о необычных способностях.
  4. IV. Глава об Освобождении.
  5. IV. Глава подразделения по стране
  6. XI. ГЛАВА О СТАРОСТИ
  7. XIV. ГЛАВА О ПРОСВЕТЛЕННОМ
  8. XVIII. ГЛАВА О СКВЕРНЕ
  9. XXIV. ГЛАВА О ЖЕЛАНИИ
  10. XXV. ГЛАВА О БХИКШУ
  11. XXVI. ГЛАВА О БРАХМАНАХ
  12. Аб Глава II ,

Специфика метода динамического программирования заключается в том, что для отыскания оптимального решения задачи последняя разбивается на ряд последовательных шагов или этапов. Соответственно и сам процесс планирования становится многошаговым. Термин «динамическое программирование» относится скорее к вычислительному методу, чем к особому типу задач. Многие задачи статического характера оказывается возможным сформулировать и решать как задачи динамического программирования. В то же время некоторые динамические задачи успешно решаются методами линейного и нелинейного программирования.

Покажем принцип метода динамического программирования на модели эффективного использования ресурсов.

Имеется некоторое количество ресурса , которое можно использовать различными способами. Пусть – количество ресурса, используемое -м способом, – доход от использования ресурса -м способом (). Требуется распределить общее количество ресурса между различными способами, чтобы суммарный доход был максимальным. Математически задача выразится следующим образом.

Найти

(10.1)

при условиях:

(10.2 )

Вместо одной задачи с данным количеством ресурса и фиксированным числом способов рассматриваем целое семейство таких задач, в которых принимает любые положительные значения и – любые целые. Развертываем процесс во времени, производим распределение ресурсов в каждую единицу времени.

 

Зададим последовательность функций , определенных для следующим образом:

(10.3 )

где

Очевидно,

Существует рекуррентное соотношение

(10.4 )

для

Вывод этого соотношения основан на принципе оптимальности Беллмана.

Очевидно,

Соотношения (10.4) позволяют заменить вычисление максимума по N переменным в исходной задаче решением N задач, в каждой из которых максимум находится лишь по одной переменной.

Примечания.

1. Наряду с решением исходной задачи получают решения целого семейства сходных между собой задач.

2. Та же идея построения рекуррентных соотношений может быть использована в случае нескольких видов ресурсов, но с увеличением размерности быстро растет объем вычислений.

Схема решения задачи [10.1] –[10.2]

1. Находят функции и .

2. Строят рекуррентное соотношение.

3. Находят функции и .

4. Выбирают значения – максимальное значение целевой функции - значение переменной в решении.

5. Остальные переменные получают следующие значения:

Пример

при условиях:

 

Решение. Для построения рекуррентного соотношения обозначим , . Построим последовательность функций

Легко видеть, что при , а при .

Запишем значения функций и при дискретных целых значениях из заданного интервала

Построим рекуррентное соотношение, связывающее функции и :

Поскольку записать данную функцию в явном виде сложно, вычислим ее значения при дискретных значениях х:

Здесь минимальное значение выбрано из двух выражений – при и и достигается при =1.





Находим

Следовательно, решение данной задачи следующее .

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)