《運(yùn)籌學(xué)》胡運(yùn)權(quán)第4版線性規(guī)劃的對(duì)偶理論及靈敏度分析省公開課一等獎(jiǎng)全國示范課微課金獎(jiǎng)?wù)n件

第二章線性規(guī)劃對(duì)偶理論及靈敏度分析OperationalResearch(OR)1/69線性規(guī)劃對(duì)偶問題與靈敏度分析線性規(guī)劃對(duì)偶問題對(duì)偶問題基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃2/69對(duì)偶原理對(duì)偶問題概念：任何一個(gè)線性規(guī)劃問題都有一個(gè)伴生線性規(guī)劃問題，稱為其“對(duì)偶”問題。對(duì)偶問題是對(duì)原問題從另一角度進(jìn)行描述，其最優(yōu)解與原問題最優(yōu)解有著親密聯(lián)絡(luò)，在求得一個(gè)線性規(guī)劃最優(yōu)解同時(shí)也就得到對(duì)偶線性規(guī)劃最優(yōu)解，反之亦然。對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問題理論，是線性規(guī)劃理論主要內(nèi)容之一。3/69問題導(dǎo)出項(xiàng)目ⅠⅡ天天可用能力設(shè)備A（h）0515設(shè)備B（h）6224調(diào)試工序（h）115利潤（元）21例2-1我們引用第一章中美佳企業(yè)例子，如表1其線性規(guī)劃問題為：？假定有某個(gè)企業(yè)想把美佳企業(yè)資源收買過來，它最少應(yīng)付出多大代價(jià)，才能使美佳企業(yè)愿意放棄生產(chǎn)活動(dòng)，出讓自己資源？（LP1）4/69問題導(dǎo)出例2-1條件：出讓代價(jià)應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活動(dòng)時(shí)獲取贏利。y1,y2,y3分別代表單位時(shí)間（h）設(shè)備A、設(shè)備B和調(diào)試工序出讓代價(jià)。y1,y2,y3取值應(yīng)滿足：美佳企業(yè)用6h設(shè)備B和1h調(diào)試可生產(chǎn)一件家電I,贏利2元用5h設(shè)備A,2h設(shè)備B及1h調(diào)試可生產(chǎn)一件家電Ⅱ，贏利1元該企業(yè)希望用最小代價(jià)把美佳企業(yè)全部資源收買過來，即：5/69問題導(dǎo)出例2-1總而言之，（LP2）LP1和LP2兩個(gè)線性規(guī)劃問題，通常稱LP1為原問題，LP2為前者對(duì)偶問題。6/69對(duì)偶問題定義對(duì)稱形式對(duì)偶問題7/69對(duì)偶問題定義對(duì)稱形式對(duì)偶問題8/69對(duì)偶問題定義對(duì)偶問題特點(diǎn)若原問題目標(biāo)是求極大化，則對(duì)偶問題目標(biāo)是極小化，反之亦然原問題約束系數(shù)矩陣與對(duì)偶問題約束系數(shù)矩陣互為轉(zhuǎn)置矩陣極大化問題每個(gè)約束對(duì)應(yīng)于極小化問題一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問題一個(gè)約束。

9/69對(duì)偶問題定義普通線性規(guī)劃問題對(duì)偶問題10/69對(duì)偶問題定義對(duì)偶問題對(duì)應(yīng)表原問題（對(duì)偶問題）對(duì)偶問題（原問題）目標(biāo)函數(shù)maxZ目標(biāo)函數(shù)minZ約束條件：m個(gè)第i個(gè)約束類型為“≤”第i個(gè)約束類型為“≥”第i個(gè)約束類型為“＝”變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量

變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量

約束條件：n個(gè)第j個(gè)約束類型為“≥”第j個(gè)約束類型為“≤”第j個(gè)約束類型為“＝”11/69對(duì)稱形式下

