線性規(guī)劃對(duì)偶理論及其應(yīng)用

1、運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外 線性規(guī)劃對(duì)偶理論線性規(guī)劃對(duì)偶理論運(yùn)籌學(xué)君子曰：學(xué)不可以已。君子曰：學(xué)不可以已。青，取之于藍(lán)而青于藍(lán)；冰，水為之而寒于水。青，取之于藍(lán)而青于藍(lán)；冰，水為之而寒于水。故不登高山，不知天之高也；故不登高山，不知天之高也；不臨深溪，不知地之厚也；不臨深溪，不知地之厚也； 荀子荀子勸學(xué)勸學(xué)掌握掌握線性規(guī)劃對(duì)偶理論及其基本經(jīng)濟(jì)學(xué)意義；教學(xué)要求：教學(xué)要求：了解了解運(yùn)用對(duì)偶理論對(duì)線性規(guī)劃最優(yōu)解進(jìn)行分析的基本方法；會(huì)會(huì)運(yùn)用對(duì)偶理論對(duì)一些基本的管理問(wèn)題進(jìn)行經(jīng)濟(jì)學(xué)分析。第三章線性規(guī)劃對(duì)偶理論第三章線性規(guī)劃對(duì)偶理論p線性規(guī)劃的對(duì)偶問(wèn)題線性規(guī)劃的對(duì)偶

2、問(wèn)題p對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)p對(duì)偶單純形法對(duì)偶單純形法p影子價(jià)格和靈敏度分析影子價(jià)格和靈敏度分析重點(diǎn)：對(duì)偶轉(zhuǎn)換、對(duì)偶單純形法重點(diǎn)：對(duì)偶轉(zhuǎn)換、對(duì)偶單純形法難點(diǎn)：對(duì)偶性質(zhì)、靈敏度分析難點(diǎn)：對(duì)偶性質(zhì)、靈敏度分析第三章線性規(guī)劃對(duì)偶理論第三章線性規(guī)劃對(duì)偶理論某家具廠木器車(chē)間生產(chǎn)木門(mén)和木窗兩種產(chǎn)品，加工木門(mén)收入為某家具廠木器車(chē)間生產(chǎn)木門(mén)和木窗兩種產(chǎn)品，加工木門(mén)收入為56元元/扇、加工木窗收入為扇、加工木窗收入為30元元/扇，生產(chǎn)扇，生產(chǎn) 一扇木門(mén)需要木工一扇木門(mén)需要木工4小時(shí)，油漆工小時(shí)，油漆工2小時(shí)；生產(chǎn)一扇木窗需要木工小時(shí)；生產(chǎn)一扇木窗需要木工3小時(shí)，油漆工小時(shí)，油漆工1小小時(shí)，該車(chē)間可

3、用本工總工時(shí)為時(shí)，該車(chē)間可用本工總工時(shí)為120小時(shí)，油漆工總工時(shí)為小時(shí)，油漆工總工時(shí)為50小小時(shí)問(wèn)該車(chē)間應(yīng)如何安排生產(chǎn)才能使每日收入最大？時(shí)問(wèn)該車(chē)間應(yīng)如何安排生產(chǎn)才能使每日收入最大？令該車(chē)間每日安排生產(chǎn)木門(mén)令該車(chē)間每日安排生產(chǎn)木門(mén)x1,木窗木窗x2扇，則其數(shù)學(xué)模型為：扇，則其數(shù)學(xué)模型為：max z=56x1+30 x2s.t 4x1+3x2120 2x1+x2 50 x1,x20即每日安排生產(chǎn)木門(mén)即每日安排生產(chǎn)木門(mén)15扇，木窗扇，木窗20扇時(shí)，收入最大為扇時(shí)，收入最大為1440元元一、一、對(duì)偶問(wèn)題的提出最優(yōu)解為：最優(yōu)解為：x=(15,20)，最優(yōu)值為最優(yōu)值為1440元元第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題

4、第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題 假若有一個(gè)個(gè)體經(jīng)營(yíng)者，手中有一批木器家具生產(chǎn)訂單，但無(wú)人手加工，因此想利用該木器車(chē)間的木工與油漆工來(lái)加工完成他的訂單，它需要考慮付給該車(chē)間每個(gè)工時(shí)的價(jià)格 那他應(yīng)如何定價(jià)才能使木器車(chē)間覺(jué)得有利可圖從而愿意替他加工這批訂單，同時(shí)又使自己所付的工時(shí)費(fèi)用總數(shù)最少？設(shè)w1,w2分別為付給木工、油漆工每個(gè)工時(shí)的價(jià)格，則該個(gè)體經(jīng)營(yíng)者的目標(biāo)函數(shù)為：min f=120w1+50w2第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題另外，該個(gè)體經(jīng)營(yíng)者所付的價(jià)格不能太低，至少不能低于該另外，該個(gè)體經(jīng)營(yíng)者所付的價(jià)格不能太低，至少不能低于該車(chē)間生產(chǎn)木門(mén)和木窗所得到的收入，否則該車(chē)間覺(jué)得無(wú)利可車(chē)間

5、生產(chǎn)木門(mén)和木窗所得到的收入，否則該車(chē)間覺(jué)得無(wú)利可圖就不會(huì)替他加工這批訂單，因此，圖就不會(huì)替他加工這批訂單，因此，w1,w2 應(yīng)滿足應(yīng)滿足 4w1+2w2 56上式可理解：生產(chǎn)一扇木門(mén)的木工工時(shí)上式可理解：生產(chǎn)一扇木門(mén)的木工工時(shí)*木工工時(shí)價(jià)木工工時(shí)價(jià)+生產(chǎn)生產(chǎn)一扇木門(mén)的油漆工時(shí)一扇木門(mén)的油漆工時(shí)*油漆工工時(shí)價(jià)油漆工工時(shí)價(jià)生產(chǎn)一扇木門(mén)的收入生產(chǎn)一扇木門(mén)的收入 3w1+w2 30上式可理解：生產(chǎn)一扇木窗的木工工時(shí)上式可理解：生產(chǎn)一扇木窗的木工工時(shí)*木工工時(shí)價(jià)木工工時(shí)價(jià)+生產(chǎn)生產(chǎn)一扇木窗的油漆工時(shí)一扇木窗的油漆工時(shí)*油漆工工時(shí)價(jià)油漆工工時(shí)價(jià)生產(chǎn)一扇木窗的收入生產(chǎn)一扇木窗的收入第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第

6、一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題該個(gè)體經(jīng)營(yíng)者的數(shù)學(xué)模型為min f=120w1+50w24w1+2w2 563w1+w2 30w1,w2 0解得解得w1=2,w2=24,f=1440第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題一、一、對(duì)偶問(wèn)題的提出原問(wèn)題原問(wèn)題某工廠甲生產(chǎn)a、b、c三種產(chǎn)品。這三種產(chǎn)品的單位利潤(rùn)分別是60、30、20。生產(chǎn)這三種單位產(chǎn)品所占用m、n、p三種機(jī)器的時(shí)間如表所示，機(jī)器m、n、p每天可供使用的時(shí)間分別是48、20、8小時(shí)。這三種產(chǎn)品每天生產(chǎn)多少才能使工廠獲得最大效益。產(chǎn)品機(jī)器abc資源限制m86148n421.520p210.

