1、靈敏度分析與對(duì)偶,王廣民 中國地質(zhì)大學(xué) 經(jīng)濟(jì)管理學(xué)院 ,一、線性規(guī)劃的對(duì)偶問題,1、問題的提出,生產(chǎn)問題,分析： 決策者顯然要考慮兩個(gè)因素： 第一，每種資源所收回的費(fèi)用應(yīng)不底于自己生產(chǎn)時(shí)所獲得的利潤； 第二，定價(jià)又不能太高，要使對(duì)方容易接受。,資源定價(jià)問題,(DP),(LP),2、對(duì)稱形式的原始對(duì)偶問題,對(duì)稱形式 LP與DP之間的關(guān)系：,A,b,c,y,x,3、對(duì)稱形式的對(duì)偶規(guī)則,給每個(gè)原始約束條件定義一個(gè)非負(fù)對(duì)偶變量yi(i=1,2,m)； 使原問題的目標(biāo)函數(shù)系數(shù) cj 變?yōu)槠鋵?duì)偶問題約束條件的右端常數(shù)； 使原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵?duì)偶問題目標(biāo)函數(shù)的系數(shù)； 將原問題約束條件的系

2、數(shù)矩陣轉(zhuǎn)置，得到其對(duì)偶問題約束條件的系數(shù)矩陣； 改變約束問題不等號(hào)的方向，即將“”改為“”； 原問題為“max”型，對(duì)偶問題為“min”型。,4、一般的線性規(guī)劃問題的對(duì)偶問題,混合型問題的對(duì)偶規(guī)則：,原問題為“max”，對(duì)偶問題為“min”； 原問題中目標(biāo)函數(shù)系數(shù) ci 變?yōu)槠鋵?duì)偶問題約束條件的右端常數(shù)； 原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵?duì)偶問題目標(biāo)函數(shù)的系數(shù)； 原問題約束條件的系數(shù)矩陣轉(zhuǎn)置，即為其對(duì)偶問題的系數(shù)矩陣； 原問題的變量個(gè)數(shù)n等于其對(duì)偶問題的約束條件個(gè)數(shù)n，原問題 約束條件的個(gè)數(shù)m等于其對(duì)偶問題變量的個(gè)數(shù)m； 在求極大值的原問題中，“”，“”和“=”的約束條件分別對(duì)應(yīng)其對(duì)偶變

3、量“0”，“0”和“無符號(hào)限制”； 在求極大值的原問題中，變量“0”，“0”和“無符號(hào)限制”分別對(duì)應(yīng)其對(duì)偶約束條件的“”，“”和“=”約束.,對(duì)偶規(guī)則表,二、對(duì)偶原理,對(duì)偶原理給出了原問題和對(duì)偶問題之間的重要關(guān)系.,為了討論問題方便我們以“對(duì)稱形式”來進(jìn)行研究和證明，當(dāng)然所有這些結(jié)論對(duì)于其它形式的對(duì)偶問題也同樣成立。,定理1（對(duì)稱性）對(duì)偶問題的對(duì)偶是原問題.,定理2（弱對(duì)偶定理）,分別是問題(P)和(D)的可行解，,設(shè),和,則必有,注：推論2不存在逆.,推論1：若 X0 和Y0 分別是問題(P)和(D)的可行解，則 （1） CX0是問題(D)的目標(biāo)函數(shù)的一個(gè)下界；（2） Y0 b是問題(P)的

4、目標(biāo)函數(shù)的一個(gè)上界。,推論3：在一對(duì)對(duì)偶問題(P)和(D)中，若其中一個(gè)問題有可行解，而另一個(gè)無可行解，則該問題無界.,推論2：在一對(duì)對(duì)偶問題(P)和(D)中，若其中一個(gè)問題有可行解，但目標(biāo)函數(shù)無界，則另一個(gè)問題無可行解.,定理4（對(duì)偶定理） 若一對(duì)對(duì)偶問題（P）和（D）一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等.,定理5 （互補(bǔ)松弛定理）,設(shè) X* 和Y* 分別是問題（P）和（D）的可行解，則它們分別是最優(yōu)解的充要條件是 同時(shí)成立：,定理3(最優(yōu)性判別定理) 若X*和Y*分別是問題(P)和(D)的可行解，且CX*=Y*b， 則X*，Y*分別是問題(P)和(D)的最優(yōu)解.,緊約

