運籌學(xué)教材資料

運籌學(xué)

OperationalResearch

貴州大學(xué)理學(xué)院周國利教授

運籌學(xué)作為一門學(xué)科誕生于20世紀(jì)30年代末期，從第

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

籌學(xué)小組諸如護(hù)航艦隊保護(hù)商船隊的編隊問題；當(dāng)船隊遭受

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

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

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

急轉(zhuǎn)向，小船應(yīng)緩慢轉(zhuǎn)向的躲避方法，該研究成果使船只的

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

度后，德國潛艇的被摧毀數(shù)增加到400%o第二次世界大戰(zhàn)

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

統(tǒng)的設(shè)計和未來戰(zhàn)爭的戰(zhàn)略，1957年美國研究北極星導(dǎo)彈提

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

到工業(yè)、農(nóng)業(yè)、商業(yè)及政府管理部門等，并得到了迅速發(fā)展。

為了有效地應(yīng)用運籌學(xué)，一般要遵循六條原則：

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

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

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

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

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

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

應(yīng)用運籌學(xué)解決問題時，關(guān)健是建立數(shù)學(xué)模型，再選擇

數(shù)學(xué)軟件進(jìn)行計算，結(jié)合實際作出決策。

第一章線性規(guī)劃及對偶問題

LinearprogrammingandDualproblem

1、兩個引例

引例1.環(huán)保排污問題

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

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

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

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

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

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

費用達(dá)最??？

解：（1）首先建立數(shù)學(xué)模型，

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

為決策變量；目標(biāo)是使總費用達(dá)到最省，

即求最小值MinZ=1000再+800%,稱之為目標(biāo)函數(shù)，

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

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

500+2001000

再W2X2WI.4,且有：再2020（非負(fù)約束）

稱以上數(shù)學(xué)模型為線性規(guī)劃問題，記為“問題。

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

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

成），且標(biāo)出可行區(qū)域D頂點的坐標(biāo)。

目標(biāo)函數(shù)等值線，令：Z=1000玉+800=>%2="|須+。

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

數(shù)值減少方向，一簇相互平行的目標(biāo)函數(shù)等值線既要在可行

域D內(nèi)，又要目標(biāo)函數(shù)值達(dá)到最小，最優(yōu)解一定可在某一頂

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

**

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

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

引例2.銀行理財?shù)淖顑?yōu)投資方法

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

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

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

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

解：（1）數(shù)學(xué)模型

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

目標(biāo)是使銀行利潤最大，即

求MaxZ=0.1玉+0.05%

s.t須+工2至10000

X23000

當(dāng)20.25（%+工2）=3工2》再

國20x220

（2）求最優(yōu)解

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

0.1c

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

-0.0511

目標(biāo)函數(shù)等值線的斜率％等值線二-旦=-2（并標(biāo)出目標(biāo)函數(shù)值

寺但*0.05

增加方向），如圖：

**

最優(yōu)投資方案：西=7500萬，%2=2500萬,

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

為”問題的最優(yōu)值，即銀行的最大利潤。

2、七尸問題的一般數(shù)學(xué)模型及標(biāo)準(zhǔn)型

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

j=t

再，％2…,Z是決策變量,…,g是對應(yīng)的價值系數(shù)，

為目標(biāo)函數(shù)

7=1

aX

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

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

x

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

4也,…一為資源限制

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

入對第，種產(chǎn)品的產(chǎn)出量。

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

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

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

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

s.tZXW(=,2)6X20。

￡產(chǎn)問題的標(biāo)準(zhǔn)形為：

求MaxZ=CXS.tAX=bX>0。

用Exce/,Lindo,Mcz〃ab軟件包計算lP時都要化為標(biāo)準(zhǔn)形。

下面給出化標(biāo)準(zhǔn)形方法

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

在目標(biāo)函數(shù)上加一負(fù)號，即求MaxZ=-CX。

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

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

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

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

成立。

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

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

%；>0,xJ>0o

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

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

☆生產(chǎn)的最優(yōu)安排問題(綜合題型)

某工廠在一個生產(chǎn)期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，需4民。三

種資源，如表所示

單位甲產(chǎn)單位乙產(chǎn)資源限制

品資源數(shù)品資源數(shù)

z資源2140

3資源1240

C資源1125

單位利2030

潤

如何組織生產(chǎn)，可使工廠獲利最大？

(1)建立數(shù)學(xué)模型

