單純形法的靈敏度分析與對偶對偶問題市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

分別用大M法和兩階段法求解以下線形規(guī)劃問題,并指出解類型minZ=2x1+3x2+x3x1+4x2+2x3≥8S.t.3x1+2x2≥6x1,x2,x3≥0時(shí)間:1:40—2:10單純形法的靈敏度分析與對偶對偶問題第1頁CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x7-2-3-100-M-M8142-1010x6x7-M-M初始單純形表格4M-26M-32M-1-M-M0063200-101CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x7-2-3-100-M-M9/5013/5-3/101/103/10-1/10X2x1-3-2最終單純形表格4M-26M-32M-1-M-M004/510-2/51/5-2/5-1/52/5單純形法的靈敏度分析與對偶對偶問題第2頁第六章

單純形法靈敏度分析與對偶DUAL窗含西嶺千秋雪，門泊東吳萬里船對偶是一個(gè)普遍現(xiàn)象單純形法的靈敏度分析與對偶對偶問題第3頁§1單純形表靈敏度分析(重點(diǎn).難點(diǎn).掌握)§2線性規(guī)劃對偶問題(重點(diǎn).了解.掌握)§3對偶規(guī)劃基本性質(zhì)(重點(diǎn).應(yīng)用)§4對偶單純形法(難點(diǎn).掌握---前面已講)學(xué)習(xí)重點(diǎn)與難點(diǎn)§1單純形表靈敏度分析(重點(diǎn).難點(diǎn).掌握)單純形法的靈敏度分析與對偶對偶問題第4頁§2線性規(guī)劃對偶問題一、對偶問題實(shí)例例1某工廠生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B和C三種資源，已知每件產(chǎn)品對這三種資源消耗、這三種資源現(xiàn)有數(shù)量和每件產(chǎn)品可取得利潤如表所表示.問：怎樣安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源又使總利潤最大？

產(chǎn)品資源甲乙資源限制A3265B2140C0375單件利潤15002500

該問題數(shù)學(xué)模型為：maxZ=1500x1+2500x2s.t.3x1+2x265A資源2x1+x240B資源3x275C資源x1,x20單純形法的靈敏度分析與對偶對偶問題第5頁考慮：1、定價(jià)不能太高？2、定價(jià)不能太低？假設(shè)該廠現(xiàn)自己不生產(chǎn)，因而要轉(zhuǎn)讓資源A、B和C，請問他們應(yīng)怎樣給這三種資源定價(jià)？咋辦？設(shè)A、B、C資源出售價(jià)格分別為y1、y2和y3甲乙資源限制A3265y1B2140y2C0375y3單件利潤15002500≥1500≥2500≥0單純形法的靈敏度分析與對偶對偶問題第6頁原問題：maxZ=1500x1+2500x2s.t.3x1+2x265A資源2x1+x240B資源3x275C資源x1,x20對偶問題：MinW=65y1+40y2+75y3s.t.3y1+2y2

≥15002y1+y2+3y3≥2500y1,y2,y3≥02103A=654075b=15002500c=20213A=15002500b=654075c=maxmin單純形法的靈敏度分析與對偶對偶問題第7頁對偶問題

MinW=bTYs.t.ATY≥CT Y≥0≥maxbACCTATbT≤minmnmn二、對偶問題形式

1、對稱型對偶問題原問題

MaxZ=cXs.t.AX≤b X≥0單純形法的靈敏度分析與對偶對偶問題第8頁對偶關(guān)系表

x1x2…xm…xnc1c2…cm…cnmaxZminW

Y1A11a12…a1m…a1n≤b1Y2a21a22…a2m…a2n≤b2Ymam1am2…amm…amn≤bm單純形法的靈敏度分析與對偶對偶問題第9頁由表能夠看出：從行看是原問題（Ⅰ），從列看是對偶問題（Ⅱ），兩個(gè)問題變量系數(shù)矩陣互為轉(zhuǎn)置矩陣。原問題（Ⅰ）常數(shù)項(xiàng)是對偶問題（Ⅱ）目標(biāo)系數(shù)，反之，原問題（Ⅰ）目標(biāo)系數(shù)是對偶問題（Ⅱ）常數(shù)項(xiàng)。原問題（Ⅰ）有n個(gè)決議變量，對偶問題（Ⅱ）有n個(gè)約束方程；原問題有m個(gè)約束方程，對偶問題就有m個(gè)決議變量。原問題約束是“≤”型，對偶問題約束是“≥”型。原問題目標(biāo)函數(shù)是求極大，對偶問題目標(biāo)是求極小。單純形法的靈敏度分析與對偶對偶問題第10頁maxZ＝5x1+4x2

