第3章 對(duì)偶理論及靈敏度分析

1、第 3 3 章線性規(guī)劃的對(duì)偶理論及靈敏度分析 BY 蔡連僑蔡連僑北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-2如果企業(yè)考慮把設(shè)備等資源出租，應(yīng)該如何定租金，才能保證出租是合算的增加資金投入，應(yīng)該如何進(jìn)行合理分配在目前的生產(chǎn)計(jì)劃情況下，如果產(chǎn)品價(jià)格發(fā)生變化，對(duì)生產(chǎn)計(jì)劃是否有影響，采用新工藝對(duì)生產(chǎn)計(jì)劃又有什么影響為了增加產(chǎn)量，需要再購(gòu)買(mǎi)原材料，多高的價(jià)格是可以接受的（即采購(gòu)后可增加產(chǎn)量，也能增加利潤(rùn)）采購(gòu)原材料后對(duì)生產(chǎn)計(jì)劃有什么影響北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-3線性規(guī)劃的對(duì)偶問(wèn)題(Dual Problem)線性規(guī)劃的對(duì)偶單純形法(Dual Simplex

2、 Method)線性規(guī)劃的靈敏度分析(Sensitivity Analysis)參數(shù)線性規(guī)劃(Parametric Linear Programming)北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-4對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的形式對(duì)偶問(wèn)題的基本性質(zhì)影子價(jià)格北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-5 例1（同第2章例1）：某工廠擁有A、B、C三種類(lèi)型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示： 問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）15002500

3、北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-6 可以建立如下的線性規(guī)劃模型： 目標(biāo)函數(shù) Max z =1500 x1+2500 x2 約束條件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1, x2 0 化為標(biāo)準(zhǔn)型，利用單純形法進(jìn)行求解，得到最優(yōu)解X=(5, 25, 0, 5, 0)T，最優(yōu)值（利潤(rùn)）為70000。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-7最優(yōu)解 x1 = 5 x2 = 25 x4 = 5（松弛標(biāo)量，表示B設(shè)備有5個(gè)機(jī)時(shí)的剩余）， 最優(yōu)值 z* = 70000 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-8 現(xiàn)在從另一個(gè)角度來(lái)討論該問(wèn)題：如果工廠考慮不安排生產(chǎn)，而準(zhǔn)備把所

4、有設(shè)備出租（或用于外協(xié)加工），工廠收取租金（或加工費(fèi)）。試問(wèn)：設(shè)備 A、B、C 每工時(shí)各如何收費(fèi)（租金或加工費(fèi)）才最有競(jìng)爭(zhēng)力？ 工廠為了獲得最大利潤(rùn)，在為設(shè)備定價(jià)時(shí)，應(yīng)保證生產(chǎn)某產(chǎn)品的設(shè)備工時(shí)所收取的費(fèi)用不低于生產(chǎn)該產(chǎn)品的利潤(rùn)；同時(shí)，為了提高競(jìng)爭(zhēng)力，應(yīng)該使定價(jià)盡可能低北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-9 設(shè) y1 ，y2 ，y3 分別為每工時(shí)設(shè)備 A、B、C 的收費(fèi)?？梢越⒁韵戮€性規(guī)劃模型： Min f = 65 y1 + 40 y2 + 75 y3 s.t. 3 y1 + 2 y2 1500 （不少于甲產(chǎn)品的利潤(rùn)） 2 y1 + y2 + 3 y3 2500 （不少于乙產(chǎn)品的利潤(rùn)） y1,

5、 y2 , y3 0化為標(biāo)準(zhǔn)型，利用單純形法進(jìn)行求解，得到最優(yōu)解Y=(500, 0, 500, 0, 0)T，最優(yōu)值（收費(fèi)）為70000。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-10最優(yōu)解 y1 = 500 y3 = 500， 最優(yōu)值 f* = 70000 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-11 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 65 2 x1 + x2 40 原問(wèn)題原問(wèn)題 3 x2 75 x1 , x2 0 Min f = 65 y1 + 40 y2 + 75 y3 s.t. 3 y1 + 2 y2 1500 2 y1 + y2 + 3 y3 2

