第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件

§2線性規(guī)劃的對(duì)偶理論與靈敏度分析§2-1線性規(guī)劃的對(duì)偶問(wèn)題對(duì)偶:在不同的領(lǐng)域有著不同的詮釋。在詞語(yǔ)中，它是一種修辭方法，兩個(gè)字?jǐn)?shù)相等、結(jié)構(gòu)相似的語(yǔ)句表現(xiàn)相關(guān)或相反的意思。在數(shù)學(xué)上表現(xiàn)為數(shù)式或圖形的對(duì)稱,命題或結(jié)構(gòu)的對(duì)應(yīng)

§2線性規(guī)劃的對(duì)偶理論與靈敏度分析§2-1線性規(guī)劃的11.對(duì)偶問(wèn)題的提出例1第一章例1中美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品時(shí),其線性規(guī)劃問(wèn)題為1.對(duì)偶問(wèn)題的提出例1第一章例1中美佳公司利用該2

假定有某個(gè)公司想把美佳公司的資源買過(guò)來(lái)，它至少應(yīng)付出多大代價(jià)，才能使美住公司愿意放棄生產(chǎn)活動(dòng)，出讓自己的資源。美佳公司愿意讓自己資源的條件是，出讓代價(jià)應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活動(dòng)時(shí)獲取的贏利。1.對(duì)偶問(wèn)題的提出假定有某個(gè)公司想把美佳公司的資源買過(guò)來(lái)，它至少應(yīng)付出3用y1，y2，y3代表單位時(shí)間設(shè)備A、設(shè)備B和調(diào)試工序的出讓代價(jià)，為使美佳公司愿意出讓自己的資源（出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少），則：

