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

1、運(yùn) 籌 學(xué)“運(yùn)籌學(xué)”課題組本章內(nèi)容重點(diǎn) 2.1 線性規(guī)劃的對(duì)偶理論2.2對(duì)偶單純形法2.3靈敏度分析第二章 線性規(guī)劃的對(duì)偶理論與靈敏度分析2.1 線性規(guī)劃的對(duì)偶理論一、對(duì)偶問題的提出 對(duì)偶理論是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃（LP）必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，即任何一個(gè)求maxZ的LP都有一個(gè)求minW的LP。其中的一個(gè)問題叫“原問題”，記為“LP”，另一個(gè)稱為“對(duì)偶問題”，記為“DP”。第二章 線性規(guī)劃的對(duì)偶理論與靈敏度分析例2.1 資源的合理利用問題 某工廠在計(jì)劃期內(nèi)安排生產(chǎn)、兩種產(chǎn)品，已知資料如表2.1所示，問應(yīng)如何安排生產(chǎn)計(jì)劃使得既能充分利用現(xiàn)有資源有使總利

2、潤最大？表2.1 III資源總量原材料2 3 24 工時(shí)52 26 利潤(元)4 3 假設(shè) x1、x2分別表示在計(jì)劃期內(nèi)生產(chǎn)產(chǎn)品I、II的件數(shù)，其數(shù)學(xué)模型為： 現(xiàn)從另一角度考慮此問題。假設(shè)有客戶提出要求，租賃工廠的工時(shí)和購買工廠的材料，為其加工生產(chǎn)別的產(chǎn)品，由客戶支付工時(shí)費(fèi)和材料費(fèi)，此時(shí)工廠應(yīng)考慮如何為每種資源定價(jià)，同樣使其獲得的利潤最大？分析問題：1、每種資源定價(jià)不能低于自己生產(chǎn)時(shí)的可獲利潤；2、定價(jià)又不能太高，要使對(duì)方能夠接受解: 1)決策變量：設(shè)y1，y2分別表示出售單位原材料的價(jià)格（含附加值）和出租設(shè)備單位工時(shí)的租金。 2）目標(biāo)函數(shù)：此時(shí)工廠的總收入為 ，這也是租賃方需要付出的成本。而

3、在這個(gè)問題中，是企業(yè)不生產(chǎn)，將自己的資源出售或出租，因此，此時(shí)起決定作用的是租賃方，所以此時(shí)的目標(biāo)函數(shù)為 3)約束條件:工廠決策者考慮： （1）出售原材料和出租設(shè)備應(yīng)不少于自己生產(chǎn)產(chǎn)品的獲利，否則不如自己生產(chǎn)為好。因此有： （2）價(jià)格應(yīng)盡量低，否則沒有競爭力（此價(jià)格可成為與客戶談判的底價(jià)）。租賃者考慮：希望價(jià)格越低越好，否則另找他人。 于是，能夠使雙方共同接受的是： 上述兩個(gè)LP問題的數(shù)學(xué)模型是在同一企業(yè)的資源狀況和生產(chǎn)條件下產(chǎn)生的，且是同一個(gè)問題從不同角度考慮所產(chǎn)生的，因此兩者密切相關(guān)。稱這兩個(gè)LP問題是互為對(duì)偶的兩個(gè)LP問題。其中一個(gè)是另一個(gè)問題的對(duì)偶問題。 模型對(duì)比：（原問題） （對(duì)偶問

4、題） 一般地對(duì)于任何一個(gè)線性規(guī)劃問題都有一個(gè)與之相對(duì)應(yīng)的對(duì)偶問題。原問題與對(duì)偶問題的一般形式為：原問題（LP） 對(duì)偶問題（DP） 相應(yīng)的矩陣形式為：原問題（LP） 對(duì)偶問題（DP） 二、對(duì)偶理論1、原問題與對(duì)偶問題的關(guān)系 對(duì)稱形式的對(duì)偶問題為：原問題（LP） 對(duì)偶問題（DP） 由以上兩式可知，原問題與對(duì)偶問題之間具有如下關(guān)系：(1) 原問題中的約束條件個(gè)數(shù)等于它的對(duì)偶問題中的變量數(shù)；(2) 原問題中目標(biāo)函數(shù)的系數(shù)是其對(duì)偶問題中約束條件的右端項(xiàng)；(3) 約束條件在原問題中為“”，則在其對(duì)偶問題中為“”；(4) 目標(biāo)函數(shù)在原問題中為求最大值，在其對(duì)偶問題中則為求最小值。例2.2 寫出下述線性規(guī)劃問