設(shè)在該生產(chǎn)時期分別生產(chǎn)甲、乙兩種產(chǎn)品為玉個

單位，目標(biāo)是使工廠獲利最大，即：

求MaxZ=20項+30X2

s.t2%i+/(40

x{+2X2<40

x1+x2<25

占20%20

(2)圖解法求最優(yōu)生產(chǎn)條件

左等值線=一［＜0(左為目標(biāo)函數(shù)等值線的斜率)

**

最優(yōu)生產(chǎn)條件芯=10,%=15,

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

(3)單純形法，先化為標(biāo)準(zhǔn)形，求最大值

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

s.t2再+x2+x3=40

國+2X2+X4=40

玉+々+x5=25

X/20J=…5

x3,x4,x5為松弛變量

標(biāo)準(zhǔn)形約束條件4x5中的3行及后3列組成3階單位矩

陣為基矩陣03=用，對應(yīng)的變量/出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為基變量

。產(chǎn)4-工儲旬為檢驗數(shù)，j=i,2,...n

Z=1

當(dāng)區(qū)wo時可得最優(yōu)解。

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

=%2進(jìn)基

取.=跖釁卷，第=20

=>%4出基

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

其余元素化為Oo

（71=5>0

n再進(jì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,最優(yōu)解x：=10,x；=15Z*=650,

生產(chǎn)最優(yōu)安排例中

求MaxZ=20再+30々

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

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

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

X]川%>0

**

最優(yōu)生產(chǎn)條件玉=10,々=15,

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

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

%=。廠2>他W0得最優(yōu)解（第一個考試題與它有關(guān)）。

/=1

（4）對偶問題

若生產(chǎn)的組織者不準(zhǔn)備安排生產(chǎn)，而是將設(shè)備出租，資源

轉(zhuǎn)讓，在市場經(jīng)濟的條件下，如何定價？（涉及到資產(chǎn)評估

問題）

假設(shè)45。三種資源轉(zhuǎn)讓的附加值，分別為凹,外，為、

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

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

2j,+y2+y3>20,

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

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

%+2%+%230，

3°購買方購買。三種資源，組織生產(chǎn)另一類產(chǎn)品，

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

稱求MinW=40y+408+25%

S.t2乂+%+為220

%+2%+%230

%，％，%>0

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

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

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

**

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

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

（5）影子價格對市場經(jīng)濟有調(diào)節(jié)作用

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

乜、

由%=功=（必,%,%）b2為。P問題的目標(biāo)函數(shù)及多元函

dw

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

是目標(biāo)函數(shù)對第，種資源4求偏導(dǎo)數(shù)（其它資源為常數(shù)），表

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

由單純形法最終表的檢驗數(shù)行中，松弛變量恐，、4，％5對應(yīng)的

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

區(qū)二10（6資源）其=10（。資源）

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

從40—41,2M+%441,

25-1

2再+々=40

其它資源不變，解方程組

斗+吃=25

**

最優(yōu)解=10,%2二15,

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

表明4資源沒有升值，按原價轉(zhuǎn)讓。

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

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

%]+%=25

**

最優(yōu)解%二9,超二16,

最優(yōu)值Z*=20X9+30X16=660,

函數(shù)值增加了10個單位，表明B資源升值，轉(zhuǎn)讓的附加

值為10個單位。

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

Y+2x—40

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

玉+W=26

**

最優(yōu)解=12,々=14,

最優(yōu)值Z*=20X12+30X14=660,

函數(shù)值增加了10個單位，表明C資源升值，轉(zhuǎn)讓的附加

值為10個單位。

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

fX,+2x,=41

25f26,解方程組?上2

%+%2=26

**

最優(yōu)解玉=11,%2=15,

最優(yōu)值Z*=20X11+30X15=670,

函數(shù)值增加了20個單位。

5°若甲乙產(chǎn)品每單位的利潤都為30,目標(biāo)函數(shù)Z=30玉+30%

〃等值線二TVO(左為目標(biāo)函數(shù)等值線的斜率)

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

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

最優(yōu)值Z*=30X10+30X15=750。

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

價格，則應(yīng)該購進(jìn)該資源擴大再生產(chǎn)，

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

資源以獲得最大利潤。

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

求MinW=40M+40為+25%

S.t2yx+y2+y3>20

必+2歹2+為230

必，為，8-0

的最優(yōu)解，

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

s.t2xx+x2<40

x1+2X2<40

$+%2<25

國20x220

可用圖解法求最優(yōu)解

**

最優(yōu)解-^1=10,%2=15,

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

設(shè)原問題的最優(yōu)解分別為，則由互補松弛條件,

給出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

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

4、LP問題的一個應(yīng)用：最優(yōu)下料問題

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

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

使用料最?。?/p>

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

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加,看表

示，

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

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)且為整數(shù)

