货物装载问题

1、货物装载问题例 一艘货轮分前、中、后三个舱位。它们的容积与最大载重量如下表所示：前舱中舱后舱最大允载量(kg)200030001500容积（m3）400054001500现有三种货物待运，已知有关数据如下表商品数量(件）每件体积(m3) 每件重量(kg) 每件运价(元）A6001081000B100056700C80075600又为了航运安全，前、中、后三个舱位的实际载重量大体保持各仓位最大允载量的比例关系。具体要求：前、后舱位分别与中舱之间载重比例上偏差不超过15%，前、后舱之间不超过10%。问该货轮应装载A、B、C货物各多少件，才能使得运费最大？试建立该问题的数学模型（货物不可分）。1、问

2、题分析： 该问题要求设计运载方案，满足硬件要求：货物数量约束、三个舱位载重量约束、三个舱位体积约束、货物不可分割约束、三个舱位比例偏差约束。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.目标函数：总运费最大3133

3、2211maxiiircrcrcrcz装载货物的件数约束3 ,2, 1,3 ,2, 1,31iarixriijiji舱位重量约束3 ,2, 1,3 ,2, 1,31jTyjxwyjjiijij仓位体积约束3 , 2 , 1j ,qxvj31iiji三个舱位之间的重量平衡(第一种理解方式)前后舱与中舱的比例平衡11222y|.3000y2000y450yy22000015450y3000 223223y450y1500y3000y45015. 0|30001500yy|前后舱位比例平衡113113y200y1500y2000y20010. 0|20001500yy|最后需要注意的是货物是按件数计

4、算，为整数变量。上面的三个约束如果是第二种理解，为前后舱与中舱的比例平衡前后舱位比例平衡15.0|30002000|21yy15. 0|30001500|23yy10. 0|2000y1500y|13900000y2000y300090000021575000y1500y300057500023300000y1000y2000300000133、建立数学模型3 , 2 , 1,31iarxriijiji3ijiji 1xv, j1, 2, 3QjjyT , j1,2,33 ,2, 1j,xwy31iijij31maxiiircz%15|30002000yy|21%15|30001500yy|2

5、3%10|15002000yy|313 ,2, 1j, i ,Zx,0 xijij这个问题，要求所有的决策变量取整数，故称为整数规划。15.0|30002000|21yy15. 0|30001500|23yy10. 0|20001500|13yy 当整数规划规模很大(决策变量很多)时，求解变得十分困难，一般求对应的实数规划模型，然后直接将最优解整数化即可。但是，规模不大时，一般采用分枝定界法求解整数规划或者包含整数变量的混合规划。两种理解方式计算结果一样附件1：第一种理解的lingosets:cangwei/1.3/:t,q,y;huowu/1.3/:a,v,w,c,r;link(huowu,

6、cangwei):x;endsetsmax=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)sum(huowu(i):x(i,j)*v(i);-450*y(2)3000*y(1)-2000*y(2);-450*y(2)3000*y(3)-1500*y(2);-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

7、=1000,700,600;t=2000,3000,1500;q=4000,5400,1500;enddata Objective value: 801000.0 X( 1, 1) 250.0000 -1000.000 X( 1, 2) 275.0000 -1000.000 X( 1, 3) 75.00000 -1000.000 X( 2, 3) 150.0000 -700.0000 X( 3, 2) 160.0000 -600.0000附件2：第二种理解的lingosets:cangwei/1.3/:t,q,y;huowu/1.3/:a,v,w,c,r;link(huowu,cangwei)

8、:x;endsetsmax=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)sum(huowu(i):x(i,j)*v(i);-9000003000*y(1)-2000*y(2);-5750003000*y(3)-1500*y(2);-3000002000*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;

9、t=2000,3000,1500;q=4000,5400,1500;enddataObjective value: 801000.0 X( 1, 1) 250.0000 -1000.000 X( 1, 2) 275.0000 -1000.000 X( 1, 3) 75.00000 -1000.000 X( 2, 3) 150.0000 -700.0000 X( 3, 2) 160.0000 -600.0000问题问题：某办公大楼有11层高，办公室都设置在711层上，假设办公人员都乘电梯上楼，每层有60人办公，现有3台电梯A,B,C可利用，每层楼之间电梯的运行时间是3秒，最低层楼（一层）的停留时

10、间为20秒，其它各层的停留时间是10秒。每台电梯的最大容量为10人，在上班前电梯只在711层停靠。为了简单起见，假设早晨8：00以前办公人员已经陆续到达1层，能保证每部电梯在底层的停留时间（等待20秒）达到电梯的最大容量，电梯在各层的相应停留时间内办公人员能够顺利出入电梯；当无人使用电梯时，电梯在1楼待命，请问：（1）把这些人都送到相应的办公楼层，需要多少时间？（2）怎样调度电梯，能使办公人员到达相应的楼层所需总时间 尽可能最少？（3）请给出具体的电梯运行方案。2、电梯问题、电梯问题模型假设模型假设：（1）8：00前所有员工陆续到达候梯厅；（2）所有员工均坐电梯到达目标层；（3）3台电梯同时运

11、行；（4）早上上班时间，电梯只在711层楼停靠，且停靠的10秒 内这层楼的有关人员均可以全部出电梯；（5）到达目标层的5层楼的员工均匀到达；（6）每台电梯的计算时间为从开始运行，到最后停留在第一 层楼。一、 回答问题1 考虑一种理想状态：每部电梯每次只运输到达同一层楼的员工，那么，每层楼60人，电梯按照最大载重运输，则需要6个来回。每次所花费时间为第七楼：电梯运行时间: (3+3)x6x6=216秒电梯停留时间: (10+20)x6=180秒合计： 396秒第八楼(3+3)x7x6=252秒(10+20)x6=180秒432秒电梯运行时间: (3+3)x8x6=288秒电梯停留时间: (10+

12、20)x6=180秒合计： 468秒第九楼第十楼(3+3)x9x6=324秒(10+20)x6=180秒504秒第十一楼：电梯运行时间: (3+3)x10 x6=360秒电梯停留时间: (10+20)x6=180秒合计： 540秒 有3台电梯，假设A电梯运送7，10楼层，B电梯运送8，9楼层，C电梯只运送11楼层，那么最晚900秒可以运送完毕！但是，考虑到C电梯比A,B电梯早完工360秒，可以让A电梯在减少两次7层楼的运送，减少132秒；B电梯减少一次8层楼的运送，减少144秒；共减少276秒，那么将这276秒的运送任务加在C电梯，则C电梯运送完毕时间为540+276=816秒；A电梯运送完毕

13、时间为768秒；B电梯运送完毕时间为756秒；三台电梯完工时间差距都小于任何楼层的一次运送的调配，故将这300名工作人员运送完毕，需要816秒。二、回答问题21、分析、分析：显然，电梯每次混合运输各层楼的员工比每次只运输一层楼的员工需要多停几次，即所花费的时间多。所以运输最佳方案一定在后面的方案中产生。2、变量设置、变量设置：xij: 第i电梯运送的j层楼员工的次数；i=1,2,3表示A,B,C电梯, j=1,2,3,4,5表示第7,8,9,10,11层楼，其中，xij取整数，且 介于06。ti : 表示第i电梯的运行时间；i=1,2,3；w: 表示3台电梯的最长运行时间。3、建立模型、建立模

14、型3 , 2 , 1itw. t . swmini5 , 4 , 3 , 2 , 1j60 x1031iij3 , 2 , 1i)x)5j)(33(x)2010( (tijij61ji5 , 4 , 3 , 2 , 1j ; 3 , 2 , 1ixij取非负整数3 ,2, 1i12x61jij4、计算sets:dianti/1.3/:t;louceng/1.5/:;link(dianti,louceng):x;endsetsmin=w;for(dianti:w=t);for(louceng(j):10*sum(dianti(i):x(i,j)=60);for(dianti(i):t(i)=su

15、m(louceng(j):(10+20)*x(i,j)+(3+3)*(j+5)*x(i,j);for(link:gin(x);for(dianti(i):sum(louceng(j):x(i,j)=12);计算结果 Global optimal solution found at iteration: 21 Objective value: 780.0000 Variable Value Reduced Cost W 780.0000 0.000000 T( 1) 780.0000 0.000000 T( 2) 780.0000 0.000000 T( 3) 780.0000 0.000000 X( 1, 1) 2.000000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 6.000000 0.000000 X( 1, 4) 0.000000 0.000000 X( 1, 5) 2.000000 0.000000 X( 2, 1) 0.000000 66.00000 X( 2, 2) 0.000000 72.00000 X( 2, 3) 0.000000 78.00000 X( 2, 4) 5.000000 84.0000