Chapter-2-對偶理論及靈敏度分析解析課件

1、線性規(guī)劃的對偶理論與靈敏度分析第二章介紹對偶問題的寫法、基本性質(zhì)及對偶單純形法；介紹影子價格的概念；介紹靈敏度分析的基本方法10/10/20221線性規(guī)劃的對偶理論與靈敏度分析第二章介紹對偶問題的寫法、基本章目錄2-1 線性規(guī)劃的對偶問題2-2 對偶問題的基本性質(zhì)2-3 影子價格2-4 對偶單純形法2-5 靈敏度分析2-6 參數(shù)線性規(guī)劃10/10/20222本章目錄2-1 線性規(guī)劃的對偶問題10/9/202222-1 線性規(guī)劃的對偶問題引言一、對偶問題二、對稱形式對偶問題的一般形式三、非對稱形式的原-對偶問題四、對偶問題的寫法返回本章目錄10/10/202232-1 線性規(guī)劃的對偶問題引言返回

2、本章目錄10/9/20引 言在實際問題中，一個問題的優(yōu)化往往可以從不同的兩個角度提出問題。譬如，要求在有限資源條件下生產(chǎn)利潤最大；或在一定生產(chǎn)能力條件下使資源消耗最少。所以，在線性規(guī)劃中，對任一給定的求最大值問題，相應(yīng)也存在一個求最小值的問題。且兩者包括有相同的數(shù)據(jù)。若稱前者為原問題，則后者便稱為對偶問題；或稱前者為對偶問題，而稱后者為原問題。兩者互為對偶，具有密切的關(guān)系。只要得到其中一個問題的解，也就能夠得到另一個問題的解。因而，從中選一個問題求解就可以了。10/10/20224引 言在實際問題中，一個問題的優(yōu)化往往可以從不同的兩一、對偶問題例1 美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品的線性

3、規(guī)劃模型為：設(shè)y1，y2，y3分別表示設(shè)備A、B和調(diào)試工序單位時間的價格。則0y1+6y2+y325y1+2y2+y31對生產(chǎn)產(chǎn)品的全部資源的定價。假如另一公司想收購美佳公司的資源，美佳公司出讓自己資源的條件是什么？出讓代價不低于用同等資源組織生產(chǎn)兩種產(chǎn)品所能獲得的利潤。對生產(chǎn)產(chǎn)品的全部資源的定價。產(chǎn)品的利潤產(chǎn)品的利潤10/10/20225一、對偶問題例1 美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品的原問題與對偶問題的數(shù)據(jù)比較 原問題對偶問題x1x2原關(guān)系min wy10515y26224y3115對偶關(guān)系max z = min wmax z2110/10/20226原問題與對偶問題的數(shù)據(jù)比較 原

4、問題x1二、對稱形式對偶問題的一般形式定義：滿足下列條件的線性規(guī)劃問題稱為具有對稱形式：其變量均具有非負約束，其約束條件當目標函數(shù)求極大時取“”號，當目標函數(shù)求極小時均取“”號。則其對偶問題的一般形式為：若原問題的一般形式為：yi(i=1,2,，m)代表第i種資源的估價。10/10/20227二、對稱形式對偶問題的一般形式定義：滿足下列條件的線性規(guī)劃問矩陣形式表示的原問題與對偶問題原問題：對偶問題：令ww對偶問題令zz對偶問題的對偶是原問題10/10/20228矩陣形式表示的原問題與對偶問題原問題：對偶問題：令ww三、非對稱形式的原-對偶問題考慮標準形式的線性規(guī)劃：max z = CX AX

5、= b X0max z = CX AX b AX b X0min w = bT (YY) AT (Y Y ) CT Y0， Y 0令Y= YY min w = bT Y AT Y CT Y 為自由變量這就是非對稱形式的對偶關(guān)系。在這種形式中，Y 不要求非負。max z = CX AX b AX b X0YYmin w = Yb AY C Y 為自由變量10/10/20229三、非對稱形式的原-對偶問題考慮標準形式的線性規(guī)劃：max 四、對偶問題的寫法在寫對偶問題時，要特別注意上表中原問題與其對偶問題的對應(yīng)關(guān)系。10/10/202210四、對偶問題的寫法在寫對偶問題時，要特別注意上表中原問題與其

