運籌學課件(簡化)

第一部分運籌學

一、什么是運籌學？

實例：一公司有：

三個工廠：A、B、Co各工廠分別有140噸、120噸、50噸產(chǎn)品待運；

三個倉庫：甲、乙、丙。甲庫可存貨60噸，乙?guī)炜纱尕?00噸，丙庫可存貨150噸;

任一工廠到倉庫的路程如表：

工廠

倉庫、逢BC

甲9126

乙613.54.5

丙1.539

問：如何調(diào)運貨物才能使總的噸公里最??？

直觀思路：1、距離最短A一丙。（140噸）；2,B-丙。（10噸）；依此類推。

可得調(diào)運方案：

^工廠存貨量

ABC

倉庫

甲6060

乙5050100

丙14010150

供應(yīng)量14012050總和=310

總噸公里數(shù)=140*1.5+60*12+50*13.5+10*3+50*4.5=I860,

最佳方案:

工廠存貨量

ABC

倉庫

甲105060

乙100100

丙30120150

供應(yīng)量14012050總和=310

總噸公里數(shù)=1395。

對該問題如果利用數(shù)學符號（即建立數(shù)學模型）來表示，可如下討論：

設(shè)工廠A向倉庫甲、乙、丙的調(diào)運噸數(shù)分別為X”、/2、xl3,工廠B向倉庫甲、乙、

丙的調(diào)運噸數(shù)分別為X2I、/2、乙3,工廠C向倉庫甲、乙、丙的調(diào)運噸數(shù)分別為與1、與2、

七3,則調(diào)運貨物的總噸公里數(shù)（相當于運輸費用）為

z=9X]]+6匹2+L5XQ+12X2I+13.5X22+3X33+6X3I+4.5x32+9x33

現(xiàn)在需要求該函數(shù)的最小值，而限制條件為:

+x12+x13=140

x2]+x22+尤23=120

知+》32+X33=50

X”+x2i+》3i=60

占2+X22+*32=10°

*3+X23+》33=150

、X]”$2，X”，X21，X22，％23，X31，X32，X33—°

運籌學：以系統(tǒng)為研究對象，把系統(tǒng)的功能和特點用模型表示，通過對模型的定量分

析，從總體上尋求最優(yōu)策略，為決策和揭露新問題提供數(shù)量根據(jù)，并以研究結(jié)果的應(yīng)用為H

的，保證系統(tǒng)高效運行。

運籌學建立模型的最終目的是實現(xiàn)系統(tǒng)的最優(yōu)化，幫助管理者作出正確的決策，使系統(tǒng)

正常有效地運行。這里的最優(yōu)化是指在一定條件下求最優(yōu)解（可以是求最大值，也可以是求

最小值）。

運籌學研究系統(tǒng)的基本方法由以下5個階段構(gòu)成：

第一階段：觀察所要研究的系統(tǒng)，確定存在的問題、影響問題的因素、約束、假設(shè)以及

準備優(yōu)化的目標。

第二階段：對系統(tǒng)進行描述一一建立模型。

模型的復(fù)雜程度視具體問題而定，過份簡單則不能準確反映系統(tǒng)的實質(zhì)，過份復(fù)雜則造

成求解的困難。模型是所研究系統(tǒng)的一個理想（簡化的）表達形式。一個現(xiàn)實系統(tǒng)的性質(zhì)可

能受到許多因素的影響，但是一般只有一小部分因素真正支配著系統(tǒng)的特性。建模時應(yīng)該抓

住這些支配系統(tǒng)的因素，從現(xiàn)實系統(tǒng)中抽象出一個“假想的現(xiàn)實系統(tǒng)”，然后把這些因素之

間的關(guān)系確定下來，并簡化成一個適合于分析的形式，這種形式就是模型。

第三階段：根據(jù)實際條件對模型進行檢驗。

模型一旦確定，就應(yīng)該根據(jù)實際條件對模型的正確性、可靠性進行分析檢驗。一般可按

照下述三種情況之一處理：（1）給出有關(guān)方程的統(tǒng)一的精確解法；（2）如果沒有統(tǒng)一解法，

則可以代入具體數(shù)據(jù)進行測算，分析測算結(jié)果是否和實際情況相符；（3）如果該模型不能用

任何正規(guī)的數(shù)學方法處理，則可以用類比方法進行模擬處理。

第四階段：分析模型。按優(yōu)化目標的要求選取最優(yōu)解，即在模型規(guī)定的約束條件下求出

