MBA《運(yùn)籌學(xué)》講義課件

MBA《運(yùn)籌學(xué)》講義

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

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

運(yùn)籌學(xué)的核心思想是建立在優(yōu)化的基礎(chǔ)上。

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

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

成？

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

最多？

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

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

學(xué)依據(jù)。

隨著計(jì)算機(jī)及計(jì)算技術(shù)的迅猛發(fā)展，目前對(duì)運(yùn)籌學(xué)的數(shù)學(xué)模型的求解

已有相應(yīng)的軟件。因此，在實(shí)際求解計(jì)算時(shí)常可借助于軟件在計(jì)算機(jī)上進(jìn)

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

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

LP問題

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

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

煽本最優(yōu)解

提出

一基本方法

圖解法

「原始單純形法

單純形法一r大M法

L人工變量法一

對(duì)偶單純形法L兩階段法

偶理論

一進(jìn)一步討論

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

經(jīng)濟(jì)管理領(lǐng)域內(nèi)應(yīng)用

—「運(yùn)輸問題(轉(zhuǎn)運(yùn)問題)

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

、多目標(biāo)LP問題*

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

及其應(yīng)用

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

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

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

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

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

所示。問應(yīng)如何安排計(jì)劃使該工廠獲利最多？

1II資源限量

設(shè)備128（臺(tái)時(shí)）

原材料A4016(kg)

原材料B0412(kg)

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

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

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

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

限制，所以有：

機(jī)器設(shè)備的限制條件：XI+2X2W8I、

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

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

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

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

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

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

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

Z=2X,+3X2的值達(dá)到最大。

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

maxz=2x1+3x2

x]+2X2<8

4%]<16

s.t.

4X2<12

%1?%NO

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

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

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

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

購買食品的費(fèi)用最?。?/p>

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

1豬肉10005040010

2雞蛋800602006

3大米900203003

4白菜200105002

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

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é)為在變量滿足線性約束條件下，求使

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

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

的值就代表一個(gè)具體方案。通常可根據(jù)決策變量所代表的事物特點(diǎn)，可對(duì)

變量的取值加以約束，如非負(fù)約束。

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

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

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

滿足以上三個(gè)條件的數(shù)學(xué)模型稱為L(zhǎng)P的數(shù)學(xué)模型，其一般形式為：

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,…,品)，稱為價(jià)值系數(shù)向量；

a、]，，…Qi

2w

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

，。帆2,…"〃皿_

=(Pl,P2,'",Pn)

飛「

b、

b=：稱資源限制向量

_bm_

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

(三)LP問題的標(biāo)準(zhǔn)型

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

把LP問題的?般形式化為統(tǒng)一的標(biāo)準(zhǔn)型：

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,-??,?)

標(biāo)準(zhǔn)型的特點(diǎn)：

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

②約束條件均由等式組成

③決策變量均為非負(fù)

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

2.化一般形式為標(biāo)準(zhǔn)型

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

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

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

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

3.模型隱含的假設(shè)

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

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

定意味著每種經(jīng)營(yíng)活動(dòng)對(duì)目標(biāo)函數(shù)的貢獻(xiàn)是一個(gè)常數(shù)，對(duì)資源的消耗也是

一個(gè)常數(shù)。

②可加性假定：每個(gè)決策變量對(duì)目標(biāo)函數(shù)和約束方程的影響是獨(dú)立于

其它變量的。

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

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

題，不含隨機(jī)因素。

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

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

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

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

對(duì)LP標(biāo)準(zhǔn)型，我們還假定r(A)=m<n。

(四)LP問題的解的概念

設(shè)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}。

而使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解，對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最

優(yōu)值。

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

的。

2.從LP角度看：

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

則稱B是LP問題的一個(gè)基。

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

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

向量Prj相對(duì)應(yīng)的變量Xg稱為基變量，其它變量稱為非基變量。顯然，對(duì)應(yīng)

于每個(gè)基總有m個(gè)基變量，n—m個(gè)非基變量。

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

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

一一對(duì)應(yīng)的，基本解的個(gè)數(shù)WC'、。在基本解中，稱滿足非負(fù)條件的基本解

為基可行解，對(duì)應(yīng)的基稱為可行基。

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

的，否則是非退化的。

最優(yōu)基如果對(duì)應(yīng)于基B的基可行解是LP問題的最優(yōu)解，則稱B為L(zhǎng)P

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

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

（五）兩個(gè)變量LP問題的圖解法

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

maxz=2xi+3x2

$+2X2<8①

4x,<16②

4X2<12③

A：,>0,x2>0④

按以下順序進(jìn)行：

解：（1）畫出直角坐標(biāo)系；

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

可行域；

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

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

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

圖1

一21

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

-33

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

3

點(diǎn)具有相同的值。

解的幾種情況：

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

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

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

（3）無界解

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

可行域最優(yōu)解

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

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

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

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

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

(3)LP問題的可行域的頂點(diǎn)個(gè)數(shù)是有限的；

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

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