6、寫對偶問題的步驟：第一步：根據(jù)原問題數(shù)學(xué)模型的形式統(tǒng)一符號。若原問題目標函數(shù)求極大，則將其約束條件統(tǒng)一成“”或“”的形式；若原問題目標函數(shù)為求極小，則將其約束條件統(tǒng)一成“”或“”的形式。第二步：假設(shè)對偶變量。對偶變量與原問題的約束條件一一對應(yīng)，每一個約束條件都有一個對偶變量與它相對應(yīng)。所以，對偶變量數(shù)等于原問題的約束方程數(shù)。第三步：根據(jù)原問題與對偶問題的關(guān)系寫出對偶規(guī)劃模型。10/10/202211寫對偶問題的步驟：第一步：根據(jù)原問題數(shù)學(xué)模型的形式統(tǒng)一符號。例: 寫出下面規(guī)劃問題的對偶規(guī)劃問題。原問題：max z = 4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5 = -

7、6 3x1+x2-x3-x4 2 - 4x1+2x3-2x4 - 5 - 6 x1 18 x2 25 x3,x4 0; x5 不受限制統(tǒng)一符號（因求max,故約束統(tǒng)一成“ ”的形式：max z = 4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5 = - 6 - 3x1- x2 +x3 +x4 - 2 - 4x1 +2x3 -2x4 - 5 x1 18 - x1 6 x2 25 x3,x4 0;x1,x2, x5 不受限制y1y2y3y4y6y5min w = - 6y1-2y2-5y3+18y4+6y5+25y6-3y2-4y3+y4- y5 = 42y1-y2+y6=1y

8、1+y2+2y3 -53y1+y2-2y3 - 44y1= - 2yi 0 ( i=2,3,4,5,6) ; y1為自由變量對偶問題第一步：統(tǒng)一符號第二步：假設(shè)變量第三步：寫對偶問題10/10/202212例: 寫出下面規(guī)劃問題的對偶規(guī)劃問題。原問題：統(tǒng)一符號（例2 寫出下述線性規(guī)劃問題的對偶問題原問題：令x2x4，x40統(tǒng)一約束符號：y1y2y3對偶問題：令y2y4，可得到教材上的形式：10/10/202213例2 寫出下述線性規(guī)劃問題的對偶問題原問題：令x2x4，教材上例2的解法：原問題：令x2x2；x3x3x3用兩個不等式約束表示等式約束：統(tǒng)一約束符號：10/10/202214教材上例2

9、的解法：原問題：令x2x2；x3x3假設(shè)變量：寫對偶問題：令y2y2；y3y3y310/10/202215假設(shè)變量：寫對偶問題：令y2y2；y3y3y310/10/20221610/9/2022162-2 對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述原問題對偶問題Xs為松弛變量；Xs= (xn+1,xn+2,xn+m);I為mm階單位矩陣。返回本章目錄提綱：一、單純形法計算的矩陣描述二、對偶問題的基本性質(zhì)10/10/2022172-2 對偶問題的基本性質(zhì)一、單純形法計算的矩陣描述原問10/10/20221810/9/202218表2-3 初始單純形表非基變量基變量CjCBCN0CB基bXBXN

10、Xs0XsbBNIcj-zjCBCN0表2-4 最終單純形表基變量非基變量CjCBCN0CB基bXBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-110/10/202219表2-3 初始單純形表非基變量基變量CjCBCN0C基變量XB的檢驗數(shù)為：CBCBI 0所以，在最終單純形表中，原變量的檢驗數(shù)可寫為CCBB-1A0（2.17）CBB-10（2.18）CBB-1稱為單純形乘子。令Y CBB-1，則2.17、2.18式可以改寫為CCBB-1A0 YACI AYC Y0可以看出，原問題得到最優(yōu)解時，其檢驗數(shù)的相反數(shù)是對偶問題的一個可行解。代入對偶問題的目標函數(shù)得

