2自來水輸送與貨機裝運

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

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

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

4、個區(qū)(j = 1, 2, 3, 4)的供水量. 設(shè)水庫i向j區(qū)的日供水量為xij，由于C水庫與丁區(qū)之間沒有輸水管道，即x34 = 0，因此只有11個決策變量. 由上分析，問題的目標可以從獲利最多轉(zhuǎn)化為引水管理費最少，于是有Min Z = 160x11 + 130x12 + 220x13 + 170x14 + 140x21 + 130x22 + 190X23 + 150x24 + 190x31 + 200x32 + 230x33 (1) 約束條件有兩類: 一類是水庫的供應(yīng)量限制，另一類是各區(qū)的需求量限制. 由于供水量總能賣出并獲利，水庫的供應(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)成一個線性規(guī)劃模型(當然要加上xij的非負約束). 輸入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為各變量下界約束的影子價格. 例如對X11，若其下界從0提高到e，則目標Z的最優(yōu)值會提高30e，其“價格”為30e/e = 30.) 送水方案為: A水庫向乙區(qū)供水50千噸，B水庫向乙、丁區(qū)分別供水50, 10 千噸，C水庫向甲、丙分別供水40, 10千噸. 引水管理費為24400元. 利潤為 144000 - 72000 - 24400 = 47600元 討論 如果A, B, C三個水庫每天的最大供水量都提高一倍，則公司總供 水能力為320千噸，大于總需求量300千噸，水庫供水量不能全部賣出，因而不能像前面那樣，將獲

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

9、(4)的右端增加一倍的同時，應(yīng)將等號改成小于、等于號，即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水庫向乙區(qū)供水100千噸，B水庫向甲、乙、丁區(qū)分別供水30, 40, 50千噸，C水庫向甲、丙區(qū)分別供水50，30千噸總利潤為88700元 其實，由于每個區(qū)的供水量都能完全滿足，所以上面(5)(8)每

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

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

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

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

15、x23 + 580x33 + 390x43 £ 5300 (23) 4) 三個貨艙裝入重量的平衡約束，即 (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 實際上，不妨將所得最優(yōu)解作四舍五入，結(jié)果為貨物2裝入前倉10噸、裝入后倉5噸；貨物3裝人中倉13噸、裝入后倉3噸；貨物4裝人中倉3噸最大利潤約121516元. 評注 初步看來，本例與運輸問題類似，似乎可以把4種貨物看成4個供應(yīng)點，3個貨艙看成3個需求點(或者反過來，把貨艙看成供應(yīng)點，貨物看成需求點). 但是，這里對供需量的限制包括兩個方

17、面：重量限制和空間限制，且有裝載均勻要求. 因此它只能看成是運輸問題的一種變形和擴展.附例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)說明： 線性規(guī)劃為min fval = f *x (輸入時f為行向量或列向量都行)s.t A*x £ b, Aeq*x = beq, lb £ x £ ub 設(shè)置linprog(f, A, b, Aeq, beq, lb, ub) 中參數(shù)時，若后面全空缺可不寫，中間有空缺時用代替，如linprog(f, A, b, , ,lb), linprog(f, A, b)等. 運行后，要知道結(jié)果，則x = 0.0000 50.0000 0.0000 0.0000 0.0000 50.0000 0.0000 10.0000 40.0000 0.0000 10.0000fval