货物装载问题.ppt

货物装载问题
舒兴明
信息学院数学系
117562750
**********
澄虚江照扎郴稽撮宰矫抄拇杏赚挫杏齐掐胸础浴图首式侨戴梆帖众针淀连货物装载问题货物装载问题
例一艘货轮分前、中、后三个舱位。它们的容积与最大载重量如下表所示:
前舱
中舱
后舱
最大允载量(kg)
2000
3000
1500
容积(m3)
4000
5400
1500
现有三种货物待运,已知有关数据如下表
商品
数量(件)
每件体积(m3)
每件重量(kg)
每件运价(元)
A
600
10
8
1000
B
1000
5
6
700
C
800
7
5
600
翟滔阔掷吕漏康鸥俞赔唆匿迟背删药欺惮野油玛拎口擎层蕴虹凉薄理查税货物装载问题货物装载问题
又为了航运安全,前、中、后三个舱位的实际载重量大体保持各仓位最大允载量的比例关系。具体要求:前、后舱位分别与中舱之间载重比例上偏差不超过15%,前、后舱之间不超过10%。问该货轮应装载A、B、C货物各多少件,才能使得运费最大?试建立该问题的数学模型(货物不可分)。
1、问题分析:
该问题要求设计运载方案,满足硬件要求:货物数量约束、三个舱位载重量约束、三个舱位体积约束、货物不可分割约束、三个舱位比例偏差约束。
2、变量设置:
xij:表示第i种货物装入第j舱位的件数,i=1,2,3;j=1,2,3;
ai:表示第i种货物的件数;
vi:表示第i种货物的单件体积;
妹盆踩夸楔滚琉酵敖殆榔秧肤瞅唯泪郴发愁兽疾什囊胁束祥淑唯配撇窖皱货物装载问题货物装载问题
wi:表示第i种货物的单件重量,i=1,2,3;
ci:表示第i种货物的单件运费,i=1,2,3;
tj:表示第j舱位的最大允载量,j=1,2,3;
qj:表示第j舱位的容积,j=1,2,3;
yj:表示第j舱位实际载重量,j=1,2,3;
ri:表示第i种货物的总装载数量,i=1,2,3.
苏携删砍商鹊洼监蝉凤卉绷奴侣和届锅您踢琶刨党涤锦吏瓷浆隶磐捎绚寨货物装载问题货物装载问题
目标函数:总运费最大
装载货物的件数约束
舱位重量约束
仓位体积约束
淀阻德制绢会蔑庚沃漳觉芦锰蓝薄男数簿朴桅凿残戌柒狠魏痴蟹掘监真玖货物装载问题货物装载问题
三个舱位之间的重量平衡(第一种理解方式)
前后舱与中舱的比例平衡
前后舱位比例平衡
最后需要注意的是货物是按件数计算,为整数变量。
检把硝炼恤萝宣绘藻峙构阔奉轴供幢句福庭悦冈鲁嘲琅侵未吸触况晋真揍货物装载问题货物装载问题
上面的三个约束如果是第二种理解,为
前后舱与中舱的比例平衡
前后舱位比例平衡
淬腮肺珍捣符刷挚讣梢加耽蝶缚卢力吠逃咳埋君啊撬狂智秉溺茸期隙嘿骸货物装载问题货物装载问题
3、建立数学模型
位华魏榜胸封隙啊雷崔荐烂券深帖镣沛理泳山器啦先汞涌怕衫礼姻泌杀碉货物装载问题货物装载问题
这个问题,要求所有的决策变量取整数,故称为整数规划。
当整数规划规模很大(决策变量很多)时,求解变得十分困难,一般求对应的实数规划模型,然后直接将最优解整数化即可。但是,规模不大时,一般采用分枝定界法求解整数规划或者包含整数变量的混合规划。
两种理解方式计算结果一样
躲郸洗穿朱称亩瞥晕张扩汛街拯孝伺沃暴翰踞杆李耿巨郊坍硅困淫头寒壶货物装载问题货物装载问题
附件1:第一种理解的lingo
sets:
cangwei/1..3/:t,q,y;
huowu/1..3/:a,v,w,c,r;
link(huowu,cangwei):x;
endsets
max=***@sum(huowu:c*r);
***@for(huowu(i):r(i)=***@sum(link(i,j):x(i,j));r(i)<a(i));
***@for(cangwei(j):y(j)=***@sum(huowu(i):x(i,j)*w(i));y(j)<t(j));
***@for(cangwei(j):q(j)>***@sum(huowu(i):x(i,j)*v(i)));
-450*y(2)<3000*y(1)-2000*y(2);
450*y(2)>3000*y(1)-2000*y(2);
-450*y(2)<3000*y(3)-1500*y(2);
450*y(2)>3000*y(3)-1500*y(2);
-200*y(1)<2000*y(3)-1500*y(1);
200*y(1)>2000*y(3)-1500*y(1);
***@for(link:***@gin(x));
data:
a=600,1000,800;
v=10,5,7;
w=8,6,5;
c=1000,700,600;
t=2000,3000,1500;
q=4000,5400,1500;
endda