對(duì)偶問題例2－2標(biāo)準(zhǔn)型對(duì)偶問題12/69對(duì)稱形式下對(duì)偶問題例2－313/69非對(duì)偶形式原-對(duì)偶問題例2-4寫出以下問題對(duì)偶問題（2.4a）（2.4b）（2.4c）（2.4d）對(duì)偶變量y1y2′y2″y3′先轉(zhuǎn)換成對(duì)稱形式，以下：14/69非對(duì)偶形式原-對(duì)偶問題例2-4令各約束對(duì)應(yīng)對(duì)偶變量分別為y1、y2′、y2″、-y3′令y2=y2′-y2″，y3=-y3′，原問題對(duì)偶問題為15/69對(duì)應(yīng)關(guān)系總結(jié)項(xiàng)目原問題（對(duì)偶問題）對(duì)偶問題（原問題）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=∑CjXjminw=∑

biyi16/69線性規(guī)劃對(duì)偶問題與靈敏度分析線性規(guī)劃對(duì)偶問題對(duì)偶問題基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃17/69對(duì)偶問題基本性質(zhì)單純形法計(jì)算矩陣描述對(duì)稱形式線性規(guī)劃矩陣表示式加上松弛變量Xs后為：其中松弛變量Xs=（xn+1,xn+2,...,xn+m）,I為m×m單位矩陣項(xiàng)目基變量基變量XBXNXs0XsbBNIcj-zjCBCN0選取I為初始基，對(duì)應(yīng)基變量為Xs。設(shè)迭代若干步后，基變量為XB，XB在初始單純形表中系數(shù)矩陣為B。A中去掉B若干列后剩下列組成矩陣N。18/69深入迭代,新單純形表以下：對(duì)偶問題基本性質(zhì)項(xiàng)目基變量非基變量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N–CBB-1對(duì)應(yīng)初始單純形表中單位矩陣I，迭代后單純形表中為B-1初始單純形表中基變量Xs=b，迭代后表中XB=B-1b初始單純形表中約束系數(shù)矩陣為[A,I]=[B,N,I]，迭代后表中約束系數(shù)矩陣為[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]若初始矩陣中變量xj系數(shù)向量為Pj，迭代后為Pj′，則有Pj′=B-1Pj當(dāng)B為最優(yōu)基時(shí)，表中應(yīng)有CN-CBB-1N≤0,-CBB-1≤019/69對(duì)偶問題基本性質(zhì)例2-5參看例2-1中原問題和對(duì)偶問題，并分別加上松弛變量和剩下變量，以下：對(duì)偶變量y1y2y3對(duì)偶變量x1x220/69對(duì)偶問題基本性質(zhì)兩個(gè)問題最終單純形表以下：項(xiàng)目原問題變量原問題松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2變量對(duì)偶問題剩下變量對(duì)偶問題變量y4y5y1y2y3項(xiàng)目對(duì)偶問題變量對(duì)偶問題剩下變量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2變量原問題松弛變量原問題變量x3x4x5x1x221/69對(duì)偶問題基本性質(zhì)1.弱對(duì)偶性

假如xj（j=1，...，n）是原問題可行解，yi（i=1，...，m）是其對(duì)偶問題可行解，則恒有22/69對(duì)偶問題基本性質(zhì)弱對(duì)偶性推論：(1)原問題任一可行解目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值下界；反之對(duì)偶問題任一可行解目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值上界。23/69(2)如原問題有可行解且目標(biāo)函數(shù)值無界(含有沒有界解)，則其對(duì)偶問題無可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解。注意：本點(diǎn)性質(zhì)逆不成立，當(dāng)對(duì)偶問題無可行解時(shí)，其原問題或含有沒有界解或無可行解，反之亦然。對(duì)偶問題基本性質(zhì)24/69(3)若原問題有可行解而其對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題目標(biāo)函數(shù)值無界。對(duì)偶問題基本性質(zhì)25/69對(duì)偶問題基本性質(zhì)最優(yōu)性假如(j=1,...,n)是原問題可行解，(i=1,...,m)是其對(duì)偶問題可行解，且有則(j=1,...,n)是原問題最優(yōu)解，(i=1,...,m)是其對(duì)偶問題最優(yōu)解。26/69對(duì)偶問題基本性質(zhì)強(qiáng)對(duì)偶性(或稱對(duì)偶定理)

