運籌學

OperationalResearch

貴州大學理學院周國利教授

運籌學作為一門學科誕生于20世紀30年代末期，從第

二次世界大戰早期軍事部門開始的，英國和美國軍隊中的運

籌學小組諸如護航艦隊保護商船隊的編隊問題；當船隊遭受

德國潛艇攻擊時，如何使船隊損失最小的問題；反潛深水炸

彈的合理起爆深度問題；稀有資源在軍隊中的分配問題等。

研究了船只受到敵機攻擊時應采取的策略，他們提出大船應

急轉向，小船應緩慢轉向的躲避方法，該研究成果使船只的

中彈率有47%降到29%,研究了反潛深水炸彈的合理起爆深

度后，德國潛艇的被摧毀數增加到400%o第二次世界大戰

后英、美的一些部門開始著重研究戰略問題，如未來武器系

統的設計和未來戰爭的戰略，1957年美國研究北極星導彈提

前二年完成，由于運籌學在軍事上的顯著成功，很快就深入

到工業、農業、商業及政府管理部門等，并得到了迅速發展。

為了有效地應用運籌學，一般要遵循六條原則：

(1)合伙原則，尤其是同實際部門的工作者合作；

(2)催化原則，創新思想，突破常規的看法；

(3)相互滲透原則，多部門協作，彼此滲透考慮問題;

(4)獨立原則，研究問題時，獨立工作，不受干擾，

(5)寬容原則，解決問題時，思路要寬，方法要多，

(6)平衡原則，要考慮各種矛盾、關系的平衡；

應用運籌學解決問題時，關健是建立數學模型，再選擇

數學軟件進行計算，結合實際作出決策。

第一章線性規劃及對偶問題

LinearprogrammingandDualproblem

1、兩個引例

引例1.環保排污問題

設某條河流上下游有兩個化工廠，如圖所示

化工廠1、2每小時排出污水分別為2萬m3、1.4萬加3,環

保要求河水中污水含量不超過2%0,且化工廠1排入河流的

污水到化工廠2有20%自然凈化，兩個化工廠處理污水的費

用分別是1000元/萬〃?3、800元/萬加3,在滿足環保的要求

下，兩個化工廠每小時應處理多少萬加3的污水，可使得總

費用達最省？

解：（1）首先建立數學模型，

設兩個化工廠每小時分別處理污水否,看萬m,稱

為決策變量；目標是使總費用達到最省，

即求最小值MinZ=1000再+800%,稱之為目標函數，

S.t（受約束于）益（近似模型）化工廠1,再21

生公駁242nl.6-0.8玉-％W0,化工廠2,

500+2001000

再W2X2WI.4,且有：再2020（非負約束）

稱以上數學模型為線性規劃問題，記為“問題。

（2）圖解法求最優解（僅限于兩個決策變量情形）

圖中陰影部分圍成可行區域D（本例由四條直線圍

成），且標出可行區域D頂點的坐標。

目標函數等值線，令：Z=1000玉+800=>%2="|須+。

等值線的斜率左=-5/4<0,過2、4象限，并標出目標函

數值減少方向，一簇相互平行的目標函數等值線既要在可行

域D內，又要目標函數值達到最小，最優解一定可在某一頂

點處取得，（此結論可用于“問題的單純形算法）

**

本例最優處理污水化工廠1、2為：%2=0.8（萬加3）

最省費用r=MinZ=lOOQX1+800X0.8=1640元。

引例2.銀行理財的最優投資方法

某銀行有資金1億元，擬投資兩個理財項目，第一個項目

利率為10%,第二個項目利率為5%o銀行要求第一個項目

的投資額不少于3000萬，第二個項目的投資額不少于第一、

二項目投資總額的25%,如何理財可使銀行利潤最大？

解：（1）數學模型

設兩個項目的投資額分別為項,馬萬元，

目標是使銀行利潤最大，即

求MaxZ=0.1玉+0.05%

s.t須+工2至10000

X23000

當20.25（%+工2）=3工2》再

國20x220

（2）求最優解

令Z=0.ix+o.05X2+G

0.1c

X）=jVi+c=-2X]+c

-0.0511

目標函數等值線的斜率％等值線二-旦=-2（并標出目標函數值

寺但*0.05

增加方向），如圖：

**

最優投資方案：西=7500萬，%2=2500萬,

Z：=MaxZ=0.1X7500+0.05X2500=875萬元，

