運籌學(xué)第一章-對偶理論南京大學(xué)課件

對偶理論例1.某工廠在計劃期內(nèi)要生產(chǎn)甲乙兩種產(chǎn)品。這些產(chǎn)品分別需要在A,B,C,D四種不同的設(shè)備上加工。具體工況如下：設(shè)備產(chǎn)品ABCD利潤（元/件）甲21402乙22043臺時1281612如何獲取最大利潤？解:問題的數(shù)學(xué)模型為:Maxf=2x1+3x2s.t.2x1+2x212x1+2x284x1164x212xj

0,j=1,2假如設(shè)備的有效工時也可以用來承接對外加工，應(yīng)如何對每種設(shè)備的工時定價？設(shè)A,B,C,D四種設(shè)備的工時價格分別定為y1,y2,y3,y4.生產(chǎn)一件甲產(chǎn)品所用A,B,C,D四種設(shè)備的工時分別為2,1,4,0,得到2元利潤。工時的價格應(yīng)保證相應(yīng)工時用于對外加工時獲利不低于2元。即有

2y1+y2+4y3

2.同樣，對于乙產(chǎn)品應(yīng)有2y1+2y2+4y43.相應(yīng)的總利潤為12y1+8y2+16y3+12y4為了能夠得到對外加工訂單，工時的價格只能盡量的低，這就導(dǎo)致利潤要盡可能的小。Ming=12y1+8y2+16y3+12y4s.t.2y1+y2+4y3

22y1+2y2+4y43y1,y2,y3,y40這樣我們就有如下的規(guī)劃模型Maxf=2x1+3x2s.t.2x1+2x212x1+2x284x1164x212xj

0,j=1,2Ming=12y1+8y2+16y3+12y4s.t.2y1+y2+4y3

22y1+2y2+4y43y1,y2,y3,y40例2.市場上有6種食物都含有維生素A

和C，具體數(shù)據(jù)如下：一二三四五六最少需要量A1022129C01313219價格353060502722問題：消費者應(yīng)如何選購食物，既花費最少又能滿足人體每日9個單位維生素A、19個單位維生素

C的需要？解.設(shè)6種食物的選購量分別為x1,x2,x3,x4,x5,x6,

則

若有一家藥廠計劃生產(chǎn)兩種藥丸，分別含一個單位的維生素A

和C.假定市場上含維生素A

和C

的食品價格如例1所示。問這兩種藥丸應(yīng)如何定價才能既與市場上的食品價格競爭又使合要求的飲食費用最大（賺錢最多）？(LP1)s.t.Minf=35x1+30x2+60x3+50x4+27x5+22x6x1+2x3+2x4+x5+2x69x2+3x3+x4+3x5+2x6

19xi

0,i=1,…,6.

(LP2)設(shè)維生素A丸和C丸的價格分別定為y1和y2,

則有Maxg=9y1＋19y2s.t.y135y2

302y1+3y2602y1+y250y1+3y2272y1+2y222y10,y20

(LP1)s.t.x1+2x3+2x4+x5+2x69x2+3x3+x4+3x5+2x619

xi

0,i=1,…,6.Minf=35x1+30x2+60x3+50x4+27x5+22x6

Maxg=9y1+19y2s.t.y1

35

y2302y1+3y2602y1+y250

y1+3y2272y1+2y222

y10,y20(LP2)極大極小(LP2)(LP1)目標系數(shù)右端向量目標系數(shù)右端向量系數(shù)矩陣轉(zhuǎn)置n

個變量m

個變量m

個約束n

個約束定義：給定一個一般形式的(LP),稱它為原始(LP),那么它的對偶定義如下：原始Minf=cxs.t.aix＝bi

i

Maix

bi

i

M’xj

0j

Nxj

0j

N’對偶Maxg=bTys.t.yi

0i

Myi

0

i

M’AjT

y

cj

j

NAjTy

cj

j

N’其中，ai

表示A

的第

i

個行向量,Aj

表示A

的第j

個列向量,

M

和M’分別表示對應(yīng)于等式和不等式約束的行指標集合,N

