Стохастическое динамическое программирование. 1 страница

Динамическая задача управления запасами.

Распределение Q средств между N предприятиями.

Пусть х _n – средства, выделенные n-му предприятию; они приносят в конце года прибыль с_n(х _n).

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

Найти целочисленные неотрицательные переменные х _n (n=1,2,…,N), удовлетворяющие ограничению:

∑_n х _n = Q, (2.8.2)

и обращающие в максимум функцию

С=∑_n с_n(х _n). (2.8.3)

Здесь процесс распределения средств можно рассматривать как многошаговый, номер шага совпадает с номером предприятия; состояние будет определяться величиной s_n – количество средств, подлежащих распределению на n-м шаге (с конца).

Обозначим f_n(s_n) – условную оптимальную прибыль, полученную от последних n предприятий при распределении между ними s_n средств и вычисляемую в соответствие с динамическим рекуррентным соотношением:

f_n(s_n)=mах_"х(с_n(х _n) + f_n-1(s_n-1)), n=1,2,…,N. (2.8.4)

Пример 2.8.2. Пусть N = 4, Q =5, значения с_n(х _n) заданы в табл. 2.8.1.

Таблица 2.8.1.

х	с4(х)	с3(х)	с2(х)	с1(х)

Как и в предыдущем примере начинаем анализ с последнего предприятия. Индекс «1» соответствует последнему предприятию, а индекс «4» –первому. Для n=1 прибыль проставлена в последней колонке.

Для n=2

f₂(0)=mах[с₂(0)+f₁(0)]=0 при x ₂(0)=0,

f₂(1)=mах[с₂(1)+f₁(0),с₂(0)+f₁(1)]=mах[3+0,0+4]=4 при x ₂(1)=0,

f₂(2)=mах[с₂(2)+f₁(0),c₂(1)+f₁(1),с₂(0)+f₁(2)]=

=mах[4+0,3+4,0+6]=7 при x ₂(2)= 1,

f₂(3)=mах[с₂(3)+f₁(0),с₂(2)+f₁(1),с₂(1)+f₁(2),с₂(0)+f₁(3)]=

=mах[7+0,4+4,3+6,0+8]=9 при x ₂(3)=1,

f₂(4)=mах[с₂(4)+f₁(0),с₂(3)+f₁(1),с₂(2)+f₁(2),с₂(1)+f₁(3),с₂(0)+f₁(4)]=

=mах[11+0,7+4,4+6,3+8,0+13]=13 при х ₂(4)=0,

f₂(5)=mах[с₂(5)+f₁(0),с₂(4)+f₁(1),с₂(3)+f₁(2),с₂(2)+f₁(3),с₂(1)+f₁(4),с₂(0)+f₁(5)]

=mах[18+0,11+4,7+6,4+8,3+13,0+16]=18 при x₂(5)=5.

Для n=3

f₃(0)=mах[с₃(0)+f₂(0)]=0 при x₃(0)=0,

f₃(1)=mах[с₃(1)+f₂(0),с₃(0)+f₂(1)]=mах[6+0,0+4,]=6 при x ₃(1)=1,

f₃(2)=mах[с₃(2)+f₂(0),c₃(1)+f₂(1),с₃(0)+f₂(2)]=

=mах[9+0,6+4,0+7]=10 при x ₃(2)=1,

f₃(3)=mах[с₃(3)+f₂(0),с₃(2)+f₂(1),с₃(1)+f₂(2),с₃(0)+f₂(3)]=

=mах[11+0,9+4,6+7,0+9]=13 при x ₃(3)=1 или 2,

f₃(4)=mах[с₃(4)+f₂(0),с₃(3)+f₂(1),с₃(2)+f₂(2),с₃(1)+f₂(3),с₃(0)+f₂(4)]=

=mах[13+0,11+4,9+7,6+9,0+13]=16 при х ₃(4)=2,