5、題的對(duì)偶問題解：按照上述規(guī)則，該問題的對(duì)偶線性規(guī)劃為: 當(dāng)線性規(guī)劃的約束條件為等式約束時(shí)，原問題與其對(duì)偶問題之間的變量關(guān)系就是非對(duì)稱形式的對(duì)偶關(guān)系。此時(shí)，原問題為:對(duì)偶問題為:該對(duì)偶問題的特點(diǎn)是：對(duì)偶變量符號(hào)不限，系數(shù)矩陣為原問題系數(shù)矩陣的轉(zhuǎn)置矩陣。 根據(jù)上述實(shí)例計(jì)算結(jié)果，考慮可能出現(xiàn)的各種情況，歸納出原問題與對(duì)偶問題之間的關(guān)系，可以用表2.2表示。表2.2 原問題與對(duì)偶問題的關(guān)系原問題Max（對(duì)偶問題） 對(duì)偶問題Min（原問題） 約束條件數(shù)=m 變量個(gè)數(shù)=m 第i個(gè)約束條件為“”第i個(gè)約束條件為“”第i個(gè)約束條件為“=” 第i個(gè)變量0第i個(gè)變量0第i個(gè)變量無限制 變量個(gè)數(shù)=n 約束條件個(gè)數(shù)=

6、n 第i個(gè)變量0第i個(gè)變量0第i個(gè)變量無限制 第i個(gè)約束條件為“”第i個(gè)約束條件為“”第i個(gè)約束條件為“=” 第i個(gè)約束條件的右端項(xiàng)目標(biāo)函第i個(gè)變量的系數(shù) 目標(biāo)函數(shù)第i個(gè)變量的系數(shù)第i個(gè)約束條件的右端項(xiàng) 例2.3 寫出下述線性規(guī)劃問題的對(duì)偶問題按照表2.2將線性規(guī)劃問題化為對(duì)偶問題2、對(duì)偶問題的基本定理原問題（LP） 對(duì)偶問題（DP） （1）（對(duì)稱性）對(duì)偶問題的對(duì)偶是原問題。 證：設(shè)原問題是 其對(duì)偶問題為 若將上式兩邊取負(fù)號(hào)，又因?yàn)?可得到又因?yàn)榭傻眠@就是原問題。根據(jù)對(duì)稱變換關(guān)系，上式的對(duì)偶問題是（2）（弱對(duì)偶定理）若X(0)是原問題的可行解，Y(0)是對(duì)偶問題的可行解，則有C X(0)Y(0

7、)b。證：設(shè)原問題是 因 是原問題的可行解，所以滿足約束條件，即 若是給定的一組值，設(shè)它是對(duì)偶問題的可行解，將 左乘上式，得到原問題的對(duì)偶問題是因?yàn)槭菍?duì)偶問題的可行解，所以滿足將右乘上式，得到（3）（無界性）若原問題（對(duì)偶問題）為無界解，則其對(duì)偶問題（原問題）無可行解。證：由弱對(duì)偶性顯然得。 注意這個(gè)問題的性質(zhì)不存在逆。當(dāng)原問題（對(duì)偶問題）無可行解時(shí)，其對(duì)偶問題（原問題）或具有無界解或無可行解。4）（最優(yōu)性定理），若X(0)、Y(0)分別是互為對(duì)偶問題的可行解，且C X(0) = Y(0) b，則X(0)、Y(0)分別是它們的最優(yōu)解。 證：若 ，根據(jù)性質(zhì)2知 ，對(duì)偶問題的所有可行解Y都存在 ，