例2請給出以下線性規(guī)劃問題對偶問題：對稱型線性規(guī)劃問題

怎么樣簡單吧單純形法的靈敏度分析與對偶對偶問題第11頁

2、非對稱型對偶問題表對偶變換規(guī)則約束條件類型(規(guī)范是否)與非負(fù)條件相互對應(yīng)非標(biāo)準(zhǔn)約束條件類型對應(yīng)非正常非負(fù)條件對偶變換是一一對應(yīng)好難記呀！單純形法的靈敏度分析與對偶對偶問題第12頁例3：Minz=5x1+25x27x1+75x2≤98s.t.5x1+6x2=7824x1+12x2≥54x1≥0、x2≤0Maxw=98y1+78y2+54y37y1+5y2+24y3≤

5s.t.75y1+6y2+12y3≥25y1≤

0、y2無限制、y3≥0

怎么樣，沒問題吧！單純形法的靈敏度分析與對偶對偶問題第13頁對稱形式線形規(guī)劃問題為:MaxZ=cXs.t.AX≤b X≥0加上松弛變量化為標(biāo)準(zhǔn)形后為:MaxZ=cX+0Xss.t.AX+IXs=b X≥0,Xs≥0§3對偶規(guī)劃基本性質(zhì)一、單純形法計(jì)算矩陣描述:單純形法的靈敏度分析與對偶對偶問題第14頁檢驗(yàn)數(shù)j當(dāng)?shù)舾刹?，基變量為XB時(shí)，新單純形表:bXS0Cj

XBXNXS

BNI

CBCN0

CBCN0檢驗(yàn)數(shù)jB-1bXBCBCj

XBXNXS

IB-1NB-1

0CN-CBB-1N-CBB-1

CBCN0初始單純形表為:單純形法的靈敏度分析與對偶對偶問題第15頁maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000

35000舉例單純形法的靈敏度分析與對偶對偶問題第16頁最優(yōu)基

Cj35000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3檢驗(yàn)數(shù)j

000-1/2-1x3x2x1最優(yōu)基逆

最優(yōu)基和最優(yōu)基逆單純形法的靈敏度分析與對偶對偶問題第17頁maxZ=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1,x2≥0maxZ=2x1+x2+0x3+0x4+0x55x2+x3=15s.t.6x1+2x2+x4=24x1+x2+x5=5x1,x2,x3,x4,x5≥0例4：對稱形線性規(guī)劃問題：標(biāo)準(zhǔn)型：單純形法的靈敏度分析與對偶對偶問題第18頁

j

x3x1x20210

00-1/4-1/2x1x2x3x4x5CBXBbCB

j

21000x3x4x5000150

5100246

201051

10012

1000初始單純形表最終單純形表B=(P3,P1,P2)15/20

015/4-15/27/21

001/4-1/23/20

10-1/43/2B-1=(P'3,P'4,P'5)初表中終表中單純形法的靈敏度分析與對偶對偶問題第19頁minZ=2x1+3x2+x3x1+4x2+2x3≥8S.t.3x1+2x2≥6x1,x2,x3≥0單純形法的靈敏度分析與對偶對偶問題第20頁CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x7-2-3-100-M-M8142-1010x6x7-M-M初始單純形表格4M-26M-32M-1-M-M0063200-101CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x7-2-3-100-M-M9/5013/5-3/101/103/10-1/10X2x1-3-2最終單純形表格000-1/2-1/2?-M?-M4/510-2/51/5-2/5-1/52/5單純形法的靈敏度分析與對偶對偶問題第21頁maxZ=50x1+100x2x1+x2≤300s.t.2x1+x2≤400x2≤250x1,x2≥0maxZ=50x1+100x2+0x3+0x4+0x5x1+x2+x3=300s.t.2x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0例5：對稱形線性規(guī)劃問題：x1x2x3x4x5CBXBbCB

j

x3x4x50003001

11004002

10102500

100150

100000原問題初始單純形表50100000單純形法的靈敏度分析與對偶對偶問題第22頁已知最優(yōu)基基變量為x1，x4，x2，請直接寫出該線性規(guī)劃問題最終單純形表。并給出其對偶問題最優(yōu)解最優(yōu)基為B=（p1，p4，p2）=B-1=（p3'，p4'

，p5'

）=b'=B-1b=10-1-21100110121100110-1-2110013004002505050250=σj=Cj-CBB-1Pj

單純形法的靈敏度分析與對偶對偶問題第23頁x1x2x3x4x5CBXBbCB

j

x1x4x2500100501

010-1500

0-2112500

10010

0-500-50原問題最終單純形表50100000原問題初始單純形表x1x2x3x4x5CBXBbCB

j

x3x4x50004002

10102500

100150

100000501000003001

1100單純形法的靈敏度分析與對偶對偶問題第24頁檢驗(yàn)數(shù)j當(dāng)?shù)舾刹?，基變量為XB時(shí)，新單純形表:bXS0Cj