符合目標函數(shù)要求的最優(yōu)條件組合。

這一階段還需要檢驗在這些約束條件下最優(yōu)解的敏感程度，即弄清楚當約束條件之一稍

有變化時最優(yōu)解會不會改變。經(jīng)過檢驗，就可以知道最優(yōu)解對各個約束條件的依賴程度。

第五階段：貫徹執(zhí)行.

二、規(guī)劃問題的幾個基本概念：

決策變量：規(guī)劃問題需要求解的一組變量，這組變量的每一組定值就對應(yīng)規(guī)劃問題的

一個具體實施方案。如上例中的/;

目標函數(shù)：規(guī)劃問題一定有一個要求目標，并且這個要求目標可以表示為決策變量的

函數(shù)，問題的解決歸結(jié)為尋求一組決策變量的值，使目標函數(shù)實現(xiàn)最大或最?。蝗缟侠械?/p>

函數(shù)z；

約束條件：每一個規(guī)劃問題中，決策變量都要滿足一定的約束條件，這些條件可用包

含決策變量的等式或不等式表示；

可行域：由約束條件所確定的決策變量的集合，可行域中的每一組決策變量的取值稱

為可行解，如上例中的第一個調(diào)運方案；

最優(yōu)解：使目標函數(shù)達到最值的可行解，如上例中的最佳方案。

分類：線性規(guī)劃和非線性規(guī)劃

單目標規(guī)劃和多目標規(guī)劃

注意：

1、規(guī)劃問題類似于高等數(shù)學中的多元函數(shù)的最值問題，如：

例：求函數(shù)z=，+3xy+6)，的最值，其中x+yW10,x+3y<l,x20,yN0

決策變量：x,y

目標函數(shù)：z=x2+3xy+6y

約束條件：x+y<10,x+3y<l,x>O,y>0

Y

可行域：由不等式x+y<10,-+y<8,x>0,y>0所確定的平面區(qū)域

顯然，可行域中的任何一個點(x,y),都滿足約束條件，都是可行解，而要求的最值點

應(yīng)該是可行域中的最優(yōu)解。

2、優(yōu)化問題中目標函數(shù)和決策變量必不可少，約束條件對于實際問題一般情況下也一

定存在，但是在利用軟件求解時，沒有目標函數(shù)也可以給出結(jié)果，但是這時的結(jié)果一般只是

一個可行解，并不是最優(yōu)解。

三、線性規(guī)劃：

1、線性規(guī)劃的特征：目標函數(shù)和約束條件都是決策變量的線性函數(shù)。

2、一般形式：

max(min)z=gc/,

j=i

Z%尤j<（二,2）2i=1,2,…，m

j=i

xj>0j-1,2,?-?,??

注意：1>規(guī)劃問題的理論求解方法很多，但是這里我們將不考慮具體理論方法，只需

要掌握軟件求解即可。

2>實際解決問題時，對于規(guī)劃問題一定要對目標函數(shù)，以及每一個約束條件給于詳細

的解釋，不要不加解釋只是純粹的羅列公式。

例1資源最優(yōu)利用問題

某廠生產(chǎn)甲、乙兩種產(chǎn)品，需要煤、電力、水泥三種資源。生產(chǎn)每種產(chǎn)品Ikt需要各種

資源的數(shù)量、各種資源的限量以及生產(chǎn)每種產(chǎn)品（kt）的利潤（千元）如表所示。問在這種

條件下，應(yīng)該安排生產(chǎn)甲、乙產(chǎn)品各多少，才能使該廠獲得最大利潤？

\產(chǎn)品

單位消耗\

甲乙資源限量

煤218

電力127

水泥039

產(chǎn)品利潤45

解：（1）問題中待確定的變量一一決策變量：甲、乙兩種產(chǎn)品的生產(chǎn)量七，與

（2）決策變量所受的約束。問題中受到限制的是煤、電力、水泥的數(shù)量。于是有：

煤的總需求量不能超過供應(yīng)量：2.YI+X2<8

電力的總需求量不能超過供應(yīng)量：士+2X247

水泥的總需求量不能超過供應(yīng)量：3^49

此外，甲、乙兩種產(chǎn)品的生產(chǎn)量應(yīng)該取非負值：X,>0,x2>0

（3）建立目標函數(shù)。在三種資源供應(yīng)量的限制下，合理安排兩種產(chǎn)品的產(chǎn)量，使得總

利潤

z=4*+5X2

達到最大。

