MBA《運籌學》講義

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

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

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

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

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

成？

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

最多？

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

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

學依據(jù)。

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

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

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

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

LP問題

L1基本概念一數(shù)學模型「可行解、最優(yōu)解

實際問題*LP問題I解的概念一基本解、基可行解

煽本最優(yōu)解

提出

一基本方法

圖解法

「原始單純形法

單純形法一r大M法

L人工變量法一

對偶單純形法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、H的兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品

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

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

1II資源限量

設備128（臺時）

原材料A4016(kg)

原材料B0412(kg)

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

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

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

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

限制，所以有：

機器設備的限制條件：XI+2X2W8I、

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

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

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

xi20,X2?0（稱為變量的非負約束）

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

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

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

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

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

maxz=2x1+3x2

x]+2X2<8

4%]<16

s.t.

4X2<12

%1?%NO

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

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

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

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

購買食品的費用最??？

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

1豬肉10005040010

2雞蛋800602006

3大米900203003

4白菜200105002

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

minz=1Ox16x28x32x4

lOOOOX1+800々+900x,+200x4>3000

X

50x,+60X2+203+10x4>55

400x,+200X2+3OOX3+500》42800

Xj>0(J=1,2,3,4)

（-）LP問題的模型

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

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

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

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

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

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

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

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

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

max(或min)z=ciXi+C2X2+…+CnXn

(1.1)

+/2%2+…+<(=,>)/?,

a2ix2+a22x2+---+a2nxn<(=,>)b2

s.t.......(1.2)

—+%%+…<(=，之電(1.3)

_X.-x2---x>0

或緊縮形式

max(或min)z=ZCX

j=iJJ

才4'W(=,2)〃(i=1,2,…,M

j=1(1.4)

x>0

_J

或矩陣形式

max(或min)z=cx

NX<(=>)/?

(1.5)

X>0

或向量形式：

max(或min)z=cx

￡p產(chǎn)jW(=,N)b

(1.6)

X/>O=1,2,.??,//)

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

a、]，，…Qi

2w

A=222稱為技術系數(shù)矩陣(并稱消耗系數(shù)矩陣)

，。帆2,…"〃皿_

=(Pl,P2,'",Pn)

飛「

b、

b=：稱資源限制向量

_bm_

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

(三)LP問題的標準型

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

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

maxz=VCX；

Jjj

maxz=cx

=h(i=1,2,…,⑼[AX=h

./=1或C

X.>0(；=1,2,???,?)l_X20

maxz=cx

EPjXj=b

或J=1

X>0(J=1,2,-??,?)

標準型的特點：

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

②約束條件均由等式組成

③決策變量均為非負

④bi(i=l,2,…,n)

2.化一般形式為標準型

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

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

③變量XjWOf-XjNO變量Xj無限制一令Xj=x：—x丁

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

3.模型隱含的假設

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

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

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

一個常數(shù)。

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

其它變量的。

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

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

題，不含隨機因素。

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

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

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

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

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

(四)LP問題的解的概念

設LP問題

maxz=Zc.X.(1.7)

>1

￡%吃=2"=1,2,...,八)(1.8)

>=|

%.>0(J=1,2,--?,?!)(1.9)

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

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

可行解。所有可行解構(gòu)成可行解集，即可行域3={X|A'=〃,％20}。

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

優(yōu)值。

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

的。

2.從LP角度看：

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

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

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

B=(Pr|,Pr2,…,Prm)，其中Prj=(airj,a2中…,am寸)\0=1,2,…,m)稱為基向理。與其

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

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

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

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

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

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

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

的，否則是非退化的。

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

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

3.LP問題解之間的關系如圖所示

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

LLP問題解的幾何表示。以引例為例說明

maxz=2xi+3x2

$+2X2<8①

4x,<16②

4X2<12③

A：,>0,x2>0④

按以下順序進行：

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

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

可行域；

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

函數(shù)（最大或最?。╊愋停揭圃撝本€即將離開可行域上，則與目標函數(shù)

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

圖1

一21

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

-33

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

3

點具有相同的值。

解的幾種情況：

（1）此例有唯一解Q2，即X|=4,X2=2,Z=14

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

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

（3）無界解

可行域與最優(yōu)解間的關系：

可行域最優(yōu)解

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

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

無界集-------------＞無有限最優(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

$+2X2+工=8

4xt+乙=16

4%+4=12

_再,…,％5之0

可求得所有的基本解：

x⑴=(0,0,8/6,12)T(0^),X(2)=(4,0,4,0,12)1QI點)

x°)=(4,2,0,0,4尸92點),x?)=(2,3,0,8,0)T(Q3點)

*°)=(0,3,2,16,0,((24點)46)=(4,3,-2,0,0)19點)

