运筹学实验_动态规划

1、实验二用MATLAB解决动态规划问问题：有一部货车每天沿着公路给四个售货店卸下6箱货物，如果各零售店出售该货物所得利润如下表所示，试求在各零售店卸下几箱货物，能使获得总利润最大其值为多少店1234000001423426455376764788657986671086解：1）将问题按售货店分为四个阶段2）设以表示为分配给第k个售货店到第n个工厂的货物数，Xk设为决策变量，表示为分配给第k个售货店的货物数，状态转移方程为Skf=SkXk。%（8）表示为箱货物分到第k个售货店所得的盈利值。fk（Sk）表示为Sk箱货物分配给第k个售货店到第n个售货店的最大盈利值。3）递推关系式：fk（$*）=max

2、Pk（x0+fk+i（”x044,3,2,1边界条件：f5包）=04）从最后一个阶段开始向前逆推计算。第四阶段：设将sa箱货物（$4=0,1,2,345,6）全部分配给4售货店时，最大盈利值为：f，S4）=maxP4（X4）其卜X4=54=0,l,2,3,4,5,6,表不使得竹）为最大值时的最优决策。P4（X4）fg)X401234560000144125523663466456656666第三阶段：设将S3箱货物（$3=0,123,4,5,6）分配给3售货店和4售货店时，对每一个弱值，都有一种最优分配方案,使得最大盈利值为：f3（S3）=maxP3（X3）+f4（S3X3），X3=0,123

3、45,6P3(X3)+f，S3X3)f3（S3）.X3012345600+00010+43+04020+53+45+07130+63+55+47+09240+63+65+57+48+011350+63+65+67+58+48+012泗60+63+65+67+68+58+48+013小第二阶段：设将$2箱货物（$2=0,123,4,5,6）分配给2售货店、3售货店和4售货店时，则最大盈利值为:f2（s2）=maxP2（X2）+f3（52X2）其中,X2=0,12345,6P2(X2)+f3(S2X2)f2（S2）X2012345600+00010+42+04020+72+44+07030+92+

4、74+46+090/140+112+94+76+48+0110/1/250+122+114+96+78+49+013360+132+124+116+98+79+410+015裕第一阶段：设将2箱货物（sl=0,1,2,3,456）分配给1售货店、2售货店、3售货店和4售货店时，则最大盈利值为：fi（sj=maxPi（xi）+f2（si-*1）其中,x】=0,12345,6Pi(xi)+fz(si-X1)fg)Xi012345600+00010+44+040/120+74+46+08130+94+76+47+011140+114+96+77+47+01350+134+116+97+77+47+0

5、1560+154+136+117+97+77+47+017按计算表格的顺序反推，可知最优分配方案有6个:1)2)3)4)5)6)X1*=11xj=l,X1*=1,xj=2,xi*=2,Xi*=2,X2,=l，X2*=2,X2*=3,X2*=0,X2,=l，X2*=2,X3*=3,X4*=1cx3*=2ix4*=1cX3*=l,X4*=lcx3*=3>x4*=1cX3*=2iX4*=1cX3*=l,X4*=lc以上6种最优方案的总利润均为17。使用Matlab解决上面的问题：在matlab命令窗口输入下面的程序:图1程序及其运行结果1CommandWindowNewtoMATLAB?See

6、resourcesforGettingStarted,MAXNum=d(l);for1=1:size(d.,2)ifd(l)KAXNumMAXNum=d(l):p=l:elsecontinue:endendfor1=1:size(d,2)ifd(l)=MMNumE(l,：)-lelsecontinue:endendMAXNmnans=1131ans=fx1221图2程序及其运行结果2CommandWindowNewtoMATLAB?SeeresourcesforGettingStarted.MAXlfum=Aad图3程序及其运行结果3m=l;A=0467777;B=02468910;C=035

7、7888;D=0456666;fora=l:7forb=l:7forc=l:7fore=l:7ifa+b+c+e=10d(m)=A(a)+B(b)+C(c)+D(e);E(m,l)=a;E(m,2)=b;E(m,3)=c;E(mz4)=e;m=m+l;elsecontinue;endendendendendMAXNum=d(l);forl=l:size(dz2)ifd(l)>MAXNumMAXNum=d(l);p=l;elsecontinue;endendforl=l:size(d,2)ifd(l)=MAXNumE(L：)-1elsecontinue;endendMAXNum按回车后可以得到以下的结果:111111ans=113ans=122ans=131ans=203ans=212ans=221MAXNum=17由运行结果可知最优方案有6个:1) xl*=l,x2*=l,x3*=3,x4*=lo2) xl*=l,x2*=2,x3*=2,x4*=lo3) xl*=l,x2