（4）資源最優(yōu)利用問題的數(shù)學模型：求七，X2的值，使

Z=4出|+5X2

達到最大，并滿足：

2X1+x2<8

x,+2X2<7

3X2<9

Xf,x2>0

例2物資調(diào)運問題

設(shè)有兩個倉庫ApA?,分別儲存水泥23t和27%有三個工地B『B2，B3各需水泥17318t

和15t（總存貨量等于總需求量）。己知各倉庫到各工地的單位運費如表所示，問應(yīng)如何調(diào)運，

使運費最??？

\工地

運費\

B,B2B3

A.3113

192

A2

數(shù)學模型：求變量與（從倉庫A,運往工地號的水泥數(shù)量）的值，使目標函數(shù):

z=]+6X12+9X]3+6X21+1lx22+6x23

達到最小，并滿足：

xn+xI2+x13=23

x2]+x22+x23=27

X”+x21=17

X|2+X22=18

XI3+工23=15

與NO,/=1,2;J=1,2,3

例3生產(chǎn)安排問題

某車間的車工分i、n兩級，各級車工每人每天的加工能力、成品合格率及日工資數(shù)如

表所示

級別加工能力（個/人?天）成品合格率（％）工資（元/天）

I240975.6

II16095.53.6

工廠要求每天至少加工配件2400個，車工每出一個廢品，工廠要損失2元，現(xiàn)有I級

車工8人，n級車工12人，且工廠要求至少安排6個II級車工。試安排車工工作，使工廠

每天支出費用最小。

解：（1）決策變量：安排I、II兩級車工的人數(shù)為占，x2

（2）分析約束條件：

車工人數(shù)限制：%,<8,6<x2<12

每天加工的配件總數(shù)限制：240J,+160X2>2400即3x,+2x2>30

特殊約束：X,>0,乙20且為整數(shù)

（3）目標函數(shù)：這個問題的目標是使工廠每天的總費用最小。包括車工的工資和因為

出廢品而造成的損失。

每個I級車工每天的費用：工資：5.6廢品損失：2x（240x3%）共計：20

同理每個H級車工每天的總費用為：18

工廠每天的總費用為：z=20x1+18x2。

(4)數(shù)學模型：求求匹，々的值，使.

Z=20戈1+18X2

達到最大，并滿足：

X148

x2>6

x2<12

3X[+2X2>30

X1,x2>0且為整數(shù)

四、整數(shù)規(guī)劃：

1、整數(shù)規(guī)劃：決策變量只能取整數(shù)值。

整數(shù)規(guī)劃對應(yīng)的線性規(guī)劃：去掉整數(shù)規(guī)劃中的整數(shù)限制，得到的一般線性規(guī)劃。

2、常見基本模型：

(1)最優(yōu)生產(chǎn)計劃問題

一家玩具公司制造三種玩具，每?種要求不同的制造技術(shù)，高級的?種每臺需要17小

時加工裝配勞動力，8小時檢驗，利潤30元。中級的每臺需要2小時加工裝配勞動力，半

小時檢驗，利潤5元。低級的每臺需要半小時加工裝配勞動力，10分鐘檢驗，利潤0.6元。

可供利用的加工勞動力為500小時，檢驗100小時，同時，據(jù)市場預(yù)測，對高級玩具需求量

不超過10臺，中級不超過30分，低級不超過100臺。該公司應(yīng)如何安排生產(chǎn)計劃才能使利

潤最大？

(2)工廠選址問題

有〃個城市，每日需要某種物資的數(shù)量分別是4,電,…,4,先在計劃要在其中選取加個

城市，建造，〃座生產(chǎn)這種物資的工廠。假設(shè)已知若在城市/建廠，II產(chǎn)量最多為鳥，而建設(shè)

費用為人。設(shè)城市i到城市/的單位運價為0,問這加個工廠應(yīng)該設(shè)在何處，才能使得既滿

足需要又能使總費用最??？

解：設(shè)變量為=1|在城]嚴,，從城市i到城市j?運送的物資數(shù)量為％.，則可以建