8、因?yàn)?，所以 ，可見 是使目標(biāo)函數(shù)取值最小的可行解，因而是最優(yōu)解。同樣可以證明：對(duì)于原問題的所有可行解X，存在 ，所以 是最優(yōu)解。（5）（強(qiáng)對(duì)偶定理）若互為對(duì)偶問題之一有最優(yōu)解，則另一問題必有最優(yōu)解，且它們的目標(biāo)函數(shù)值相等。 從上述性質(zhì)中，可看到原問題與對(duì)偶問題的解必然是下列三種情況之一：原問題與對(duì)偶問題都有最優(yōu)解，且CX=Yb；一個(gè)問題具有無界解，則它的對(duì)偶問題無可行解；兩個(gè)問題均無可行解。（6）（互補(bǔ)松馳性）若X*、Y*分別是原問題和對(duì)偶問題的可行解，則X*、Y*是最優(yōu)解的充要條件是： Y*XS=0,YSX*=0(其中XS，YS分別是原問題和對(duì)偶問題的松馳變量向量)。證明：設(shè)原問題和對(duì)偶問

9、題的標(biāo)準(zhǔn)型是 原問題 對(duì)偶問題 將原問題目標(biāo)函數(shù)中的系數(shù)向量C用 代替后，得到 將對(duì)偶問題的目標(biāo)函數(shù)中的系數(shù)向量，用 代替后，得到 若 ；則 故 是最優(yōu)解。 又若 分別是原問題和對(duì)偶問題的最優(yōu)解，則必有 由 ，我們可以得到如下結(jié)論：（1） 若對(duì)偶變量值不等于零，則其對(duì)應(yīng)的原問題約束方程中的松弛變量必定為0，也即該約束方程取嚴(yán)格等式。（2） 若原問題中某個(gè)松弛變量不等于零，則對(duì)應(yīng)的對(duì)偶問題中的變量必定為0。 由 ，我們可以得到如下結(jié)論：（1） 若對(duì)偶問題中某個(gè)剩余變量不等于零，則對(duì)應(yīng)的原問題中的變量必定為0。（2） 若原問題的變量值不等于零，則其對(duì)偶問題中對(duì)應(yīng)的松弛變量必定為0，也即對(duì)偶問題中該

10、約束方程取嚴(yán)格等式。 一般而言，我們把某一可行點(diǎn)（如X*和Y*）處的嚴(yán)格不等式約束（包括對(duì)變量的非負(fù)約束）稱為松約束，而把嚴(yán)格等式約束稱為緊約束。所以有如下結(jié)論： 設(shè)一對(duì)對(duì)偶問題都有可行解，若原問題的某一約束是某個(gè)最優(yōu)解的松約束，則它的對(duì)偶約束一定是其對(duì)偶問題最優(yōu)解的緊約束。例2.5 已知 試通過求對(duì)偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對(duì)偶問題為 用圖解法可求得對(duì)偶問題的最優(yōu)解：Y*=（1，3），W=11。 將代入對(duì)偶約束條件，（1），（2），（5）式為緊約束，（3），（4）為松約束。 令原問題的最優(yōu)解為X* = （x1，x2，x3，x4，x5），則根據(jù)互補(bǔ)松弛條件，必有x3 = x4 =

11、0化簡為又由于，原問題的約束必為等式，即 此方程組為無窮多解 令x5 =0,得到x1=1，x2=2， 即X*1 =（1，2，0，0，0）為原問題的一個(gè)最優(yōu)解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0，即X*2（5/3，0，0，0，2/3）也是原問題的一個(gè)最優(yōu)解，Z=11。三、對(duì)偶問題的經(jīng)濟(jì)解釋影子價(jià)格1、影子價(jià)格 在一對(duì)LP和DP中，若LP的某個(gè)約束條件的右端項(xiàng)常數(shù)bi增加一個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值Z*的改變量稱為第i個(gè)約束條件的影子價(jià)格，又稱為邊際價(jià)格。 設(shè)：B是問題LP的最優(yōu)基，由前式可知， 當(dāng)bi變?yōu)閎i+1時(shí)（其余右端項(xiàng)不變，也不影響 B），則目標(biāo)函數(shù)最優(yōu)值