6、500 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 y1, y2 , y3 0北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-12可以看到，這兩個(gè)問(wèn)題關(guān)系密切，用同樣的原始數(shù)據(jù)目標(biāo)函數(shù)MaxMin約束條件系數(shù)矩陣AAT資源常數(shù)bc目標(biāo)系數(shù)cb 2個(gè)變量2個(gè)約束 3個(gè)約束3個(gè)變量 解檢驗(yàn)數(shù) 檢驗(yàn)數(shù)解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-13線性規(guī)劃有一個(gè)有趣的特性，就是對(duì)于任何一個(gè)求極大的線性規(guī)劃問(wèn)題都存在一個(gè)與其匹配的求極小的線性規(guī)劃問(wèn)題，并且這一對(duì)線性規(guī)劃問(wèn)題的解之間還存在著密切的關(guān)系。線性規(guī)劃的這個(gè)特性稱(chēng)為對(duì)偶性對(duì)這兩個(gè)線性規(guī)劃問(wèn)題，一般稱(chēng)前者為原問(wèn)題，后者是前者的對(duì)偶問(wèn)題北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-14對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題

7、的形式對(duì)偶問(wèn)題的基本性質(zhì)影子價(jià)格北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-15如果線性規(guī)劃問(wèn)題的變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時(shí)均取“”，當(dāng)目標(biāo)函數(shù)求極小時(shí)均取“”，則稱(chēng)具有對(duì)稱(chēng)形式對(duì)稱(chēng)形式下原問(wèn)題和對(duì)偶問(wèn)題的形式 (LP) Max z = CX (DP) Min f = YTb s.t. AX b s.t. ATY CT X 0 Y 0 “Max - ” “Min- ”北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-16一對(duì)對(duì)稱(chēng)形式的對(duì)偶規(guī)劃之間具有下面的對(duì)應(yīng)關(guān)系若一個(gè)模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對(duì)偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，”和“m

8、in，”相對(duì)應(yīng)從約束系數(shù)矩陣看：一個(gè)模型中為，則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型中，b和C的位置對(duì)換兩個(gè)規(guī)劃模型中的變量皆非負(fù)北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-17把對(duì)稱(chēng)形式的對(duì)偶規(guī)劃之間的對(duì)應(yīng)關(guān)系表示在表中Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2ymam1am2amnbmyi 0c1c2cn北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-18對(duì)偶問(wèn)題的對(duì)偶即是原問(wèn)題(DP) Min f = YTb s.t. ATY CT Y 0 (LP) Max f = -YTb s

9、.t. - ATY - CT Y 0 (DP) Min z = - CX s.t. - AX - b X 0 (LP) Max z = CX s.t. AX b X 0 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-19一般稱(chēng)不具有對(duì)稱(chēng)形式的一對(duì)線性規(guī)劃為非對(duì)稱(chēng)形式的對(duì)偶規(guī)劃對(duì)于非對(duì)稱(chēng)形式的規(guī)劃，可以按照下面的對(duì)應(yīng)關(guān)系進(jìn)行處理并給出其對(duì)偶規(guī)劃將模型統(tǒng)一為“max，”或“min，” 的形式，對(duì)于其中的等式約束按下面的方法處理若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒(méi)有非負(fù)限制若原規(guī)劃的某個(gè)變量的值沒(méi)有非負(fù)限制，則在對(duì)偶問(wèn)題中與此變量對(duì)應(yīng)的那個(gè)約束為等式也可以直接給出其對(duì)偶規(guī)

10、劃北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-20例2：寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃模型 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 沒(méi)有非負(fù)限制北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-21解：先化為對(duì)稱(chēng)形式（Max）“”的約束兩端同乘以“1”“=”的約束等價(jià)轉(zhuǎn)換為“”和“”的兩個(gè)約束，再變換變量0，用變量替換，如 x2 = x2 變量無(wú)非負(fù)限制，用變量替換，如 x3 = x3 x3” Max z = x1 4 x2 + 3 x3 3 x3” s.t. 2 x1 3

11、 x2 5 x3 + 5 x3” 2 3 x1 x2 6 x3 + 6 x3” 1 x1 x2 + x3 x3” 4 x1 + x2 x3 + x3” 4 x1，x2，x3 ，x3” 0北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-22寫(xiě)出對(duì)偶問(wèn)題 Min f = 2 y1 y2 + 4 y3 4 y3” s.t. 2 y1 3 y2 + y3 y3” 1 3 y1 y2 y3 + y3” 4 5 y1 6 y2 + y3 y3” 3 5 y1 + 6 y2 y3 + y3” 3 y1，y2，y3 ，y3” 0北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-23變量替換，令y2 = y2 ，y3 = y3 y3” Mi

12、n f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1 3 y1 y2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3 無(wú)非負(fù)限制北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-24把對(duì)偶問(wèn)題和原問(wèn)題進(jìn)行比較 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2原問(wèn)題 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 沒(méi)有非負(fù)限制 Min f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1對(duì)偶問(wèn)題 3 y1 y

