第五節(jié) 線性規(guī)劃建模舉例

第五節(jié)線性規(guī)劃建模舉例線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛和最有效的一個分支，在用線性規(guī)劃方法解決實(shí)際問題時，建模是十分重要和很關(guān)鍵的一步，它是在把實(shí)際問題條理化和抽象化的基礎(chǔ)上進(jìn)行的，是一種創(chuàng)造性的思維過程，興有當(dāng)建立的模型能正確反映實(shí)際問題的條件和決策者的要求時，才能進(jìn)一步得出有意義的解答，為決策者作出正確決策提供幫助。線性規(guī)劃問題建模可按以下步驟進(jìn)行：分析實(shí)際問題，弄清需要確定的未知量，在此基礎(chǔ)上假定自變量（決策變量）。這些自變量應(yīng)彼此獨(dú)立，意義明確，且可借助它們將實(shí)際問題正確、方便地表達(dá)出來。確定有關(guān)參數(shù)的數(shù)據(jù)，包括價值系數(shù)c、約束條件右側(cè)常數(shù)b和約束j 1條件中的系數(shù)a。認(rèn)清決策者想要達(dá)到的主要目標(biāo)，據(jù)此列出目標(biāo)函數(shù)（自變量的線性函數(shù)），并決定是要極大化或極小化。分析并匯總問題的限制條件（包括明顯的和隱含的）將其與有關(guān)自變量和參數(shù)聯(lián)系起來，并逐一表達(dá)成等式或不等式約束。約束條件既不要遺漏（有些限制條件未考慮到）也不要重復(fù)。寫出完整的線性規(guī)劃數(shù)學(xué)模型，并進(jìn)一步檢驗(yàn)是否與描述的實(shí)際問題一致，如有不一致之處，則應(yīng)適當(dāng)修改模型。對復(fù)雜的實(shí)際問題，有時還需在求解時進(jìn)一步修正模型。下面在本章第一節(jié)的基礎(chǔ)上，再舉出另外一些線性規(guī)劃問題建模的例子，供讀者分析思考，從中得到啟發(fā)。例14裁料問題在某建筑工程施工中需要制作10000套鋼筋，每套鋼筋由2.9m2.1m和1.5m三種不同長度的鋼筋各一根組成，它們的直徑和材質(zhì)相同。目前在市場上采購到的同類鋼筋的長度每根均7.4m問應(yīng)購進(jìn)多么根7.4m長的鋼筋才能滿足工程的需要？解該問題最簡單的處理方法是：在每根.4m長的鋼筋上截取2.9m2.1m和1.5m的短鋼筋各一根，剩下料頭0.9m共用去10000根7.4m長的鋼筋。但這樣做常是不經(jīng)濟(jì)的，基改用套裁就會節(jié)約原材料。為此，必須分析共有多少種不同的裁法，該問題的可能裁料方案示于表1.10中。表1.10*裁得根'方案下料長度（m^^\^裁料方案編號i123456782.9211100002.1021032101.510130234料頭長度（m）0.10.30.901.10.20.81.4設(shè)以x（i=1’2，…，8）表示按第i種裁料方案下料的原材料數(shù)量，則可i得該問題的數(shù)學(xué)模型如下fminz=x+x+x+x+x+x+x+x1 2 3 4 5 6 7 8I2x+x+x+x=10000」2x1+x+3x+2x+x=10000x2x辛3x卓2x牛3x7+4x=10000x1>0,j=f,2,,8 7 8j最后算出的z=1?x就是所需使用的7.4m鋼筋原料的總數(shù)。jj=1該問題的目標(biāo)函數(shù)也可改用總料頭長度極小化。由本例的分析過程可知，這類問題的建模需列出所有裁料方案，當(dāng)方案很多時常是十分困難的。為此，需設(shè)立一些準(zhǔn)則刪除明顯不合理的方案，以減少計(jì)算工作量。例15工作人員計(jì)劃安排問題某晝夜服務(wù)的公共交通系統(tǒng)每天各時間段（每4小時為一個時間段）所需