7、58利潤(rùn)603020該問(wèn)題的數(shù)學(xué)模型為：該問(wèn)題的數(shù)學(xué)模型為：0,85 . 02205 . 1244868203060max321321321321321xxxxxxxxxxxxxxxzm機(jī)器機(jī)器n機(jī)器機(jī)器p機(jī)器機(jī)器 現(xiàn)在甲廠擬出租機(jī)器給乙廠，即甲廠出租機(jī)器現(xiàn)在甲廠擬出租機(jī)器給乙廠，即甲廠出租機(jī)器m、n和和p給乙廠，請(qǐng)問(wèn)甲廠應(yīng)如何給這三種機(jī)器定價(jià)？給乙廠，請(qǐng)問(wèn)甲廠應(yīng)如何給這三種機(jī)器定價(jià)？考慮：1、定價(jià)不能太低太低？2、定價(jià)不能太高太高？既要保證甲廠利潤(rùn)又必須使乙廠的租金越少越好咋辦？第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題第一節(jié)線性規(guī)劃的對(duì)偶問(wèn)題產(chǎn)品機(jī)器abc資源限制m86148y1n421.520y2p210

8、.58y3利潤(rùn)60 3020設(shè)m、n、p機(jī)器的單位出售價(jià)格分別為 y1 、 y2和y3，針對(duì)乙廠，建立其相應(yīng)的數(shù)學(xué)模型：目標(biāo)：目標(biāo)：min w=48y1+20y2+8y3對(duì)于a產(chǎn)品而言，甲廠生產(chǎn)一件產(chǎn)品可獲利60元，如果8y1+4y2+2y30 0 ，則有，則有y y0 0p pj j=c=cj j2. 2. 如果如果y y0 0p pj jccj j, ,則有則有x x0 0=0=03. 3. 如果如果y y0 0i i00，則有，則有a ai ix xi i0 0 =b=bi i4.4.如果如果a ai ix xi i0 0 b,0，由松馳性質(zhì)得到原問(wèn)題約束條件應(yīng)取等號(hào)即，由松馳性質(zhì)得到原

9、問(wèn)題約束條件應(yīng)取等號(hào)即w10 2x3+3x4=20w2 0 3x3+2x4=20， 解方程組，得解方程組，得x3=x4=4故原問(wèn)題的最優(yōu)解為故原問(wèn)題的最優(yōu)解為(0,0,4,4)第二節(jié)對(duì)偶規(guī)劃的基本性質(zhì)第二節(jié)對(duì)偶規(guī)劃的基本性質(zhì) w1+2w212w1+w222w1+3w2=33w1+2w2=4x1=0 x2=0例例3.3已知線性規(guī)劃問(wèn)題已知線性規(guī)劃問(wèn)題max z=2x1+x2+5x3+6x4s.t 2x1 + x3+ x4 8 2x1+2x2+x3+2x412 x1 ,x2 ,x3 , x4 , 0其對(duì)偶問(wèn)題的最優(yōu)解為其對(duì)偶問(wèn)題的最優(yōu)解為w=(4,1)t，試根據(jù)對(duì)偶理論求出原問(wèn)題的最優(yōu)解，試根據(jù)對(duì)

10、偶理論求出原問(wèn)題的最優(yōu)解解，該原問(wèn)題的對(duì)偶問(wèn)題為：解，該原問(wèn)題的對(duì)偶問(wèn)題為：min y=8w1+12w2s.t 2w1+2w2 2 (1) 2w1+2w22 x1=0 2w2 1 (2) 2w21 x2=0 w1+ w2 5 (3) w1+w2=5 w1+2w2 6 (4) w1+2w2=6 w1,w2 0將對(duì)偶問(wèn)題的最優(yōu)解代入，得到將對(duì)偶問(wèn)題的最優(yōu)解代入，得到(1),(2)為嚴(yán)格不等式，故由互補(bǔ)松馳性質(zhì)得到為嚴(yán)格不等式，故由互補(bǔ)松馳性質(zhì)得到x1=x2=0又又w1,w20，由松馳性質(zhì)得到原問(wèn)題約束條件應(yīng)取等號(hào)即，由松馳性質(zhì)得到原問(wèn)題約束條件應(yīng)取等號(hào)即w10 x3+x4=8w20 x3+2x4=

11、12，解方程組，得，解方程組，得x3=x4=4故問(wèn)題的最優(yōu)解為（故問(wèn)題的最優(yōu)解為（0,0，4,4）第二節(jié)對(duì)偶規(guī)劃的基本性質(zhì)第二節(jié)對(duì)偶規(guī)劃的基本性質(zhì) 第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 一、對(duì)偶單純形法原理一、對(duì)偶單純形法原理 對(duì)偶單純形法是利用對(duì)偶原理求解原問(wèn)題的一對(duì)偶單純形法是利用對(duì)偶原理求解原問(wèn)題的一種方法（而不是求解對(duì)偶問(wèn)題的方法）種方法（而不是求解對(duì)偶問(wèn)題的方法） 對(duì)偶單純形法基本思想是：首先從原問(wèn)題的一對(duì)偶單純形法基本思想是：首先從原問(wèn)題的一個(gè)對(duì)偶可行的基本解個(gè)對(duì)偶可行的基本解(它不是原線性規(guī)劃問(wèn)題的可它不是原線性規(guī)劃問(wèn)題的可行解行解)出發(fā)，求改進(jìn)的對(duì)偶可行的基本解，向原問(wèn)出發(fā)，求

12、改進(jìn)的對(duì)偶可行的基本解，向原問(wèn)題的題的 可行域逼近，當(dāng)求到對(duì)偶可行的基本解是原可行域逼近，當(dāng)求到對(duì)偶可行的基本解是原問(wèn)題的可行解時(shí)，就得到了最優(yōu)解。問(wèn)題的可行解時(shí)，就得到了最優(yōu)解。p原單純型迭代要求每步都是基礎(chǔ)可行解p達(dá)到最優(yōu)解時(shí)，檢驗(yàn)數(shù) cjzj 0 (max) 或 cjzj 0 (min)p但對(duì)于(min, )型所加的剩余變量無(wú)法構(gòu)成初始基礎(chǔ)可行解，因此通過(guò)加人工變量來(lái)解決p大m法和二階段法較繁p能否從剩余變量構(gòu)成的初始基礎(chǔ)非可行解出發(fā)迭代，但保證檢驗(yàn)數(shù)滿足最優(yōu)條件， cjzj 0 (max) 或 cjzj 0 (min)n每步迭代保持檢驗(yàn)數(shù)滿足最優(yōu)條件，但減少非可行度n如何判斷達(dá)到最優(yōu)解

13、n如何保證初始基礎(chǔ)解滿足最優(yōu)條件b=b1b0考慮對(duì)偶線性規(guī)劃問(wèn)題 min z=cxs.t ax=b x0其中a=(p1,p2,pn)b=(b1,b2,.bn)bi可以是任意數(shù)第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 二、對(duì)偶單純形法的計(jì)算步驟：二、對(duì)偶單純形法的計(jì)算步驟：1、給定一個(gè)初始對(duì)偶可行的基本解，設(shè)相應(yīng)的基為b；2若 ，則停止計(jì)算，現(xiàn)行對(duì)偶可行的基本解為最優(yōu)解。否則令 ，則該行所對(duì)應(yīng)的變量xr 為換出基的變量； 3若對(duì)所有j， ，則停止計(jì)算，原問(wèn)題無(wú)可行解。否則，令則 為換入基的變量；4以 為主元進(jìn)行主元消去，返回2。01bbb0miniirbb0ija0|maxrjrjjjjrkrkkk

