Этапы решения задачи динамического программирования. 
Формулировка задачи о замене оборудования

После того как выполнены пункты 1−7, и математическая модель составлена, приступают к ее расчету.

Основные этапы решения задачи динамического программирования:

• 1. Определение множества возможных состояний Sm для последнего шага.
• 2. Проведение условной оптимизации для каждого состояния s€ Sm на последнем m-м шаге по формуле (1.3) и определение условного оптимального управления x (s), s€ Sm
• 3. Определение множества возможных состояний Si для i-го шага, i=2,3…, m-1.
• 4. Проведение условной оптимизации i-го шага, i=2,3…, m-1 для каждого состояния s€ S_m по формуле (1.4) и определение условного оптимального управления x_i (s), s€ S_m, i=2,3…, m-1.
• 5. Определение начального состояния системы s₁, оптимального выигрыша W1(S1) и оптимального управления x1(S1) по формуле (1.4) при i=1. Это есть оптимальный выигрыш для всей задачи W* =W₁(x₁*).
• 6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x₁*=x₁(s₁) подставить в формулу (1.2) и определить следующее состояние системы s₁=f₁(s₁, x₁). Для измененного состояния найти оптимальное управление x₂*=x₂(s₂), подставить в формулу (1.2) и т. д. Для i-го состояния s₁ найти s_i+1=f_i+1(s_i, x_i*) и x*_i+1(s_i+1) и т. д.

Динамическое программирование обычно придерживается двух подходов к решению задач:

• · нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач;
• · восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи.

Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

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

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

Следовательно, если имеется оптимальная траектория, то и любой ее участок представляет собой оптимальную траекторию.

Этот принцип позволяет сформулировать эффективный метод решения широкого класса многошаговых задач.

Под функцией Беллмана в текущий момент времени понимаем минимальное значение критерия качества в текущий момент времени: Если t=0, то.

Таким образом, значение функции Беллмана S (x, t) определяет минимальную величину функционала для любого начального состояния x (t) в любой момент времени t. С другой стороны, значение функции Беллмана совпадает со значением, так называемых текущих потерь на управление:

Эксплуатация оборудования планируется в течение n лет, но оборудование имеет тенденцию с течением времени стареть и приносить все меньшую годовую прибыль r (t), где t — возраст оборудования. При этом есть выбор: либо в начале любого года продать устаревшее оборудование за цену S (t), которая также зависит от возраста, и купить новое оборудование за цену P, либо оставить оборудование в эксплуатации. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарная прибыль за все n лет была максимальной, учитывая, что к началу эксплуатационного периода возраст оборудования составляет t₀ лет.

Входными данными к этой задаче являются:

r (t) — доход от эксплуатации в течение одного года оборудования возраста t лет;

S (t) — остаточная стоимость оборудования;

P — цена нового оборудования;

t₀ — начальный возраст оборудования.

Переменной управления на k-м шаге является логическая переменная, которая может принимать два значения: С — сохранить, З — заменить оборудование в начале k-го года. Переменной состояния системы на k-м шаге является переменная t.

Функцию Беллмана F_k(t) определим как максимально возможную прибыль от эксплуатации оборудования за годы с k-го по n-й, если к началу k-го года возраст оборудования составлял t лет. Применяя то или иное управление, мы переводим систему в некоторое новое состояние, а именно, если в начале k-го года мы оборудование сохраняем, то к началу следующего (k+1)-го года его возраст увеличится на 1 (состояние системы станет равно t+1), за год оно принесет прибыль r (t), и максимально возможная прибыль за оставшиеся годы (с (k+1)-го по n-й) составит F_k+1(t+1). Если же в начале k-го года принимаем решение на замену оборудования, то мы продаем старое оборудование возраста t лет за цену S (t), покупаем новое оборудование за цену P и эксплуатируем его в течение k-го года, что приносит за этот год прибыль r (0). К началу следующего года возраст оборудования составит 1 год, и за все годы с (k+1)-го по n-й максимально возможная прибыль будет F_k+1(1).

Из этих двух вариантов управления выбираем тот, который приносит большую прибыль. Уравнение Беллмана на каждом шаге имеет вид:

. (1).

Функцию Беллмана для первого шага (k=n) легко вычислить — это максимально возможная прибыль только за последний n-й год:

. (2).

Вычислив значение функции F_n(t) по формуле (2), далее можно посчитать F_n-1(t), затем F_n-2(t) и так далее до F₁(t₀). Функция F₁(t₀) представляет собой максимально возможную прибыль за все годы (с 1-го по n-й). Этот максимум достигается при некотором управлении, применяя которое в течение первого года, мы определяем возраст оборудования к началу второго года (в зависимости от того, какое управление является для первого года оптимальным, это будет 1 или t₀+1). Для данного возраста оборудования по результатам, полученным на этапе условной оптимизации, мы смотрим, при каком управлении достигается максимум прибыли за годы со 2-го по n-й и так далее. На этапе безусловной оптимизации отыскиваются годы, в начале которых следует произвести замену оборудования.