11、w Yb CBB-1bz即 原問題得到最優(yōu)解時，對偶問題為可行解，兩者具有相同的目標函數(shù)值。10/10/202220基變量XB的檢驗數(shù)為：CBCBI 0可以看出，原問題得到例3 兩個互為對偶的線性規(guī)劃問題解的比較原問題：對偶問題：10/10/202221例3 兩個互為對偶的線性規(guī)劃問題解的比較原問題：對偶問題原問題的解為X(x1,x2,x3,x4,x5)T(7/2,3/2,15/2,0,0)T與最優(yōu)解對應(yīng)的目標函數(shù)值為：對偶問題的解為Y(y1,y2,y3,y4,y5)T(0,1/4,1/2,0,0)T與最優(yōu)解對應(yīng)的目標函數(shù)值為：10/10/202222原問題的解為X(x1,x2,x3,x4,x

12、5)T(7/2例 3原變量松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2cj-zj000-1/4-1/2對偶剩余變量對偶問題變量y4y5y1y2y3對偶問題變量對偶剩余變量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2原問題松弛變量原問題變量x3x4x5x1x2 在最優(yōu)單純形表的檢驗數(shù)行，原問題變量對應(yīng)的數(shù)的相反數(shù)，是對偶問題剩余變量的值；原問題松弛變量對應(yīng)的數(shù)的相反數(shù)，是對偶問題變量的值。反之亦然。10/10/202223例 3原變

13、量松弛變量x1x2x3x4x5x315/20015二、對偶問題的基本性質(zhì)1.弱對偶性：證：10/10/202224二、對偶問題的基本性質(zhì)1.弱對偶性：證：10/9/20222由弱對偶性得到推論：（1）原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。（2）如原問題有可行解且目標函數(shù)值無界（無界解），則其對偶問題無解；反之，對偶問題有可行解且目標函數(shù)值無界，則其原問題無可行解。（3）若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界；反之，對偶問題有可行解而其原問題無可行解，則對偶問題目標函數(shù)值無界。10/10/2

14、02225由弱對偶性得到推論：（1）原問題任一可行解的目標函數(shù)值是其對2. 最優(yōu)性：3. 強對偶性（對偶定理）：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。10/10/2022262. 最優(yōu)性：3. 強對偶性（對偶定理）：10/9/20224. 互補松弛性：在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之，如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。10/10/2022274. 互補松弛性：在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束2-3 影子價格當線性規(guī)劃原問題求得最優(yōu)解xj*( j =1,2,n

15、 )時，其對偶問題也得到最優(yōu)解yi*( i =1,2,m )，且兩者的目標函數(shù)值相等。即bi：線性規(guī)劃原問題右端項，代表第 i 種資源的擁有量；yi*：對偶變量，代表在最優(yōu)資源利用條件下對單位第 i 種資源的估價，稱為影子價格。影子價格(Shadow Price)也稱為機會成本(Opportunity Cost),它是根據(jù)具體的經(jīng)濟目標、技術(shù)水平和資源條件作出的對資源利用的評價。市場價格：是資源在市場上流通的實際價格，它由整個社會的經(jīng)濟技術(shù)狀況決定。返回本章目錄10/10/2022282-3 影子價格當線性規(guī)劃原問題求得最優(yōu)解xj*( j 根據(jù) 求 bi 的偏導(dǎo)數(shù)得：這說明，原問題某一約束條件

16、的右邊常數(shù)bi增加一個單位時，則由此引起最優(yōu)目標函數(shù)值的增加量，就等于與該約束相對應(yīng)的對偶變量的最優(yōu)值。這樣一來，在有限資源條件下使收益最大化這一類問題中，就可以把對偶變量的最優(yōu)值，看成是相應(yīng)資源每一單位對于目標函數(shù)的貢獻，即這些資源被充分利用時所能帶來的收益。從而， yi* 的值就相當于對單位 i 種資源在實現(xiàn)最大利潤時的一種價格估計。這種估計是針對具體企業(yè)，具體產(chǎn)品而存在的一種特殊價格，稱之為影子價格，它與市場價格不同。若僅從經(jīng)濟上考慮，當某種資源的市場價格低于影子價格時，企業(yè)就可以考慮買進這種資源；當市場價格高于影子價格時，企業(yè)則可以出售這種資源。隨著資源的買進賣出，它的影子價格也將隨之

17、變化，直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。10/10/202229根據(jù) 影子價格是一種邊際價格（圖示）Q1Q3Q2Q4Ox1x25x2156x12x224x1x25z2z8.5(3.5，1.5)(25)10/10/202230影子價格是一種邊際價格（圖示）Q1Q3Q2Q4Ox1x25x影子價格的應(yīng)用（1）用影子價格判別資源的供求關(guān)系如果線性規(guī)劃的原問題在得到最優(yōu)解時，某個約束條件為嚴格的不等式，即最優(yōu)解中該約束的松弛變量的值大于零，即表明該種資源有剩余，供大于求。增加這種資源時，目標函數(shù)值不會有任何改善。如果線性規(guī)劃的原問題在得到最優(yōu)解時，某個約束條件為嚴格的等式，即最優(yōu)解中

18、該約束的松弛變量的值等于零，即表明該資源恰恰用完。這種資源增加一個單位，目標函數(shù)值就改進一個影子價格。由此可見，影子價格大于零，說明資源緊缺；影子價格等于零，說明資源有剩余。影子價格愈大，說明該資源愈緊缺，該種資源每增加一個單位所相應(yīng)增加的目標函數(shù)值愈大。10/10/202231影子價格的應(yīng)用（1）用影子價格判別資源的供求關(guān)系表明該種資源如果xn+i=0,必有yi0，資源緊缺；如果xn+i0,必有yi0，資源剩余。松弛變量xs對偶變量yi資源限量bi10/10/202232如果xn+i=0,必有yi0，資源緊缺；如果xn+i0（2）應(yīng)用影子價格來合理分配資源算出各種資源的影子價格后，可參考影子

19、價格高低順序合理分配資源，高者優(yōu)先投資。同時，也可以參考資源的影子價格，合理地確定各種資源的價格。10/10/202233（2）應(yīng)用影子價格來合理分配資源算出各種資源的影子價格后，可2-4 對偶單純形法引言前面介紹的單純形法，是從一個基本可行解開始進行迭代運算，在迭代過程中，始終保持解的可行性，當所有檢驗數(shù)都非正時，就得到了原問題的最優(yōu)解。根據(jù)對偶定理，原問題單純形表中的檢驗數(shù)實際上是對偶問題的一組解，但不一定可行，檢驗數(shù)逐漸變?yōu)榉钦倪^程，可以理解為對偶問題解的不可行性逐漸消失的過程，當對偶問題的解變?yōu)榭尚薪鈺r，原問題就得到了最優(yōu)解。因此，我們可以選擇在對偶問題的解之間進行迭代運算，在迭代過

