對(duì)偶理論與靈敏度分析

1、§2 對(duì)偶與靈敏度分析一、本章學(xué)時(shí)數(shù)：6學(xué)時(shí)其中講授學(xué)時(shí)：5學(xué)時(shí)，課堂練習(xí)學(xué)時(shí)：1學(xué)時(shí)。二、本章主要內(nèi)容：1.對(duì)偶問題的提出及原問題與對(duì)偶問題轉(zhuǎn)化；2.對(duì)偶問題的基本性質(zhì)；3.影子價(jià)格；4.對(duì)偶單純形法；5.靈敏度分析。三、本章重點(diǎn)、難點(diǎn)：1.對(duì)偶問題的提出及原問題與對(duì)偶問題轉(zhuǎn)化；2.對(duì)偶問題的基本性質(zhì)；3. 靈敏度分析。§2.1LP的對(duì)偶問題無(wú)論從理論和實(shí)踐角度，對(duì)偶理論是LP中的一個(gè)最重要和有趣的概念，支持對(duì)偶理論的基本思想是：每一個(gè)LP問題都存在一個(gè)與其對(duì)偶的問題，在求解一個(gè)問題解的時(shí)候，也同時(shí)給出了另一問題的解。一、問題的提出例2.1：設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲乙，生產(chǎn)

2、過程需要4種設(shè)備ABCD進(jìn)行加工，每件產(chǎn)品加工所需機(jī)時(shí)數(shù)，每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)如下表：設(shè)備產(chǎn)品ABCD利潤(rùn)甲21402乙22043總機(jī)時(shí)12816121.問：充分利用設(shè)備時(shí)，應(yīng)怎樣安排甲乙產(chǎn)品的生產(chǎn)數(shù)量，利潤(rùn)才能最大？2.問：如有另外一家公司想租用該廠設(shè)備加工生產(chǎn)，那么，這家公司應(yīng)至少對(duì)每臺(tái)設(shè)備的機(jī)時(shí)價(jià)格為多少時(shí)，才能使該廠愿意出租設(shè)備？解：1.設(shè)甲乙產(chǎn)品各生產(chǎn)件LP1：2.設(shè)每臺(tái)設(shè)備的機(jī)時(shí)最低價(jià)分別為：，LP2：二、原問題和對(duì)偶問題之間的關(guān)系：1.對(duì)稱形式下的原問題與對(duì)偶問題對(duì)稱形式下原問題的一般式：矩陣形式：若用代表第i種資源的估價(jià)，則其對(duì)偶問題的一般式為：2.非對(duì)稱形式

3、下原問題與對(duì)偶問題：方法一：將非對(duì)稱形式轉(zhuǎn)化為對(duì)稱形式，求出對(duì)偶問題，然后再還原。例2.2寫出下列LP問題的對(duì)偶問題：為寫出基對(duì)偶問題，先將其轉(zhuǎn)化為對(duì)稱形式，再進(jìn)行變化：因目標(biāo)函數(shù)為，故約束條件全部轉(zhuǎn)化為“”，所有變量均應(yīng)為“”。將（1）式變?yōu)椋?。再將將?）式兩端同乘以“-1”，并令：得：所以，例2.2可以變?yōu)椋毫顚?duì)應(yīng)上述四個(gè)約束條件的對(duì)偶變量為，則其對(duì)偶問題為：令，將第4與第5個(gè)不等式合并，將第三個(gè)不等式兩端同乘以“-1”得：由以上的推導(dǎo)可以發(fā)現(xiàn)有以下規(guī)律：方法二：根據(jù)原問題與對(duì)偶問題之間的關(guān)系，可將其歸納如下表：原問題（或?qū)ε紗栴}）對(duì)偶問題（原問題）目標(biāo)函數(shù)目標(biāo)函數(shù)變量 約束條件約束條件