f₃(5)=mах[с₃(5)+f₂(0),с₃(4)+f₂(1),с₃(3)+f₂(2),с₃(2)+f₂(3),с₃(1)+f₂(4),с₃(0)+f₂(5)]

=mах[15+0,13+4,11+7,9+9,6+13,0+18]=19 при x ₃(5)=1.

И, наконец, для n=4

f₄(0)=mах[с₄(0)+f₃(0)]=0 при x ₄(0)=0,

f₄(1)=mах[с₄(1)+f₃(0),с₄(0)+f₃(1)]=mах[8+0,0+6,]=8 при x ₄(1)=1,

f₄(2)=mах[с₄(2)+f₃(0),c₄(1)+f₃(1),с₄(0)+f₃(2)]=

=mах10+0,8+6,0+10]=14 при x ₄(2)=1,

f₄(3)=mах[с₄(3)+f₃(0),с₄(2)+f₃(1),с₄(1)+f₃(2),с₄(0)+f₃(3)]=

=mах[11+0,10+6,8+10,0+13]=18 при x ₄(3)=1,

f₄(4)=mах[с₄(4)+f₃(0),с₄(3)+f₃(1),с₄(2)+f₃(2),с₄(1)+f₃(3),с₄(0)+f₃(4)]=

=mах[12+0,11+6,10+10,8+13,0+16]=21 при х ₄(4)=1,

f₄(5)=mах[с₄(5)+f₃(0),с₄(4)+f₃(1),с₄(3)+f₃(2),с₄(2)+f₃(3),с₄(1)+f₃(4),с₄(0)+f₃(5)]

=mах[18+0,12+6,11+10,10+13,8+16,0+19]=24 при x ₄(5)=1.

Теперь соберем оптимальное решение (при последовательном рассмотрении всех состояний оптимальные переходы подчеркивались):

Для первого предприятия, когда s₄=5, видим, что x ₄(5)=1, значит, первое предприятие получает 1 и остается s₃=s₄– x ₄(5)=5–1=4. Находим лучшее размещение средств для второго предприятия (на третьем с конца шаге) при s₃=4. Это х ₃(4)=2, остается s₂=s₃– x ₃(4)=4–2=2. На втором (с конца) шаге x ₂(2)=1 и на последнее предприятие (первый с конца шаг) остается s₁= s₂ – x ₂(2)=2–1=1 и x₁(1)=1.

Максимум суммарной прибыли равен 24 у.е.

Применим изложенный выше подход к решению простейшей задачи управления запасами.

Пример 2.8.3. Необходимо разработать такую календарную программу выпуска изделия на плановый период, состоящий из Т временных отрезков, при которой общая сумма затрат на производство и на содержание запасов минимизируется при условии полного и своевременного удовлетворения спроса. Обозначим:

d_n – спрос на отрезке n от конца;

c_n(x,s) – затраты на отрезке n, связанные с выпуском х единиц изделия и с содержанием запасов, объем которых на конец отрезка равен s единиц. В этой системе обозначений подстрочный индекс «1» соответствует конечному, а «Т» – начальному состоянию.

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

Пусть f_n(s) – стоимость, отвечающая стратегии минимальных затрат на n оставшихся отрезках при уровне запасов s на начало n-го от конца отрезка;

x _n(s) – объем выпуска, обеспечивающий достижение f_n(s).

Пусть уровень запасов на конец планового периода равен нулю, тогда при уровне запасов s на начало последнего (1-го от конца) отрезка выпуск x ₁(s)=d₁–s и

f₁(s)= c₁(x,0)= c₁(d₁ – s,0), s=0,1,…,d₁.

Заметим, что если начальный уровень запасов отрезка n равен s, а объем выпуска – х, то величина (s+ х –d_n) – есть уровень запасов на конец данного отрезка, отсюда получаем общее рекуррентное соотношение в виде:

f_n(s) = min_x[c_n(x, s+ х –d_n)+ f_n-1(s+ х –d_n)], n=1,…,Т, s=0,1,…,d₁+…+ d_n.

