線性規(guī)劃的對偶理論優(yōu)秀文檔

第二章線性規(guī)劃的對偶理論(DualityTheory)線性規(guī)劃的對偶問題對偶問題的基本性質(zhì)對偶問題的經(jīng)濟(jì)解釋----影子價(jià)格對偶單純形法靈敏度分析WinQSB軟件應(yīng)用第一節(jié)線性規(guī)劃的對偶問題一、問題的提出【例2-1】第一章例1-1中討論了某企業(yè)利用三種資源生產(chǎn)甲乙兩種產(chǎn)品的生產(chǎn)計(jì)劃問題，得到其線性規(guī)劃問題為：

下面從另一個(gè)角度來討論這個(gè)問題：假定該企業(yè)決定自己不生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源轉(zhuǎn)讓或出租給其他企業(yè)，那么該如何確定資源的轉(zhuǎn)讓價(jià)格？分析問題：1、定價(jià)不能太高，否則買方無法接受，并且對買方來說，其目的是越低越好

；2、定價(jià)不能太低，否則企業(yè)不愿意放棄生產(chǎn)、出讓資源

合理的價(jià)格應(yīng)是對方用最少的資金購買該企業(yè)的全部資源，而該企業(yè)所獲得的利潤又不低于自己組織生產(chǎn)時(shí)所獲得的利潤。

設(shè)分別用y1、y2和y3代表單位時(shí)間(h)設(shè)備、每公斤材料A、材料B的出讓代價(jià)，則有：

（LP2）

對偶問題二、對稱形式下對偶問題的一般形式滿足下列條件的線性規(guī)劃問題稱為具有對稱形式:(1)變量均滿足非負(fù)約束；(2)約束條件當(dāng)目標(biāo)函數(shù)求極大時(shí)取“≤”號(hào)，目

