《案例4：背包问题》由会员分享，可在线阅读，更多相关《案例4：背包问题（8页珍藏版）》请在金锄头文库上搜索。
1、案例：背包问题有一个徒步旅行者，已知他能承受的旅行背包的重量不超过a(kg)。 设有n种物品可供他选择装入背包，这n种物品分别编号为1, 2, n。其中第i种物品每件的重量为a.(kg)，其使用价值(指一件第i种 物品对旅行者来说所带来的好处的一种数量指标)为c. (i=1, 2, n)o问这位旅行者应如何选择携带这n种物品的件数，使得总价值最 大？分析：这是一个组合最优化问题，易将此问题归结为一个线性整数规划问题。 建立线性规划模型【建立线性规划模型】设旅行者选择携带第种物品的件数为兀.,不难看出，背包问题可以归i结为如下的线性规划问题：max z =刀 c xi ii=1s.t.刀 a x
2、 0且整，i = 1,2, ni 建立动态规划模型【建立动态规划模型】设把可装入背包的物品种类分为n个阶段。在第i阶段先装入前i种物 品(i=1, 2,n)。在第i阶段开始时，把旅行者背包中允许装入前 i种物品的总重量作为状态变量，设为y装入每种物品的件数x(i=1, 2, n)为各阶段的决策变量。变量说明：设fk( y)等于当背包中允许装入物品的总重量不超过y和只允许装入前 k种物品采用最优策略时的最大使用价值。(k=1, 2,，n)。芳 c x (k = 1,2, n)i ii=1则f (y) = max ky并且当k=n,乙 a.x. yy=a时，有maxax. a i ii=1兰c x
3、i i i=1显然fn (a)也就是上述线性规划模型的最优解。 把上式转化为递归方程：一 f y) = maxy a1 - f (y) = max-yak -0 x. i0 x, k(属于前向算法)c x1 1x + f (y -a x )k k k-ik k其中x k为非负整数。案例：运载问题问题描述有一辆最大货运量为lot的卡车，用来装载三种货物。每种货物的单位 重量及相应的单位价值如表所示。问应如何装载才能使总的价值最大？货物编号123单位重量345单位价值456件数x1x2x3问题分析：此装载问题类似与背包问题。此问题是一个典型的最优化问题，优化目标是卡车装载的总价值最大； 装载当然越
4、多越好，但又受到卡车本身的最大货运量的限制；所以此问 题可以归结为如下的线性规划问题：max f (x) = 4x + 5x + 6x123s.t. 3 x + 4x + 5x 0且为整数，i=1, 2, 3i其中x. (i=1, 2, 3)分别表示装载第i种货物的件数。其他变量说明：W (i=1, 2，3)：第i种货物的单位重量(单位：吨)ci (i=1, 2, 3)：第i种货物的单位价值yk (k=1, 2, 3)分别表示装载前i种货物的货运量f (y )当背包中允许装入物品的总重量不超过yk和只允许装入前k种 k k物品采用最优策略时的最大使用价值。(k=1, 2, 3)。前向算法建立动
5、态规划模型可归结为动态规划问题，此问题的递归方程为f (y ) = max 4 x = 410 x1 戈f (y ) = max c x + f (y - w x )k+1k+1II k+1 k+1kk+1k+1 k+10 xk+1 1 茫Jk=1,2初始条件:状态转移方程:y = y 一 w x (k = 1,2)kk+1k+1 k+1具体如下：f (y) = max 4x = 41 0辭 1f (y) = max 5x + f (y - 4x )2 Iy I 2120x24Jf (y) = max 6x + f (y - 5x )3 IyI 3230 x3 J要求得总价值最大即求f (10
6、)。3求解线性规划模型的Lindo程序max 4 x1 + 5 x2 + 6 x3st3 x1 + 4 x2 + 5 x3 =0x2 =0x3 =0x1 =3x2 =2x3 valuevalue = curvalue;which=num; 存储第k阶段的决策变量最优值end %fordisp(sprintf(第 %d 阶段 f%d(%8.2f)=%8.2f=%d(单)*%d(决 策)+f(%d,%8.2f),.k,k,y,value,M(2,k),which,k-1,y-M(1,k)*which)Matlab程序运行结果 在命令行输入：MyFirstDP2Matlab运行结果：第 1 阶段 f
7、l（10.00）= 12.00=4（单）*3（决策）第 1 阶段 f1（ 6.00）= 8.00=4（单）*2 （决策）第 1 阶段 f1（ 2.00）= 0.00=4（单）*0（决策）第 2 阶段 f2（10.00）= 13.00=5（单）*1（决策）+f（1, 6.00）第 1 阶段 f1（ 5.00）= 4.00=4（单）*1（决策）第 1 阶段 f1（1.00）= 0.00=4（单）*0（决策）第 2 阶段 f2（5.00）= 5.00=5（单）*1（决策）+f（1, 1.00）第 1 阶段 f1（0.00）= 0.00=4（单）*0（决策）第 2 阶段 f2（ 0.00）= 0.00
8、=5（单）*0（决策）+f（1, 0.00）第 3 阶段 f3（10.00）= 13.00=6（单）*0（决策）+f（2, 10.00） ans =13可知总价值最大为13,根据以上结果分析依次可得此时决策变量x3 = 0, 乂2=1, X = 2；可见对这个问题建立线性整数规划模型与动态规划模型求解结果一致。 思考：得到决策是根据以上程序的输出字符串确定的，能否自动给出？ 后向算法建立动态规划模型可归结为动态规划问题，此问题的递归方程为如)=覽严3 = 6彳j0V x3 斗 y jf2(y)=晋严 2+y - 4 x2)0V / y jf (y) = max 4x + f (y 一 3x )
9、10吨1 21要求得总价值最大即求Z/10）。 求解动态规划模型的Matlab程序 function value=MyFirstDPl %动态规划模型求解程序示例%这是一个采用【后向算法】的动态规划建模方法 global M%M矩阵第i列针对第i种货物的信息M=3 4 5;%第行：单位重量4 5 6; 第二行：单位价值value = getmaxvalue（1,10）;%后向算法模型，这个就获得最优结果 function value=getmaxvalue（k,y）global M value = -inf;ek=3;%结束阶段if k=ekvalue = M(2,ek)*fix(y/M(1,
10、ek);%对第一阶段(只包含第一个决策 变量)which = fix(y/M(1,ek);disp(sprintf (第 %d 阶段 f%d(%8.2f)=%8.2f=%d(单)*%d(决 策)，k,k,y,value,M(2,k),which)returnendfor num=0 : fix(y/M(1,k)curvalue = M(2,k)*num + getmaxvalue(k+1,y-M(1,k)*num); if curvalue valuevalue = curvalue;which=num; 存储第k阶段的决策变量最优值end %ifend %fordisp(sprintf(第
11、%d 阶段 f%d(%8.2f)=%8.2f=%d(单)*%d(决 策)+f(%d,%8.2f),.k,k,y,value,M(2,k),which,k+1,y-M(1,k)*which)Matlab程序运行结果 在命令行输入：MyFirstDPlMatlab运行结果：第 3 阶段 f3( 10.00)= 12.00=6(单)*2(决策)第 3 阶段 f3( 6.00)= 6.00=6(单)*1(决策)第 3 阶段 f3( 2.00)= 0.00=6(单)*0(决策)第 2 阶段 f2( 10.00)= 12.00=5(单)*0(决策)+f(3,10.00)第 3 阶段 f3( 7.00)=
12、6.00=6(单)*1(决策)第 3 阶段 f3( 3.00)= 0.00=6(单)*0(决策)第 2 阶段 f2( 7.00)= 6.00=5(单)*0(决策)+f(3, 7.00)第 3 阶段 f3( 4.00)= 0.00=6(单)*0(决策)第 3 阶段 f3( 0.00)= 0.00=6(单)*0(决策)第 2 阶段 f2( 4.00)= 5.00=5(单)*1(决策)+f(3, 0.00)第 3 阶段 f3( 1.00)= 0.00=6(单)*0(决策)第 2 阶段 f2( 1.00)= 0.00=5(单)*0(决策)+f(3, 1.00)第 1 阶段 f1( 10.00)= 3.00=4(单)*2(决策)+f(2, 4.00) ans =13可知总价值最大为13,根据以上结果分析依次可得此时决策变量x3 = 0, 乂2=1, X = 2；可见对这个问题建立线性整数规划模型与动态规划模型求解结果一
