貨物裝載問題

1、貨物裝載問題例 一艘貨輪分前、中、后三個(gè)艙位。它們的容積與最大載重量如下表所示：前艙中艙后艙最大允載量(kg)200030001500容積（m3）400054001500現(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)如下表商品數(shù)量(件）每件體積(m3) 每件重量(kg) 每件運(yùn)價(jià)(元）A6001081000B100056700C80075600又為了航運(yùn)安全，前、中、后三個(gè)艙位的實(shí)際載重量大體保持各倉(cāng)位最大允載量的比例關(guān)系。具體要求：前、后艙位分別與中艙之間載重比例上偏差不超過15%，前、后艙之間不超過10%。問該貨輪應(yīng)裝載A、B、C貨物各多少件，才能使得運(yùn)費(fèi)最大？試建立該問題的數(shù)學(xué)模型（貨物不可分）。1、問

2、題分析： 該問題要求設(shè)計(jì)運(yùn)載方案，滿足硬件要求：貨物數(shù)量約束、三個(gè)艙位載重量約束、三個(gè)艙位體積約束、貨物不可分割約束、三個(gè)艙位比例偏差約束。2、變量設(shè)置： xij：表示第i種貨物裝入第j艙位的件數(shù)，i=1,2,3;j=1,2,3;ai：表示第i種貨物的件數(shù)；vi：表示第i種貨物的單件體積；wi：表示第i種貨物的單件重量，i=1,2,3;ci：表示第i種貨物的單件運(yùn)費(fèi)，i=1,2,3；tj：表示第j艙位的最大允載量，j=1,2,3;qj：表示第j艙位的容積，j=1,2,3;yj：表示第j艙位實(shí)際載重量，j=1,2,3;ri：表示第i種貨物的總裝載數(shù)量,i=1,2,3.目標(biāo)函數(shù)：總運(yùn)費(fèi)最大3133

3、2211maxiiircrcrcrcz裝載貨物的件數(shù)約束3 ,2, 1,3 ,2, 1,31iarixriijiji艙位重量約束3 ,2, 1,3 ,2, 1,31jTyjxwyjjiijij倉(cāng)位體積約束3 , 2 , 1j ,qxvj31iiji三個(gè)艙位之間的重量平衡(第一種理解方式)前后艙與中艙的比例平衡11222y|.3000y2000y450yy22000015450y3000 223223y450y1500y3000y45015. 0|30001500yy|前后艙位比例平衡113113y200y1500y2000y20010. 0|20001500yy|最后需要注意的是貨物是按件數(shù)計(jì)

4、算，為整數(shù)變量。上面的三個(gè)約束如果是第二種理解，為前后艙與中艙的比例平衡前后艙位比例平衡15.0|30002000|21yy15. 0|30001500|23yy10. 0|2000y1500y|13900000y2000y300090000021575000y1500y300057500023300000y1000y2000300000133、建立數(shù)學(xué)模型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這個(gè)問題，要求所有的決策變量取整數(shù)，故稱為整數(shù)規(guī)劃。15.0|30002000|21yy15. 0|30001500|23yy10. 0|20001500|13yy 當(dāng)整數(shù)規(guī)劃規(guī)模很大(決策變量很多)時(shí)，求解變得十分困難，一般求對(duì)應(yīng)的實(shí)數(shù)規(guī)劃模型，然后直接將最優(yōu)解整數(shù)化即可。但是，規(guī)模不大時(shí)，一般采用分枝定界法求解整數(shù)規(guī)劃或者包含整數(shù)變量的混合規(guī)劃。兩種理解方式計(jì)算結(jié)果一樣附件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層高，辦公室都設(shè)置在711層上，假設(shè)辦公人員都乘電梯上樓，每層有60人辦公，現(xiàn)有3臺(tái)電梯A,B,C可利用，每層樓之間電梯的運(yùn)行時(shí)間是3秒，最低層樓（一層）的停留時(shí)

10、間為20秒，其它各層的停留時(shí)間是10秒。每臺(tái)電梯的最大容量為10人，在上班前電梯只在711層停靠。為了簡(jiǎn)單起見，假設(shè)早晨8：00以前辦公人員已經(jīng)陸續(xù)到達(dá)1層，能保證每部電梯在底層的停留時(shí)間（等待20秒）達(dá)到電梯的最大容量，電梯在各層的相應(yīng)停留時(shí)間內(nèi)辦公人員能夠順利出入電梯；當(dāng)無人使用電梯時(shí)，電梯在1樓待命，請(qǐng)問：（1）把這些人都送到相應(yīng)的辦公樓層，需要多少時(shí)間？（2）怎樣調(diào)度電梯，能使辦公人員到達(dá)相應(yīng)的樓層所需總時(shí)間 盡可能最少？（3）請(qǐng)給出具體的電梯運(yùn)行方案。2、電梯問題、電梯問題模型假設(shè)模型假設(shè)：（1）8：00前所有員工陸續(xù)到達(dá)候梯廳；（2）所有員工均坐電梯到達(dá)目標(biāo)層；（3）3臺(tái)電梯同時(shí)運(yùn)

11、行；（4）早上上班時(shí)間，電梯只在711層樓停靠，且?？康?0秒 內(nèi)這層樓的有關(guān)人員均可以全部出電梯；（5）到達(dá)目標(biāo)層的5層樓的員工均勻到達(dá)；（6）每臺(tái)電梯的計(jì)算時(shí)間為從開始運(yùn)行，到最后停留在第一 層樓。一、 回答問題1 考慮一種理想狀態(tài)：每部電梯每次只運(yùn)輸?shù)竭_(dá)同一層樓的員工，那么，每層樓60人，電梯按照最大載重運(yùn)輸，則需要6個(gè)來回。每次所花費(fèi)時(shí)間為第七樓：電梯運(yùn)行時(shí)間: (3+3)x6x6=216秒電梯停留時(shí)間: (10+20)x6=180秒合計(jì)： 396秒第八樓(3+3)x7x6=252秒(10+20)x6=180秒432秒電梯運(yùn)行時(shí)間: (3+3)x8x6=288秒電梯停留時(shí)間: (10+

12、20)x6=180秒合計(jì)： 468秒第九樓第十樓(3+3)x9x6=324秒(10+20)x6=180秒504秒第十一樓：電梯運(yùn)行時(shí)間: (3+3)x10 x6=360秒電梯停留時(shí)間: (10+20)x6=180秒合計(jì)： 540秒 有3臺(tái)電梯，假設(shè)A電梯運(yùn)送7，10樓層，B電梯運(yùn)送8，9樓層，C電梯只運(yùn)送11樓層，那么最晚900秒可以運(yùn)送完畢！但是，考慮到C電梯比A,B電梯早完工360秒，可以讓A電梯在減少兩次7層樓的運(yùn)送，減少132秒；B電梯減少一次8層樓的運(yùn)送，減少144秒；共減少276秒，那么將這276秒的運(yùn)送任務(wù)加在C電梯，則C電梯運(yùn)送完畢時(shí)間為540+276=816秒；A電梯運(yùn)送完畢

13、時(shí)間為768秒；B電梯運(yùn)送完畢時(shí)間為756秒；三臺(tái)電梯完工時(shí)間差距都小于任何樓層的一次運(yùn)送的調(diào)配，故將這300名工作人員運(yùn)送完畢，需要816秒。二、回答問題21、分析、分析：顯然，電梯每次混合運(yùn)輸各層樓的員工比每次只運(yùn)輸一層樓的員工需要多停幾次，即所花費(fèi)的時(shí)間多。所以運(yùn)輸最佳方案一定在后面的方案中產(chǎn)生。2、變量設(shè)置、變量設(shè)置：xij: 第i電梯運(yùn)送的j層樓員工的次數(shù)；i=1,2,3表示A,B,C電梯, j=1,2,3,4,5表示第7,8,9,10,11層樓，其中，xij取整數(shù)，且 介于06。ti : 表示第i電梯的運(yùn)行時(shí)間；i=1,2,3；w: 表示3臺(tái)電梯的最長(zhǎng)運(yùn)行時(shí)間。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取非負(fù)整數(shù)3 ,2, 1i12x61jij4、計(jì)算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);計(jì)算結(jié)果 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