运筹学动态规划应用举例

运筹学动态规划应用举例演示文稿目前一页\总数五十八页\编于五点运筹学动态规划应用举例目前二页\总数五十八页\编于五点第四节动态规划在经济管理中的应用

连续变量的离散化解法

先介绍连续变量离散化的概念。如投资分配问题的一般静态模型为：模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量状态转移方程、基本方程、指标函数、最优指标函数目前三页\总数五十八页\编于五点建立它的动态规划模型，其基本方程为：其状态转移方程为:由于与都是连续变量，当各阶段指标没有特殊性而较为复杂时，要求出会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如下：目前四页\总数五十八页\编于五点（1）

令，把区间[0，a]进行分割，的大小可依据问题所要求的精度以及计算机的容量来定。目前五页\总数五十八页\编于五点(2)

规定状态变量及决策变量只在离散点上取值，相应的指标函数就被定义在这些离散值上，于是递推方程就变为：其中

目前六页\总数五十八页\编于五点

作为离散化例子，在例5中规定状态变量和决策变量只在给出的离散点上取值，见例6。（3）按逆序方法，逐步递推求出，最后求出最优资金分配方案。目前七页\总数五十八页\编于五点问如何分配投资数额才能使总效益最大?例5

某公司有资金10万元，若投资于项目i(i=1,2,3)的投资额为xi时，其效益分别为：目前八页\总数五十八页\编于五点例6

连续变量的离散化解法目前九页\总数五十八页\编于五点解

令，将区间[0，10]分割成0，2，4，6，8，10六个点，即状态变量集合为允许决策集合为，与均在分割点上取值。

动态规划基本方程为：

当k=3时，

目前十页\总数五十八页\编于五点式中与的集合均为：计算结果见表7-1。02468100832721282000246810当k=3时，

表7-1目前十一页\总数五十八页\编于五点当k=2时，

计算结果见表7-2。

02468100020240246024680246810081832263672504454128906862722001461088680900183672128200024000表7-2目前十二页\总数五十八页\编于五点当k=1时，

计算结果见表7-3。

表7-3

10

101010

1010024681020013688605040200

0

目前十三页\总数五十八页\编于五点最大收益为，与例5结论完全相同。计算结果表明，最优决策为：

应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。目前十四页\总数五十八页\编于五点一、背包问题

一位旅行者携带背包去登山，已知他所能承受的背包重量限度为akg，现有n种物品可供他选择装入背包，第i种物品的单件重量为aikg，其价值是携带数量xi的函数ci(xi)(i=1,2,…,n)，问旅行者应如何选择携带各种物品的件数，以使总价值最大？目前十五页\总数五十八页\编于五点例1

有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？货物编号i123单位重量(t)345单位价值ci456逆序解法：阶段k：

k=1,2,3状态变量sk:第k阶段可以装载第k种到第3种货物的重量。决策变量xk:决定装载第k种货物的数量。状态转移方程:sk+1=sk-akxk最优指标函数fk(sk):当可装载重量为sk,装载第k种到第3种货物所获得的最大价值。基本方程：目前十六页\总数五十八页\编于五点当阶段k=3时，有s3012345678910x3000000101010101012c3+f40000006060606060612f3000006666612x3*00000111112当阶段k=2时，有s2012345678910x2000001010101012012012c2+f3000005+0656565651065+610125+610f200005666101112x2*00001000210目前十七页\总数五十八页\编于五点当阶段k=1时，有s110x10123c1+f3124+68+512f213x1*2目前十八页\总数五十八页\编于五点二、生产经营问题

在生产和经营管理中，经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。下面通过例子来说明对不同特点问题的不同处理技巧。目前十九页\总数五十八页\编于五点例2

生产与存贮问题

某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产j单位产品费用为：

