Примеры задач динамического программирования

Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий («операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной? Для того, что

 

Задача планирования рабочей силы:

При выполнении некоторых проектов число рабочих, необходимых для выполнения какого-либо проекта, регулируется путем их найма и увольнения. Поскольку как наем, так и увольнение рабочих связано с дополнительными затратами, необходимо определить, каким образом должна регулироваться численность рабочих в период реализации проекта.

Предположим, что проект будет выполнятся в течение n недель и минимальная потребность в рабочей силе на протяжении i -й недели составит b_i рабочих. При идеальных условиях хотелось бы на протяжении i -й недели иметь в точности b_i рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей.

Если x_i – количество работающих на протяжении i -й недели, то возможны затраты двух видов:

1) С₁(x_i – b_i) – затраты, связанные с необходимостью содержать избыток x_i – b_i рабочей силы;

2) С₂(x_i – x_{i -1}) -затраты, связанные с необходимостью дополнительного найма (x_i – x_{i -1}) рабочих.

Элементы модели динамического программирования определяются следующим образом:

1. Этап і представляется порядковым номером недели і, і =1,2,… n.

2. Вариантами решения на і -ом этапе являются значения x_i – количество работающих на протяжении і -й недели.

3. Состоянием на і -м этапе является x_{i -1} – количество работающих на протяжении (і- 1) –й недели (этапа).

Рекуррентное уравнение динамического программирования представляется в виде

где .

Вычисления начинаются с n -го этапа при x_n = b_n и заканчиваются на 1 –ом этапе.

 

Задача замены оборудования:

Чем дольше механизм эксплуатируется, тем выше затраты на его обслуживание и ниже его производительность. Когда срок эксплуатации механизма достигает определенного уровня, может оказаться более выгодной его замена. Задача замены оборудования, таким образом, сводится к определению оптимального срока эксплуатации механизма.

Предположим, что мы занимаемся заменой механизмов на протяжении n лет. В начале каждого года принимается решение либо об эксплуатации механизма еще один год, либо о замене его новым.

Обозначим через r (t) и c (t) прибыль от эксплуатации t -летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s (t) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна l.

Элементы модели динамического программирования таковы:

1. Этап і представляется порядковым номером года і, і=1,2,... n.

2. Вариантами решения на і -м этапе (т.е. для і -ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і -ого года.

3. Состоянием на і -м этапе является срок эксплуатации t (возраст) механизма к началу і -ого года.

Пусть f_i (t) – максимальная прибыль, получаемая за годы от і до n при условии, что в начале і -ого года имеется механизм t -летнего возраста.

Рекуррентное уравнение имеет следующий вид:

(1) – если эксплуатировать механизм,

(2) – если заменить механизм.

 

Задача инвестирования:

Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P ₁, P ₂,…, P_n соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r ₁, а второй - r ₂. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы.

Премиальные меняются от года к году, и для і -ого года равны q_{i 1} и q_{i 2} в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.

Элементы модели динамического программирования следующие:

1. Этап і представляется порядковым номером года і, і=1,2,...n

2. Вариантами решения на і -м этапе (для і -ого года) являются суммы l_i и  инвестиций в первый и второй банк соответственно.

3. Состоянием x_i на і -м этапе является сумма денег на начало і -ого года, которые могут быть инвестированы.

Заметим, что по определению = x_i - l_i. Следовательно,

где і= 2,3,… n, x ₁ = P ₁. Сумма денег x_i, которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за инвестиции, сделанные на протяжении (і -1) -го года.

Пусть f_i (x_i) – оптимальная сумма инвестиций для интервала от і -го до n -го года при условии, что в начале і -го года имеется денежная сумма x_i. Далее обозначим через s_i накопленную сумму к концу n -го года при условии, что l_i и (x_i - l_i) – объемы инвестиций на протяжении і -го года в первый и второй банк соответственно. Обозначая , і= 1,2, мы можем сформулировать задачу в следующем виде.

Максимизировать z = s ₁ + s ₂ +…+ s_n, где

Так как премиальные за n -й год являются частью накопленной денежной суммы от инвестиций, в выражения для s_n добавлены q_{n 1} и q_{n 2}.

Итак, в данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид

где x_{i +1} выражается через x_i в соответствии с приведенной выше формулой, а f_{n +1} (x_{n +1})=0.