x⑺=(8,0,0,-16,12)T(人點)小岱)=(0,4,0,16,-4)T(B點)

但A、B、C三點是非可行域上的點,即非可行解。因此，x⑴,x⑵，X。),

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

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

域的頂點。

(6)LP問題可行域頂點的個數(shù)=基可行解的個數(shù)W基的個數(shù)

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

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

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

②從可行域的一個頂點(基可行解)迭代到另一個頂點(基可行解)。

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

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

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

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

設maxZ=c1x1+C2X2+…+cnxn

%+4",+1

々+a2m+]xm+l+---a2nx?=b2

X；>0(J=l,2,???,?)

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

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

并寫成增廣矩陣的形式:

-zX|X2""XmXm+1…Xnh

「010…0alm+1…五In

001…0a2m+1…汀2nb2

...1

000〃mm+1…m

l-l0J

ClC2""CmCm+1'??Cn

=。一七%%,代入Z中的基變量，有

以非基變變量量表表示示基基變變量量形形式式X七,.=〃-當代入Z中的基變量，有

7j==1l

Z=-E%Xj)+?jXj

/=1j=ni+\j=m+]

/〃_，n〃.

=EcA-EE(函M+YCJXJ

i=li=\j=m+}j=m+\

-E(ZMLX

i=ly=m+li=l

_，n__，〃

令Zo=￡c及Zj=￡q%

i=lf=l

于是Z=Z0+Z(ZJ-cj)Xj

j=m+\

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

h

zX|X2…XmXm+1…Xn

<010…0aim+i**?aIn

001…0了2m+la2nb2

000…1Qmm+lQmnbm

11inin

00...oZq”而+i-Cm+i

i=i1=1

再令bj=C,-Z,=c「￡c%

1=1

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

CiGCmCm+1品

Oi

bXix

CBXBmXm+IXn

c.X|b?1........0aim+ia〔n

b20........0^2m+1a2n

c2X2

:.:::

CmXmbm0........1^mm+1^mn

zZo0........0Om+1...........On―g檢驗數(shù)行

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

B=(P1,P2,…,Pm)=I,X=(bi,b2,…,bm,0……0)T

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

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

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

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

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

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

(3)20=工(:也,2=2廣5=工生為一的(/=機+1/一〃)

i=li=l

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

設MaxX=CXMaxZ=CX+OXL

「

AX<bA+ixL=b

其標準型為

x>0x,xL>0

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

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

TT

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

MaxZ=(C^,CA.,O)XNMaxZ=CBXB+CNXN+0XL

1X」

XN=h\'BXB+NXN+IXL=h

XLTLXB，X.,,X二。

_xs,xN,xt>o

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

ll1

XB=Bb-BNXN-BXL

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

Z=CB(B"b-BTNXN-B-1XL)+CNXN+OXL

=CBB』b-CBB"NXN-CBB/XL)+CNXN

^BB-^-CCBB^N-C^XN-CBB-'XL

將

Z+(CKB-'N-CJXN+CKB"'x,=CKB''b

XB+BtNXN+B~'XL=B一%

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

N

CBCCL

bXBXNXL

B'b

B-1

XB1B'N

ZCBBI0CBB'N-CNCBB-1

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

Ci23000

6i

CBXBbXlX2X3X4X5

0X3812100

0X41640010

0X51204001

-z0-2-3000一0j

初始可行基B=(P3HR)=I,X=(o,0,8,16,12)T

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

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

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

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

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

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

10先確定入基變量Xk：k=min{jloj<0}

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

0=min1aik>0=

_縱電

3°以瓦,為主元，進行初等行變換(又稱旋轉(zhuǎn)變換)即將列向量區(qū)變

換為單位列向量：

返回(2)o

換基迭代的關鍵在于將換入變量對應的列向量區(qū)用初等行變換方法

變換成單位列向量。其中主元瓦K變成1。即

品0

aik0

Pk=->f第L個分量

a\k1

0

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

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

（■■）人工變量法

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

法得到初始基可行解。

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

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

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

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

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

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

明原問題無可行解。

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

人工變量法常見的有大M法和兩階段法。

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

例，用大M法求解

MinZ=xi+1.5x2

xx+3X2>3

%1+x2>2

xpx2>0

解：MinZ=xi+1.5x2+0.xs+0.X4+Mx5+Mx6

%14-3X2-x3+x5=3

X1+x2-x4+4=2

_XpX2>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)性準則應是Cj—ZjWO。

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

（2）兩階段法

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

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

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

MinW=Xn+1+…+Xn+m

"%陽+…+冊,/+%用二4

生西+…+”2戶“+Z+2=b2

王，....工…之0

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

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

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

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

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

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

計算的初始表。

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

MinZ=Xi+l.5x24-0x3+0x4

X]+3々-X3=3

原I可題：*+/—x4=2

_x,,x2>0,x3,x4>0

MinW=X5+X6

/+3X2-X3+x5=3

輔助問題：X]+—x4+x6-2

x,,x2>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)化為minZ^Zk-Z）