[0否則

立如下數(shù)學模型：

Minz='t'tcijxij+XfJyj

1=1j=\j=\

使得：

(3)背包問題

一個背包的容積為V。現(xiàn)有〃中物品可裝，而每種物品都只能整件裝入；物品，的重量

為叼，體積為5。問如何配裝，使得既不超過背包的容積，又使裝的總重量最大？

解：設(shè)x.=P物品里裝入，則可以建立如下數(shù)學模型：

'[0否則

n

Maxz=Z（OjXj

j=i

使得：

tv；-v

＜7=1

Xj=0或Lj=1,2，…,n

（4）指派問題

設(shè)有〃項任務(wù)，恰好有〃個人可以分別完成其中一項，但由于各人能力不同，由不同的

人去完成不同的工作所耗用的時間不同，具體所耗用的時間可用如下效率矩陣。表示，問指

派那個人完成那項任務(wù)，總耗時最少？

效率矩陣：第i個人完成第，項任務(wù)所耗時與

CllC\2…C\n

C_C2IC22…C2n

%…Gm.

解：設(shè)局=P當分配第i個竺產(chǎn)j項工作時，則可以建立如下數(shù)學模型:

10否則

Mm?

足

滿

3、整數(shù)規(guī)劃的求解：

幾個結(jié)論：

1＞整數(shù)規(guī)劃無法直接求解，往往先轉(zhuǎn)化為對應(yīng)的線性規(guī)劃求解，但是對應(yīng)的線性規(guī)

劃的解一般不是整數(shù)規(guī)劃的最優(yōu)解；

2＞對求最大的整數(shù)規(guī)劃，整數(shù)規(guī)劃的最優(yōu)目標函數(shù)值不大于其對應(yīng)的線性規(guī)劃的最

優(yōu)目標函數(shù)值；

3＞對求最小的整數(shù)規(guī)劃，整數(shù)規(guī)劃的最優(yōu)目標函數(shù)值不小于其對應(yīng)的線性規(guī)劃的最

優(yōu)目標函數(shù)值；

4＞如果將線性規(guī)劃的可行域分為若干子域，則在每個子域上求得的最優(yōu)值不優(yōu)于整

個可行域上的最優(yōu)值。

求解方法：分枝定界解法步驟

Stepl:設(shè)原整數(shù)規(guī)劃為A,對應(yīng)的線性規(guī)劃為A，；

Step2:如果A，沒有可行解，則A也無可行解；

Step3:如果A，有最優(yōu)解，則進一步檢查是否符合整數(shù)條件:

符合：則該解就是A的最優(yōu)解，程序停止；

不符合：任選一個不符合整數(shù)條件的變量勺=鳥，將A分解為四，當兩個

問題：

AA

Bi：xjAbi][x.<[^]+l

Step4:分別求身,耳的最優(yōu)解；

Step5:比較尚未分解的兩個問題的最優(yōu)解，注意其中最大的一個，若該最優(yōu)值對

應(yīng)的解以符合整數(shù)條件，則該解就是A的最優(yōu)解，停止；若該最優(yōu)值對應(yīng)的解不符合

整數(shù)條件，則重復(fù)3繼續(xù)分解。

例：問題A：

maxz=3玉+2x2

2玉+3九2414

<2xl+x2<9

Xi，xNO,且為整數(shù)

解：(1)求解A對應(yīng)的線性規(guī)劃A的最優(yōu)解

xl=3.25,x2=2.5,max=14.75

(2)因為不滿足整數(shù)條件，故可以按照變量再將問題分解為

maxz3匹+2X2maxz=+2x2

X

2玉+32<142xl+3X2<14

2x+x<92%j+x<9

用：l2B2:2

xl<3x1>4

x?x2NO且為整數(shù)和/NO且為整數(shù)

(3)不考慮整數(shù)條件，求解以上兩個問題的對應(yīng)線性規(guī)劃禺，不得最優(yōu)解:

B；：%,=3,X2=8/3,maxz=14.33

B'2：X,=4,X2=l,maxz=14.00

其中B'2已經(jīng)是整數(shù)解，故不必繼續(xù)分解.但是B'2所對應(yīng)的目標函數(shù)值不一定是原問題

A的最優(yōu)解，這是因為皆還沒有得到整數(shù)解，由與所確定的原整數(shù)規(guī)劃A的最優(yōu)值的上界

是14.33,而由提所確定的最優(yōu)值為14.00,故原問題A的最優(yōu)解的目標函數(shù)值可能在14.00

和14.33之間，故仍需對用進行分解.

(4)考慮劣中非整數(shù)解/將問題分解為：

maxz=3匹+2x2maxz=3匹+2x2

X

2xl+3/<142x1+32<14

21]+x2<92x,<9

G:,%)<3。2：<王<3

x2<2x2>3

X,,X2。旦為整數(shù)

2XpX2NO且為整數(shù)