20、程中，始終保持最優(yōu)判別條件得到滿足，當求出對偶問題的可行解時，也就得到了原問題的最優(yōu)解。返回本章目錄10/10/2022342-4 對偶單純形法引言返回本章目錄10/9/20223例4 用對偶單純形法求解線性規(guī)劃問題：將約束條件兩邊同時乘以“-1”得：標準形式得到初始基為：基變量為y4,y5，非基變量為y1,y2,y3。令所有的非基變量等于0，得到該問題的一個解為：Y= ( 0,0,0,-2,-1 )T這個解不可行，稱為正則解。對偶單純形法就是從一個正則解開始迭代的。10/10/202235例4 用對偶單純形法求解線性規(guī)劃問題：將約束條件兩邊同時乘表2-8cj-15-24-500CB基by1y

21、2y3y4y50y4-20-6-1100y5-1-5-2-101cjzj-15-24-500確定換出變量y4為換出變量2.確定換入變量y2為換入變量。3.迭代運算，得新單純形表。-24y21/3011/6-1/600y5-1/3-50-2/3-1/31cjzj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cjzj-15/200-7/2-3/2sj0，最優(yōu)解Y=(0,1/4,1/2,0,0)TMin w=15y1+24y2+5y3=17/210/10/202236表2-8cj-15-24-500CB基by1y2y3y4y2-5 靈敏度分析對一

