數(shù)學(xué)建模教程

目錄

為

第

一線性規(guī)劃

早

第

一

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

第

三

章非線性規(guī)劃

第

四

章動態(tài)規(guī)劃

第

五

章圖與網(wǎng)絡(luò)

第

六

章初等數(shù)學(xué)方法建模

第

七

章變分法

第

章

八

層次分析法

章

第

九

章差分法

第

十

一模糊數(shù)學(xué)

第

十

章

Matlab教程

-1-

第一章線性規(guī)劃

§1線性規(guī)劃

在人們的生產(chǎn)實(shí)踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大

經(jīng)濟(jì)效益的問題。此類問題構(gòu)成了運(yùn)籌學(xué)的一個重要分支一數(shù)學(xué)規(guī)劃，而線性規(guī)劃

（LinearProgramming簡記LP）則是數(shù)學(xué)規(guī)劃的一個重要分支。自從1947年G.B.

Dantzig提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實(shí)

用中日益廣泛與深入。特別是在計(jì)算機(jī)能處理成千上萬個約束條件和決策變量的線

性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的

基本方法之一.

1.1線性規(guī)劃的實(shí)例與定義

例1某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺銷售后的利潤分別為4000元與3000

元。生產(chǎn)甲機(jī)床需用A、8機(jī)器加工，加工時間分別為每臺2小時和1小時；生產(chǎn)

乙機(jī)床需用4、B、C三種機(jī)器加工，加工時間為每臺各一，J、時。若每天可用于加

工的機(jī)器時數(shù)分別為A機(jī)器10小時、6機(jī)器8小時和C機(jī)器7小時，問該廠應(yīng)生

產(chǎn)甲、乙機(jī)床各幾臺，才能使總利潤最大？

上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)七臺甲機(jī)床和％?乙機(jī)床時總利潤最大，則

Xi，%?應(yīng)滿足

（目標(biāo)函數(shù)）maxz=43]+3x2

（1）

2x,+x2<10

、-x.+<8

s.t.（約束條件）12

x2<7

x,,x2>0

(2)

這里變量x”聲稱之為決策變量，（1）式被稱為問題的目標(biāo)函數(shù)，（2）中的幾個不

等式是問題的約束條件，記為s.t.（即subjectto）。上述即為一規(guī)劃問題數(shù)學(xué)模

型的三個要素。由于上面的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃

-2-

問題。

總之，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大

或最小的問題。

在解決實(shí)際問題時，把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但

往往也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選取適當(dāng)?shù)臎Q策

變量，是我們建立有效模型的關(guān)鍵之一。

1.2線性規(guī)劃的Matlab標(biāo)準(zhǔn)形式

線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號

可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便，Matlab中規(guī)

定線性規(guī)劃的標(biāo)準(zhǔn)形式為

mincTxsuchthatAx<b

x

其中C和X為〃維列向量，為〃?維列向量，A為"2X"矩陣。

例如線性規(guī)劃

maxc1xsuchthatAx>b

x

的Ma11ab標(biāo)準(zhǔn)型為

min-cTxsuchthat-Ax<-b

x

1.3線性規(guī)劃問題的解的概念

一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為

min2=

六i

(3)

s.t.￡a^Xj<bji-1,2,???,/?

j=i

(4)

可行解滿足約束條件(4)的解x=(x”X2,…,x”)，稱為線性規(guī)劃問題的可

行解，而使耳標(biāo)函數(shù)(3)達(dá)到最小值的可行解叫最優(yōu)解。

可行域所有可行解構(gòu)成的集合稱為問題的可行域，記為

1.4線性規(guī)劃的圖解法

-3-

10

圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理。我們先應(yīng)用圖解

法來求解例1。如上圖所示，陰影區(qū)域即為LP問題的可行域R。對于每一固定的值

Z，使目標(biāo)函數(shù)值等于z的點(diǎn)構(gòu)成的直線稱為目標(biāo)函數(shù)等位線，當(dāng)z變動時，我們

得到一族平行直線。讓等位線沿耳標(biāo)函數(shù)值減小的方向移動，直到等位線與可行域

有交點(diǎn)的最后位置，此時的交點(diǎn)（一個或多個）即為LP的最優(yōu)解。

對于例1,顯然等位線越趨于右上方，其上的點(diǎn)具有越大的目標(biāo)函數(shù)值。不難

看出，本例的最優(yōu)解為狀=（2,61，最優(yōu)目標(biāo)值z*=26。