為”問題的最優值，即銀行的最大利潤。

2、七尸問題的一般數學模型及標準型

求Max(Min)Z=弓玉+c2x2+???+cnxn=￡c產,

j=t

再，％2…,Z是決策變量,…,g是對應的價值系數，

為目標函數

7=1

aX

S.tauX1+%2%2---^innW(二，2)4

%玉+冊2%2+3+冊"%?(=,2)bm

x

7>0,J=1,2,…〃

4也,…一為資源限制

4心”=(%),心”為投入產出矩陣，時表第/種資源的投

入對第，種產品的產出量。

若引入價值行向量c=(C],。2,…C)X"，

引入決策列向量X.xi=(再,％2,…X”)[1

資源列向量嘮尸歷，則問題的矩陣形式為：

^Max(Min)Z=CX(由矩陣乘法)

s.tZXW(=,2)6X20。

￡產問題的標準形為：

求MaxZ=CXS.tAX=bX>0。

用Exce/,Lindo,Mcz〃ab軟件包計算lP時都要化為標準形。

下面給出化標準形方法

(1)若目標函數是求跖〃Z=CX,化為求最大值，僅需

在目標函數上加一負號，即求MaxZ=-CX。

(2)若約束條件為“W”形式，可在不等式左邊加上

一個非負松弛變量%三0,可使等式成立。

(3)若約束條件為“2”形式。可在不等式左邊減去

一個非負的剩余變量弓20(或松弛變量)使等式

成立。

(4)若4W0,只需將等式或不等式兩端同乘以-1即可。

(5)若決策變量無非負約束，令3二￡一《,其中：

%；>0,xJ>0o

(6)若決策變量4W0,則令匕=一租匕三0即可。

3、LP問題的單純形法及對偶問題

☆生產的最優安排問題(綜合題型)

某工廠在一個生產期內生產甲、乙兩種產品，需4民。三

種資源，如表所示

單位甲產單位乙產資源限制

品資源數品資源數

z資源2140

3資源1240

C資源1125

單位利2030

潤

如何組織生產，可使工廠獲利最大？

(1)建立數學模型

設在該生產時期分別生產甲、乙兩種產品為玉個

單位，目標是使工廠獲利最大，即：

求MaxZ=20項+30X2

s.t2%i+/(40

x{+2X2<40

x1+x2<25

占20%20

(2)圖解法求最優生產條件

左等值線=一［＜0(左為目標函數等值線的斜率)

**

最優生產條件芯=10,%=15,

最大利潤Z*=20X10+30X15=650（單位）

(3)單純形法，先化為標準形，求最大值

即求MaxZ=20石+30+。%3+014+0%5

s.t2再+x2+x3=40

國+2X2+X4=40

玉+々+x5=25

X/20J=…5

x3,x4,x5為松弛變量

標準形約束條件4x5中的3行及后3列組成3階單位矩

陣為基矩陣03=用，對應的變量/出4戶5為基變量，

單純形表給出單純形算法：

Cj2030000

CBXBB-'bX2x3X5

0X34021100

0X4401[2]010

B為基矩陣0X52511001

%2030000

3_j_

0X.20010

22

]_j_

30X.20100

22

W_j_

0X.5001

12」2

%500-150

0X3100011-3

30X2150101-1

20X|10100—12

%000-10-10

初始基本可行解為：

%1=0,%2=O,X3=40,x4=40,x5=25,滿足約束條件，

毛，、4，、5為基變量

。產4-工儲旬為檢驗數，j=i,2,...n

Z=1

當區wo時可得最優解。

取9=Max((y/1^>0)=Max(20y30)=30=(72

=%2進基

取.=跖釁卷，第=20

=>%4出基

[2]為主元素作行初等變換，將其化為1,且1所在的列

其余元素化為Oo

（71=5>0

n再進基

八，20205、，c

d二,-p）=10

222

=>%5出基

[￡|為主元素，作迭代

<r4=0-0x1-30xl-20x（-l）=-10<0,

<r5=0-0x（-3）-30x（-l）-20x2=-10<0,

ai<0,j=1,2---5,最優解x：=10,x；=15Z*=650,

生產最優安排例中

求MaxZ=20再+30々

s.t2』+工2工40,（4資源約束）

X,+2X2<40,（3資源約束）

X）+X2<25,（C資源約束）

X]川%>0

**

最優生產條件玉=10,々=15,

最大利潤Z*二20X10+30X15=650o

單純形法的檢驗數為：0=0,。2=。，0=0,<74=-10,<75=-10,

%=。廠2>他W0得最優解（第一個考試題與它有關）。

/=1

（4）對偶問題

若生產的組織者不準備安排生產，而是將設備出租，資源

轉讓，在市場經濟的條件下，如何定價？（涉及到資產評估

問題）

假設45。三種資源轉讓的附加值，分別為凹,外，為、

1°生產一個單位的甲產品，分別用4SC三種資源為2、

1、1個單位獲利20個單位，則廠方要求

2j,+y2+y3>20,

2°生產一個單位的乙產品，分別用4民。三種資源為1、

2、1個單位獲利30個單位，則廠方要求

%+2%+%230，

3°購買方購買。三種資源，組織生產另一類產品，

則希望價格最省，即求M加印=40乂+40%+25%，

稱求MinW=40y+408+25%

S.t2乂+%+為220

%+2%+%230

%，％，%>0

是原線性規劃￡尸問題的對偶問題，記為。尸問題,

。產問題有三個決策變量，不可能用圖解法，但由于對偶的

對偶是原問題，若題目要求求。尸的解，先轉化為“問題，

**

用圖解法求最優解（^1=10,%=15,）,再用互補松弛條件求

出。尸問題的最優解（成倍放大，最優解不變，最優值要變）。

（5）影子價格對市場經濟有調節作用

影子價格是指某種資源在公司、企業中的特定價格

乜、

由%=功=（必,%,%）b2為。P問題的目標函數及多元函

dw

數求極值的必要條件，有病=%i=l,2,3,

是目標函數對第，種資源4求偏導數（其它資源為常數），表

明對第i種資源2的變化率的影子價格,，

由單純形法最終表的檢驗數行中，松弛變量恐，、4，％5對應的

檢驗數0=0,%=-10必=-10，變號即有必*=。（/資源）

區二10（6資源）其=10（。資源）

1°弘*=0表明4資源增加一個單位

從40—41,2M+%441,

25-1

2再+々=40

其它資源不變，解方程組

斗+吃=25

**

最優解=10,%2二15,

最大利潤仍為Z=20xl0+30xl5=650,

表明4資源沒有升值，按原價轉讓。

2°回=1。表明6資源增加一個單位，從40-41,

^+2X2<41,其它資源不變，解方程組卜

%]+%=25

**

最優解%二9,超二16,

最優值Z*=20X9+30X16=660,

函數值增加了10個單位，表明B資源升值，轉讓的附加

值為10個單位。

3°四=10表明C資源增加一個單位，從25f26

Y+2x—40

%+々<26,其它資源不變，解方程組?上2-

玉+W=26

**

最優解=12,々=14,

最優值Z*=20X12+30X14=660,

函數值增加了10個單位，表明C資源升值，轉讓的附加

值為10個單位。

4°若SC兩種資源同時增加一個單位，分別從40-41

fX,+2x,=41

25f26,解方程組?上2

%+%2=26

**

最優解玉=11,%2=15,

最優值Z*=20X11+30X15=670,

函數值增加了20個單位。

5°若甲乙產品每單位的利潤都為30,目標函數Z=30玉+30%

〃等值線二TVO(左為目標函數等值線的斜率)

與%+%2=25斜率相同，直線再+%2=25上點點是最優解，

如點(10,15),(15,10)都是最優解

最優值Z*=30X10+30X15=750。

公司經營決策:若某種資源的市場價格低于該公司的影子

價格，則應該購進該資源擴大再生產，

若某種資源的市場價格高于該公司的影子價格,則出售該

資源以獲得最大利潤。

(6)LP問題與問題的互補

求MinW=40M+40為+25%

S.t2yx+y2+y3>20

必+2歹2+為230

必，為，8-0

的最優解，

其對偶問題，求MaxZ=20X+30X2

s.t2xx+x2<40

x1+2X2<40

$+%2<25

國20x220

可用圖解法求最優解

**

最優解-^1=10,%2=15,

最大利潤為Z=20x10+30x15=650

設原問題的最優解分別為，則由互補松弛條件,

給出5個方程：（2必*+蘇+%-20）.%*=0

（弘*+2父+其-30）芯=0

（2%；+%；-40）.齊=0

（玉*+2］；-40）.y；=0

（X：+x；-25）?y；=0

二項乘積中一項不為0，則另一項一定取0

西=10>0i=>2y：+%+y；-20=0

石=15>00y；+2y；+y；-30=0

2%：+芯-40=2義10+15-40=-5。0

=%*=0

%；+2%；-40=10+2*15-40=0

*八

=>>o

%；+%；-25=10+15-25=0

|=>其>0

**

ky2y3=20

,--Y

**

21y2+-3=30

%*=10乃*=10

Z*=cr=（20,30）『］=20*10+30X15=650

（40）

,=y*b=（y：，K，耳）40

㈤

’40、

=(0,10,10)40=0x40+10x40+10x25=650

、25,

z*=cr==Y*b

原問題和對偶問題的目標函數值相等。(強對偶定理)

4、LP問題的一個應用：最優下料問題

某建筑工地需要制作100套鋼架，每套鋼架要用長為

2.9九2.1加,1.5m的圓鋼各一根。已知原料長7.4加，如何下料，

使用料最省？

解：下料方法很多，最簡單的想法是：在每一個原料上截取

2.9m,2.1加，1.5加的圓鋼各一根，組成一套鋼架，這樣每制

作一套鋼架，就多余一根料頭0.9加，制作100套鋼架，需要

用原料100根，剩余料頭90加，顯然不是用料最省的方法。如

何巧妙搭配，才能既滿足配套要求又使所用原料最省，這就

是所謂套裁。

方法1:下料一1根2.9根三根1.5加，用料7.4加，余料0加，玉表

示，

方法2:下料二根29%一根1.5加，用料7.3加，余料0.加,馬表

示，

方法3:下料二根2.1加二根1.5加，用料7.2%余料0.2加,￡表

示，

方法4:下料一根2.9加二根2.1加，用料7.1加,余料0.3加，人表

示，

方法5:下料一■根2.1加三根1.5加，用料6.6〃?，余料0.8加,看表

示，

建立數學模型如下：求

MinZ=0xt+0.1x2+0.2x3+0.3x4+0.8x5

s.tX]+2X2+X4=100

2X3+2尤4+x5=100

3X1+x2+2X3+3X5=100

x/0,(7=1,2,…5)且為整數

以上數學模型可用Exce/,Lindo,MK/ab軟件包計算，最

優下料方法為：X*=(30,10,0,50,0)，Z*=16,即方法1下料30

根，方法2下料10根，方法4下料50根，總共需要原料長

7.4m的圓鋼90根即可制作100套鋼架。

又若2.9加,2.1加，1.5加的圓鋼分別為129、100、72根,

組成鋼架，x：=13,x；=33,x；=50。

其他應用有配料問題、生產工藝優化問題、有配套約束

的資源優化問題、多周期動態生產計劃問題、投資問題、運

輸問題及運輸問題的擴展等。

5、幾點說明：

(1)￡尸問題最優解的判定，

￡產問題的標準形矩陣形式的約束條件=6中，對矩陣

j不妨假設機＜〃，即約束條件的個數小于決策變量的

個數，且"4)=加，稱4,〃為滿秩矩陣，即中至少有一個

m階子式不為零，不妨假設Amxn前m列組成的列向量組線性

無關，令4X"=(Bmxm,Nmx(n.m))為一分塊矩陣,r⑻=〃2,忸|W0,

（）,Xg=12,X,”）,（X）,

又^令'X"X\=XB,XN（石，…，XN—m+Xm+2,

由ZX=6n（民N）=BXB+NXN=b,二邊左乘得:

XB=B"B-'NXN，再令目標函數中的價值系數

）（，，）

Gxn=（CB，CN）,CB=（CI,C2,---,Cm,CN=Cm+lC,"+2,…C"，則

Z=G*”X,M=(g，g)(X8，xj=64+。/,丫=

}}]