XBXNXS

BNI

CBCN0

CBCN0檢驗(yàn)數(shù)jB-1bXBCBCj

XBXNXS

IB-1NB-1

0CN-CBB-1N-CBB-1

CBCN0初始單純形表為:單純形法的靈敏度分析與對偶對偶問題第25頁對應(yīng)初始單純表中單位矩陣I，迭代后單純形表中為B-1初始單純表中基變量Xs=b，迭代后單純形表中為XB=B-1b初始單純表中約束系數(shù)矩陣為：[A,I]=[B,N,I]迭代后單純形表中約束系數(shù)矩陣為：[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]若初始矩陣中變量xj系數(shù)向量為Pj，迭代后為Pj`，則有：Pj`=B-1Pj

小結(jié)單純形法的靈敏度分析與對偶對偶問題第26頁當(dāng)B為最優(yōu)基時(shí)，迭代后單純表中檢驗(yàn)數(shù)：CN-CBB-1N≤0-CBB-1≤0因XB檢驗(yàn)數(shù)可寫為：CB-CBB-1B

故可重寫為：C-CBB-1A≤0-CBB-1≤0CBB-1稱為單純形乘子。若令YT=CBB-1則：C-YTA≤0ATY

≥C所以：ATY

≥CT

Y

≥0單純形法的靈敏度分析與對偶對偶問題第27頁可見檢驗(yàn)數(shù)相反數(shù)恰好是其對偶問題一個(gè)可行解，將這個(gè)解代入對偶問題目標(biāo)函數(shù)，有：W=YTb=CBB-1b=Z當(dāng)原問題為最優(yōu)解時(shí)，這時(shí)對偶問題為可行解，且二者含有相同目標(biāo)函數(shù)值，依據(jù)對偶問題基本性質(zhì)，將看到這時(shí)對偶問題解也為最優(yōu)解。所以從最優(yōu)解單純形表中同時(shí)能夠得到其對偶問題最優(yōu)解。單純形法的靈敏度分析與對偶對偶問題第28頁maxZ=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1,x2≥0maxZ=2x1+x2+0x3+0x4+0x55x2+x3=15y1s.t.6x1+2x2+x4=24y2x1+x2+x5=5y3x1,x2,x3,x4,x5≥0minW=15y1+24y2+5y36y2+y3-y4=2x1s.t.5y1+2y2+y3-y5=1x2y1,y2,y3,y4,y5≥0minW=15y1+24y2+5y36y2+y3≥2s.t.5y1+2y2+y3≥1y1,y2,y3≥0例5：對稱形線性規(guī)劃問題：對偶問題：標(biāo)準(zhǔn)型：單純形法的靈敏度分析與對偶對偶問題第29頁x1x2x3x4x5CBXBbCB

j

21000x3x1x202115/20

015/4-15/27/21

001/4-1/23/20

10-1/43/20

00-1/4-1/2y1y2y3y4y5CBXBbCB

j

-15-24-500y2y3-24-51/4-5/41

0-1/41/41/215/2

011/2-3/2-15/2

00-7/2-3/2-y4-y5-y1-y2-y3

-

x3-x4-x5-x1-x2原問題最終單純形表對偶問題最終單純形表松弛變量對偶變量剩下變量決議變量單純形法的靈敏度分析與對偶對偶問題第30頁例6、利用原問題最優(yōu)單純形表求解對偶問題最優(yōu)解s.t.≤100≤100≥0解:對偶問題為s.t.≥4≥3≥7≥0單純形法的靈敏度分析與對偶對偶問題第31頁CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x54370025-3/4103/4-1/2255/401-1/41/2x2x337

-5/200-1/2-2最終單純形表格x4x5松弛變量可見原問題最優(yōu)解為:X*=(0,25,25)T其對偶問題最優(yōu)解為:y*=(1/2,2)T單純形法的靈敏度分析與對偶對偶問題第32頁

為了便于討論，下面不妨總是假設(shè):定理1（對稱性定理）對偶問題對偶是原問題。依據(jù)對稱性定理，在任一對偶問題中，能夠把其中任何一個(gè)稱為原問題，而把另一個(gè)稱為其對偶問題。:?íì33=0YCTATYbTY..mintsW對偶問題=:?íì3￡0XbAXCX..maxtsZ原問題二、對偶問題基本性質(zhì):單純形法的靈敏度分析與對偶對偶問題第33頁?íì33=0YCTATYbTY..mintsW?íì3≤=0Y-CT-ATY-bTY..maxts(-W)?íì3≤=0..maxXbAXtsCXZ證實(shí):由前面可知對偶問題為:等價(jià)于該問題:可見此問題為對稱型規(guī)劃問題,其對偶問題表示為:令Z=-f,則化簡為:即為原問題可見對偶問題對偶是原問題。證畢單純形法的靈敏度分析與對偶對偶問題第34頁

