Навигация
Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом
26694
знака
6
таблиц
0
изображений
1. Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом.
2. Расчленить операцию на этапы (шаги).
3. Выяснить набор шаговых управлений xi для каждого шага и налагаемые на них ограничения.
4. Определить какой выигрыш приносит на i-ом шаге управление xi, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:
.
5. Определить, как изменяется состояние S системы S под влиянием управление xi на i-ом шаге: оно переходит в новое состояние
. (1.1)
6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш Wi(S) (начиная с i-го шага и до конца) через уже известную функцию Wi+1(S):
. (1.2)
Этому выигрышу соответствует условное оптимальное управление на i-м шаге xi(S) (причем в уже известную функцию Wi+1(S) надо вместо S подставить измененное состояние )
7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле 
8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление xi(S), при котором максимум достигается.
Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния S0. Это и есть оптимальный выигрыш за всю операцию
9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге 
; изменить состояние системы по формуле (1.1); для вновь найденного состояния найти оптимальное управление на втором шаге х2* и т.д. до конца.
Данные этапы рассматривались для аддитивных задач, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Метод динамического программирования применим также и к задачам с так называемым «мультипликативным» критерием, имеющим вид произведения:
(если только выигрыши wi положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (1.2) вместо знака «плюс» ставится знак «умножения»: 
1.2 Примеры задач динамического программирования
Задача планирования рабочей силы:
При выполнении некоторых проектов число рабочих, необходимых для выполнения какого-либо проекта, регулируется путем их найма и увольнения. Поскольку как наем, так и увольнение рабочих связано с дополнительными затратами, необходимо определить, каким образом должна регулироваться численность рабочих в период реализации проекта.
Предположим, что проект будет выполнятся в течение n недель и минимальная потребность в рабочей силе на протяжении i-й недели составит bi рабочих. При идеальных условиях хотелось бы на протяжении i-й недели иметь в точности bi рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей.
Если xi – количество работающих на протяжении i-й недели, то возможны затраты двух видов: 1) С1(xi- bi)-затраты, связанные с необходимостью содержать избыток xi - bi рабочей силы и 2) С2(xi- xi-1)-затраты, связанные с необходимостью дополнительного найма (xi- xi-1) рабочих.
Элементы модели динамического программирования определяются следующим образом:
1. Этап і представляется порядковым номером недели і, і=1,2,…n.
2. Вариантами решения на і-ом этапе являются значения xi – количество работающих на протяжении і-й недели.
3. Состоянием на і-м этапе является xi-1 – количество работающих на протяжении (і-1) –й недели (этапа).
Рекуррентное уравнение динамического программирования представляется в виде
где 
Вычисления начинаются с этапа n при xn=bn и заканчиваются на этапе 1.
Задача замены оборудования:
Чем дольше механизм эксплуатируется, тем выше затраты на его обслуживание и ниже его производительность. Когда срок эксплуатации механизма достигает определенного уровня, может оказаться более выгодной его замена. Задача замены оборудования, таким образом, сводится к определению оптимального срока эксплуатации механизма.
Предположим, что мы занимаемся заменой механизмов на протяжении n лет. В начале каждого года принимается решение либо об эксплуатации механизма еще один год, либо о замене его новым.
Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна l.
Элементы модели динамического программирования таковы:
1. Этап і представляется порядковым номером года і, і=1,2,...n.
2. Вариантами решения на і-м этапе (т.е. для і-ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і-ого года.
3. Состоянием на і-м этапе является срок эксплуатации t (возраст) механизма к началу і-ого года.
Пусть fi(t)-максимальная прибыль, получаемая за годы от і до n при условии, что в начале і-ого года имеется механизм t-летнего возраста.
Рекуррентное уравнение имеет следующий вид:
(1)-если эксплуатировать механизм,
(2)-если заменить механизм.
Задача инвестирования:
Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P1, P2,…, Pn соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r1, а второй - r2. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы.
Премиальные меняются от года к году, и для і-ого года равны qi1 и qi2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.
Элементы модели динамического программирования следующие:
Похожие работы
... задачи, то лучше потратить время на построение приближенного алгоритма, чем пытаться построить полиномиальный, или же, если это позволяют условия, использовать алгоритмы с экспоненциальной сложностью работы Глава 2 Методы решения задачи о рюкзаке 2.1 Классификация методов На практике очень часто возникают NP-полные задачи, задач о рюкзаке – одна из них . Конечно надежд, на то что для ...
... 0 505/103 0 792/103 669/103 500/103 Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T. 3.4 Результат решения задачи планирования производства В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем ...
... времени на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости. 2. КЛАССИФИКАЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 2.1. Машинно – ориентированные языки Машинно – ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и ...
... реакции или вмешательства оператора. Точки диалога по своей природе подразделяются на информационные (для ввода данных) и управляющие (для выбора дальнейшего хода обработки). Принятый в автоматизированной системе маркетинга одежды способ построения человеко-машинного диалога обеспечивает максимальную наглядность, простоту и удобство работы в режиме эксплуатации. 3. Определение емкости, оценка ...
0 комментариев