14、aazcaazc檢驗(yàn)數(shù)kxrka第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 標(biāo)準(zhǔn)化乘以(-1)icbcbxjjzc3100bx1x2x3x40 x3-1-1-1100 x4-2-2-3013100初始對(duì)偶單純形表：初始對(duì)偶單純形表：出基出基進(jìn)基進(jìn)基主元主元 直到直到b0，停止，停止第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 為了得了初始基本解，為了得了初始基本解，可用大可用大m法和兩階段法法和兩階段法例例3100cbxbbx1x2x3x40 x3-1/3-1/301-1/30 x22/32/310-1/37/3001/3 3100cbxbbx1x2x3x40 x4110-311x2111-102010因?yàn)?/p>

15、因?yàn)閎0，且所有檢驗(yàn)數(shù)，且所有檢驗(yàn)數(shù) cj-zj0,運(yùn)算結(jié)束，得到最優(yōu)解為運(yùn)算結(jié)束，得到最優(yōu)解為x1=0,x2=1 最優(yōu)目標(biāo)值為最優(yōu)目標(biāo)值為 fmin=1表二表二表三表三第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 例例3.4用對(duì)偶單純形法求解線性規(guī)劃用對(duì)偶單純形法求解線性規(guī)劃0,2 33843623min321321321321xxxxxxxxxxxxz解：在第解：在第2 2個(gè)約束方程的兩邊同乘以個(gè)約束方程的兩邊同乘以-1 -1，然后引入變量，然后引入變量x x4 4,x ,x5 5得：得：0,2 338 436 23min5432153214321321xxxxxxxxxxxxxxxxz 第三節(jié)對(duì)

16、偶單純形法第三節(jié)對(duì)偶單純形法 13200cbxbbx1x2x3x4x50 x4863-4100 x5-2-3-1301cj-zj01320013200cbxbbx1x2x3x4x50 x44012121x12/311/3-10-1/3cj-zj-2/308/3301/3 表一表一表二表二用對(duì)偶單純形法求解得最優(yōu)解用對(duì)偶單純形法求解得最優(yōu)解 ：, 4, 3/241xx0532xxx最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值 ：fmin=2/3第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 例3.5 某工廠有生產(chǎn)a、b兩種化工產(chǎn)品 的能力，生產(chǎn)一千克a產(chǎn)品需要2小時(shí)，花費(fèi)成本為2元，而生產(chǎn)一千克b產(chǎn)品則需要1小時(shí)，成本為

17、3元，下個(gè)月的總生產(chǎn)時(shí)間是600小時(shí)，公司決定a，b的總產(chǎn)量至少為350千克，此外公司的一個(gè)主要客戶訂購(gòu)了125千克a產(chǎn)品的要求必須滿足，在滿足客戶要求的前提下，公司應(yīng)怎樣安排生產(chǎn)計(jì)劃，才能盡量降低成本？解 設(shè)a產(chǎn)品的產(chǎn)量為x1千克，b產(chǎn)品的產(chǎn)量為x2千克，則建立相應(yīng)模型min z=2x1+3x2s.t x1 125 x1+x2 350 2x1+x2600 x1,x2 0第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 在第一、二兩個(gè)約束條件兩邊同乘以-1，然后引入變量x3,x4,x5，化為如下形式minz=2x1+3x2s.t -x1 +x3 =-125 -x1-x2 +x4 =-135 2x1+x2

18、+x5=600 x1,x2,x3,x4,x50表一23000cbxbbx1x2x3x4x50 x3-125-101000 x4-350-1-10100 x56002100123000 第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 表二23000cbxbbx1x2x3x4x50 x3225011-102x1350110-100 x5-1000-102101020表三23000cbxbbx1x2x3x4x50 x3125001112x1250100113x2100010-2-100041此時(shí)所有此時(shí)所有b且所有檢驗(yàn)數(shù)大于等于且所有檢驗(yàn)數(shù)大于等于0，所得得到最優(yōu)解為，所得得到最優(yōu)解為x1=250,x2=10

19、0,x3=125 最優(yōu)值為最優(yōu)值為800 第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 三、單純形算法和對(duì)偶單純形算法之差別三、單純形算法和對(duì)偶單純形算法之差別 第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 四、原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題的解的總結(jié)四、原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題的解的總結(jié)在主對(duì)偶定理的證明中我們有：對(duì)偶在主對(duì)偶定理的證明中我們有：對(duì)偶(min型型)變量的最變量的最優(yōu)解等于原問(wèn)題松弛變量的機(jī)會(huì)成本，或者說(shuō)原問(wèn)題松弛變優(yōu)解等于原問(wèn)題松弛變量的機(jī)會(huì)成本，或者說(shuō)原問(wèn)題松弛變量檢驗(yàn)數(shù)的絕對(duì)值量檢驗(yàn)數(shù)的絕對(duì)值不管原問(wèn)題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型表中，都有原不管原問(wèn)題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型表中，都有原問(wèn)題問(wèn)題虛

20、變量虛變量(松弛或剩余松弛或剩余) 的檢驗(yàn)數(shù)對(duì)應(yīng)其對(duì)偶問(wèn)題的檢驗(yàn)數(shù)對(duì)應(yīng)其對(duì)偶問(wèn)題實(shí)變量實(shí)變量 (對(duì)偶變量對(duì)偶變量)的最優(yōu)解，原問(wèn)題的最優(yōu)解，原問(wèn)題實(shí)變量實(shí)變量(決策變量決策變量) 的檢驗(yàn)數(shù)對(duì)的檢驗(yàn)數(shù)對(duì)應(yīng)其對(duì)偶問(wèn)題應(yīng)其對(duì)偶問(wèn)題虛變量虛變量 (松弛或剩余變量松弛或剩余變量)的最優(yōu)解。的最優(yōu)解。第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 max z=4x1+3x2+7x3s.t x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30解：其對(duì)偶問(wèn)題為：解：其對(duì)偶問(wèn)題為：min w=100y1+100y2s.t. y1+3y2 4 2y1+y2 3

21、 2y1+3y2 7 y1,y2 0例例3.6單純形法(max, )對(duì)偶單純形法(min, )化為標(biāo)準(zhǔn)形max z=4x1+3x2+7x3s.t x1+2x2+2x3 +x4=100 3x1+x2+3x3 +x5=100 x1.x2.x3.x4.x50min =100y1+100y2s.t. -y1-3y2+y3=-4 -2y1-y2 +y4=-3 -2y1-3y2 +y5=-7 y1,y2 ,y3,y4,y50最優(yōu)性檢驗(yàn)所有檢驗(yàn)數(shù)是否0 所有b是否0進(jìn)基出基變量的確定檢驗(yàn)數(shù)大的max4,3,7,0,0對(duì)應(yīng)的變量進(jìn)基比值最小的min100/3,100/2 為出基b最小的min-4,-3,-7對(duì)

