动态规划例1求解下列整数规划的最优解要点

1、例1求解下列整数规划的最优解:maxZ=4x15x26x3(3xi+4x2+5x3010st1一xj>0(j=1,2,31xj为整数.解(1)建立动态规划模型：阶段变量：将给每一个变量xj赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3.设状态变量Sk表示从第k阶段到第3阶段约束右端最大值，则Sj=10.设决策变量xk表示第k阶段赋给变量xk的值(k=1,2,3).状态转移方程：s2=&-3x1,s3=s2-4x2.即段指标：U1(s1,x1)-4x1,u2(s2,x2)=5x2,u3(&,x3)=6x3.基本方程；fk(Sk)=maxsuk(Sk,xk)+fk

2、书(s)0Y)/)=0.其中a1=3,a2=4,a3=5.(1)用逆序法求解：当k=3时，f3(ss尸max-6x3+f4(s4p=max,6x3,0Vx3.口0Vx3：23l5j3(J而.0,1,2,3,4,5,6,7,8,9,10x】表示不超过x的最大整数。因此，当国=0,1,2,3,4时,x3=0；当&=般时，x3可取0或1；当s3=10时，x3可取0,1,2,由此确定f3(s3).现将有关数据列入表4.1中表4.1中.XSs弋6x3+f4(S4)f3(S3)*x3012000010002000300040005066160661706618066190661100612122m

3、axs2max15x2f3s2-4x2上0X2玄了当k=2时，有而S2w0,1,2,3,4,5,6,7,8,9,10。所以当S2=0,1,2,3时，x2=0;当&=4,5,6,7时,X2=0或1;当S2=8,9,10时X2=0,1,2。由此确定f2(s2现将有关数据列入表4.2中.maxs1max14x1f2S|-3x1p,而、=10，故Xi只能取0,1,2,3，由此确定力(4%现将有关数据列入表为”=2时11(G)取得最大值13.又由s2=4查表4.2得x21b=1,一S14x1+f2(§-3x1)f1(s)*X1S2L0123100+124+68+512+013244.3

4、中。及表4.3由表4.3可知按计算顺序反推S3=0,再由表4.1查得X3=0.因此，最优解为X3=2,x3=1,x3=0,最优解maxZ=13.例5用动态规划方法解下列非线性规划问题2maxz=X1x2x3X1+x2+x3<c、为主0i=1,2,3解：解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1,2,3设状态变量为S1,S2,S3,S4并记S10C取问题中的变量X1,状态转移方程为：允许决策集合为：各阶段指标函数为：X2,X3为决策变量S3=X3S3+X2=S2S2+X1=S1<CX3

5、=S300X20S2V1(X1)=X1V2(X2)00X10S1=X22V3(X3)=X3,各指标函k=3,2,1*X3=S32X2-X2)数以乘积方式结合，最优指标函数fk（Sk）表示从第k阶段初始状态Sk出发到第3阶段所得到的最大值，则动态规划基本方程为：'fk(Sk)=maXVk(Xk)fk中(Sk4)jXkk(sk)f4(S4)=1用逆序解法由后向前依次求解：k=3时，f3(S3)=maX、V3(X3)f4(S4)=maX(X3)=S3X3-D3(s3)x3壬3k=2时,2以与）二方初血人）"3）=°max2（x2-zmaxJ令h2（S2,X2）=X22（S

6、2-X2）用经典解析法求极值点：解得:X2dh22八=2x2s2-3x2=0dx22=S2X2=0(舍)3吟二2“6X2dx2d2h2dx2X22一3S2=-2S2:0一.2所以X2=-S2是极大值点。32224f2(S2)=(-S2)(S2-S2)=-_3327k=1时，43xr4,、3,f1(s1)=maxv1(x1)f2(s2)=max(x1s2)=maxx1(s1-x1)x.D(s)0Mq27o学堂27h1(',x)=x1(Si-x1)27dh1dx1_43二27(s1-x1)12,、2,x1(g-x1)(-1)-0271.斛得：x1S|x1=S1(舍)4d2%dx121212

7、z、2，二27(g-x1)(-1)-27(s1-x1)2424万兑(6-x1)=为佃-xI)(2x1-s)d2%dx1x1=-s4:二0一.1所以x=1S1是极大值点4一。'1041。、314力(与)=:5(s1-S1)=17s1427464由于S1未知，所以对S1再求极值，一、，14、maxf1(S1)=max(&)o多/"o<S1-；cv641显然S1=c时，f1(si)取得最大值f1(S1)=c464反向追踪得各阶段最优决策及最优值：*x1S1=c*3S2=S1fxi二一c4*11x1二一s1二一c44*21x2二一S2二一c323)1二一c64f2(s2

8、)=-S3=c32716*1s3=s2-x2=-c*x31=s3=c41f3(s3)=S3=-c4所以最优解为：x1=c,x2=c,x3=c,z=-c442464例6用动态规划方法解下列非线性规划问题23maxz=x1x2x3x1+x2+x3M6凶之0j=1,2,3解：按变量个数将原问题分为三个阶段，阶段变量k=1,2,3;选才?xk为决策变量；状态变量Sk表示第k阶段至第3阶段决策变量之和；取小区间长度A=1,小区间数目m=6/1=6,状态变量Sk的取值点为：付卜=0,1,2,3,4,5,6k之2-Si=6状态转移方程：Sk+1=SkXk；允许决策集合：Dk（Sk）=xk|0<Xk&l

9、t;Skk=1,2,3Xk,Sk均在分割点上取值；阶段指标函数分别为：g1（X1）=X12g2（X2）=X2g3（X3）=X33,最优指标函数fk（Sk）表示从第k阶段状态&出发到第3阶段所得到的最大值，动态规划的基本方程为：7k（Sk）=nmaXgk（Xk）fk+（Sk+）k=3,2,10k0kf4（S4）=1k=3时，f3（S3）=maX（X3）=S3X3自S3及X3取值点较多，计算结果以表格形式给出，见表6.1-6.3所示。表6.1计算结果X3f3（S3）*X301234560000111128823272734646445125125562162166表6.2计算结果X2f3（

10、S2X2）f2（S2）*0123456X20000101X000,1201X12X011301X82X13X081401X272X83X14X0271501X642X273X84X15X0641601X1252X643X274X85X16X01282表6.3计算结果5xi2f2(Sixi)fi(Si)*xi0123456601X644X279X816X1E25X036x01082由表6.3知，xi=2,si=6,则S2=sixi=62=4,查表6.2得：X2=1,则S3=S2X2=41=3,查表6.1得：X3=3,所以最优解为：xi=2,X2=1,x3=3,fi(si)=108o上面讨论的问题

11、仅有一个约束条件。对具有多个约束条件的问题，同样可以用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。例7某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表6.4所示。试问在各地区如何设置销售点可使每月总利润最大。表6.4利润值地区销售点01234101625303220121721223010141617解：如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1,2,3;决策变量xk表示分配给第k个地区的销售点数；状态变量为w表示分配给第k个至第3个地区的销售点总数；状态转移方程：Sk+1=Skxk,其中S1

12、=4；允许决策集合：Dk(Sk)=xk|0<xk<Sk阶段指标函数：gk(xk)表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk(Sk)表示将数量为的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：Jk(Sk)=0螳卜0)+fk书(Skxk)k=3,2,13(S4)=0数值计算如表所示表6.5k=3时计算结果s3Xg3（X3）f3（S3）*X3012340000110101214142316163417174表6.6k=2时计算结果Ag2（X2）+f3（S2X2）f2（S2）*X201234000010+1012+012120+1412+1017+

13、022130+1612+1417+1021+027240+1712+1617+1421+1022+0312,3表6.7k=1时计算结果g1（X1）+f2（S1X1）f1（S1）*01234X140+3116+2725+2230+1232+0472所以最优解为：xi=2,X2=1,X3=1,fi（4）=47,即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。例9（生产一库存问题）某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2,3,2,4单位，假设每批产品固定成本为3千元，若不生产为0,每单位产品

14、成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0,问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。解：以每个时期作为一个阶段，该问题分为4个阶段，k=1,2,3,4;决策变量Xk表示第k阶段生产的产品数；状态变量Sk表小第k阶段初的库存量；以dk表示第k阶段的需求，则状态转移方程：Sk+i=Sk+xkdk；k=4,3,2,1由于期初及期末库存为0,所以S1=0,S5=0；允许决策集合Dk(Sk)的确定：当Sk>dk时，Xk可以为0,当Sk<dk时，至少应生产dkSk,故Xk的下限为ma

15、x(0,dk-Sk)每期最大生产能力为6,Xk最大不超过6,由于期末库存为0,Xk还应小于本期至4期需求之和减去本期的库存44量，£dj-Sk,所以蛛的上限为min(£dj-Sk,6),故有：jkj=k4Dk(Sk)=xk|max(0,dkSk)<xk<min(Zdj-Sk,6)j4阶段指标函数rk(Sk,Xk)表示第k期的生产费用与存贮费用之和：0.5SkXk=0rk(Sk，Xk)-：3+Xk+0.5SkXk=1,2,3,4,5,6最优指标函数fk(s。表示第k期库存为Sk到第4期末的生产与存贮最低费用，动态规划基本方程为：fk(Sk)=min、Tk(Sk,X

16、k)fk1(Sk1)k=4,3,2,1Xk二Dk(Sk)f5(s5)=0先求出各状态允许状态集合及允许决策集合，如表6.8所示。表6.8状态允许状态集合及允许决策集合S10D1(s1)2,3,4,5,6S201234D2(S2)3,4,5,62,3,4,5,61,2,3,4,5,60,1,2,3,4,5,60,123,4,5S30123456D3(S3)2,3,4,5,6123,4,50,1,2,3,40,1230,1,20,10S401234D4(S4)4310由基本方程计算各阶段策略，结果如下表所示。表6.9k=4时计算结果S4X4r4(S4,X4)=，0.5s43+x4+0.5s4X4=

17、0X4#0S5f5(S5)f4(S4)0*4*700*7*13*6.5006.5*22600631*5.5005.5*402002表6.10k=3时计算结果S3X3r3（备？3）=<0.5S3X3=03+x3+0.5s3x3#0S4=S3+X32f4（S4）f3（S3）02345*6567890123476.565.521212.51313.5*1111234*54.55.56.57.58.50123476.565.5211.51212.513*10.5201234156780123476.565.52811.51212.5103-01231.55.56.57.512346.565.52

18、-811.5129.540*1226723465.528*11.595012.56.5345.52*88.56*0342*5表6.11k=2时计算结果S2X22（0?2）=0.5S2,3+x2+0.5S2X2=0x200S3=S2+X23f3（S3）f2（S2）360111747110.517.50*58281669381725.501116.536.5110.5171*47.528*15.558.53816.569.54817.5150111626110.516.52*3728*154838165948176105818*01.5011*12.515.5110.51626.52814.533

19、7.53815.548.54816.559.55817.5610.56515.5*02110.5*12.516281427381543848164958175106515表6.12k=1时计算结果S1X11（5,%）='0.5s3+X1+0.5slX1=0X1¥0S2=X1-2f2（S2）f1（S1）250162136115.521.504*721522*58312.520.569412.521.5逆向追踪可得：X1=5,S2=3,X2=0,S3=0,X3=6,S4=4,X4=01时期生产5个单位，第3时期生产6个单位，第2,4时期不生产，可使总费用最小，最小费用为20.5千

20、元。例10（库存一销售问题）设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表6.13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。表6.13单位购货成本及销售价格月份购货成本C销售价格P14045238423403944244解：按月份划分阶段，k=1,2,3,4;状态变量Sk表示第k月初的库存量，S1=200,S5=0;决策变量：xk表示第k月售出的货物数量，yk表示第k月购进的货物数量;状态转移方程：

21、Sk+1=Sk+ykXk；允许决策集合：0&xk&sk,0<yk<600-(skxk);阶段指标函数为：pkxk-ayk表示k月份的利润，其中pk为第k月份的单位销售价格，a为第k月份的单位购货成本；最优指标函数fk(sk)表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为：fk(sj=.maxPkXk-Ckykfk1(&i)k=4,3,2,102kSk02k900JA-xt)f5(s5)=0k=4时，*f4(s4)=max(44x4142y4)=44s4X4=s4y4=00,34940<y4<600,s4_x4)k=3时

22、，f3(S3)=max39x3-40y3f/sj0<x3学0可3<600_(S3-x3)max39x3-40y344(备y3-x3)0x等0耳3<600-(s3*)0<x<max(44s3-5x3+4ys)053<600_(s333)为求出使44s35x3+4y3最大的x3,y3,须求解线性规划问题：maxz=44s3-5x34y3JX3-S3x-x3+y3<600-S3e,y320只有两个变重x3,y3,可用图解法也可用单纯形法求解，取得取优解，x3=0,*-，、._y3=600-S3,f3(S3)=40S3+2400k=2时，f2S)=max42x

23、2-38y2f3(s3)0£x2至20a2至00Ts2-2).max42x2-38y240(s2V2-x2)24000_x2_s20等2哆00Ys2美),max(40S22x22y22400)0:子2:S2002多002气)类似地求得:k=1时，x2=s2,y2=600,f2(s2)=42s2+3600fi(Si)=max45xi-40y1f2(S2)0学¥0<yiJ00.(si*)=max45x-40y42(sy-x1)36000*s0-£yi工00，S-xi)=max(42s3x12yl3600)0<xS0?w00，s当)类似地求得：xi=si,y