CB(B-b-B-'NXN)+CNXN=CBB-b+{CN-CBB-N)XN,

由XN20,當。=品-。心一0二0時，目標函數Z取得最

大值Z*=CM",稱5v=g-為檢驗數矩陣，其坐標

m

形式為%=Cj—￡c4,j=m+l,m+2,…n,當檢驗數滿足

?=1

m

%=盯-2。&40,<=冽+1,冽+2,…及時,“問題得最優解。

f=l

(2)Z/P|可題求MaxZ=Gx"X,xiS上4x"X"xi〈九xiX”xi>0,

的對偶。尸問題求防〃%=%,也Xs.t幾4x〃〉Gx“幾,”20。

的理論性較強，對偶理論深刻揭示了原問題與對偶問題的內

在聯系，由對偶問題引伸出來的對偶解有著重要的經濟意

義，對偶理論有七個定理，在此不一一敘述，對偶解在對。

問題可作靈敏度分析，即價值系數、資源約束和投入產出矩

陣4x“=(%)心〃中投入量的變化對最優解及最優值的影響。

(3)￡產問題主要解決一個目標函數的最優化問題，但在實

際問題中往往要考慮多個目標，如設計一個新產品的工藝過

程，不僅希望利潤大，而且希望產量高、消耗低、質量好、

污染小、投入少等，由于需要同時考慮多個目標，則引入了

目標規劃，線性目標規劃的圖解法既難作而且僅限于二個決

策變量，可將原多目標規劃分解成一系列的傳統的單目標線

性規劃，并引入正、負偏差變量然后依次求解，最

后按優先級別、綜合評價決策出最優解和最優值，稱之為線

性目標規劃的序貫式算法。

（4）對于非線性規劃，由無約束問題的最優解的必要條件,

梯度v/（x）=（%三，…三）=0是一個非線性方程組，求解非常

dx{ax2dxn

困難，甚至根本無法得到解析解，因此求解非線性規劃問題

一般都采用數值計算的最速下降法、牛頓法、共機梯度法，

非線性規劃中對于有約束問題的最優性條件要用到庫恩一

塔克條件、可行方向法、近似規劃法及制約函數法，非線性

規劃的數學基礎要求很深，求解規劃問題的關健在于建立數

學模型，非線性規劃求解可用G/NO軟件完成。

第二章運輸問題（物流問題）

1、問題的提出，設某種物質有加個產地4、出……4,，其

產量分別為％，出，……冊，有〃個銷地，用、斗……Bn,

其銷量分別為4也,……

先討論產銷平衡問題，（總產量）（總需求量）

i=lj=\

%表從第i個產地運輸該物質到第j個銷地的單位運價，

，=1,2,...m,y=l,2,....n,在滿足供需平衡條件下，如

何組織運輸可使總運費達到最省？

2.數學模型

設％H表從第i個產地運輸該物質到第j個銷地的運輸量，

目標函數是使得其總運費達最省，即求：

MinZ=ZZ&jXij

i=]j=\

S?tP^Xij=bjj=1,2〉....〃

i=l

表次個產地運輸該物質到第/個銷地的運量之和等于第

J銷地的需求量與，

ZM?=i=1,2,...m

六i

表第，個產地運輸該物質到幾個銷地的運量之和等于

第i個產地的產量q

（供需平衡）共相+〃+i個約束，

i=lj=l

Xjj^Oz=1,2,.....m,j=1,2,........n,

3.運輸問題也是一個線性規劃問題，由運輸問題的特殊性，

該問題一定有最優調運，由于％”中有一部分取零，可用表

上作業法求最優解，以舉例說明。

☆例：某地區有三個煤礦4,A2,4其年產量分別為4=112,

%=164,%=154（單位：萬噸），有三個電廠與，鳥，與每

年需求量分別為々=144,8=204,4=82（單位：萬噸），供

需平衡。熱分別為4、8、8,16、24、16,8、16、24單位:

萬元/萬噸。如何調運既要滿足供需平衡又要使總運費最省。

解：用表上作用法求最優調運。

<1>用最小元素法求解初始調運方案，

minmin4/=。“=4（就近運輸），

44坊并劃去4所在行的格子，用x表示，余下4/

中最小元素為8。

4」3一片并劃去為所在列的格子，用x表示，余

下4/中最小元素為16o

A2B.并劃去層所在列,4?4沮j當,A2B2

稱表格中填數字的格子為有效數字格，恰為

加+“-1=3+3-1=5個，其余為空格，且滿足供需平衡，初

始總運費z°=4X112+24義82+16義82+8*32+16X122=5936萬

元。

\銷

地\

B]B?名產量ui