若原問題及其對(duì)偶問題均含有可行解，則二者均含有最優(yōu)解，且它們最優(yōu)解目標(biāo)函數(shù)值相等。27/69對(duì)偶問題基本性質(zhì)互補(bǔ)松弛性

在線性規(guī)劃問題最優(yōu)解中，假如對(duì)應(yīng)某一約束條件對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之假如約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)對(duì)偶變量一定為零。也即若>0，則有，即若，即，則有所以一定有，

28/69線性規(guī)劃對(duì)偶問題與靈敏度分析線性規(guī)劃對(duì)偶問題對(duì)偶問題基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃29/69影子價(jià)格對(duì)偶最優(yōu)解經(jīng)濟(jì)含義――影子價(jià)格

代表著當(dāng)?shù)趇個(gè)右端常數(shù)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值對(duì)應(yīng)增量。其含義是在當(dāng)前已給定情況下，最優(yōu)目標(biāo)值隨資源數(shù)量改變改變率；其經(jīng)濟(jì)含義是為約束條件所付出代價(jià)。

當(dāng)B是原問題最優(yōu)基時(shí)，Y=CBB-1就是影子價(jià)格向量。30/69影子價(jià)格資源市場(chǎng)價(jià)格是其價(jià)值客觀表達(dá)，相對(duì)比較穩(wěn)定，而它影子價(jià)格則有賴于資源利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生改變，資源影子價(jià)格也隨之改變。影子價(jià)格是一個(gè)邊際價(jià)格。資源影子價(jià)格實(shí)際上又是一個(gè)機(jī)會(huì)成本。伴隨資源買進(jìn)賣出，其影子價(jià)格也將隨之發(fā)生改變，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。31/69影子價(jià)格生產(chǎn)過程中假如某種資源未得到充分利用時(shí)，該種資源影子價(jià)格為零；又當(dāng)資源影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已花費(fèi)完成。影子價(jià)格反應(yīng)單純形表中各個(gè)檢驗(yàn)數(shù)經(jīng)濟(jì)意義。普通說對(duì)線性規(guī)劃問題求解是確定資源最優(yōu)分配方案，而對(duì)于對(duì)偶問題求解則是確定對(duì)資源恰當(dāng)估價(jià)，這種估價(jià)直接包括資源最有效利用。32/69影子價(jià)格舉例ABC擁有量工時(shí)1113材料1479單件利潤233

y1=5/3,y2=1/3

即工時(shí)影子價(jià)格為5/3，材料影子價(jià)格為1/3。假如當(dāng)前市場(chǎng)上材料價(jià)格低于1/3，則企業(yè)能夠購進(jìn)材料來擴(kuò)大生產(chǎn)，反之能夠賣掉部分材料。假如有客戶以高于5/3價(jià)格購置工時(shí)，則能夠出售一些工時(shí)，反之則反33/69線性規(guī)劃對(duì)偶問題與靈敏度分析線性規(guī)劃對(duì)偶問題對(duì)偶問題基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃34/69對(duì)偶單純形法對(duì)偶單純形法并不是求解對(duì)偶問題解方法，而是利用對(duì)偶理論求解原問題解方法。求解單純形法基本思緒：對(duì)原問題一個(gè)基可行解，判別是否全部檢驗(yàn)數(shù)cj-zj≤0(j=1,…,n)。若是，又基變量中無非零人工變量，即找到了問題最優(yōu)解；若為否，再找出相鄰目標(biāo)函數(shù)值更大基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進(jìn)行到找出最優(yōu)解為止。35/69對(duì)偶單純形法對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：可行基B

若B對(duì)應(yīng)基本解是可行解最優(yōu)基B

若B對(duì)應(yīng)基本解是最優(yōu)解對(duì)偶可行基B