24、i=600,fi(si)=45si+4800=13800逆向追踪得各月最优购货量及销售量：* *xi=si=200yi=600;x2=s2=si+yixi=600y2=600;* *、一x3=0y3=600s3=600(s2+y2x2)=0x4=s4=(s3+y3x3)=600y4=0即i月份销售200件，进货600件，2月份销售600件，进货600件，3月份销售量及进货量均为0,4月份销售600件，不进货，可获得最大总利润13800c例11某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从I0月I日至3月3I日。下个销售季节各月的需求预测值如表6.I4所示表6.I4需求预测值

25、（单位：双）月份i0iii2i23需求402030403020该鞋店的此种鞋完全从外部生产商进货，进货价每双4美元。进货批量的基本单位是箱，每箱I0双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6.I5所示表6.I5数量折扣数值表进货批量i箱2箱3箱4箱5箱数量折扣4%5%i0%20%25%假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办理一次，每次订货的采购费（与采购数量无关）为I0美元。月存贮费按每月月底鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的存贮量为“0”。试确定最佳的进货方案，以使总的

26、销售费用最小。解：阶段：将销售季节6个月中的每一个月作为一个阶段，即k=i,2,，6；状态变量：第k阶段的状态变量Sk代表第k个月初鞋的存量；决策变量：决策变量xk代表第k个月的采购批量；状态转移律：Sk+=Sk+xk-dk（dk是第k个月的需求量）；边界条件：S=S7=0,f7（S7）=0；阶段指标函数：rk（Sk，Xk）代表第k个月所发生的全部费用，即与采购数量无关的采购费Ck、与采购数量成正比的购置费Gk和存贮费Zk.其中：0,Xk=0Ckc；Gk=PxMXk；Zk=0.2（Sk+Xk-dk）10,Xk0最优指标函数：最优指标函数具有如下递推形式fk（Sk）=minCkGkZkfki（Ski）Xk=minCkGk0.2（SkXk-dk）fk1Xk-dJXk当k=6时（3月）：表6.16k=6时计算结果S601020X620100f6（琵）86480当k=5时（2月）:表6.17k=5时计算结果、X5S501020304050*X5f5(S5)020418816450164101721681424014220134136122301223086989008640505205050404当k=4时（1月）:表6.18k=4时计算结果弋、S4、01020304050帝X4f4(S4)0302304403021028228228630、402822025026226