MBA運籌學講義課件

MBA《運籌學》講義

運籌學是一門應用科學，它廣泛應用現(xiàn)代科學技術(shù)知識、用定量分析

的方法，解決實際中提出的問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。

運籌學的核心思想是建立在優(yōu)化的基礎上。

例如，在線性規(guī)劃中體現(xiàn)為兩方面：

(1)對于給定的一項任務，如何統(tǒng)籌安排，使以最少的資源消耗去完

成？

(2)在給定的一定數(shù)量的資源條件下，如何合理安排，使完成的任務

最多？

運籌學解決問題的主要方法是用數(shù)學模型描述現(xiàn)實中提出的決策問

題，用數(shù)學方法對模型進行求解，并對解的結(jié)果進行分析，為決策提供科

學依據(jù)。

隨著計算機及計算技術(shù)的迅猛發(fā)展，目前對運籌學的數(shù)學模型的求解

已有相應的軟件。因此，在實際求解計算時?？山柚谲浖谟嬎銠C上進

行，這樣可以節(jié)省大量的人力和時間。

第一部分線性規(guī)劃內(nèi)容框架

可行解、最優(yōu)解

基本解、基可行解

'?基本最優(yōu)解

一基本方法

圖解法

「原始單純形法

單純形法一「大M法

-人工變量法一

［對偶單純形法I兩階段法

-----------「寸偶理論

T進一步討論I—

L靈敏度分析一參數(shù)規(guī)劃*

」在經(jīng)濟管理領域內(nèi)應用

，__________運輸問題(轉(zhuǎn)運問題)

特殊的LP問題整數(shù)規(guī)劃

「多目標LP問題*

第一部分線性規(guī)劃(LinearProgramming)

及其應用

第一章LP問題的數(shù)學模型與求解

§1LP問題及其數(shù)學模型

(-)弓I例1(生產(chǎn)計劃的問題)

某工廠在計劃期內(nèi)要安排生產(chǎn)I、II的兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品

所需的設備臺時，A、B兩種原材料的消耗以及每件產(chǎn)品可獲的利潤如下表

所示。問應如何安排計劃使該工廠獲利最多？

III資源限量

設備128（臺時）

原材料A4016(kg)

原材料B0412(kg)

單位產(chǎn)品利潤（元）23

該問題可用一句話來描述，即在有限資源的條件下，求使利潤最大的

生產(chǎn)計劃方案。

解：設XI,X2分別表示在計劃期內(nèi)生產(chǎn)產(chǎn)品I、II的產(chǎn)量。由于資源的

限制，所以有：

機器設備的限制條件：XI+2X2W8-,

原材料A的限制條件：4xi^l6（稱為資源約束條件）

原材料B的限制條件：4x2^12-

同時，產(chǎn)品I、II的產(chǎn)量不能是負數(shù)，所以有

xi20,X220（稱為變量的非負約束）

顯然，在滿足上述約束條件下的變量取值，均能構(gòu)成可行方案，且有

許許多多。而工廠的目標是在不超過所有資源限量的條件下，如何確定產(chǎn)

量XI,X2以得到最大的利潤，即使目標函數(shù)

Z=2XI+3X2的值達到最大。

綜上所述，該生產(chǎn)計劃安排問題可用以下數(shù)學模型表示：

maxz=2x1+3x2

x.+2兒<8

IX

4x<16

s.t.t

4X2<12

x1-x2>0

引例2.（營養(yǎng)配餐問題）

假定一個成年人每天需要從食物中獲取3000卡路里熱量，55克蛋白質(zhì)

和80（）毫克鈣。如果市場上只有四種食品可供選擇，它們每千克所含熱量和

營養(yǎng)成份以及市場價格如下表所示。問如何選擇才能滿足營養(yǎng)的前提下使

購買食品的費用最?。?/p>

序號食品名稱熱量（卡路里）蛋白質(zhì)（克）鈣(mg)價格（元）

1豬肉10005040010

2雞蛋800602006

3大米900203003

4白菜2001()5002

解:設Xj（j=l,2,3,4）為第j種食品每天的購買量，則配餐問題數(shù)學模型為

minz=1Ox16x23x32x4

1OOOOx,+800X2+900X3+200x4>3000

50x)+60X2+20X3+10x4>55

400.r)4-200X2+300x3+500%>800

Xj>(X,7=1,2,3,4)

（-）LP問題的模型

上述兩例所提出的問題，可歸結(jié)為在變量滿足線性約束條件下，求使

線性目標函數(shù)值最大或最小的問題。它們具有共同的特征。