12、變?yōu)椋核杂幸部梢詫懗桑杭幢硎綵*對(duì)bi的變化率。其經(jīng)濟(jì)意義是： 在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即對(duì)偶變量yi就是第 i 個(gè)約束條件的影子價(jià)格。 影子價(jià)格是在最優(yōu)決策下對(duì)資源的一種估價(jià)，沒有最優(yōu)決策就沒有影子價(jià)格，所以影子價(jià)格又稱“最優(yōu)計(jì)劃價(jià)格”，“預(yù)測價(jià)格”等等。 資源的影子價(jià)格定量的反映了單位資源在最優(yōu)生產(chǎn)方案中為總收益所做出的貢獻(xiàn)，因此，資源的影子價(jià)格也可稱為在最優(yōu)方案中投入生產(chǎn)的機(jī)會(huì)成本。 也可以理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù)（但問題中所有其它數(shù)據(jù)都保持不變）。 若第i 種資源的單位市場價(jià)格為mi，當(dāng)yi mi時(shí)，企業(yè)愿意購進(jìn)這種資源，單位

13、純利為yimi，則有利可圖； 如果yi 0，說明該資源已耗盡，成為短線資源 影子價(jià)格=0，說明該資源有剩余，成為長線資源（3）可以預(yù)測產(chǎn)品的價(jià)格 產(chǎn)品的機(jī)會(huì)成本為CBB-1A-C，只有當(dāng)產(chǎn)品價(jià)格定在機(jī)會(huì)成本之上，企業(yè)才有利可圖。 （2）對(duì)市場資源的最優(yōu)配置起著推進(jìn)作用 即在配置資源時(shí)，對(duì)于影子價(jià)格大的企業(yè)，資源優(yōu)先供給（4）可作為同類企業(yè)經(jīng)濟(jì)效益評(píng)估指標(biāo)之一。 對(duì)于資源影子價(jià)格越大的企業(yè)，資源的利用所帶來的收益就越大，經(jīng)濟(jì)效益就越好。 通過以上討論可知： 只有某資源對(duì)偶解大于0，該資源才有利可圖，可增加此種資源量；若某資源對(duì)偶解為0，則不增加此種資源量。 直接用影子價(jià)格與市場價(jià)格相比較，進(jìn)行決

14、策，是否買入該資源。 對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法的原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。 不要簡單理解為是求解對(duì)偶問題的單純形法。2.2 對(duì)偶單純形法 求解原問題（LP）時(shí)，可以從（LP）的一個(gè)基本解（非基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值（Z=Y b= CB B-1b =CX）減少，當(dāng)?shù)絏B=B-1b0時(shí)，即找到了（LP）的最優(yōu)解，這就是對(duì)偶單純形法。 因此，單純形法是在保持原始可行下，經(jīng)過迭代，逐步實(shí)現(xiàn)對(duì)偶可行，達(dá)到求出最優(yōu)解的過程。1. 單純形法的重新解釋 設(shè)X*是最大化LP問題最優(yōu)解的充要條件是同時(shí)滿足 根據(jù)對(duì)偶問題的對(duì)稱性，也可以在

15、保持對(duì)偶可行下，經(jīng)過迭代，逐步實(shí)現(xiàn)原始可行，以求得最優(yōu)解。對(duì)偶單純形法就是根據(jù)這種思想所設(shè)計(jì)的。 因此對(duì)偶單純形是先保證現(xiàn)行解對(duì)對(duì)偶問題可行，即 ，然后從 迭代到 。對(duì)偶單純形的計(jì)算步驟：（1）根據(jù)線性規(guī)劃問題，列出初始單純形表。 檢查b列的數(shù)字，若都為非負(fù)，且檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解，停止計(jì)算。 若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，轉(zhuǎn)（2）；（3）確定換入變量 在單純形表中檢查所在的行的系數(shù) ， 若所有的 ，則無可行解，停止計(jì)算。 若存在 ，計(jì)算（2）確定換出變量 按 對(duì)應(yīng)的基變量為換出變量； 按規(guī)則，所對(duì)應(yīng)的列變量的非基變量為換入變量；（4）以 為主元素，按單純形