產地\

4X880

4112

11?112XX0

16241612

4164

><828216

8W-re-----10244

4154

32122X8

銷/p>

4124

V.J

080

<2>檢驗是否為最優調運。

1°首先對有效數字格建立位勢方程組%、，分別表產銷地

的位勢?=%+，，

41=4=%+=>匕=4

^22=24=4+嶺=>〃2=12

d?3=16=〃2+V3n“3=4

。31=8=〃3+=>%=4

°32=16=“3+V2n%=12

5個方程6個未知數，有無窮多組解。

令%=0（規定），可表上作業。

2°對空格的檢驗數，定義為%=&-（/+，），

若所有%M0（求M譏Z）,則得最優調運。

由02二《2-（%+%）=8-（0+12）=-4<0初始調運不

是最優的。（注意對有效數字格的檢驗數為零）。

<3>調整。

1°從檢驗數小于零的空格出發作水平或鉛直線，若遇空格

則只能按原方向畫線。若遇上有效數字格可按原方向或轉

90°畫線，回到原空格處形成一條閉曲線。（注意閉曲線的

頂點除起點在空格處，其余都在有效數字格內。）

2°以閉曲線空格頂點為1,依次為2、3、4…，

令6=min｛偶數頂點的運量｝=min（112,122）=112,