定理2（弱對偶性定理）

對偶問題(min)任何可行解Y0，其目標(biāo)函數(shù)值總是大于原問題(max)任何可行解X0目標(biāo)函數(shù)值。證:假設(shè)X0,Y0分別為原問題和對偶問題可行解,故有:?íì3￡0X0bAX0CX0..maxtsZ?íì33=0Y0CTATY0bTY0..mintsW=--------(1)--------(2)因?yàn)閅0是對偶問題可行解,用Y0T左乘(1)得:Y0TAX0≤Y0Tb轉(zhuǎn)置得:X0TATY0≤bTy0

因?yàn)閄0是原問題可行解,用X0左乘(2)得:X0TATY0≥X0TCT

轉(zhuǎn)置得:Y0TAX0≥CX0可見CX0≤Y0TAX0≤Y0Tb=bTY0

即CX0≤bTY0單純形法的靈敏度分析與對偶對偶問題第35頁例7、應(yīng)用弱對偶定理，證實(shí)以下線性規(guī)劃問題最大值不超出1.

s.t.證實(shí)：該線性問題對偶問題為：

單純形法的靈敏度分析與對偶對偶問題第36頁弱對偶定理推論

推論1最優(yōu)解判別定理若原問題某個(gè)可行解X0目標(biāo)函數(shù)值與對偶問題某個(gè)可行解Y0目標(biāo)函數(shù)值相等，則X0,Y0分別是相應(yīng)問題最優(yōu)解證：由弱對偶定理可知結(jié)論是顯然,即CX0=bTY0

CX,bTY0=CX0

Yb。證畢。單純形法的靈敏度分析與對偶對偶問題第37頁推論2

假如原max(min)問題為無界解，則其對偶min(max)問題無可行解(反之不然)maxZ=x1+x2x1-x2≤-1s.t.-x1+x2≤-1x1,x2≥0minW=-y1-y2y1-y2≥1s.t.-y1+y2≥

1y1,y2≥

0原問題和對偶問題同時(shí)無可行解單純形法的靈敏度分析與對偶對偶問題第38頁推論3原問題(max)任何可行解目標(biāo)函數(shù)值是其對偶問題(min)目標(biāo)函數(shù)值下界；原問題(min)任何可行解目標(biāo)函數(shù)值是其對偶問題(max)目標(biāo)函數(shù)值上界推論4

假如原問題max(min)有可行解，其對偶問題min(max)無可行解，則原問題為無界解單純形法的靈敏度分析與對偶對偶問題第39頁例8、應(yīng)用對偶理論證實(shí)以下線性規(guī)劃問題目標(biāo)函數(shù)值無界.s.t.證實(shí)：

是線性問題可行解，即該問題存在可行解；

又∵其對偶問題為：單純形法的靈敏度分析與對偶對偶問題第40頁

定理3主對偶定理(強(qiáng)對偶性定理)

假如原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們最優(yōu)解所對應(yīng)目標(biāo)函數(shù)值相等。

證:

由弱對偶定理推論1可知，原問題和對偶問題目標(biāo)函數(shù)有界，故一定存在最優(yōu)解?，F(xiàn)證實(shí)定理后一句話。設(shè)X0為原問題最優(yōu)解，它所對應(yīng)基矩陣是B，

X0=B1

b，則其檢驗(yàn)數(shù)滿足CCBB1A0令Y0=

CBB1，則有Y0

AC

顯然Y0為對偶問題可行解。所以有對偶問題目標(biāo)函數(shù)值,

W=Y0b=CBB1

b而原問題最優(yōu)解目標(biāo)函數(shù)值為

Z=CX0=CBB1

b故由最優(yōu)解判別定理可知Y0為對偶問題最優(yōu)解。證畢。單純形法的靈敏度分析與對偶對偶問題第41頁定理4互補(bǔ)松弛定理定理

設(shè)X0,Y0分別是原問題和對偶問題可行解，U0為原問題松弛變量值、V0為對偶問題剩下變量值。X0,Y0分別是原問題和對偶問題最優(yōu)解充分必要條件是Y0

U0

=V0X0=0證：由定理所設(shè)，可知有AX0+U0=bX0,U00(1)Y0AV0