Для упрощения вычислений предположим, что производственные мощности и складские площади ограничены, пусть х =0,1,…,5 и s=0,1,…,4. Допустим также, что спрос и затраты постоянны во времени, и пусть d_n=3, а c_n(x, s)= c(x)+hs, где первое слагаемое относится к производству, а второе определяется стоимостью содержания запасов (арендная плата за складские помещения, проценты за кредит для создания запасов, страховые взносы и собственно расходы по содержанию запасов). Пусть с(0)=0, с(1)=15, с(2)=17, с(3)=19,с(4)=21, с(5)=23; h=1.

Для n=1 f₁(0)=с(3)=19 при x ₁(0)=3,

f₁(1)=с(2)=17 при x ₁(1)=2,

f₁(2)=с(1)=15 при x ₁(2)=1,

f₁(3)=с(0)=0 при x ₁(3)=0.

Для n=2 f₂(0)=min[с(3)+0+f₁(0),c(4)+1+f₁(1),c(5)+2+f₁(2)]=

=min[19+19,21+1+17,23+2+15]=38 при x ₂(0)=3,

f₂(1)=min[с(2)+0+f₁(0),c(3)+1+f₁(1),c(4)+2+f₁(2),c(5)+3+f₁(3)]=

=min[17+19,19+1+17,21+2+15,23+3+0]=26 при x ₂(1)=5,

f₂(2)=min[с(1)+0+f₁(0),c(2)+1+f₁(1),c(3)+2+f₁(2),c(4)+3+f₁(3)]=

=min[15+19,17+1+17,19+2+15,21+3+0]=24 при x ₂(2)=4,

f₂(3)=min[с(0)+0+f₁(0),c(1)+1+f₁(1),c(2)+2+f₁(2),c(3)+3+f₁(3)]=

=min[0+19,15+1+17,17+2+15,19+3+0]=19 при x ₂(3)=0,

f₂(4)=min[с(0)+1+f₁(1),c(1)+2+f₁(2),c(2)+3+f₁(3)]=

=min[0+1+17,15+2+15,17+3+0]=18 при x ₂(4)=0.

Для n=3 f₃(0)=min[с(3)+0+f₂(0),c(4)+1+f₂(1),c(5)+2+f₂(2)]=

=min[19+38,21+1+26,23+2+24]=48 при x ₃(0)=4,

f₃(1)=min[с(2)+0+f₂(0),c(3)+1+f₂(1),c(4)+2+f₂(2),c(5)+3+f₂(3)]=

=min[17+38,19+1+26,21+2+24,23+3+19]=45 при x ₃(1)=5,

f₃(2)=min[с(1)+f₂(0),c(2)+1+f₂(1),c(3)+2+f₂(2),c(4)+3+f₂(3),c(5)+4+f₂(4)]=

=min[15+38,18+26,21+24,24+19,23+4+18]=43 при x ₃(2)=4,

f₃(3)=min[с(0)+0+f₂(0),c(1)+1+f₂(1),c(2)+2+f₂(2),c(3)+3+f₂(3),c(4)+4+f₂(4)]=

=min[0+38,16+26,19+24,22+19,25+18]=38 при x ₃(3)=0,

f₃(4)=min[с(0)+1+f₂(1),c(1)+2+f₂(2),c(2)+3+f₂(3),c(3)+4+ f₂(4)]=

=min[1+26,17+24,20+19,23+18]=27 при x ₃(4)=0.

И, наконец, для n=4

f₄(0)=min[с(3)+0+f₃(0),c(4)+1+f₃(1),c(5)+2+f₃(2)]=

=min[19+48,21+1+45,23+2+43]=67 при x ₄(0)=3 или 4,

f₄(1)=min[с(2)+0+f₃(0),c(3)+1+f₃(1),c(4)+2+f₃(2),c(5)+3+f₃(3)]=