13、2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3無(wú)非負(fù)限制北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-25 由此得到非對(duì)稱(chēng)形式的線性規(guī)劃原問(wèn)題和對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系（對(duì)稱(chēng)形式也適用）原問(wèn)題對(duì)偶問(wèn)題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件右端項(xiàng)目標(biāo)函數(shù)中的系數(shù)C目標(biāo)函數(shù)中的系數(shù)約束條件右端項(xiàng)目標(biāo)函數(shù)Max z = cj xjMin f = bi yi變量n個(gè) xj 0(0，無(wú)限制)約束條件n個(gè)aij yj(，=)cj約束條件m個(gè)aij xj(，=)bi變量m個(gè) yi0(0，無(wú)限制)北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-26例3：寫(xiě)出下面線性規(guī)劃的對(duì)偶問(wèn)題 Max z =

14、x1 x2 + 5 x3 7 x4 s.t. x1 + 3 x2 2 x3 + x4 = 25原問(wèn)題 2 x1 7 x3 + 2 x4 60 2 x1 + 2 x2 4 x3 30 5 x4 10 ，x1，x2 0 ，x3 沒(méi)有非負(fù)限制 Min f = 25 y1 60 y2 + 30 y3 5 y4 + 10 y5 s.t. y1 + 2 y2 + 2 y3 1對(duì)偶問(wèn)題 3 y1 + 2 y3 1 2 y1 7 y2 4 y3 = 5 y1 + 2 y2 + y4 + y5 = 7 y1無(wú)非負(fù)限制， y2， y4 0 ， y3， y5 0 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-27例：寫(xiě)出下面運(yùn)

15、輸問(wèn)題的對(duì)偶問(wèn)題njmixnjdxmisxtsxcwMinijjmiijinjijminjijij, 2 , 1;, 2 , 10, 2 , 1, 2 , 1. .1111北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-28對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的形式對(duì)偶問(wèn)題的基本性質(zhì)影子價(jià)格北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-29對(duì)偶問(wèn)題的基本性質(zhì)對(duì)對(duì)稱(chēng)形式和非對(duì)稱(chēng)形式都是同樣適用的，但為了方便，在說(shuō)明或證明時(shí)以對(duì)稱(chēng)形式為例（非對(duì)稱(chēng)形式可以化為對(duì)稱(chēng)形式）對(duì)稱(chēng)形式下原(Primal)問(wèn)題和對(duì)偶(Dual)問(wèn)題如下 (P) Max z = CX (D) Min f = YTb s.t. AX b s.t. ATY CT X 0