和N’表示x

Rn

中對應(yīng)于限制和非限制變量的列指標集合。注意：當目標函數(shù)求極小值時

(Min),

不等式約束均為,

當目標函數(shù)求極大值時

(Max),

不等式約束均為.xTycb如何寫出一個(LP)問題的對偶？1.若原問題的第i

個約束為等式，則對偶問題的第i

個變量為自由變量；2.若原問題的第j

個變量為自由變量，則對偶問題的第j

個約束為等式。例3.寫出下面(LP)問題的對偶。Maxf=x1+2x2?3x3+4x4s.t.?x1+x2?x3?3x4

56x1+7x2?3x3?5x4812x1?9x2+9x3+9x420xi0,i=1,2,3;x40.解.原問題等價于：Maxf=x1+2x2?3x3+4x4s.t.?x1+x2?x3?

3x4

5?6x1?

7x2+3x3+

5x4?812x1?9x2+9x3+9x420xi0,i=1,2,3;x40.由定義，原問題的對偶為：Ming=5y1?8y2+20y3s.t.?y1?6y2+12y31y1?

7y2?9y32?y1+

3y2+

9y3

?3?

3y1+

5y2+9y3

4y10,

yj

0,j=2,3.對偶問題的基本性質(zhì)定理1.

對偶問題的對偶是原問題

原問題Minf=cxs.t.Aix=bi

i

Maix

bi

i

M’xj

0j

Nxj

0j

N’

對偶問題Maxg=bTys.t.yi

0

i

Myi

0

i

M’AjTy

cj

j

NAjTy

=cj

j

N’證.原始問題對偶的一般形式為：Min(bT)ys.t.(AjT)

y

cj

j

N(AjT)

y

cj

j

N’yi

0

i

M’yi

0

i

M把它看作原始(LP),按定義其對偶為：Max(c)xs.t.xj

0

j

Nxj0

j

N’aix

bi

i

M’aix

bi

i

M定理2.(弱對偶定理)設(shè)x0,y0分別是(LP)問題及其對偶問題的可行解，則cx0bTy0.證.由題設(shè)可知Ax0b,x00;ATy0cT,y00.由(2)式得ATy0

cT

0.由(1)式和(4)式得bTy0(x0)TATy0cx0.(1)(2)(3)式兩邊同乘以(x0)T得(x0)T(ATy0

cT)

0.(3)(4)定理3.(無界性定理)若原問題與其對偶問題中有一個有無界解，則另一個必無可行解。證.由定理1我們不妨假設(shè)原(LP)問題有無界解。若其對偶有可行解，令y0為其任一可行解，于是有

ATy0cT.設(shè)x

是原(LP)問題任一可行解，則

xTATy0cx.由于

xTATy0(Ax)Ty0bTy0故有

cxbTy0,這表明原問題目標函數(shù)值有下界，矛盾。定理4.(最優(yōu)性定理)設(shè)x0,y0分別是(LP)問題及其對偶問題的可行解且cx0bTy0.則x0,y0分別是原問題與其對偶問題的最優(yōu)解。定理5.(強對偶定理)若原問題存在最優(yōu)解，則其對偶問題也有最優(yōu)解，且兩者的最優(yōu)目標函數(shù)值相同。證.設(shè)原(LP)問題的標準型為：Mincx+0x’s.t.

AxImx’=b

x0,x’0.設(shè)x*是用單純形法求出的原(LP)問題的最優(yōu)bfs,其對應(yīng)的基為B,所有非基列記為N.于是有N

cN

cBB1N0.由于基變量的檢驗數(shù)為0，我們有(c,

0)

cBB1(A,Im)0.

(1)令y*(cBB1)T,則由(1)式可得ATy*cT,

y*0.這說明y*是對偶問題的可行解。由于

cx*

cBxB*

cBB1bbTy*,根據(jù)定理

4,y*是對偶問題的最優(yōu)解。注意上下銜接的過程，我們把整個C=(c,0)拿出來了，用得是前面得到的B,這個B不是初始基，而是最終的可行基！互為對偶的兩個(LP)的解之間的關(guān)系：1.兩個均有最優(yōu)解；2.兩個都沒有可行解；3.