（1）每個問題都可用一組決策變量（X],X2,…Xn）表示某一方案，其具體

的值就代表一個具體方案。通?？筛鶕?jù)決策變量所代表的事物特點，可對

變量的取值加以約束，如非負約束。

（2）存在一組線性等式或不等式的約束條件。

（3）都有一個用決策變量的線性函數(shù)作為決策目標（即目標函數(shù)）,

按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化。

滿足以上三個條件的數(shù)學模型稱為LP的數(shù)學模型，其一般形式為：

max（或min）z=c1x1+02x2+,?,+CnXn

（1.1）

-%也+〃12匕+…+

。2112+。22*2<（=，N）"

S.t...............（1.2）

4/2+32+???+am<（=，滋

（1.3）

_…2.f2°

或緊縮形式

max（或min）z=，C.X.

J=I

<（=,〉）〃（，=1,2,??,,加）

耳（1.4）

x.>0

一J

或矩陣形式

max（或min）z=cx

AX<（=>）b

（1.5）

X>0

或向量形式:

max（或min）z=cx

，PjXjW(=，N)b

(1.6)

x/>0=

其中C=(C1,C2,…,Cn),稱為價值系數(shù)向量；

——.

ciCL…a

A="2I，"22，???“2”稱為技術(shù)系數(shù)矩陣(并稱消耗系數(shù)矩陣)

，加1，a”12'…。"徵_

=(pi,P2,---,Pn)

b、

b=,2稱資源限制向量

■

b

Lm」

X=(X|,X2,…,Xn)T稱為決策變量向量。

(三)LP問題的標準型

1.為了討論LP問題解的概念和解的性質(zhì)以及對LP問題解法方便，必須

把LP問題的一般形式化為統(tǒng)一的標準型：

maxz=7CX.；

Jjj

J=i

maxz=cx

=b,(i=1,2,…，m)及AX-b

Xj>0(y=1,2，…,〃)_X2°

maxz=cx

z“

pN-pf

J.

>.h2

X-;=lZ=:

J-0(

標準型的特點：

①目標函數(shù)是最大化類型

②約束條件均由等式組成

③決策變量均為非負

2.化一般形式為標準型

@minz—>max(-z)=-cx

②—左邊+松馳變量；f左邊一“松馳變量”

③變量xjWO—>-Xj20變量xj無限制—>令Xj=xj'—xj〃

④bi<0一等式兩邊同乘以(-1)。

3.模型隱含的假設

①比例性假定：決策變量變化的改變量與引起目標函數(shù)的改變量成比

例；決策變量變化的改變量與引起約束方程左端值的改變量成比例。此假

定意味著每種經(jīng)營活動對目標函數(shù)的貢獻是一個常數(shù)，對資源的消耗也是

一個常數(shù)。

②可加性假定：每個決策變量對目標函數(shù)和約束方程的影響是獨立于

其它變量的。

③連續(xù)性假定：決策變量應取連續(xù)值。

④確定性假定：所有的參數(shù)(aij,bi?)均為確定，所以LP問題是確定型問

題，不含隨機因素。

以上4個假定均由于線性函數(shù)所致。在現(xiàn)實生活中，完全滿足這4個假

定的例子并不多見，因此在使用LP時必須注意問題在什么程度上滿足這些

假定。若不滿足的程度較大時，應考慮使用其它模型和方法。如非線性規(guī)

劃，整數(shù)規(guī)劃或不確定型分析方法。

對LP標準型，我們還假定r(A)=m<n。

(四)LP問題的解的概念

設LP問題

maxz=ZcX(1.7)

j=iJJ

iajxj=〃(i=12???,〃)(1.8)

與20(J=l,2,???2)(19)

1.從代數(shù)的角度看：

可行解和最優(yōu)解滿足約束條件(1.8)和(1.9)的解X=(X|,X2,…,Xn)T稱為

可行解。所有可行解構(gòu)成可行解集，即可行域5={*|4,=4x20}。

而使目標函數(shù)達到最大值的可行解稱為最優(yōu)解，對應的目標函數(shù)值稱為最

優(yōu)值。

求解LP問題就是求其最優(yōu)解和最優(yōu)值，但從代數(shù)的角度去求是困難

的。

2.從LP角度看：

基:設A為mxn矩陣,r(A)=m,B是A中的mxm階非奇異子矩陣(即

則稱B是LP問題的一個基。

若B是LP問題的一個基，則B由m個線性獨立的列向量組成，即

B二(Prl,Pr2,…,Prm),其中Prj=(ai"2rj,…,amrj)'=…,m)稱為基向理。與其

向量Prj相對應的變量Xrj稱為基變量，其它變量稱為非基變量。顯然，對應

于每個基總有m個基變量，n—m個非基變量。

基本解與基可行解設B是LP問題的一個基，令其n—m個非基變量均

為零，所得方程的解稱為該LP問題的一個基本解。顯然，基B與基本解是

對應的，基本解的個數(shù)在基本解中，稱滿足非負條件的基本解

為基可行解，對應的基稱為可行基。

退化解如果基解中非零分量的個數(shù)小于m,則稱此基本解為退化

的，否則是非退化的。

最優(yōu)基如果對應于基B的基可行解是LP問題的最優(yōu)解，貝稱B為LP

問題的最優(yōu)基，相應的解又稱基本最優(yōu)解。

3.LP問題解之間的關(guān)系如圖所示

（五）兩個變量LP問題的圖解法

1.LP問題解的幾何表示。以引例為例說明

maxz=2xi+3x2

,+2X2<8①

4玉<16②

4X2<12③

A：1>0,x2>0④

按以下順序進行：

解：（1）畫出直角坐標系；

（2）依次做每條約束線，標出可行域的方向，并找出它們共同的

可行域：

（3）任取一目標函數(shù)值作一條目標函數(shù)線（稱等值線），根據(jù)目標

函數(shù)（最大或最?。╊愋?，平移該直線即將離開可行域上，則與目標函數(shù)

線接觸的最終點即表示最優(yōu)解。

圖1

21

其中，將目標函數(shù)Z=2XI+3X2改寫為羽=——X+-Z,因此，它可

-33

以表示為：以z為參數(shù)，以一2為斜率的一族平行線。位于同一條直線上的

3

點具有相同的值。

解的幾種情況：

（1）此例有唯一解Q2,即XI=4,X2=2,z=14

（2）有無窮多最優(yōu)解（多重解），若將目標函數(shù)改為Z=2XI+4X2則線段

Q2,Q3上的點均為最優(yōu)解。

（3）無界解

求max無界

但求min有唯一解

可行域與最優(yōu)解間的關(guān)系:

可行域最優(yōu)解

空集A無最優(yōu)解（無可行解）

有界唯一最優(yōu)解

多重解

無界集A無有限最優(yōu)解（無界解）

結(jié)論：（1）LP問題的可行域是凸集（凸多邊形，凸多面體，…）;

（2）LP問題最優(yōu)解若存在，則必可在可行域的頂點上得到；

（3）LP問題的可行域的頂點個數(shù)是有限的；

（4）若LP問題有兩個最優(yōu)解，則其連線上的點都是最優(yōu)解。因

此，求解LP問題可轉(zhuǎn)化為如何在可行域的頂點上求出使目標函數(shù)值達到最

優(yōu)的點的問題。

2.基可行解的幾何意義

對例1LP問題標準化為maxZ=2x1+3x2

陽

4-2X24-X3=8

再

4+x4=16

4X2+x5=12

_再,…，2NO

可求得所有的基本解：

x⑴二（（）,0,8/6,12"0點）,x⑵=（4,（）,4,0』2）T（QI點）

x（3）=（4,2,0,0,4）T（Q2點）,x（4）=（2,3,0,8,0）T（Q3點）

x⑸二（0,3,216,0）1'94點）46）=（43?2,0,0尸（。點）

x⑺二（8,0,0,?16,12）T（A點）,x（8）=（0,4,0,16,-4）T（B點）

但A、B、C三點是非可行域上的點，即非可行解。因此，x（,）,x（2）,x（*

乂⑷，x⑸才是基可行解，它們與可行域的頂點相對應。于是還有

結(jié)論：（5）對于標準型的LP問題，X是基可行解的充要條件是X為可行

域的頂點。

（6）LP問題可行域頂點的個數(shù)=基可行解的個數(shù)〈基的個數(shù)這C%

3.圖解法只適用于兩個變量（最多含三個變量）的LP問題。

4.求解LP問題方法的思考：

①完全枚舉法，對m、n較大時，C%是一個很大的數(shù)，幾乎不可能；

②從可行域的一個頂點（基可行解）迭代到另一個頂點（基可行解）0

§2單純形法與計算機求解

1.解LP問題單純形法的基本思路：

2.單純形法的計算步驟(表格形式)

(1)建立初始單純形表，假定B=I,b20

設maxZ=cix1+02x2+,,,+cnXn

-

x+萬麗/+1+.-4〃居=bi_

X2+~％+???％%=%

\;

+…=吼

Xj>0(j=1,2,???,/?)

將目標函數(shù)改寫為：-Z+C1X1+C2X2+…+CnXn=0

把上述方程組和目標函數(shù)方程構(gòu)成n+1個變量，m+1個方程的方程組,

并寫成增廣矩陣的形式:

-ZXIX2XmXm+1…Xnb

<010…0Cl1m+1…aInbh

001…0Cl2m+1…-2nb2

000…1Clmm+i…ClmnZ?m

1-10J

ClC2CmCm+1**?Cn

以非基變量表示基變量形式七=八￡%當代入Z中的基變量，有

./=!

加〃〃

Z=￡cg-工瓦心口+￡5

J-1y-/H4-1

mm〃”

C?w+Ef

i=\/=!j=〃i+Tj=m+\

"i〃加

=SCA-S①弓為一⑺吃

/=!j=m+t/=1

mm

令Zo=23，Zj=￡c@ij

i=\?=1

于是Z=Z,,+之(Zj-Cj)Xj

J=W+I

因此，上述的增廣矩陣就可寫成:

zXIX2XmXm+l***Xnb

<010…0alm+1,,,ciIn心、

001…0萬2m+l…a2nbi

000…1Clmm+1***Clmnbm

11nim

00…0匯哂用一明…Z“加一CnZw

;=1/=1/=!)

m

再令bj=Cj-Z.=c.f

1=1

則上述增廣矩陣可寫成下面表格形式：即初始單純形表T(B)

11

CjCrCmCm+1Cn

6i

CBXBbXIXmXm+1Xn

ClXIbi1……0aim+1Uln

C2X2b20……032m+la2n

?*?.???*??

CmXmbm0........1amm+13mn

zZo0……0CTm+1CJn-5檢驗數(shù)行

上述初始單純形表可確定初始可行基和初始基可行解：

B=(P1,P2,…,Pm)=LX=(bl,b2,…,bm,0........0)T

從初始單純形表建立的過程可以看到以下事實：

(1)凡LP模型中約束條件為型，在化為標準型后必有B=I,如

果b20,則模型中約束方程的各數(shù)據(jù)不改變符號照抄在表中相應的位置。

目標函數(shù)非基變量的系數(shù)則以相反數(shù)填入檢驗數(shù)行各相應位置。

(2)在單純形表中，凡基變量所在的列向量必是單位列向量，其相應

的檢驗數(shù)均為零。

⑶z0=￡皿巴=Zq周一。+1，…〃)

J-lI

更好表現(xiàn)一般規(guī)律的在矩陣形式的單純形表中

設MaxX二CXMaxZ=CX+OXL

A<b「A+Zr,=〃

“其標準型為“L

x20x,xL>0

將系數(shù)矩陣(A,I)分劃為(B,NJ),其中B為可行基，對應于基變量向量

XB,N對應于XN,I對應于XL,(XN,XL)為非基變量向量。于是

(X,L)T=(XB,XN,XL)T,(C,0)=(CB,CN,0)O因此，矩陣形式的LP模型改寫為:

乂一

MaxZ=G，CN,0)XNMaxZ=CBXB+CNXN+0XL