16、 Y 0 “Max - ” “Min- ”北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-30（弱對(duì)偶定理）若X，Y分別為（P) 和（D）的可行解，那么CX YTb。證明：由變量的非負(fù)性限制，可以得到miiinjjjybxc11 minjijijnjjmiiijnjjjyxaxyaxc11111)( minjijijmiinjjijmiiiyxayxayb11111)(北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-31弱對(duì)偶定理的推論（P）任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；（D）任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界若（P）可行，那么（P）無(wú)有限最優(yōu)解的充分必要條件是（D）無(wú)可行解若（D）可

17、行，那么（D）無(wú)有限最優(yōu)解的充分必要條件是（P）無(wú)可行解若（P）、 （D）可行，那么（P）、 （D）都有最優(yōu)解（P）有最優(yōu)解的充分必要條件是（D）有最優(yōu)解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-32（最優(yōu)性準(zhǔn)則定理）若X，Y分別為(P)，(D)的可行解，且CTX=YTb，則X，Y分別為(P)和(D)的最優(yōu)解證明：設(shè) X 為(P)的可行解，由弱對(duì)偶定理可得 CTX YTb = CTX 因此 X 為(P) 的最優(yōu)解設(shè) Y 為(D)的可行解，由弱對(duì)偶定理可得 YTb CTX = YTb 因此 Y 為(D) 的最優(yōu)解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-33（主對(duì)偶定理）若(P)和(D)均可行，那么(P)和(D

18、)均有最優(yōu)解，且最優(yōu)值相等。證明：若(P)和(D)均可行，則由弱對(duì)偶定理的推論知 (P)和(D)均有最優(yōu)解 設(shè)(P)的最優(yōu)基為B，令YT= CBB-1，由=C - CBB-1A 0，對(duì)于松弛變量部分，目標(biāo)函數(shù)系數(shù)為0，系數(shù)矩陣為單位陣，檢驗(yàn)數(shù)為= - CBB-10，故Y0，且YTAC，ATY CT，因此 Y 為(D)的可行解 目標(biāo)YTb = CBB-1b = CX（原問(wèn)題最優(yōu)值），由最優(yōu)性準(zhǔn)則定理知 Y 為 (D) 的最優(yōu)解注：(P) 松弛變量的檢驗(yàn)數(shù)的絕對(duì)值是(D)的基可行解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-34對(duì)稱(chēng)形式下原問(wèn)題和對(duì)偶問(wèn)題的標(biāo)準(zhǔn)形式如下 （互補(bǔ)松弛定理）若X 和Y 分別是 (

19、P)和(D)的最優(yōu)解（對(duì)稱(chēng)形式的標(biāo)準(zhǔn)型下），則有 即約束取等式或?qū)?yīng)的變量為0), 2 , 1(0), 1(11mnjxmibxxaxczMaxjiinnjjijnjjj), 2 , 1( 0), 1(11mniynjcyyaybfMinijjmmiiijmiii), 1;, 1( 0, 0njmixyyxinijmj北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-35證明：由弱對(duì)偶定理（CXYTb）得 由主對(duì)偶定理可知最優(yōu)值相等，上述不等式取“=”， miiiminjijijnjjjybyxaxc1111 miiinmiinjjijiminjijijmiiiyxyxabyxayb111111)(00, 0

20、,yxyxiinij得由 njjjmnjjjmiiijnjjjminjijijxyxcyaxcyxa111111)(00, 0,yxyxjmjij得由北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-36對(duì)偶問(wèn)題基本性質(zhì)的應(yīng)用利用單純形法，求得對(duì)偶問(wèn)題最優(yōu)解 X=(1, 0, 0, 2, 0)T，最優(yōu)值 z* = 9。由互補(bǔ)松弛定理，得 x1 y3 = 0， x2 y4 = 0，x3 y5 = 0，x4 y1 = 0， x5 y2 =0，因此有 y1 = 0，y3 = 0，代入第1個(gè)約束得到y(tǒng)2 = 9，代入其余約束得 y4 = 4， y5 = 64對(duì)于變量數(shù)量少、約束多的問(wèn)題，可以利用基本性質(zhì)簡(jiǎn)化求解例4：

21、 Min f = 5 y1 + y2 s.t. 3 y1 + y2 9 y1 + y2 5 y1 + 8 y2 8 y1，y2 0 Max z = 9 x1 + 5 x2 + 8 x3 s.t. 3 x1 + x2 + x3 5 x1 + x2 + 8 x3 1 x1， x2， x3 0 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-37對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的形式對(duì)偶問(wèn)題的基本性質(zhì)影子價(jià)格北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-38影子價(jià)格 (Shadow Price) 的概念若X*，Y* 分別為（P）和（D）的最優(yōu)解，則 z = CX* = Y*Tb = f根據(jù) z = b1y1*+b2y2*+bmym*

22、可知 z / bi = yi* 其中bi表示第 i 種資源的擁有量， yi*表示 bi 變化1個(gè)單位對(duì)目標(biāo) z 產(chǎn)生的影響，也是在資源最優(yōu)利用條件下對(duì)該資源的估價(jià)，稱(chēng)為該資源的影子價(jià)格例如，在例1中 yi* 是對(duì)設(shè)備租金的估價(jià)注意：注意：若 B 是最優(yōu)基， y*T = CBB-1北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-39影子價(jià)格的經(jīng)濟(jì)含義及應(yīng)用資源的市場(chǎng)價(jià)格是已知的，且相對(duì)比較穩(wěn)定，而影子價(jià)格有賴(lài)于資源的利用情況，是未知數(shù)，隨著企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況的變化而發(fā)生變化影子價(jià)格是一種邊際價(jià)格，說(shuō)明在資源得到最優(yōu)利用的條件下，增加單位資源量可以增加的收益影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià)

23、，實(shí)際上是一種機(jī)會(huì)成本。企業(yè)可以根據(jù)現(xiàn)有資源的影子價(jià)格，考慮經(jīng)營(yíng)策略：如果影子價(jià)格高于市場(chǎng)價(jià)格，可考慮買(mǎi)進(jìn)設(shè)備，以擴(kuò)大生產(chǎn)能力，否則不宜買(mǎi)進(jìn)；若某設(shè)備的租費(fèi)高于影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-40由互補(bǔ)松弛定理，可知如果某種資源未得到充分利用時(shí)（松弛變量不為0），則其影子價(jià)格為0（對(duì)應(yīng)變量為0）；當(dāng)資源的影子價(jià)格不為0，表明該資源在生產(chǎn)中已耗費(fèi)完畢從影子價(jià)格的含義上來(lái)考察檢驗(yàn)數(shù)j = cj - aij yi，其中 cj 表示產(chǎn)品的價(jià)值，aij yi是生產(chǎn)該產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品的價(jià)值大于隱含成本時(shí)，表明生產(chǎn)該產(chǎn)品