22、線性規(guī)劃問題來說，一旦其約束條件系數(shù)矩陣A、約束條件右側(cè)常數(shù)向量b和價值系數(shù)向量C給定之后，這個線性規(guī)劃問題就確定了。反之，給定一個線性規(guī)劃問題，就有確定的一組A、b和C與之對應(yīng)。在此之前，我們一直假定A、b和C中的元素是常數(shù)，它們不發(fā)生變化。但實際上這些系數(shù)往往是通過估計、預(yù)測或人為決策得來的，不可能十分準確和一成不變。例如：市場條件一變，價值系數(shù)cj就會跟著變化；約束條件系數(shù)矩陣A中的元素aij往往隨著工藝技術(shù)條件的變化而改變；bi通常取決于現(xiàn)有條件和決策人的決策。這就是說，隨著時間的推移或情況的變化，我們往往需要修改原來線性規(guī)劃問題中的若干系數(shù)，從而使原來的規(guī)劃問題有所改變。就實際需要來

23、講，求出最優(yōu)解，還不能說問題已完全解決。決策者還需要知道以下一些問題。返回本章目錄10/10/2022372-5 靈敏度分析對一線性規(guī)劃問題來說，一旦其約束條件系當這些系數(shù)中的一個或幾個發(fā)生變化時，已求得的最優(yōu)解有什么變化？這些系數(shù)在什么范圍內(nèi)改變時，規(guī)劃問題的最優(yōu)解或最優(yōu)基不變？若最優(yōu)解變化，如何用最簡便的方法找到新的最優(yōu)解？靈敏度分析就是研究提出在原始計算結(jié)果基礎(chǔ)上直接分析參數(shù)變化對最優(yōu)解影響的方法。靈敏度分析的步驟：（1）將參數(shù)的變化反映到最終單純形表上；（2）檢查原問題是否仍為最優(yōu)解；（3）檢查對偶問題是否仍為最優(yōu)解；（4）按下表所列情況得出結(jié)論，決定繼續(xù)計算的步驟。10/10/202

24、238當這些系數(shù)中的一個或幾個發(fā)生變化時，已求得的最優(yōu)解有什么變化靈敏度分析的有關(guān)計算公式表2-9原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量，重新編單純形表計算10/10/202239靈敏度分析的有關(guān)計算公式表2-9原問題對偶問題結(jié)論或繼續(xù)計算美佳公司用三中資源生產(chǎn)兩種產(chǎn)品的線性規(guī)劃模型初始單純形表：初始單純形表cj 21000CB基bx1x2x3x4x50 x315051000 x424620100 x5511001cjzj2100010/10/2022

25、40美佳公司用三中資源生產(chǎn)兩種產(chǎn)品的線性規(guī)劃模型初始單純形表：初靈敏度分析的主要內(nèi)容一、分析cj變化二、分析bi的變化三、增加一個變量xj的分析四、分析參數(shù)aij的變化五、增加一個約束條件的分析10/10/202241靈敏度分析的主要內(nèi)容一、分析cj變化10/9/202241（1）美佳公司家電的利潤降至1.5元/件，家電的利潤增至2元/件。一、分析 cj 的變化（例 5）最終單純表cj 21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cjzj000-1/4-1/20 x46004/51-61.5x121

26、0-1/5012x23011/500cjzj00-1/100-3/2y1=0, y2=1/4, y3=1/21.521.521/8-9/4返回提要10/10/202242（1）美佳公司家電的利潤降至1.5元/件，家電的利潤增至家電的利潤變化范圍：若要保持最優(yōu)解不變，必須(2)家電的利潤變?yōu)椋?）元最終單純表cj 21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cjzj000-1/4-1/21+l1+l10/10/202243家電的利潤變化范圍：若要保持最優(yōu)解不變，必須(2)家電的二、分析 bi 的變化（