每月库存j单位产品的费用为，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。12342324目前二十页\总数五十八页\编于五点用动态规划方法求解时，对有关概念作如下分析：(1)阶段：每个月为一个阶段，k＝1，2，3，4。(2)状态变量：为第k个月初的库存量。(3)决策变量：为第k个月的生产量。(4)状态转移方程：(5)最优指标函数：表示第k月状态为时，采取最佳策略生产，从本月到计划结束(第4月末)的生产与存贮最低费用。（6）基本方程：目前二十一页\总数五十八页\编于五点

k＝4，s5=s4+u4-g4=0，所以u4=g4-s4=4-s4，s4可取0，1，2，3。s40123u44321C+E+f576+0.55+14+1.5f476.565.5u4*4321

k＝3，s4=s3+u3-g3，所以u3=s4+g3-s3，s3可取0，1，2，3。s30123u3234512340123012C+E+f45+76+6.57+68+5.54.5+75.5+6.56.5+67.5+5.51+75+6.56+67+5.51.5+6.55.5+66.5+5.5f31211.588u3*2100目前二十二页\总数五十八页\编于五点

k＝2，s3=s2+u2-g2，所以u2=s3+g2-s2，s2可取0，1，2，3。s20123u23456234512340123C+E+f36+127+11.58+89+85.5+126.5+11.57.5+88.5+85+126+11.57+88+81.5+125.5+11.56.5+87.5+8f21615.51513.5u2*5430

k＝1，s2=s1+u1-g1，所以u1=s2+g1-s1，s1可取0。s10u12345C+E+f25+166+15.57+158+13.5f121u1*2反推回去，u1*=2，u2*=5，u3*=0，u4*=4。目前二十三页\总数五十八页\编于五点例3

采购与销售问题

某商店在未来的4个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存这种商品l000单位。假定该商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如表7_12所示，假定商店在1月开始经销时，仓库贮有该商品500单位。试问若不计库存费用，该商店应如何制定1月至4月的订购与销售计划，使预期获利最大。月份（k）购买单价（ck）销售单价（pk）110122983111341517目前二十四页\总数五十八页\编于五点解

按月份划分为4个阶段，k=l，2，3，4状态变量：第k月初时仓库中的存货量(含上月订货)。决策变量：第k月卖出的货物数量。

：第k月订购的货物数量。

状态转移方程：

最优指标函数：第k月初存货量为时，从第k月到4月末所获最大利润。则有逆序递推关系式为：目前二十五页\总数五十八页\编于五点当k=4时

显然，决策应取时才有最大值目前二十六页\总数五十八页\编于五点当k=3时

这个阶段需解一个线性规划问题：

因为只有两个变量x3,y3

，可以用图解法，也可以用单纯形法，求解得到：时有最大值

目前二十七页\总数五十八页\编于五点当k=2时

求解线性规划问题：

得目前二十八页\总数五十八页\编于五点当k=1时

求解一个线性规划问题：

得∵∴目前二十九页\总数五十八页\编于五点最优策略见下表。最大利润为16000。月份期前存货售出量购进量15005000200100031000100010004100010000目前三十页\总数五十八页\编于五点例4限期采购问题(随机型)

某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概率如表7-14所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。原材料单价（元）概率5006007000.30.30.4表7-14目前三十一页\总数五十八页\编于五点

阶段k：可按采购期限(周)分为5段，k＝1，2，3，4，5。状态变量：第k周的原料实际价格。

决策变量：第k周如采购则＝1，若不采购则=0。

另外用表示：当第k周决定等待，而在以后采购时的采购价格期望值。

最优指标函数：第k周实际价格为时，从第k周至第5周采取最优策略所花费的最低期望价格。则有逆序递推关系式为：解

本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而按某种已知的概率分布取值，即属于随机型动态规划问题。为状态集合{500，600，700}。

目前三十二页\总数五十八页\编于五点当k=5时

因为若前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以

目前三十三页\总数五十八页\编于五点当k=4时

由于

所以

目前三十四页\总数五十八页\编于五点当k=3时

由于

所以

目前三十五页\总数五十八页\编于五点当k=2时同理

目前三十六页\总数五十八页\编于五点当k=1时