從上面的圖解過程可以看出并不難證明以下斷言：

（1）可行域R可能會出現(xiàn)多種情況。R可能是空集也可能是非空集合，當(dāng)R非

空時，它必定是若干個半平面的交集（除非遇到空間維數(shù)的退化）。R既可能是有

界區(qū)域，也可能是無界區(qū)域。

（2）在R非空時，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)

解（其目標(biāo)函數(shù)值無界）。

（3）R非空且LP有有限最優(yōu)解時，最優(yōu)解可以唯一或有無窮多個。

（4）若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標(biāo)函數(shù)值的可行域R

的“頂點(diǎn)”。

上述論斷可以推廣到一般的線性規(guī)劃問題，區(qū)別只在于空間的維數(shù)。在一般的

〃維空間中，滿足一線性等式汽/七=〃的點(diǎn)集被稱為一個超平面，而滿足一線性

/=!

不等式‘/看（或'《陽>b）的點(diǎn)集被稱為一個半空間（其中⑷,…,明）為

（=1<=1

一〃維行向量，匕為一實(shí)數(shù)）。有限個半空間的交集被稱為多胞形，有界的多胞形又

被稱為多面體。易見，線性規(guī)劃的可行域必為多胞形（為統(tǒng)一起見，空集①也被視

為多胞形）,

在一般〃維空間中，要直接得出多胞形“頂點(diǎn)”概念還有一些困難。二維空間中的

頂點(diǎn)可以看成為邊界直線的交點(diǎn)，但這一幾何概念的推廣在一般〃維空間中的幾何

意義并不十分直觀。為此，我們將采用另一途徑來定義它。

定義1稱〃維空間中的區(qū)域R為一凸集，若VxUeR及V/le（O,l）,有

-4-

Ax'+(l-2)x2e7?。

定義2設(shè)R為〃維空間中的一個凸集，R中的點(diǎn)x被稱為R的一個極點(diǎn)，若

不存在x；犬eR及2e(0,1),使得x=加？+(1-九)/。

定義1說明凸集中任意兩點(diǎn)的連線必在此凸集中；而定義2說明，若x是凸

集R的一個極點(diǎn)，則x不能位于R中任意兩點(diǎn)的連線上。不難證明，多胞形必為凸

集。同樣也不難證明，二維空間中可行域R的頂點(diǎn)均為R的極點(diǎn)(R也沒有其它的

極點(diǎn))。

1.5求解線性規(guī)劃的Matlab解法

單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。單純形法是首先

由

GeorgeDantzig于1947年提出的，近60年來，雖有許多變形體已被開發(fā)，但卻保

持著同樣的基本觀念。由于有如下結(jié)論：若線性規(guī)劃問題有有限最優(yōu)解，則一定有

某個最優(yōu)解是可行區(qū)域的一個極點(diǎn)?；诖?，單純形法的基本思路是：先找出可行

域的一個極點(diǎn)，據(jù)一定規(guī)則判斷其是否最優(yōu)；若否，則轉(zhuǎn)換到與之相鄰的另一極點(diǎn)，

并使目標(biāo)函數(shù)值更優(yōu)；如此下去，直到找到某一最優(yōu)解為止。這里我們不再詳細(xì)介

紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的

Matlab解法。

Matlab5.3中線性規(guī)劃的標(biāo)準(zhǔn)型為

mincTxsuchthatAx<h

X

基本函數(shù)形式為1inprog(c,A,b),它的返回值是向量x的值。還有其它的一些函數(shù)

調(diào)用形式(在Matlab指令窗運(yùn)行help1inprog可以看到所有的函數(shù)調(diào)用形式),

如：

[x,fval]=1inprog(c,A,b,Aeq,beq,LB,UB,Xo,OPTIONS)

這里fval返回目標(biāo)函數(shù)的值，Aeq和beq對應(yīng)等式約束=beq,LB和UB

分別是變量x的下界和上界，X。是x的初始值，OPTIONS是控制參數(shù)。

例2求解下列線性規(guī)劃問題

maxz=2尤|+3x2-5x3

匹+%+%3=7

V-5X2+x3>10

XpX2,x3>0

解(錯誤！未找到引用源。)編寫M文件

c=[2;3;-5];

a=[-2,5,-1];b=-10;

aeq=[l,1,1];

beq=7;

x=linprog(-c,a,b,aeq,beq,zeros(3,1))

value=cz*x

(錯誤！未找到引用源。)將M文件存盤，并命名為examplel.m。