5、束與松約束,一個(gè)約束稱為緊約束，如果該約束在所有最優(yōu)解上的值使左右取等號(hào)。 即我們把嚴(yán)格等式約束稱為緊約束（或起作用約束）.,不是緊約束的約束稱為松約束。 即把某一最優(yōu)解處取嚴(yán)格不等式的約束稱為松約束（或不起作用約束）。,以上關(guān)系稱為對(duì)偶問題的互補(bǔ)松弛關(guān)系或松緊關(guān)系。在計(jì)算上，若已知一個(gè)問題的最優(yōu)解，則可利用互補(bǔ)松弛條件求另一個(gè)問題的最優(yōu)解.,松緊關(guān)系,非常重要,對(duì)于最優(yōu)解X*和Y*而言，松約束的對(duì)偶約束是緊約束.,1、簡介 在線性規(guī)劃中，若某個(gè)約束條件的右端常數(shù)bi增加1個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值Z* 的改變量稱為第i個(gè)約束條件的影子價(jià)格。影子價(jià)格又稱為邊際價(jià)格。 影子價(jià)格的經(jīng)濟(jì)意義是

6、在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化，即對(duì)偶變量yi就是第i個(gè)約束條件的影子價(jià)格。 影子價(jià)格是針對(duì)某一具體的約束條件而言的，而問題所有其他數(shù)據(jù)都保持不變，因此影子價(jià)格也可以理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù).,三、影子價(jià)格,考慮一對(duì)對(duì)稱的對(duì)偶問題,從對(duì)偶問題的基本性質(zhì)可知，當(dāng)(P)問題求得最優(yōu)解 x* 時(shí)，(D)問題也得到最優(yōu)解 y*，,且有,在上式中對(duì) z 求,的偏導(dǎo)數(shù)，得：,的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn),每增加一個(gè)單位時(shí)目標(biāo)函數(shù)z的增量，,這說明,條件下，,所以，影子價(jià)格是一種邊際價(jià)格.,影子價(jià)格說明增加哪一種資源對(duì)增加經(jīng)濟(jì)效益最有利. 三種資源的影子

7、價(jià)格為（0,1,3），說明首先應(yīng)考慮增加資源C，因?yàn)橄啾戎滤芙o收益帶來的增加最大. 影子價(jià)格又是一種機(jī)會(huì)成本. 企業(yè)經(jīng)營決策者可以把本企業(yè)資源的影子價(jià)格與當(dāng)時(shí)的市場(chǎng)價(jià)格進(jìn)行比較，當(dāng)年i種資源的影子價(jià)格高于市場(chǎng)價(jià)格時(shí)，則企業(yè)可以買進(jìn)該種資源；而當(dāng)某種資源的影子價(jià)格低于市場(chǎng)價(jià)格時(shí)（特別是當(dāng)影子價(jià)格為零時(shí)），則企業(yè)可以賣出該種資源，以獲得較大的利潤 企業(yè)在新產(chǎn)品投產(chǎn)之前，可利用影子價(jià)格，通過分析新產(chǎn)品使用資源的經(jīng)濟(jì)效果，以決定新產(chǎn)品是否應(yīng)該投產(chǎn). 利用影子價(jià)格分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)時(shí)資源緊缺情況的影響。 利用影子價(jià)格可以幫助分析工藝改變后對(duì)資源節(jié)約的收益. 根據(jù)互補(bǔ)松弛定理可知，當(dāng)一種資源的影子價(jià)

8、格為0時(shí)表明這種資源尚未用完，而當(dāng)一種資源的影子價(jià)格大于0時(shí)，表明這種資源已經(jīng)用完，屬于緊缺資源，增加這種資源可以增加總的利潤。,2、影子價(jià)格在經(jīng)營管理中的應(yīng)用,影子價(jià)格能批示企業(yè)內(nèi)部挖潛的方向 利用影子價(jià)格進(jìn)行企業(yè)經(jīng)濟(jì)活動(dòng)分析，不僅可以實(shí)現(xiàn)資源的最優(yōu)配置，而且可以指明企業(yè)內(nèi)部挖潛的主攻方向。因?yàn)橛白觾r(jià)格能指出各種資源在實(shí)現(xiàn)企業(yè)最優(yōu)目標(biāo)時(shí)的影響作用，影子價(jià)格愈高的資源，表明它對(duì)目標(biāo)增益的影響愈大，同時(shí)也表明這種資源對(duì)該企業(yè)來說愈稀缺和愈貴重，企業(yè)的管理者就應(yīng)該更加重視對(duì)這種資源的管理，通過挖潛革新、降低消耗或及時(shí)補(bǔ)充該資源，以保證給企業(yè)帶來較大的收益。對(duì)影子價(jià)格大于零的資源都應(yīng)采取措施，增加投