4、變量A約束系數(shù)矩陣b約束條件右端項(xiàng)向量C目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束系數(shù)矩陣的轉(zhuǎn)置C目標(biāo)函數(shù)中的價(jià)格系數(shù)向量b約束條件右端項(xiàng)向量§2.2 對(duì)偶問題的基本性質(zhì)一、單純形法計(jì)算的矩陣描述設(shè)線性規(guī)劃問題的矩陣表達(dá)式為：，加上松弛變量后為：式中：。單純形法計(jì)算時(shí)，總選取為初始基I，對(duì)應(yīng)基變量為。設(shè)迭代若干步后，基變量為，在初始單純形表中的系數(shù)矩陣為B。將B在初始單純形表中單獨(dú)列出，而A中去掉B的若干列后組成矩陣N，同時(shí)將C也分為兩塊，是目標(biāo)函數(shù)中基變量的系數(shù)行向量；是目標(biāo)函數(shù)中非基變量的系數(shù)行向量。這樣LP的初始單純形表可列成如下形式：項(xiàng)目非基變量基變量0bBNI0于是原LP問題可以改寫為：

5、將約束條件移項(xiàng)并左乘后得到的表達(dá)式：代入目標(biāo)函數(shù)得：所以，經(jīng)過迭代之后，得出新的單純形表為：項(xiàng)目基變量非基變量I0當(dāng)為最優(yōu)基時(shí)，在上述單純形表中有：， 而的檢驗(yàn)數(shù)可以寫為：因此有：，稱為單純形乘子，若令則有：可以發(fā)現(xiàn)這時(shí)檢驗(yàn)數(shù)行，若取其相反數(shù)恰好是其對(duì)偶問題的一個(gè)可行解。將這個(gè)解代入對(duì)偶問題的目標(biāo)函數(shù)值，有：即：當(dāng)原問題為最優(yōu)解時(shí)，這時(shí)對(duì)偶問題為可行解，且兩者具有相同的目標(biāo)函數(shù)值。（其實(shí)，這時(shí)對(duì)偶問題的解也為最優(yōu)解。）二、本節(jié)討論先假定原問題和對(duì)偶問題為對(duì)稱形式的LP，即原問題為：其對(duì)偶問題為：然后說明對(duì)偶問題的基本性質(zhì)在非對(duì)稱形式也適用。1.對(duì)稱性：對(duì)偶問題的對(duì)偶是原問題。證明：原問題與其對(duì)

6、偶問題分別為：與2.弱對(duì)偶性：若是原問題可行解，是對(duì)偶問題的可行解，則存在。證明：設(shè)原問題為：原問題的對(duì)偶問題為：3.無(wú)界性：若原問題為無(wú)界解，則其對(duì)偶問題為無(wú)可行解。證明：由弱對(duì)偶性可得，本性質(zhì)成立。4.可行解是最優(yōu)解時(shí)的性質(zhì)：若是原問題可行解，是對(duì)偶問題的可行解，當(dāng)時(shí)，與是原問題與對(duì)偶問題的最優(yōu)解。證明：5.對(duì)偶定理：若原問題有最優(yōu)解，那么其對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。6.互補(bǔ)松弛性：若是原問題可行解，是對(duì)偶問題的可行解，那么，當(dāng)且僅當(dāng)為，最優(yōu)解。（在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)

7、偶變量值一定為零。）；。將互補(bǔ)松弛性質(zhì)應(yīng)用于其對(duì)偶問題時(shí)可以這樣敘述：；。由互補(bǔ)松弛定理可知：若原問題最優(yōu)解中的第j個(gè)變量為正，則其對(duì)偶問題中與之對(duì)應(yīng)的第j個(gè)約束條件在最優(yōu)情況下必呈嚴(yán)格等式（即其松弛變量為0）；而如果對(duì)偶問題中第j個(gè)約束條件在最優(yōu)情況下呈嚴(yán)格不等式，則原問題最優(yōu)解中第j個(gè)變量必為0。類似地，若對(duì)偶問題最優(yōu)解中第i個(gè)對(duì)偶變量為正，則其原問題中與之對(duì)應(yīng)的第i個(gè)約束條件在最優(yōu)情況下必呈嚴(yán)格等式（即其剩余變量為0）；而如果原問題中第i個(gè)約束條件在最優(yōu)情況下呈嚴(yán)格不等式，則對(duì)偶問題最優(yōu)解中第i個(gè)對(duì)偶變量必為0?；パa(bǔ)松弛定量闡明了原問題及其對(duì)偶問題最優(yōu)解各分量之間的關(guān)系，當(dāng)已知一對(duì)對(duì)偶問