收購(gòu)美佳公司應(yīng)付出的代價(jià)為（總的收購(gòu)價(jià)越小越好）：15y1+24y2+5y31.對(duì)偶問(wèn)題的提出用y1，y2，y3代表單位時(shí)間設(shè)備A、設(shè)備B和調(diào)試工序的出讓41.對(duì)偶問(wèn)題的提出1.對(duì)偶問(wèn)題的提出5)2(LP???íì33++3+++=0,,12526st.

52415min32132132321yyyyyyyyyyyw比較LP1和LP2)2(LP???íì33++3+++=0,,12526st.6對(duì)偶問(wèn)題minW=Y’b

A’Y

C’Y0maxZ=CX

AX

bX0原問(wèn)題每個(gè)線性規(guī)劃問(wèn)題都存在一個(gè)與其對(duì)應(yīng)的對(duì)偶問(wèn)題對(duì)偶問(wèn)題minW=Y’bmaxZ=CX原問(wèn)題72.對(duì)偶問(wèn)題的一般形式2.對(duì)偶問(wèn)題的一般形式8矩陣形式表示原－對(duì)偶問(wèn)題原問(wèn)題(P) 對(duì)偶問(wèn)題(D)價(jià)格系數(shù)—————— 資源向量資源向量—————— 價(jià)格系數(shù)最大化—————— 最小化變量個(gè)數(shù)—————— 約束個(gè)數(shù)約束個(gè)數(shù)—————— 變量個(gè)數(shù)約束系數(shù)行 ————— 約束系數(shù)列互稱對(duì)偶問(wèn)題對(duì)應(yīng)關(guān)系：矩陣形式表示原－對(duì)偶問(wèn)題原問(wèn)題(P) 對(duì)偶93.非對(duì)稱形式的原－對(duì)偶問(wèn)題關(guān)系3.非對(duì)稱形式的原－對(duì)偶問(wèn)題關(guān)系10第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件11第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件12對(duì)偶變換的規(guī)則約束條件的類型與非負(fù)條件對(duì)偶非標(biāo)準(zhǔn)的約束條件類型對(duì)應(yīng)非正常的非負(fù)條件對(duì)偶變換的規(guī)則約束條件的類型與非負(fù)條件對(duì)偶13練習(xí)：練習(xí)：14矩陣形式表示原－對(duì)偶問(wèn)題原問(wèn)題(P) 對(duì)偶問(wèn)題(D)價(jià)格系數(shù)—————— 資源向量資源向量—————— 價(jià)格系數(shù)最大化—————— 最小化變量個(gè)數(shù)—————— 約束個(gè)數(shù)約束個(gè)數(shù)—————— 變量個(gè)數(shù)約束系數(shù)行 ————— 約束系數(shù)列互稱對(duì)偶問(wèn)題對(duì)應(yīng)關(guān)系：矩陣形式表示原－對(duì)偶問(wèn)題原問(wèn)題(P) 對(duì)偶15對(duì)偶變換的規(guī)則約束條件的類型與非負(fù)條件(非負(fù)約束)對(duì)偶非標(biāo)準(zhǔn)的約束條件類型對(duì)應(yīng)非正常的非負(fù)條件對(duì)偶變換的規(guī)則約束條件的類型與非負(fù)條件(非負(fù)約束)對(duì)偶16§2-2對(duì)偶問(wèn)題的基本性質(zhì)1.對(duì)稱性：一個(gè)線性規(guī)劃的對(duì)偶問(wèn)題的對(duì)偶問(wèn)題即是原問(wèn)題2.弱對(duì)稱性：假定X是原規(guī)劃（P）的任一可行解，Y是對(duì)偶規(guī)劃（D）的任一可行解，則有CX≤bTY3.無(wú)界性：若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解§2-2對(duì)偶問(wèn)題的基本性質(zhì)1.對(duì)稱性：一個(gè)線性規(guī)174.設(shè)X是原問(wèn)題的可行解，Y是對(duì)偶問(wèn)題的可行解，當(dāng)CX＝bTY時(shí)，X，Y皆為最優(yōu)解。5.強(qiáng)對(duì)偶性原規(guī)劃有最優(yōu)解，則對(duì)偶規(guī)劃也有最優(yōu)解，且最優(yōu)值相同。6.互補(bǔ)松弛性(松緊定理)在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值非0，則該約束取嚴(yán)格等式，如果約束條件取嚴(yán)格不等式，其對(duì)應(yīng)的對(duì)偶變量一定為0?！?-2對(duì)偶問(wèn)題的基本性質(zhì)4.設(shè)X是原問(wèn)題的可行解，Y是對(duì)偶問(wèn)題的可行解，當(dāng)CX18原問(wèn)題與對(duì)偶問(wèn)題最終單純型表的比較原問(wèn)題與對(duì)偶問(wèn)題最終單純型表的比較19第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件20在最優(yōu)解的單純型表中，原問(wèn)題虛變量(松弛或剩余)的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題實(shí)變量(對(duì)偶變量)的最優(yōu)解，原問(wèn)題實(shí)變量(決策變量)的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題虛變量(松弛或剩余變量)的最優(yōu)解。在最優(yōu)解的單純型表中，原問(wèn)題虛變量(松弛或剩余)的檢21例：min

=2x1+3x2+5x3+2x4+3x5其對(duì)偶解y1﹡=4/5y2﹡=3/5Z﹡=5用對(duì)偶理論求(P)的最優(yōu)解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53

xi0(i=1…5)(P)對(duì)偶性質(zhì)的應(yīng)用例：min=2x1+3x2+5x3+2x4+3x522解：(D)為maxZ

=4y1+3y2y1+2y22①y1-y23②2y1+3y25③y1+y22④3y1+y23⑤y1,

y20其對(duì)偶解y1﹡=4/5y2﹡=3/5解：(D)為maxZ=4y1+3y2其對(duì)偶解y1﹡=23將y1﹡，y2﹡代入，知②,③,④為嚴(yán)格不等式∴x2=x3=x4=0∴x

=(1,0,0,0,1)T

Z=5由y1﹡，y2﹡﹥0知原約束為等式

x1+3x5=42x1+x5=3將y1﹡，y2﹡代入，知②,③,④為嚴(yán)格不等式∴x24§2—3影子價(jià)格§2—3影子價(jià)格25

當(dāng)線性規(guī)劃原問(wèn)題求得最優(yōu)解xj*時(shí)，其對(duì)偶問(wèn)題也得到最優(yōu)解yi*，且式中bi*是線性規(guī)劃原問(wèn)題約束條件的右端項(xiàng)，代表第i種資源的擁有量；對(duì)偶變量yi*的意義代表在資源最優(yōu)利用條件下對(duì)單位第i種資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，這個(gè)概念在西方經(jīng)濟(jì)學(xué)中稱為影子價(jià)格當(dāng)線性規(guī)劃原問(wèn)題求得最優(yōu)解xj*時(shí)，其對(duì)偶問(wèn)題26影子價(jià)格提供的信息1.影子價(jià)格可以告訴決策者，增加哪一種資源對(duì)增加效益最有利。影子價(jià)格提供的信息1.影子價(jià)格可以告訴決策者，增加哪一種資27第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件28

資源1影子價(jià)格為0，增加與否對(duì)總利潤(rùn)沒(méi)有影響。 資源2影子價(jià)格為1，增加一個(gè)單位，總利潤(rùn)增加1， 資源3影子價(jià)格為3，增加一個(gè)單位，一產(chǎn)品產(chǎn)量34件，二產(chǎn)品產(chǎn)量12，總利潤(rùn)218，增加3，資源3對(duì)目標(biāo)函數(shù)貢獻(xiàn)最大， 資源3售價(jià) <3購(gòu)入生產(chǎn)獲利 >3賣出獲利資源1影子價(jià)格為0，增加與否對(duì)總利潤(rùn)沒(méi)有影響。292.影子價(jià)格可以告訴決策者，用多大代價(jià)增加資源才是合算——機(jī)會(huì)成本。如：資源3的影子價(jià)格為3，即增加一個(gè)單位的會(huì)使收益增加3，獲取資源3的代價(jià)<3，就可以獲利。3.影子價(jià)格告訴決策者，資源利用程度對(duì)線性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，對(duì)于對(duì)偶問(wèn)題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。影子價(jià)格不為零，則該資源已消耗完畢；影子價(jià)格為零，則該資源沒(méi)有充分利用2.影子價(jià)格可以告訴決策者，用多大代價(jià)增加資源才是合算——30§2－4對(duì)偶單純形法§2－4對(duì)偶單純形法31第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件32對(duì)某標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題當(dāng)所有檢驗(yàn)數(shù)小于等于零（cj-zj≤0），bi≥0；此線性規(guī)劃問(wèn)題取得最優(yōu)解。若存在bi<0,則用對(duì)偶單純形法進(jìn)行求解。對(duì)某標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題當(dāng)所有檢驗(yàn)數(shù)小于等33應(yīng)用對(duì)偶單純形法進(jìn)行求解時(shí)，bi的值不要求為正。單純形法計(jì)算的前提是bi的值總保持非負(fù)，對(duì)偶單純形法計(jì)算的前提是檢驗(yàn)數(shù)總保持非正。應(yīng)用對(duì)偶單純形法進(jìn)行求解時(shí)，bi的值不要求34對(duì)偶單純形法基本步驟max型(min型)(1)、確定初始基Bo,作初始表，使全部σj

0(0)(2)、檢驗(yàn)：若B-1b0，是最優(yōu)。否則轉(zhuǎn)（3）(b)l=min{(b)i}----xl出基b<0(3)、基變換，先確定出基變量xl對(duì)偶單純形法基本步驟max型(min型)(1)、確35再確定換入基變量①若Xl所在行的alj全0，停，原問(wèn)題無(wú)可行解。②若Xl行的alj有alj<0,則求θ=min{}=σjσkaljalkalj<0

Xk為換入變量(4)、以alk為主元，換基迭代再確定換入基變量①若Xl所在行的alj全036第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件37第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件38第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件39第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件40

對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可行基，因而這種方法在求解線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)應(yīng)用.對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很41§2-5靈敏度分析§2-5靈敏度分析42