優(yōu)的點(diǎn)的問題。

2.基可行解的幾何意義

對(duì)例1LP問題標(biāo)準(zhǔn)化為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點(diǎn))

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

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

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

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

x(%,x⑸才是基可行解，它們與可行域的頂點(diǎn)相對(duì)應(yīng)。于是還有

結(jié)論：(5)對(duì)于標(biāo)準(zhǔn)型的LP問題，X是基可行解的充要條件是X為可行

域的頂點(diǎn)。

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

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

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

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

②從可行域的一個(gè)頂點(diǎn)(基可行解)迭代到另一個(gè)頂點(diǎn)(基可行解)。

§2單純形法與計(jì)算機(jī)求解

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

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

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

設(shè)maxZ=c1x1+C2X2+…+cnxn

%+4",+1

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

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

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

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

并寫成增廣矩陣的形式:

-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七,.=〃-當(dāng)代入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檢驗(yàn)數(shù)行

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

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

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

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

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

目標(biāo)函數(shù)非基變量的系數(shù)則以相反數(shù)填入檢驗(yàn)數(shù)行各相應(yīng)位置。

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

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

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

i=li=l

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

設(shè)MaxX=CXMaxZ=CX+OXL

「

AX<bA+ixL=b

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

x>0x,xL>0

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

XB,N對(duì)應(yīng)于XN，I對(duì)應(yīng)于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

代入目標(biāo)函數(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一%

寫成對(duì)應(yīng)于基B的矩陣形式的單純形表T(B)：

N

CBCCL

bXBXNXL

B'b

B-1

XB1B'N

ZCBBI0CBB'N-CNCBB-1

例如將例1化成標(biāo)準(zhǔn)型后如下表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)中，若所有的檢驗(yàn)數(shù)。j2O0=1,2,…,n)

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

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

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

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

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

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

0=min1aik>0=

_縱電

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

換為單位列向量：

返回(2)o

換基迭代的關(guān)鍵在于將換入變量對(duì)應(yīng)的列向量區(qū)用初等行變換方法

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

品0

aik0

Pk=->f第L個(gè)分量

a\k1

0

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

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

（■■）人工變量法

若對(duì)LP模型標(biāo)準(zhǔn)化后，不具有B=I時(shí)，如何辦？此時(shí)可采用人工變量

法得到初始基可行解。

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

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

問題后求解。當(dāng)增加的人工變量全部取值為。時(shí)，才與原問題等價(jià)。這樣，

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

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

被恢復(fù)，同時(shí)也得到一個(gè)基可行解。在最終表中若不能全部被換出，則說

明原問題無可行解。

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

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

（1）大M法（通過下例簡(jiǎn)略介紹其方法與步驟）

例，用大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)成“人工基”

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

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

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

③對(duì)于minZ判別最優(yōu)性準(zhǔn)則應(yīng)是Cj—ZjWO。

④大M法適合于手算，不適用于計(jì)算機(jī)求解。

（2）兩階段法

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

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

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

MinW=Xn+1+…+Xn+m

"%陽+…+冊(cè),/+%用二4

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

王，....工…之0

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

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

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

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

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

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

計(jì)算的初始表。

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

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）第一階段的初始表中非基變量

的檢驗(yàn)數(shù)=人工變量所在行的非基變量相應(yīng)系數(shù)之和，目標(biāo)函值值=人工變

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

（2）第二階段單純形表中目標(biāo)函數(shù)系數(shù)應(yīng)將非基變量表示基變量后所

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

為0。

（3）若maxZ,則可轉(zhuǎn)化為minZ^Zk-Z）

（二）退化

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

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

如某個(gè)最大化問題的單純形表為：

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

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

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

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

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

k=min{jIOj>0}

(2)按。規(guī)則計(jì)算，若存在兩個(gè)相同以上最小比值時(shí)，選取下標(biāo)最小

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

b

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

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

§3對(duì)偶理論與靈敏度分析

一、LP的對(duì)偶問題

1.引例前已述引例1是一個(gè)在有限資源的條件下，求使利潤(rùn)最大的生

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

maxZ=2xi+3x2

（設(shè)備）

X]+2X2<8

（原材料A）

4X2<16

（原材料B）

4X2<12

xt,x,>0

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

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

和材料費(fèi)，此時(shí)工廠應(yīng)考慮如何為每種資源的定價(jià)問題？

解：設(shè)yi,y2,y3分別表示出租單位設(shè)備臺(tái)時(shí)的租金和出售單位原材料A、

B的價(jià)格（含附加值）

工廠決策者考慮：

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

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

~yt+4y2>2

_2y,+4y3>3

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

（2）價(jià)格應(yīng)盡量低，否則沒有競(jìng)爭(zhēng)力（此價(jià)格可成為與客戶談判的底

價(jià)）

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

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

MinW=8yi+l6y2+12y3

一%+4乃之2

s.t2yl+4y3>3

J?%?”20

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

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

