第一部分運(yùn)籌學(xué)

一、什么是運(yùn)籌學(xué)？

實(shí)例：一公司有：

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

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

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

工廠

倉庫、逢BC

甲9126

乙613.54.5

丙1.539

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

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

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

^工廠存貨量

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ù)學(xué)符號（即建立數(shù)學(xué)模型）來表示，可如下討論：

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

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

七3,則調(diào)運(yùn)貨物的總噸公里數(shù)（相當(dāng)于運(yùn)輸費(fèi)用）為

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—°

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

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

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

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

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

最小值）。

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

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

準(zhǔn)備優(yōu)化的目標(biāo)。

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

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

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

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

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

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

第三階段：根據(jù)實(shí)際條件對模型進(jìn)行檢驗(yàn)。

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

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

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

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

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

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

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

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

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

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

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

一個(gè)具體實(shí)施方案。如上例中的/;

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

函數(shù)，問題的解決歸結(jié)為尋求一組決策變量的值，使目標(biāo)函數(shù)實(shí)現(xiàn)最大或最小；如上例中的

函數(shù)z；

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

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

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

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

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

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

單目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃

注意：

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

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

決策變量：x,y

目標(biāo)函數(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ū)域

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

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

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

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

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

三、線性規(guī)劃：

1、線性規(guī)劃的特征：目標(biāo)函數(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>實(shí)際解決問題時(shí)，對于規(guī)劃問題一定要對目標(biāo)函數(shù)，以及每一個(gè)約束條件給于詳細(xì)

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

例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)該取非負(fù)值：X,>0,x2>0

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

利潤

z=4*+5X2

達(dá)到最大。

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

Z=4出|+5X2

達(dá)到最大，并滿足：

2X1+x2<8

x,+2X2<7

3X2<9

Xf,x2>0

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

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

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

使運(yùn)費(fèi)最省？

\工地

運(yùn)費(fèi)\

B,B2B3

A.3113

192

A2

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

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

達(dá)到最小，并滿足：

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ù)如

表所示

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

I240975.6

II16095.53.6

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

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

每天支出費(fèi)用最小。

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

（2）分析約束條件：

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

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

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

（3）目標(biāo)函數(shù)：這個(gè)問題的目標(biāo)是使工廠每天的總費(fèi)用最小。包括車工的工資和因?yàn)?/p>

出廢品而造成的損失。

每個(gè)I級車工每天的費(fèi)用：工資：5.6廢品損失：2x（240x3%）共計(jì)：20

同理每個(gè)H級車工每天的總費(fèi)用為：18

工廠每天的總費(fèi)用為：z=20x1+18x2。

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

Z=20戈1+18X2

達(dá)到最大，并滿足：

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)計(jì)劃問題

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

時(shí)加工裝配勞動力，8小時(shí)檢驗(yàn)，利潤30元。中級的每臺需要2小時(shí)加工裝配勞動力，半

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

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

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

潤最大？

(2)工廠選址問題

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

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

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

足需要又能使總費(fèi)用最省？

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

[0否則

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

Minz='t'tcijxij+XfJyj

1=1j=\j=\

使得：

(3)背包問題

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

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

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

'[0否則

n

Maxz=Z（OjXj

j=i

使得：

tv；-v

＜7=1

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

（4）指派問題

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

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

派那個(gè)人完成那項(xiàng)任務(wù)，總耗時(shí)最少？

效率矩陣：第i個(gè)人完成第，項(xiàng)任務(wù)所耗時(shí)與

CllC\2…C\n

C_C2IC22…C2n

%…Gm.

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

10否則

Mm?

足

滿

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

幾個(gè)結(jié)論：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題：

AA

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

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

Step5:比較尚未分解的兩個(gè)問題的最優(yōu)解，注意其中最大的一個(gè)，若該最優(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)因?yàn)椴粷M足整數(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ù)條件，求解以上兩個(gè)問題的對應(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)的目標(biāo)函數(shù)值不一定是原問題

A的最優(yōu)解，這是因?yàn)榻赃€沒有得到整數(shù)解，由與所確定的原整數(shù)規(guī)劃A的最優(yōu)值的上界

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

和14.33之間，故仍需對用進(jìn)行分解.

(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ù)條件,求解以上兩個(gè)問題的對應(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)的目標(biāo)函數(shù)值以及尚未分解的目標(biāo)函數(shù)值13.50,山于

益所對應(yīng)的目標(biāo)函數(shù)值最大，故對繼續(xù)分解已無意義(因?yàn)椤?的后繼問題所對應(yīng)的最優(yōu)

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

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

五、0一1規(guī)劃

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

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

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

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

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

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

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

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

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

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

總的費(fèi)用最小？

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

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

劃模型：