(錯誤！未找到引用源。)在Matlab指令窗運(yùn)行examplel即可得所求結(jié)果。

-5-

例3求解線性規(guī)劃問題

minz=2x]+3x2+x3

X

X]+42+2X3>8

<3/+2X2>6

X1,x2,x3>0

解編寫Matlab程序如下：

c=[2;3;1];

a=[l,4,2;3,2,0];

b=[8;6];

[x,y]=linprog(c,-a,-b,[],[],zeros(3,D)

1.6可以轉(zhuǎn)化為線性規(guī)劃的問題

很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃問題來解決。

如：

例4問題為

minIX]I+I々?---FII

s.t.Ax<b

1

其中元=[西???xn],A和。為相應(yīng)維數(shù)的矩陣和向量。

要把上面的問題變換成線性規(guī)劃問題，只要注意到事實(shí)：對任意的匹，存在

%,匕>0滿足

xi=%—匕，I玉1=%+匕

事實(shí)上，我們只要取%=土土！史，v=就可以滿足上面的條件。

22

T

這樣，記〃=[%???Un],V=[V]…匕J，從而我們可以把上面的問

題變成

minZ(%+匕)

i=l

A(u-v)<h

s.t.<

w,v>0

§2運(yùn)輸問題(產(chǎn)銷平衡)

例5某商品有機(jī)個產(chǎn)地、〃個銷地，各產(chǎn)地的產(chǎn)量分別為Q],…,，各銷地

的需求量分別為4,…若該商品由i產(chǎn)地運(yùn)到，銷地的單位運(yùn)價為G片問應(yīng)該

如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最省？

解：引入變量同，其取值為由，產(chǎn)地運(yùn)往/銷地的該商品數(shù)量，數(shù)學(xué)模型為

ni〃

minEEC?X?

J=1)=1

-6-

￡xjj=%,z=m

j=i

s.t.<=bj,j=1,2,,■■,n

i=l

XijN。

顯然是一個線性規(guī)劃問題，當(dāng)然可以用單純形法求解。

對產(chǎn)銷平衡的運(yùn)輸問題，由于有以下關(guān)系式存在：

￡“=￡=￡￡/=!>

j=]1=11j—1yj=]\,i=lJz=i

其約束條件的系數(shù)矩陣相當(dāng)特殊，可用比較簡單的計(jì)算方法，習(xí)慣上稱為表上作業(yè)

法（由康托洛維奇和希奇柯克兩人獨(dú)立地提出，簡稱康一希表上作業(yè)法）。

表上作業(yè)法是單純形法在求解運(yùn)輸問題時的一種簡化方法，其求解工作在運(yùn)輸

表上進(jìn)行逐步迭代如下：先按某一規(guī)則找出一個初始解（初始調(diào)運(yùn)方案）；再對現(xiàn)

行解作最優(yōu)性判斷；若這個解不是最優(yōu)的，就在運(yùn)輸表上對它進(jìn)行調(diào)整改進(jìn)，得一

新解；再判斷，再改進(jìn)，直到得到最優(yōu)解。

§3指派問題（又稱分配問題AssignmentProblem）

3.1指派問題的數(shù)學(xué)模型

例6擬分配“人去干”項(xiàng)工作，每人干且僅干一項(xiàng)工作，若分配第i人去干

第/項(xiàng)工作，需花費(fèi)與單位時間，問應(yīng)如何分配工作才能使工人花費(fèi)的總時間最

少？

容易看出，要給出一個指派問題的實(shí)例，只需給出矩陣C=（%）,C被稱為指

派問題的系數(shù)矩陣。

引入變量馬若分配i干/工作，則取冏=1,否則取x?=0。上述指派問題

的數(shù)學(xué)模型為

min汽

;=1;=|

ZX。=l,z=1,2,…，〃

j=i

s.t.<ZX。=1,J=1,2,…，〃⑸

i=\

=0或1,i,j=1,2,…，n

（5）的可行解既可以用一個矩陣（稱為解矩陣）表示，其每行每列均有且只有一

個元素為1,其余元素均為0,也可以用1,…，〃中的一個置換表示。

（5）的變量只能取0或1,從而是一個0-1規(guī)劃問題。一般的0-1規(guī)劃問題求

解極為困難。但指派問題并不難解，其約束方程組的系數(shù)矩陣十分特殊(被稱為全

單位模矩陣，其各階非零子式均為±1),其非負(fù)可行解的分量只能取0或1,故約