22、應(yīng)的變量為出基變量比值最大的max-100/2,-100/3為進(jìn)基表一表一43700cbxbbx1x2x3x4x50 x4100122100 x51003130143700表一表一100 100000cbybby1y2y3y4y50y3-4-1-31000y4-3-2-10100y5-7-2-3001100 100000表一43700cbxbbx1x2x3x4x50 x4100122100 x51003130143700表二43700cbxbbx1x2x3x4x50 x4100/3-14/301-2/37x3100/311/3101/3-32/300-7/3表三43700cbxbbx1x2x3

23、x4x53x225-3/4103/4-1/27x3255/401-1/41/2-5/200-1/2-2原問(wèn)題求解（單純形法）：原問(wèn)題求解（單純形法）：第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 得到最優(yōu)解為得到最優(yōu)解為x=(0,25,25),松馳變量的檢驗(yàn)數(shù)為（松馳變量的檢驗(yàn)數(shù)為（1/2，2)max z=4x1+3x2+7x3s.t x1+2x2+2x3 100 3x1+x2+3x3 100 x1.x2.x30表一表一100100000cbybby1y2y3y4y50y3-4-1-31000y4-3-2-10100y5-7-2-3001100100000表二表二100100000cbybby1y2y

24、3y4y50y331010-10y4-2/3-4/3001-1/3100y27/32/3100-1/3100/3000100/3表三表三100100000cbybby1y2y3y4y50y35/20013/4-5/4100y11/2100-3/41/4100y220101/2-1/20002525對(duì)偶問(wèn)題求解對(duì)偶問(wèn)題求解(對(duì)偶單純形法對(duì)偶單純形法)：第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 得到最優(yōu)解得到最優(yōu)解y=(1/2,2)t,松馳變量對(duì)應(yīng)的檢驗(yàn)數(shù)為松馳變量對(duì)應(yīng)的檢驗(yàn)數(shù)為(0,25,25)min w=100y1+100y2s.t. y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,

25、y2 0表三43700cbxbbx1x2x3x4x53x225-3/4103/4-1/27x3255/401-1/41/2-5/200-1/2-2表三表三100100000cbxbbx1x2x3x4x50 x35/20013/4-5/4100 x11/2100-3/41/4100 x220101/2-1/20002525最優(yōu)解為：最優(yōu)解為：x=(0,25,25)t，松馳變量的檢驗(yàn)數(shù)為（，松馳變量的檢驗(yàn)數(shù)為（1/2，2)原問(wèn)題原問(wèn)題(max型型)最優(yōu)表：最優(yōu)表：對(duì)偶問(wèn)題對(duì)偶問(wèn)題(min型型)最優(yōu)表：最優(yōu)表：最優(yōu)解為：最優(yōu)解為：x=(1/2,2)t,剩余變量對(duì)應(yīng)的檢驗(yàn)數(shù)為剩余變量對(duì)應(yīng)的檢驗(yàn)數(shù)為(0

26、,25,25)第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 結(jié)論：結(jié)論：若是若是max型型(單純形法單純形法)在最優(yōu)表中，基變量對(duì)應(yīng)的解為原問(wèn)題在最優(yōu)表中，基變量對(duì)應(yīng)的解為原問(wèn)題(max)的最優(yōu)的最優(yōu)解，松馳變量的解，松馳變量的檢驗(yàn)數(shù)的相反數(shù)檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)為對(duì)偶問(wèn)題對(duì)應(yīng)為對(duì)偶問(wèn)題(min)的最的最優(yōu)解優(yōu)解若是若是min型型 (對(duì)偶單純形法對(duì)偶單純形法)基變量對(duì)應(yīng)的解為本身問(wèn)題的基變量對(duì)應(yīng)的解為本身問(wèn)題的(min)的最優(yōu)解，剩余變的最優(yōu)解，剩余變量的量的檢驗(yàn)數(shù)檢驗(yàn)數(shù)對(duì)應(yīng)為對(duì)偶問(wèn)題對(duì)應(yīng)為對(duì)偶問(wèn)題(max)的最優(yōu)解的最優(yōu)解因此，針對(duì)線性規(guī)劃問(wèn)題，只要解原問(wèn)題或?qū)ε紗?wèn)題其因此，針對(duì)線性規(guī)劃問(wèn)題，只要解原問(wèn)

27、題或?qū)ε紗?wèn)題其中之一就可以中之一就可以第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 思考題：思考題：1、如有原問(wèn)題為、如有原問(wèn)題為max z=2x1+5x2s.t x1 4 2x2 12 3x1+2x2 18 x1.x20利用單純形法求得最優(yōu)表如右表，利用單純形法求得最優(yōu)表如右表，問(wèn)其對(duì)偶問(wèn)題最優(yōu)解為（問(wèn)其對(duì)偶問(wèn)題最優(yōu)解為（ ）a, (2,6,2)b, (0,-11/6,-2/3)c, (0,11/6,2/3)d, (4,12,18)第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 最優(yōu)表最優(yōu)表25000cbxbbx1x2x3x4x50 x320011/3-1/35x260101/200 x12100-1/31/

28、3000-11/6-2/32、某問(wèn)題為、某問(wèn)題為min w=4u1+12u2+18u3s.t u1+3u32 2u2+2u35 u1,u2,u30利用對(duì)偶單純形法求得最優(yōu)，利用對(duì)偶單純形法求得最優(yōu)，如右表所示，問(wèn)對(duì)偶問(wèn)題的如右表所示，問(wèn)對(duì)偶問(wèn)題的最優(yōu)解為：（）最優(yōu)解為：（）a, (2,6)b, (-11/6,-2/3)c, (11/6,2/3)d, (2,5)最優(yōu)表最優(yōu)表4121800cbubbu1u2u3u4u50u32/31/301-1/3012u211/6 -1/310-1-1/220026第三節(jié)對(duì)偶單純形法第三節(jié)對(duì)偶單純形法 第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格二、影子價(jià)格和對(duì)偶價(jià)格二、影子價(jià)

29、格和對(duì)偶價(jià)格 約束條件右側(cè)（即資源）每增加1個(gè)單位，由由此引起最優(yōu)目標(biāo)函數(shù)值的增加量，就等于與該約束條件相對(duì)應(yīng)的對(duì)偶變量的最優(yōu)解值。對(duì)偶解的經(jīng)濟(jì)含義對(duì)偶解的經(jīng)濟(jì)含義：資源的單位改變量引起目標(biāo)函數(shù)值的增加量，經(jīng)濟(jì)學(xué)上稱(chēng)為影子價(jià)格影子價(jià)格。它度量了約束條件對(duì)應(yīng)的那種資源的價(jià)值。第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格在對(duì)偶問(wèn)題的互補(bǔ)松弛性質(zhì)中有 如果某種資源 bi未得到充分利用時(shí)，該種資源的影子價(jià)格為零；如果某種資源bi已完全耗盡，則該種資源的影子價(jià)格不為零資源的影子價(jià)格越高，表明該種資源的貢獻(xiàn)越大 0y 0時(shí)，11injinjijijijijbxa;ybxa時(shí)，當(dāng)當(dāng)?shù)谒墓?jié)影子價(jià)格第四節(jié)影子價(jià)格3020101