8、題之一的最優(yōu)解時(shí)，可利用該定量求出另一個(gè)問題的最優(yōu)解。7.設(shè)原問題是：對(duì)偶問題為：則原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解，其對(duì)應(yīng)關(guān)系如下表所示：0這里是對(duì)應(yīng)原問題中基變量的剩余變量，是對(duì)應(yīng)原問題中非基變量的剩余變量。證明：例2.3已知LP已知其對(duì)偶問題的最優(yōu)解為：試用對(duì)偶理論找出原問題的最優(yōu)解。練習(xí)：1. 已知LP寫出其對(duì)偶問題；已知原問題的最優(yōu)解為試根據(jù)對(duì)偶理論求出對(duì)偶問題最優(yōu)解。2. 已知LP寫出其對(duì)偶問題；已知原問題的最優(yōu)解為試根據(jù)對(duì)偶理論求出對(duì)偶問題最優(yōu)解。§2.3對(duì)偶問題的經(jīng)濟(jì)解釋影子價(jià)格由對(duì)偶問題的性質(zhì)可知，當(dāng)LP原問題求得最優(yōu)解時(shí)，其對(duì)偶問題也得到最優(yōu)解，且

9、代入各自目標(biāo)函數(shù)后有：，在式中是LP原問題約束條件的右端項(xiàng)，它代表第i種資源的擁有量，對(duì)偶變量的意義代表在資源最優(yōu)利用條件下，對(duì)單位第i種資源的估價(jià)。這種估價(jià)還是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，為區(qū)別起見稱為影子價(jià)格。其特點(diǎn)如下：1.資源的市場(chǎng)價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是未知的。由于企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。2.影子價(jià)格是一種邊際價(jià)格，在上式中對(duì)求的偏導(dǎo)數(shù)得：。說明的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，每增加一單位時(shí)目標(biāo)函數(shù)的增量。3.資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。當(dāng)某種資源的

10、市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)可以買進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)賣出已有資源，可見影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。4.由對(duì)偶問題互補(bǔ)的松弛性有：；，這表明生產(chǎn)過程中如果某種資源未得到充分利用時(shí)，該種資源的影子價(jià)格為0，又當(dāng)資源的影子價(jià)格不為0時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。5.從影子價(jià)格的含義上來(lái)考察單純形表的計(jì)算。，式中代表第種產(chǎn)品的產(chǎn)值；是生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該種產(chǎn)品有利，可在計(jì)劃中安排生產(chǎn)；否則用這些資料來(lái)生產(chǎn)別的產(chǎn)品更有利，就不在生產(chǎn)計(jì)劃中安排。這就是單純形表中各個(gè)檢

11、驗(yàn)數(shù)的經(jīng)濟(jì)意義。6.一般來(lái)說，對(duì)LP的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及到資源的最有效的利用，如在一個(gè)大公司內(nèi)部，可借助于資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的好壞。又如在社會(huì)上可借助影子價(jià)格規(guī)定使用這種資源一單位時(shí)必須上繳的利潤(rùn)額，以控制一些經(jīng)濟(jì)效益低的企業(yè)自學(xué)地節(jié)約緊缺資源，使有限資源發(fā)揮最大的經(jīng)濟(jì)效益。§2.4對(duì)偶單純形法一、對(duì)偶單純形法的理論依據(jù)：根據(jù)對(duì)偶問題的基本性質(zhì)7，在單純形表進(jìn)行迭代求解時(shí)，在b列中得到的是原問題的基本可行解，在檢驗(yàn)數(shù)行得到的是對(duì)偶問題的基可行解，根據(jù)最優(yōu)