=CY0,V00(2)分別以Y0左乘(1)式，以X0右乘(2)式后，兩式相減，得Y0U0+V0X0

=Y0b

CX0若Y0U0+V0X0

=0，依據(jù)最優(yōu)解判別定理，X0,Y0分別是原問題和對偶問題最優(yōu)解。反之亦然。證畢。單純形法的靈敏度分析與對偶對偶問題第42頁例9、考慮以下原始線性規(guī)劃

(1)寫出其對偶問題；(2)已知（3,2,0）是上述原始問題最優(yōu)解，依據(jù)互補(bǔ)松弛定理，求出對偶問題最優(yōu)解；(3)假如上述規(guī)劃中第一個(gè)約束為資源約束，寫出這種資源影子價(jià)格.解：（1）對偶問題：單純形法的靈敏度分析與對偶對偶問題第43頁（2）由題知原問題最優(yōu)解為

由互補(bǔ)松弛定理得：在對偶問題中對應(yīng)第一，二個(gè)約束為緊約束，第三個(gè)約束條件為松約束，即，∴對偶規(guī)劃問題最優(yōu)解

（3）影子價(jià)格為y1=4

-1(4,-1)單純形法的靈敏度分析與對偶對偶問題第44頁例10：利用互補(bǔ)松弛定理

單純形法的靈敏度分析與對偶對偶問題第45頁單純形法的靈敏度分析與對偶對偶問題第46頁原問題檢驗(yàn)數(shù)與對偶問題解總結(jié)在主對偶定理(強(qiáng)對偶性)證實(shí)中我們有：對偶(min型))變量最優(yōu)解等于原問題松弛變量機(jī)會(huì)成本，或者說原問題松弛變量檢驗(yàn)數(shù)絕對值輕易證實(shí)，對偶問題最優(yōu)解剩下變量解值等于原問題對應(yīng)變量檢驗(yàn)數(shù)絕對值因?yàn)樵瓎栴}和對偶問題是相互對偶，所以對偶問題檢驗(yàn)數(shù)與原問題解也有類似上述關(guān)系。更普通地講，不論原問題是否標(biāo)準(zhǔn)，在最優(yōu)解單純型表中，都有原問題虛變量(松弛或剩下)檢驗(yàn)數(shù)對應(yīng)其對偶問題實(shí)變量(對偶變量)最優(yōu)解，原問題實(shí)變量(決議變量)檢驗(yàn)數(shù)對應(yīng)其對偶問題虛變量(松弛或剩下變量)最優(yōu)解。所以，原問題或?qū)ε紗栴}只需求解其中之一就能夠了。單純形法的靈敏度分析與對偶對偶問題第47頁§4對偶單純形法一、對偶單純形法基本思緒單純形迭代要求每步都是基本可行解到達(dá)最優(yōu)解時(shí)，檢驗(yàn)數(shù)cj–zj

0(max)但對于所加剩下變量無法組成初始基礎(chǔ)可行解，所以經(jīng)過加人工變量來處理大M法和二階段法較繁能否從剩下變量組成初始基礎(chǔ)非可行解出發(fā)迭代，但確保檢驗(yàn)數(shù)滿足最優(yōu)條件，cj–zj

0(max)b=B1b0單純形法的靈敏度分析與對偶對偶問題第48頁≤0≤0？單純形法的靈敏度分析與對偶對偶問題第49頁二、對偶單純形法計(jì)算步驟對某線形規(guī)劃問題存在一個(gè)對偶問題可行基，即必須全部cj-zj≤0，bi值不要求全為正:1、確定換出變量（離基變量）在小于0b中找出最小者，其所對應(yīng)變量xr為換出變量2、確定換入變量（進(jìn)基變量）

θ=min{σj/arj|arj<0}=σk/ark其所對應(yīng)變量xk為換入變量3、確定主元素：ark為主元素4、用換入變量替換換出變量，繼續(xù)迭代得到一個(gè)新基5、檢驗(yàn)是否全部bi

≥0，如是，找到了二者最優(yōu)解，不然返回第一步循環(huán)進(jìn)行。單純形法的靈敏度分析與對偶對偶問題第50頁例12：對偶單純形法計(jì)算過程單純形法的靈敏度分析與對偶對偶問題第51頁x1x2x3x4x5CBXBbCB

j

-15-5-1100x4x500-5-3-2-21

0-4-5

-1-201-15

-5-1100初始單純形表θ→15/35/211/2------

j

x2x5

-505/23/21-1-1/2

0-3/2-7/2

0-1-1/21-15/2

0-6-5/20θ→15/7---65---

j

-5-1513/7014/7-5/7

3/73/71

02/71/7-2/7

0