30、008060402020406080 x1100b第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格20101008060402020406080 x1100b第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格3020101008060402020406080 x1100b第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格2010 1008060402020406080 x1100b第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格在最優(yōu)表中，松馳變量的檢驗(yàn)數(shù)與對(duì)偶決策變量是一一對(duì)應(yīng)的在最優(yōu)表中，松馳變量的檢驗(yàn)數(shù)與對(duì)偶決策變量是一一對(duì)應(yīng)的max()松馳變量的松馳變量的檢驗(yàn)數(shù)的相反數(shù)檢驗(yàn)數(shù)的相反數(shù)為對(duì)偶問(wèn)題的最優(yōu)解為對(duì)偶問(wèn)題的最優(yōu)解min() 檢驗(yàn)變量的

31、檢驗(yàn)變量的檢驗(yàn)數(shù)檢驗(yàn)數(shù)就為對(duì)偶問(wèn)題的最優(yōu)解就為對(duì)偶問(wèn)題的最優(yōu)解因此，可知因此，可知max()松馳變量的松馳變量的檢驗(yàn)數(shù)的相反數(shù)檢驗(yàn)數(shù)的相反數(shù)就為相應(yīng)資源的影子價(jià)格就為相應(yīng)資源的影子價(jià)格min() 檢驗(yàn)變量的檢驗(yàn)變量的檢驗(yàn)數(shù)檢驗(yàn)數(shù)相應(yīng)資源的影子價(jià)格相應(yīng)資源的影子價(jià)格由上述關(guān)系可知，影子價(jià)格其實(shí)就是對(duì)偶問(wèn)題的最優(yōu)解由上述關(guān)系可知，影子價(jià)格其實(shí)就是對(duì)偶問(wèn)題的最優(yōu)解決策變量、影子價(jià)格之間的對(duì)應(yīng)關(guān)系決策變量、影子價(jià)格之間的對(duì)應(yīng)關(guān)系 例例3.83.8：求下列原問(wèn)題的最優(yōu)解及影子價(jià)格和對(duì)偶問(wèn)題的最優(yōu)解：求下列原問(wèn)題的最優(yōu)解及影子價(jià)格和對(duì)偶問(wèn)題的最優(yōu)解及影子價(jià)格。及影子價(jià)格。 min z=4x1+7x2 +8

32、x3 s.t. x1+ x2 3 x2 +2x3 1 （lp） x1+ x2 + x3 8 x10,x20,x30其對(duì)偶問(wèn)題為：其對(duì)偶問(wèn)題為： max w=3u1+u2 +8x3 s.t. u1 + u3 4 u1+u2 + u3 7 （ld） 2u2 + u3 8 u10,u20 ,u30求解（求解（lp）得最優(yōu)解為）得最優(yōu)解為x*=7.5, 0, 0.5；最優(yōu)值為；最優(yōu)值為34。 求解（求解（ld）得最優(yōu)解為）得最優(yōu)解為u*=0，2，4；最優(yōu)值為；最優(yōu)值為34。所以（所以（lp）的影子價(jià)格是：）的影子價(jià)格是：0，2，4 ；（；（ld）的影子價(jià)格為）的影子價(jià)格為7.5, 0, 0.5； 第四

33、節(jié)影子價(jià)格第四節(jié)影子價(jià)格四、影子價(jià)格的經(jīng)濟(jì)含義1、是否將設(shè)備用于外加工或出租若租金高于某設(shè)備的影子價(jià)格，則可以出租，否則不宜出租。2、是否將投資用于購(gòu)買(mǎi)設(shè)備，以擴(kuò)大生產(chǎn)能力若市場(chǎng)價(jià)低于某設(shè)備的影子價(jià)格，可考慮買(mǎi)進(jìn)設(shè)備，若高于，則不宜買(mǎi)進(jìn)p市場(chǎng)價(jià)格是由市場(chǎng)決定的，一般較穩(wěn)定的，而影子價(jià)格是有賴于資源的利用情況，是未知數(shù)。第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格解：解：x1：產(chǎn)品甲的計(jì)劃生產(chǎn)量；：產(chǎn)品甲的計(jì)劃生產(chǎn)量；x2：產(chǎn)品乙的計(jì)劃生產(chǎn)量，則有如下線：產(chǎn)品乙的計(jì)劃生產(chǎn)量，則有如下線性規(guī)劃問(wèn)題：性規(guī)劃問(wèn)題： max z=7x1 + 12x2 (總銷(xiāo)售收入總銷(xiāo)售收入) s.t. 9x1 + 4x2 360 (煤

34、資源限制煤資源限制) 4x1 + 5x2 200 (電資源限制電資源限制) 3x1 + 10 x2 300 (油資源限制油資源限制) x1 0，x2 0 (非負(fù)條件非負(fù)條件)第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格例例3.93.9：a a工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。每千克產(chǎn)品的銷(xiāo)售工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。每千克產(chǎn)品的銷(xiāo)售價(jià)格和能源消耗量、以及能源資源見(jiàn)表價(jià)格和能源消耗量、以及能源資源見(jiàn)表3-263-26，怎樣安排生產(chǎn)計(jì)，怎樣安排生產(chǎn)計(jì)劃才能使劃才能使a a工廠獲益最大？工廠獲益最大？ 712000cbxbbx1x2x3x4x50 x3360941000 x4200450100 x5300310001c

35、j-zj0712000表一表一表表二二xbbx1x2x3x4x50 x32407.8010-0.40 x4502.5001-0.512x2300.31000.1cj-zj-3603.4000-1.2 xbbx1x2x3x4x50 x3224.4001-3.121.160 x1201000.4-0.212x224010-0.120.04cj-zj-428000-1.36-0.52第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格表表三三原問(wèn)題的最優(yōu)解為原問(wèn)題的最優(yōu)解為x(20,24)t,對(duì)應(yīng)的對(duì)偶價(jià)格，也就是影子價(jià)格為對(duì)應(yīng)的對(duì)偶價(jià)格，也就是影子價(jià)格為(0,1.36,0.52)所以，煤、電、石油的影子價(jià)格分別為：所以，

36、煤、電、石油的影子價(jià)格分別為：0 0、1.361.36、0.520.52。 理論上，如果一個(gè)生產(chǎn)計(jì)劃是最優(yōu)的，則該計(jì)劃必然會(huì)耗盡某些資源。 通過(guò)比較可知，應(yīng)首先增加電資源，因?yàn)樗軐?dǎo)致更多的生產(chǎn)收入，即每增加1度電能使生產(chǎn)收入增加1.36。而如果1度電的價(jià)格高于1.36，對(duì)企業(yè)來(lái)講就不劃算，反之如果低于1.36，則應(yīng)購(gòu)買(mǎi)電資源進(jìn)行生產(chǎn)。第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格原問(wèn)題的最優(yōu)解為原問(wèn)題的最優(yōu)解為x(20,24)t,對(duì)應(yīng)的對(duì)偶價(jià)格，也就是影子價(jià)格為對(duì)應(yīng)的對(duì)偶價(jià)格，也就是影子價(jià)格為(0,1.36,0.52) 根據(jù)影子價(jià)格還可制定新產(chǎn)品的價(jià)格，如上例的a工廠要生產(chǎn)一種新產(chǎn)品，如果每單位新產(chǎn)品需耗用煤