靈敏度是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度。在線性規(guī)劃問(wèn)題中，假定aij,bi,cj是己知常數(shù)。但實(shí)際上這些數(shù)往往是一些估計(jì)和預(yù)測(cè)的數(shù)字，如隨市場(chǎng)條件變化，cj值就會(huì)變化。aij隨工藝技術(shù)條件的改變而改變，而bi值是根據(jù)資源投入后能產(chǎn)生多大經(jīng)濟(jì)效果來(lái)決定的一種決策選擇。

§2-5靈敏度分析靈敏度是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程43

當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問(wèn)題的最優(yōu)解會(huì)有什么變化，或者這些參數(shù)在一個(gè)多大范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)解不變。這就是靈敏度分析所要研究解決的問(wèn)題。

當(dāng)線性規(guī)劃問(wèn)題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化后，原來(lái)已得結(jié)果一般會(huì)發(fā)生變化?？梢杂脝渭冃畏◤念^計(jì)算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也沒(méi)有必要。可以把發(fā)生變化的個(gè)別系數(shù)，經(jīng)過(guò)一定計(jì)算后直接填入最終計(jì)算表中，并進(jìn)行檢查和分析，§2-5靈敏度分析當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問(wèn)題的最優(yōu)44LP的靈敏度分析的步驟：⑴分析問(wèn)題，建立適當(dāng)?shù)腖P模型；⑵求解LP模型；

⑶將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表上；(4)檢查原問(wèn)題是否仍為可行解；(5)檢查對(duì)偶問(wèn)題是否仍為可行解LP的靈敏度分析的步驟：(4)檢查原問(wèn)題是否仍為可行解；45第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件46初始基變量在最終單純形表中對(duì)應(yīng)的系數(shù)矩陣初始基變量在最終單純形表中對(duì)應(yīng)的系數(shù)矩陣471.分析Cj變化方法：

cj

的變化只影響檢驗(yàn)數(shù)的變化，只需要計(jì)算變化后的檢驗(yàn)數(shù)，并反映到最終單純形表中。