0-27/7-10/7-15/7x2x1最終單純形表負(fù)數(shù)中最小者比值中最小者單純形法的靈敏度分析與對偶對偶問題第52頁檢驗(yàn)數(shù)j當(dāng)?shù)舾刹?，基變量為XB時(shí)，新單純形表:bXS0Cj

XBXNXS

BNI

CBCN0

CBCN0檢驗(yàn)數(shù)jB-1bXBCBCj

XBXNXS

IB-1NB-1

0CN-CBB-1N-CBB-1

CBCN0初始單純形表為:單純形法的靈敏度分析與對偶對偶問題第53頁§1單純形表靈敏度分析

靈敏度分析所研究問題是，當(dāng)某一規(guī)劃最優(yōu)解已知情況下，某數(shù)據(jù)發(fā)生改變后對最優(yōu)解產(chǎn)生影響。原數(shù)據(jù)發(fā)生改變主要原因可能有原始數(shù)據(jù)不可靠或準(zhǔn)確度不高，實(shí)際問題條件含糊不清或被忽略，最優(yōu)解執(zhí)行一段時(shí)間后環(huán)境條件發(fā)生改變等。單純形法的靈敏度分析與對偶對偶問題第54頁所以我們有必要研究以下問題:當(dāng)一些系數(shù)改變，最優(yōu)解改變多少?當(dāng)增加或降低變量，最優(yōu)解改變多少?當(dāng)增加或降低約束條件時(shí)，問題最優(yōu)解改變多少?最優(yōu)解不改變時(shí)，一些系數(shù)允許改變范圍又有多大?系數(shù)包含：目標(biāo)函數(shù)中價(jià)值系數(shù)cj、約束條件中常數(shù)項(xiàng)bi、約束條件中技術(shù)系數(shù)aij。單純形法的靈敏度分析與對偶對偶問題第55頁靈敏度分析步驟以下：將參數(shù)改變經(jīng)過計(jì)算反應(yīng)到最終單純表上來。檢驗(yàn)原問題是否仍為可行解；檢驗(yàn)對偶問題是否仍為可行解；按下表所列情況出結(jié)論或決定繼續(xù)計(jì)算步驟單純形法的靈敏度分析與對偶對偶問題第56頁原問題對偶問題結(jié)論或繼續(xù)計(jì)算步驟可行解可行解問題最優(yōu)解或最優(yōu)基不變可行解非可行解非可行解可行解非可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解用對偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新單純形表重新計(jì)算單純形法的靈敏度分析與對偶對偶問題第57頁靈敏度分析主要內(nèi)容一、目標(biāo)函數(shù)系數(shù)靈敏度分析二、約束條件常數(shù)項(xiàng)靈敏度分析三、增加或降低決議變量靈敏度分析四、系數(shù)矩陣靈敏度分析五、增加或降低約束條件靈敏度分析單純形法的靈敏度分析與對偶對偶問題第58頁一、目標(biāo)函數(shù)系數(shù)靈敏度分析

目標(biāo)函數(shù)中價(jià)值系數(shù)Cj改變只會(huì)引發(fā)檢驗(yàn)數(shù)σj改變，所以將Cj改變直接反應(yīng)到最終單純形表中，只可能出現(xiàn)表中前兩種情況。例13佳美企業(yè)計(jì)劃制造Ⅰ、Ⅱ兩種產(chǎn)品，已知各制造一個(gè)單位產(chǎn)品時(shí)，分別占用設(shè)備A、B臺(tái)時(shí)、調(diào)試時(shí)間、天天設(shè)備A、B臺(tái)時(shí)、調(diào)試工序可用于這兩種產(chǎn)品能力及各售出一單位時(shí)贏利情況，如表所表示。1、問應(yīng)怎樣組織生產(chǎn)才能使總利潤最多？2、假如產(chǎn)品Ⅰ利潤降至1.5百元/單位，而產(chǎn)品Ⅱ利潤增至2百元/單元時(shí)，最優(yōu)生產(chǎn)計(jì)劃有何改變？3、假如產(chǎn)品Ⅰ利潤不變，則產(chǎn)品Ⅱ利潤在什么范圍內(nèi)改變時(shí)，該企業(yè)最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生改變？j最終單純形表bXS0Cj

XBXNXS

BNI

CBCN0

CBCN0jB-1bXBCBCj

XBXNXS

IB-1NB-1

0CN-CBB-1N-CBB-1

CBCN0初始單純形表單純形法的靈敏度分析與對偶對偶問題第59頁產(chǎn)品資源ⅠⅡ天天可用能力設(shè)備A（h）0515設(shè)備B（h）6224調(diào)試工序（h）115利潤（百元）21

