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

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Проектирование дороги
Прокладывается участков лесовозной дороги между нижним складом леспромхоза и погрузочной площадкой лесопункта по пересеченной местности. Требуется провести дорогу, чтобы суммарные затраты на сооружение участка были минимальные.
Управление всей операции состоит из совокупности шаговых управлений u = (j1, j2,..., jm). Требуется найти такое оптимальное управление u*, при котором суммарные затраты W на сооружение участков минимальны, т.е.
W*=ΣWi ? min.
Участок местности разбивается на сетку, вдоль направлений которой будет сроиться дорога из пункта А в пункт В. Дорогу из каждой точки можно строить столько слева-направо или снизу-вверх.
Цифры, стоящие рядом с отрезками, обозначают затраты на строительство данного кусочка дороги.
Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, была бы минимальна.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Метод решения
Решение задач динамического программированияидет двухэтапным способом. На первом этапе решается последовательно несколько задач условного программирования, начиная от последнего шага задачи, двигаясь по направлению к первому.
Условность задачи объясняется тем, что m шаг решается исходя из предположения о том, как завершился m-1 шаг.
Решение неявного второго этапа носит безусловный характер, т.к. оптимальным решением задачи является решение, полученное на первом шаге (оно учитывает все последующие шаги (например, участки дороги) и соответствует оптимальной ситуации в целом).

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Проектирование дороги

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Проектирование дороги
После решения последовательности задач условной оптимизации общее оптимальное решение находится прямым проходом "по карте" и практически соответствует решению первого (самого ближнего к точке А) шага.
Общие затраты на строительство дороги составят 78 условных единиц.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальное распределение ресурсов
В общем виде задачи оптимального распределения ресурсов могут быть описаны следующим образом. Имеется некоторое количество ресурсов (материальные, трудовые, финансовые), которые необходимо распределить между различными объектами их использования по отдельным промежуткам планового периода так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.
Показателем эффективности может служить, например, прибыль, себестоимость, суммарные затраты и т.д.
Пример. Оптимальное распределение памяти.
Завлаб имеет в своем распоряжении 7 модулей оперативной памяти, которые должен использовать при модернизации 5 компьютеров. Эффективность работы каждого из них при добавлении нескольких модулей приведена в таблице. Определить самый оптимальный вариант распределения модулей между компьютерами для получения наивысшего суммарного коэффициента эффективности.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальное распределение памяти
Эффективность работы i-того компьютера при добавлении в него u модулей оперативной памяти выражается функцией fi(u).

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальное распределение памяти
Решение задачи разбивается на 5 шагов, при этом подразумевается, что на первом шаге ОЗУ выделялось для 1-го компьютера, на втором – для второго и т.д.
Тогда, все оставшиеся модули после модернизации четырех компьютеров, будут использованы в пятом.
W*=W1-5=Σfi(u)
Таким образом, начиная решать задачу условной пошаговой оптимизации с последнего шага, функция на пятом шаге будет W5=f5(u).
Переходя к 4 шагу и осуществляя перебор возможных вариантов остатков модули памяти после распределения по трем первым компьютерам, находим
W*4-5=(f4(u)+f5(u))*.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальное распределение памяти
Эффективность работы i-того компьютера при добавлении в него u модулей оперативной памяти выражается функцией fi(u).

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальное распределение памяти
Далее от рассмотрения 4-го шага переходим к третьему. Общая целевая функция будет выглядеть как W*=f3(u)+W4-5(s-u), где s – остаток от u после модернизации третьего компьютера, u – остаток модулей к третьему шагу.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальное распределение памяти
Рассматривая аналогичным образом распределение модулей памяти между вторым и оставшимися (третьим, четвертым, пятым), а также производя вычисления для первого (u1=7), на "прямом проходе" получаем, что оптимальная политика модернизации компьютеров выглядит следующим образом.
W*(3,1,0,0,3)=4.43

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Оптимальная политика замены оборудования
В результате физического и морального износа оборудования растут производственные затраты по выпуску продукции, увеличиваются затраты на ремонт и обслуживание техники, а также снижается производительность. Наступает момент, когда старое оборудование более выгодно продать, заменив новым, чем эксплуатировать ценой больших затрат. При этом оборудование можно заменить либо новым оборудованием того же вида, либо новым или бывшем в употреблении, более совершенным в техническом отношении, с учетом технического прогресса.
При составлении модели динамического программирования процесс замены рассматривается как N-шаговый, разбив весь период на N промежутков. Так как в начале каждого из этих промежутков принимается решение о сохранении оборудования, либо его замене, то управление на i шаге (i=1,2,...,N) содержит лишь две альтернативные переменные.
Обозначим через uc решение, состоящее в сохранении старого оборудования, а через uз - решение, состоящее в замене старого оборудования новым. Условная оптимизация на каждом шаге состоит в вычислении двух величин и в выборе из них наибольшей (наименьшей). Это значительно упрощает расчеты на стадии условной оптимизации и позволяет решать вручную задачи о замене с большим числом шагов.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Замена форвардера
Рассматривается эксплуатация форвардера в течении шести лет. В начале каждого года может быть принято решение о замене машины новой.
Стоимость нового форвардера на i шаге эксплуатации составляет zi=50000+5000(i-1) долларов. После t лет эксплуатации машину можно продать за s(t)=zi2-t долларов. Стоимость содержания машины в течении i года составляет g(t)=0.1zi*(t+1) долларов. Найти оптимальный способ эксплуатации машины: когда нужно заменить машину новой, чтобы суммарные затраты (с учетом затрат на покупку новой машины в начале срока эксплуатации и компенсации за счет заключительной продажи) были минимальны.

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Замена форвардера
Процесс эксплуатации форвардера описывается шестью шагами. Состояние si-1 системы в начале i шага характеризуется одним параметром t – возрастом машины. Управление на каждом шаге состоит в выборе одного из двух решений: uc – решение, состоящее в сохранении форвардера, или uз – решение, состоящее в его замене. Основные функциональные уравнения модели динамического программирования имеют вид:
Wi(t) = min , i<6
Для шестого шага:
W6(t) = min , i=6
Подставляя уравнения задачи в первую систему, получаем
Wi(t) = min , i<6
gi(t) + Wi+1(t+1), ui=uc
zi + gi(0) – si(t) + Wi+1(1), ui=uз
g6(t) – s7(t+1), u6=uc
z6 + g6(0) – s6(t) – s7(1), u6=uз
500(t+1)(i+9) + Wi+1(t+1), ui=uc
5000(i+9)(1.1–2-t) + Wi+1(1), ui=uз

Теория принятия решений
ПетрГУ, А.П.Мощевикин, 2004 г.
Динамическое программирование
Замена форвардера
Подставляя уравнения задачи в систему для шестого шага, получаем
W6(t) = min , i=6, t=0..5
Рассчитываем два варианта исхода 6 шага в зависимости от срока предыдущей эксплуатации форвардера (1-5 лет, 0 лет ему быть не может, т.к. рассматривается начало 6 года, и смена форвардера на новый в начале года, а не в конце).
7500(t+1) – 80000*2-t+1, u6=uc
42500 – 75000*2-t, u6=uз