лекции, учебные пособия / конспект лекций / Lekcii / Лекция 13 (Устюжанин В.А

Многоэтапные процессы принятия решений.

Динамическое программирование (принцип Белламана).

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

w(u)=w(u₁, u₂, …, u_n)

Существует два способа решения этой задачи:

1. последовательно просчитывать каждый процесс (с первого и до последнего)

2. используя принцип Белламана, который гласит: нельзя получить оптимальное значение целевой функции, i-го шагового процесса, если существует некоторое управление u1, выбранное на некотором i-ом шаге, так, что значение целевой функции для оставшихся i-1 шагов не является оптимальным.

Нужно рассматривать такое решение, которое учитывает все последующие шаги. Должна быть оптимальная сумма выигрыша на всех оставшихся шагах + на данном.

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

Рассмотрим пример: предположим, что нам необходимо проложить оптимальный путь из одного города в другой, учитывая то, что у нас есть сеть дорог, проходящих через промежуточные населенные пункты. Длины дорог известна.

Изобразим это графически:

Движемся справа налево и рассматриваем каждый узел, присваиваем ему определенный вес, например:

Идем по самой верхней ветке справа налево:

На первом участке имеем оптимальные потере в размере 10.

На втором: 16=10+6, и т.д., т.е. учитываем весь путь.

Необходимо проделать подобное для каждой ветки.

После этого мы будем двигаться в обратную сторону (слева направо), и учитывая минимальные веса, найдем решение.

Принцип Белламана может использоваться при решении следующих задач:

1. распределения ресурсов (несколько сегментов сети)

2. задача о загрузке судна

3. задача о ранце (сколько чего нужно собрать в поход солдату/туристу)

4. задача оптимальной политики замены оборудования

Многоэтапные процессы в условиях неопределенности

Рассмотрим такой вариант:

Имеется возможность закупить партию деталей (большую или маленькую).

Прибыль от этой партии будет зависеть от коньюктуры рынка.

Нужно выработать стратегию на календарный год.

	Z1 (благоприятность)	Z2 (неблагоприятность)	Издержки на приобретение
x1	50	40	200
x2	200	60	1000
Вероятность	0,75	0,25	-

После 4-х месяцев мы можем докупать (y1) или не докупать (y2) детали, в зависимости от наших потребностей.

	Z1 (благоприятность)	Z2 (неблагоприятность)	Издержки на приобретение**
y1	180	40	840
y2	50	40	-

Построим граф:

Дополнительная партия требует дополнительных затрат на покупку**

Рассчитаем нашу прибыль в случае с принятием решения в условиях риска:

1. Вершина 4:

для y₁:

[180*0.75+40*0.25]*8месяцев-840=320

для y₂:

[50*0.75+40*0.25]*8месяцев =380

2. Переходим к вершине 1:

при выборе x₂:

[200*0.75+60*0.25]*12месяцев-100=980 (*** - мы принимаем это решение, как оптимальное в условиях риска)

по х₁(при неблагоприятных условиях за календарный год):

[40*0.25*12месяцев+50*0.75*4месяца]+380*0.75-200=475

Решим эту же задачу в условиях неопределенности (минимаксный критерий):

Матрица решений для узла 4:

	Z1	Z2
y1	600	-520	-520 (min)	320 (max)
y2	400	320	320 (min)

600=180*8-840

-520=40*8-840

Матрица решений для узла 1:

	Z1	Z2
y1	320	280	280 (min)	280 (max)
y2	1400	-280	-280 (min)

-280=12*40-200

-280=60*12-1000

Таким образом, используя минимаксный критерий (в условиях неопределенности), мы должны закупить малую партию в начале календарного года.