班次時間r?nA段1n?nn所需人數(shù)16:0010:0060210：00-一-14：0070314：00-一-18：0060418：00-一-22:0050522:00-一2:002062：00-一6：0030表1.11解在本例中，每一時段上班的工作人員，既包括本時段開始上班的人，又包括上一個時段開始上班的人。為便于的值班人數(shù)如表1.11所示，這些值班人員在某一時段開始上班后要連續(xù)工作8表1.11解在本例中，每一時段上班的工作人員，既包括本時段開始上班的人，又包括上一個時段開始上班的人。為便于建模，可設(shè)x為第i個時段開i始上班的人員數(shù)，如此可得數(shù)學(xué)模型如下:'minz=x+x+x+x+x+xx+x2苴60 6x6M>70x12+x3>60x2+x>50x34+x>20x45+x>30x56>0,j=1,2,,6（僅在2（僅在2：1.9現(xiàn)給出它的一個解（如圖.9中所示，可知該系統(tǒng)有150人好夠1.9234521r60Ajr60A]1 50人「20A?,r30A節(jié)2：00這個時段多10人】x14:002040201030圖6:00Z10:0018: 22:■:OC/2■:00 630x=40x=30x=30x=40x=10x=201例16廠址選擇問題考慮A、B、C三地，每地都出產(chǎn)一定數(shù)量的原料，也消耗一定數(shù)量的產(chǎn)

品（見表1.12）。已知制成每噸產(chǎn)品需噸原料，各地之間的距離為：A—B:150kmA—C：100kmB—C：200km假定每萬噸原料運(yùn)輸1km的運(yùn)價是5000元，每萬噸產(chǎn)品運(yùn)輸1km的運(yùn)價是6000元。由于地區(qū)條件的差異，在不同地點(diǎn)設(shè)廠的生產(chǎn)費(fèi)用也不同。問究竟在哪些地方設(shè)廠，規(guī)模多大，才能使總費(fèi)用最?。苛硗?，由于其它條件限制，在B處建廠的規(guī)模（生產(chǎn)的產(chǎn)品數(shù)量）不超過5萬噸。表1.12解令x為由i地運(yùn)到j(luò)地的原料數(shù)量（萬噸），y為由主地運(yùn)往解令x為由i地運(yùn)到j(luò)地的原料數(shù)量（萬噸），y為由主地運(yùn)往j地的產(chǎn)ij ij品數(shù)量（萬噸），i，j=1,2，3（分別對應(yīng)A、B、C三地）。根據(jù)題意，'x+x+x<2012 13■廠x+x+x<16i21+x22+x23<2431 32 33y+y+y=7y11+y21+y31=1322 32注意，本來還可列出方程y+y+y=0，13 23 33而有y二y二y=0，從而可將該方程略去。13 23 33若設(shè)Q為第i處的設(shè)廠規(guī)模（年產(chǎn)產(chǎn)品數(shù)量，iQ=y+y2 21但因y、y和y132333萬噸）則有Q=y122非負(fù)，因+y，11 12將x、11如下：x12Q=y+y。從而得到3 31 32x+x+x=3(y+y)x11+x12+x13=3(y11+y12)x21+x22+X3=3/1+y)31 32 33 31 32和x消去，并考慮y+yW5和變量非負(fù)條件，得約束條件33 21 22地點(diǎn)年產(chǎn)原料（萬噸）年銷產(chǎn)品（萬噸）生產(chǎn)費(fèi)用（萬元萬噸）A207150B1613120C240100i+3yi2+xi?+xi廠xkx3冬20+3y-x+x+x-x<16TOC\o"1-5"\h\z21 22 12 21 23 323y+3y-x-x+x+x<24y*y *y 翌7 23 31 32y11+y21+項(xiàng)1=1312 22 32y+y<5x2E0,2,2j=1,2,3；豐j頊?zhǔn)?,i=1,2,3j=1,2j目標(biāo)函數(shù)為（包括原材料運(yùn)輸費(fèi)、產(chǎn)品運(yùn)輸費(fèi)和生產(chǎn)費(fèi)）minz=75x+75x+50x+50x+100x+100xTOC\o"1-5"\h\z12 21 13 31 23 32+90y+90y+60y+60y+150(y+y)12 21 31 32 11 12+120(y+y)+100(y+y)21 22 31 32=75x+75x+50x+50x+100x+100x12 21 13 31 23 32+150y+240y+210y+210y+160y+220y11 12 21 22 31 32某石油公司用A、B、C三種原料混合成普通汽油、高級汽油和低鉛汽油3種成品出售。3種原料的單位成本及每月最大購入如表3-1。表3-1原料單位成本（元/她）每月最大購入量（也Aa100Bb150Cc50每公斤成品售價為：普通汽油d元，高級汽油e元，低鉛汽油？元。低鉛汽油每月最多銷售50匕各種汽油規(guī)格如下：普通汽油R：A不少于20%C不多于30%高級汽油P：A不少于40%B不少于10%并不多于20%C不多于10%低鉛汽油L:B不少于30%要求建立線性規(guī)劃模型，以決定各種汽油的銷售數(shù)量來取得最大利潤。解通常，建立數(shù)學(xué)模型的第一步是確定決策變量。如果我們設(shè)x、x、x3分別為3種成品的銷售數(shù)量，那么，必須知道各種汽油的成本和售價2，以便決定c?，F(xiàn)在題目中已給出了售價，但由于各種汽油的確切配方不知道，算不出各種汽油的單位成本，因此用上面設(shè)的決策變量不能建立問題的線性規(guī)劃模型。在這個問題里，必須作出兩個決策，即每種汽油各用多少入、B、C原料以及各生產(chǎn)多少。遇到這種情況，采用雙下標(biāo)決策變量往往能順利建立模型。我們設(shè):x=j種汽油中所用的原料i(kg)，" i=A，B，C；j=R，P，L。這樣，j種汽油的生產(chǎn)量就是：（3-1）T二丈x,j=RZFJL（3-1）ji1ij例如對普通汽油：T=x+x+xRARBRCR與此相似，原料i的需要量是：D=ILx,i=A,B,C （3-2）'j=Rj例如對原料A：D=x+x+xAARAPAL目標(biāo)函數(shù)是總銷售收入減總成本的余額最大，maxz=d+e+f-a-b-cTRTPTLDADBDC將式（3-1）、3-2）代入得maxz=d（x+x+x）+e（x+x+x）+f（x+x+x）ARBRCR APBPCP ALBLCL-a(x+x+x)-b(x+x+x)-c(x+x+x)(3-3)ARAPAL BRBPBL CRCPCL根據(jù)各種原料的每月最大購入量列出第一組約束條件方程：