一個有無界可行解，另一個沒有可行解。對偶原始最優(yōu)值有界最優(yōu)值無界無可行解最優(yōu)值有界1最優(yōu)值無界3無可行解32定理6.

(互補松弛性定理)設(shè)x,y

分別是(LP)問題及其對偶問題的可行解，則它們是最優(yōu)解的充要條件是,對一切i和j有：

(1)uiyi(aixbi)0;

(2)vj(cj

yTAj)xj0.證.由對偶關(guān)系知，對一切i

和j

有ui

0,vj

0.令易見，u0當且僅當(1)成立；v0當且僅當(2)成立。對一切i和j,將(1)式和(2)式相加，則可消去既含x又含y

的項，從而有

u+v=cxyTb.因此，(1)和(2)成立當且僅當u+v=0,或者

cx=yTb.由定理2,cx=yTb

是x

和y分別是最優(yōu)解的充要條件。定理6結(jié)論表明：若原問題最優(yōu)解的某分量xi>0,則其對偶問題中第i個約束在最優(yōu)解處必呈等式；若對偶問題第i個約束在最優(yōu)解處呈嚴格不等式，則原問題最優(yōu)解中第i個分量必為0.互補松弛性定理的應(yīng)用:設(shè)x,y

分別是(LP)問題及其對偶問題的可行解，則它們是最優(yōu)解的充要條件是:對一切i和j有：(1)yi(aixbi)0;

(2)(cj

yTAj)xj0.例4.已知線性規(guī)劃問題其對偶最優(yōu)解為y*=(4/5,3/5)T,試求原問題的最優(yōu)解。Minf=2x1+3x2+5x3+2x4+3x5s.t.x1+x2+2x3+x4+3x542x1?x2+3x3+x4+x5

3xj0,j=1,…,5解.

其對偶為:

Maxg=4y1＋3y2s.t.y1+2y22y1

y2

32y1+3y2

5y1+y2

23y1+y2

3yj0,j=1,2設(shè)x*=(x1,x2,x3,x4,x5)T

是原問題的最優(yōu)解。[在對偶問題中，一共7個約束(含2個非負約束)。找出對偶最優(yōu)解y*=(4/5,3/5)T的等式約束，即約束1和約束5,其余約束皆為嚴格不等式約束。]由互補松弛性可知：

x2x3

x40且由此可得x*=(1,0,0,0,1)T.x1+3x5=42x1+

x5=3影子價格當(LP)原問題求得最優(yōu)解x*時，其對偶問題也求得最優(yōu)解y*,且有

f*cx*bTy*g*.在實際的經(jīng)濟活動中，bi

代表資源的擁有量；對偶變量yi*代表在資源最優(yōu)利用的條件下對單位第i

種資源的估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價。為區(qū)別市場價格，稱其為影子價格。如果資源i

增加一個單位，而其它資源都保持不變，那么由此引起的目標函數(shù)最優(yōu)值的增量稱為該資源的影子價格。(1)如何計劃可使周收益最大？(2)若每周多工作一小時，最多可增加多少收入？例1.某生產(chǎn)果汁杯和酒杯的個體經(jīng)營者，每周工作60小時，擁有150立方米的儲藏室。這兩種產(chǎn)品的生產(chǎn)工況如下：杯型工效(小時/百箱)儲藏量(立方米/百箱)最大需求(百箱)收益(元/箱)果汁杯61085酒杯5204.5解.(1)設(shè)每周生產(chǎn)果汁杯x1百箱,酒杯x2百箱。則

基x1x2x3x4x5bx36510060x41020010150x51000185004500000該問題化為標準型后的單純形初表為Maxf=500x1＋450x2s.t.6x1＋5x26010x1＋20x2150x18xi0,i=1,2基x1x2x3x4x5bx2011/73/35030/7x5002/71/14111/7x1102/71/14045/700550/720/7036000/7上述問題的單純形終表為故每周應(yīng)生產(chǎn)果汁杯45/7百箱,酒杯30/7百箱。(2)這時，b’=(61,150,8)T.于是