束%=0或1可改寫為馬NO而不改變其解。此時，指派問題被轉(zhuǎn)化為一個特殊的運(yùn)

輸問題，其中m=〃，%=鳥=1。

3.2求解指派問題的匈牙利算法

由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家D.Konig提出的更為簡便的

解法一匈牙利算法。算法主要依據(jù)以下事實(shí)：如果系數(shù)矩陣。=(%)一行(或一列)

中每一元素都加上或減去同一個數(shù)，得到一個新矩陣B=(%),則以C或B為系

數(shù)矩陣的指派問題具有相同的最優(yōu)指派。

利用上述性質(zhì)，可將原系數(shù)陣C變換為含零元素較多的新系數(shù)陣B,而最優(yōu)解

不變.若能在B中找出n個位于不同行不同列的零元素，令解矩陣中相應(yīng)位置的元

素取值為1,其它元素取值為零，則所得該解是以B為系數(shù)陣的指派問題的最優(yōu)解，

從而也是原問題的最優(yōu)解。

由C到B的轉(zhuǎn)換可通過先讓矩陣C的每行元素均減去其所在行的最小元素得矩

陣D,D的每列元素再減去其所在列的最小元素得以實(shí)現(xiàn)。

下面通過一例子來說明該算法。

例7求解指派問題，其系數(shù)矩陣為

"16151922-

17211918

c=

24221817

17192216

解將第一行元素減去此行中的最小元素15,同樣，第二行元素減去17,第

三行元素減去17,最后一行的元素減去16,得

-1047

0421

By=

7510

1360

再將第3列元素各減去1,得

'10*37

0*411

B[=

750,0

1350*

以B2為系數(shù)矩陣的指派問題有最優(yōu)指派

(1234)

[2134J

由等價性，它也是例7的最優(yōu)指派。

有時問題會稍復(fù)雜一些。

-8-

例8求解系數(shù)矩陣C的指派問題

127979

89666

c=717121412

15146610

4107106

解：先作等價變換如下

-7127979一-50*202

-6896662300*0

-7717121412->0*10575v

-615146610980*04

-4_410710606362v

v

容易看出，從變換后的矩陣中只能選出四個位于不同行不同列的零元素，但

〃=5,最優(yōu)指派還無法看出。此時等價變換還可進(jìn)行下去。步驟如下:

(1)對未選出。元素的行打V；

⑵對行中0元素所在列打v;

(3)對v列中選中的0元素所在行打v;

重復(fù)(2)、(3)直到無法再打v為止。

可以證明，若用直線劃沒有打v的行與打v的列，就得到了能夠覆蓋住矩陣中

所有零元素的最少條數(shù)的直線集合，找出未覆蓋的元素中的最小者，令v行元素減

去此數(shù)，v列元素加上此數(shù)，則原先選中的0元素不變，而未覆蓋元素中至少有一

個已轉(zhuǎn)變?yōu)?,且新矩陣的指派問題與原問題也等價。上述過程可反復(fù)采用，直到

能選取出足夠的。元素為止.例如，對例5變換后的矩陣再變換，第三行、第五行

元素減去2,第一列元素加上2,得

70202

43000

08353

118004

04140

1234

現(xiàn)在已可看出，最優(yōu)指派為

2413;)

§4對偶理論與靈敏度分析

4.1原始問題和對偶問題

考慮下列一對線性規(guī)劃模型:

maxcrxs.t.Ax<b,x>0

(P)

-9-

和

minbrys.t.Ary>c,y>0

(D)

稱(P)為原始問題，(D)為它的對偶問題。

不太嚴(yán)謹(jǐn)?shù)卣f，對偶問題可被看作是原始問題的“行列轉(zhuǎn)置”：

(1)原始問題約束條件中的第/列系數(shù)與其對偶問題約束條件中的第/行

的系數(shù)相同；

(2)原始目標(biāo)函數(shù)的系數(shù)行與其對偶問題右側(cè)的常數(shù)列相同；

(3)原始問題右側(cè)的常數(shù)列與其對偶目標(biāo)函數(shù)的系數(shù)行相同；

(4)在這一對問題中，除非負(fù)約束外的約束不等式方向和優(yōu)化方向相反。

考慮線性規(guī)劃：

mincTxs.t.Ax-b,x>Q

把其中的等式約束變成不等式約束，可得

"A'-b-

mi?ncTxs.t.x>,x>0

-A_-b

它的對偶問題是