16、法進(jìn)行換基迭代，得到新的單純形表； 重復(fù)（1）（4）的步驟進(jìn)行計(jì)算。例2.7 用對(duì)偶單純形法求解：解：將模型轉(zhuǎn)化為cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-50010-9-12-15000表24 從表24可以看出，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問題的是可行的，因b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。 換出變量的確定：按上述對(duì)偶單純形計(jì)算步驟（2），計(jì)算 故 為換出變量。 故 為換入變量。換入、換出變量所在列、行的交叉處的元素為主元素。 按單純形法計(jì)算步驟進(jìn)行迭代，得表25換入變量的確定： 按上述對(duì)偶單純形計(jì)

17、算步驟（3），計(jì)算表25 cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-7.2-1.8-1.8010-0.20 x5-9.2-1.8-2.8001-0.2-15x32.80.20.2100-0.242-6-9000-3重復(fù)以上步驟得表26、表27cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14501/7-3/14000-5/1433/14表26 表27 cj-9-12-15000CBxBbx1x2x3x4x5

18、x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/972000-1/3-3-7/3所以，X*=（2，2，2，0，0，0）， =72 原問題 Z* =72。 通過上面的例子，可以看出對(duì)偶單純形方法與一般單純形方法的區(qū)別：（1）單純形表。 一般單純形表始終保持基本可行解，而對(duì)偶單純形表先保持對(duì)偶解可行，原問題的解不可行。（2）換基迭代過程。 一般單純形方法先確定換入基變量，后確定換出基變量。對(duì)偶單純形方法反過來，先確定換出基變量，后確定換入基變量。（3）換出基變量的確定規(guī)則。 一般單純形方法是以最大檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量作為換出基變量，然后將已得到的基變

19、量的值與換入基變量所在的列的正分量相除，以最小比值對(duì)應(yīng)的基變量作為換出基變量。 在對(duì)偶單純形求解時(shí)，以基變量的負(fù)值中最小的對(duì)應(yīng)的為換出基變量，將檢驗(yàn)數(shù)與換出基變量所在行的負(fù)分量相除，然后選取最小比值對(duì)應(yīng)的非基變量為換入基變量。（4）最優(yōu)解的判別標(biāo)準(zhǔn)。 一般單純形最優(yōu)解的判別標(biāo)準(zhǔn)為 對(duì)偶單純形最優(yōu)解的判別標(biāo)準(zhǔn)為對(duì)偶單純形的優(yōu)點(diǎn)與用途：（1）初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都是負(fù)數(shù)時(shí)，就可以進(jìn)行基變換，這樣避免了增加人工變量，使運(yùn)算簡便。（2）對(duì)變量較少時(shí)，而約束條件很多的線性規(guī)劃問題，可先將其變?yōu)閷?duì)偶問題，再用對(duì)偶單純形求解，簡化計(jì)算。（3）用于后面的靈敏度分析。 最后提醒一下： 對(duì)偶單純形方法不

20、能理解為是求解對(duì)偶問題的方法，相反它卻是求解原問題最優(yōu)解的有效工具。2.3 靈敏度分析 在前面的線性規(guī)劃問題討論中，都是假定為常數(shù)，但實(shí)際工作中這些系數(shù)往往是估計(jì)值和預(yù)測值。 如市場條件發(fā)生變化，價(jià)值系數(shù)就會(huì)發(fā)生變化； 當(dāng)資源投入量發(fā)生改變時(shí)，也隨著發(fā)生變化； 因此當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解會(huì)有什么變化？ 或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的最優(yōu)解不發(fā)生變化。因此我們?cè)谶M(jìn)行靈敏度分析時(shí)，要弄清楚：1）系數(shù)在什么范圍內(nèi)變化時(shí)，最優(yōu)解（基）不變；2）若系數(shù)的變化使最優(yōu)解發(fā)生變化，如何最簡便地求得新的最優(yōu)解ABC資源量甲11112乙12220利潤586問