若CBB-1是對(duì)偶問題可行解即C-CBB-1A≤0或檢驗(yàn)數(shù)≤036/69對(duì)偶單純形法對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：最優(yōu)基B可行基B對(duì)偶可行基B單純形法可行基B保持可行性對(duì)偶可行基B對(duì)偶單純形法可行基B保持對(duì)偶可行性對(duì)偶可行基B37/69對(duì)偶單純形法對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：對(duì)偶單純形法可行基B保持對(duì)偶可行性對(duì)偶可行基B①找一個(gè)基，建立初始對(duì)偶單純形表，檢驗(yàn)數(shù)全部非正；②若b列元素非負(fù)，則已經(jīng)是最優(yōu)基。反之，則取對(duì)應(yīng)行基變量為出基變量；③為確保能對(duì)基可行性有所改進(jìn)，則未來主元應(yīng)該為負(fù)數(shù)；為確保下一個(gè)基還能是對(duì)偶可行基，應(yīng)使檢驗(yàn)數(shù)仍為非正。④主元變換38/69對(duì)偶單純形法舉例例2－6用對(duì)偶單純形法求解：

39/69cj→-15-24-500CB基by1y2y3y4y50y4-20[-6]-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y3-1/3-50[-2/3]-1/31cj-zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2對(duì)偶單純形法舉例40/69對(duì)偶單純形法練習(xí)：用對(duì)偶單純形法求解

41/69線性規(guī)劃對(duì)偶問題與靈敏度分析線性規(guī)劃對(duì)偶問題對(duì)偶問題基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃42/69靈敏度分析

在生產(chǎn)計(jì)劃問題普通形式中，A代表企業(yè)技術(shù)情況，b代表企業(yè)資源情況，而C代表企業(yè)產(chǎn)品市場(chǎng)情況，在這些原因不變情況下企業(yè)最優(yōu)生產(chǎn)計(jì)劃和最大利潤由線性規(guī)劃最優(yōu)解和最優(yōu)值決定。在實(shí)際生產(chǎn)過程中，上述三類原因均是在不停改變，假如按照初始情況制訂了最正確生產(chǎn)計(jì)劃，而在計(jì)劃實(shí)施前或?qū)嵤┲猩鲜銮闆r發(fā)生了改變，則決議者所關(guān)心是當(dāng)前所執(zhí)行計(jì)劃還是不是最優(yōu)，假如不是應(yīng)該怎樣修訂原來最優(yōu)計(jì)劃。更深入，為了預(yù)防在各類情況發(fā)生時(shí)，來不及隨時(shí)對(duì)其改變作出反應(yīng)，即所謂“計(jì)劃不如改變快”，企業(yè)應(yīng)該預(yù)先了解，當(dāng)各項(xiàng)原因改變時(shí)，應(yīng)該作出什么樣反應(yīng)。43/69靈敏度分析步驟靈敏度分析步驟可歸納以下：1.將參數(shù)改變經(jīng)過計(jì)算反應(yīng)到最終單純形表上來。2.檢驗(yàn)原問題是否仍為可行解。3.檢驗(yàn)對(duì)偶問題是否仍為可行解。4.按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算步驟。原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算步驟可行解可行解問題最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新單純形表重新計(jì)算44/69靈敏度分析

CB

XB

cjCBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N若B是最優(yōu)基，則最優(yōu)表形式以下靈敏度分析總是在最優(yōu)表上進(jìn)行45/69靈敏度分析當(dāng)系數(shù)A，b，C發(fā)生改變時(shí)，當(dāng)前最優(yōu)基是否還最優(yōu)？為保持當(dāng)前最優(yōu)基還是最優(yōu)，系數(shù)A，b，C允許改變范圍是什么？假設(shè)每次只有一個(gè)系數(shù)改變①目標(biāo)系數(shù)C改變基變量系數(shù)發(fā)生改變；

非基變量系數(shù)發(fā)生改變；②右端常數(shù)b改變③增加一個(gè)變量④增加一個(gè)約束⑤技術(shù)系數(shù)A發(fā)生改變46/69靈敏度分析舉例分析cj改變例2-7

在第一章例1美佳企業(yè)例子中：（1）若家電Ⅰ利潤降至1.5元/件，而家電Ⅱ利潤增至2元/件時(shí)，美佳企業(yè)最優(yōu)生產(chǎn)計(jì)劃有何改變?cj→1.52000CB基bx1x2x3x4x50x315/2001[5/4]-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/40x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳企業(yè)隨家電Ⅰ，Ⅱ利潤改變應(yīng)調(diào)整為生產(chǎn)2件Ⅰ，生產(chǎn)3件Ⅱ。47/69項(xiàng)目21+λ000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21+λx23/2010-1/43/2cj-zj000-1/4+1/4λ-1/2-3/2λ（2）若家電Ⅰ利潤不變，則家電Ⅱ利潤在什么范圍內(nèi)改變時(shí)，該企業(yè)最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生改變？設(shè)家電Ⅱ利潤為（1+λ）元，以下為確保最優(yōu)解，-1/4+1/4λ≤0，-1/2-3/2λ