以上數(shù)學(xué)模型可用Exce/,Lindo,MK/ab軟件包計算，最

優(yōu)下料方法為：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。

其他應(yīng)用有配料問題、生產(chǎn)工藝優(yōu)化問題、有配套約束

的資源優(yōu)化問題、多周期動態(tài)生產(chǎn)計劃問題、投資問題、運

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

5、幾點說明：

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

￡產(chǎn)問題的標(biāo)準(zhǔn)形矩陣形式的約束條件=6中，對矩陣

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

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

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

無關(guān)，令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，再令目標(biāo)函數(shù)中的價值系數(shù)

）（，，）

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,當(dāng)。=品-。心一0二0時，目標(biāo)函數(shù)Z取得最

大值Z*=CM",稱5v=g-為檢驗數(shù)矩陣，其坐標(biāo)

m

形式為%=Cj—￡c4,j=m+l,m+2,…n,當(dāng)檢驗數(shù)滿足

?=1

m

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

f=l

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

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

的理論性較強，對偶理論深刻揭示了原問題與對偶問題的內(nèi)

在聯(lián)系，由對偶問題引伸出來的對偶解有著重要的經(jīng)濟意

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

問題可作靈敏度分析，即價值系數(shù)、資源約束和投入產(chǎn)出矩

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

(3)￡產(chǎn)問題主要解決一個目標(biāo)函數(shù)的最優(yōu)化問題，但在實

際問題中往往要考慮多個目標(biāo)，如設(shè)計一個新產(chǎn)品的工藝過

程，不僅希望利潤大，而且希望產(chǎn)量高、消耗低、質(zhì)量好、

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

目標(biāo)規(guī)劃，線性目標(biāo)規(guī)劃的圖解法既難作而且僅限于二個決

策變量，可將原多目標(biāo)規(guī)劃分解成一系列的傳統(tǒng)的單目標(biāo)線

性規(guī)劃，并引入正、負(fù)偏差變量然后依次求解，最

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

性目標(biāo)規(guī)劃的序貫式算法。

（4）對于非線性規(guī)劃，由無約束問題的最優(yōu)解的必要條件,

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

dx{ax2dxn

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

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

非線性規(guī)劃中對于有約束問題的最優(yōu)性條件要用到庫恩一

塔克條件、可行方向法、近似規(guī)劃法及制約函數(shù)法，非線性

規(guī)劃的數(shù)學(xué)基礎(chǔ)要求很深，求解規(guī)劃問題的關(guān)健在于建立數(shù)

學(xué)模型，非線性規(guī)劃求解可用G/NO軟件完成。

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

1、問題的提出，設(shè)某種物質(zhì)有加個產(chǎn)地4、出……4,，其

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

其銷量分別為4也,……

先討論產(chǎn)銷平衡問題，（總產(chǎn)量）（總需求量）

i=lj=\

%表從第i個產(chǎn)地運輸該物質(zhì)到第j個銷地的單位運價，

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

何組織運輸可使總運費達(dá)到最??？

2.數(shù)學(xué)模型

設(shè)％H表從第i個產(chǎn)地運輸該物質(zhì)到第j個銷地的運輸量，

目標(biāo)函數(shù)是使得其總運費達(dá)最省，即求：

MinZ=ZZ&jXij

i=]j=\

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

i=l

表次個產(chǎn)地運輸該物質(zhì)到第/個銷地的運量之和等于第

J銷地的需求量與，

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

六i

表第，個產(chǎn)地運輸該物質(zhì)到幾個銷地的運量之和等于

第i個產(chǎn)地的產(chǎn)量q

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

i=lj=l

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

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

該問題一定有最優(yōu)調(diào)運，由于％”中有一部分取零，可用表

上作業(yè)法求最優(yōu)解，以舉例說明。

☆例：某地區(qū)有三個煤礦4,A2,4其年產(chǎn)量分別為4=112,

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

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

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

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

解：用表上作用法求最優(yōu)調(diào)運。

<1>用最小元素法求解初始調(diào)運方案，

minmin4/=?！?4（就近運輸），

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