B1b’=(29/7,9/7,47/7)T.又cB=(450,0,500),可算得

cB

B1b’=36550/7.對原問題而言，其目標值為36550/7,實際增加=550/7,即每周多工作1小時可增加收入550/7元。影子價格的計算

Max

z=cx

s.t.

Ax

b

x0考慮問題化為標準型

Min

f=cx

s.t.

Ax+Imx’

=b

x

0

x’

0(D)若最優(yōu)基為B,且A=(B

N),則其單純形表為:基變量xBxNx’x’BNImbccBcN00基變量xBxNx’解xBImB1NB1B1b0cN+cBB1NcBB1cBB1b上表說明資源i

的影子價格在數(shù)值上就等于其對偶問題最優(yōu)解的第

i

個分量。這也就是說，對于形如(D)的線性規(guī)劃問題，其資源的影子價格可從原問題的單純形終表中讀出?，F(xiàn)在C’=--C,例2.求下列線性規(guī)劃問題中諸資源的影子價格。

Maxf=80x1+100x2

s.t.8x1+4x22205x1+5x21703x1+4x2120

xi0,i=1,2解.該問題的初始單純形表為基x1x2x3x4x5解x384100220x455010170x53400112080100000單純形終表為：基x1x2x3x4x5解x30014420x11004/5116x20103/5118000420對應(yīng)于松弛變量的檢驗數(shù)可直接讀出資源的影子價格為

(0,4,20)T.另一方面，由影子價格公式w=(B1)TcBT

也可算得14404/5103/51例3.若在例1中增加一個問題：今有客戶欲訂購一種香檳杯，其工況如下表。這位個體經(jīng)營者是否應(yīng)該接下此活？杯型

工效(小時/百箱)

儲藏量(立方米/百箱)最大需求(百箱)

收益(元/箱)果汁杯61085酒杯5204.5香檳杯8106解.設(shè)每周生產(chǎn)果汁杯x1百箱,酒杯x2百箱，香檳杯x3百箱。則

Maxf=500x1+450x2+600x3

s.t.6x1+5x2+8x36010x1+20x2+10x3

150

x18

xi0,i=1,2,3從例1的單純形終表中可知三種資源的影子價格為

w=(550/7,20/7,0)T.若生產(chǎn)香檳杯,則所需的隱含費用為8×550/7+10×20/7+0=4600/7元。由于4600/7＞600,即隱含費用＞收益，故此活不能接。考慮(LP)問題若最優(yōu)基為B,且A=(B

N),則其單純形終表為基變量xBxN解BNbxBImB1NB1b0

cNcBB1NcBB1b靈敏度分析其中，cN

cBB1N

0;

B1b

0.Minf=cx

s.t.Ax=bx0由上表可知

1.bi

的變化分析設(shè)bi有改變量bi

,要保證B

的最優(yōu)基不變，只須使得變化后的基變量依然可行，即B1(b+b)0,由此可以確定bi

的變化范圍，其中B1可由問題的單純形終表讀出，b=(0,..,0,bi,0,..,0)T.改變影響不影響bi(1)可行性(2)目標值最優(yōu)性(可行情況下)cB(1)最優(yōu)性(2)目標值可行性cN最優(yōu)性(1)可行性aij

(jN)最優(yōu)性(1)可行性(2)目標值(2)目標值例1.已知一個(LP)問題的單純形初表終表如下，試求

b1

的變化范圍?；鵻1x2x3x4x5bx36510060x41020010150x51000185004500000基x1x2x3x4x5bx2011/73/35030/7x5002/71/14111/7x1102/71/14045/700550/720/7036000/71/73/3502/71/1412/71/140解.由終表可得則由B1(b+b)

0可得–45/2

b1

11/2,即75/2

b1131/2.令2.cj

的變化分析情形1.

cj

,Pj

N設(shè)A=(P1,P2,…,Pn

)設(shè)cj’

cj+cj,Pj

N,則

cj

–

j

欲保持B

的最優(yōu)性，只需j’