，解：設(shè)分別表示Ⅰ、Ⅱ兩種產(chǎn)品生產(chǎn)數(shù)量，可建立以下線性規(guī)劃模型：maxZ=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1,x2≥0maxZ=2x1+x2+0x3+0x4+0x55x2+x3=15

s.t.6x1+2x2+x4=24

x1+x2+x5=5

x1,x2,x3,x4,x5≥0yY1Y2y3單純形法的靈敏度分析與對偶對偶問題第60頁

j

x3x1x202115/20

015/4-15/27/21

001/4-1/23/20

10-1/43/20

00-1/4-1/2可見原問題含有唯一最優(yōu)解：思索：對偶問題最優(yōu)解和最優(yōu)值？x1x2x3x4x5CBXBbCB

j

21000x3x4x5000150

5100246

201051

10010

00-1/4-1/2初表終表單純形法的靈敏度分析與對偶對偶問題第61頁將產(chǎn)品Ⅰ、Ⅱ利潤改變直接反應(yīng)到最終單純形表中得表，因非基變量檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代計(jì)算2、假如產(chǎn)品Ⅰ利潤降至1.5百元/單位，而產(chǎn)品Ⅱ利潤增至2百元/單元時(shí)，最優(yōu)生產(chǎn)計(jì)劃有何改變？x1x2x3x4x5CBXBbCB

j

000x3x1x202115/20

015/4-15/27/21

001/4-1/23/20

10-1/43/20

00-1/4-1/2211.5201.520

001/8-9/4j最終單純形表bXS0Cj

XBXNXS

BNI

CBCN0

CBCN0jB-1bXBCBCj

XBXNXS

IB-1NB-1

0CN-CBB-1N-CBB-1

CBCN0初始單純形表單純形法的靈敏度分析與對偶對偶問題第62頁CBXBbCB

j

000x3x1x215/20

015/4-15/27/21

001/4-1/23/20

10-1/43/21.5201.52

0

001/8-9/4x1x2x3x4x5614---

j

x4x1x260

04/51-621

0-1/50130

11/500

01.52

0

0-1/100-3/2可見改變后問題含有唯一最優(yōu)解X*=(2,3)T單純形法的靈敏度分析與對偶對偶問題第63頁3、假如產(chǎn)品Ⅰ利潤不變，則產(chǎn)品Ⅱ利潤在什么范圍內(nèi)改變時(shí)，該企業(yè)最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生改變？x1x2x3x4x5CBXBbCB

j

2000x3x1x202115/20

015/4-15/27/21

001/4-1/23/20

10-1/43/20

00-1/4-1/21解：設(shè)產(chǎn)品Ⅱ利潤為c2元，反應(yīng)到最終單純形表中，得表：

c2

c20

00-1/2+1/4

c2

1-3/2

c2為使表中解仍為最優(yōu)解，應(yīng)有：-1/2+1/4

c2

≤01-3/2c2

≤0即產(chǎn)品Ⅱ利潤改變范圍是：[2/3，2]解得：2/3≤c

2≤2單純形法的靈敏度分析與對偶對偶問題第64頁二、約束條件常數(shù)項(xiàng)靈敏度分析

在現(xiàn)實(shí)問題中，約束條件右端常數(shù)項(xiàng)，往往代表資源限制量。普通來說，資源限制量不是一成不變，而是隨生產(chǎn)條件、市場供給情況進(jìn)行變動(dòng)。所以人們經(jīng)常想知道，對于一個(gè)確定優(yōu)方案，當(dāng)資源增加或降低多少時(shí)，對方案影響將有多大。這種類型靈敏度分析就是處理該類問題方法?，F(xiàn)假定問題第l種資源限制。因?yàn)槌?shù)項(xiàng)改變，對最優(yōu)判別準(zhǔn)則檢驗(yàn)數(shù)無關(guān)。即是說，最優(yōu)基對應(yīng)單純變量表中最終一行不發(fā)生改變。而表中基變量是否可行還需討論。j最終單純形表bXS0Cj

XBXNXS

BNI

CBCN0

CBCN0jB-1bXBCBCj

XBXNXS

IB-1NB-1

0CN-CBB-1N-CBB-1