≤0解得-1/3≤λ≤1即家電Ⅱ利潤c2改變范圍應(yīng)滿足2/3≤c2≤2靈敏度分析舉例48/69分析bi改變例2-8

在美佳企業(yè)例子中：（1）若設(shè)備A和調(diào)試工序天天能力不變，而設(shè)備B天天能力增加到32h，分析企業(yè)最優(yōu)計(jì)劃改變；靈敏度分析舉例cj→21000CB基bx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2cj-zj000-1/4-1/20x315051002x15110010x420-401-6cj-zj0-100-249/69靈敏度分析舉例例2-8

（2）設(shè)設(shè)備A和設(shè)備B天天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)改變時(shí)，問題最優(yōu)基不變。設(shè)調(diào)試工序天天可用能力為（5+λ）h，因有最終單純形表中b列數(shù)字為因b>0時(shí)最優(yōu)基不變，故-1≤λ≤1。調(diào)試工序能力應(yīng)在4h~6h之間。50/69增加一個(gè)變量xj分析若企業(yè)在計(jì)劃期內(nèi)，有新產(chǎn)品能夠生產(chǎn)，則在知道新產(chǎn)品單位利潤，單件資源消耗量時(shí)，能夠在最優(yōu)表中補(bǔ)充一列，其中前m行能夠由基矩陣逆矩陣得到，而檢驗(yàn)數(shù)行也能夠由與其它列相同方法計(jì)算得到。若檢驗(yàn)數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；不然，當(dāng)檢驗(yàn)數(shù)為正時(shí)，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新最優(yōu)解。51/69增加一個(gè)變量xj分析靈敏度分析舉例增加一個(gè)變量在實(shí)際問題中反應(yīng)為增加一個(gè)新產(chǎn)品。其分析步驟為：3.若σj′≤0，原最優(yōu)解不變，只需將計(jì)算得到Pj′和σj′直接寫入最終單純形表中；若σj′>0，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。52/69例2-9

設(shè)美佳企業(yè)又計(jì)劃推出新型號(hào)家電Ⅲ，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序時(shí)間分別為3h、4h、2h，該產(chǎn)品預(yù)期盈利為3元/件，試分析該產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對(duì)該企業(yè)最優(yōu)生產(chǎn)計(jì)劃有何影響。設(shè)生產(chǎn)x6件家電Ⅲ，有c6=3，P6=（3，4，2）T靈敏度分析舉例53/69靈敏度分析舉例cj→210003CB基bx1x2x3x4x5x60x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/2[2]cj-zj000-1/4-1/210x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40最優(yōu)生產(chǎn)計(jì)劃應(yīng)為天天生產(chǎn)7/2件家電Ⅰ，51/4件家電Ⅲ。54/69靈敏度分析舉例分析參數(shù)aij改變例2-10在美佳企業(yè)例子中，若家電Ⅱ每件需設(shè)備A,B和調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品利潤變?yōu)?元/件，試重新確定該企業(yè)最優(yōu)生產(chǎn)計(jì)劃。設(shè)生產(chǎn)工時(shí)改變后新家電Ⅱ生產(chǎn)量為x2′，其中：55/69靈敏度分析舉例cj→23000CB基bx1x2′x3x4x50x315/2011/215/4-15/22x17/211/201/4-1/21x23/20[1/2]0-1/43/2cj-zj03/20-1/4-1/20x3-90014-242x121001/2-23x2′3010-1/23cj-zj0001/2-5原問題和對(duì)偶問題均為非可行解56/69上表中第二階段第一行約束為：x3+4x4-24x5=-9-x3-4x4+24x5+x6=9替換后重新得表：靈敏度分析舉例cj→23000-MCB基bx1x2′x3x4x5x6-Mx6900-1-4[24]12x121001/2-203x2′3010-1/230cj-zj00-M1/2-4M-5+24M00x53/800-1/24-1/611/242x111/410-1/121/601/123x2′15/8011/800-1/8cj-zj00-5/24-1/30-M+5/24最優(yōu)生產(chǎn)計(jì)劃為天天生產(chǎn)11/4臺(tái)家電Ⅰ，15/8臺(tái)家電Ⅱ57/69靈敏度分析舉例增加一個(gè)約束條件在企業(yè)生產(chǎn)過程中，經(jīng)常有一些突發(fā)事件產(chǎn)生，造成原本不緊缺某種資源變成為緊缺資源，對(duì)生產(chǎn)計(jì)劃造成影響。若把當(dāng)前最優(yōu)解代入新增加約束，能滿足約束條件，則說明該增加約束對(duì)最優(yōu)解不組成影響，即不影響最優(yōu)生產(chǎn)計(jì)劃實(shí)施。若當(dāng)前最優(yōu)解不滿足新增加約束，則應(yīng)把新約束添到原問題最優(yōu)表內(nèi)新一行中去，用對(duì)偶單純形方法來進(jìn)行迭代，求出新最優(yōu)解。58/69增加一個(gè)約束條件靈敏度分析舉例例2-11