稱這兩個(gè)LP問題是互為對(duì)偶的兩個(gè)LP問題。其中一個(gè)是另一個(gè)問題的對(duì)偶

問題。

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

由例1有maxZ=cx

~YX<b

X>0

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

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

當(dāng)—C“NO①

CBB120②

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

☆Y=CBB」,且②有Y20

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

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

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

即YA2C

又對(duì)②Y=CBBL兩邊右乘b,有

Yb=CBB'b=Z

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

MinW=Yb

~YA>C

r>o

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

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

MaxZ=CXMinW=Yb

~YX>b「E4"

與

X>0丫20

任何一個(gè)LP問題均有一個(gè)對(duì)偶LP問題與之匹配。

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

內(nèi)容之一。

二、對(duì)偶理論

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

原始對(duì)偶表

原問題Max（對(duì)偶問題）對(duì)偶問題Min（原問題）

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

第i個(gè)約束條件為第i個(gè)變量20

第i個(gè)約束條件為“2”第i個(gè)變量W0

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

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

第i個(gè)變量N0第i個(gè)約束條件為

第i個(gè)變量W0第i個(gè)約束條件為

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

第i個(gè)約束條件的右端項(xiàng)目標(biāo)函數(shù)第i個(gè)變量的系數(shù)

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

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

MaxZ=CXMinW=Yb

'YX<b「E4”

設(shè)

_x>o[_r>o

（i）（對(duì)稱性）對(duì)偶問題的對(duì)偶是原問題；

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

則。又（再；

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

問題）無可行解；

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

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

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

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

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

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

②一個(gè)問題具有無界解，則它的對(duì)偶問題無可行解；

③兩個(gè)問題均無可行解。

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

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

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

充要條件是：

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

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

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

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

三、對(duì)偶單純形法

1.單純形法的重新解釋

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

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

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

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

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

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

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

2.對(duì)偶單純形法的計(jì)算步驟:

舉例說明

3.對(duì)偶單純形法與單純形法的不同之點(diǎn):

①不要求模型中b20

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

③，=min,'\arj<0=

）%Jark

4.對(duì)偶單純形法適用對(duì)象

①maxZ=CX（CW0）②maxZ=CX

AX=bAX=b

（b無限制），Z（0

X>0X>0

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

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

④進(jìn)行靈敏度分析時(shí)，有時(shí)會(huì)用到此法

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

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

設(shè)互為對(duì)偶的LP問題

maxZ=CXminW=Yb

AX<bYA>C

（原）（對(duì)）

X>0y>o

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

*

因此^—=CB=y*

dbB

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

SZ*,

則-----

=y:*

dbl,

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

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

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

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

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

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

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

%1+2X<8

2-乂+4”之2

4x<16

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

4X2<12

J，為20,>32°

xt,x2>0

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

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表示單獨(dú)對(duì)設(shè)備臺(tái)時(shí)增加1個(gè)單位，可使Z值增加1.5個(gè)單

位的利潤(rùn)；丫2*=0.125表示單獨(dú)對(duì)原材料A增加1個(gè)單位，可使Z值增加0.125

個(gè)單位的利潤(rùn)；而丫3*=0表示單獨(dú)對(duì)原材料B增加一個(gè)單位，卻不使Z值增

加。這是因?yàn)閺淖罱K表中可看出，在最優(yōu)方案中，松馳變量X5=4,即表示

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

O

2.影子價(jià)格的定義

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

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

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

子價(jià)格，所以影子價(jià)格又稱“最優(yōu)計(jì)劃價(jià)格”，“預(yù)測(cè)價(jià)格”等等。

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

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

會(huì)成本。

3.影子價(jià)格的求法

(1)在非退化情況下：設(shè)B為L(zhǎng)P問題的最優(yōu)基，貝U

資源的影價(jià)=Y*=CBB」

(2)在退化情況下：

當(dāng)對(duì)偶問題有K個(gè)最優(yōu)解，則第i種資源的影價(jià)=叫11{)<">}即影價(jià)的

第i個(gè)分量等于這K個(gè)對(duì)偶解中第i個(gè)分量的最小值。

例如，設(shè)某資源利用問題為

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的影價(jià)

=min{yj⑴,yj⑵}

=min{3,0}=0

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

4.影子價(jià)格的參謀作用

-影價(jià)>0,說明伊資源已耗盡，

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

影價(jià)=0,說明該資源有剩余，

成為長(zhǎng)線資源。

(2)對(duì)市場(chǎng)資源的最優(yōu)配置起著推進(jìn)作用

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

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

CBB8—Cj>0說明第j種產(chǎn)品不應(yīng)投產(chǎn)

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

(4)可以預(yù)測(cè)產(chǎn)品的價(jià)格

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

五、靈敏度分析

面對(duì)市場(chǎng)變化，靈敏度分析的任務(wù)是須解決以下兩類問題：

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

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

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

么？

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

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

CBB~'N-CN>0

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

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

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

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