CBCN0初始單純形表所以只可能出現(xiàn)表中1、3兩種情況單純形法的靈敏度分析與對偶對偶問題第65頁例14在上述佳美企業(yè)例子中：（1）若設(shè)備A和調(diào)試工序天天能力不變，而設(shè)備B天天能力增加到32小時(shí)，分析企業(yè)最優(yōu)計(jì)劃改變；（2）若設(shè)備A和B天天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)改變時(shí)，問題最優(yōu)基不變.解：（1）由題意得改變后b為b`:所以有1532515/4-15/201/4-1/20-1/43/2B-1b`=15/4-15/201/4-1/20-1/43/2B-1=由最終單純形表得原最優(yōu)基逆矩陣:15325b`==35/211/2-1/2將其反應(yīng)到最終單純形表中

j

x3x1x202115/20

015/4-15/27/21

001/4-1/23/20

10-1/43/20

00-1/4-1/2x1x2x3x4x5CBXBbCB

j

21000x3x4x5000150

5100246

201051

10010

00-1/4-1/2初表終表單純形法的靈敏度分析與對偶對偶問題第66頁CBXBbCB

j

x3x1x2021

0

015/4-15/2

1

001/4-1/2

0

10-1/43/20

00-1/4-1/2x1x2x3x4x521000

j

150

510051

10012

0

-401-60

-100-2x3x1x402

035/211/2-1/2可見改變后問題含有唯一最優(yōu)解:X*=(5,0)TZ*=10單純形法的靈敏度分析與對偶對偶問題第67頁第二種解法利用改變率所以有08015/4-15/201/4-1/20-1/43/2B-1?b==102-2將其反應(yīng)到最終單純形表中因?yàn)锽-1

b'=B-1(b+?b)=B-1b+B-1

?b終表中第三列080b'=15325=b+?b=15245+解：單純形法的靈敏度分析與對偶對偶問題第68頁CBXBbCB

j

x3x1x202115/2

0

015/4-15/27/2

1

001/4-1/23/2

0

10-1/43/20

00-1/4-1/2x1x2x3x4x521000

j

150

510051

10012

0

-401-60

-100-2x3x1x402

0+10=35/2+2=11/2-2=-1/2可見改變后問題含有唯一最優(yōu)解:X*=(5,0)TZ*=10單純形法的靈敏度分析與對偶對偶問題第69頁（2）若設(shè)備A和B天天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)改變時(shí)，問題最優(yōu)基不變.解法一:設(shè)調(diào)試工序天天可用能力為b3小時(shí)1524b315/4-15/201/4-1/20-1/43/2B-1b`==45-15/2

b36-1/2b3

-6+3/2b3

要使問題最優(yōu)基不變，只要其新b列數(shù)全部大于等于零，即：45-15/2

b3≥06-1/2

b3

≥0-6+3/2b3

≥04≤b3≤6由此調(diào)試工序能力應(yīng)在4~6小時(shí)之間1524b3

b`=單純形法的靈敏度分析與對偶對偶問題第70頁解法二：設(shè)調(diào)試工序天天可用能力為5+Δb300Δb315/4-15/201/4-1/20-1/43/2B-1?b==-15/2Δb3

-1/2Δb3

3/2Δb3

將其反應(yīng)到最終單純形表中,其b列數(shù)字為:B-1

b'=15/2-15/2

Δb3

7/2-1/2

Δb3

3/2+3/2

Δb3

當(dāng)B-1

b'≥0時(shí),問題最優(yōu)基不變,解得-1≤Δb3

≤14≤5+

Δb3

≤6由此調(diào)試工序能力應(yīng)在4~6小時(shí)之間因?yàn)锽-1

b'=B-1(b+?b)=B-1b+B-1

?b終表中第三列00Δb3b'=15245+Δb3=b+?b=15245+單純形法的靈敏度分析與對偶對偶問題第71頁三、決議變量靈敏度分析

在討論一個(gè)規(guī)劃問題時(shí)，從資源充分利用角度考慮，有時(shí)認(rèn)為多安排一些生產(chǎn)項(xiàng)目是有利，這反映在線性規(guī)劃模型上是增添決策變量問題。其次當(dāng)規(guī)劃執(zhí)行一段時(shí)間后，資源供給不能滿足要求時(shí)，有時(shí)也要考慮少安排一些生產(chǎn)項(xiàng)目是有利，這反映在數(shù)模上就是降低決策變量問題。所以，決策變量個(gè)數(shù)變化有兩種情況，一是增多，一是降低?，F(xiàn)分別在下面討論。單純形法的靈敏度分析與對偶對偶問題第72頁(1)增加決議變量靈敏度分析

設(shè)已知增加新變量xj目標(biāo)函數(shù)為cj，對應(yīng)約束系數(shù)為aij（或表示為Pj），其分析步驟為：2、計(jì)算檢驗(yàn)數(shù)1、計(jì)算P'j=B-1Pj3、若σ‘j≤0，原最優(yōu)解不變，只需將計(jì)算得到P’jσ‘j和直接寫入最終單純形表中；若σ‘j>0，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)解j最終單純形表bXS0Cj

XBXNXS

BNI

CB