2自來(lái)水輸送與貨機(jī)裝運(yùn)

1、第4章 數(shù)學(xué)規(guī)劃模型4.2 自來(lái)水輸送與貨機(jī)裝運(yùn) 鋼鐵、煤炭、水電等生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或者利潤(rùn)最大? 各種類型的貨物裝箱，由于受體積、重量等的限制，如何相互搭配裝載，使獲利最高，或者裝箱數(shù)量最少? 本節(jié)將通過(guò)兩個(gè)例子討論用數(shù)學(xué)規(guī)劃模型解決這類問(wèn)題的方法. 例1 自來(lái)水輸送問(wèn)題 問(wèn)題 某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)水由A，B，C三個(gè)水庫(kù)供應(yīng). 四個(gè)區(qū)每天必須得到保證的基本生活用水量分別為30，70，10，10千噸，但由于水源緊張，三個(gè)水庫(kù)每天最多只能分別供應(yīng)50，60，50千噸自來(lái)水. 由于地理位置的差別，自來(lái)水公司從各水庫(kù)向各區(qū)送水所

2、需付出的引水管理費(fèi)不同(見(jiàn)表1，其中C水庫(kù)與丁區(qū)之間沒(méi)有輸水管道)，其他管理費(fèi)用都是450元千噸. 根據(jù)公司規(guī)定，各區(qū)用戶按照統(tǒng)一標(biāo)準(zhǔn)900元千噸收費(fèi)此外，四個(gè)區(qū)都向公司申請(qǐng)了額外用水量，分別為每天50，70，20，40千噸該公司應(yīng)如何分配供水量，才能獲利最多? 為了增加供水量，自來(lái)水公司正在考慮進(jìn)行水庫(kù)改造，使三個(gè)水庫(kù)每天的最大供水量都提高一倍，問(wèn)那時(shí)供水方案應(yīng)如何改變? 公司利潤(rùn)可增加到多少?引水管理費(fèi)(元/千噸)甲乙丙丁A160130220170B140130190150C190200230/表1 從水庫(kù)向各區(qū)送水的引水管理費(fèi) 問(wèn)題分析 分配供水量就是安排從三個(gè)水庫(kù)向四個(gè)區(qū)送水的方案，目

3、標(biāo)是獲利最多而從題目給出的數(shù)據(jù)看，A, B, C三個(gè)水庫(kù)的供水量160千噸，不超過(guò)四個(gè)區(qū)的基本生活用水量與額外用水量之和300千噸，因而總能全部賣(mài)出并獲利，于是自來(lái)水公司每天的總收入是900 ´ (50 + 60 + 50) = 144000元，與送水方案無(wú)關(guān). 同樣，公司每天的其它管理費(fèi)用450 ´ (50 + 60 + 50) = 72000元也與送水方案無(wú)關(guān). 所以，要使利潤(rùn)最大，只需使引水管理費(fèi)最小即可. 另外，送水方案自然要受三個(gè)水庫(kù)的供應(yīng)量和四個(gè)區(qū)的需求量的限制. 模型建立 很明顯，決策變量為A, B, C三個(gè)水庫(kù)(i = 1, 2, 3)分別向甲、乙、丙、丁四

4、個(gè)區(qū)(j = 1, 2, 3, 4)的供水量. 設(shè)水庫(kù)i向j區(qū)的日供水量為xij，由于C水庫(kù)與丁區(qū)之間沒(méi)有輸水管道，即x34 = 0，因此只有11個(gè)決策變量. 由上分析，問(wèn)題的目標(biāo)可以從獲利最多轉(zhuǎn)化為引水管理費(fèi)最少，于是有Min Z = 160x11 + 130x12 + 220x13 + 170x14 + 140x21 + 130x22 + 190X23 + 150x24 + 190x31 + 200x32 + 230x33 (1) 約束條件有兩類: 一類是水庫(kù)的供應(yīng)量限制，另一類是各區(qū)的需求量限制. 由于供水量總能賣(mài)出并獲利，水庫(kù)的供應(yīng)量限制可以表示為x11 + x12 + x13 + x

5、14 = 50 (2)x21 + x22 + x23 + x24 = 60 (3)x31 + x32 + x33 = 50 (4)考慮到各區(qū)的基本生活用水量與額外用水量，需求量限制可以表示為30 £ x11 + x21 + x31 £ 80 (5)70 £ x12 + x22 + x32 £ 140 (6)10 £ x13 + x23 + x33 £ 30 (7)10 £ x14 + x24 £ 50 (8) 模型求解 (1) (8)構(gòu)成一個(gè)線性規(guī)劃模型(當(dāng)然要加上x(chóng)ij的非負(fù)約束). 輸入LINDO求解，得到如下