設(shè)家電Ⅰ，Ⅱ經(jīng)調(diào)試后，還需經(jīng)過一道環(huán)境試驗(yàn)工序。家電Ⅰ每件需環(huán)境試驗(yàn)3h，家電Ⅱ每件需2h，又環(huán)境試驗(yàn)工序天天生產(chǎn)能力為12h。試分析增加該工序后美佳企業(yè)最優(yōu)生產(chǎn)計(jì)劃。（1）檢驗(yàn)原問題最優(yōu)解是否仍適用。將x1=7/2，x2=3/2代入3x1+2x2≤12，27/2>12，所以不適用。（2）加入松弛變量x6，得3x1+2x2+x6=12（3）單純形表求解。59/69靈敏度分析舉例cj→210000CB基bx1x2x3x4x5x60x315/20015/4-15/20①2x17/21001/4-1/20②1x23/2010-1/43/20③0x612320001④cj-zj000-1/4-1/200x315/20015/4-15/20①′2x17/21001/4-1/20②′1x23/2010-1/43/20③′0x6-3/2000-1/4[-3/2]1④′cj-zj000-1/4-1/200x3150015/20-52x141001/30-1/31x20010-1/2010x510001/61-2/3cj-zj000-1/60-1/3注：表中①′②′③′同①②③，④′=④-3×②-2×③。60/69線性規(guī)劃對(duì)偶問題與靈敏度分析線性規(guī)劃對(duì)偶問題對(duì)偶問題基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃61/69參數(shù)線性規(guī)劃當(dāng)目標(biāo)函數(shù)中cj值連續(xù)改變時(shí)，其參數(shù)線性規(guī)劃形式為：當(dāng)約束條件右端項(xiàng)連續(xù)改變時(shí)，其參數(shù)線性規(guī)劃形式為：62/69參數(shù)線性規(guī)劃分析步驟分析步驟：（1）令λ=0求解得最終單純形表；（2）將λC*或λb*項(xiàng)反應(yīng)到最終單純形表中去；（3）隨λ值增大或減小，觀察原問題或?qū)ε紗栴}，一是確定表中現(xiàn)有解（基）允許λ值得變動(dòng)范圍，而是當(dāng)λ值變動(dòng)超出這個(gè)范圍時(shí)，用單純形法或?qū)ε紗渭冃畏ㄇ笕⌒陆猓唬?）重復(fù)（3），一直到λ值繼續(xù)增大或減小時(shí)，表中解（基）不再出現(xiàn)改變時(shí)為止。63/69參數(shù)線性規(guī)劃舉例例2-11

分析λ值改變時(shí)，下述參數(shù)線性規(guī)劃問題最優(yōu)解改變。（1）令λ=0求得最優(yōu)解，并將λC*反應(yīng)到最終單純形表中，得下表。cj→2+λ