三節(jié)對(duì)偶與靈敏度分析

對(duì)偶問題與靈敏度分析一、對(duì)偶問題及其模型問題的提出這時(shí)有另一家廠商提出要購(gòu)買其煤、電、油全部資源，并希望花費(fèi)盡量少。試建立購(gòu)買者的線性規(guī)劃模型。原問題,記為（P）對(duì)偶問題,記為（D）.對(duì)偶模型的一般式以例1為例，原問題為（P）（D）這是最常見的對(duì)偶模型形式，稱為對(duì)稱式對(duì)偶模型。二者間具有十分對(duì)稱的對(duì)應(yīng)關(guān)系：

原問題（P）對(duì)偶問題（D）

目標(biāo)max型目標(biāo)min型有n個(gè)變量（非負(fù)）有n個(gè)約束（大于等于）有m個(gè)約束（小于等于）有m個(gè)變量（非負(fù)）價(jià)格系數(shù)資源向量資源向量?jī)r(jià)格系數(shù)技術(shù)系數(shù)矩陣技術(shù)系數(shù)矩陣的轉(zhuǎn)置.此外，還有一種情形

原問題（P）對(duì)偶問題（D）第j個(gè)變量為自由變量第j個(gè)約束為等式約束第i個(gè)約束為等式約束第i個(gè)變量為自由變量.例：寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型：.寫出下面線性規(guī)劃的對(duì)偶規(guī)劃模型：.練習(xí)：寫出下面LP的對(duì)偶.其對(duì)偶模型為：.二、對(duì)偶的性質(zhì)（P）（D）考慮1.對(duì)稱性（P）與（D）互為對(duì)偶。.證：X,Y分別為(P)、(D)的可行解，由約束條件可得幾何意義：CXYb2.弱對(duì)偶性由此可以推出：若(P)為無(wú)界解，則(D)無(wú)可行解若(D)為無(wú)界解，則(P)無(wú)可行解.例設(shè)線性規(guī)劃問題1，是其對(duì)偶問題的最優(yōu)解；又設(shè)線性規(guī)劃問題2，其中k是已知的常向量；求證：由(I)和(II)的約束相同，故(I)的最優(yōu)解為(II)的可行解。由弱對(duì)偶性，，由解的最優(yōu)性，得證.3.解的最優(yōu)性4.對(duì)偶定理若(P)有最優(yōu)解，則(D)也有最優(yōu)解，且二者最優(yōu)值相等.證：對(duì)（P）增加松弛變量Xs，化為設(shè)其最優(yōu)基為B，終表為其檢驗(yàn)數(shù)為.問題：(1)由性質(zhì)4可知，對(duì)偶問題最優(yōu)解的表達(dá)式Y(jié)*=？

(2)

求Y*是否有必要重新求解（D）？

——CBB-1——不必。可以從原問題（P）的單純形終表獲得。.例如，在前面的練習(xí)中已知的終表為請(qǐng)指出其對(duì)偶問題的最優(yōu)解和最優(yōu)值。.5.互補(bǔ)松弛定理（自證）。。故只有而即是最優(yōu)解，所以、因?yàn)楱?=3+=-=T

0