21、：如何安排產(chǎn)品產(chǎn)量，可獲最大利潤？表2.12下面分別就各個(gè)參數(shù)改變后的情形進(jìn)行討論。例2.9 已知某企業(yè)計(jì)劃生產(chǎn)3種產(chǎn)品A、B、C，其資源消耗與利潤如表2.12所示解：設(shè)三種產(chǎn)品的產(chǎn)量分別為x1、x2、x3其數(shù)學(xué)模型的標(biāo)準(zhǔn)型為該問題的初始單純形表如表2.14所示58600XBbx1x2x3x4x50 x412111100 x52012201058600表2.14經(jīng)過計(jì)算得最優(yōu)表如表2.1558600XBbx1x2x3x4x55x141002-18x28011-11Z8400-2-2-3這時(shí)最優(yōu)方案為 X=(4,8,0)T,目標(biāo)值為84表2.151.目標(biāo)函數(shù)中的價(jià)值系數(shù)Cj的靈敏度分析（1）非基

22、變量的價(jià)值系數(shù)的靈敏度分析 由于檢驗(yàn)數(shù) j= cj CBB-1 Pj，因此 cj 的改變，只使檢驗(yàn)數(shù) j 發(fā)生改變，其它不變。 如果 cj的改變，檢驗(yàn)數(shù) j仍小于零時(shí)，這時(shí)對(duì)最優(yōu)解方案沒有影響。 在例2.9中，如果改變 c3 ，使 原最優(yōu)方案不發(fā)生改變。若改變?yōu)?0時(shí)， ，這時(shí)原方案已不是最優(yōu)方案。這時(shí)單純形表變?yōu)楸?.16581000XBbx1x2x3x4x55x141002-18x28011-11Z84002-2-3表2.16581000XBbx1x2x3x4x55x141002-110 x38011-11Z1000-200-5表2.17 單位產(chǎn)品C3的利潤為10時(shí)，則最優(yōu)方案調(diào)整為 X=

23、(4,0,8)T,目標(biāo)值為100。（2）基變量的價(jià)值系數(shù) Cj 的靈敏度分析如果cj的改變，使全部檢驗(yàn)數(shù)j仍小于零時(shí)，這時(shí)對(duì)最優(yōu)解方案沒有影響，但對(duì)最優(yōu)值發(fā)生改變。在例2.9中，如果c1改變，使即 解得 ， 這時(shí)原最優(yōu)方案不發(fā)生改變。即單位產(chǎn)品A的利潤在4,8之間變化時(shí),最優(yōu)方案不變，但最優(yōu)值為 。若改變?yōu)?0時(shí)， ，這時(shí)需要換基迭代。這時(shí)原方案已不是最優(yōu)方案。這時(shí)單純形表變?yōu)楸?.18108600XBbx1x2x3x4x510 x141002-18x28011-11Z10400-2-122表2.18表2.19108600XBbx1x2x3x4x510 x112111100 x58011-11

24、Z1200-2-4-100單位產(chǎn)品A的利潤為10時(shí)，則最優(yōu)方案調(diào)整為 X=(12,0,0)T,目標(biāo)值為120。2、資源約束數(shù)量b的靈敏度分析從矩陣形式的單純形表中可以看出，b的變化只影響最優(yōu)解的變化和最優(yōu)值的變化。bXXBB-1bB-1AZ-C BB-1bC-C BB-1A 因此，當(dāng) 時(shí)，最優(yōu)基不變（即生產(chǎn)產(chǎn)品的品種不變，但數(shù)量及最優(yōu)值會(huì)變化）。 是一個(gè)不等式組，從中可以解得b的變化范圍，若 B-1b中有小于0的分量，則需用對(duì)偶單純形法迭代，以求出新的最優(yōu)方案。（1） 若 的改變，使 時(shí)，最優(yōu)方案不變。在例2.9中，如果 改變，則 解得 即原料甲的供應(yīng)量在10，20之間時(shí)并不影響最優(yōu)方案。當(dāng)

