Принцип оптимальности Беллмана

Управление на каждом шаге нужно выбирать так, чтобы оп­тимальным был выигрыш, начиная с этого шага и до конца про­цесса.

Выигрыш, начиная с i -го шага и до конца процесса, обозна­чим W_i, и этот выигрыш зависит от состояния системы, в котором процесс подошел к i -му шагу.

Построение модели

1. Смотрим, можно ли разбить модель на этапы. Если да, то разбиваем на m -этапов, при этом шаги не должны быть сильно мелкими, иначе, задача может непомерно разрастись, обычно число шагов вытекает из условий задачи.

2. Определяем, что является состоянием системы, формулиру­ем критерий эффективности (S,W).

3. Выбираем управляющие переменные (X).

4. Записываем критерий эффективности на каждом шаге, т.е.

5. Определяем функцию перехода в новое состояние под воздействием управления X_i,-, т.е. = .

6. Определяем выигрыш, начиная с шага m для каждого состояния

,

Два последних уравнения называются рекуррентными со­отношениями Беллмана и отражают принцип динамического программирования. Итак, модель построена.

Метод решения ЗДП

1.Определяем все возможные состояния системы на последнем этапе -S₁,S₂,…S_k.

2.Для каждого состояния системы определяем наилучшее управление х_m (S_р), р = , исходя из формулы в п.6 по­становки модели.

3.Переходим на шаг m - 1 и т.д. до самого начала процесса

х_m-1 (S_р),… х_i (S_р),… х₁ (S_р), Для всех р =

4.Находим оптимальное значение

как максимум по всем возможным состояниям системы. Состояние системы, на котором достигается максимум, обозначим через S₁^*.

5.Определяем, при каком управлении достигается .

6.Определяем все оптимальные управления и состояния для каждого шага, S₁^*= где определяются из соотношений Беллмана. Получаем оптимальное управление X^* = ().

Ответом будут являться выигрыш W^* и вектор оптимального управления X^*.

На каждом шаге нам нужно находить значение W_i (S) для всех возможных состояний S, указывая при этом управление x_i, при котором данное значение критерия достигается.

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

Требуется определить стратегию замены оборудования на предприятии за 5 лет, если известно, что t - это возраст оборудования на начало периода или этапа,

r{t) - выручка от реализации продукции, произведенной на оборудовании возраста t лет,

l(t) - затраты на эксплуатацию оборудования возраста t лет,

с(t) - остаточная стоимость оборудования возраста t лет,

(t) - годовая прибыль от работы на оборудовании возраста t лет.

- предполагается, что решение о замене оборудования принимается перед началом деятельности в данном году.

t
r (t)
l (t)
c (t)
(t)

На первом году у нас может быть оборудование любого воз­раста, предполагается также, что эксплуатация оборудования не будет превышать 5 лет. Решение

Состоянием системы является возраст оборудования. Управляющие переменные

Критерием эффективности будет являться прибыль за пять лет.

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

	i = 5	i= 4	i= 3	i = 2	i= 1

=225

=160

=110

=59

=255

=190

=134

=104

=57

=285

=214

=164

=134

=87

=309

=244

=194

=164

=117

	i = 5	i= 4	i= 3	i = 2	i= 1
	-	-	-	-
	0225	0255	0285	0309
	0160	0190	0/1214	0/1244
	0110	1134	0/1164	0/1194
	159	1104	1134	1164
	112	157	187	1117

W^*=159

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

Вопросы для самоконтроля

1.Что представляет собой динамическое программирование?

2.С именем какого ученого-математика связано возникновение динамического программирования и в чем состоит суть сформулированного им принципа оптимальности?

3.Какие трудности связаны с вычислительными алгоритмами динамического программирования?

4.В чем заключается суть динамического программирования?

5.Каковы основные черты задач динамического программирования?

6.Какова существенная особенность метода динамического программирования?

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