37、、電、石油分別是5、10、3單位，則新產(chǎn)品的價(jià)格必須大于5*0+10*1.3+3*0.52=15.16 如果售價(jià)低于15.16，生產(chǎn)該產(chǎn)品就是不劃算的。 根據(jù)影子價(jià)格還可以分析生產(chǎn)工藝的改變對(duì)資源節(jié)約所帶來(lái)的收益。 例如，如果a工廠經(jīng)過(guò)工藝改造后使石油節(jié)約了2%，則帶來(lái)的經(jīng)濟(jì)收益為 3002%0.52=3.12第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格相當(dāng)于生產(chǎn)成本相當(dāng)于生產(chǎn)成本 五、利用excel求影子價(jià)格在報(bào)告列表框中選擇“敏感性報(bào)告”microsoft excel 9.0 敏感性報(bào)告microsoft excel 9.0 敏感性報(bào)告工作表 solve.xlssheet2工作表 solve.xlsshe

38、et2報(bào)告的建立: 2004-10-7 13:40:18報(bào)告的建立: 2004-10-7 13:40:18可變單元格終終遞減遞減目標(biāo)式目標(biāo)式允許的允許的允許的允許的單元格單元格名字名字值值成本成本系數(shù)系數(shù)增量增量減量減量$b$2x120072.63.4$c$2x22401211.333333333.25約束終終陰影陰影約束約束允許的允許的允許的允許的單元格單元格名字名字值值價(jià)格價(jià)格限制值限制值增量增量減量減量$b$8lhs27603601e+3084$b$9lhs2001.3620026.9230769250$b$10lhs3000.5230010072.4137931第四節(jié)影子價(jià)格第四節(jié)影子

39、價(jià)格max z = 7x1 + 12x2 s.t. 9x1 + 4x2 360 4x1 + 5x2 200 3x1 + 10 x2 300 x1 0，x2 0min g = 360y1 + 200y2 + 300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0第四節(jié)影子價(jià)格第四節(jié)影子價(jià)格在線性規(guī)劃中，我們假定模型的系數(shù)都是已知常數(shù)。而在實(shí)際中，這些系數(shù)往往是通過(guò)估計(jì)、預(yù)測(cè)或人為決策得到的，不可能很準(zhǔn)確，更不可一成不變，靈敏度分析就是研究當(dāng)線性規(guī)劃問(wèn)題中的系數(shù)發(fā)生變化時(shí)，對(duì)函數(shù)最優(yōu)解的影響程度靈敏度分析主要研究以下兩個(gè)問(wèn)題：

40、（1）這些系數(shù)中的一個(gè)或多個(gè)發(fā)生變化時(shí)對(duì)已求得的線性規(guī)劃問(wèn)題最優(yōu)解的影響。（2）若原最優(yōu)基不再是最優(yōu)時(shí)，如何用最簡(jiǎn)便的方法找到新最優(yōu)解和最優(yōu)值一、靈敏度分析概念一、靈敏度分析概念第五節(jié)靈敏度分析第五節(jié)靈敏度分析)24.3(,2, 1,0)23.3(.max1nixbaxtscxxcziniii設(shè)最優(yōu)解為設(shè)最優(yōu)解為xb=b-1b，xn=0，其中，其中b是最優(yōu)可行基是最優(yōu)可行基考慮模型：考慮模型：第五節(jié)靈敏度分析第五節(jié)靈敏度分析單純形法max型 最大檢驗(yàn)數(shù) 最小比 檢驗(yàn)數(shù)小于等于0對(duì)偶單純形法max型 最小b 最小比 所有b大于等于0ccncbcbxbbxnxbcbxbb-1bb-1ni檢驗(yàn)數(shù)向量

41、cb b-1bcn-cbb-1n0第五節(jié)靈敏度分析第五節(jié)靈敏度分析最優(yōu)表：最優(yōu)表：（1）如果）如果非基變量非基變量xk 的系數(shù)的系數(shù)ck變?yōu)樽優(yōu)閏k時(shí)，此時(shí)時(shí)，此時(shí)zj=cbb-1pj不變不變,這種情況只引起一個(gè)檢驗(yàn)數(shù)的變化。這種情況只引起一個(gè)檢驗(yàn)數(shù)的變化。如果檢驗(yàn)數(shù)（如果檢驗(yàn)數(shù)（ck zk）0則原來(lái)問(wèn)題的最優(yōu)解也是新問(wèn)題的最優(yōu)解則原來(lái)問(wèn)題的最優(yōu)解也是新問(wèn)題的最優(yōu)解 如果檢驗(yàn)數(shù)（如果檢驗(yàn)數(shù)（ck -zk ）0則改變后則改變后xk為進(jìn)基變量，把原來(lái)最優(yōu)單純形表中的為進(jìn)基變量，把原來(lái)最優(yōu)單純形表中的ck-zk換成換成ck-zk，然后用單純形表求新問(wèn)題的最優(yōu)解，然后用單純形表求新問(wèn)題的最優(yōu)解1、目標(biāo)

42、函數(shù)系數(shù)（、目標(biāo)函數(shù)系數(shù)（c）的變化）的變化第五節(jié)靈敏度分析第五節(jié)靈敏度分析例例3.10已知線性規(guī)劃問(wèn)題已知線性規(guī)劃問(wèn)題max z=-5x1+5x2+13x3s.t -x1+ x2+ 3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化解分別有什么變化.（1）目標(biāo)函數(shù)）目標(biāo)函數(shù)x3的系數(shù)由的系數(shù)由13變?yōu)樽優(yōu)?解，將原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)，通過(guò)兩步迭代得到最優(yōu)解，將原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)，通過(guò)兩步迭代得到最優(yōu)單純形表：?jiǎn)渭冃伪恚罕砣?55130

43、0cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-50第五節(jié)靈敏度分析第五節(jié)靈敏度分析x3為非基變量，其變化后的檢驗(yàn)數(shù)為3 ck zk85*3+0*(-2)=-70，則用3代替原最優(yōu)解x3的檢驗(yàn)數(shù)，并以x3為進(jìn)基變量，繼續(xù)迭代表三-55800cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-503第五節(jié)靈敏度分析第五節(jié)靈敏度分析例例3.11， 考慮例考慮例2.1，即其線性規(guī)劃為：，即其線性規(guī)劃為：0,0 135 708 600 630 .910 max21241110123212651212110721xxxxx

44、xxxxxtsxx問(wèn)中檔球袋的利潤(rùn)即問(wèn)中檔球袋的利潤(rùn)即x1的系數(shù)在什么范圍內(nèi)變化時(shí)，公司的的系數(shù)在什么范圍內(nèi)變化時(shí)，公司的最優(yōu)生產(chǎn)計(jì)劃不變？最優(yōu)生產(chǎn)計(jì)劃不變？第五節(jié)靈敏度分析第五節(jié)靈敏度分析目標(biāo)函數(shù)系數(shù)在什么范圍變化時(shí)，目標(biāo)函數(shù)的最優(yōu)解不會(huì)目標(biāo)函數(shù)系數(shù)在什么范圍變化時(shí)，目標(biāo)函數(shù)的最優(yōu)解不會(huì)發(fā)生變化，稱(chēng)這樣的范圍為可行最優(yōu)范圍。發(fā)生變化，稱(chēng)這樣的范圍為可行最優(yōu)范圍。解：原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)形經(jīng)過(guò)迭代得最優(yōu)單純形表為：解：原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)形經(jīng)過(guò)迭代得最優(yōu)單純形表為：1090000cbxbbx1x2x3x4x5x69x2252011.8740-1.31200 x412000-0.93