max卜>s.t.[AT-AT]Y'<c

L>2

其中必和乃分別表示對應(yīng)于約束AxN8和-Ax2的對偶變量組。令

y=y,-y2,則上式又可寫成

maxbTys.t.ATy<c

原問題和對偶的對偶問題約束之間的關(guān)系：

minmax

>0<

變量<0行約束■>

無限制=

>0

行約束<<變量<<0

=無限制

4.2對偶問題的基本性質(zhì)

1°對稱性：對偶問題的對偶是原問題。

20弱對偶性：若工是原問題的可行解，》是對偶問題的可行解。則恒有：

cTx<bTy.

3°無界性：若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行

解。

4"可行解是最優(yōu)解時的性質(zhì)：設(shè)2是原問題的可行解，S是對偶問題的可行解，

當(dāng)/￡=//$時，$是最優(yōu)解。

-10-

5"對偶定理：若原問題有有限最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標(biāo)函數(shù)

值相同。

6"互補(bǔ)松弛性：若土J分別是原問題和對偶問題的最優(yōu)解，貝”

yT(Ax-b)=O,xr(Ary-c)=O

由上述性質(zhì)可知，對任一LP問題(P),若它的對偶問題(D)可能的話，我們總

可以通過求解(D)來討論原問題(P)：若(D)無界，貝MP)無可行解；若(D)有有限

最優(yōu)解卬*,最優(yōu)值卬7,則利用互補(bǔ)松弛性可求得(P)的所有最優(yōu)解，且(P)的最

優(yōu)值為例如對只有兩個行約束的LP,其對偶問題只有兩個變量，總可用圖解

法來求解。

例9已知線性規(guī)劃問題

mina)=2x,+3x2+5x3+2x4+3x5

s+無2+2X3+x4+3X5>4

2%]-x2+3X3+X4+X5>3

Xj>0,/=1,2,…,5

已知其對偶問題的最優(yōu)解為y：=1,y；=],最優(yōu)值為Z*=5。試用對偶理論找出

原問題的最優(yōu)解。

解先寫出它的對偶問題

max2=4%+3為

s.t.y]+2y2<2錯

誤！未找到引用源。

%一為W3錯

誤！未找到引用源。

2%+3y345錯

誤！未找到引用源。

%+為42錯

誤！未找到引用源。

3yl+為43錯

誤！未找到引用源。

月，為

將y：，y；的值代人約束條件，得錯誤！未找到引用源。，錯誤！未找到引用源.，錯

誤！未找到引用源。為嚴(yán)格不等式；設(shè)原問題的最優(yōu)解為/=x；),由互補(bǔ)

松弛性得x；=x；=x；=0。因>0;原問題的兩個約束條件應(yīng)取等式，故有

3x；+%；=4

2x：+x；=3

求解后得到x：=1,匕=1;故原問題的最優(yōu)解為

000I]1;最優(yōu)值為W*=5。

-11-

4.3靈敏度分析

靈敏度分析是指對系統(tǒng)或周圍事物因周圍條件變化顯示出來的敏感程度的分

析。

在以前討論線性規(guī)劃問題時，假定％也,的都是常數(shù)。但實(shí)際上這些系數(shù)往往

是估計(jì)值和預(yù)測值。如市場條件一變，的值就會變化；與往往是因工藝條件的改

變而改變；乙是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩

個問題：當(dāng)這些參數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會

有什么變化；或者這些參數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解不變。這

里我們就不討論了.

4.4參數(shù)線性規(guī)劃

參數(shù)線性規(guī)劃是研究％,4,與這些參數(shù)中某一參數(shù)連續(xù)變化時，使最優(yōu)解發(fā)生

變化的各臨界點(diǎn)的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這參變

量的線性函數(shù)，含這參變量的約束條件是線性等式或不等式。因此仍可用單純形法

和對偶單純形法進(jìn)行分析參數(shù)線性規(guī)劃問題。

習(xí)題一

1.某廠生產(chǎn)三種產(chǎn)品錯誤！未找到引用源。，錯誤！未找到引用源。，錯誤！

未找到引用源…每種產(chǎn)品要經(jīng)過A,B兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能

完成4工序，它們以4，A2表示；有三種規(guī)格的設(shè)備能完成8工序，它們以

與，生,當(dāng)表示。產(chǎn)品錯誤！未找到引用源?？稍贏,8任何一種規(guī)格設(shè)備上加工。

