运筹学动态规划

运筹学动态规划生产－库存问题产品仓库容量H=9。期初库存量为2，要求期末（七月底）库存量为0。每个月生产的产品在月末入库。求最优生产计划xk

分析处理方法

静态处理——线性(整数)规划动态处理——动态规划生产－库存问题的动态结构阶段最优与总体最优之间的非一致性

每一阶段的最优决策未必能保证总体最优总体最优并不能保证每一阶段最优

能否通过阶段决策达到总体最优目标？

在什么条件下总体最优包含了阶段最优？

一般多阶段决策问题的结构Sj:j阶段初系统所处状态Xj：j阶段所作决策rj(Sj,Xj):j阶段在状态Sj下作决策Xj得到的收益(成本)允许状态集合

——

每一阶段可能初始状态的全体

决策空间——每一阶段决策变量的允许取值空间状态变换——每一阶段的初始状态经决策变量的作用产生下一阶段的初始状态策略——从初始阶段到最终阶段，每一阶段的决策所形成的序列子策略——从k阶段到最终阶段，每一阶段的决策所形成的序列最优指标函数——当k阶段的状态为Sk，并采取最优子策略此时得到的从k到n+1各阶段指标值的总和：

Bellman最优性原理“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然形成最优子策略”

动态规划递归方程建立动态规划模型及求解步骤划分阶段确定状态变量及允许状态集合确定决策变量及决策空间确定状态转移方程确定转移指标函数并建立递归方程

最短路径问题的应用找出A到E的最短路径

阶段划分IIVIIIII将A到E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题

求解策略记S(x)为节点x到E的最短路求解S(D1)=5，S(D2)=2

S(C1)=8；S(C2)=7；S(C3)=12

S(C1)=8；S(C2)=7；S(C3)=12S(B1)=20；S(B2)=14；S(B3)=19最优解资源分配问题有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）的关系见下表：求对三个项目的最优投资分配，使总投资效益最大。

项目A项目B项目C指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3阶段k：每投资一个项目作为一个阶段；状态变量sk：投资第k个项目前的资金余额；决策变量xk：第k个项目的投资额；决策允许集合：Dk(sk)={0≤xk≤sk}状态转移方程：sk+1=sk-xk阶段指标：vk(sk,xk)见表中所示；递推方程：fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}终端条件：f4(s4)=0k=4，f4(s4)=0;k=3，0≤x3≤s3，s4=s3-x3

k=2，0≤x2≤s2，s3=s2-x2

k=1，0≤x1≤s1，s2=s1-x1

最优解为:s1=4,x1*=1,s2=s1-x1=3,x2*=0,

最大效益为60万吨s3=s2-x2*=3,x3*=3,s4=s3-x3=0机器负荷分配问题某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。

第1年s1s2s3x1x2x3第2年第3年第4年第5年s4s5s6x4x5指标值(产量)V1(s1,x1)指标值(产量)V2(s2,x2)指标值(产量)V5(s5,x5)指标值(产量)V4(s4,x4)指标值(产量)V3(s3,x3)动态规划模型构造阶段k：

运行年份（k=1,2,3,4,5,6）；状态变量xk：

第k年初完好的机器数（k=1,2,3,4,5,6）；决策变量dk：

第k年投入高负荷运行的机器数；状态转移方程：sk+1=0.7xk+0.9(sk-xk)决策允许集合：Dk(sk)={xk|0xksk}阶段指标：vk(sk,xk)=8xk+5(sk-xk)终端条件：f6(s6)=0递推方程：

fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}

xkDk(sk)

=max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]}

0xksk第5年s5s6x5指标值(产量)V5(s5,x5)…+f6(s6)第4年s4s5x4指标值(产量)V4(s4,x4)…+f5(s5)f3(s3)=max{8x3+5(s3-x3)+f4(s4)}

0x3s3=max{8x3+5(s3-x3)+13.7s4}

0x3s3=max{8d3+5(s3-d3)+13.7[0.7d3+0.9(s3-d3)]}0x3s3=max{0.28x3+17.24s3}=17.52s3

0x3s3

x3*=s3s3x3第3年s4指标值(产量)V3(s3,x3)…+f4(s4)f2(s2)=max{8x2+5(s2-x2)+f3(s3)}

0x2s2=max{8x2+5(s2-x2)+17.52s3}

0x2s2=max{8x2+5(s2-x2)+17.52[0.7x2+0.9(s2-x2)]}

0x2s2=max{-0.504x2+20.77s2}=20.77s2

0x2s2x2*=0s2s3x2第2年指标值(产量)V2(s2,x2)…+f3(s3)f1(s1)=max{8x1+5(s1-x1)+f2(s2)}

0x1s1=max{8x1+5(s1-x1)+20.77s2}

0x1s1=max{8x1+5(s1-x1)+20.77[0.7x1+0.9(s1-x1)]}

0x1s1=max{-0.05x1+23.69s1}=23.69s1

0x1s1x1*=0第1年s1s2x1指标值(产量)V1(s1,x1)…+f2(s2)由此可以得到：

f1(s1)=23.69s1, x1*=0

f2(s2)=20.77s2, x2*=0 f3(s3)=17.52s3, x3*=s3

f4(s4)=13.60s4, x4*=s4 f5(s5)=8s5 x5*=s5用s1=1000代入，得到五年最大产量为

f1(s1)=f1(1000)=23690每年投入高负荷运行的机器数以及每年初完好的机器数为：

s1=1000

x1*=0, s2=0.7x1+0.9(s1-x1)=900

x2*=0, s3=0.7x2+0.9(s2-x2)=810

x3*=s3=810, s4=0.7x3+0.9(s3-x3)=567

x4*=s4=567, s5=0.7x4+0.9(s4-x4)=397

x5*=s5=397, s6=0.7x5+0.9(s5-x5)=278生产－库存问题一个工厂生产某种产品，1～7月份生产成本和产品需求量的变化情况如下表：为了调节生产生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低.。

阶段k：月份，k=1,2,…,7,8；状态变量sk：第k个月初（发货以前）的库存量；决策变量xk：第k个月的生产量；状态转移方程：sk+1=sk-rk+xk；决策允许集合：Dk(sk)={xk

|xk0,rk+1sk+1H} ={xk

|xk0,rk+1sk-rk+xkH}；阶段指标：vk(sk,xk)=ckxk；终端条件：f8(s8)=0, s8=0；递推方程：fk(sk)=min{vk(sk,xk)+fk+1(sk+1)}

xkDk(sk) =min{ckxk+fk+1(sk-rk+xk)}

xkDk(sk)设