mingcjJ(x-aj2+(y-bj2

i=l

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

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

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

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

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

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

min^FJpJ

i=l

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

i=l

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

系數(shù)矩陣為

auai2…a；

3a”,,,a*

A=(a)=

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

_anlan2ann_

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

uJ

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

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

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

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

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

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

配，以使國民收入最大。

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

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

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

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

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

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

第二部分賽題選講

鋼管訂購和運(yùn)輸

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

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

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

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

為方便計(jì)，1km主管道鋼管稱為1單位鋼管。

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

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

i1234567

Si80080010002000200020003000

Pi160155155160155150160

1單位鋼管的鐵路運(yùn)價(jià)如下表:

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

運(yùn)價(jià)（萬元）2023262932

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

運(yùn)價(jià)（萬元）3744505560

1000km以上每增加1至100km運(yùn)價(jià)增加5萬元。

公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）。

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

（1）請制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最小（給出總費(fèi)用）。

（2）請就（1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化對購運(yùn)計(jì)劃和總費(fèi)用影響最大,

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

果。

（3）如果要鋪設(shè)的管道不是一條線，而是個(gè)樹形圖，鐵路、公路和管道構(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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題重述

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

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

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

計(jì)劃，使總費(fèi)用最小。并分析鋼廠鋼管銷價(jià)和產(chǎn)量上限變化對購運(yùn)計(jì)劃和總費(fèi)用

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

模型的假設(shè)

1.公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元，不足整公里按整公里計(jì)算。

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

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

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

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

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

最優(yōu)解附近的微小變化對總費(fèi)用和運(yùn)購計(jì)劃的影響。銷價(jià)最小變化是1萬元,

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

三.問題分析

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

費(fèi)和鋪設(shè)時(shí)的運(yùn)費(fèi)。購買鋼管的費(fèi)用由鋼廠的鋼管銷價(jià)和向這個(gè)廠訂購的鋼管數(shù)

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

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

輸比公路運(yùn)輸要節(jié)省費(fèi)用（只有在200公里以內(nèi)，公路運(yùn)輸比鐵路運(yùn)輸要節(jié)省）。

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

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

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

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

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

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

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

因?yàn)殇佋O(shè)費(fèi)用的表達(dá)式是二次式，所以求解總費(fèi)用是一個(gè)非線性規(guī)劃問題。

四.符號說明

Pi：鋼廠S的鋼管銷售價(jià)格

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

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

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

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

Fi,j：一單位鋼管從Si運(yùn)到Aj的最少費(fèi)用

Dx.y：相鄰兩點(diǎn)Ax.Ay之間的路程

G：購買鋼管的費(fèi)用

C2：把鋼管運(yùn)送到所有Aj的總運(yùn)費(fèi)

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

C：總費(fèi)用，C=Ci+c2+c3

ki：S廠鋼管價(jià)格對總費(fèi)用的邊際影響

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

五.模型的建立與求解

（-）問題--的訂購和運(yùn)輸計(jì)劃求解：

1.模型一的建立：

由定義得：

15

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

7

購買鋼管的費(fèi)用：C1=^（Ti*Pi）

157

把鋼管運(yùn)送到所有Aj的總運(yùn)費(fèi)：C2=，￡心」+九）*凡]

j=\i=\

77

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

i=li=l

15

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

j=l

目標(biāo)函數(shù)（總費(fèi)用）為：

nnn（Ci+C2+C3）

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

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

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

2.先求出從S運(yùn)送單位鋼管到Aj的最少費(fèi)用E,j,這是一個(gè)類似求最短軌道的

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

段指標(biāo)是運(yùn)費(fèi)。求解結(jié)果列表如下：

表一：最小運(yùn)費(fèi)表（問題一）單位（萬元）

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編程序求解目標(biāo)函數(shù)，得到最優(yōu)解為127.54億元，此時(shí)從Si,S?

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

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

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

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

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

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

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

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

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

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

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

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

進(jìn)行下一步求解，依次類推。

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

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

SiSSS

23s45s6s7

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

Ai00000000000000

75

A2001040000000000

A3002260000002820000

A4370950336000000000

A52980000000308100000

As18415000000000000

19076000000000000

A7

As001251750000000000

A9000050515900000000

A1000000000321300000

An000000002701450000

A120000000000751100

A13000000000019913400

A14000000000028633500

A150000000000165000

Ti80080010000136612050

說明：

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

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

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

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

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

1、符號說明：

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

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

C,：單位鋼管從鋼廠S,運(yùn)到4所需最小訂購和運(yùn)輸費(fèi)用；

X”鋼廠S,是否承擔(dān)制造這種鋼管；

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

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

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

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

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

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

〃：單位鋼管1公里的公路運(yùn)輸費(fèi)用。

2、基本假設(shè)：

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