6、輸出: OBJECTIVE FUNCTION VALUE 1) 2440000 VARIABLE VALUE REDUCED COST X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.000000 X3

7、3 10.000000 0.000000(hyd注：REDUCED COST為各變量下界約束的影子價(jià)格. 例如對(duì)X11，若其下界從0提高到e，則目標(biāo)Z的最優(yōu)值會(huì)提高30e，其“價(jià)格”為30e/e = 30.) 送水方案為: A水庫(kù)向乙區(qū)供水50千噸，B水庫(kù)向乙、丁區(qū)分別供水50, 10 千噸，C水庫(kù)向甲、丙分別供水40, 10千噸. 引水管理費(fèi)為24400元. 利潤(rùn)為 144000 - 72000 - 24400 = 47600元 討論 如果A, B, C三個(gè)水庫(kù)每天的最大供水量都提高一倍，則公司總供 水能力為320千噸，大于總需求量300千噸，水庫(kù)供水量不能全部賣(mài)出，因而不能像前面那樣，將獲

8、利最多轉(zhuǎn)化為引水管理費(fèi)最少. 此時(shí)我們首先需要計(jì)算A, B, C三個(gè)水庫(kù)分別向甲、乙、丙、丁四個(gè)區(qū)供應(yīng)每千噸水的凈利潤(rùn)，即從收入900元中減去其它管理費(fèi)450元，再減去表1中的引水管理費(fèi)，得表2凈利潤(rùn)(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/表2 從水庫(kù)向各區(qū)送水的凈利潤(rùn)于是決策目標(biāo)為Max Z = 290x11 + 320x12 + 230x13 + 280xl4 + 310x21 + 320x22+ 260x23 + 300x24 + 260x31 + 250x32 + 220x33 (9) 由于水庫(kù)供水量不能全部賣(mài)出，所以上面約束(2)

9、(4)的右端增加一倍的同時(shí)，應(yīng)將等號(hào)改成小于、等于號(hào)，即x11 + x12 + x13 + x14 £ 100 (10)x21 + x22 + x23 + x24 £ 120 (11)x31 + x32 + x33 £ 100 (12) 約束(5)(8)不變將(5)(12)構(gòu)成的線性規(guī)劃模型輸入LINDO求解得到: OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 4

10、0.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 送水方案為：A水庫(kù)向乙區(qū)供水100千噸，B水庫(kù)向甲、乙、丁區(qū)分別供水30, 40, 50千噸，C水庫(kù)向甲、丙區(qū)分別供水50，30千噸總利潤(rùn)為88700元 其實(shí)，由于每個(gè)區(qū)的供水量都能完全滿足，所以上面(5)(8)每

11、個(gè)式子左邊的約束可以去掉，右邊的小于、等于號(hào)可以改寫(xiě)成等號(hào). 作這樣的簡(jiǎn)化后得到的解沒(méi)有任何變化. 評(píng)注 本題考慮的是將某種物質(zhì)從若干供應(yīng)點(diǎn)運(yùn)往一些需求點(diǎn)，在供需量約束條件下使總費(fèi)用最小，或總利潤(rùn)最大. 這類問(wèn)題一般稱為運(yùn)輸問(wèn)題，是線性規(guī)劃應(yīng)用最廣泛的領(lǐng)域之一. 在標(biāo)準(zhǔn)的運(yùn)輸問(wèn)題中，供需量通常是平衡的，即供應(yīng)點(diǎn)的總供應(yīng)量等于需求點(diǎn)的總需求量. 本題中供需量不平衡，但這并不會(huì)引起本質(zhì)的區(qū)別，一樣可以方便地建立線性規(guī)劃模型求解. 例2 貨機(jī)裝運(yùn) 問(wèn)題 某架貨機(jī)有三個(gè)貨艙：前倉(cāng)、中倉(cāng)、后倉(cāng). 三個(gè)貨艙所能裝載的貨物的最大重量和體積都有限制，如表3所示. 并且，為了保持飛機(jī)的平衡，三個(gè)貨艙中實(shí)際裝載貨

12、物的重量必須與其最大容許重量成比例.前倉(cāng)中倉(cāng)后倉(cāng)重量限制(噸)10168體積限制(米3)680087005300表3 三個(gè)貨倉(cāng)裝載貨物的最大允許重量和體積 現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，其有關(guān)信息如表4，最后一列指裝運(yùn)后所獲得的利潤(rùn).重量(噸)空間(米3/噸)利潤(rùn)(元/噸)貨物1184803100貨物2156503800貨物3235803500貨物4123902850表4 四類裝運(yùn)貨物的信息應(yīng)如何安排裝運(yùn)，使該貨機(jī)本次飛行獲利最大? 模型假設(shè) 問(wèn)題中沒(méi)有對(duì)貨物裝運(yùn)提出其它要求，我們可作如下假設(shè)： 1) 每種貨物可以分割到任意?。?2) 每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布； 3) 多種貨