=min[17+48,19+1+46,21+2+43,23+3+38]=64 при x ₄(1)=5,

f₄(2)=min[с(1)+f₃(0),c(2)+1+f₃(1),c(3)+2+f₃(2),c(4)+3+f₃(3),c(5)+4+f₃(4)]=

=min[15+48,18+45,21+43,24+38,23+4+27]=54 при x ₄(2)=5,

f₄(3)=min[с(0)+0+f₃(0),c(1)+1+f₃(1),c(2)+2+f₃(2),c(3)+3+f₃(3),c(4)+4+f₃(4)]=

=min[0+48,16+45,19+43,22+38,25+27]=48 при x ₄(3)=0,

f₄(4)=min[с(0)+1+f₃(1),c(1)+2+f₃(2),c(2)+3+f₃(3),c(3)+4+ f₃(4)]=

=min[1+45,17+43,20+38,23+27]=46 при x ₄(4)=0.

Сведем результаты вычислений в таблицу 2.8.2.

Таблица 2.8.2.

s

n=1

n=2

n=3

n=4

n=5

n=6

n=7

n=8

х 1

f1

x 2

f2

x 3

f3

x 4

f4

x 5

f5

x 6

f6

x 7

f7

x 8

f8

3,4

3,4

Читателю предоставляем возможность проверить результаты вычислений для n = 5 ¸ 8. Теперь, задаваясь различным уровнем запасов на начало планового периода, можно определить оптимальные стратегии для любого Т от 1 до 8. Так, например, если исходный уровень запасов на начало планового периода равен нулю, то оптимальный календарный план при Т=4 будет:

x ₄(0)=3, x ₃(0)=4, x ₂(1)=5, x ₁(3)=0 или

x ₄(0)=4, x ₃(1)=5, x ₂(3)=0, x ₁(0)=3

и минимальная общая сумма затрат составит 67.

Пусть Т=8, тогда минимальная общая сумма затрат составит 127 и x ₈(0)=5, останется на следующий отрезок 5 - 3=2, имеем x ₇(2)=5, значит на следующий отрезок останется 2+5 - 3=4 и x ₆(4)=0, останется 4 - 3=1 и x ₅(1)=5, останется 1+5 - 3=3, x ₄(3)=0, останется 3 - 3=0, x ₃(0)=4, останется 4 - 3=1, x ₂(1)=5, останется 1+5 - 3=3 и x ₁(3)=0.

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

Обратим внимание на Т=4. Здесь два оптимальных решения, дающих минимальные затраты 67. При Т=7 имеем три решения с одинаковым значением целевой функции 115.

Таблица. 2.8.3

Плановый период Т	n=8 янв	n=7 фев	n=6 мар	n=5 апр	n=4 май	n=3 июн	n=2 июл	n=1 авг	Общая сумма затрат	Средне- месячные затраты
							16.75
								15.8
										16.43
										15.9

Анализ оптимальных вариантов производственной программы, приведенных в табл. 2.8.3, свидетельствует о том, что январский выпуск поначалу возрастает с ростом Т, а затем колеблется около 5, аналогично, среднемесячные затраты испытывают колебания (при минимальном их значении 15.8). Проводя подобный анализ для следующих месяцев (при достаточно большом Т), получим оптимальное решение для бесконечного периода планирования. В условиях настоящего примера таким решением будет повторение производственного цикла (5,5,0,5,0,…) при среднемесячных затратах 15.8. (вычисления опускаем).

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

1) Управляемые переменные и соответствующие ограничения группируются по шагам, и многошаговый процесс принятия решений исследуется в определенной последовательности.

2) Для выбора оптимальных значений переменных на рассматриваемом шаге используется значение состояния только на данном шаге.

3) Решение, принимаемое при заданном текущем состоянии системы, оказывает прогнозируемое влияние на состояние системы на последующем шаге.

4) Оптимальность текущего решения оценивается в терминах прогнозируемого экономического эффекта для рассматриваемого шага и всех последующих шагов.

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

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