產(chǎn)品錯誤！未找到引用源?？稍谌魏我?guī)格的A設(shè)備上加工，但完成6工序時，只能

在用設(shè)備上加工；產(chǎn)品錯誤！未找到引用源。只能在A2與當(dāng)設(shè)備上加工。已知在

各種機(jī)床設(shè)備的單件工時，原材料費(fèi)，產(chǎn)品銷售價格，客種設(shè)備有效臺時以及滿負(fù)

荷操作時機(jī)床設(shè)備的費(fèi)用如下表，要求安排最優(yōu)的生產(chǎn)計(jì)劃，使該廠利潤最大。

產(chǎn)品

錯錯錯

誤！誤！誤！

滿負(fù)荷時的

設(shè)備未找未找未找設(shè)備有效臺時

設(shè)備費(fèi)用（元）

到引到引到引

用用用

源。源。源。

A5106000300

4791210000321

坊684000250

B]4117000783

當(dāng)74000200

原料費(fèi)（元/件）0.250.350.50

單價（元/件）1.252.002.80

-12-

2.有四個工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作所消耗的時

間如下表：

作

ABCD

甲15182124

乙19232218

丙26171619

丁19212317

問指派哪個人去完成哪項(xiàng)工作，可使總的消耗時間為最小？

3.某戰(zhàn)略轟炸機(jī)群奉命摧毀敵人軍事目標(biāo)。已知該目標(biāo)有四個要害部位，只

要摧毀其中之一即可達(dá)到目的。為完成此項(xiàng)任務(wù)的汽油消耗量限制為48000升、重

型炸彈48枚、輕型炸彈32枚。飛機(jī)攜帶重型炸彈時每升汽油可飛行2千米，帶輕

型炸彈時每升汽油可飛行3千米。又知每架飛機(jī)每次只能裝載一枚炸彈，每出發(fā)轟

炸一次除來回路程汽油消耗（空載時每升汽油可飛行4千米）外，起飛和降落每次

各消耗100升。有關(guān)數(shù)據(jù)如表所示。

禺機(jī)場距禺摧毀可能性

要害部位

（千米）每枚重型彈每枚輕型彈

14500.100.08

24800.200.16

35400.150.12

46000.250.20

為了使摧毀敵方軍事目標(biāo)的可能性最大，應(yīng)如何確定飛機(jī)轟炸的方案，要求建立這

個問題的線性規(guī)劃模型。

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

§1概論

1.1定義

規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模

型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，

往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。

1.2整數(shù)規(guī)劃的分類

如不加特殊說明，一般指整數(shù)線性規(guī)劃。對于整數(shù)線性規(guī)劃模型大致可分為兩

類：

1°變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。

2"變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。

3°變量只能取?；?時，稱之為0-1整數(shù)規(guī)劃。

整數(shù)規(guī)劃特點(diǎn)

（錯誤！未找到引用源。）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其

整數(shù)規(guī)劃解出現(xiàn)下述情況：

-13-

錯誤！未找到引用源。原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性

規(guī)劃最優(yōu)解一致。

錯誤！未找到引用源。整數(shù)規(guī)劃無可行解。

例1原線性規(guī)劃為

minz=xi+x2

s.t.2x,+4X2=5,x,>0,x2>0

其最優(yōu)實(shí)數(shù)解為：x,=0,x,=—,minz=—.

44

錯誤！未找到引用源。有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值一定不會

優(yōu)于原線性規(guī)劃的最優(yōu)值。

例2原線性規(guī)劃為

minz=X,+x2

s.t.2/+4X2=6,x,>0,x2>0

.33

其最優(yōu)實(shí)數(shù)解為：x,=0,x=—,minz=—?

2■22

若限制整數(shù)得：x,=1,x2=1,minz=2。

（錯誤！未找到引用源。）整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡單取整而獲

得。

1.3求解方法分類：

（錯誤！未找到引用源。）分枝定界法一可求純或混合整數(shù)線性規(guī)劃。

（錯誤！未找到引用源。）割平面法一可求純或混合整數(shù)線性規(guī)劃。

（錯誤！未找到引用源。）隱枚舉法一求解“0-1”整數(shù)規(guī)劃：

錯誤！未找到引用源。過濾隱枚舉法；

錯誤！未找到引用源。分枝隱枚舉法。

（錯誤！未找到引用源。）匈牙利法一解決指派問題（“0-1”規(guī)劃特殊情形）。

（錯誤！未找到引用源。）蒙特卡洛法一求解各種類型規(guī)劃。