作調整，奇數頂點格+e（二112）,偶數頂點格-6,

仍保持供需平衡。

<4〉再檢驗是否為最優調運。仍對有效數字格，建立位勢方

程組熱=%+vj,令%=0,產銷地位勢如表，且有

5尸4-（0+0）=4>003=8-（0+0）=8>0

/尸16-（16+0）=0/3=24-（8+0）=16>0

最優調運：4―易A2―9JB2A2一S—>By

4」^片44當，

最省總運費:

Z*=8義112+24X82+16X82+8義114+16X10=5488萬元，

節省了=448萬元。

4.幾點說明

<1>若空格的檢驗數3>0,則最優調運唯一，若存在空格檢

驗數%=0,則最優調運不唯一。

<2>最小元素法有一個缺點，在按最小元素實施調運時，可

能造成另一處調運的單價較高，總運費也較高。伏格爾給出

最小元素法的改進。給出每一個產銷地次小元素與最小元素

的差異，分別稱為行、列差。按行、列差中最大者的所在行,

列中的最小元素先行調運。

☆以下用伏格爾法求最優調運：

產銷地的行、列差如表所示，其中最大者為8,一般取行、

列標較小的先實施調運。

4」『斗，調整行、列差，

仍選第2列的列差為8,

4204-2)之調整行、列差；