24、有利；否則就不安排生產(chǎn)。這就是檢驗(yàn)數(shù)的經(jīng)濟(jì)含義影子價(jià)格反映了不同的局部或個(gè)體的增量可以獲得不同的整體經(jīng)濟(jì)效益。如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價(jià)格高的設(shè)備入手，以較少的局部努力，獲得較大的整體效益北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-41一般來(lái)說(shuō)，對(duì)線性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問(wèn)題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)。這種估價(jià)涉及到資源的最有效利用，如在一個(gè)大公司內(nèi)部，可借助資源的影子價(jià)格確定內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的好壞需要指出的是，影子價(jià)格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤(rùn)等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格

25、說(shuō)明增加單位資源量可以增加的收益，是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過(guò)了一定的范圍，總利潤(rùn)的增加量就不是按照影子價(jià)格給出的數(shù)值線性地增加。這將在靈敏度分析中討論北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-42 影子價(jià)格的應(yīng)用舉例例5：某外貿(mào)公司準(zhǔn)備購(gòu)進(jìn)兩種產(chǎn)品A1，A2。購(gòu)進(jìn)產(chǎn)品A1每件需要10元，占用5平方米的空間，賣(mài)出1件可獲純利潤(rùn)3元；購(gòu)進(jìn)產(chǎn)品A2每件需要15元，占用3平方米的空間，賣(mài)出1件可獲純利潤(rùn)4元。公司現(xiàn)有資金1400元，有430平方米的倉(cāng)庫(kù)空間存放產(chǎn)品。根據(jù)這些條件可以建立求最大利潤(rùn)的線性規(guī)劃模型： Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15

26、 x2 1400 5 x1 + 3 x2 430 x1, x2 0 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-43求解后得到最優(yōu)單純形表如下所示 ：因此，最優(yōu)方案是分別購(gòu)進(jìn)兩種產(chǎn)品50件和60件，公司的最大利潤(rùn)為390元。同時(shí)，從表中也可以看到，資金的影子價(jià)格為11/45，即增加1元用于購(gòu)買(mǎi)產(chǎn)品，可以多獲利潤(rùn)11/45元；倉(cāng)庫(kù)的影子價(jià)格為1/9，即增加1平方米的倉(cāng)庫(kù)空間，可以多獲利潤(rùn)1/9元CBXBbx1x2x3x44x260011/9-2/93x15010-1/151/3-z-39000-11/45-1/9北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-44假設(shè)公司現(xiàn)在另有一筆資金585元，準(zhǔn)備用于投資。當(dāng)然，這

27、筆資金用于購(gòu)買(mǎi)產(chǎn)品或者增加倉(cāng)庫(kù)空間都可以使公司獲得更多的利潤(rùn)。問(wèn)題是應(yīng)該如何合理安排投資，使公司能夠獲得更多的利潤(rùn)。已知增加1平方米的倉(cāng)庫(kù)空間需要0.8元，因此如果資金用于增加倉(cāng)庫(kù)空間，每投資0.8元可以多獲利1/9元，即每增加1元投資可多獲利5/36=0.14元；而每增加1元用于購(gòu)買(mǎi)產(chǎn)品，可以多獲利11/45=0.24元。因此應(yīng)該把資金用于購(gòu)買(mǎi)產(chǎn)品，這樣可以獲得更多的利潤(rùn)將這585元也用于購(gòu)買(mǎi)產(chǎn)品，可以增加利潤(rùn) 585y1=58511/45=143元北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-45這可通過(guò)對(duì)改變條件的新模型的求解結(jié)果得到驗(yàn)證。新模型為 Max z = 3 x1 + 4 x2 s.t.

28、10 x1 + 15 x2 1985 5 x1 + 3 x2 430 x1, x2 0 得到最優(yōu)解X =(11, 125)T，總利潤(rùn)為533元，增加533-390=143元如果采用其他方案，利潤(rùn)增加量肯定小于143元。如585元中510元用于購(gòu)買(mǎi)產(chǎn)品，75元用于增加倉(cāng)庫(kù)空間(75/0.8=93.75)。則有 Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15 x2 1910 5 x1 + 3 x2 523.75 x1, x2 0 得最優(yōu)解X =(47.25, 95.83)T，總利潤(rùn)為525.08元，只增135.08元北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-46線性規(guī)劃的對(duì)偶問(wèn)題線