0,即

j+cj

0即可。故cj

,Pj

N的變化準則是：例2.已知某(LP)問題的單純形初、終表如下。若目標系數(shù)

c4有改變量c4,求使原問題最優(yōu)解保持不變的c4變化范圍?；鵻1x2x3x4x5bx31310090x42101080x51100145540000基x1x2x3x4x5bx30012525x11001135x20101210

00013215解.由cj

–j

可得，c4

1.

情形2.ci,Pi

B設(shè)ci’

ci+ci,Pi

B,則對于一切Pj

N,有欲保持B

的最優(yōu)性，只需對于一切Pj

N,有j’

0,即

j

–cBB1Pj0即可。故ci

,Pi

B

的變化準則是：

Pj

N,cBB1Pj

j

其中cB’

=cB

+cB.例3.已知某(LP)問題的單純形初、終表如下。若基變量x2的目標系數(shù)c2有改變量c2,求使原問題最優(yōu)解保持不變的c2變化范圍。基x1x2x3x4x5bx31310090x42101080x51100145540000基x1x2x3x4x5bx30012525x11001135x20101210

00013215125011012解.cB=(0,5,4),

N={P4,P5},4=1,5=3.

1

c23/2,

5

c2

5/2.

B1P4=(2,1,1)T,

B1P5=(5,1,2)T,

cB

=(0,0,c2).由cBB1Pj

j

可得即

Pj

N,cBB1Pj

j

3.aij

的變化分析分三種情形：情形1.aij

,

Pj

N設(shè)Pj’

Pj+Pj,Pj

N,則欲保持B

的最優(yōu)性，只需j’

0,即

j

–cBB1Pj

0即可。故aij

,Pj

N

的變化準則是：

cBB1Pj

j

情形2.aij

,

Pj

B此時情況比較復(fù)雜。一般來說要用單純形法重新求解。若變化僅限于B

的某一列，那么新問題的求解可在原單純形終表基礎(chǔ)上變換一些數(shù)據(jù)進行。情形3.增加新變量增加新變量相當于原約束矩陣增加一列。類似于情形2,一般來說要用單純形法重新求解。新問題的求解可在原單純形終表基礎(chǔ)上，增加一列數(shù)據(jù)進行。

新產(chǎn)品開發(fā)問題在約束矩陣中增加一列計算諸資源的影子價格；2.計算開發(fā)新品所需的隱含費用，決定是否開發(fā)；若開發(fā)，令新產(chǎn)品的技術(shù)參數(shù)向量為P*,計算B1P*

和相應(yīng)的檢驗數(shù)*=c*–cBB1P*,并將其加到原問題的單純形表中；4.運用單純形法直至求得最優(yōu)解。例4.某廠生產(chǎn)兩種產(chǎn)品，其工況如下：原料產(chǎn)品A1產(chǎn)品A2資源(公斤)D1390E2180F1145利潤(千元/件)54

(1)應(yīng)如何安排生產(chǎn)可獲利最多？(2)若新品A3每件耗D、E、F分別為2、4、1公斤，且每件新品可獲利8000元，該廠是否應(yīng)當開發(fā)？應(yīng)生產(chǎn)多少為好？基x1x2x3x4x5bx30012525x11001135x2010121000013215生產(chǎn)方案是：A1:35件，A2:10件；獲利21.5萬元。解.(1)本題的單純形終表是

(2)從單純形終表中可知三種資源的影子價格為：

w=(0,1,3)T.

若生產(chǎn)新品,則所需的隱含費用為：

2×0+4×1+1×3=7000.

由于8000＞7000,即收益＞隱含費用，故應(yīng)當開發(fā)。125011012B1P*=(5,3,2)T,由終表得由于P*=(2,4,1)T,cB=(0,–5,–4)T,故*=c*–cBB1P*=–1.將B1P*

和*

加入原單純形終表中得基x1x2x3x4x5x*

bx300125525x110011335x201012210000131215基x1x2x3x4x5x*bx*001/52/5115x1103/51/52020x2012/51/50020