45、710.156010 x154010-1.24901.87500 x61800-0.34400.141cj-zj766800-4.3750-6.9380設(shè)中檔球袋的利潤(rùn)變化設(shè)中檔球袋的利潤(rùn)變化c時(shí)，令時(shí)，令1090000cbxbbx1x2x3x4x5x69x2252011.8740-1.31200 x412000-0.93710.156010 x154010-1.24901.87500 x61800-0.34400.141cj-zj7668540 c 001.249 c -4.3750-1.875 c -6.9380c第五節(jié)靈敏度分析第五節(jié)靈敏度分析 要使原問(wèn)題最優(yōu)生產(chǎn)計(jì)劃不變，也就是最優(yōu)解不

46、變，要使原問(wèn)題最優(yōu)生產(chǎn)計(jì)劃不變，也就是最優(yōu)解不變，則必須所有檢驗(yàn)數(shù)則必須所有檢驗(yàn)數(shù)0，所以令所以令1.249 c -4.3750-1.875 c -6.9380故得故得x1系數(shù)的最優(yōu)可行范圍：系數(shù)的最優(yōu)可行范圍：-3.7 c 3.5 即當(dāng)即當(dāng)x1在在6.3,13.5此范圍內(nèi)變化，此范圍內(nèi)變化，最優(yōu)解不變，為最優(yōu)解不變，為x=（540,252）目標(biāo)函數(shù)值變?yōu)椋耗繕?biāo)函數(shù)值變?yōu)椋簔=(10+ c) x19x27668540 c可行最優(yōu)范圍可行最優(yōu)范圍第五節(jié)靈敏度分析第五節(jié)靈敏度分析x240403020 x1 最優(yōu)解變化max z = 40 x + 50y利潤(rùn)s.t.1x + 2y 40時(shí)間約束4x

47、+ 3y 120人力約束x, y 0非負(fù)約束利用圖解法求最優(yōu)可行范圍，考慮如下模型：利用圖解法求最優(yōu)可行范圍，考慮如下模型：第五節(jié)靈敏度分析第五節(jié)靈敏度分析x240403020 x1 最優(yōu)解變化第五節(jié)靈敏度分析第五節(jié)靈敏度分析 即當(dāng)目標(biāo)函數(shù)的斜率滿足- 4/3 k目標(biāo)- 1/2時(shí)，q仍為最優(yōu)解也就是- 4/3 c1/c2- 1/2時(shí)，q仍為最優(yōu)解假設(shè)c1變化c ,則解不等式- 4/3 （c1 c） /c2- 1/2即得c 。解上述不等式- 4/3 （40 c） /50- 1/215 c80/3 當(dāng)c1在上述范圍內(nèi)變化時(shí)，最優(yōu)解不變第五節(jié)靈敏度分析第五節(jié)靈敏度分析如果檢驗(yàn)數(shù)（如果檢驗(yàn)數(shù)（ck z

48、k）0則原來(lái)問(wèn)題的最優(yōu)解也是新問(wèn)題的最優(yōu)解則原來(lái)問(wèn)題的最優(yōu)解也是新問(wèn)題的最優(yōu)解,但最優(yōu)值發(fā)生變化但最優(yōu)值發(fā)生變化如果檢驗(yàn)數(shù)（如果檢驗(yàn)數(shù)（ck -zk ）0則以最終單純形表為基礎(chǔ)，換上變化后的價(jià)值系數(shù)和檢驗(yàn)數(shù)，則以最終單純形表為基礎(chǔ)，換上變化后的價(jià)值系數(shù)和檢驗(yàn)數(shù)，繼續(xù)迭代可以求出新的最優(yōu)解。繼續(xù)迭代可以求出新的最優(yōu)解。第五節(jié)靈敏度分析第五節(jié)靈敏度分析（2）如果基變量的系數(shù)）如果基變量的系數(shù)ck變?yōu)樽優(yōu)閏k時(shí)，此時(shí)，影響時(shí)，此時(shí)，影響檢驗(yàn)數(shù)和目標(biāo)函數(shù)值。檢驗(yàn)數(shù)和目標(biāo)函數(shù)值。例例3.12已知線性規(guī)劃問(wèn)題已知線性規(guī)劃問(wèn)題max z=2x1-x2+x3s.t x1+x2+x3 6 -x1+2x2 4 x

49、1 ,x2 ,x3 0先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化變化.（1）目標(biāo)函數(shù)變?yōu)椋┠繕?biāo)函數(shù)變?yōu)閙ax z=4x1-x2+x3解，將原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)，通過(guò)兩步迭代得到最優(yōu)單純形表：解，將原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)，通過(guò)兩步迭代得到最優(yōu)單純形表：表三2-1100cbxbbx1x2x3x4x52x16111100 x510031110-3-1-20故原問(wèn)題的最優(yōu)解為故原問(wèn)題的最優(yōu)解為x=(6,0,0,0,10)t，最優(yōu)值為最優(yōu)值為max z=12相當(dāng)于相當(dāng)于x1的系數(shù)變化了的系數(shù)變化了c2

50、方法一：直接將方法一：直接將c加到加到x1的檢的檢驗(yàn)數(shù)上得到新的檢驗(yàn)數(shù)，并繼驗(yàn)數(shù)上得到新的檢驗(yàn)數(shù)，并繼續(xù)迭代續(xù)迭代方法二：求變化后的方法二：求變化后的x1檢驗(yàn)數(shù)檢驗(yàn)數(shù)2 然后繼續(xù)迭代然后繼續(xù)迭代第五節(jié)靈敏度分析第五節(jié)靈敏度分析表四4-1100cbxbbx1x2x3x4x54x16111100 x510031112-3-1-20表五4-1100cbxbbx1x2x3x4x54x16111100 x510031110-5-3-4-2表三2-1100cbxbbx1x2x3x4x52x16111100 x510031110-3-1-20故原問(wèn)題的最優(yōu)解為故原問(wèn)題的最優(yōu)解為x=(6,0,0,0,10)t

51、，最優(yōu)值為最優(yōu)值為max z=24例例3.13已知線性規(guī)劃問(wèn)題已知線性規(guī)劃問(wèn)題max z=2x1-x2+x3s.t x1+x2+x3 6 -x1+2x2 4 x1 ,x2 ,x3 0先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化變化.（1）目標(biāo)函數(shù)變?yōu)椋┠繕?biāo)函數(shù)變?yōu)閙ax z=2x1+3x2+x3解，將原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)，通過(guò)兩步迭代得到最優(yōu)單純形表：解，將原問(wèn)題引入松馳變量化為標(biāo)準(zhǔn)，通過(guò)兩步迭代得到最優(yōu)單純形表：表三2-1100cbxbbx1x2x3x4x52x16111100 x5100311