目前三十七页\总数五十八页\编于五点所以，最优采购策略为：若第一、二、三周原料价格为500，则立即采购，否则在以后的几周内再采购。若第四周价格为500或600，则立即采购，否则等第五周再采购。而第五周时无论当时价格为多少都必须采购。按照以上策略进行采购，期望价格为：目前三十八页\总数五十八页\编于五点三、设备更新问题从经济上分析，一台设备应该使用多少年更新最合算，这就是设备更新问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多,维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费，为了比较不同决策的优劣，常常要在一个较长的时间内考虑更新决策问题。目前三十九页\总数五十八页\编于五点

设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。

rk(t)：在第k年设备已使用过t年(或称役龄为t年)，再使用1年时的效益。

uk(t)：在第k年设备役龄为t年，再使用一年的维修费用。

ck(t)：在第k年卖掉—台役龄为t年的设备，买进一台新设备的更新净费用。

为折扣因子(01)，表示一年以后的单位收入价值相当于现年的单位。目前四十页\总数五十八页\编于五点动态规划模型阶段变量k：k=1,2,…,n，表示计划使用该设备的年限数。

状态变量sk:第k年初，设备已使用过的年数，即役龄。决策变量xk:是第k年初更新（Replacement），还是保留使用（keep）旧设备，分别用R与K表示。

状态转移方程为：

阶段指标为：

指标函数为：目前四十一页\总数五十八页\编于五点最优指标函数fk(sk)表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程：实际上，目前四十二页\总数五十八页\编于五点例5

设某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新策略，使总收益最大。（设）

役龄项目012345效益54.543.7532.5维修费0.5

11.522.53更新费0.51.52.22.533.5目前四十三页\总数五十八页\编于五点解如前述建立动态规划模型，n=5

当k=5时，

状态变量s5可取1，2，3，4。

=2.5=2=1.5役龄项目012345效益54.543.7532.5维修费0.5

11.522.53更新费0.51.52.22.533.5目前四十四页\总数五十八页\编于五点当k=4时，

状态变量s4可取1，2，3。

==6.5役龄项目012345效益54.543.7532.5维修费0.5

11.522.53更新费0.51.52.22.533.5==5.8==5.5目前四十五页\总数五十八页\编于五点当k=3时，

状态变量s3可取1，2。

==9.5役龄项目012345效益54.543.7532.5维修费0.5

11.522.53更新费0.51.52.22.533.5==8.8目前四十六页\总数五十八页\编于五点当k=2时，

状态变量s2只能取1役龄项目012345效益54.543.7532.5维修费0.5

11.522.53更新费0.51.52.22.533.5==12.5目前四十七页\总数五十八页\编于五点当k=1时，

状态变量s1只能取0役龄项目012345效益54.543.7532.5维修费0.5

11.522.53更新费0.51.52.22.533.5=17目前四十八页\总数五十八页\编于五点上述计算递推回去，当时，由状态转移方程，

则

则查得：状态，查：

推出，查

最优策略为：，即第一年初购买的设备到第二、三、四年初各更新一次，用到第5年末，其总效益为17万元。

目前四十九页\总数五十八页\编于五点

k＝5，s5可取1,2,3,4。s51234u5KRKRKRKRv5+f64.5-15-0.5-1.54-1.55-0.5-2.23.75-25-0.5-2.53-2.55-0.5-3f53.52.521.5u5*KKRR

k＝4,s4可取1,2,3。s4123u4KRKRKRv4+f54.5-1+2.55-0.5-1.5+3.54-1.5+25-0.5-2.2+3.53.75-2+1.55-0.5-2.5+3.5f46.55.85.5u4*RRR目前五十页\总数五十八页\编于五点

k＝3，s3可取1,2。s312u3KRKRv3+f44.5-1+5.85-0.5-1.5+6.54-1.5+5.55-0.5-2.2+6.5f49.58.8u4*RR

k＝2,s2可取1。s21u2KRv3+f24.5-1+8.85-0.5-1.5+9.5f212.5u2*R

k＝1,s2可取0。s10u1KRv1+f25-0.5+12