001/57/520220生產(chǎn)方案：A1:20件，A2:20件，A3:5件；獲利22萬元。基x1x2x3x4x5x*

bx300125525x110011335x201012210000131215例5.某廠生產(chǎn)兩種產(chǎn)品，其工況如下：產(chǎn)品I產(chǎn)品II資源設(shè)備128臺時材料A4016公斤材料B0412公斤利潤(千元/單位)23應(yīng)如何安排生產(chǎn)可獲利最多？若該廠又增調(diào)4臺時用于這兩種產(chǎn)品的生產(chǎn)，求最優(yōu)方案。確定產(chǎn)品II

價格系數(shù)的變化范圍。新品III的技術(shù)參數(shù)為：設(shè)備2臺時；材料A6公斤；材料B

3公斤；利潤為5千元/單位。是否值得開發(fā)？應(yīng)生產(chǎn)多少？(5)工藝改進后，產(chǎn)品I

技術(shù)參數(shù)為：設(shè)備2臺時；材料A5公斤；材料B2公斤；利潤為4千元/單位。試分析它對原最優(yōu)計劃有何影響？基x1X2x3x4x5bx3121008x44001016x50400112230000解.(1)設(shè)生產(chǎn)產(chǎn)品I

x1

單位，產(chǎn)品II

x2單位。則Maxf=2x1+3x2

s.t.

x1+2x284x1164x212

xi

0,i=1,2.Minz=2x1

3x2

s.t.

x1+

2x2+

x3=84x1+

x4=16

4x2+

x5=12

xi0,i=1,…,5.其單純形初表為：其單純形終表為：基x1x2x3x4x5bx11001/404x50021/214x2011/21/802

003/21/8014最優(yōu)解為：

x*=(4,2)T;f*=14.即生產(chǎn)產(chǎn)品I4單位，產(chǎn)品II2單位；獲利1.4萬元。(2)由單純形終表得：

cB=(2,0,3)T;cN

=(0,0)T;

B=(P1,P5,P2);b=(4,0,0)T.

B1(b+b)=(4,4,4)T.這樣，我們有在終表中以B1(b+b)

替代B1b,以cBB1(b+b)

替代cBB1b

有：基x1x2X3X4x5bx1100?04x5002?14x201?1/804

003/21/8020如何在上表的基礎(chǔ)上求新問題的最優(yōu)解？對偶單純形法此時，(b1,…,bm,0,…,0)T

是基解而非基可行解。但是b0!基x1x2xmxm+1xm+2xn

bx1100b1x2010b2xm001bm000m+1m+2n

1.確定出基變量:若bk=minbi|bi＜0,則選取

xk

為出基變量；2.確定入基變量:若所有λkj

0,則該問題無解。若

=maxjλkj

λkj＜0=lλkl,則選取

xl

為入基變量。3.進行換基迭代：若得最優(yōu)解，中止；否則，重復(fù)上述過程。

基x1x2x3x4x5bx11001/404x50021/214x2011/21/804

003/21/8020基x1x2x3x4x5bx11001/404x50021/214x2011/21/804

003/21/8020基x1x2x3x4x5bx11001/404x30011/41/22x201001/43

0001/23/417經(jīng)過一次換基迭代有：最優(yōu)解為x*=(4,3)T,f*=17,即生產(chǎn)4單位產(chǎn)品I,3單位產(chǎn)品II,獲利1.7萬元。

1

c23,4

c20.

B1P4=(1/4,1/2,1/8)T

B1P3=(0,2,1/2)T

N={P3,P4},

3=3/2,4=1/8,

令

cB

=(0,0,c2)T,由cBB1Pj

j,jN,得即(3)

由(1)中單純形終表得(4)由(1)中單純形終表得影子價格為wP*=3/2×2+1/8×6+0×3=15/4(千元)，由于15/4＜5,即隱含費用＜收益，故可以開發(fā)。將B1P*和*

代入(1)中單純形終表得：cB

=(2,0,3)TB1P*=(3/2,2,1/4)T*=c*

cBB1P*=5/4w=(3/2,1/8,0).令P*=(2,6,3)T,則新品III