中最小元素為8。

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

下4/中最小元素為16o

A2B.并劃去層所在列,4?4沮j當(dāng),A2B2

稱表格中填數(shù)字的格子為有效數(shù)字格，恰為

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

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

元。

\銷

地\

B]B?名產(chǎn)量ui

產(chǎn)地\

4X880

4112

11?112XX0

16241612

4164

><828216

8W-re-----10244

4154

32122X8

銷/p>

4124

V.J

080

<2>檢驗是否為最優(yōu)調(diào)運。

1°首先對有效數(shù)字格建立位勢方程組%、，分別表產(chǎn)銷地

的位勢?=%+，，

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個未知數(shù)，有無窮多組解。

令%=0（規(guī)定），可表上作業(yè)。

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

若所有%M0（求M譏Z）,則得最優(yōu)調(diào)運。

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

是最優(yōu)的。（注意對有效數(shù)字格的檢驗數(shù)為零）。

<3>調(diào)整。

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

則只能按原方向畫線。若遇上有效數(shù)字格可按原方向或轉(zhuǎn)

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

頂點除起點在空格處，其余都在有效數(shù)字格內(nèi)。）

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

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

作調(diào)整，奇數(shù)頂點格+e（二112）,偶數(shù)頂點格-6,

仍保持供需平衡。

<4〉再檢驗是否為最優(yōu)調(diào)運。仍對有效數(shù)字格，建立位勢方

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

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

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

最優(yōu)調(diào)運：4―易A2―9JB2A2一S—>By

4」^片44當(dāng)，

最省總運費:

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

節(jié)省了=448萬元。

4.幾點說明

<1>若空格的檢驗數(shù)3>0,則最優(yōu)調(diào)運唯一，若存在空格檢

驗數(shù)%=0,則最優(yōu)調(diào)運不唯一。

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

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

最小元素法的改進(jìn)。給出每一個產(chǎn)銷地次小元素與最小元素

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

列中的最小元素先行調(diào)運。

☆以下用伏格爾法求最優(yōu)調(diào)運：

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

列標(biāo)較小的先實施調(diào)運。

4」『斗，調(diào)整行、列差，

仍選第2列的列差為8,

4204-2)之調(diào)整行、列差；

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

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

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

產(chǎn)銷地的位勢如表：

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

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

『24-(16+8)=0,

最優(yōu)調(diào)運不唯一

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

以上調(diào)運為最優(yōu)。

最小的總運費：

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

\銷

、地

BlB?為產(chǎn)量行差%

產(chǎn)地\

488

411240

X112X

162416

4164016

82X82

81624

乂31548,168

6292X

銷/p>

4,

列差88

8

匕080

<3>對與產(chǎn)銷不平衡問題，可化為產(chǎn)銷平衡問題求最優(yōu)調(diào)運。

r若產(chǎn)大于銷，供過于求。即>±b}o可虛設(shè)一個銷地

/=!7=1

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

j=1j=l

列中有有效數(shù)字，表明產(chǎn)量仍在原產(chǎn)地，沒有運出。

2°若產(chǎn)小于銷，供不應(yīng)求，即與，可虛擬一個產(chǎn)地,

/=17=1

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

;=1/=1

M>0充分大，第m+1個產(chǎn)地沒有有效數(shù)字。

第三章整數(shù)規(guī)劃

若規(guī)劃問題的決策變量取整數(shù)則稱之為整數(shù)規(guī)劃

1、0-1整數(shù)規(guī)劃

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

設(shè)某市有6個行政區(qū)，每個行政區(qū)都可布消防站，當(dāng)發(fā)生

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

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

區(qū)相互到達(dá)的時間，給出最佳布點方案。

123456

101016282720

210024321710

316240121721

4W,我11；01525

527171715014

620102125140

上表為一對稱矩陣，其中0表示在同一個行政區(qū)內(nèi)，當(dāng)發(fā)生

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

解：引入決策變量:

%第左個行政區(qū)布點

設(shè)0第4個行政區(qū)不布點

目標(biāo)函數(shù)是使布點以少為好,

6

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

k=\

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

（對第二行政區(qū)），

-UN1（對第三行政區(qū)），

+4+匕21（對第四行政區(qū)），

4（對第五行政區(qū)）,

（對第六行政區(qū)），

/二0或1,

**

最優(yōu)解％2=1，x4=l?%j=0，j=1、3、5、6o

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

布點可兼顧3、5行政區(qū)。