27、 例 6 ）最終單純表cj 21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cjzj000-1/4-1/2（1）美家公司設(shè)備A和調(diào)試工序的每天能力不變，設(shè)備B每天的能力增加到32小時，分析公司最優(yōu)計劃的變化。35/211/2-1/20 x315051002x15110010 x420-401-6cjzj0-100-2返回提要10/10/202244二、分析 bi 的變化（ 例 6 ）最終單純表cj 210（2）設(shè)備A和設(shè)備B可用能力不變，則調(diào)試工序能力在什么范圍變化時，問題的最優(yōu)基不變。最終單純表cj

28、21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cjzj000-1/4-1/2設(shè)調(diào)試工序每天可用能力為（5+l）小時。調(diào)試工序能力在4之間變化時，最優(yōu)基不變。10/10/202245（2）設(shè)備A和設(shè)備B可用能力不變，則調(diào)試工序能力在什么范圍變?nèi)?、增加一個變量xj的分析增加一個變量在實際問題中表示增加一種新產(chǎn)品。分析步驟：例7 美佳公司計劃推出新型產(chǎn)品家電，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時間分別為3小時、4小時、2小時，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，該公司生產(chǎn)計劃有何變

29、化。解：設(shè)該公司每天生產(chǎn)家電x6件，則有c6 = 3; P6 = ( 3,4,2 )T返回提要10/10/202246三、增加一個變量xj的分析增加一個變量在實際問題中表示增加一例 7最終單純形表cj 21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cjzj000-1/4-1/2x63-70210 x33/407/213/8-9/402x17/21001/4-1/201x63/401/20-1/83/41cjzj0-1/20-1/8-5/40美佳公司新的最優(yōu)生產(chǎn)計劃應(yīng)為每天生產(chǎn)家電7/2件，家電3/4件

30、?？色@得利潤27/210+33/437/4（元）10/10/202247例 7最終單純形表cj 21000CB基bx1x2x3x4四、分析參數(shù)aij的變化aij 的變化將引起約束條件系數(shù)矩陣 A 發(fā)生變化。例8 在美佳公司的例子中，若家電每件需設(shè)備A、B和調(diào)試工時變?yōu)?小時、4小時、1小時，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定該公司的最優(yōu)生產(chǎn)計劃。解：將生產(chǎn)工時變化后的新家電看作是一種新產(chǎn)品，生產(chǎn)量為x2，則返回提要10/10/202248四、分析參數(shù)aij的變化aij 的變化將引起約束條件系數(shù)矩陣例8最終單純形表cj 213000CB基bx1x2x2x3x4x50 x315/20011/21

31、5/4-15/22x17/2101/201/4-1/21x23/2011/20-1/43/2cjzj003/20-1/4-1/20 x3-90014-242x121001/2-23x23010-1/23cjzj0001/2-5從上表看出，原問題和對偶問題均為非可行解，故先設(shè)法使原問題變?yōu)榭尚薪?。x34x424x59x34x424x5x69人工變量10/10/202249例8最終單純形表cj 213000CB基bx1x2x2x表2-19cj23000MCB基bx1x2x3x4x5x6-Mx6900-1-42412x121001/2-203x23010-1/230cjzj00-M-4M-5+24M

32、00 x53/800-1/24-1/611/242x111/410-1/121/601/123x215/8011/800-1/8cjzj00-5/24-1/30-M+5/24因為所有檢驗數(shù)sj0，所以得到問題的最優(yōu)解，即美佳公司的最優(yōu)生產(chǎn)計劃是每天生產(chǎn)家電11/4件，新家電15/8件。10/10/202250表2-19cj23000MCB基bx1x2x3x4x5cj213000CB基bx1x2x2 x3x4x50 x3-90014-242x121001/2-23x23010-1/23cjzj0001/2-5如果不加人工變量，可用對偶單純形法從正則解開始迭代找出最優(yōu)解。0 x53/800-1/2

33、4-1/612x111/410-1/121/603x215/8011/800cjzj00-5/24-1/30因為所有檢驗數(shù)sj0，所以得到問題的最優(yōu)解，即美家公司的最優(yōu)生產(chǎn)計劃是每天生產(chǎn)家電11/4件，新家電15/8件。10/10/202251cj213000CB基bx1x2x2 x3x4x50 x3五、增加一個約束條件的分析增加一個約束條件在實際問題中相當于增加一道工序。分析方法是先將原問題最優(yōu)解的變量值代入新增的約束條件，如滿足，說明新增的約束條件未起到限制作用，原最優(yōu)解不變。否則，將新增的約束直接反映到最終單純形表中再進一步分析。例9 設(shè)美佳公司家電，家電經(jīng)調(diào)試后，還需經(jīng)過一道環(huán)境試驗工