Пример 2.8.4. Задача садовника.

Предположим, что каждый год почва может находиться в одном из трех состояний: хорошем (1), удовлетворительном (2) или плохом (3). Пусть k=1 и 2 – две возможные стратегии поведения садовника: не удобрять или удобрять. Оптимальное поведение садовника определяется такой стратегией, при которой он получает наибольший ожидаемый доход через N лет. Обозначим р_ij(k) – вероятность перехода почвы из состояния i в состояние j при применении садовником стратегии k.

Пусть 0.2 0.5 0.3 0.3 0.6 0.1

{р_ij(1)}= 0 0.5 0.5, {р_ij(2)}= 0.1 0.6 0.3

0 0 1 0.05 0.4 0.55

Поясним суть приведенных данных:

Если садовник не применяет удобрения (k=1), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.2, в удовлетворительное – 0.5 и в плохое – 0.3. При плохом состоянии (строка 3) с вероятностью 1 почва остается плохой.

Если садовник применяет удобрения (k=2), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.3, в удовлетворительное – 0.6 и в плохое – 0.1. При плохом состоянии (строка 3) с вероятностью 0.05 почва станет хорошей, с вероятностью 0.4 удовлетворительной и с вероятностью 0.55 останется плохой.

Обозначим r_ij(k) – доход (или убыток), который получит садовник за одногодичный период, если почва перейдет из состояния i в состояние j при применении садовником стратегии k.

Пусть 7 6 3 6 5 – 1

{r_ij(1)}= 0 5 1, {r_ij(2)}= 7 4 0.

0 0 –1 6 3 –2

Поясним суть приведенных данных:

Если садовник не применяет удобрения (k=1), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 7 единиц, в удовлетворительное – 6 и в плохое – 3. При переходе из плохого состояния (строка 3, вспомним, что в этом случае с вероятностью 1 почва остается плохой) доход составит –1 (убыток).

Если садовник применяет удобрения (k=2), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 6, в удовлетворительное – 5 и в плохое – убыток в размере 1 (не в коня корм). При переходе из плохого состояния (строка 3) в хорошее доход составит 6, в удовлетворительное – 3 и в плохое – убыток 2.

Обозначим v_i(k) – ожидаемый доход, обусловленный одним переходом из состояния i при стратегии k, тогда

v_i(k)=∑_jp_ij(k)r_ij(k).

Если удобрения не применяются (k=1), тогда

v₁(1)=0.2´7+0.5´6+0.3´3=5.3,

v₂(1)=0´0+0.5´5+0.5´1=3,

v₃(1)=0´0+0´0+1´ (–1)= –1.

При использовании удобрений (k=2) имеем

v₁(2)=0.3´6+0.6´5+0.1´ (–1)=4.7,

v₂(2)=0.1´7+0.6´4+0.3´0=3.1,

v₃(2)=0.05´6+0.4´3+0.55´ (–2)=0.4.

Как и прежде будем анализировать плановый период с конца, обозначим f_n(i) – оптимальный ожидаемый доход за n лет до конца периода, тогда рекуррентные соотношения примут вид:

f₁(i)=max_k{v_i(k)},

f_n(i)=max_k{v_i(k)+∑_jp_ij(k)f_n-1(j)}, n=2,3,…,N. (2.8.4)

Проведем вычисления при N=4. Результаты поместим в таблицы 2.8.4 – 2.8.7.

n=1 Таблица. 2.8.4

i	vi(k)	Оптимальное решение
k=1	k=2	f1(i)	k*
	5.3	4.7	5.3
		3.1	3.1
	–1	0.4	0.4

n=2 Таблица. 2.8.5