4--92=62>B]A,--62=82〉坊乙也〉區

有效數字格為根+〃-1=3+3-1=5個，

對有效數字建立位勢方程組：%=%+匕,令4=0。

產銷地的位勢如表：

0尸4-(0+0)-4>0,

(r13=8-(0+0)=8>0,

『24-(16+8)=0,

最優調運不唯一

%=24-(8+0)=16>0,

以上調運為最優。

最小的總運費：

Z*=8x112+16x82+16x82+8x62+16x92=5488萬元。

\銷

、地

BlB?為產量行差%

產地\

488

411240

X112X

162416

4164016

82X82

81624

乂31548,168

6292X

銷/p>

4,

列差88

8

匕080

<3>對與產銷不平衡問題，可化為產銷平衡問題求最優調運。

r若產大于銷，供過于求。即>±b}o可虛設一個銷地

/=!7=1

5加其銷量卻尸卷廠如，4,“+1=0,"1,2,……加，若第〃+1

j=1j=l

列中有有效數字，表明產量仍在原產地，沒有運出。

2°若產小于銷，供不應求，即與，可虛擬一個產地,

/=17=1

4+1其產量％用=t“一1>，d"，+ij=">°，，=1，2,....〃，

;=1/=1

M>0充分大，第m+1個產地沒有有效數字。

第三章整數規劃

若規劃問題的決策變量取整數則稱之為整數規劃

1、0-1整數規劃

引例、消防站最佳布點問題

設某市有6個行政區，每個行政區都可布消防站，當發生

緊急情況時，要求15分鐘內趕到出事地點，由于布消防站

有較大費用，市政府希望布點以少為好，下表給出6個行政

區相互到達的時間，給出最佳布點方案。

123456

101016282720

210024321710

316240121721

4W,我11；01525

527171715014

620102125140

上表為一對稱矩陣，其中0表示在同一個行政區內，當發生

緊急情況時，15分鐘可趕到出事地點。

解：引入決策變量:

%第左個行政區布點

設0第4個行政區不布點

目標函數是使布點以少為好,