9、入以保證生產(chǎn)正常進(jìn)行，實(shí)現(xiàn)利潤最大化。 緊缺資源 對(duì)影子價(jià)格為零的資源，企業(yè)的管理者也不能忽視，這種資源對(duì)該企業(yè)來說是相對(duì)富裕的。一方面，可以向另的企業(yè)轉(zhuǎn)讓這種資源或者以市場(chǎng)價(jià)出售，以免形成積和浪費(fèi)；另一方面，通過企業(yè)內(nèi)部的改造、挖潛和增加對(duì)影子價(jià)格大于零的資源投入后，使原有的剩余資源又可以得到充分利用，而變?yōu)樾碌木o缺資源（變?yōu)橛白觾r(jià)格大于零）。這樣不斷調(diào)整、補(bǔ)充，真正實(shí)現(xiàn)資源的合理利用 影子價(jià)格在企業(yè)經(jīng)營決策中的作用 因?yàn)橛白觾r(jià)格不是市場(chǎng)價(jià)格，它是根據(jù)企業(yè)本身的資源情況 、消耗系數(shù) 和產(chǎn)品的利潤計(jì)算出來的一種價(jià)格，是新增資源所創(chuàng)造的價(jià)值，是邊際價(jià)格。不同的企業(yè)，即使是相同的資源（例如鋼材），

10、其影子價(jià)格也不一定相同。就是同一個(gè)企業(yè)，在不同的生產(chǎn)周期，資源的影子價(jià)格也不完全一樣。因此，企業(yè)的決策者可以把本企業(yè)資源的影子價(jià)格與當(dāng)時(shí)的市場(chǎng)價(jià)格進(jìn)行比較，當(dāng)?shù)?種資源的影子價(jià)格高于市場(chǎng)價(jià)格時(shí)，則 企業(yè)可以買進(jìn)該種資源，以獲得較大的利潤，隨著資源的買進(jìn)和賣出，它的影子價(jià)格也將發(fā)生變化，直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。所以我們說影子價(jià)格又是一種機(jī)會(huì)成本，它在決定企業(yè)的經(jīng)常策略中起著十分重要的作用。,3、影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用,四、對(duì)偶單純形法,對(duì)偶規(guī)劃可以用線性規(guī)劃的單純形法求解。 由對(duì)偶原理可見，原問題與對(duì)偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對(duì)偶問題

11、的解，反之依然。 互補(bǔ)松弛條件就可以解決由原問題的最優(yōu)解直接求出對(duì)偶問題的最優(yōu)解。 對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法，它是根據(jù)對(duì)偶原理和單純形法的原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。,先回顧一下單純形算法：它是從線性規(guī)劃的一個(gè)基可行解迭代到另一個(gè)基可行解的過程，在迭代過程中，保持基解的可行性，逐步消除基解的檢驗(yàn)數(shù)的非負(fù)性，即,1、對(duì)偶單純形法的基本思想,為了求解線性規(guī)劃，我們也可以從線性規(guī)劃的一個(gè)基解迭代到另一個(gè)基解，在迭代過程中，保持基解的檢驗(yàn)數(shù)的非正性，逐步消除基解的不可行性，即,概念：正則解,如果原問題(P)的一個(gè)基解X 對(duì)應(yīng)的檢驗(yàn)數(shù)向量滿足條件,則稱X為(P)的一個(gè)正則解

12、，同時(shí)稱這一基為正則基.,求解原問題(P)時(shí)，可以從(P)的一個(gè)正則解開始,迭代到另一個(gè)正則解，使目標(biāo)函數(shù)值增加，當(dāng)?shù)秸齽t解滿足原始可行性條件(即xi0)時(shí)，就找到了原問題(P)的最優(yōu)解。這一方法稱為對(duì)偶單純形法.,2、對(duì)偶單純法的迭代步驟：,（1）找一個(gè)正則基B和初始正則解X(0)，將問題（P）化為關(guān)于基B的典式，列初始對(duì)偶單純形表.,設(shè)正則解,的典式為：,將上面的典式轉(zhuǎn)換成前面所學(xué)習(xí)過的單純形表：,為換出變量。若,（3）確定換出變量：若,則取相應(yīng)的變量,則迭代停止，原問題無解；否則轉(zhuǎn)下一步。,找初始正則解X0及可行基B,對(duì)偶單純法計(jì)算框圖,3、初始正則解的確定(略),4、對(duì)偶單純形法的