x+x+xW100000(3-4)ARAPALx+x+xW150000(3-5)BRBPBLx+x+xW50000(3-6)CRCPCL第二組約束條件方程是對低鉛汽油銷售量的限制:X+X+xW50000 (3-7)ALBLCL第三組約束條件方程是各種汽油規(guī)格的限制，以普通汽油規(guī)格1為例：普通汽油中原料A的重量普通汽油中原料A的重量普通汽油重量N0.2X

AR N0.2■X +xAR+X(3-8(3-8)-0.8x+0.2x+0.2xW0與此相似，普通汽油規(guī)格2aR BRCRTOC\o"1-5"\h\z-0.3x +0.3x +0.7x W0 (3-9)高級汽油規(guī)格1： CR-0.6x +0.4x +0.4x W0 (3-10高級汽油規(guī)格2： BP C'0.1x -0.9x + 0.1x W0 (3-1D-0.2x +0.8x -0.2x W0 (3-12)AP BP CP高級汽油規(guī)格3：-0.1x-0.1x+0.9xW0 (3-13)低鉛汽油規(guī)格： APBPC'0.3x-0.7x+0.3xW0 (3-14)式(3-3)至(3-14,加上^(N0,i=AB,C；j=RP,L,就是這個問j題的線性規(guī)模模型。用單純形法求出這個問題的解以后，決策人不但知道最有利的各種汽油數(shù)量，而且知道各種汽油的確切配方。例3多階段投資問題某公司有200000元可用于投資，投資方案有以下5種，每種方案的投資額不受限制。方案A：5年內(nèi)每年都可投資，在年初投資1元，2年后可收回1.2元；方案B：5年內(nèi)每年都可投資，在年初投資1元，3年后可收回1.3元；方案C：只在第1年初有一次投資機(jī)會，每投資1元，4年后可收回1.4元；方案D：只在第2年初有一次投資機(jī)會，每投資1元，4年后可收回1.7元；方案E:只在第4年初有一次投資機(jī)會，每投資元，年后可收回1.4元。此外，每年年初若將1元資金存入銀行，年末可收回1.06元。投資所得的收益及銀行利息也可用于投資。要求建立線性規(guī)劃模型，使公司在第5年末收回的資金最多。解和例2一樣，若將投資及收益情況歸納成表3-2對建立數(shù)學(xué)模型，將有幫助。表中投資方案的下標(biāo)表示投資年級。用F表示未投資完而存入銀行的金額。在第4年，因有投資方案E，所以沒有F4。此外，不考慮B4A5，B5,因這些投資收回時已過了5年的期限。表3-2中虛線的起點(diǎn)是當(dāng)年初投資的金額，虛線的終點(diǎn)是當(dāng)年初可用的金額（第1年初是20000（元），兩者必須相等。這樣，對第年至第5年初的資金情況，都可建立一個約束條件方程：第1年A+B+C+F=2000001111第2年A+B+D+F=1.06F2 2 2 2 1或A+B+D+F—1?06F=02 2 2 2 2表3-2年份（年初）12456I.2A1.3B1氣1

F……1TO6F1A…2B…F……1TO6F1A…2B…2D…2F…21.06F2A31.2A21.3B21.2A31.06FA?…4B…41.4E4F-5I1.7D1.3B1.2A31.06F第3年A+B+F—1.2A-1.06F=03 3 3 1 2第4年A+E—1.3B—1.2A—1.06F=04 4 1 2 3第5年 F5—1.4C1—1.3B2—1.2^—1.4E4=0L還有非負(fù)約束A,B.，C，D.，E.，F(xiàn).N0,jjjjjjj=1,…，5。目標(biāo)函數(shù)是第6年初（即第5年末）收回的的資金最大;maxz=1.7D+1?3B+1?2A+1?06F2 3 4 5這個問題也可以用動態(tài)規(guī)劃解決。例4城市間汽車運(yùn)輸問題現(xiàn)舉例說明建立數(shù)學(xué)模型的技巧，為不使問題太大，我們舉出下面被簡化了的例題。某汽車運(yùn)輸公司經(jīng)營A、B、C三個城市之間的貨物運(yùn)輸業(yè)務(wù)，在任兩個城市之間都有公路連通，貨運(yùn)量及每車?yán)麧櫲绫?-5和表3-6所列。到站發(fā)站\^ABC到站發(fā)站\^ABCA150250B100200C500100每周貨運(yùn)量（車）表3-5到站發(fā)站\^ABCA150200B50300C100150每年利潤（元）表3-6該公司有汽車250輛，每周每輛車最多在兩城市間單程運(yùn)行4次，由于技術(shù)上及業(yè)務(wù)上的原因，全部汽車每周末必須停在A城。汽車回空沒有利潤，也不計(jì)成本。要求建立最大利潤的線性規(guī)劃模型。解建立這個問題的數(shù)學(xué)模型，有兩種不同的思路，從而有兩種確定決策變量的方法，兩個表面看來不同的線性規(guī)劃模型。第一種方法是按照例6下料問題的方法，以采用某種方案的次數(shù)作為決策變量。第二種方法是用三下標(biāo)變量?，F(xiàn)分別敘述如下：題目中規(guī)定周初的汽車必須由A城開出，最多運(yùn)行4個單程，周末必須返回A城，所以汽車運(yùn)行路線可以有8個，設(shè)x為采用第j種行車路線的次數(shù)即j按此路線行車的汽車數(shù)，行車路線如表3-7所示。標(biāo)號（j）行車路線標(biāo)號（j）行車路線1A一B一A一C-A5A一C一A-B一A2A—B—C一A6A—C一B—A3A-B—C-B—A7A—C一B—C一A4A-B—A-B—A8A-C-A—C-A由于題止中規(guī)定空車不計(jì)成本，因此可能產(chǎn)生空車運(yùn)行，再設(shè):y=A-B間重車數(shù)，iy=A-C間重車數(shù)，y2二B-A間重車數(shù)，3y=B-C間重車數(shù)，4y=C-A間重車數(shù)，y5=C-B間重車數(shù)6目標(biāo)函數(shù)為：maxz=150y+200y+50y+300y+100y+150y。1 2 3 4 5 6第一組約束條件方程是按8種行車路線開行的汽車數(shù)等于250（因空車不計(jì)成本，所以全部開出）28x=250j

j=1第二組約束條件方程是兩地間運(yùn)行的重車數(shù)小于或等于運(yùn)量：y1^150七W2502ywiooy4W200y5W500yW10Q8第三組約束條件是兩地間的重車數(shù)小于等于空重車總數(shù):y〔Wx+x+x+2x+x，1 2 3 4 5y2Wx+x+x+x+2x，yv1」6g8□y3Wxx++++xx*+x+2xx+x+-x+2+2xx121，5326437548y有x+x+xx++4x1 25 36 74x+xy1 y+W3xxx~++2xx++<x++x2x++2x+x^++xx+2xx++xx。+2x1 12 53 64 7最后一組約束條件是非負(fù)及整數(shù)約束：xN0，x為整數(shù)，j=1,2，…，8，yjN0，yj為整數(shù)，k=1,2，…，8。kk這個線性規(guī)劃模型有14個決策變量，13個約束條件方程（不包括非負(fù)及整數(shù)約束）。若城市數(shù)增多，要列舉所有行車方案而不遺漏，費(fèi)時費(fèi)事，第三組約束條件方程也很易列錯。因此，這個模型在題目規(guī)模較大時無實(shí)用價值。如果用三下標(biāo)變量，就可克服上述缺點(diǎn)。現(xiàn)設(shè)：x=第i次從j地開往k地的空重車數(shù)：y=第i'次從j地到k地的重車數(shù)，ijk 一i=1,2,3,4；j=ABC；k=ABC根據(jù)題目所給條件，可以列出表3-8題目中規(guī)定的周初只能從A出發(fā)，周末全部返回心以及每周最多單程運(yùn)行4次，都在表3-8中確定決策變量時考慮到了。目標(biāo)函數(shù)是:

表3-8第1次第2次第3次第4次A—BAtCX1ab：3朋B―AB―C1ACAx3ACX3BAX4BAC―Ax2BCx3BCxC―Bx2CAX2cb3CAX3CB4CAmaxz=15y+15y+20y+20y +5y+5y+5y+30y1AB3AB1AC3AC2BA3BA4BA2BC30y+10y+10y+10y+15y+15y。 (3-183BC2CA3CA4CA2CB3CB第一組約束條件方程是第1,2,3次單程的重空車總數(shù)等于250輛(因空車不計(jì)成本，所以寧愿放空車也不停在原地不發(fā)，使問題簡化一些第3次單程到達(dá)A的車不再走，所以第4單程車數(shù)小于等于25Qx+x二250，(3-181AB1ACx+x+x+x二250，(3-17)2BA2BC2CA2CBx+x+x+x+x+x=250(3-183AB3AC3BA3BC3CA 3CBx+x<250(3-194BA4CA第二組約束條件方程是每個單程從某地出發(fā)之車數(shù)等于上一個單程到達(dá)該地的車數(shù)：x+x二x，(3-202BA2BC1ABx+x二x，(3-21)2CA2CB1ACx+x二x+x，(3-22)3AB3AC2BA 2CAx+x二x，(3-23)3BA3BC2CBx+x二x，(3-243CA3CB2BCx=x+x，(3-25)4BA3AB3CBx二x+x。(3-284CA3AC3BC第三組約束條件方程是每次兩地間重車數(shù)小于等于運(yùn)量:yWx, (3-27)TOC\o"1-5"\h\z\o"CurrentDocument"yW250 (3-28ACvAW10O (3-29yBAyW200 (3-30BC\o"CurrentDocument"yW500 (3-3DCA\o"CurrentDocument"yW10Q (3-32CB第四組約束條件方程是兩地間重車數(shù)等于空重車總數(shù)：y Wx +x , (3-33)AB 1AB 3ABTOC\o"1-5"\h\zy Wx +x , (3-34AC 1AC 3ACy Wx +x +x , (3-35BA 2BA 3BA 4BAy Wx +x , (3-38BC 2BC 3BCy Wx +x +x , (3-37)CA 2CA 3CA 4CAy Wx +x , (3-38CB 2CB 3CB第五組約束條件是非負(fù)和整數(shù)約束：xNO,x是整數(shù)，ijk ijktyNO,y是整數(shù)，jk jki=1,2,3,，4；j=AB,C；k=AB,Cx與y均為表3-7中所列的變量。因?為有式(3-16、3-2。和(3