Динамическое программирование

2
Приложения динамического программирования
В данном разделе рассмотрено четыре примера, каждый из которых выбран для демонстрации методов динамического программирования. При рассмотрении каждого примера особое внимание обратите на три основных элемента моделей динамического программирования.
1. Определение этапов.
2. Определение на каждом этапе вариантов решения (альтернатив).
3. Определение состояний на каждом этапе.
Из перечисленных выше элементов понятие состояния, как правило, представляется весьма сложным для восприятия. Рассмотренные в этом разделе приложения последовательно показывают, что определение состояния меняется в зависимости от моделируемой ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы:
1) какие соотношения связывают этапы вместе?
2) какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах?

3

4

5

6

7
В таблице 5 сравниваются допустимые решения для каждого значения х3.
Таблица 5 – Результаты этапа 3 задачи о загрузке
Этап 2. Таблица 6
(6)
Таблица 6 – Результаты этапа 2 задачи о загрузке

8

9

10
Задача замены оборудования
Чем дольше механизм эксплуатируется, тем выше затраты на его обслуживание и ниже его производительность. Когда срок эксплуатации механизма достигает определенного уровня, может оказаться более выгодной его замена. Задача замены оборудования, таким образом, сводится к определению оптимального срока эксплуатации механизма.
Предположим, что мы занимаемся заменой механизмов на протяжении t лет. В начале каждого года принимается решение либо об эксплуатации механизма еще один год, либо о замене его новым. Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) - стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I.
Элементы модели динамического программирования таковы.
1. Этап i представляется порядковым номером года, i = 1, 2, ..., n.
2. Вариантами решения на i-м этапе (т.е. для i-го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале i-го года.
3. Состоянием на i-м этапе является срок эксплуатации t (возраст) механизма к началу i-го года.

11

12
Таблица 8 – Исходные данные к примеру 4
Определение допустимых значений возраста механизма на каждом этапе является нетривиальной задачей. На рисунке 3 представлена рассматриваемая задача замены оборудования в виде сети. В начале первого года имеется механизм, эксплуатирующийся 3 года (на графике рисунка 3 по оси Y откладывается возраст механизма). Мы можем либо заменить его (З), либо эксплуатировать (С) на протяжении следующего года. Если механизм заменили, то в начале второго года его возраст будет равен одному году, в противном случае его возраст будет 4 года. Такой же подход используется в начале каждого года, начиная со второго по четвертый.

13
Рисунок 3 – Схема возможной замены механизма

14
Если однолетний механизм заменяется в начале второго или третьего года, то заменивший его механизм к началу следующего года также будет однолетним. К тому же, в начале 4-го года 6-летний механизм обязательно должен быть заменен, если он еще эксплуатируется; в конце 4-го года все механизмы продаются (П) в обязательном порядке. На схеме сети также видно, что в начале второго года возможны только механизмы со сроком эксплуатации 1 или 4 года. В начале третьего года механизм может иметь возраст 1, 2 или 5 лет, а в начале четвертого - 1, 2, 3 или 6 лет.
Решение данной задачи эквивалентно поиску маршрута максимальной длины (то есть приносящего максимальную прибыль) от начала первого года к концу четвертого в сети, показанной на рисунке 3. При решении этой задачи используем табличную форму записи (числовые данные в таблице кратны тысячам долларов).
Этап 4.
Таблица 9 – Результаты этапа 4 задачи замена оборудования

15
Этап 3.
Таблица 10 – Результаты этапа 3 задачи замена оборудования
Этап 2.
Таблица 11 – Результаты этапа 3 задачи замена оборудования
Этап 1.
Таблица 12 – Результаты этапа 3 задачи замена оборудования

16
На рисунке 4 показана последовательность получения оптимального решения. В начале первого года оптимальным решением при t = 3 является замена механизма. Следовательно, новый механизм к началу второго года будет находиться в эксплуатации 1 год. При t = 1 в начале второго года оптимальным решением будет либо использование, либо замена механизма. Если он заменяется, то новый к началу третьего года будет находиться в эксплуатации 1 год, иначе механизм будет иметь возраст 2 года. Описанный процесс продолжается до тех пор, пока не будет определено оптимальное решение для четвертого года.
Рисунок 4 – Решение примера 4