(5)不考慮整數(shù)條件,求解以上兩個問題的對應(yīng)線性規(guī)劃C：,得最優(yōu)解：

C；：X[=3,0=2,maxz=13.00

C'2：x,-2.5,x2-3,maxz=13.50

其中C；已是整數(shù)解,所以不必繼續(xù)分解.仍未得到整數(shù)解，故仍可對c2繼續(xù)分解.

比較已經(jīng)得到的整數(shù)解對應(yīng)的目標函數(shù)值以及尚未分解的目標函數(shù)值13.50,山于

益所對應(yīng)的目標函數(shù)值最大，故對繼續(xù)分解已無意義(因為。2的后繼問題所對應(yīng)的最優(yōu)

目標函數(shù)值的上界是13.50,小于14.00).所以原問題的最優(yōu)解為

X]=4,x2=1,maxz=14.00.

五、0一1規(guī)劃

0-1規(guī)劃是一種特殊的整數(shù)規(guī)劃問題，它的全部決策變量只取0或1兩個值，對它的

求解可以利用整數(shù)規(guī)劃的方法，也可以利用完全枚舉法(n個變量的可能情況為2n種)。

注意：1、在實際問題中，決策變量往往只有兩種可能或兩種狀態(tài)，如，對某個建設(shè)項

目投資或不投資，對某種貨物購進或不購進，在某地建廠或不建廠。此時可以引入0—1變

量，建立數(shù)學模型。

2、在實際的數(shù)學建模競賽題目中，往往決策變量中的幾個屬于0—1變量，而其余仍是

普通變量，這是就不能用以上方法解決。而需要具體問題具體對待。

六、非線性規(guī)劃：目標函數(shù)和約束條件中至少有一個是非線性的。

例1某城市要選定一個運輸服務(wù)中心的位置，為該城后有固定位置的m個用戶提供服

務(wù)，其中k(k<m)個用戶要求其距離不超過d.。如何確定服務(wù)中心的位置，才能使其服務(wù)時

總的費用最?。?/p>