,0,),()(

,

XYXYXYXYXIXAYXIYAYbYXCYXssssss的約束化為等式：、證：將=-=+,,)D()P(CIYYAbIXAXss.y1…yi…ymym+1…ym+j…yn+m

x1…xj…xnxn+1…xn+i…xn+m

對(duì)偶問題的變量對(duì)偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0直觀上.在線性規(guī)劃問題的最優(yōu)解中，若對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式，另一方面，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的變量一定為零。.例：已知線性規(guī)劃問題已知其對(duì)偶問題的最優(yōu)解為：試用對(duì)偶理論找出原問題的最優(yōu)解.

對(duì)偶問題的經(jīng)濟(jì)解釋

（1）對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋——資源的影子價(jià)格（ShadowPrice）CBB-1——對(duì)偶問題的最優(yōu)解——買主的最低出價(jià)；——原問題資源的影子價(jià)格——當(dāng)該資源增加1單

位時(shí)引起的總收入的增量——賣主的內(nèi)控價(jià)格。簡(jiǎn)單推導(dǎo)：設(shè)D其最優(yōu)值為(注：與P最優(yōu)值相同），則根據(jù).例：例1（煤電油例）的單純形終表如下：（1）請(qǐng)指出資源煤、電、油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？解：（1）煤、電、油的影子價(jià)格分別是0、1.36、0.52；其經(jīng)濟(jì)意義是當(dāng)煤、電、油分別增加1單位時(shí)可使總收入分別增加0、1.36、0.52。（2）由單純形終表還可得到：原問題的最優(yōu)生產(chǎn)計(jì)劃、最大收入、資源剩余，對(duì)偶問題的最低購(gòu)買價(jià)格、最少的購(gòu)買費(fèi)用等。.影子價(jià)格在管理決策中的作用：（1）影子價(jià)格≠市場(chǎng)價(jià)格若影子價(jià)格＞市場(chǎng)價(jià)格，則應(yīng)買進(jìn)該資源影子價(jià)格＜市場(chǎng)價(jià)格，則應(yīng)賣出該資源（2）影子價(jià)格反映了資源的稀缺性，影子價(jià)格越高，則越稀缺。.y1y2ym（2）對(duì)偶約束的經(jīng)濟(jì)解釋——產(chǎn)品的機(jī)會(huì)成本(OpportunityCost)機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn)增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品可以節(jié)省的資源0xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj22113￡+++￡+++￡++++++=LLLLLLLLLLLLLLLLL.機(jī)會(huì)成本利潤(rùn)差額成本（3）對(duì)偶松弛變量的經(jīng)濟(jì)解釋——產(chǎn)品的差額成本（ReducedCost）差額成本=機(jī)會(huì)成本－利潤(rùn)0..min2121221122222211211122111122113=-++=-++=-++++=++++++nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybwLLLLLLLLLLLL.在利潤(rùn)最大化的生產(chǎn)計(jì)劃中（1）影子價(jià)格大于0的資源沒有剩余；（2）有剩余的資源影子價(jià)格等于0；（3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)；（4）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)。（4）互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋.三、靈敏度分析

討論模型的系數(shù)或變量發(fā)生小的變化時(shí)對(duì)解的影響（如它們?cè)诤畏秶鷥?nèi)變化時(shí)可使原最優(yōu)解或最優(yōu)基不變？）我們主要討論C、b和變量結(jié)構(gòu)變化時(shí)對(duì)解的影響。對(duì)解怎樣影響？-最優(yōu)性-可行性.1.b變化時(shí)的分析（只影響解的可行性）.2.C變化時(shí)的分析即可。故只要，為因只影響自己的檢驗(yàn)數(shù)0,

1￡-D+=-jjBjjjPBCccss的價(jià)格系數(shù)是非基變量(1)jjxc

的價(jià)格系數(shù)是基變量jjxc

(2)。解得公共的應(yīng)由所有的數(shù)這時(shí)要影響所有的檢驗(yàn)jiimiiiicPBcccccD￡D+-=-0,)(

11ssLL.3.增加新變量時(shí)的分析

主要討論增加新變量xn+1是否有利。經(jīng)濟(jì)意義是第n+1種新產(chǎn)品是否應(yīng)當(dāng)投產(chǎn)，數(shù)學(xué)意義是xn+1是否應(yīng)進(jìn)基。經(jīng)濟(jì)意義：市場(chǎng)價(jià)影子價(jià).例：在例1（煤電油例）中，其單純形終表如下：（1）電的影子價(jià)格是多少？使最優(yōu)基仍適用的電的變化范圍為何？（2）若有人愿以每度1元的價(jià)格向該廠供應(yīng)25度電，是否值得接受？（3）甲產(chǎn)品的價(jià)格在何范圍內(nèi)變化時(shí)，現(xiàn)最優(yōu)解不變？（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，售價(jià)為6.5，問該產(chǎn)品是否可投產(chǎn)？.例：在例1（煤電油例）中，其單純形終表如下：（1）電的影子價(jià)格是多少？使最優(yōu)基仍適用的電的變化范圍為何？解：（1）電的影子價(jià)格是1.36。.例：在例1（煤電油例）中，其單純形終表如下：（2）若有人愿以每度1元的