13、理論解釋,對(duì)偶單純形法所使用的表格與原單純形法一樣，可將典式中的數(shù)據(jù)放在原單純形表上，即得到對(duì)偶單純形表，所不同的是這里保證在整個(gè)過程中,而不保證,這就是為什么我們從本章起,不強(qiáng)調(diào)右端常數(shù)非負(fù)這個(gè)條件的原因。,即右端常數(shù)中可以出現(xiàn)負(fù)數(shù).,設(shè)正則基 的典式為：,對(duì)偶單純形表,對(duì)偶單純形法的迭代方式與原單純形法基本一致.所不同的是：先定換出變量，再定換入變量，決定主元并作基變換得到一個(gè)新的正則解X(1),從而完成一次迭代.算法的后半部分與原單純形法完全一致.,(2)再選進(jìn)基變量:假定xk為進(jìn)基變量, 我們分析一下xk 應(yīng)滿足什么條件,才能使迭代后得到的解仍為問題(P)的正則解.,(1)先選出基變量

14、:若 則取與 相對(duì)應(yīng)的基變量 xr 為出基變量.,因?yàn)?,而換基運(yùn)算的第一步是用主元 去除第r 行中的各元素,為了使變換后 為正數(shù),所以主元 必須從第r 行的負(fù)元素中選取,即 .,設(shè)主元處在第 k 列,于是換基運(yùn)算后,各檢驗(yàn)數(shù)變?yōu)?因?yàn)橐蟮蟮玫降慕馊詾檎齽t解,于是,又因?yàn)?于是當(dāng) 時(shí),不等式(1)自然成立;,由此,則取與之相對(duì)應(yīng)的非基變量 為換入變量。,否則,當(dāng) 時(shí),要使不等式(1)成立,必須,又因?yàn)?于是當(dāng) 時(shí),不等式(1)自然成立;,最后證明對(duì)應(yīng)于新的正則解X(1),對(duì)偶問題(D)的目標(biāo)函數(shù)值將得到改善.,這樣,上述求極大值問題(P)的迭代過程,實(shí)質(zhì)上是在對(duì)對(duì)偶問題(D)求極小值,所

15、以目標(biāo)函數(shù)越小就越接近最優(yōu)解.直到得到對(duì)偶問題(D)的最小值,相應(yīng)地也就求出了原問題(P)的最大值.,出基變量 與進(jìn)基變量 xk 確定以后,以 為主元進(jìn)行換基運(yùn)算(方法與原單純形法相同)即可得新的正則解X(1) .,這是因?yàn)?,故,和原始單純形法一樣,若對(duì)偶問題是非退化的(即對(duì)偶問題的每一個(gè)基可行解都是非退化的,或者說,對(duì)于原問題的每一個(gè)正則解，都有 ,則每迭代一次,目標(biāo)函數(shù)都將嚴(yán)格減小,從而一定能在有限次迭代后得到原問題的最優(yōu)解,或者判定它無解.,容易證明:若 ,且所有的 ,則原問題(P)無解(自己證明).,用對(duì)偶單純形法求解線性規(guī)劃問題時(shí)當(dāng)約束條件為“”時(shí)，不必引進(jìn)人工變量，使計(jì)算簡化。

16、當(dāng)線性規(guī)劃問題中變量多于約束條件時(shí)，用對(duì)偶單純形法計(jì)算可以減少工作量。 對(duì)偶單純形法的局限性主要是：對(duì)大多數(shù)線性規(guī)劃問題，很難找到一個(gè)初始正則解。因此對(duì)偶單純形法一般不單獨(dú)使用，而主要應(yīng)用于靈敏度分析及整數(shù)規(guī)劃等有關(guān)章節(jié)中。,從以上對(duì)對(duì)偶單純形法的討論，可以看到：,因此就會(huì)提出以下問題： （1）當(dāng)參數(shù)中的一個(gè)或者幾個(gè)發(fā)生變化時(shí)，導(dǎo)致決策變量的最優(yōu)解 X 的變化情況； （2）參數(shù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解 X 不會(huì)發(fā)生變化. 這就是線性規(guī)劃的靈敏度分析所要研究解決的問題.,1、問題簡介,以前講的線性規(guī)劃問題中，都假定問題中的A、b、C 是已知常數(shù)。但實(shí)際上這些數(shù)往往是一些估計(jì)和預(yù)測(cè)的數(shù)字，如市場(chǎng)

17、條件一變C 值就會(huì)變化。 A 是隨工藝技術(shù)條件的改變而改變而 b 值則是根據(jù)資源投入后能產(chǎn)生多大經(jīng)濟(jì)效果來決定的一種決策選擇。,五、靈敏度分析,靈敏度分析的含義是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。,靈敏度分析（Sensitivity analysis)又稱為優(yōu)化后分析（Postoptimality analysis)。因?yàn)樗窃谝亚蟮镁€性規(guī)劃最優(yōu)解的基礎(chǔ)上，來討論這些數(shù)據(jù)的變化對(duì)最優(yōu)解的影響。,當(dāng)然當(dāng)線性規(guī)劃問題中的一個(gè)或幾個(gè)參數(shù)變化時(shí)，可以用單純形法從頭計(jì)算，看最優(yōu)解有無變化，但這樣做既麻煩又沒有必要。 因?yàn)榍懊嬉呀?jīng)講到，單純形法的迭代計(jì)算是從一組基變量變換為另一組基變量