下面將簡要介紹常用的幾種求解整數(shù)規(guī)劃的方法。

§2分枝定界法

對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的可行解空間恰當(dāng)?shù)剡M(jìn)行系

統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小

的子集，稱為分枝；并且對每個子集內(nèi)的解集計(jì)算一個目標(biāo)下界（對于最小值問題）,

這稱為定界。在每次分枝后，凡是界限不優(yōu)于已知可行解集目標(biāo)值的那些子集不再

進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思

路。

分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在二十世紀(jì)六十年代初由

LandDoig和Dakin等人提出。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它

已是解整數(shù)規(guī)劃的重要方法。目前已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員

問題、工廠選址問題、背包問題及分配問題等。

設(shè)有最大化的整數(shù)規(guī)劃問題A,與它相應(yīng)的線性規(guī)劃為問題8,從解問題8開

始，若其最優(yōu)解不符合A的整數(shù)條件，那么8的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函

-14-

數(shù)z*的上界，記作彳；而A的任意可行解的目標(biāo)函數(shù)值將是z*的一個下界工。分枝

定界法就是將8的可行域分成子區(qū)域再求其最大值的方法。逐步減小彳和增大z,

最終求到z*?，F(xiàn)用下例來說明：

例3求解下述整數(shù)規(guī)劃

Maxz=40X（+90X2

9匹+7X2<56

s.t.<7X]+20X2>70

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

解（錯誤！未找到引用源。）先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃8,得

最優(yōu)解為：

x,=4.8092,々=1.8168,4=355.8779

可見它不符合整數(shù)條件。這時z是問題A的最優(yōu)目標(biāo)函數(shù)值Z*的上界，記作I而

X1=0,%=0顯然是問題A的一個整數(shù)可行解，這時z=0,是z*的一個下界，記

作即04z*4356。

（錯誤！未找到引用源。）因?yàn)楫?dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任

選一個進(jìn)行分枝。設(shè)選為進(jìn)行分枝，把可行集分成2個子集：

%,<[4.8092]=4,%,>[4.8092]+1=5

因?yàn)?與5之間無整數(shù)，故這兩個子集內(nèi)的整數(shù)解必與原可行集合整數(shù)解一

致。這一步稱為分枝。這兩個子集的規(guī)劃及求解如下：

問題用：Maxz=40x1+90X2

9玉+7X2<56

s.t.<7x,+20X2>70

0<x,<4,X2>0

最優(yōu)解為：X1=4.0,x2=2.1,Z1=349?

問題B2:Maxz=40玉+90X2

9玉+7X2<56

s.t.<7X]+20X2>70

%>5,x2>0

最優(yōu)解為:玉=5.0,x2=1.57,Z]=341.4。

再定界：0<z*<349。

（錯誤！未找到引用源。）對問題用再進(jìn)行分枝得問題練和與2，它們的最優(yōu)

解為

8]I:X[=4,%=2,石1=340

%:%1=1.43,x2=3.00,Z,2=327.14

再定界：340Wz*K341,并將用2剪枝。

（錯誤！未找到引用源。）對問題當(dāng)再進(jìn)行分枝得問題魚|和§22,它們的最優(yōu)

-15-

解為

:X］=5.44,x,=1.00,z,2=308

斗2無可行解。

將與21，822剪枝。

于,可以斷定原問題的最優(yōu)解為：

xt—4,x2-2,z=340

從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃(最大化)問題的步驟為：

開始，將要求解的整數(shù)規(guī)劃問題稱為問題A,將與它相應(yīng)的線性規(guī)劃問題稱為

問題8。

(錯誤！未找到引用源。)解問題B可能得到以下情況之一：

(a)8沒有可行解，這時A也沒有可行解，則停止.

(b)8有最優(yōu)解，并符合問題A的整數(shù)條件，8的最優(yōu)解即為A的最優(yōu)解，

則停止。

(c)8有最優(yōu)解，但不符合問題A的整數(shù)條件，記它的目標(biāo)函數(shù)值為彳.

(錯誤！未找到引用源。)用觀察法找問題A的一個整數(shù)可行解，一般可取

X,=0,/=1,…，試探，求得其目標(biāo)函數(shù)值，并記作z。以Z"表示問題A的最優(yōu)

目標(biāo)函數(shù)值；這時有

z<z*<z

進(jìn)行迭代。

第一步:分枝，在6的最優(yōu)解中任選一個不符合整數(shù)條件的變量勺，其值為%,

以［%］表示小于身的最大整數(shù)。構(gòu)造兩個約束條件

Xj<\bj］和Xj>［&J+1

將這兩個約束條件，分別加入問題8,求兩個后繼規(guī)劃問題與和不。不考慮整數(shù)

條件求解這兩個后繼問題。

定界，以每個后繼問題為一分枝標(biāo)明求解的結(jié)果，與其它問題的解的結(jié)果中，

找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界彳。從已符合整數(shù)條件的各分支中，找出

目標(biāo)函數(shù)值為最大者作為新的下界工,若無作用4=0。

第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于z者，則剪掉這枝，

即以后不再考慮了。若大于z，且不符合整數(shù)條件，則重復(fù)第一步驟.一直到最后

得到z*=工為止。得最優(yōu)整數(shù)解x；,j=1,…,〃。

§30-1型整數(shù)規(guī)劃

0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量與僅取值0或L這時與

稱為0-1變量，或稱二進(jìn)制變量。勺僅取值0或1這個條件可由下述約束條件：

0<<1,整數(shù)

所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實(shí)際問題中，如果引入0-1

變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論

了。我們先介紹引入0-1變量的實(shí)際問題，再研究解法。

-16-

3.1引入0-1變量的實(shí)際問題

3.1.1投資場所的選定一一相互排斥的計(jì)劃

例4某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置(點(diǎn))

4a=1,2,…,7)可供選擇.規(guī)定

