《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第七章动态规划 第五节车辆配载问题》由会员分享，可在线阅读，更多相关《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第七章动态规划 第五节车辆配载问题（12页珍藏版）》请在金锄头文库上搜索。
1、若某物流公司在某一条运输路线上发运一辆汽车，汽车的载重上限为a公斤。设该条路线上有n种物品需发运，可以选择性装载，这n种物品编号为1、2、n。已知第i种物品每件重量为wi公斤，可为公司创造效益是装载数量xi的函数ci(xi)。问此时应如何选择装载的物品(各几件)，使为公司创造效益最大。这就是著名的车辆装载问题，如流通加工中的下料问题，人造卫星内的物品装载问题等问题都可以归结为本类问题。 设xi为第i种物品的装载件数，则本问题的数学模型为：,上述问题模型是一个整数规划问题。如果xi只取0或1，则又称为0-1配载问题。下面用动态规划的方法来求解。 设按可装入物品的n个种类划分为n个阶段。 状态变量
2、sk表示用于装第1种物品至第k种物品的总重量。 决策变量xk表示装入第k种物品的件数。则状态转移方程为,允许决策集合为,最优值函数fk(sk)是当总装载重量不超过sk公斤时，车辆中可以装入第1种到第k种物品能为公司创造的最大效益值。即,xi0，且为整数。 因而可写出动态规划的顺序递推关系为：,然后，逐步计算出f1(s1)、f2(s2)、fn(sn)及相应的决策函数x1、x2、xn，最后得出的fn(a)就是所求的最大价值，其相应的最优策略由反推运算即可得出。,表7-7,例7-5 若某物流公司在某一条运输路线上发运一辆汽车，汽车的载重上限为10吨。设该条路线上有3种物品需发运，可以选择性装载。物品
3、单位重量和效益值如表77所示。问此时应如何选择装载的物品(各几件)，使该次运输为公司创造效益最大？,例7-5 解：将3件物品顺序标号为1、2、3。 本题的数学模型为：,用动态规划方法来解，此问题变为求f3(10)。而,例7-5,因此，要先计算出f2(10)、f2(5)、f2(0),同理,例7-5,因此，要先计算出f1(10)、f1(6)、f1(5)、f1(2)、f1(1)、f1(0)，一般地有,相应的最优决策为 ，,于是有 f1(10)=4312， 相应的x13 f1(6)=428， 相应的x12 f1(5)=414， 相应的x11 f1(2)=400， 相应的x10 f1(1)=400， 相
4、应的x10 f1(0)=400， 相应的x10,例7-5,从而 f2(10)=max12,5+8,10+0=13， 相应的x12，x2=1 f2(5)=max4,5+0=5， 相应的x10，x2=1 f2(0)=0， 相应的x10，x2=0 故最后得到 f3(10)=max13,6+5,12+0=13， 相应的x12，x2=1，x3=0 所以最优的装载方案为A物品2件、B物品1件、C物品不装，本次运输可为公司带来最大效益值为13（千元）。,例7-5,注：（1）若使用计算机求解时，对f1(s1)和f2(s2)(s1,s2=1,2,10)的值都应计算并存储以备用。 （2）在实际问题中，当a不大时，
5、为了计算的简便，可将单位重量wi排成递减序列，然后逐个分析xi的取值可能性，并适当加以比较调整，再删除某些可能性，这样可以节省计算量。 （3）当n很大时，就会产生存储量过大的困难，如果ci(xi)都是线性函数cixi，可按照单位重量的价值i=ci/xi(i=1,2,n)由小到大进行排序。设有ii1(i=1,2,n)，则对于给定的可供装载重量a，如果awn，且不是wn的整倍数时，若装载第n种物品，可能是最优解，但可以找到一个粗略的 估算公式：当 成立时，最优解中xn* 一定大于或等于1，即一定要装入第n种物品。,上面例子我们只考虑了装载重量的限制，它称为“一维配载问题”。如果还增加装载体积的限制
6、为b，并假设第i种物品每件的体积为vi立方米，问应如何配载可使得为公司创造效益最大。这就是“二维配载问题”，它的数学模型为,用动态规划方法来解，其思想方法与一维配载问题完全类似，只是这时的状态变量是 两个（重量和体积），决策变量仍是一个（物品的件数）。设最优值函数fk(a,b)是当总装载重量不超过a公斤、总装载体积不超过b立方米时，车辆中可以装入第1种到第k种物品能为公司创造的最大效益值。即 ，xi0，且为整数。 因而可写出动态规划的顺序递推关系为：,然后，逐步计算，最后得出的fn(a,b)就是所求的最大价值，其相应的最优策略由反推运算即可得出。,本节思考题,1. 什么是车辆配载问题？ 2.动态规划方法是如何求解车辆配载问题最优解的？,