例2.最優(yōu)投資方案問題。

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

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

(萬)，研發(fā)人員分別為16、8、7、5(人)，凈現(xiàn)值分別為

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

給出最優(yōu)投資方案，使公司收益最大。

解：＜1＞建立數(shù)學(xué)模型

、二對第4個項目投資

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

目標(biāo)函數(shù)是使公司收益最大，即求

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)；

共有變量組合數(shù)為=24=16種。

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

1。.隱枚舉法：

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

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

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

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

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

解。最優(yōu)投資方案為：

*****

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

2。巴拉斯改進(jìn)算法

首先作變換使目標(biāo)函數(shù)中的價值系數(shù)全部變?yōu)檎龜?shù)，即

若CjV0,令U=1-X；,當(dāng)％廣0時,又當(dāng)今=1時，必=0,

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

數(shù))的大小重新排序，可從大到小。然后按目標(biāo)函數(shù)值從大

到小取變量組合。，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)都不是可行解。其

目標(biāo)函數(shù)值逐漸下降，按此取法，一旦是可行解，一定是最

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

舉法可節(jié)省40%以上的計算，改進(jìn)算法，可節(jié)省60%以上計

算。

2、最優(yōu)指派問題（考試要求）

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

工作，規(guī)定每個人僅能承擔(dān)〃項工作中的一項工作，每一項

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

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

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

如何指派可使效率最高。

<2>數(shù)學(xué)模型，引入0-1決策變量

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

令%j=<

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

目標(biāo)函數(shù)是求Min（Max）Z=￡工cuxy

Z=1J=\

n

S.tj=1,2,…，n

f=l

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

』，2,…，n

7=1

表第，個人對〃項工作僅能承擔(dān)一項。

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

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

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

例1.某公司開發(fā)一種新產(chǎn)品，擬推向國際市場，需將產(chǎn)品說

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

擔(dān)該項任務(wù)，每位工程師翻譯一種語言，下表給出譯文的用

時，給出最優(yōu)指派,以使總用時最短。

min

‘215134、’013112、

2少137砂

104141546010116?69

（\C"）4x4=—>

914161390574?532

、）

、78119,70142g1?町

min0042

’0o01、

010o

100o

01o7

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

所有元素減去對應(yīng)的最小元素，使得每一行（列）至少出現(xiàn)

一個零元素。

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

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

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

素令其為0得最優(yōu)指派矩陣。

4表工程師，，=123,4

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

/—B4A2-B2AA4上^^

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

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

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

率矩陣單位：萬元。

min

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

。384644363621080288中

4*4=EL-)-?

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

、38424634,34、48120,、4612.

minC產(chǎn)獷

000、

0017或

010

10

川@820、'0100、

@22/7;:;二,為最優(yōu)指派矩陣。

24/?12

<2/6媯、0001,

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

設(shè)馬二<

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

44

求：=與巧.

Z=1J=1

,4?

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

/=1

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

4?

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

j=l

表第，個工程隊對4個項目僅能承擔(dān)一項。

福=0或1

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

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

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

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

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

1°對未圈零的行打J

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

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

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

最少直線數(shù)

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

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

上過程，直至得最優(yōu)指派矩陣。

B

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

箕@820、’0100、

?22/1000

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

24/?120010

<2/6、000"

為最優(yōu)指派矩陣

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

可轉(zhuǎn)化為最小值題求最優(yōu)指派

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

ij

令d..=M-與構(gòu)造一個新的效率矩陣

%,=（四）『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、整數(shù)規(guī)劃問題的分支定界法

例5.某房開公司在某時段內(nèi)擁有土地30000m2,擬開發(fā)兩種

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

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

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

解（1）建立數(shù)學(xué)模型

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

MaxZ=l0000玉+200009

s.t2500再+40009W30000

玉W8,%W4,

司20/20且為整數(shù)

（2）稱整數(shù)規(guī)劃問題為A,其最優(yōu)值為Z*,去掉整數(shù)約

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

=10000_1

K等值線一一麗6=一5

最優(yōu)解國=5.6,%=4

*

Zo=10000X5.6+20000X4=136000

定界0Wz*Wz；=136000

2°分支，任取一個非整數(shù)解：

5<玉=5.6<6

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

最優(yōu)解：匯=5,%；=4,最優(yōu)值為

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

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

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

最優(yōu)解：%；=6,芯=3.75,

最優(yōu)值為z；=10000X6+200