29、性規(guī)劃的對(duì)偶單純形法線性規(guī)劃的靈敏度分析參數(shù)線性規(guī)劃北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-47單純形法的思路對(duì)原問(wèn)題的一個(gè)基本可行解，判別是否所有檢驗(yàn)數(shù)滿足最優(yōu)條件。若是，即找到了問(wèn)題最優(yōu)解；否則，再找出相鄰的目標(biāo)函數(shù)值更大的基本可行解，并繼續(xù)判別，直到找到最優(yōu)解或判別出無(wú)最優(yōu)解為止也就是說(shuō)，單純形法在求解過(guò)程中保持原問(wèn)題的可行性，尋找對(duì)偶問(wèn)題的可行解根據(jù)對(duì)偶問(wèn)題的基本性質(zhì)，當(dāng)對(duì)于某個(gè)基而言，原問(wèn)題的基本解是可行的，對(duì)偶問(wèn)題的解也是可行的，則由兩者的目標(biāo)函數(shù)值相等，因此此解為最優(yōu)解。是否可以保持對(duì)偶問(wèn)題的可行性，然后尋找原問(wèn)題的可行解，這就是對(duì)偶單純形法的思路北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-48

30、對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-49對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程：建立初始對(duì)偶單純形表，對(duì)

31、應(yīng)一個(gè)基本解，所有檢驗(yàn)數(shù)均非正，轉(zhuǎn)下一步若b0，則得到最優(yōu)解，停止；否則，若有bk0則選k行的基變量為出基變量，轉(zhuǎn)下一步若所有akj0( j = 1,2,n)，則原問(wèn)題無(wú)可行解，停止；否則，若有akj0 則選 =minj / akj | akj0=r/akr，那么 xr為進(jìn)基變量，轉(zhuǎn)下一步以akr為轉(zhuǎn)軸元，作矩陣行變換使其變?yōu)?，該列其他元變?yōu)?，轉(zhuǎn)回第二步北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-50例6：求解線性規(guī)劃問(wèn)題：求解線性規(guī)劃問(wèn)題：標(biāo)準(zhǔn)化：標(biāo)準(zhǔn)化： Max z = - 2 x1 3 x2 - 4 x3 s.t. - x1 - 2 x2 - x3 + x4 = -3 -2 x1 + x2 -

32、 3 x3 + x5 = -4 x1, x2, x3, x4, x5 0Min f = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2 x2 + x3 3 2 x1 - x2 + x3 4 x1 , x2 , x3 0北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-51北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-52ekeikikiabaab0minekkejejiaaa0min是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算原規(guī)劃的基本解是可行的原規(guī)劃的基本解的檢驗(yàn)數(shù)為非正所有所有計(jì)算計(jì)算以aek為中心元素進(jìn)行迭代以aek為中心元素進(jìn)行迭代停沒(méi)有有限最優(yōu)解沒(méi)有可行解單純形法對(duì)偶單純形法0j0ib0maxjj

33、k0miniiebbb0ika0eja北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-53對(duì)偶單純形法的應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足：?jiǎn)渭冃伪淼臋z驗(yàn)數(shù)行全部非正（對(duì)偶可行）變量取值可有負(fù)數(shù)（非可行解）對(duì)偶單純形法適合于解如下形式的線性規(guī)劃問(wèn)題njxmibxacxcfjnjijijnjjjj,2, 1,0,2, 10min11北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-54在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便對(duì)于有些線性規(guī)劃模型，如果在開(kāi)始求解時(shí)不能很快使所有檢驗(yàn)數(shù)非正，最好還是采用單純形法求解。因?yàn)?，這樣可以

34、免去為使檢驗(yàn)數(shù)全部非正而作的許多工作。從這個(gè)意義上看，可以說(shuō)，對(duì)偶單純形法是單純形法的一個(gè)補(bǔ)充。除此之外，在對(duì)線性規(guī)劃進(jìn)行靈敏度分析中有時(shí)也要用到對(duì)偶單純形方法，可以簡(jiǎn)化計(jì)算北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-55上表中6個(gè)常數(shù) a1 , a2 , a3 , b , 1 , 2 取值在什么范圍可使1、現(xiàn)可行解最優(yōu)，且唯一？何時(shí)不唯一？2、現(xiàn)基本解不可行；3、問(wèn)題無(wú)可行解；4、無(wú)有限最優(yōu)解；5、現(xiàn)基本解可行，由 x1 取代 x6 目標(biāo)函數(shù)可改善。 北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-561、b0,10,20, 1=0或2=0時(shí)不唯一（不考慮退化的復(fù)雜情況，需要再分情況討論）2、b 0 時(shí)現(xiàn)基本解不可