的隱含費用為：基x1x2x3x4x5x*bx11001/403/24x50021/2124x2011/21/801/42

003/21/805/414

x*=(1,3/2,2)T;f*=33/2分別生產(chǎn)產(chǎn)品I,II

和III1,3/2,2單位；獲利1.65萬。基x1x2x3x4x5x*bx1103/21/83/401x*0011/41/212x2013/43/161/803/2

001/47/165/8033/2(5)計算B1P1’

和1

基x1x2x3x4x5bx15/4001/404x51/20–21/214x23/811/2–1/802–3/803/21/8014用B1P1’

和1

替換(1)中單純形終表中x1所在列得B1P1’

=(5/4,1/2,3/8)T1=c1’–cBB1P1=–3/8

換基迭代有：基x1x2x3x4x5bx11001/5016/5x500–22/5112/5x2011/2–1/504/5003/21/5076/5x*=(16/5,4/5)T即，工藝改進后，應(yīng)生產(chǎn)3.2單位的產(chǎn)品I,0.8單位的產(chǎn)品II;可獲利1.52萬元。最優(yōu)解為f*=76/5新資源限制考慮問題

Max

f=cx

s.t.

Ax

b

x0在原模型中增加一個資源限制

Max

f=cx

s.t.

Ax

b

x

x0問題:如何求出變化后的最優(yōu)解？設(shè)A=(B

N),其中B

是最優(yōu)基，且=(B,N).將增加約束后的模型化為標準型得：

Min

z=cx

s.t.

Ax+Imx’=b

x+xs=

x,x’,xs

0xBxNx’

xsxBBNIm

0bxsBN01

cB

cN

000列出其單純形表：此時，矩陣構(gòu)成了新問題的一個基，并且xBxNx’

xsxBBNIm

0bxsαBN01

cB

cN

000BB01于是xBxNx’xsxBI

B1NB1

0B1bxs0NBB1N

BB1

1

BB1b

0

cBB1N

cNcBB1

0cBB1b

由于B

是最優(yōu)基，故

0,B1b

0.

準則1.

若BB1b

0,則B’

是新最優(yōu)基。2.若BB1b

＜0,且NBB1N

0,BB1

0,則新問題無解；否則，可由對偶單純形法求解。xs0NBB1N

BB1

1

αBB1b

例6.

某廠用三種原料生產(chǎn)兩種產(chǎn)品，其工況如下：原料產(chǎn)品A產(chǎn)品B資源甲84220乙55170丙34120單價(元)80100應(yīng)如何安排生產(chǎn)可獲利最多？若甲原料不允許有剩余，求最優(yōu)方案。增加限制4x1+6x2

164，求最優(yōu)方案。解(1)設(shè)產(chǎn)品A

生產(chǎn)x1

單位，產(chǎn)品B

生產(chǎn)x2單位。則

Max

f=80x1＋100x2

s.t.8x1＋4x22205x1＋5x21703x1＋4x2120

xi0,i=1,2.

Minz=80x1100x2

s.t.8x1﹢4x2﹢x3=2205x1+5x2﹢x4=170

3x1+4x2x5=120

xi0,i=1,…,5.化為標準型得：基x1x2x3x4x5x384100220x455010170x534001120801000000基x1x2x3x4x5x30014420x11004/5116x20103/51180004203080

x*=(16,18)T;f*=3080.生產(chǎn)A:16,B:18,獲利3080元。14404/5103/51若甲原料不允許有剩余，可將甲資源約束改為等式，用二階段法重新計算?；鵻1x2x3x4x5x384100220x455010170x534001120*001000801000000基x1x2x3x4x5x384100220x455010170x534001120*84000220801000000基x1x2x3x4x5x384100220x455010170x534001120*84000220801000000基x1x2x3x4x5x111/21/80055/2x405/25/81065/2x505/23/8

0175/2*00100006010002200基x1x2x4x5x111/20055/2x405/21065/2x505/20175/2060002200基x1x2x4x5x1101/5021x2012/5013x500115002402980第二階段基x1x2x3x4x5x5001/4115x1101/4