6

即求MinZ=￡xk=X]+x2H------FX6

k=\

S.tx,'Ex,21（1,2行政區至少有1個布點）,

（對第二行政區），

-UN1（對第三行政區），

+4+匕21（對第四行政區），

4（對第五行政區）,

（對第六行政區），

/二0或1,

**

最優解％2=1，x4=l?%j=0，j=1、3、5、6o

第2個行政區布點可兼顧1、6行政區，第4個行政區

布點可兼顧3、5行政區。

例2.最優投資方案問題。

美國/K公司有資金1100萬，擬向四個項目投資，可調動研

發人員22人。四個項目需投資額分別為650、500、550、400

(萬)，研發人員分別為16、8、7、5(人)，凈現值分別為

900、700、650、600(萬),且要求1、4項目不能同時研發,

給出最優投資方案，使公司收益最大。

解：＜1＞建立數學模型

、二對第4個項目投資

設”=(()對第4個項目不投資

目標函數是使公司收益最大，即求

MaxZ=900玉+700X2+65。七+600x4

S.t650$+500%+5509+4001100

16^+8^2+7^3+5^4^22

玉+%wi

叫=0或1,左=1,2,3,4.

＜2＞求解：決策變量4個，每個僅取2個值，

C；：(0,0,0,0);

0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1);

1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,0),(0,1,0,1),(0,0,1,1);

cj:(l,1,1,0),(1,0,1,1),(1,1,0,1),(0,1,1,1);

c：：(l,1,1,1)；

共有變量組合數為=24=16種。

c：+c；+c；+c；+c：=24=16

1。.隱枚舉法：

任取一個可行解：如X。=(1,0,0,0),

則z°=900,可增加一個約束條件，

900再+700%+650毛+600%>900稱之為過濾條件，凡目標

函數值不超過900的不予考慮，又得可行解(0,1,1,0),修改過

濾條件900再+700々+650$+600%21350,其余不是可行

解。最優投資方案為：

*****

再=0,工2=1，“3=1，、4=0Z=1350

2。巴拉斯改進算法

首先作變換使目標函數中的價值系數全部變為正數，即

若CjV0,令U=1-X；,當％廣0時,又當今=1時，必=0,

叼仍是0T變量。其次將目標函數按價值系數(已全部為正

數)的大小重新排序，可從大到小。然后按目標函數值從大

到小取變量組合。，1，11),1,0),(1/,0,1),(1,0,1,1),

(0,1,1,1),(1,1,0,0),(1,0,1,0),(1,0,0,1)都不是可行解。其

目標函數值逐漸下降，按此取法，一旦是可行解，一定是最

優解，本例中(0,1,1,0)是可行解，一定是最優解，一般隱枚

舉法可節省40%以上的計算，改進算法，可節省60%以上計

算。

2、最優指派問題（考試要求）

<1>問題的提出，〃個人（”個工程隊）被指派去完成“項

工作，規定每個人僅能承擔〃項工作中的一項工作，每一項

工作必須由一人承擔，由于每一個人完成〃項工作的效率不

同，則有效率矩陣C.x”=（cJ其中與表第，個人完成第/項

工作的效率（用時最短，費用最省，收益最大，利潤最高等）

如何指派可使效率最高。

<2>數學模型，引入0-1決策變量

1第，個人被指派去完成第/項工作

令%j=<

10第，個人不被指派去完成第7項工作

目標函數是求Min（Max）Z=￡工cuxy

Z=1J=\

n

S.tj=1,2,…，n

f=l

表對第j項工作n個人僅有一個人被指派去承擔。

』，2,…，n

7=1

表第，個人對〃項工作僅能承擔一項。

%=0或1,i,j=1,2,…，〃

最優指派一定存在，由于指派方式有〃！種，但僅有〃個

取1,其余全部取0,可用矩陣變換法求解。

例1.某公司開發一種新產品，擬推向國際市場，需將產品說

明書譯成英、法、德、俄四種語言。公司派四名工程師，承

擔該項任務，每位工程師翻譯一種語言，下表給出譯文的用

時，給出最優指派,以使總用時最短。

min

‘215134、’013112、

2少137砂

104141546010116?69

（\C"）4x4=—>

914161390574?532

、）

、78119,70142g1?町

min0042

’0o01、

010o

100o

01o7

（1）求效率矩陣C中每一行每一列最小元素，使每一行（列）