（二）退化

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

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

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

G403000

0i

BbXl

cBXX2X3X4X5X6

0X562010103

0X43[1]-101003

0X651110015

z0-40-3000-5

0X500[2]1-2100

4Xl31-10100/

0X63021-1011

z120-4-3400-5

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

B]—>B2f...—>Bj

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

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

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

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

k=min{jIOj>0}

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

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

b

L=minr\3r=min{—Iajk>0}

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

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

一、LP的對偶問題

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

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

maxZ=2xi+3x2

（設備）

X]+2X2<8

（原材料A）

4X2<16

（原材料B）

4X2<12

xt,x,>0

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

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

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

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

B的價格（含附加值）

工廠決策者考慮：

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

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

~yt+4y2>2

_2y,+4y3>3

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

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

價）

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

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

MinW=8yi+l6y2+12y3

一%+4乃之2

s.t2yl+4y3>3

J?%?”20

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

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

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

問題。

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

由例1有maxZ=cx

~YX<b

X>0

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

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

當—C“NO①

CBB120②

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

☆Y=CBB」,且②有Y20

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

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

(CBB」B-CB,CBBN—CN)=(CBB」A—C)=YA—CNO

即YA2C

又對②Y=CBBL兩邊右乘b,有

Yb=CBB'b=Z

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

MinW=Yb

~YA>C

r>o

它是原問題（maxZ=CXIAX<b,X>0）的對偶問題

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

MaxZ=CXMinW=Yb

~YX>b「E4"

與

X>0丫20

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

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

內(nèi)容之一。

二、對偶理論

1.原問題與對偶問題的關系如下表所示

原始對偶表

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

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

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

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

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

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

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

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

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

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

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

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

MaxZ=CXMinW=Yb

'YX<b「E4”

設

_x>o[_r>o

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

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

則。又（再；

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

問題）無可行解；

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

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

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

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

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

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

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

③兩個問題均無可行解。

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

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

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

充要條件是：

①若y*i>0,則ZaijX：=bi

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

③若X；>0,則￡aijy*i=Cj

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

三、對偶單純形法

1.單純形法的重新解釋

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

6-%20①（稱為原始可行條件）

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

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

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

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

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

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

舉例說明

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

①不要求模型中b20

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

③，=min,'\arj<0=

）%Jark

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

①maxZ=CX（CW0）②maxZ=CX

AX=bAX=b

（b無限制），Z（0

X>0X>0

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

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

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

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

1.對偶解Y*=CBB”的經(jīng)濟含義

設互為對偶的LP問題

maxZ=CXminW=Yb

AX<bYA>C

（原）（對）

X>0y>o

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

*

因此^—=CB=y*

dbB

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

SZ*,

則-----

=y:*

dbl,

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

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

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

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

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

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

maxZ=2x1+3x2minW=8y1+16y?+l2y3

%1+2X<8

2-乂+4”之2

4x<16

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

4X2<12

J，為20,>32°

xt,x2>0

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

C23000

CBXBbXlX2X3X4X5

2X]41001/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=8Y]*+16Y2*12Y3*

上az*—,az**=經(jīng)\

y*=---=1.5,y*=----=0.125,”0

12

西db2db.

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

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

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

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

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

O

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)基，貝U

資源的影價=Y*=CBB」

(2)在退化情況下：

當對偶問題有K個最優(yōu)解，則第i種資源的影價=叫11{)<">}即影價的

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

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

maxZ=3xj+X2

(資源1限制)

xt+x2<2

(資源2限制)

3%]+2x,<6

陽，12之0

最終表

3100

b

XBX|X2X3X4

X121110

X400-1[-3]1

Z60230

X1212/301/3

X3001/31-1/3

Z60101

...資源1的影價

=min{yj⑴,yj⑵}

=min{3,0}=0

資源2的影價=min{丫2*"),丫2汽"}=min{0,1}=0

4.影子價格的參謀作用

-影價>0,說明伊資源已耗盡，

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

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

成為長線資源。

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

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

CBB」Pj-Cj<0說明第j種產(chǎn)品應投產(chǎn)

CBB8—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ā)生變化時，考察是否影響以下兩式的成立？

CBB~'N-CN>0

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

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

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

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