34、序，家電每件須環(huán)境試驗3小時，家電每件2小時，環(huán)境試驗工序每天生產(chǎn)能力為12小時。試分析增加該工序后，美家公司的最優(yōu)生產(chǎn)計劃。 解：環(huán)境試驗工序的約束條件為3x1+2x212將原問題最優(yōu)解代入得：37/223/227/212由此可見，新增約束得不到滿足，需加入松弛變量，將其化為標準形式：3x1+2x2x612以x6為基變量，將新增約束填入最終單純形表中。返回提要10/10/202252五、增加一個約束條件的分析增加一個約束條件在實際問題中相當于表2-21cj210000CB基bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-

35、1/43/200 x612320001cj-zj000-1/4-1/200 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/200 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/332用對偶單純形法迭代計算增加環(huán)境試驗工序后，美佳公司的最優(yōu)生產(chǎn)計劃為每天生產(chǎn)家電4 件。10/10/202253表2-21cj210000CB基bx1x2x3x4x5x62-6 參數(shù)線性規(guī)劃靈

36、敏度分析中研究cj、bi等參數(shù)改變到某一值時對問題最優(yōu)解的影響，若令cj、bi沿某一方向連續(xù)變動，則目標函數(shù) z將隨 cj 或 bi 的變動而呈線性變動，z 是這個變動參數(shù)的線性函數(shù)，因而稱為參數(shù)線性規(guī)劃。參數(shù)線性規(guī)劃的一般形式：cj 連續(xù)變化時：bi 連續(xù)變化時：C*和b*為變動向量，l為變動參數(shù)。返回本章目錄10/10/2022542-6 參數(shù)線性規(guī)劃靈敏度分析中研究cj、bi等參數(shù)改變例10 分析 l值變化時，下述線性規(guī)劃最優(yōu)解的變化解：令l0，求得：最終單純形表cj 21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2

37、010-1/43/2cjzj000-1/4-1/22+l1+2l2+l1+2l若1，x4換入基，x3換出基10/10/202255例10 分析 l值變化時，下述線性規(guī)劃最優(yōu)解的變化解：令表2-25最終單純形表cj 2+l1+2l000CB基bx1x2x3x4x50 x46004/51-62+lx1210-1/5011+2lx23011/500cjzj000-2-l所以，l1時，最優(yōu)解為X*（2，3，0，6，0）T z ()= 7+8l10/10/202256表2-25最終單純形表cj 2+l1+2l000CB基bx若l-15，x5為換入變量，x2為換出變量。最終單純形表cj 2+1+2000C

38、B基bx1x2x3x4x50 x315/20015/4-15/22+lx17/21001/4-1/21+2lx23/2010-1/43/2cjzj000-1/4-1/210/10/202257若l-15，x5為換入變量，x2為換出變量。最終單純形表表2-26cj2+l1+2l000CB基bx1x2x3x4x50 x315051002+lx1411/301/600 x5102/30-1/61cj-zj000若2，X4為換入變量，X1為換出變量。10/10/202258表2-26cj2+l1+2l000CB基bx1x2x3x42cj2+l1+2l000CB基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj2+l1+2l00010/10/2022592cj2+l1+2l000CB基bx1x2x3x4x例10小結(jié)l變化范圍最優(yōu)解目標函數(shù)-1/517/2，3/2，15/2，0，0z = 17/2 + 13/2ll12，3，0，6，0z = 7 + 8l-2-1/54，0，15，0，1z = 8 + 4l20，0，15，24，5z = 0lz(l)-20-0.27.211522310/10/202260例10小結(jié)l變化范圍最優(yōu)解目標函數(shù)-1/517/2，3例11 分析l變化時，下屬線性規(guī)劃問題最優(yōu)解的變化解：1. 令l=0求出最優(yōu)單