標(biāo)函數(shù)求極小時(shí)取“≥”號(hào)注：對稱形式與線性規(guī)劃標(biāo)準(zhǔn)型是兩種不同的形式，對稱形式中約束條件的符號(hào)由目標(biāo)函數(shù)決定從以下方面比較(LP1)與(LP2)：原問題對偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件的右端項(xiàng)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量C目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束條件的右端項(xiàng)向量目標(biāo)函數(shù)Maxz=CXMinw=Y’b約束條件AX≤bA’Y≥C’決策變量X≥0Y≥0將其反映到最終單純形表中：第六節(jié)WinQSB軟件應(yīng)用滿足下列條件的線性規(guī)劃問題稱為具有對稱形式:aij隨工藝技術(shù)條件的改變而改變；只要即可，故而單純形法適用于所有線性規(guī)劃問題，是線性規(guī)劃問題的一般解法市場價(jià)格低于影子價(jià)格，企業(yè)愿意購進(jìn)這種資源，若所有的(B-1b)i非負(fù)，則X為(P)的基可行解，此時(shí)X為(P)的最優(yōu)解，Y為(D)的最優(yōu)解；又由于y*1＞0，y*2＞0，原問題的約束必為等式，即由對偶問題的基本性質(zhì)，Y也為(D)的最優(yōu)解?！`敏度分析線性規(guī)劃問題中的參數(shù)往往是一些估計(jì)和預(yù)測的數(shù)字原問題對偶問題

若原問題為求極小形式的對稱形式線性規(guī)劃問題，對偶問題應(yīng)該具有什么形式？

若一個(gè)線性規(guī)劃問題是另一個(gè)線性規(guī)劃問題的對偶問題，則它們互為對偶問題

對偶問題的對偶問題是原問題【例2-2】寫出下述線性規(guī)劃問題的對偶問題

例中目標(biāo)函數(shù)為max，若為對稱形式，則約束條件應(yīng)為“≤”號(hào)，所有變量均應(yīng)≥0。——非對稱形式三、非對稱形式的原——對偶問題關(guān)系2．變量均有非負(fù)約束

令則1．目標(biāo)函數(shù)為求極大，故約束條件應(yīng)均為“≤”號(hào)

約束b兩邊乘-1：約束c寫成兩個(gè)不等式約束：令，則原問題對偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件的右端項(xiàng)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量C目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束條件的右端項(xiàng)向量目標(biāo)函數(shù)Maxz=CX目標(biāo)函數(shù)Minw=Y’b約束條件m個(gè)≤≥=m個(gè)≥0≤0無約束變量變量n個(gè)≥0≤0無約束n個(gè)≥≤=約束條件【例2-3】寫出下列線性規(guī)劃問題的對偶問題【練習(xí)】寫出下列線性規(guī)劃問題的對偶問題第二節(jié)對偶問題的基本性質(zhì)一、單純形法計(jì)算的矩陣描述(P)(D)對稱形式線性規(guī)劃問題的矩陣表達(dá)式加上松弛變量后為：其中，Xs=(xn+1,xn+2,…，xn+m)為松弛變量，I為m×m單位矩陣。

設(shè)B是一個(gè)可行基，也稱基矩陣。若將系數(shù)矩陣A分為(B,N)兩塊(這里N是非基變量的系數(shù)矩陣),對應(yīng)于基B的變量為XB，其它非基變量用XN表示。則:同時(shí)也將C分為兩塊(CB,CN)，CB是目標(biāo)函數(shù)中基變量XB的系數(shù)行向量，CN是目標(biāo)函數(shù)中非基變量XN的系數(shù)行向量。于是0CNCBCj-zjINBbXs0XsXNXB基變量非基變量初始單純形表-CBB-1CN-CBB-1N0Cj-zjB-1B-1NIB-1bXBCBXsXNXB非基變量基變量最終單純形表此時(shí)，若B-1b為最優(yōu)解，則B-12.對于原問題的任意可行解，各松弛變量檢驗(yàn)數(shù)的相反數(shù)恰好是其對偶問題的一個(gè)可行解，且兩者具有相同的目標(biāo)函數(shù)值。根據(jù)下面介紹的對偶問題的基本性質(zhì)還將看到，若原問題取得最優(yōu)解，則對偶問題的解也為最優(yōu)解。二、對偶問題的基本性質(zhì)1、弱對偶性：設(shè)和分別是問題（P）和（D）的可行解，則恒有:證明：推論1：原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。

試估計(jì)它們目標(biāo)函數(shù)的界，并驗(yàn)證弱對偶性原理。例1（P）（D）解：由觀察可知：=（1,1,1,1），=（1,1），分別是（P）和（D）的可行解。Z=10，W=40，故有弱對偶定理成立。由推論⑴可知，W的最小值不能小于10，Z的最大值不能超過40。由推論⑴可知，W的最小值不能小于10，Z的最大值不能超過40。由單純形法原理，當(dāng)所有檢驗(yàn)數(shù)均不大于零時(shí)，(P)取得最優(yōu)解?！纠?-3】寫出下列線性規(guī)劃問題的對偶問題第一節(jié)線性規(guī)劃的對偶問題由對偶問題的基本性質(zhì)，Y也為(D)的最優(yōu)解。注：對稱形式與線性規(guī)劃標(biāo)準(zhǔn)型是兩種不同的形三、非對稱形式的原——對偶問題關(guān)系影子價(jià)格是企業(yè)生產(chǎn)過程中資源的一種隱含的它之所以被稱為“對偶單純形法”，是因?yàn)樵摲椒ㄔ谇蠼膺^程中是以對偶原理和單純形法原理為理論依據(jù)的。市場價(jià)格低于影子價(jià)格，企業(yè)愿意購進(jìn)這種資源，【例2-10】仍以某企業(yè)為例，設(shè)甲乙產(chǎn)品生產(chǎn)完后，還需經(jīng)過一道環(huán)境試驗(yàn)工序。這些參數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變？(2)約束條件當(dāng)目標(biāo)函數(shù)求極大時(shí)取“≤”號(hào)，目目標(biāo)函數(shù)中的價(jià)格系數(shù)向量增加一個(gè)變量在實(shí)際問題中反映為增加一種新的表明生產(chǎn)過程中如果某種資源未得到充分利用時(shí)，線性規(guī)劃問題中的參數(shù)往往是一些估計(jì)和預(yù)測的數(shù)字推論2：如原問題有可行解且目標(biāo)函數(shù)值無界(具有無界解)，則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解注：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對偶問題無可行解時(shí)，其原問題或具有無界解或無可行解，反之亦然推論3：若原問題有可行解而其對偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之，對偶問題有可行解而其原問題無可行解，則對偶問題的目標(biāo)函數(shù)值無界

例3已知試用對偶理論證明原問題無界。無界解如：（P）無可行解（D）又如兩個(gè)問題都無可行解2、最優(yōu)性

若

和分別是P和D的可行解且，則和分別是問題P和D的最優(yōu)解。證：設(shè)和分別是原問題和對偶問題的最優(yōu)解證：由于兩者均有可行解，根據(jù)弱對偶性的推論(1)，原問題的目標(biāo)函數(shù)值具有上界，對偶問題的目標(biāo)函數(shù)值具有下界，因此兩者均具有最優(yōu)解。又因?yàn)楫?dāng)原問題有最優(yōu)解時(shí),其對偶問題的解為可行解，且有z=w，由最優(yōu)性知，這時(shí)兩者的解均為最優(yōu)解。3、強(qiáng)對偶性

若一對對偶問題P和D都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。推論4：若P和D的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等4、互補(bǔ)松弛性在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。也即

若，則有，即若，即，則有若，則有若，則根據(jù)最優(yōu)性證：由弱對偶性知故因，,故有所以，當(dāng)時(shí)，必有當(dāng)時(shí)，必有續(xù)迭代計(jì)算找出最優(yōu)解。正確理解影子價(jià)格將有利于更好地調(diào)節(jié)生產(chǎn)規(guī)模。資源分別產(chǎn)生了多少利潤。Z=10，W=40，故有解，則Y為(D)的最優(yōu)解。將其反映到最終單純形表中得：【例2-7】在某企業(yè)的例子中：(1)若設(shè)備和材料B的現(xiàn)有資源不變，而材料A的現(xiàn)有資源增加到51公斤時(shí)，分析企業(yè)最優(yōu)計(jì)劃的變化；將y*1=1，y*2=3代入對偶約束條件，(1)(2)(5)式為緊約束，(3)(4)為松約束(約束條件為嚴(yán)格不等式)。目標(biāo)函數(shù)中的價(jià)格系數(shù)向量【練習(xí)】寫出下列線性規(guī)劃問題的對偶問題若，即，則有目標(biāo)函數(shù)中的價(jià)格系數(shù)向量消耗各項(xiàng)資源的影子價(jià)格的總和，即隱含成本。由對偶問題的基本性質(zhì)，Y也為(D)的最優(yōu)解。要使迭代后的ars=1，首先應(yīng)將第r行均除以ars題求得最優(yōu)解時(shí)，其對偶問題也得到最優(yōu)【例2-4】已知原問題的最優(yōu)解為X*=（0,0,4），Z=12試求對偶問題的最優(yōu)解。解：（1）（2）（3）將X*=（0,0,4）代入原問題中，有下式：所以，根據(jù)互補(bǔ)松弛條件，必有y*1=y*2=0，代入對偶問題(3)式，y3=3。因此，對偶問題的最優(yōu)解為Y*=(0,0,3)，W=12【練習(xí)】已知試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對偶問題為用圖解法求出：Y*=（1,3），W=11將y*1=1，y*2=3代入對偶約束條件，(1)(2)(5)式為緊約束，(3)(4)為松約束(約束條件為嚴(yán)格不等式)。令原問題的最優(yōu)解為X*=（x1,x2,x3,x4,x5），則根據(jù)互補(bǔ)松弛條件，必有x3=x4=0(1,3)（1）（2）（3）（4）（5）該方程組與構(gòu)成的方程組有無窮多組解故原問題有無窮多組最優(yōu)解，且取得最優(yōu)解時(shí)目標(biāo)函數(shù)值又由于y*1＞0，y*2＞0，原問題的約束必為等式，即

綜上所述，一對對偶的線性規(guī)劃問題的解只能有下面三種情況之一出現(xiàn)：①都有最優(yōu)解，分別設(shè)為X*

和Y*，則必有CX*=Y*b；②一個(gè)問題無界，則另一個(gè)問題無可行解；③兩個(gè)都無可行解第三節(jié)對偶問題的經(jīng)濟(jì)解釋——影子價(jià)格在單純形法的迭代過程中，目標(biāo)函數(shù)z=CBB-1b和檢驗(yàn)數(shù)CN-CBB-1N中都有單純乘子Y’=CBB-1，那么Y的經(jīng)濟(jì)意義是什么？

從上節(jié)對偶問題的基本性質(zhì)看出，當(dāng)線性規(guī)劃原問題求得最優(yōu)解時(shí)，其對偶問題也得到最優(yōu)解，且代入各自的目標(biāo)函數(shù)后有

式中，bi是線性規(guī)劃原問題約束條件的右端項(xiàng)，它代表第i種資源的擁有量。

目標(biāo)函數(shù)最優(yōu)值變?yōu)椋?/p>

Z′*=y*1b1+y*2b2+…+y*i(bi+1)+…+y*mbm

∴△Z*=Z′*－Z*=y*i

也可以寫成：即y*i

表示Z*對bi的變化率。其經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。

設(shè)B是問題P的最優(yōu)基，

Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*ibi+…+y*mbm

當(dāng)bi

變?yōu)閎i+1時(shí)（其余右端項(xiàng)不變，也不影響B(tài)）左圖為第一章例1-1用圖解法求解時(shí)的情形，圖中陰影部分標(biāo)出了問題的可行域，點(diǎn)Q3（4,12）是最優(yōu)解，代入目標(biāo)函數(shù)得Z*=1200；如果將例1-1中的第2個(gè)約束條件右端項(xiàng)增加l，變?yōu)?x1+2x2≤37，可行域邊界線由(b)移至(b’)，見右圖，最優(yōu)解變?yōu)镼3（5,11），代入目標(biāo)函數(shù)得Z*=1220，說明第2種資源每增加1個(gè)單位即可多獲利20例如

由此可以看出，yi表示對第i種資源的估價(jià)，這種估價(jià)不同于資源的市場價(jià)格，是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價(jià)，它是針對具體企業(yè)的具體產(chǎn)品而存在的一種特殊價(jià)格，為區(qū)別起見，稱它為“影子價(jià)格”一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及到資源的最有效利用。正確理解影子價(jià)格，可幫助決策者分析經(jīng)濟(jì)活動(dòng)，作出有利決策。

資源的影子價(jià)格實(shí)際上是一種機(jī)會(huì)成本在完全市場經(jīng)濟(jì)條件下，若第i種資源的單位市場價(jià)格低于影子價(jià)格，企業(yè)愿意購進(jìn)這種資源，用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場價(jià)格高于影子價(jià)格時(shí)，則企業(yè)應(yīng)有償轉(zhuǎn)讓這種資源，否則，企業(yè)無利可圖，甚至虧損?？梢?，影子價(jià)格對市場價(jià)格有調(diào)節(jié)作用，直到影子價(jià)格與市場價(jià)格保持同等水平才處于平衡狀態(tài)。正確理解影子價(jià)格將有利于更好地調(diào)節(jié)生產(chǎn)規(guī)模。資源的影子價(jià)格是一種邊際產(chǎn)出影子價(jià)格反映了在其他條件不變的情況下，第i種資源增加1個(gè)單位所帶來的收益，因此可用于評估生產(chǎn)要素對產(chǎn)出貢獻(xiàn)的分解,大致估計(jì)各種資源分別產(chǎn)生了多少利潤。從影子價(jià)格的含義考察互補(bǔ)松弛性的意義若，則有，即

若，即，則有表明生產(chǎn)過程中如果某種資源未得到充分利用時(shí)，該種資源的影子價(jià)格為零；資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。影子價(jià)格是企業(yè)生產(chǎn)過程中資源的一種隱含的潛在價(jià)值，表明單位資源的貢獻(xiàn)，與市場價(jià)格是不同的兩個(gè)概念資源的市場價(jià)格是已知數(shù)，相對比較穩(wěn)定；而它的影子價(jià)格則有賴于資源的利用情況，是未知數(shù)，隨著企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況的變化而改變。例如，某種鋼板市場價(jià)格是每噸8000元，一個(gè)企業(yè)用來生產(chǎn)汽車，另一個(gè)企業(yè)用來生產(chǎn)空調(diào)外殼，每噸鋼板的產(chǎn)值不同，它們的影子價(jià)格也就不同。

從影子價(jià)格的含義考察單純形法檢驗(yàn)數(shù)的意義Cj代表第j種產(chǎn)品的產(chǎn)值，是生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和，即隱含成本。當(dāng)產(chǎn)品的產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則，轉(zhuǎn)而安排生產(chǎn)其他產(chǎn)品。第四節(jié)對偶單純形法設(shè)（P）則（D）一、對偶單純形法的基本思路化為標(biāo)準(zhǔn)型（P）（D）設(shè)B為(P)的一個(gè)基，可記A=(B,N)，C=(CB,CN)，X=(XB,XN)T此時(shí)，（P）的標(biāo)準(zhǔn)型可寫為（P）（D）若B為(P)的可行基，則XB=B-1b為(P)的一個(gè)基可行解，相應(yīng)的檢驗(yàn)數(shù)為0，CN-CBB-1N，-CBB-1令Y’=CBB-1，代入(D)的約束條件中，可發(fā)現(xiàn)檢驗(yàn)數(shù)行恰為對偶問題的一組基解的相反數(shù)cj→CBCN0CBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1-Y’s1-Y’s2-Y’對偶單純形法的基本思路：若(D)取得一組基可行解Y，且對應(yīng)的X為(P)的基可行解，則Y為(D)的最優(yōu)解。此時(shí)，X也為(P)的最優(yōu)解。由單純形法原理，當(dāng)所有檢驗(yàn)數(shù)均不大于零時(shí)，(P)取得最優(yōu)解。此時(shí)，Y為(D)的可行解。結(jié)論：若(P)取得一組基可行解X，且對應(yīng)的Y為(D)的基可行解，則X為(P)的最優(yōu)解。由對偶問題的基本性質(zhì)，Y也為(D)的最優(yōu)解。注：不要簡單地把對偶單純形法理解為是求解對偶問題的單純形法。對偶單純形法不是對對偶問題使用單純形法，而是求解線性規(guī)劃的另一有效方法。它之所以被稱為“對偶單純形法”，是因?yàn)樵摲椒ㄔ谇蠼膺^程中是以對偶原理和單純形法原理為理論依據(jù)的。對偶單純形法對偶單純形法的一般形式若此時(shí)滿足所有檢驗(yàn)數(shù)不大于零，則Y為(D)的基可行解。

與單純形法的標(biāo)準(zhǔn)型相比，這里沒有對右端項(xiàng)不大于零的要求，因此，在得到的單純型表中b列的值(B-1b)i不一定非負(fù)。

若所有的(B-1b)i非負(fù)，則X為(P)的基可行解，此時(shí)X為(P)的最優(yōu)解，Y為(D)的最優(yōu)解；若存在某一個(gè)或幾個(gè)的(B-1b)i<0，則X不是(P)的可行解，需在保證Y為(D)的基可行解的前提下進(jìn)行迭代，直至找到(P)的一個(gè)可行解。1、建立初始單純形表

二、對偶單純形法的計(jì)算步驟2、最優(yōu)性判斷檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解，停止計(jì)算；若b列有負(fù)數(shù)，其中某負(fù)數(shù)對應(yīng)的行沒有負(fù)數(shù),

則問題無可行解；

若b列有負(fù)數(shù)，而且所有負(fù)數(shù)對應(yīng)的行都有負(fù)數(shù)，則轉(zhuǎn)入下一步。3、得出新的單純形表確定出基變量，對應(yīng)變量xr

為出基變量

確定入基變量

對應(yīng)變量xs

為入基變量

以ars為主元素進(jìn)行迭代4、重復(fù)2、3步若要令迭代后的為可行解，必有，即b列的數(shù)應(yīng)不小于0，故需將小于0的xi從基中換出；若X存在一個(gè)以上分量小于0，則首先將其中最小的xr換出出基變量xs應(yīng)滿足：（1）使迭代后的解為可行解，即要使迭代后的ars=1，首先應(yīng)將第r行均除以ars

因?yàn)?，若要，只能?）保持Y為對偶問題的基可行解，即當(dāng)時(shí)，要故當(dāng)時(shí)，必有成立而，,即，,即當(dāng)時(shí)，要只要即可，故【例2-5】用對偶單純形法求解下述線性規(guī)劃問題：

解：先將問題改寫為約束條件（a），(b)兩端乘以“-1”得→-16-36-6500CB基by1y2y3y4Y50y4-90-1-30100y5-70-1-2-501-16-36-6500-36y2301/310-1/300y5-10-1/30-5-2/31-40-65-120

初始解可以是非可行解，當(dāng)約束條件右端項(xiàng)≤0時(shí)，不必劃為標(biāo)準(zhǔn)型；當(dāng)約束條件為≥時(shí)，不必引入人工變量，從而簡化了計(jì)算

對許多線性規(guī)劃問題，因?yàn)楹茈y找到一個(gè)初始可行基，因而有局限性

對偶單純形法是對特殊問題的特殊解法，它與單純形法不是完全平行的，不能解決所有線性規(guī)劃問題；而單純形法適用于所有線性規(guī)劃問題，是線性規(guī)劃問題的一般解法

對偶單純形法的重要應(yīng)用——靈敏度分析-36y22001-5-11-16y13010152-300-5-4-12所以，原問題最優(yōu)解為：Y*=（20,30,0,0,0）其對偶問題的最優(yōu)解為：X*=(4,12)【練習(xí)】用對偶單純形法求解下述線性規(guī)劃問題：

解：將模型轉(zhuǎn)化為→-2-3-400CB基bx1x2x3x4x50x4-3-1-2-1100x5-4-21-301-2-3-4000x4-10-5/21/21-1/2-2x121-1/23/20-1/20-4-10-1-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/500-9/5-8/5-1/5所以，原問題最優(yōu)解為：X*=（11/5,2/5,0,0,0）其對偶問題的最優(yōu)解為：Y*=(8/5,1/5)第五節(jié)靈敏度分析第一章例題中某企業(yè)利用其資源生產(chǎn)兩種產(chǎn)品時(shí)，其線性規(guī)劃模型為：

甲乙每天可用能力設(shè)備（h）1116材料A（公斤）3236材料B（公斤）0565利潤（元）9070

線性規(guī)劃問題中的參數(shù)往往是一些估計(jì)和預(yù)測的數(shù)字市場條件一變，cj的值就會(huì)變化；

aij隨工藝技術(shù)條件的改變而改變；

bi值是根據(jù)資源投入后能產(chǎn)生多大經(jīng)濟(jì)效果來決定的一種決策選擇；……問題：1.當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解有什么變化？2.這些參數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變？——靈敏度分析方法：將個(gè)別參數(shù)的變化直接在計(jì)算得到最優(yōu)解的最終單純形表上反映出來，并進(jìn)行檢查和分析原問題對偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新單純形表，重新計(jì)算→9070000CB基bx1x2x3x4x570x212013-1090x1410-2100x5500-155100-30-200表1某企業(yè)生產(chǎn)計(jì)劃安排最終單純形表cj→CBCN0CBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1-Y’s1-Y’s2-Y’表2單純形法計(jì)算表41325一、價(jià)值系數(shù)cj的變化分析線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù)cj的變化僅僅影響到檢驗(yàn)數(shù)的變化，此時(shí)只可能出現(xiàn)表中前兩種情況：若原問題和對偶問題均為可行解，則最優(yōu)解不變；若原問題為可行解，對偶問題為非可行解，則用單純形法繼續(xù)迭代求最優(yōu)解。

【例2-6】在第一章某企業(yè)的例子中，(1)若甲產(chǎn)品的利潤降至85元/件，而乙產(chǎn)品的利潤增至95元/件時(shí)，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃有何變化;(2)若甲產(chǎn)品的利潤不變，則乙產(chǎn)品的利潤在什么范圍內(nèi)變化時(shí)，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？解：(1)將甲、乙產(chǎn)品的利潤變化直接反映到最終單純形表中，得下表：因變量x4的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代計(jì)算得：即該企業(yè)隨產(chǎn)品甲、乙的利潤變化應(yīng)調(diào)整為生產(chǎn)甲3件，乙13件?！?595000CB基bx1x2x3x4x595x212013-1085x1410-2100x5500-155100-115100→8595000CB基bx1x2x3x4x595x21301001/585x131010-1/50x4100-311/500-850-2（2）設(shè)產(chǎn)品乙的利潤為（70+λ）元，反映到最終單純形表中，得表:

為使上表中的解仍為最優(yōu)解，應(yīng)有：解得:

即家電Ⅱ的利潤c2的變化范圍應(yīng)滿足：→9070+λ000CB基bx1x2x3x4x570+λx212013-1090x1410-2100x5500-155100-30-3λ-20-λ0二、資源限量bi的變化分析當(dāng)右端項(xiàng)發(fā)生變化后，會(huì)引起單純型表中b列數(shù)字的變化，此時(shí)可能出現(xiàn)表中第一或第三種情況：當(dāng)出現(xiàn)第一種情況時(shí)，問題最優(yōu)解不變；當(dāng)出現(xiàn)第三種情況時(shí)，用對偶單純形法繼續(xù)迭代找到最優(yōu)解【例2-7】在某企業(yè)的例子中：(1)若設(shè)備和材料B的現(xiàn)有資源不變，而材料A的現(xiàn)有資源增加到51公斤時(shí)，分析企業(yè)最優(yōu)計(jì)劃的變化；(2)材料A和B的現(xiàn)有資源不變，則設(shè)備的現(xiàn)有資源在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變？解：（1）將其反映到最終單純形表中得：因上表中原問題為非可行解，故用對偶單純形法繼續(xù)計(jì)算得表：→9070000CB基bx1x2x3x4x570x2-3013-1090x11910-2100x58000-155100-30-200→9070000CB基bx1x2x3x4x50x430-1-31090x116111000x565050010-20-9000由此美佳公司的最優(yōu)計(jì)劃改為只生產(chǎn)甲產(chǎn)品16件。（2）設(shè)調(diào)試工序每天可用能力為(16+λ)小時(shí)，因有：

將其反映到最終單純形表中，其b列數(shù)字為：當(dāng)b≥0時(shí)問題的最優(yōu)基不變，解得-4≤λ≤1/3。由此調(diào)試工序的能力應(yīng)在12小時(shí)～49/3小時(shí)之間。三、增加一個(gè)新變量的分析【例2-8】在某企業(yè)的例子中，設(shè)企業(yè)又計(jì)劃推出新型號(hào)的產(chǎn)品丙，生產(chǎn)一件所需設(shè)備臺(tái)時(shí)及材料A、B分別為1小時(shí)、4公斤、3公斤，該產(chǎn)品的預(yù)期利潤為115元／件，試分析該種產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃有何變化？

增加一個(gè)變量在實(shí)際問題中反映為增加一種新的產(chǎn)品。其分析步驟為：1.計(jì)算：

2.計(jì)算新的

3.若，原最優(yōu)解不變，只需將計(jì)算得到的和直接寫入最終單純形表中；若，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)解。解

設(shè)該企業(yè)生產(chǎn)丙產(chǎn)品x6件，有c6＝115，P6＝(1，4，3)T。將其反映到最終單純形表中得表：→9070000115CB基bx1x2x3x4x5x670x212013-10-190x1410-21020x5500-1551800-30-2005，故用單純形表繼續(xù)迭代計(jì)算得表：故美佳公司新的最優(yōu)生產(chǎn)計(jì)劃應(yīng)為生產(chǎn)甲產(chǎn)品

11/4件，乙產(chǎn)品101/8件，丙產(chǎn)品5/8件→9070000115CB基bx1x2x3x4x5x670x2101/8019/8-3/81/8090x111/410-7/4-1/4-1/40115x65/800-15/85/81/8100-165/8-185/8-5/80四、技術(shù)系數(shù)aij的變化分析【例2-9】在某企業(yè)的例子中，進(jìn)行工藝改進(jìn)后若甲產(chǎn)品每件需設(shè)備、材料A和材料B變?yōu)?臺(tái)時(shí)、2公斤和0公斤，該產(chǎn)品的利潤變?yōu)?00元／件，試重新確定企業(yè)的最優(yōu)生產(chǎn)計(jì)劃。1.計(jì)算：

2.計(jì)算新的

從而判斷是否需要迭代尋找最優(yōu)解。引起矩陣A的變化若xj在最終單純形表中為非基變量，則若xj在最終單純形表中為基變量，則可能出現(xiàn)第四種情況。此時(shí)，需要引進(jìn)人工變量，編制新的單純形表，重新計(jì)算。解先將生產(chǎn)消耗變化后的新產(chǎn)品甲看作是一種新產(chǎn)品，生產(chǎn)量為，仿本節(jié)三的步驟直接計(jì)算和并反映到最終單純形表中。其中：將其反映到最終單純形表中：→9010070000CB基bx1x’1x2x3x4x570x2120113-1090x14100-2100x550-50-15510300-30-200因已變換為，故用單純形法將替換出基變量中的，得:變量x4對應(yīng)檢驗(yàn)數(shù)大于零，問題沒得到最優(yōu)解，用單純形法迭代→9010070000CB基bx1x’1x2x3x4x5100x’1120113-1090x14100-2100x56500500100-30-120100→9010070000CB基bx1x’1x2x3x4x5100x’1160111000x44100-2100x565005001-100-30-10000該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃為只生產(chǎn)工藝改進(jìn)后的甲產(chǎn)品16件。五、增加一個(gè)約束條件的分析

增加一個(gè)約束條件在實(shí)際問題中相當(dāng)增添一道工序。分析的方法是先將原問題最優(yōu)解的變量值代入新增的約束條件，如滿足，說明新增的約束未起到限制作用，原最優(yōu)解不變。否則，將新增的約束直接反映到最終單純形表中再進(jìn)一步分析?！纠?-10】仍以某企業(yè)為例，設(shè)甲乙產(chǎn)品生產(chǎn)完后，還需經(jīng)過一道環(huán)境試驗(yàn)工序。甲產(chǎn)品每件須環(huán)境試驗(yàn)2小時(shí)，乙產(chǎn)品每件1.5小時(shí)，又環(huán)境試驗(yàn)工序擁有資源為24小時(shí)。試分析增加該工序后企業(yè)的最優(yōu)生產(chǎn)計(jì)劃。

解

先將原問題的最優(yōu)解x1=4,x2=12代入環(huán)境試驗(yàn)工序的約束條件2x1x2≤24。，故原問題最優(yōu)解不是本例的最優(yōu)解。在試驗(yàn)工序的約束條件中加松弛變量得:2x1+1.5x2+x6=24以x6為基變量，將上式反映到最終單純形表中得表:由于x1、x2、x5、x6為基變量，對應(yīng)的列向量應(yīng)為單位向量，故需進(jìn)行變換，得→90700000CB基bx1x2x3x4x5x670x212013-10090x1410-21000x5500-155100x62421.50001