35、行3、b 0, a1 0, b0,無(wú)有限最優(yōu)解5、10, b0, a3 0, 3/a3 0csMinj /asjasj0csMinj /asjasj0brMin-bi/irir0北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-72例10：例9的最優(yōu)單純形表如下 0 1/4 0 這里 B-1 = -2 1/2 1 1/2 -1/8 0 各列分別對(duì)應(yīng) b1、b2、b3 的單一變化，因此，設(shè) b1 增加 4，則 x1, x5, x2分別變?yōu)椋?+04 = 4，4+(-2)4 = -40，2+1/24=4北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-73 用對(duì)偶單純形法進(jìn)一步求解，可得： x* = ( 4, 3, 2, 0,

36、0 )T, z * = 17北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-74是否投產(chǎn)新產(chǎn)品增加一個(gè)變量 假設(shè)可以生產(chǎn)一種新產(chǎn)品，增加變量 xn+1，則有相應(yīng)的pn+1，cn+1 計(jì)算出B-1pn+1 , n+1=cn+1-ci ai ,n+1，填入最優(yōu)單純形表，不影響解的可行性以及其余檢驗(yàn)數(shù) 若 n+1 0 則 最優(yōu)解不變；否則，進(jìn)一步用單純形法求解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-75例11：例9增加x6 ， p6=( 2, 6, 3 )T，c6 = 5 計(jì)算得到用單純形法進(jìn)一步求解，可得：x* = ( 1,3/2,0,0,0,2 )T z* = 33/2，應(yīng)該生產(chǎn)新產(chǎn)品北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑

37、3-76增加資源約束或加工工序增加一個(gè)約束有些資源由于緊缺，不能像以前一樣隨便使用，如電力供應(yīng)有限制等，這就增加了約束；或者增加一道工序，也需要增加一個(gè)約束增加約束一個(gè)之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過(guò)矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼獗本┩鈬?guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-77例12：例9增加3x1+ 2x215，原最優(yōu)解不滿足這個(gè)約束。引入松弛變量，得到 3 x1+ 2 x2 + x6 = 15經(jīng)過(guò)行變換，可以得到北京

38、外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-78經(jīng)對(duì)偶單純形法一步，可得最優(yōu)解為（7/2, 9/4, 0, 2, 3, 0 )T，最優(yōu)值為 55/4北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-79生產(chǎn)工藝發(fā)生變化A中元素發(fā)生變化如果發(fā)生變化的元素不在基中，則與增加變量 xn+1 的情況類(lèi)似，假設(shè) pj 變化，那么，重新計(jì)算出B-1pj ，j = cj - ci ai j ，填入最優(yōu)單純形表，若 j 0 則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解如果發(fā)生變化的元素在基中，則B和B-1都發(fā)生變化，也可能原問(wèn)題和對(duì)偶問(wèn)題的解均不可行，這時(shí)需引入人工變量將原問(wèn)題的解轉(zhuǎn)化為可行解，再用單純形法求解北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3

39、-80例13：例9中若原計(jì)劃生產(chǎn)產(chǎn)品I的工藝有了改進(jìn)，相關(guān)技術(shù)系數(shù)向量由P1=(1,4,0)T變?yōu)镻1=(2,5,2)T，每件利潤(rùn)為4元，試分析對(duì)原最優(yōu)計(jì)劃有什么影響? 解：把改進(jìn)工藝結(jié)構(gòu)的產(chǎn)品I看作產(chǎn)品I，設(shè)x1為其產(chǎn)量。于是在原計(jì)算的最終表中以于是在原計(jì)算的最終表中以x1代替代替x1，計(jì)算對(duì)，計(jì)算對(duì)應(yīng)應(yīng)x1的列向量及檢驗(yàn)數(shù)。的列向量及檢驗(yàn)數(shù)。8383214530248321452520812112120410111111TBPBCcPB北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-81以x1為換入變量，x1為換出變量，經(jīng)過(guò)迭代得到最優(yōu)解為（16/5, 4/5, 0, 0, 12/5)T，最優(yōu)值為 76