i	vi(k)+pi1(k)f1(1)+pi2(k)f1(2)+pi3(k)f1(3)	Оптимальное решение
k=1	k=2	f2(i)	k*
	5.3+.2´5.3+.5´3.1+.3´.4= =8.03	4.7+.3´5.3+.6´3.1+.1´.4= =8.19	8.19
	3+0´5.3+.5´3.1+.5´.4= =4.75	3.1+.1´5.3+.6´3.1+.3´.4= =5.61	5.61
	–1+0´5.3+0´3.1+1´0.4= = –0.6	.4+.05´5.3+.4´3.1+.55´.4= =2.13	2.13

n=3 Таблица. 2.8.6

i	vi(k)+pi1(k)f2(1)+pi2(k)f2(2)+pi3(k)f2(3)	Оптимальное решение
k=1	k=2	f3(i)	k*
	5.3+.2´8.19+.5´5.6+.3´2.13= =10.38	4.7+.3´8.19+.6´5.61+.1´2.13= =10.74	10.74
	3+0´8.19+.5´5.61+.5´2.13= =6.87	3.1+.1´8.19+.6´5.61+.3´2.13= =7.92	7.92
	–1+0´8.19+0´5.61+1´2.13= = 1.13	.4+.05´8.19+.4´5.6+.55´2.13= =4.23	4.23

n=4 Таблица. 2.8.7

i	vi(k)+pi1(k)f3(1)+pi2(k)f3(2)+pi3(k)f3(3)	Оптим. решение
k=1	k=2	f4(i)	k*
	5.3+.2´10.74+.5´7.92+.3´4.23= =12.68	4.7+.3´10.74+.6´7.92+.1´4.23= =13.097	13.10
	3+0´10.74+.5´7.92+.5´4.23= =9.075	3.1+.1´10.74+.6´7.92+.3´4.23= =10.195	10.19
	–1+0´10.74+0´7.92+1´4.23= = 3.23	.4+.05´10.74+.4´7.92+.55´4.23 =6.4315	6.43

Из оптимального решения следует, что в 1-й,2-й и 3-й годы садовник должен применять удобрения (k*=2) при любом состоянии почвы, а в 4-й год (n=1) садовнику следует применять удобрения только при условии, что состояние почвы удовлетворительное или плохое. Суммарный ожидаемый доход за четыре года составит f₄(1)=13.10 при хорошем состоянии почвы в первый год, f₄(2)= 10.19 при удовлетворительном состоянии и f₄(3)=6.43 при плохом состоянии.

Приведенный выше метод решения задачи называют еще методом итераций по стратегиям.

Задачу садовника можно обобщить в двух отношениях. Во-первых, переходные вероятности и значения дохода не обязательно одни и те же в любой год; в этом случае они являются функциями n-го этапа: p_ij(k,n) и r_ij(k,n). Во-вторых, можно использовать коэффициент дисконтирования ожидаемых доходов, вследствие чего значения f_N(i) будут представлять собой приведенные величины ожидаемых доходов по всем этапам. Если α – годовой коэффициент дисконтирования, вычисляемый по формуле α=1/(1+t), где t – годовая норма процента, то рекуррентное соотношение (4.9.4) преобразуется к виду:

f_n(i)=max_k{ v_i(k)+α∑_jp_ij(k)f_n-1(j)}, n=2,3,…,N. (2.8.5)

Упражнение. Решите задачу садовника при коэффициенте дисконтирования α=0.6. (ответ приводится в таблице 2.8.8).

Таблица. 2.8.8

i	n=1	n=2	n=3	n=4
f1(i)	k*	f2(i)	k*	f3(i)	k*	f4(i)	k*
	5.3		6.94		7.77		8.26
	3.1		4.61		5.43		5.92
	0.4		1.44		2.19		2.66

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

Для определения оптимальной долгосрочной стратегии применяют два метода. Первый метод основан на переборе всех возможных стационарных стратегий управления и может быть использован при их малом числе. Второй метод (итераций по стратегиям) более эффективен в том смысле, что определяет оптимальную стратегию за малое число итераций. Идея метода заключается в использовании соотношения (2.8.4) при n → ∞.

Дата добавления: 2015-04-24