在東區(qū)：由A1,三個點(diǎn)中至多選兩個；

在西區(qū)：由A4,4兩個點(diǎn)中至少選一個；

在南區(qū)：由兩個點(diǎn)中至少選一個。

如選用4點(diǎn)，設(shè)備投資估計(jì)為〃.元，每年可獲利潤估計(jì)為q.元，但投資總額不

能超過8元。問應(yīng)選擇哪幾個點(diǎn)可使年利潤為最大？

解題時先引入0—1變量xg=1,2,…,7)

令

1,當(dāng)4點(diǎn)被選中，

x,=<i=1,2,…,7.

[0,當(dāng)&點(diǎn)沒被選中.

于是問題可列寫成：

7

Maxz=Zcixi

i=\

7

-B

i=l

s.t.<x,+x2+x3<2

x4+x5>1

x64-x7>1,x.-0或1

3.1.2相互排斥的約束條件

①有兩個相互排斥的約束條件

5x}+4X2<24或7X[+3X2<45。

為了統(tǒng)一在一個問題中，引入0-1變量y,則上述約束條件可改寫為：

5x}+4X2<24+yM

<7%j+3X2<45+(1-y)M

y=0或1

其中M是充分大的數(shù)。

②約束條件

M=0或500<<800

可改寫為

500y<x{<800y

y=0或1

③如果有〃?個互相排斥的約束條件：

+???+ainxn</?,i=1,2,…，m

-17-

為了保證這〃？個約束條件只有一個起作用，我們引入〃2個0-1變量

=1,2,…,⑼和一個充分大的常數(shù)M,而下面這一組加+1個約束條件

%為+-?■+ainxn<"+y,Mi=1,2,

(1)

M+…+>m=加-1

(2)

就合于上述的要求。這是因?yàn)?，由?2),〃?個y中只有一個能取。值，設(shè)%,=0,

代入(1),就只有i=r的約束條件起作用，而別的式子都是多余的。

3.1.3關(guān)于固定費(fèi)用的問題(FixedCostProblem)

在討論線性規(guī)劃時，有些問題是要求使成本為最小。那時總設(shè)固定成本為常數(shù),

并在線性規(guī)劃的模型中不必明顯列出。但有些固定費(fèi)用(固定成本)的問題不能用

一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決，見下例。

例5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的

生產(chǎn)方式投資高(選購自動化程度高的設(shè)備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品

的變動成本就降低；反之，如選定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動

成本可能增加。所以必須全面考慮。今設(shè)有三種方式可供選擇，令

X,表示采用第，種方式時的產(chǎn)量；

C,表示采用第/種方式時每件產(chǎn)品的變動成本；

的表示采用第/種方式時的固定成本。

為了說明成本的特點(diǎn)，暫不考慮其它約束條件。采用各種生產(chǎn)方式的總成本分

別為

k；+c；x；,當(dāng)x；〉0

J=1,2,3.

,[0,當(dāng)Xj=0

在構(gòu)成目標(biāo)函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入0-1變量為，令

1,當(dāng)采用第/種生