12、性定理，原問題有最優(yōu)解時(shí)，對(duì)偶問題也達(dá)到最優(yōu)解。根據(jù)其對(duì)稱性，也可以這樣考慮，若保持對(duì)偶問題的解是基可行解，即，而原問題是在非可行解的基礎(chǔ)上，通過逐步迭代的方式達(dá)到基可行解，這樣也可以得到最優(yōu)解。其優(yōu)點(diǎn)是原問題的初始解不一定要是基可行解，可從非基可行解的基礎(chǔ)上開始迭代。二、基本步驟：1.根據(jù)LP問題，列出初始單純形表，檢查b列數(shù)字若都非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解，停止計(jì)算；否則，轉(zhuǎn)入下一步。2.確定換出變量：因?yàn)榭偞嬖?，令，其?duì)應(yīng)變量為換出變量。3. 確定換入變量：在單純形表中檢查所在行的各系數(shù)，若所有，則無(wú)可行解，停止計(jì)算；若存在，計(jì)算：，按規(guī)則所對(duì)應(yīng)的列的非基變量為換入變量。4.

13、以為主元素，進(jìn)行迭代運(yùn)算。5. 得到新單純形表，返回步驟1。例：2.4用對(duì)偶形法求解下列LP解： 從以上表中看出，用對(duì)偶單純形法求解LP時(shí)的優(yōu)點(diǎn)：1.初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，可以簡(jiǎn)化計(jì)算。2.當(dāng)約束條件為“”時(shí)，不必引進(jìn)人工變量，可以使計(jì)算簡(jiǎn)化。3.當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問題，用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成對(duì)偶問題，然后用對(duì)偶單純形法求解。4.但在初始單純形表中其對(duì)偶問題應(yīng)是其可行解這一點(diǎn)很多LP很難實(shí)現(xiàn)，因此，對(duì)偶單純形法一般不單獨(dú)使用，而主要用于靈

14、敏度分析及整數(shù)規(guī)劃等有關(guān)章節(jié)。§2.5靈敏度分析靈敏度分析是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度的分析。在以前講的LP問題中，總是假定問題中的是已知常數(shù)，但實(shí)際上這些參數(shù)往往是一些估計(jì)和預(yù)測(cè)的數(shù)字。如果市場(chǎng)條件變化，的值就會(huì)變化；是隨著工藝技術(shù)條件的改變而改變，而值則是根據(jù)資源投入后能產(chǎn)生多大的經(jīng)濟(jì)效果來(lái)決定的一種決策選擇。因此，靈敏度分析要解決如下問題：l 當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問題最優(yōu)解有什么變化；l 這些在多大范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。靈敏度分析的步驟可歸納如下：1.將參數(shù)的改變計(jì)算反映到最終單純形表上來(lái)：2.檢查原問題是否仍為可行解。3.檢查對(duì)偶

15、問題是否仍為可行解。4.按下表所列情況得出結(jié)論和決定繼續(xù)計(jì)算的步驟。原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算步驟可行解可行解問題最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算一、分析的變化LP目標(biāo)函數(shù)中價(jià)值系數(shù)的變化僅僅影響到檢驗(yàn)數(shù)的變化，所以將的變化直接反映到最終單純形表中，只可能出現(xiàn)上表中前兩種情況。例2.5，在第一章中例1.7中，假設(shè)產(chǎn)品的市場(chǎng)利潤(rùn)變化為，在最優(yōu)解保持不變前提下，確定的變化范圍。解：利用前面計(jì)算出的最終單純形表進(jìn)行計(jì)算：230002410000400-2132010000當(dāng)變?yōu)楹?，上表變?yōu)槿缦聠渭冃伪恚?3+0002410000400-213+2010000為了使原最優(yōu)解保持不變：則，解之得：說明產(chǎn)品的市場(chǎng)利潤(rùn)可以在0,4之間變化，而不影響最優(yōu)解。二、分析的變化資源系數(shù)的變化反映到最終單純形表上將引起b列數(shù)字的變化，在上表中可能出現(xiàn)第一或第三兩種情況。出現(xiàn)第一種情況時(shí)，問題的最優(yōu)基不變，變化后的b列值為最優(yōu)解。出現(xiàn)第三種情況時(shí)，用對(duì)偶單純形法迭代繼續(xù)找出最優(yōu)解。當(dāng)發(fā)生變化時(shí)，即，并假設(shè)規(guī)劃中的其它系數(shù)都不變，這樣使最終