案例4：背包问题.doc

案例：背包问题有一个徒步旅行者，已知他能承受的旅行背包的重量不超过a（kg）。设有n种物品可供他选择装入背包，这n种物品分别编号为1，2，n。其中第i种物品每件的重量为ai（kg），其使用价值（指一件第i种物品对旅行者来说所带来的好处的一种数量指标）为ci（i1，2，n）。问这位旅行者应如何选择携带这n种物品的件数，使得总价值最大？n 分析：这是一个组合最优化问题，易将此问题归结为一个线性整数规划问题。n 建立线性规划模型【建立线性规划模型】设旅行者选择携带第种物品的件数为，不难看出，背包问题可以归结为如下的线性规划问题：n 建立动态规划模型【建立动态规划模型】设把可装入背包的物品种类分为n个阶段。在第i阶段先装入前i种物品（i1，2，n）。在第i阶段开始时，把旅行者背包中允许装入前i种物品的总重量作为状态变量，设为y。装入每种物品的件数xi（i1，2，n）为各阶段的决策变量。变量说明：设等于当背包中允许装入物品的总重量不超过y和只允许装入前k种物品采用最优策略时的最大使用价值。（k1，2，n）。则并且当kn，ya时，有显然也就是上述线性规划模型的最优解。把上式转化为递归方程： （属于前向算法）其中为非负整数。n 案例：运载问题n 问题描述有一辆最大货运量为10t的卡车，用来装载三种货物。每种货物的单位重量及相应的单位价值如表所示。问应如何装载才能使总的价值最大？货物编号123单位重量345单位价值456件 数n 问题分析：此装载问题类似与背包问题。此问题是一个典型的最优化问题，优化目标是卡车装载的总价值最大；装载当然越多越好，但又受到卡车本身的最大货运量的限制；所以此问题可以归结为如下的线性规划问题： 且为整数，i1，2，3其中xi（i1，2，3）分别表示装载第i种货物的件数。其他变量说明：wi（i1，2，3）：第i种货物的单位重量（单位：吨）ci（i1，2，3）：第i种货物的单位价值yk（k1，2，3）分别表示装载前i种货物的货运量 当背包中允许装入物品的总重量不超过yk和只允许装入前k种物品采用最优策略时的最大使用价值。（k1，2，3）。前向算法建立动态规划模型可归结为动态规划问题，此问题的递归方程为k1，2初始条件：状态转移方程：具体如下：要求得总价值最大即求。求解线性规划模型的Lindo程序max 4 x1 + 5 x2 + 6 x3st3 x1 + 4 x2 + 5 x3 =0x2 =0x3 =0x1 =3x2 =2x3 value value = curvalue; which=num;%存储第 k阶段的决策变量最优值 end %if 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阶段f1(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=5(单)*0(决策)+f(1, 0.00)第3阶段f3(10.00)= 13.00=6(单)*0(决策)+f(2, 10.00)ans = 13可知总价值最大为13，根据以上结果分析依次可得此时决策变量x30，x21，x12；可见对这个问题建立线性整数规划模型与动态规划模型求解结果一致。n 思考：得到决策是根据以上程序的输出字符串确定的，能否自动给出？后向算法建立动态规划模型可归结为动态规划问题，此问题的递归方程为要求得总价值最大即求。求解动态规划模型的Matlab程序function value=MyFirstDP1%动态规划模型求解程序示例%这是一个采用【后向算法】的动态规划建模方法global M %M矩阵第i列针对第i种货物的信息M=3 4 5; %第一行：单位重量 4 5 6; %第二行：单位价值value = getmaxvalue(1,10);%后向算法模型，这个就获得最优结果function value=getmaxvalue(k,y)global Mvalue = -inf;ek=3;%结束阶段if k=ek value = M(2,ek)*fix(y/M(1,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 value value = curvalue; which=num;%存储第 k阶段的决策变量最优值 end %if 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程序运行结果在命令行输入：MyFirstDP1Matlab运行结果：第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)= 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，根据以上结果分析依次可得此时决策变量x30，x21，x12； 可见对这个问题建立线性整数规划模型与动态规划模型求解结果一致。（_）：前向算法与后向算法结果一致求解方法结果对比分析n 思考：从上面对同一个问题分别建立线性规划模型、动态规划模型，虽然结果一致，但有什么不同之处呢？动态规划结果更加全面，得到全局最优解。n 实验：机器负荷分配问题某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷情况下，设年初投入的完好机器数为u，年终的完好机器数为0.7u，称