13、物可以混裝，并保證不留空隙。 模型建立 決策變量：用xij表示第i種貨物裝入第j個(gè)貨艙的重量(噸)，貨艙j = l, 2, 3分別表示前倉(cāng)、中倉(cāng)、后倉(cāng). 決策目標(biāo)是最大化總利潤(rùn)，即 Max Z = 3100(x11 + x12 + x13) + 3800(x21 + x22 + x23) + 3500(x3l + x32 + x33) + 2850(x41 + x42 + x43) (13) 約束條件包括以下4個(gè)方面： 1) 供裝載的四種貨物的總重量約束，即x11 + x12 + x13 £ 18 (14)x21 + x22 + x23 £ 15 (15)x31 + x32

14、 + x33 £ 23 (16)x41 + x42 + x43 £ 12 (17) 2) 三個(gè)貨艙的重量限制，即x11 + x21 + x31 + x41 £ 10 (18)x12 + x22 + x32 + x42 £ 16 (19)x13 + x23 + x33 + x43 £ 8 (20) 3) 三個(gè)貨艙的空間限制，即480x11 + 650x2l + 580x31 + 390x41 £ 6800 (21)480x12 + 650x22 + 580x32 + 390x42 £ 8700 (22)480x13 + 650

15、x23 + 580x33 + 390x43 £ 5300 (23) 4) 三個(gè)貨艙裝入重量的平衡約束，即 (24) 模型求解 將以上模型輸入LINDO求解，可以得到： OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.

16、000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 實(shí)際上，不妨將所得最優(yōu)解作四舍五入，結(jié)果為貨物2裝入前倉(cāng)10噸、裝入后倉(cāng)5噸；貨物3裝人中倉(cāng)13噸、裝入后倉(cāng)3噸；貨物4裝人中倉(cāng)3噸最大利潤(rùn)約121516元. 評(píng)注 初步看來(lái)，本例與運(yùn)輸問(wèn)題類似，似乎可以把4種貨物看成4個(gè)供應(yīng)點(diǎn)，3個(gè)貨艙看成3個(gè)需求點(diǎn)(或者反過(guò)來(lái)，把貨艙看成供應(yīng)點(diǎn)，貨物看成需求點(diǎn)). 但是，這里對(duì)供需量的限制包括兩個(gè)方

17、面：重量限制和空間限制，且有裝載均勻要求. 因此它只能看成是運(yùn)輸問(wèn)題的一種變形和擴(kuò)展.附例1的matlab程序：(n4_2ex01.m in Matlab/work)%4.2,p93,example 1, 2004/7/18f=160 130 220 170 140 130 190 150 190 200 230; % Both f= or f=' are OK!Aeq=1 1 1 1 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0 0 0; 0 0 0 0 0 0 0 0 1 1 1;beq=50 60 50'A=1 0 0 0 1 0 0 0 1 0 0;

18、 0 1 0 0 0 1 0 0 0 1 0; 0 0 1 0 0 0 1 0 0 0 1; 0 0 0 1 0 0 0 1 0 0 0; A=A;-A; b=80 140 30 50 -30 -70 -10 -10; lb=zeros(11,1); x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb)說(shuō)明： 線性規(guī)劃為min fval = f *x (輸入時(shí)f為行向量或列向量都行)s.t A*x £ b, Aeq*x = beq, lb £ x £ ub 設(shè)置linprog(f, A, b, Aeq, beq, lb, ub) 中參數(shù)時(shí)，若后面全空缺可不寫(xiě)，中間有空缺時(shí)用代替，如linprog(f, A, b, , ,lb), linprog(f, A, b)等. 運(yùn)行后，要知道結(jié)果，則x = 0.0000 50.0000 0.0000 0.0000 0.0000 50.0000 0.0000 10.0000 40.0000 0.0000 10.0000fval