40、/5。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-82例14：例9中若原計(jì)劃生產(chǎn)產(chǎn)品I的工藝有了改進(jìn)，相關(guān)技術(shù)系數(shù)向量由P1=(1,4,0)T變?yōu)镻1=(4,5,2)T，每件利潤(rùn)為4元，試分析對(duì)原最優(yōu)計(jì)劃有什么影響? 解：把改進(jìn)工藝結(jié)構(gòu)的產(chǎn)品I看作產(chǎn)品I，設(shè)x1為其產(chǎn)量。在原計(jì)算的最終表中以在原計(jì)算的最終表中以x1代替代替x1，計(jì)算對(duì)應(yīng)，計(jì)算對(duì)應(yīng)x1的列向量及檢驗(yàn)數(shù)。的列向量及檢驗(yàn)數(shù)。8218112745302481127452540812112120410111111TBPBCcPB北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-83注意：若碰到原問(wèn)題和對(duì)偶問(wèn)題均為非可行解時(shí)，就注意：若碰到原問(wèn)題和對(duì)偶問(wèn)題均為非可

41、行解時(shí)，就需要引進(jìn)人工變量后重新求解。需要引進(jìn)人工變量后重新求解。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-84原問(wèn)題和對(duì)偶問(wèn)題都是非可行解，引入人工變量x6。在上表中x2所在行，用方程表示為0 x1 + x2 + 1/2 x3 2/5 x4 + 0 x5 = - 12/5引入人工變量x6后，化為 0 x1 x2 1/2 x3 + 2/5 x4 + 0 x5 + x6 = 12/5將x6作為基變量代替x2，填入表中，得到下表。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-85得到最優(yōu)解為（2/3, 8/3, 0, 38/3, 0, 0)T，最優(yōu)值為 32/3。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-8686多個(gè)參數(shù)同時(shí)

42、發(fā)生變化，適用100%準(zhǔn)則。多個(gè)目標(biāo)函數(shù)系數(shù)發(fā)生變化，定義變化的程度比例：為允許的最大減量）（若為允許的最大增量）（若jjjjjjjjjjDDcrcIIcrc, 0, 0然是最優(yōu)的。，那么原來(lái)的最優(yōu)解仍如果1jr北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-8787多個(gè)右端項(xiàng)同時(shí)發(fā)生變化，定義變化的程度比例：為允許的最大減量）（若為允許的最大增量）（若jjjjjjjjjjDDbrbIIbrb, 0, 0，那么最優(yōu)基不變。如果1jr北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-88利用軟件進(jìn)行求解QSBLINDOEXCEL（舉例說(shuō)明使用方法）北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-89線性規(guī)劃的對(duì)偶問(wèn)題線性規(guī)劃的對(duì)偶單純形法

43、線性規(guī)劃的靈敏度分析參數(shù)線性規(guī)劃北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-90參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃靈敏度分析時(shí)，主要討論在最優(yōu)基不變情況下，確定系數(shù)aij，bi，cj的變化范圍。而參數(shù)線性規(guī)劃是研究這些參數(shù)中某一參數(shù)連續(xù)變化時(shí)，使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù)，含這個(gè)參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對(duì)偶單純形法分析參數(shù)線性規(guī)劃問(wèn)題。北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-91參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃其步驟是：對(duì)含有某參變量t的參數(shù)線性規(guī)劃問(wèn)題。先令t=0，用單純形法求出最優(yōu)解用靈敏度分析法，將參變量t直接反映到最終

44、表中當(dāng)參變量t連續(xù)變大或變小時(shí)，觀察b列和檢驗(yàn)數(shù)行各數(shù)字的變化。若在b列首先出現(xiàn)某負(fù)值時(shí)，則以它對(duì)應(yīng)的變量為換出變量；于是用對(duì)偶單純形法迭代一步。若在檢驗(yàn)數(shù)行首先出現(xiàn)某正值時(shí)，則將它對(duì)應(yīng)的變量為換入變量；用單純形法迭代一步在經(jīng)迭代一步后得到的新表上，令參變量t繼續(xù)變大或變小，重復(fù)上一個(gè)步驟，直到b列不能再出現(xiàn)負(fù)值，檢驗(yàn)數(shù)行不能再出現(xiàn)正值為止北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-92參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃參數(shù)C的變化例15：試分析以下參數(shù)線性規(guī)劃問(wèn)題。當(dāng)參數(shù)t0時(shí)的最優(yōu)解變化。0,18231224)5()23()(max21212121xxxxxxxtxttz北京外國(guó)語(yǔ)大學(xué)國(guó)際商學(xué)院蔡連僑3-93參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃解 將此模型化為標(biāo)準(zhǔn)型令t=0，用單純形法求解：0,18231224)(0)5()23()(max543