Реферат: Динамическое программирование (задача о загрузке)

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

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

Предположим, что проект будет выполнятся в течение 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