1.分析Cj變化方法：48第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件49第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件50為使原線性規(guī)劃問(wèn)題的解仍為最優(yōu)解，應(yīng)有為使原線性規(guī)劃問(wèn)題的解仍為最優(yōu)解，應(yīng)有512.分析bi變化

右端項(xiàng)b的變化在實(shí)際問(wèn)題中反映為可用資源數(shù)量的變化，b的變化反映到最終單純形表中將引起b列數(shù)字的變化，出現(xiàn)兩種情況：(1)變換后所有b的值依然為非負(fù)，問(wèn)題的最優(yōu)基不變，變換后的b列值為最優(yōu)解。(2)變換后b存在負(fù)值，用對(duì)偶單純形法迭代，繼續(xù)尋找最優(yōu)解。2.分析bi變化右端項(xiàng)b的變化在實(shí)際問(wèn)題中反52第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件53第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件54第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件55第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件56第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件573.增加一個(gè)變量xn+1方法：?jiǎn)栴}：所加的變量是否最優(yōu)（新產(chǎn)品是否投產(chǎn)），即增加是否有利？原最優(yōu)解不變，按單純形法繼續(xù)迭代計(jì)算，3.增加一個(gè)變量xn+1方法：?jiǎn)栴}：所加的變量是否最優(yōu)（新58第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件59第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件60第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件614.分析參數(shù)aij的變化aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。若變量xj在最終單純形表中為非基變量，其約束條件中系數(shù)aij的變化分析，相當(dāng)于增加一種新產(chǎn)品。4.分析參數(shù)aij的變化aij的變化使線性規(guī)62若變量xj在最終單純形表中為基變量，則aij的變化將使B和B-1發(fā)生變化，因此有可能出現(xiàn)原問(wèn)題和對(duì)偶問(wèn)題均為非可行解的倩況。出現(xiàn)這種倩況，需引進(jìn)人工變量先將原問(wèn)題的解轉(zhuǎn)化為可行解，再用單純形法求解。4.分析參數(shù)aij的變化若變量xj在最終單純形表中為基變量，則aij的63例8在美佳公司中，若家電Ⅱ每件需設(shè)備A,B和調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品的利潤(rùn)變?yōu)?元/件，重新確定公司最優(yōu)生產(chǎn)計(jì)劃。解先將生產(chǎn)工時(shí)變化后的新家電Ⅱ看作是一種新產(chǎn)品，生產(chǎn)量為x′2，例8在美佳公司中，若家電Ⅱ每件需設(shè)備A,B和調(diào)試工時(shí)變?yōu)?64第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件65原問(wèn)題與對(duì)偶問(wèn)題均為非可行解，故先設(shè)法使原問(wèn)題變?yōu)榭尚薪?。原?wèn)題與對(duì)偶問(wèn)題均為非可行解，故先設(shè)法使原問(wèn)題變?yōu)榭尚薪狻?6第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件67用單純形法計(jì)算得最優(yōu)生產(chǎn)計(jì)劃:每天生產(chǎn)家電11/4件Ι,15/8件新家電Ⅱ用單純形法計(jì)算得最優(yōu)生產(chǎn)計(jì)劃:每天生產(chǎn)家電11/4件Ι,1685.增加一個(gè)約束條件的分析

增加一個(gè)約束條件在實(shí)際問(wèn)題中相當(dāng)于增添一道工序。分析的方法是先將原問(wèn)題最優(yōu)解的變量值代人新增的約束條件，如滿足，說(shuō)明新增的約束末起到限制作用，原最優(yōu)解不變。否則，將新增的約束直接反映到最終單純形表中再進(jìn)一步分析。5.增加一個(gè)約束條件的分析增加一69例9以美佳公司為例，設(shè)家電Ⅰ，Ⅱ經(jīng)調(diào)試后，還需要經(jīng)過(guò)一道環(huán)境試驗(yàn)工序，家電Ⅰ每件須環(huán)境試驗(yàn)3h，家電Ⅱ每件2h，又環(huán)境試驗(yàn)工序每天生產(chǎn)能力為12h.試分析增加該工序后的美佳公司最優(yōu)生產(chǎn)計(jì)劃。3×7/2+2×3/2=27/2>12原問(wèn)題最優(yōu)解不是本例的最優(yōu)解例9以美佳公司為例，設(shè)家電Ⅰ，Ⅱ經(jīng)調(diào)試后，還需要經(jīng)過(guò)一道70x1、x2列不是單位向量，故需進(jìn)行初等變換，x1、x2列不是單位向量，故需進(jìn)行初等變換，71第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件72用對(duì)偶單純形法迭代計(jì)算得用對(duì)偶單純形法迭代計(jì)算得73第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析課件74允許的增量和