解設(shè)服務(wù)中心的坐標是(x,y),第i個用戶的坐標已知為(ai,bj,j表示服務(wù)中心

到第i個用戶的單位運價，進一步假設(shè)運輸路線不受道路的影響，則可以得到以下非線性規(guī)

劃模型：

mingcjJ(x-aj2+(y-bj2

i=l

(x-aj2+(y-bj)2<d2i=l,…,k

例2在傳送網(wǎng)絡(luò)上，從n個電站向負載輸送能量。設(shè)p,為第i個電站產(chǎn)生的能量，

Fj(pj)為第i個電站產(chǎn)生能量Pi所需成本，i=l,…,n,L(p「p2,…,pQ為傳遞過程中所

造成的能量損耗，D為總的需求量。試確定一個最經(jīng)濟的產(chǎn)生能量方案，使需求得到滿足。

解最經(jīng)濟的產(chǎn)生能量方案需使總的成本最低，于是該問題中的決策變量為P,

i=I,---,n,則可得以下非線性規(guī)劃模型：

min^FJpJ

i=l

EP-L(P|，P2,…，Pn)=D

i=l

例3設(shè)國民經(jīng)濟由n個部門組成，分別編號為1,2,…，n。已知各部門間的直接消耗

系數(shù)矩陣為

auai2…a；

3a”,,,a*

A=(a)=

ijnxn????????????

_anlan2ann_

其中ajj表示第j部門生產(chǎn)價值為一單位的產(chǎn)品直接消耗第i部門的產(chǎn)品的價值，

uJ

l<i,j<n=第i個部門的生產(chǎn)函數(shù)為

Xj=fi(l,,k,)i=l,…,n

其中：Xj為第i個部門的總產(chǎn)品價值；

I為投入到第i個部門的資金總額;

1,為投入到第i個部門的勞力數(shù)。

問題是如何在給定總資金K與總勞力L的前提下，對每個部門進行最佳的資金及勞力投入分

配，以使國民收入最大。

解國民經(jīng)濟的各部門的總產(chǎn)品應(yīng)該由兩部分構(gòu)成，?部分產(chǎn)品用來供給其它部門供其

它部門消耗，另一部分作為該部門的最終產(chǎn)品。因而該部門的總產(chǎn)品價值也對應(yīng)的應(yīng)該由兩

部分構(gòu)成。國民收入應(yīng)該指國民經(jīng)濟的各個組成部門生產(chǎn)的最終產(chǎn)品的總價值之和。對每個

部門而言，最終產(chǎn)品總價值可以通過總產(chǎn)品價值減去其它部門消耗該部門的產(chǎn)品價值求得。

于是可設(shè)第i個部門的最終產(chǎn)品價值為丫廠則有

xi=Eaijxj+yii=L…,n

j=i

以矩陣形式表示為

X=AX+Y,即（I-A）X=Y

其中I為n階單位矩陣，X=（x-x2,…，x“）T,Y=（力廣2,…，yj，于是可得如下的

非線性規(guī)劃模型：

max^yj

i=l

（I-A）X=Y

Xi=fi（L，kj）i=l,…,n

與

WK

Xj>0,Yj>0,lj>0,kj>0i=n

第二部分賽題選講

鋼管訂購和運輸

要鋪設(shè)一條a…fAs的輸送天然氣的主管道，如圖一所示（見下頁）。經(jīng)

篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有S1,S2,…s,。圖中粗線表示鐵路，單細線表示公

路，雙細線表示要鋪設(shè)的管道（假設(shè)沿管道或者原來有公路，或者建有施工公路），圓圈表示

火車站，每段鐵路、公路和管道旁的阿拉伯數(shù)字表示里程（單位km）。

為方便計，1km主管道鋼管稱為1單位鋼管。

一個鋼廠如果承擔制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠S,在指定期限內(nèi)能

生產(chǎn)該鋼管的最大數(shù)量為>個單位，鋼管出廠銷價1單位鋼管為p,萬元，如下表：

i1234567

Si80080010002000200020003000

Pi160155155160155150160

1單位鋼管的鐵路運價如下表:

里程（km）W300301?350351?400401?450451?500

運價（萬元）2023262932

里程（km）501?600601?700701?800801?900901?1000

運價（萬元）3744505560

1000km以上每增加1至100km運價增加5萬元。

公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。

鋼管可由鐵路、公路運往鋪設(shè)地點（不只是運到點A"/!?，…，45,而是管道全線）。

（1）請制定一個主管道鋼管的訂購和運輸計劃，使總費用最小（給出總費用）。

（2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大,

哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)

果。

（3）如果要鋪設(shè)的管道不是一條線，而是個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，

請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。

29030

'SI

S4

16(1

S332020

16120

5269070i

30'

69070

1200170S6<415

110

720500

52OJ88、62

420414

462

202S510'

70

1100SI

4210220

20,A12

480411

1953

31前。。

30(

1150,10A8

5

600'

10

45i194205

80A6

45圖一

75i彳706

244

3

104301

A\

41

鋼管購運和管道鋪設(shè)方案一

摘要：本文解決的是一個鋼管購運和管道鋪設(shè)方案設(shè)計問題，目的是使總費用最

小。首先利用動態(tài)規(guī)劃方法求解所有鋼廠到各管道節(jié)點的最小運費表，并通過分

析得出從管道兩邊節(jié)點向中間鋪路的方法可以減少鋪設(shè)費用，以所有鋼廠到各管

道節(jié)點并向不同方向鋪設(shè)的鋼管數(shù)量為變量，導出總費用的表達式，把問題化為

以總費用為目標函數(shù)的非線形規(guī)劃，用Matlab對此進行求解。然后通過鋼廠鋼

管銷價和產(chǎn)量上限的微小變化及在新的條件下的求解，分析對總費用和購運計劃

的影響。最后把模型推廣到樹形管道，通過變換把它化為多條線形管道，用同樣

方法求解。由于計算中變量個數(shù)的增加使計算復(fù)雜度提高，我們提供了一些優(yōu)化

策略。在本文的末尾，我們討論了模型的優(yōu)缺點和實際應(yīng)用中的改進方向。

本文利用以上算法較好的解決了問題，得到了問題的最優(yōu)解。對于問題一,

解得最小總費用為127.86億元，購運和鋪設(shè)方案見表二。對于問題二，分析得

出S6廠的鋼管價格變化對總費用影響最大，S1廠的產(chǎn)量上限變化對總費用影響

最大。對于問題三，解得最小總費用為140.66億元，購運和鋪設(shè)方案見表六。

問題重述

要鋪設(shè)一條線形的天然氣的運輸管道，鋼管由7個鋼廠提供，可以由公路、

鐵路運往鋪設(shè)地點。鋼廠提供的鋼管量不能超過它的產(chǎn)量上限，且或者大于500

或者為0。公路、鐵路運輸費用的計算公式已經(jīng)給定。在此條件下求出定購運輸

計劃，使總費用最小。并分析鋼廠鋼管銷價和產(chǎn)量上限變化對購運計劃和總費用

的影響。以及推廣模型以解決鋪設(shè)樹形管道這種更一般的情形。

模型的假設(shè)

1.公路運輸費用為1單位鋼管每公里0.1萬元，不足整公里按整公里計算。

2.購買和運輸鋼管都是整單位（即為整公里）。

3.沿管道或者原來有公路或者建有施工公路。

4.一個鋼廠如果承擔制造鋼管，至少要生產(chǎn)500個單位。

5.鋼管可由鐵路、公路運往鋪設(shè)地點。

6.把“鋼廠鋼管的銷價和產(chǎn)量上限變化對總費用和運購計劃的影響”理解為在

最優(yōu)解附近的微小變化對總費用和運購計劃的影響。銷價最小變化是1萬元,

產(chǎn)量上限的最小變化是1個單位。

三.問題分析

鋪設(shè)一個天然氣運輸管道（線形或樹形），總費用包括購買鋼管的費用，運

費和鋪設(shè)時的運費。購買鋼管的費用由鋼廠的鋼管銷價和向這個廠訂購的鋼管數(shù)

量決定。運費由鋼廠向鋪設(shè)起始點運輸?shù)匿摴軘?shù)量和它到此起始點的運輸?shù)缆窙Q

定（由于通過鐵路和公路運輸，所以并不僅僅由路程決定）。一般情況下鐵路運

輸比公路運輸要節(jié)省費用（只有在200公里以內(nèi)，公路運輸比鐵路運輸要節(jié)?。?/p>

對于鋪設(shè)費用，在假設(shè)一的前提下，由一頭出發(fā)，鋪設(shè)x公里的費用的計算是：

0.1*[x+（x-l）+（x-2）+...+2+l]=0.05*x*（x+l）,通過比較可以發(fā)現(xiàn):鋪設(shè)一段管道，

從兩頭往中間鋪比從一端向另一端鋪要節(jié)省費用。再由假設(shè)三，鋪設(shè)時沿管道走

的是公路，所以當管道段較長時，兩頭鋪所節(jié)省的費用是比較可觀的。比如問題

一中，所有管道段都從一頭鋪的鋪設(shè)總費用為：0.05Z[DyX（Dx.y+l）]=12.29

億元。而在最優(yōu)的鋪設(shè)方法下（即兩頭向中間鋪的路程相同），鋪設(shè)總費用為：

0.05^2x[^x（^+l）]=6.16億元，最優(yōu)解中的鋪設(shè)費用應(yīng)在這兩者之間。

因為鋪設(shè)費用的表達式是二次式，所以求解總費用是一個非線性規(guī)劃問題。

四.符號說明

Pi：鋼廠S的鋼管銷售價格

si：指定期限內(nèi)鋼廠Si能生產(chǎn)鋼管的最大數(shù)量

Lij：從Si運到Aj,且向左邊鋪路的鋼管數(shù)量

Ri」：從S運到Aj,且向右邊鋪路的鋼管數(shù)量

Ti：從Si運出的鋼管總量，要求Ti<=Si，且R=0或Ti>=500

Fi,j：一單位鋼管從Si運到Aj的最少費用

Dx.y：相鄰兩點Ax.Ay之間的路程

G：購買鋼管的費用

C2：把鋼管運送到所有Aj的總運費

C3：從冉開始鋪設(shè)鋼管過程中的公路運費

C：總費用，C=Ci+c2+c3

ki：S廠鋼管價格對總費用的邊際影響

mi：S廠鋼管產(chǎn)量上限對總費用的邊際影響

五.模型的建立與求解

（-）問題--的訂購和運輸計劃求解：

1.模型一的建立：

由定義得：

15

從Si運出的鋼管總量：Ti=X（L,」+Rij）

7

購買鋼管的費用：C1=^（Ti*Pi）

157

把鋼管運送到所有Aj的總運費：C2=，￡心」+九）*凡]

j=\i=\

77

從Aj向左鋪設(shè)的鋼管量Lj=￡L,j；向右鋪設(shè)的鋼管量&=￡氏3

i=li=l

15

鋪設(shè)鋼管過程中的公路運費：C3=0.1*￡[LJ*（Lj+l）/2+Rj*（均+1）/2]

j=l

目標函數(shù)（總費用）為：

nnn（Ci+C2+C3）

s.t.Tj<Si，且Ti=O或Ti>500（i=l,2,...7）

對相鄰兩點Ax,Ay有Rx+Ly=Dx.y（x,y=l,2,...15）

問題即轉(zhuǎn)化為對以Lj,Ri,j為變量的非線形規(guī)劃的求解。

2.先求出從S運送單位鋼管到Aj的最少費用E,j,這是一個類似求最短軌道的

動態(tài)規(guī)劃問題，可以仿照Dijkstra算法，特殊的是邊的權(quán)以路程表示，而階

段指標是運費。求解結(jié)果列表如下：

表一：最小運費表（問題一）單位（萬元）

SISS3SSS

245s67

Ai170.7215.7230.7260.7255.7265.7275.7

160.3205.3220.3250.3245.3255.3265.3

A2

140.2190.2200.2235.2225.2235.2245.2

A3

A498.6171.6181.6216.6206.6216.6226.6

A538111121156146156166

、620.595.5105.5140.5130.5140.5150.5

3.18696131121131141

A7

As21.271.286.2116.2111.2121.2131.2

A964.2114.248.284.279.284.299.2

AJO921428262576277

An961468651335166

A121061569661514556

A13121.2171.2111.276.271.226.238.2

A1412817811883731126

A151421921329787282

3.用Matlab編程序求解目標函數(shù)，得到最優(yōu)解為127.54億元，此時從Si,S?

S7運出的鋼管數(shù)量為：

T,=800,T2=800,T3=1000,T4=0,T5=1336,T6=990,T7=245

但是由于T7=245<500,而題目中要求“一個鋼廠如果承擔制造鋼管，至少

需要生產(chǎn)500個單位”，所以此解不符合條件。

4.再分兩部分進行第二步求解，一是在增加約束T7=0的情況下，二是在增加約

束T7>=500的情況下分別計算。對于第一種情況，在實際計算中我們發(fā)現(xiàn)，

只要把S7銷售鋼管的價格P7變的很高（比如1000萬元），那么在最后的結(jié)果

中肯定不會出現(xiàn)有S7提供鋼管的情況，這樣求得的結(jié)果與增加約束17=0相

同。由Matlab解得總費用為127.86億元。對于第二種情況，求得的結(jié)果是

127.97億元。并且在兩種情況下所有的Ti都滿足條件，故不需要再繼續(xù)求解。

最優(yōu)解是第一種情況，即當T7=。時。

補充：如果在計算中，第二步求解得到的解仍然有Ti不滿足條件，再對此Ti分幾部分

進行下一步求解，依次類推。

最優(yōu)解對應(yīng)的鋼管購運計劃如下表：

表二：鋼管購運和鋪設(shè)計劃（問題一）

SiSSS

23s45s6s7

左右左右左右左右左右左右左右

Ai00000000000000

75

A2001040000000000

A3002260000002820000

A4370950336000000000

A52980000000308100000

As18415000000000000

19076000000000000

A7

As001251750000000000

A9000050515900000000

A1000000000321300000

An000000002701450000

A120000000000751100

A13000000000019913400

A14000000000028633500

A150000000000165000

Ti80080010000136612050

說明：

1）表中表示從S,訂購并運輸?shù)匠龅匿摴軘?shù)量，以及這些鋼管向左和向右鋪設(shè)的數(shù)量。

2）雖然表中有從Si運到燈的鋼管向左和向右的分配量，實際上只要所有的鋼管運到Aj

后，向左和向右的鋪設(shè)量與鋼管的來源無關(guān)。

在上表的方案下，第一問的總費用最小為127.86億元。

鋼管購運和管道鋪設(shè)方案二

1、符號說明：

5,.：鋼廠S,在指定期限內(nèi)鋼管的最大產(chǎn)量；

%：到A,之間鋪設(shè)管道的里程數(shù)；

C,：單位鋼管從鋼廠S,運到4所需最小訂購和運輸費用；

X”鋼廠S,是否承擔制造這種鋼管；

為：鋼廠S,運到4點的鋼管數(shù)量，不含路過&的部分；

Z,：運到A,的所有鋼管沿4A*鋪設(shè)的數(shù)量；

Z,：運到勺的所有鋼管沿A,--A,鋪設(shè)的數(shù)量；

"(A,)：樹中4的度數(shù)；

d-(A《：樹中A,的入度數(shù)；

1+(&)：樹中&的出度數(shù)；

〃：單位鋼管1公里的公路運輸費用。

2、基本假設(shè)：

(1)假設(shè)運到A.的鋼管，只能在4T和AJM之間包含4的某個