25、時(shí)，最優(yōu)方案調(diào)整為 X=(16,2,0)T,目標(biāo)值為96。（2）若改變?yōu)?0時(shí)表2.2058600XBbx1x2x3x4x55x1401002-18x2-10011-11-Z-12000-2-2-3利用對(duì)偶單純形法可解得58600XBbx1x2x3x4x55x120122010 x4100-1-11-1-Z-1000-2-40-5原料甲的供應(yīng)為30，則最優(yōu)方案調(diào)整為 X=(20,0,0)T,目標(biāo)值為100。表2.213、添加新變量的靈敏度分析 在例2.9中，若新開發(fā)新產(chǎn)品D，該單位產(chǎn)品需要消耗原材料甲：3個(gè)單位，乙：2個(gè)單位，可以得利潤10。 問：投產(chǎn)產(chǎn)品D是否有利？因此最優(yōu)方案不變。投產(chǎn)產(chǎn)品

26、D無利。（1）產(chǎn)品D的利潤為多少時(shí)，投產(chǎn)產(chǎn)品D有利？只有 時(shí)， 才能進(jìn)入基，也就是說產(chǎn)品D才能生產(chǎn)，這時(shí)解得 。即當(dāng) 時(shí)，投產(chǎn)產(chǎn)品D才有利。（2）當(dāng) 時(shí)，表2.225860015XBbx1x2x3x4x5x65x141002-148x28011-11-1-Z-8400-2-2-33表2.235860015XBbx1x2x3x4x5x615x611/400-1/2-1/418x291/411-1/23/40-Z-87-3/40-2-7/2-9/40單位產(chǎn)品D的利潤為15時(shí)，這時(shí)生產(chǎn)方案為： 生產(chǎn) B產(chǎn) 品 9件 ， 生產(chǎn)D產(chǎn)品1件。目標(biāo)值為87。4、添加新約束的靈敏度分析 在例2.9中，假設(shè)電力

27、供應(yīng)緊張，若電力供應(yīng)最多為13單位，而生產(chǎn)產(chǎn)品A、 B、C每單位需電力分別為2、1、3個(gè)單位問該公司生產(chǎn)方案是否需要改變？解：先將原問題的最優(yōu)解x14，x28，x30代入電力約束條件2x1+x2+3x313 因?yàn)?2+8=1613 ，故原問題最優(yōu)解已經(jīng)不是新約束條件下的最優(yōu)解。 在電力約束條件中加入松弛變量得2x1+x2+3x3x613 以x6為基變量，將上式反映到最終單純形表中得到表2.24表2.24586000XBbx1x2x3x4x5x65x141002-108x28011-1100 x613213001-Z-8400-2-2-30在表2.24中，x1、x2、x6為基變量，因此所對(duì)應(yīng)的列

28、向量應(yīng)為單位向量，因此經(jīng)計(jì)算得表2.25。586000XBbx1x2x3x4x5x65x141002-108x28011-1100 x6-3002-311-Z-8400-2-2-30表2.25利用對(duì)偶單純形法計(jì)算得表2.26586000XBbx1x2x3x4x5x65x12104/30-1/32/38x29011/302/3-1/30 x4100-2/31-1/3-1/3-Z-8200-10/30-11/3-2/3增加電力約束后，這時(shí)生產(chǎn)方案為：生產(chǎn)A產(chǎn)品1件，生產(chǎn) B產(chǎn) 品 9件。目標(biāo)值為82。表2.265、技術(shù)系數(shù)改變(計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)發(fā)生改變)（1）非基變量的工藝發(fā)生改變 當(dāng) 是非基變量 的系數(shù)時(shí)，它的變化不會(huì)改變 ,它只影響單純形表 列，只是對(duì)檢驗(yàn)數(shù)有影