18、表中每步迭代得到的數(shù)字只隨基變量的不同選擇而改變，因此有可能把個(gè)別參數(shù)的變化直接在計(jì)算得到最優(yōu)解的最終單純形表上反映出來。 這樣就不需要從頭計(jì)算，而直接對(duì)計(jì)算得到最優(yōu)解的單純形表進(jìn)行審查，看一些數(shù)字變化后，是否仍滿足最優(yōu)解的條件，如果不滿足的話，再從這個(gè)表開始進(jìn)行迭代計(jì)算，求得最優(yōu)解.,1. 將參數(shù)的改變計(jì)算反映到最終單純形表上來； 2. 檢查原問題是否仍為可行解； 3. 檢查對(duì)偶問題是否仍為可行解； 4. 按下表所列情況得出結(jié)論和決定繼續(xù)計(jì)算的步驟,靈敏度分析的步驟可歸納如下：,靈敏度分析,1、價(jià)值系數(shù)cj的靈敏度分析,從上面的典式的推導(dǎo)可以看出，目標(biāo)函數(shù)的價(jià)值系數(shù)cj的改變僅僅影響到檢驗(yàn)數(shù)

19、和最優(yōu)值,非基變量的價(jià)值系數(shù)cj的靈敏度分析,設(shè)cj有變化量 cj，則記,因此求出對(duì)檢驗(yàn)數(shù)的影響,如果要求最優(yōu)解保持不變，即,結(jié) 論,基變量的價(jià)值系數(shù)cj的靈敏度分析,設(shè)xi是基變量，ci是CB的一個(gè)分量，當(dāng)ci發(fā)生變化產(chǎn)生ci時(shí)，則多個(gè)檢驗(yàn)數(shù)都會(huì)受到影響,其中,可以得到,為了不破壞最優(yōu)基的情況，即要求,當(dāng)aij0時(shí) ；,當(dāng)aij0時(shí),令,則當(dāng)Di,1ciDi,2時(shí)，最優(yōu)基不變.,結(jié) 論,2 資源系數(shù)bi的靈敏度分析,當(dāng)資源系數(shù)bi改變時(shí)，僅影響最優(yōu)解和最優(yōu)值.,設(shè)bi改變量為bi,為保證最優(yōu)基不變，應(yīng)滿足,所以若,若,令,則當(dāng)Ti,1biTi,2時(shí)，最優(yōu)基不變.,結(jié) 論,3 技術(shù)系數(shù)（資源消耗系數(shù)）aij的靈敏度分析,非基變量的系數(shù)向量的靈敏度分析,Xj 是非基變量，pj 是其對(duì)應(yīng)的系數(shù)列向量， pj是變化量。由,可見變化僅影響xj的檢驗(yàn)數(shù)，記,為保證最優(yōu)基不變，即,記,有,令,則當(dāng)SijaijSij時(shí)，最優(yōu)基不變.,，則最優(yōu)基地位不變.,若僅限 pj 的一個(gè)分量有變動(dòng)，如aij 變動(dòng) aij ，則,結(jié) 論,結(jié) 論,對(duì)于最優(yōu)基 B 而言，當(dāng)基變量 的系數(shù)列向量 發(fā)生變化時(shí)，對(duì)基 B 及其逆矩陣 都有影響。即不僅影響原先最優(yōu)解的可行性，也影響到它的最優(yōu)性，這里不介紹求變化范圍的一般公式，而建議按具體的最優(yōu)化表格進(jìn)行分析。我們不做討論。,基變量的系數(shù)向量的靈敏度分析,4 增加新