52、10-3-1-20故原問(wèn)題的最優(yōu)解為故原問(wèn)題的最優(yōu)解為x=(6,0,0,0,10)t，最優(yōu)值為最優(yōu)值為max z=12求變化后的求變化后的x2檢驗(yàn)數(shù)檢驗(yàn)數(shù)2然后繼續(xù)迭代然后繼續(xù)迭代第五節(jié)靈敏度分析第五節(jié)靈敏度分析表四23100cbxbbx1x2x3x4x52x16111100 x5100311101-1-20表五23100cbxbbx1x2x3x4x52x18/3102/32/3-1/33x210/3011/31/31/300-4/3 -7/3-1/3即目標(biāo)函數(shù)改變后，最優(yōu)解變?yōu)椋杭茨繕?biāo)函數(shù)改變后，最優(yōu)解變?yōu)椋簒=(8/3,10/3,0,0,0)t,最優(yōu)值為最優(yōu)值為max z=46/3第五節(jié)靈

53、敏度分析第五節(jié)靈敏度分析表三2-1100cbxbbx1x2x3x4x52x16111100 x510031110-3-1-203-2*1-0*32、約束條件右邊值的變化、約束條件右邊值的變化設(shè)設(shè)bb+b ,由最優(yōu)表可知，改變的只是表中第三列，右端列由最優(yōu)表可知，改變的只是表中第三列，右端列基變量的取值由基變量的取值由xb=b-1b b-1(b+ b)目標(biāo)函數(shù)值由目標(biāo)函數(shù)值由-z=-cbb-1b -cbb-1(b+ b)（1）如果如果xb=b-1(b+ b) 0則原來(lái)的最優(yōu)基不變，但基變量的取值和目標(biāo)函數(shù)將發(fā)生則原來(lái)的最優(yōu)基不變，但基變量的取值和目標(biāo)函數(shù)將發(fā)生變化此時(shí)變化此時(shí)xb為新問(wèn)題的最優(yōu)解

54、，為新問(wèn)題的最優(yōu)解，z為新問(wèn)題的最優(yōu)值為新問(wèn)題的最優(yōu)值第五節(jié)靈敏度分析第五節(jié)靈敏度分析例例3.12， 考慮例考慮例2.1，即其線性規(guī)劃為：，即其線性規(guī)劃為：0,0 135 708 600 630 .910 max21241110123212651212110721xxxxxxxxxxtsxx 當(dāng)剪裁部門(mén)的時(shí)間再增加當(dāng)剪裁部門(mén)的時(shí)間再增加20小時(shí)，同時(shí)定型部門(mén)小時(shí)，同時(shí)定型部門(mén)增加增加100小時(shí)，考慮對(duì)公司利潤(rùn)的有如何影響？小時(shí)，考慮對(duì)公司利潤(rùn)的有如何影響？第五節(jié)靈敏度分析第五節(jié)靈敏度分析解：用單純形法求解新問(wèn)題得初始表與最終單純形表為：解：用單純形法求解新問(wèn)題得初始表與最終單純形表為：最優(yōu)表1

55、090000cbxbbx1x2x3x4x5x69x2252011.8740-1.31200 x412000-0.93710.156010 x154010-1.24901.87500 x61800-0.34400.141cj-zj766800-4.3750-6.9380初始表1090000cbxbbx1x2x3x4x5x60 x36307/10910000 x46001/25/601000 x570812/300100 x61351/101/40001cj-zj01090000b-1第五節(jié)靈敏度分析第五節(jié)靈敏度分析x=b-1b1.875 0 -1.312 0-0.937 1 0.156 0-1.

56、2 0 1.875 0-0.344 0 0.14 1b-1=約束條件的右端值約束條件的右端值b-1b=1.875 0 -1.312 0-0.937 1 0.156 0-1.2 0 1.875 0-0.344 0 0.14 1650600808135=158.25116.875702.525.1870第五節(jié)靈敏度分析第五節(jié)靈敏度分析630600708135b=650600808135b=原最優(yōu)表1090000cbxbbx1x2x3x4x5x69x2011.8740-1.31200 x400-0.93710.156010 x110-1.24901.87500 x600-0.34400.141cj-

57、zj766800-4.3750-6.9380所以最優(yōu)基不變，仍為所以最優(yōu)基不變，仍為(x2,x4,x1,x6)，即最優(yōu)解為，即最優(yōu)解為x2=158.25，x4=116.875,x1=702.5,x6=25.187,x3=x5=0此時(shí)，目標(biāo)函數(shù)此時(shí)，目標(biāo)函數(shù)z=10 x1+9x2=8449.25增加利潤(rùn)為增加利潤(rùn)為8449.25-7668=781.3也等于影子價(jià)格也等于影子價(jià)格20*4.375+100*6.938=781.3158.25116.875702.525.18725212054018第五節(jié)靈敏度分析第五節(jié)靈敏度分析p（2）如果）如果b-1b 0p則原來(lái)的最優(yōu)基不再是新問(wèn)題的可行基，但所

58、有則原來(lái)的最優(yōu)基不再是新問(wèn)題的可行基，但所有檢驗(yàn)數(shù)檢驗(yàn)數(shù)0，所以現(xiàn)行基本解是對(duì)偶可行的基本解，所以現(xiàn)行基本解是對(duì)偶可行的基本解，p此時(shí)，將最優(yōu)表中的右端列修改為：此時(shí)，將最優(yōu)表中的右端列修改為：b-1b，然，然后用對(duì)偶單純形法求解新問(wèn)題后用對(duì)偶單純形法求解新問(wèn)題第五節(jié)靈敏度分析第五節(jié)靈敏度分析例例3.13已知線性規(guī)劃問(wèn)題已知線性規(guī)劃問(wèn)題max z=-5x1+5x2+13x3s.t -x1+x2+3x3 20 12x1+4x2+10 x390 x1 ,x2 ,x3 0分析在下列各種條件下，最優(yōu)解分別有什么變化分析在下列各種條件下，最優(yōu)解分別有什么變化.（1）約束條件）約束條件的右端值由的右端值由

59、20變?yōu)樽優(yōu)?0（2）約束條件）約束條件對(duì)應(yīng)的對(duì)應(yīng)的b1的在什么范圍內(nèi)變化時(shí)，最優(yōu)基不變的在什么范圍內(nèi)變化時(shí)，最優(yōu)基不變解，（解，（1）引入松馳變量）引入松馳變量,利用單純形法得到最優(yōu)單純形表：利用單純形法得到最優(yōu)單純形表：表三表三551300cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-50最優(yōu)解為最優(yōu)解為x=(0,20,0,0,10)t,最優(yōu)值為最優(yōu)值為max z=100第五節(jié)靈敏度分析第五節(jié)靈敏度分析表三551300cbxbbx1x2x3x4x55x220-113100 x510160-2-4100-2-50由上表可知由上表可知b1=1 0-4

60、 1b-1b=1 0-4 130 9030 -30=表四551300cbxbbx1x2x3x4x55x230-113100 x5-30160-2-4100-2-50利用對(duì)偶單純形利用對(duì)偶單純形法（法（max)型求型求解解minbi出基出基最小比進(jìn)基最小比進(jìn)基存在值小于存在值小于0，即用對(duì)偶單純形法繼即用對(duì)偶單純形法繼續(xù)求解續(xù)求解第五節(jié)靈敏度分析第五節(jié)靈敏度分析表五-551300cbxbbx1x2x3x4x55x2-152310-53/213x315-8012-1/2-1600-1-1表六-551300cbxbbx1x2x3x4x50 x43-23/5-1/501-3/1013x396/52/5