所有元素減去對應的最小元素，使得每一行（列）至少出現

一個零元素。

（2）從零元素最少的行（列）圈零用Q表示。并劃去圈零

所在列（行）其余零元素用0表示。

（3）若圈零的零元素恰有〃個（〃=4）,令其為1,其余元

素令其為0得最優指派矩陣。

4表工程師，，=123,4

與表英、法、德、俄四種語言，j=l,2,3,4

/—B4A2-B2AA4上^^

Z*=4+4+9+11=28

☆例2.某公司有四個環保項目擬由四個工程隊承建，每個工

程隊僅能承建一個項目，給出最優指派，使總費用最省。效

率矩陣單位：萬元。

min

'30364248、30'061218、頊一4-12—啰-

。384644363621080288中

4*4=EL-)-?

523432383220206--20-(§)-0—o--

、38424634,34、48120,、4612.

minC產獷

000、

0017或

010

10

川@820、'0100、

@22/7;:;二,為最優指派矩陣。

24/?12

<2/6媯、0001,

解：1第，個工程隊被指派承建第J個項目

設馬二<

0第，個工程隊不被指派承建第J個項目

44

求：=與巧.

Z=1J=1

,4?

S工Zx,=l,7=1,2,3,4

/=1

表對第J個項目4個工程隊僅有一個工程隊被指派去承擔。

4?

之馬=1,z=1,2,3,4

j=l

表第，個工程隊對4個項目僅能承擔一項。

福=0或1

4表第，個工程隊，=1,2,3,4

與表第7項項目）=1,2,3,4

以下用矩陣變換法，前3個步驟與例1相同，

（4）若圈零的零元素個數小于〃（〃=4）,則要增加零元素。

首先求覆蓋所有零元素的最少直線數，

1°對未圈零的行打J

2°對打J的行含零元素的列打J

3°對打J列中含圈零的所在行打J

40對未打J的行及打J的列畫直線即為覆蓋所有零元素的

最少直線數

其次，求出未被直線覆蓋元素中最小元素，將打J行所有元

素減去該最小元素及打J列中元素加上該最小元素，重復以

上過程，直至得最優指派矩陣。

B

A^A2」^B4A3」^^％4—^2

箕@820、’0100、

?22/1000

最省總費用Z，=140萬—?

24/?120010

<2/6、000"

為最優指派矩陣

AB2AB]A&A%

Z*=140萬元

<3>求MaxZ=ZZcijxij

i=\j=l

s.tE%=1j=1,2,,,?n

Z=1

Z巧=1i=\,2,…n

7=1

為=0或1

可轉化為最小值題求最優指派

取〃=maxmax4（表〃,個元素中取最大者）

ij

令d..=M-與構造一個新的效率矩陣

%,=（四）『CH

Z=ZE2=￡￡（〃-4K=MHx'j-H%%?=旃-￡￡d/q

i-\j-\j=li-\>1i=lj-\/=1y=l

欲求MaxZ=￡￡q洛），即求Mz力吟之之4為用。作矩陣變換。

/=1y=l/=1j=\

3、整數規劃問題的分支定界法

例5.某房開公司在某時段內擁有土地30000m2,擬開發兩種

商品房,甲種每棟占地2500m2,獲利10000萬,乙種每棟占

地4000m2,獲利20000萬,由市場需求甲種住房不超過8

棟，乙種住房不超過4棟，給出最優決策，使公司獲利最大。

解（1）建立數學模型

設甲、乙兩種住房分別修建玉、馬棟，求

MaxZ=l0000玉+200009

s.t2500再+40009W30000

玉W8,%W4,

司20/20且為整數

（2）稱整數規劃問題為A,其最優值為Z*,去掉整數約

束為一個LP問題，稱為規劃紇，圖解,、求解為，

=10000_1

K等值線一一麗6=一5

最優解國=5.6,%=4

*

Zo=10000X5.6+20000X4=136000

定界0Wz*Wz；=136000

2°分支，任取一個非整數解：

5<玉=5.6<6

（1）附加一個約束條件xw5,稱為瓦問題，求解r

最優解：匯=5,%；=4,最優值為

Z；=10000X5+20000X4=130000，已是一個整數解,

修改下界：130000^7*^136000并剪支;

(2)附加約束條件占26,稱之為當問題，求解層，

最優解：%；=6,芯=3.75,

最優值為z；=10000X6+200