_X-

=b「陽++區(qū)=b

XN

F[XB，XN，XLN0

XL

LxB.xN,xL>o

用非基變量向量表示基變量向量，有

,11

XB=B-b-BNXN-BXL

代入目標函數(shù)中有

Z=CB(B/b-B,NXN-B/XL)+CNXN+OXL

=CBB/b-CBB」NXN—CBB/XL)+CNXN

二CBB"b-(CBB"N-CN)XN-CBB"XL

將

ll

Z+(CBB~'N-CN)XN+CBB~XL=CBB~b

XR+BNXN+B7X[=B~xb

寫成對應于基B的矩陣形式的單純形表T(B)：

CfCBCNCL

bXBXNXL

B[b

XB1B'NBi

ZCBB-七0CBB'N-CNCBB1

例如將例1化成標準型后如下表T(B)：

G23000

0i

CBXBhXIX2X3X4X5

0X3812100

0X41640010

0X51204001

-Z0-2-3000<-°j

初始可行基B=(P3,P4,P5)=LX=(0,0,8,16,12)T

(2)判別最優(yōu)解

1°在T(B)中，若所有的檢驗數(shù)。jN0(j=l,2,…,n)

貝IJB為最優(yōu)基，相應的基可行解為最優(yōu)解，停止計算。

2°在T(B)中，若有。k<0(l《k〈n),且Xk的系數(shù)列向量PkWO,則該問題

無界，停止計算。否則轉(zhuǎn)入(3)

(3)換基迭代(基變換)

1°先確定入基變量Xk：k=min{j|Qj<0}

2°按最小比值原則確定出基變量XL：

0=min工|aik>0=

3°以24為主元，進行初等行變換(又稱旋轉(zhuǎn)變換)即將列向量外變

換為單位列向量：

返回(2)o

換基迭代的關(guān)鍵在于將換入變量對應的列向量R用初等行變換方法

變換成單位列向量。其中主元萬比變成1。即

0

a2k0

PkT■第L個分量

1

%0

如果在最終表中有非基變量的檢驗數(shù)為o,則該問題有多重最優(yōu)解。

3.單純形法的進一步討論——用人工變量法求初始基可行解

（一）人工變量法

若對LP模型標準化后，不具有B=I時，如何辦？此時可采用人工變量

法得到初始基可行解。

所謂人工變量法是在原問題不含有初始可行基B=I的情況下，人為的對

約束條件增加虛擬的非負變量（即人工變量），構(gòu)造出含有B=I的另一個LP

問題后求解。當增加的人工變量全部取值為0時，才與原問題等價。這樣，

新問題將有一個初始基可行解（以人工變量為基變量），可用單純形法進行

迭代。經(jīng)迭代后，若人工變量全部被換成非基變量，則原問題的約京條件

被恢復，同時也得到一個基可行解。在最終表中若不能全部被換出，則說

明原問題無可行解。

因此，該法的關(guān)鍵在于將人工變量全部換出。

人T變量法常見的有大M法和兩階段法.

（1）大M法（通過下例簡略介紹其方法與步驟）

例，用大M法求解

MinZ=xi+1.5x2

24-3X2>3

X1+x2>2

x1,x2>0

解：MinZ=xi+1.5X2+0.X3+0.X4+MX5+MX6

%+3X2-x3+x5=3

%+%-%+4=2

X],x2>0,x3,x4>0,x5,x6>0

其中X3,X4為松馳變量，X5,X6為人工變量，M為任意大的正數(shù)。

注意到：①分別在約束條件增加人工變量X5,X6是為了構(gòu)成“人工基”

②對于Min的目標函數(shù)采用（+M）,而對于Max的目標函數(shù)則采

用（-M）作為人工變量的系數(shù)，是強加于人工變量的一種懲罰，其目的是為了

強制人工變量由變量轉(zhuǎn)為非基變量，使之恢復原問題，或與原問題等價。

③對于minZ判別最優(yōu)性準則應是G-ZjWO。

④大M法適合于手算，不適用于計算機求解。

（2）兩階段法

第一階段：不考慮原問題是否存在基可行解；給原LP問題的約束條件

加入人工變量，構(gòu)造僅含人工變量的目標函數(shù)并要求實現(xiàn)最小化（即使原

LP問題目標函數(shù)是求最大化）的輔助問題：

MinW=Xn+1+…+Xn+m

-…+丁二=b、

am\.x1+???+<7mnxn+x=bm

x1,',.......xn+m>0

然后用單純形法求解（Do若WM,則原問題無可行解，停止計算。

若w=o,且所有的人工變量均為非基變量，則去掉人工變量后可得到原問

題的基可行解；如果人工變量中含有為0的基變量時(即退化解)，則可再

進行初等行變換將其換出，從而獲得原問題的基可行解。

第二階段：在第一階段所得的基可行解的基礎上，將最終表中的人工

變量列刪去，同時將人工日標函數(shù)行換入原問題的目標函數(shù)作為笫二階段

計算的初始表。

仍以上例為例用兩階段法求解。

MinZ=xi+1,5x2+0x3-0x4

+3X2-=3

原問題:玉+x2-x4=2

xpx2>O,x3,x4>0

MinW=X5+x6

X)+3/—玉+x5=3

輔助問題:xi+x2-x4+4=2

xpx2>0,x3,x4>0,x5,x6>0

書中第19頁表2.9和表2.10的說明：(1)第一階段的初始表中非基變量

的檢驗數(shù)=人工變量所在行的非基變量相應系數(shù)之和，目標函值值二人工變

量所在行相應常數(shù)之和。

(2)第二階段單純形表中目標函數(shù)系數(shù)應將非基變量表示基變量后所

得結(jié)果填入，或先直接填入原系數(shù)，再通過初等行變換使基變量的檢驗數(shù)

為0。

(3)若maxZ,則可轉(zhuǎn)化為minZ1(Z1=?Z)

(二)退化

單純形法計算中用。規(guī)則決定換出變量時，有時出現(xiàn)兩個以上相同的最

小比值，這樣在下一次迭代中就有一個或幾個基變量等于0,出現(xiàn)退化解，

如某個最大化問題的單純形表為：

Cj403000

Oi

CBXBbXIX2X3X4X5X6

0X562010103

0X43[1]-101003

0X651110015

z0-40-3000-5

0X500[2]1-2100

4XI31-10100/

0X63021-1011

Z120-4-3400-5

在出現(xiàn)退化解后的繼續(xù)迭代中，有可能已現(xiàn)基循環(huán):

BI->B2->.......->Bi

這樣迭代下去便永遠得不到最優(yōu)解。

解決基循環(huán)的方法很多，如“攝動法”、“字典序法”等等。

在計算機上常采用“Bland規(guī)則”：

(1)取表中下標最小的非基變量Xk為換入變量，即

k=min{j|Qj>0}

(2)按。規(guī)則計算，若存在兩個相同以上最小比值時，選取下標最小

的基變量為換出變量XL,即

L=minr\0r-min{鄉(xiāng)|aik>0}

值得慶幸的是出現(xiàn)基循環(huán)是罕見的。

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

一、LP的對偶問題

1.引例前己述引例1是一個在有限資源的條件下，求使利潤最大的生

產(chǎn)計劃安排問題，其數(shù)學模型為：

maxZ=2xI+3X2

■%,+2%K8（設備）

4二416（原材料A）

（原材料）

4Y2<12B

一兒1，兒1>0

現(xiàn)從另一角度考慮此問題。假設有客戶提出要求，租賃工廠的設備臺

時和購買工廠的原材料A、B,為其加工生產(chǎn)別的產(chǎn)品，由客戶支付臺時費

和材料費，此時工廠應考慮如何為每種資源的定價問題？

解：設y\y2,y3分別表示出租單位設備臺時的租金和出售單位原材料A、

B的價格（含附加值）

工廠決策者考慮：

（1）出租設備和出售原材料應不少于自己生產(chǎn)產(chǎn)品的獲利，否則不如

自己生產(chǎn)為好。因此有

-Y+4%>2

_2y+4%>3

工廠的總收入為W=8yi+16y2+12y3

（2）價格應盡量低，否則沒有競爭力（此價格可成為與客戶談判的底

價）

租賃者考慮：希望價格越低越好，否則另找他人。

于是，能夠使雙方共同接受的是

MinW=8yi+16y2+12y3

-y+4y2>2

十

s.t2yt4y3>3

J?”,K20

上述兩個LP問題的數(shù)學模型是在同一企業(yè)的資源狀況和生產(chǎn)條件下

產(chǎn)生的，且是同一個問題從不同角度考慮所產(chǎn)生的，因此兩者密切相關(guān)。

稱這兩個LP問題是互為對偶的兩個LP問題。其中一個是另一個問題的對偶

問題。

2.從矩陣形式討論互為對偶LP問題

由例1有maxZ=ex

~YX<b

X>0

由矩陣形式的單純形表中可知：

檢驗數(shù)的表達式為：CBB-N-CN和CBB"

1

ICBB-N-CN>0①

L②

表示LP問題已得到最優(yōu)解

☆Y=CBB1,且②有Y2O

由于基變量XB的檢驗數(shù)為0,可改寫成CBB」B—CB=0

因此，包括基變量在內(nèi)的所有檢驗數(shù)可寫成

(CBB^B-CB,CBBN—CN)二(CBB"A-C)=YA—C20

即YANC

又對②Y=CBRL兩邊右乘h.有

Yb=CBB-'b=Z

由于Y無上界，所以只有最小值，因此有

MinW=Yb

~YA>C

y>o

它是原問題{maxZ=CX|AX<b,X>0}的對偶問題

于是，對稱形式下兩個互為對偶LP問題的數(shù)學模型為:

MaxZ=CXMinW=Yb

YX>hYA>C

與

X>Qy>o

任何一個LP問題均有一個對偶LP問題與之匹配。

對偶理論就是研究LP問題及其對偶問題的理論，它是LP理論中的重要

內(nèi)容之一。

二、對偶理論

1.原問題與對偶問題的關(guān)系如下表所示

原始對偶表

原問題Max（對偶問題）對偶問題Min（原問題）

約束條件數(shù)=m變量個數(shù)=111

第i個約束條件為第i個變量20

第i個約束條件為“2”第i個變量W0

第i個約束條件為“二”第i個變量無限制

變量個數(shù)=01約束條件個數(shù)二n

第i個變量20第i個約束條件為

第i個變量W0第i個約束條件為“2”

第i個變量無限制第i個約束條件為

第i個約束條件的右端項目標函數(shù)第i個變量的系數(shù)

目標函第i個變量的系數(shù)第i個約束條件的右端頂

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

MaxZ=CXMinW=Yb

\YX<b「??。

設

_X>0\_Y>0

（i）（對稱性）對偶問題的對偶是原問題；

（2）（弱對偶性）若又是原問題的可行解，「是對偶問題的可行解；

則CNW匹；

（3）（無界性）若原問題（對偶問題）為無界解，則其對偶問題（原

問題）無可行解；

（4）（最優(yōu)性準則），若又、「分別是互為對偶問題的可行解，且

CX=Yb,則又、「分別是它們的最優(yōu)解；

（5）（對偶定理）若互為對偶問題之一有最優(yōu)解，則另一問題必有最

優(yōu)解，且它們的目標函數(shù)值相等。

從上述性質(zhì)中，可看到原問題與對偶問題E勺解必然是下列二種情況之一：

①原問題與對偶問題都有最優(yōu)解，且CX二Yb；

②一個問題具有無界解，則它的對偶問題無可行解；

③兩個問題均無可行解。

（6）（互補松馳性），若X*、Y*分別是原問題的對偶問題的可行解，則

X*、Y&是最優(yōu)解的充要條件是：Y*Xs=O,YsX'O（其中Xs,Ys分別是原問題和

對偶問題的松馳變量向量）?；?，X*、Y*分別是原問題和對偶問題最優(yōu)解的

充要條件是：

①若y*i>0,則EaijX*j=bi

②若ZaijX*j<b,則y彳=0

③若X*j>0,則Zaijy"尸Cj

④若Zaijy*i>Cj,則X：=0

三、對偶單純形法

1.單純形法的重新解釋

X*是最大化原LP問題最優(yōu)解的充要條件是同時滿足

l

-B-b>o①（稱為原始可行條件）

X

CBB~N-CN>0②（稱為對偶可行條件）

因此，單純形法是在保持原始可行下，經(jīng)過迭代，逐步實現(xiàn)對偶可行,

達到求出最優(yōu)解的過程。

根據(jù)對偶問題的對稱性，也可以在保持對偶可行下，經(jīng)過迭代，逐步

實現(xiàn)原始可行，以求得最優(yōu)解。對偶單純形法就是這種思想所設計的。

2.對偶單純形法的計算步驟：

舉例說明

3.對偶單純形法與單純形法的不同之點:

①不要求模型中b20

②先確定換出變量XL,再確定換入變量XK

（3）6>=min<0=區(qū)

7L%J

4.對偶單純形法適用對象

①maxZ=CX（C<0）②maxZ=CX

AX=bAX=h（，）

（b無限制），I⑴?=12??"

X>0X>0

③當變量個數(shù)（約束個數(shù)時，可先轉(zhuǎn)化為其對偶問題，再用單純形法

或?qū)ε紗渭冃畏ń庵?/p>

④進行靈敏度分析時，有時會用到此法

四、對偶解的經(jīng)濟含義和影子價格

1.對偶解Y木二CBB1的經(jīng)濟含義

設互為對偶的LP問題

maxZ=CXminW=Yb

~AX<b

（原）（對）

X>0[Y>0

有Z*=CBB」b=W*（其中B為最優(yōu)基）

夕*

因此——=G,B=丫*

db'

或者說Z*=y*B+y*2b2+y*mbm

則三，二y

明

其含義是：若對原問題右端常數(shù)項向量b中的某一常數(shù)項b增加一個單

位，目標函數(shù)的最優(yōu)值Z*的變化將是Yi*。換句話說，Yi*表示當bi增加一個

單位時，目標函數(shù)最優(yōu)值的相應增量。實質(zhì)上丫涔就是第i種資源邊際價值

的一種表現(xiàn)，也是對第i種資源的一種估價。

事實匕如引例中巨為對偶LP問題分別描述生產(chǎn)計劃問題和資源的定

價問題，其數(shù)學模型分別是：

maxZ=2x1+3x2minW=8yi+16y2+12y3

x.+2工<8

ILy+4”>2

4%<16

(原問題)（對偶問題）2y+4>3>3

4工<12

X，%>°，，3>0

X],工>0

對原問題用單純形法求解所得最終表為

C23000

CBXBbXIX2X3X4X5

2XI41001/40

0X5400-21/21

3X22011/2-1/80

Z14001.50.1250

由此，它們的最優(yōu)解分別是X*=(4,2)T和Y=(1.5,0.125,0)

Z*=W*=14=8Yi*+16Y2*12Y3*

wSZ*「33Z*八….SZ*八

yj、=----=1.5,y）*=------=0.125,=-----=0

1的2db.3dh

其中Y1*=L5表示單獨對設備臺時增加1個單位，可使Z值增加1.5個單

位的利潤；丫2*=0.125表示單獨對原材料A增加1個單位，可使Z值增加0.125

個單位的利潤；而Y3a=0表示單獨對原材料B增加一個單位，卻不使Z值增

加。這是因為從最終表中可看出，在最優(yōu)方案中，松馳變量X5=4,即表示

在最優(yōu)生產(chǎn)方案中，原材料B尚有4個單位剩余被閑置，不產(chǎn)生任何經(jīng)濟效

益。

2.影子價格的定義

把某一經(jīng)濟結(jié)構(gòu)中的某種資源，在最優(yōu)決策下的邊際價值稱為該資源

在此經(jīng)濟結(jié)構(gòu)中的影子價格。

影子價格是在最優(yōu)決策下對資源的一種估價，沒有最優(yōu)決策就沒有影

子價格，所以影子價格又稱“最優(yōu)計劃價格”，“預測價格”等等。

資源的影子價格定量的反映了單位資源在最優(yōu)生產(chǎn)方案中為總收益應

提供的收益，因此，資源的影子價格也可稱為在最優(yōu)方案中投入生產(chǎn)的機

會成本。

3.影子價格的求法

(1)在非退化情況下：設B為LP問題的最優(yōu)基，則

資源的影價=Y*=CBB”

(2)在退化情況下：

當對偶問題有K個最優(yōu)解，則第i種資源的影價=｝即影價的

A

第i個分量等于這K個對偶解中第i個分量的最小值。

例如，設某資源利用問題為

maxZ=3xi+x2

(資源邛艮制)

匹+工W2

(資源2限制)

3x1+2X2<6

>0

最終表

3100

XBbXIX2X3X4

XI21110

X400-1[-3]1

Z60230

XI212/301/3

X3001/31-1/3

Z60101

???資源1的影價

=min{yi*(l),yi*(2)}

=min{3,0}=0

資源2的影價=min{y2"⑴,y2*Q)}=min{O,l)=0

4.影子價格的參謀作用

「影價>0,說明單資源已耗盡，

(1)指出企業(yè)挖潛革新的途徑成為短線資源。

影價=0,說明該資源有剩余，

成為長線資源。

(2)對市場資源的最優(yōu)配置起著推進作用

(3)可為企業(yè)決策者提供調(diào)整最優(yōu)生產(chǎn)方案的信息

CBB-E—G<0說明第j種產(chǎn)品應投產(chǎn)

CBB/Pj—Cj>0說明第j種產(chǎn)品不應投產(chǎn)

尤其對新產(chǎn)品是否應投產(chǎn)，可按以上兩式考慮。

(4)可以預測產(chǎn)品的價格

(5)可作為同類企業(yè)經(jīng)濟效益評估指標之一。

五、靈敏度分析

面對市場變化，靈敏度分析的任務是須解決以下兩類問題：

(1)當系數(shù)A、b、c中的某個發(fā)生變化時，目前的最優(yōu)基是否仍最優(yōu)

(即目前的最優(yōu)生產(chǎn)方案是否要變化)？

(2)為保持目前最優(yōu)基仍是最優(yōu)基，參數(shù)A、b、c允許變化范圍是什

么？

靈敏度分析的方法是在目前最優(yōu)基B下進行的。即當參數(shù)A、b、c中的

某一個或幾個發(fā)生變化時，考察是否影響以下兩式的成立？

"B~]h>0

CRB-'N-CNN。

1.對資源數(shù)量br變化的分析

當b中某個br發(fā)生改變時，將影響基變量的取值XB二B」b。若br的變化仍

滿足B-ib20,則目前的基B仍為最優(yōu)基，僅在B」b和CBB-十的數(shù)量上有些改

變。若br的變化使B」b中某些分量小于0,則目前的基成為非可行基，為此,

可用對偶單純形法迭代求得新的最優(yōu)解。

B/b20給出了使最優(yōu)基B保持不變時的允許的變化范圍：

由解不等式組

-0■