第三章對(duì)偶理論和靈敏度分析

1、第三章 對(duì)偶理論和靈敏度分析第三章 對(duì)偶理論和靈敏度分析第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)第3節(jié) 影子價(jià)格第4節(jié) 對(duì)偶單純形法第5節(jié) 靈敏度分析第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題一、對(duì)偶的含義對(duì)同一事物（問(wèn)題）從不同的角度（立場(chǎng)）觀察，有兩種對(duì)立的表述。例如：“平面中矩形的面積與周長(zhǎng)的關(guān)系”有兩種表述：周長(zhǎng)一定，面積最大的矩形是正方形；面積一定，周長(zhǎng)最短的矩形是正方形。第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例1：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如下表所示。該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利3元，問(wèn)應(yīng)如何安排計(jì)劃使該工

2、廠獲利最多？產(chǎn)品資源產(chǎn)品產(chǎn)品現(xiàn)有條件設(shè)備1臺(tái)時(shí)/件2臺(tái)時(shí)/件8臺(tái)時(shí)原材料A4kg/件016kg原材料B04kg/件12kg另一個(gè)角度靈敏度分析第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例1：解：設(shè)計(jì)劃期內(nèi)產(chǎn)品、的產(chǎn)量分別為x1、x2 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20求解對(duì)偶問(wèn)題圖解法確定影子價(jià)格第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題從另一個(gè)角度考慮例1。假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品、 ，而將其所有資源（設(shè)備和原材料）出租或外售，問(wèn)應(yīng)給每種資源如何定價(jià)，使該工廠的收入最合理？第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題解：設(shè)出租單位設(shè)備臺(tái)時(shí)的租金為y1，出讓單位原材料A，B的售價(jià)為y2，

3、y3 min=8y1+16y2+12y3 y1+4y22 2y1+4y33 y1，y2 ，y30第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題max z =2x1+3x2 min=8y1+16y2+12y3 x1+2x28 y1+4y22 4x116 2y1+4y33 4x212 y1，y2，y30 x1，x20第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題對(duì)于一般產(chǎn)品組合問(wèn)題的線性規(guī)劃問(wèn)題，從另一角度提出問(wèn)題：假定有另一公司欲將該公司所擁有的資源收買過(guò)來(lái)，至少應(yīng)付出多少代價(jià)，才能使該公司愿意放棄生產(chǎn)活動(dòng)，出讓資源？第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題11221112121112122222112212min,0mmmmmmnnmnmnmb

4、yb yb ya ya ya yca ya yayca ya yaycy yy解：設(shè)用yi代表收買該公司一單位i種資源時(shí)付給的代價(jià)第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xba xaxaxbx xx11221112121112122222112212min,0mmmmmmnnmnmnmb yb yb ya ya ya yca ya yayca ya yaycy yy企業(yè)決策者做生產(chǎn)規(guī)劃 最大利潤(rùn)為目標(biāo) 最小資源消耗為目標(biāo)第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題二、對(duì)偶問(wèn)題

5、含義：每一線性規(guī)劃問(wèn)題（稱為原問(wèn)題）都有一個(gè)與之對(duì)應(yīng)的線性規(guī)劃問(wèn)題，稱其為對(duì)偶問(wèn)題。第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題特點(diǎn)：原問(wèn)題與對(duì)偶問(wèn)題從不同角度對(duì)一個(gè)實(shí)際問(wèn)題提出并進(jìn)行描述，組成一對(duì)互為對(duì)偶的線性規(guī)劃問(wèn)題。（1）同一組數(shù)據(jù)參數(shù)（2）不同數(shù)據(jù)位置（3）同一個(gè)問(wèn)題從兩種不同角度描述第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題原問(wèn)題： max z =CX AXb X0對(duì)偶問(wèn)題： min=Yb YAC Y0三、原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題原（對(duì)偶）問(wèn)題對(duì)偶（原）問(wèn)題目標(biāo)函數(shù)z求最大化目標(biāo)函數(shù)求最小化n個(gè)變量變量 0變量 0變量取值無(wú)約束n個(gè)（函數(shù)）約束條件（函數(shù)）約束條件?。ê瘮?shù)）約束條件?。ê瘮?shù)）約

6、束條件取m個(gè)（函數(shù)）約束條件（函數(shù)）約束條件為（函數(shù)）約束條件為（函數(shù)）約束條件為m個(gè)變量變量 0變量 0變量取值無(wú)約束（函數(shù)）約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)（函數(shù)）約束條件右端項(xiàng)原問(wèn)題與對(duì)偶問(wèn)題的轉(zhuǎn)化規(guī)則第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題要求：求下列線性規(guī)劃原問(wèn)題的對(duì)偶問(wèn)題。例2： max z =2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例2：解： min=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 y1，y2，y30第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例3： min z =2x1+3x2 -5x3+x4 x1

7、+x2-3x3+x45 2x1+2x3+x44 x2+x3+x4=6 x10，x2，x30，x4無(wú)約束第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例3：解： max=5y1+4y2 +6y3 y1+2y22 y1+y33 -3y1+2y2+y3-5 y1+y2+y3=1 y10，y20，y3取值無(wú)約束第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例4： min z =7x1+4x2 -3x3 -4x1+2x2-6x324 -3x1-6x2-4x315 5x2+3x3=30 x10，x2無(wú)約束，x30第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例4：解： max=24y1+15y2 +30y3 -4y1-3y27 2y1-6y2+5y3=4 -6y2

8、-4y2+3y3-3 y10，y20，y3無(wú)約束第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例5： max z =3x1-7x2 -5x3+8x4+8x5 x2-x3+3x4-4x5=-16 2x1+3x2-3x3-2x42 -x1+2x3-2x4-5 -2x110 5x225 x3，x40，x5無(wú)約束第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例5：解：min=-16y1+2y2 -5y3+10y4-2y5+25y6+5y7 2y2-y3+y4+y5=3 y1+3y2+y6+y7-7 -y1-3y2+2y3-5 3y1-2y2-2y38 -4y1=8 y1無(wú)約束，y20，y30，y40，y50，y60，y70第1節(jié) 線性規(guī)劃的

9、對(duì)偶問(wèn)題例6：min z =2x1+x2 x1+3x210 x12 x2-3第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題例6： 解： max=10y1+2y2-3y3 y1+y22 3y1+y31 y10，y20，y30第1節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題小結(jié)在寫對(duì)偶問(wèn)題時(shí)，需要注意的是原問(wèn)題是最大化形式還是最小化形式，這對(duì)對(duì)偶問(wèn)題的變量與約束條件的對(duì)應(yīng)關(guān)系影響很大。作業(yè)3-1作業(yè)3-1：試求下列線性規(guī)劃原問(wèn)題的對(duì)偶問(wèn)題。1、 min z =-x1+3x2 -5x3 -2x1+6x2-x330 x1+4x2-3x320 x1-x2+x3=-4 x10，x20，x3無(wú)約束2、 max z =x1+x2+2x3+x4 2x1

10、+3x2+x3-x45 x1-x2+6x3+x47 x1+x2=-4 x1，x30 ，x20，x4無(wú)約束第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)11max0njjjnijjijjzc xa xbx假定線性規(guī)劃原問(wèn)題為：110miiimijijiib ya ycy其對(duì)偶問(wèn)題為：min第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)1、對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。i112ynmjjiijic xb yj、弱對(duì)偶性：若x 是原問(wèn)題的可行解，是其對(duì)偶問(wèn)題的可行解，則有。i11i3y=ynmjjiijic xb yjj、最優(yōu)性：若x 是原問(wèn)題的可行解，是其對(duì)偶問(wèn)題的可行解，且有，則x 是原問(wèn)題的最優(yōu)解， 是其對(duì)偶問(wèn)題的最優(yōu)解。第2節(jié)

11、對(duì)偶問(wèn)題的基本性質(zhì)4、強(qiáng)對(duì)偶性（對(duì)偶定理）：若原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也一定有最優(yōu)解，且目標(biāo)函數(shù)值相同。5、無(wú)界性：若原問(wèn)題（對(duì)偶問(wèn)題）具有無(wú)界解，則對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。無(wú)界性的應(yīng)用：當(dāng)原問(wèn)題（對(duì)偶問(wèn)題）無(wú)可行解時(shí)，其對(duì)偶問(wèn)題（原問(wèn)題）或無(wú)可行解或具有無(wú)界解。第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)即：若對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之若約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量值為零。nniijjijjij=1j=1ya xa xy =iibb6、互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解中，若0，則；若，則0。mmjijijji=1i=1xaaxjjccii類似可得：若0，

12、則y；若y，則0。第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)7、變量對(duì)應(yīng)關(guān)系：用單純形表求解線性規(guī)劃問(wèn)題時(shí)，迭代的每一步在得到原問(wèn)題的一個(gè)基可行解的同時(shí)，其檢驗(yàn)數(shù)行的相反數(shù)是其對(duì)偶問(wèn)題的一個(gè)基解。若原問(wèn)題單純形表達(dá)到最優(yōu)，則對(duì)偶問(wèn)題的最優(yōu)解為原問(wèn)題松弛變量對(duì)應(yīng)的檢驗(yàn)數(shù)的相反數(shù)。第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例8：已知線性規(guī)劃問(wèn)題 max z =x1+x2 -x1+x2+x32 -2x1+x2-x31 x1，x2，x30試應(yīng)用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例8：解：對(duì)偶問(wèn)題 min=2y1+y2 -y1-2y21 y1+y21 y1-y20 y1，y20無(wú)界性第2節(jié) 對(duì)偶問(wèn)題的基本

13、性質(zhì)例9：已知線性規(guī)劃問(wèn)題 min=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 x1，x2，x3，x4，x50已知其對(duì)偶問(wèn)題的最優(yōu)解為y1=0.8，y2=0.6，z=5，試根據(jù)對(duì)偶理論，直接求出出原問(wèn)題的最優(yōu)解。第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例9：解：對(duì)偶問(wèn)題 max z=4y1+3y2 y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20互補(bǔ)松弛性第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例10：已知線性規(guī)劃問(wèn)題 max z =x1+2x2+3x3+4x4 x1+2x2+2x3+3x420 2x1+x2+3

14、x3+2x420 x1，x2，x3，x40其對(duì)偶問(wèn)題最優(yōu)解為y1=1.2，y2=0.2，試根據(jù)對(duì)偶理論，直接求出原問(wèn)題最優(yōu)解。第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例10：解：對(duì)偶問(wèn)題 min=20y1+20y2 y1+2y21 2y1+y22 2y1+3y23 3y1+2y24 y1，y20第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例11：已知線性規(guī)劃問(wèn)題 max z =4x1+3x2 x16 2x28 2x1+3x218 x1，x20其最優(yōu)單純形表如右所示：試確定對(duì)偶問(wèn)題的最優(yōu)解。 4 3 0 0 0CBxBb x1 x2 x3 x4 x5403x1x4x2642 1 0 1 0 0 0 0 4/3 1 -2/3 0

15、 1 -2/3 0 1/3 0 0 -2 0 -1jc j單純形表中解的對(duì)應(yīng)關(guān)系第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例12：求解下述線性規(guī)劃問(wèn)題。 max z =3x1-2x2+4x3+2x4 4x1+2x2+3x3+x415 3x1-2x2+x3-4x44 x1，x2，x3，x40第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)例12：解：對(duì)偶問(wèn)題 min=15y1+4y2 4y1+3y23 2y1-2y2-2 3y1+y24 y1-4y22 y10 ，y20第2節(jié) 對(duì)偶問(wèn)題的基本性質(zhì)小結(jié)（1）在求解線性規(guī)劃問(wèn)題時(shí)，只需求解其中一個(gè)問(wèn)題，就可從最優(yōu)解的單純形表中同時(shí)得到另一個(gè)問(wèn)題的最優(yōu)解。（2）求解一個(gè)m個(gè)約束條件n個(gè)變量

16、的線性規(guī)劃問(wèn)題，可以轉(zhuǎn)化為求解一個(gè)n個(gè)約束條件m個(gè)變量的對(duì)偶問(wèn)題（3）當(dāng)m=2時(shí)，對(duì)偶問(wèn)題可以用圖解法求解，簡(jiǎn)化求解過(guò)程作業(yè)3-2作業(yè)3-2：已知線性規(guī)劃問(wèn)題 max z =2x1+4x2+x3+x4 x1+3x2+x48 2x1+x26 x1+x2+x39 x2+x3+x46 x1，x2 ，x3 ，x40已知原問(wèn)題最優(yōu)解為（2，2，4，0），試根據(jù)對(duì)偶理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。第3節(jié) 影子價(jià)格例13：試確定例1對(duì)偶問(wèn)題的最優(yōu)解。max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20第3節(jié) 影子價(jià)格解：方法一：寫出對(duì)偶問(wèn)題并求解max z =2x1+3x2 m

17、in=8y1+16y2+12y3 x1+2x28 y1+4y22 4x116 2y1+4y33 4x212 y1，y2，y30 x1，x20第3節(jié) 影子價(jià)格方法二：?jiǎn)渭冃畏ㄞD(zhuǎn)化為標(biāo)準(zhǔn)型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x150最優(yōu)單純形表如右所示： 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0jc j第3節(jié) 影子價(jià)格一、影子價(jià)格的定義根據(jù)第i種資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價(jià)，稱為影子

18、價(jià)格。數(shù)量上等于對(duì)偶問(wèn)題的最優(yōu)解yi*，量綱上是對(duì)一個(gè)單位的第i種資源的估價(jià)（或?qū)δ繕?biāo)函數(shù)的利潤(rùn)貢獻(xiàn)）。第3節(jié) 影子價(jià)格二、影子價(jià)格的計(jì)算第i種資源的影子價(jià)格是第i種資源的邊際價(jià)格，表示在給定的生產(chǎn)條件下，每增加一個(gè)單位的第i種資源時(shí)目標(biāo)函數(shù)z*的增量（z*）。=iiziyzb第 種資源的影子價(jià)格第3節(jié) 影子價(jià)格例14：試確定例1中三種資源各自的影子價(jià)格。解：圖解法圖示如下：第3節(jié) 影子價(jià)格例15：已知線性規(guī)劃問(wèn)題 max z =4x1+3x2 x16 2x28 2x1+3x218 x1，x20其最優(yōu)單純形表如右所示：試確定三種資源的影子價(jià)格，并說(shuō)明其含義。 4 3 0 0 0CBxBb x1

19、 x2 x3 x4 x5403x1x4x2642 1 0 1 0 0 0 0 4/3 1 -2/3 0 1 -2/3 0 1/3 0 0 -2 0 -1jc j第3節(jié) 影子價(jià)格小結(jié)（1）對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題可以用圖解法確定第i種資源的影子價(jià)格（即為最優(yōu)目標(biāo)函數(shù)值的改變量）（2）對(duì)于兩個(gè)及兩個(gè)以上決策變量的線性規(guī)劃問(wèn)題可以用單純形法確定第i種資源的影子價(jià)格（即為對(duì)偶問(wèn)題的最優(yōu)解）第3節(jié) 影子價(jià)格三、影子價(jià)格的經(jīng)濟(jì)意義影子價(jià)格是第i種資源的機(jī)會(huì)成本。在現(xiàn)有資源量的基礎(chǔ)上，若增加一個(gè)單位的第i種資源，企業(yè)獲利將增加yi* （即z*），反之若減少一個(gè)單位的第i種資源，企業(yè)獲利將減少yi*

20、（即z*） 。生產(chǎn)決策者可以根據(jù)第i種資源的市場(chǎng)價(jià)格來(lái)決策是否調(diào)整原來(lái)的生產(chǎn)規(guī)模。第i種資源的市場(chǎng)價(jià)格是已知數(shù)，而第i種資源的影子價(jià)格取決于該資源的利用情況，是未知數(shù)，即是一種動(dòng)態(tài)價(jià)格。第i種資源市場(chǎng)價(jià)格低于其影子價(jià)格，企業(yè)應(yīng)從市場(chǎng)上買進(jìn)該資源若干單位（獲利更大），擴(kuò)大生產(chǎn)規(guī)模。第i種資源市場(chǎng)價(jià)格高于其影子價(jià)格，企業(yè)應(yīng)把已有該資源賣掉（獲利更大），減少生產(chǎn)規(guī)模。第i種資源市場(chǎng)價(jià)格等于其影子價(jià)格，企業(yè)既不用買入該資源，也不用賣出該資源。作業(yè)3-3作業(yè)3-3：有一標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題：maxZ=CX，AX=b，X0，其最優(yōu)單純形表如下表所示。其中：x4，x5是對(duì)應(yīng)于初始單位矩陣的松弛變量。試求：（

21、1）利用最優(yōu)單純形表求c1，c2，c3，c4，c5。（2）求約束條件影子價(jià)格。 c1 c2 c3 c4 c5CBxBb x1 x2 x3 x4 x5c1c2x1x212 1 0 -1 3 -1 0 1 2 -1 1 0 0 -3 -3 -1jc j第4節(jié) 對(duì)偶單純形法例16：求解下述線性規(guī)劃問(wèn)題。 min z =15x1+24x2+5x3 6x2+x32 5x1+2x2+x31 x1，x2，x30第4節(jié) 對(duì)偶單純形法例16：解：方法一：對(duì)偶理論對(duì)偶問(wèn)題 max=2y1+y2 5y215 6y1+2y224 y1+y25 y1，y20第4節(jié) 對(duì)偶單純形法方法二：人工變量法 max z=-15x1

22、-24x2-5x3-Mx6-Mx7 6x2+x3-x4+x6=2 5x1+2x2+x3-x5+x7=1 xj0（j=1，2，7）第4節(jié) 對(duì)偶單純形法一、對(duì)偶單純形法的含義將單純形法應(yīng)用于對(duì)偶問(wèn)題的一種計(jì)算方法。第4節(jié) 對(duì)偶單純形法二、對(duì)偶單純形法的解題思路在單純形表中進(jìn)行迭代時(shí)，保持對(duì)偶問(wèn)題的解是基可行解（即所有檢驗(yàn)數(shù)都為非負(fù)），而原問(wèn)題在非可行解的基礎(chǔ)上（即b列數(shù)字中有負(fù)數(shù)），通過(guò)逐步迭代達(dá)到基可行解，進(jìn)而得到最優(yōu)解。第4節(jié) 對(duì)偶單純形法三、對(duì)偶單純形法的解題步驟第一，將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型，列初始單純形表。若表中b列數(shù)字都為非負(fù)，所有檢驗(yàn)數(shù)都為非正，則已得最優(yōu)解，停止計(jì)算；否則若b列數(shù)字中至少

23、有一個(gè)負(fù)分量，且所有檢驗(yàn)數(shù)非正，則轉(zhuǎn)入第二。第二，確定換出變量。 對(duì)應(yīng)的基變量xi為換出變量xl。第三，確定換入變量。在初始單純形表中檢查xl所在行的各系數(shù)alj（j=1，2，n）,若所有alj0，則無(wú)可行解，停止計(jì)算；否則 若存在alj0,則有 ，對(duì)應(yīng)的xk（非基變量）為換入變量。第四，以alk為主元素進(jìn)行迭代，得到新的單純形表，重復(fù)第一第四，直至終止。111min () ()()iilB bB bB b minjkljljlkaaa 對(duì)偶單純形法求解例16第4節(jié) 對(duì)偶單純形法方法三：對(duì)偶單純形法解：標(biāo)準(zhǔn)型轉(zhuǎn)化另一種形式1232312345max1524562521jzxxxxxxxxxxx

24、 0（j=1，2， ，5）1232312345max1524562521jzxxxxxxxxxxx 0（j=1，2， ，5）第4節(jié) 對(duì)偶單純形法單純形法與對(duì)偶單純形法的對(duì)應(yīng)關(guān)系單純形法對(duì)偶單純形法前提條件所有bi0所有j0最優(yōu)性檢驗(yàn)所有j0 ？所有bi0？j0 ？換入、換出變量的確定先確定換入變量后確定換出變量先確定換出變量后確定換入變量原始基解的變化可行最優(yōu)非可行可行（最優(yōu)）第4節(jié) 對(duì)偶單純形法小結(jié)（1）對(duì)于初始解是非基可行解，檢驗(yàn)數(shù)都是負(fù)數(shù)的情況，不必添加人工變量，直接應(yīng)用對(duì)偶單純形法計(jì)算（2）對(duì)于變量多于約束條件的線性規(guī)劃問(wèn)題，直接應(yīng)用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量（若約束條件僅有兩

25、個(gè)，可先將它變換為對(duì)偶問(wèn)題，然后用圖解法求解）；對(duì)于變量較少，約束條件很多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解（3）對(duì)偶單純形法應(yīng)用的局限性：很難找到一個(gè)初始可行基，使初始解是非基可行解，檢驗(yàn)數(shù)都是負(fù)數(shù)作業(yè)3-4 作業(yè)3-4：用對(duì)偶單純形法求解下述線性規(guī)劃問(wèn)題。 min z =3x1+2x2+x3+4x4 2x1+4x2+5x3+x40 3x1-x2+7x3-2x42 5x1+2x2+x3+6x415 x1，x2，x3，x40第5節(jié) 靈敏度分析一、靈敏度分析的含義系統(tǒng)或事物對(duì)因周圍條件變化而顯示出來(lái)的敏感程度的分析。第5節(jié) 靈敏度分析目標(biāo)系數(shù)cj：成本、運(yùn)輸、廣告、產(chǎn)

26、品的接受程度、競(jìng)爭(zhēng)者的數(shù)量等因素引起cj的變化約束系數(shù)aij：生產(chǎn)條件的改變引起aij的變化右端項(xiàng)bi：資源投入量的改變引起bi的變化決策變量：新產(chǎn)品的開(kāi)發(fā)引起的增加約束條件：增加新的資源限制引起約束條件的增加11max(min)( , ),1,2,0,1,2,njjjnijjijjzc xa xb imxjn 第5節(jié) 靈敏度分析二、靈敏度分析的內(nèi)容當(dāng)模型中約束系數(shù)aij、右端項(xiàng)bi和目標(biāo)系數(shù)cj有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)有什么變化模型中約束系數(shù)aij、右端項(xiàng)bi和目標(biāo)系數(shù)cj在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解（或最優(yōu)基）不變?nèi)粢亚蟮玫木€性規(guī)劃問(wèn)題的最優(yōu)解發(fā)生

27、變化，如何求出新的最優(yōu)解第5節(jié) 靈敏度分析靈敏度分析的具體解決問(wèn)題：右端項(xiàng)bi的變化分析目標(biāo)系數(shù)cj的變化分析約束系數(shù)aij的變化分析增加變量的變化分析增加約束條件的變化分析說(shuō)明：靈敏度分析的具體解決問(wèn)題以例1為例討論變化過(guò)程第5節(jié) 靈敏度分析線性規(guī)劃問(wèn)題 其最優(yōu)單純形表如下所示： max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0jc j右端項(xiàng)b2變化目標(biāo)系數(shù)c2變化

28、約束系數(shù)a1j變化增加變量x變化第5節(jié) 靈敏度分析三、靈敏度分析的步驟1、將參數(shù)的改變計(jì)算反映到最終單純形表上來(lái)2、用高斯消去法把單純形表格變成恰當(dāng)?shù)男问剑椿兞吭谒诜匠讨械南禂?shù)為1，而在其他方程中的系數(shù)為0，得到一個(gè)基解3、可行性檢驗(yàn)，檢驗(yàn)單純形表中b列數(shù)字是否都為非負(fù)4、最優(yōu)性檢驗(yàn)，檢驗(yàn)單純形表中所有非基變量檢驗(yàn)數(shù)是否都為非正5、只要可行性檢驗(yàn)和最優(yōu)性檢驗(yàn)有一個(gè)未通過(guò)，就以此單純形表作為初始單純形表進(jìn)行迭代第5節(jié) 靈敏度分析繼續(xù)迭代的具體處理方法：若可行性和最優(yōu)性同時(shí)滿足，則最優(yōu)解不變?nèi)魸M足可行性而不滿足最優(yōu)性，則用單純形法繼續(xù)迭代求最優(yōu)解若滿足最優(yōu)性而不滿足可行性，則用對(duì)偶單純形法繼

29、續(xù)迭代求最優(yōu)解若可行性和最優(yōu)性同時(shí)不滿足，則引入人工變量，編制新的單純形表，求最優(yōu)解可行性檢驗(yàn)最優(yōu)性檢驗(yàn)結(jié)論或繼續(xù)迭代的處理方法所有bi0所有j 0最優(yōu)解不變所有bi0所有j 0用單純形法繼續(xù)迭代求最優(yōu)解所有bi 0所有j 0用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解所有bi 0所有j 0引入人工變量，編制新的單純形表求最優(yōu)解第5節(jié) 靈敏度分析靈敏度分析之一：右端項(xiàng)bi的變化分析內(nèi)容：右端項(xiàng)bi發(fā)生變化時(shí)（原線性規(guī)劃問(wèn)題中其他系數(shù)不變），最優(yōu)基B是否改變；或者為使最優(yōu)基不變，右端項(xiàng)bi的允許變化范圍。方法：右端項(xiàng)bi的變化反映到最終單純形表上，只引起b列數(shù)字的變化（滿足最優(yōu)性）：若滿足可行性，則最優(yōu)解不變

30、；若不滿足可行性，則用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解第5節(jié) 靈敏度分析例17：在例1中，（1）右端項(xiàng)b2在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變；（2）右端項(xiàng)b2由8變?yōu)?2，最優(yōu)解有什么變化？第5節(jié) 靈敏度分析靈敏度分析之二：目標(biāo)系數(shù)cj的變化分析非基變量目標(biāo)系數(shù)cj的變化當(dāng)最優(yōu)單純形表中非基變量的目標(biāo)系數(shù)變化時(shí)，只影響該非基變量檢驗(yàn)數(shù)的變化，而不影響其他檢驗(yàn)數(shù)。基變量目標(biāo)系數(shù)cj的變化當(dāng)最優(yōu)單純形表中基變量的目標(biāo)系數(shù)變化時(shí)，最優(yōu)解中CB相應(yīng)的發(fā)生變化，則影響各非基變量檢驗(yàn)數(shù)。第5節(jié) 靈敏度分析例18：線性規(guī)劃問(wèn)題 max z =6x1+30 x2+13x3 0.5x1+4x2+x324 x1+4x2+

31、4x360 x1，x2，x30其最優(yōu)單純形表如下所示。（1）目標(biāo)系數(shù)c2在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變；（2）目標(biāo)系數(shù)c2由60變?yōu)?0，最優(yōu)解有什么變化？ 6 30 13 0 0CBxBb x1 x2 x3 x4 x5613x1x3366 1 12 1 3 -1 0 -2 0 -1 1/2 0 -16 0 -11 -1/2jc j非基變量第5節(jié) 靈敏度分析例19：在例1中，（1）目標(biāo)系數(shù)c2在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變；（2）目標(biāo)系數(shù)c2由3變?yōu)?，最優(yōu)解有什么變化？基變量第5節(jié) 靈敏度分析靈敏度分析之三：約束系數(shù)aij的變化分析非基變量約束系數(shù)aij的變化當(dāng)最優(yōu)單純形表中非基變量的約束系

32、數(shù)變化時(shí)，只影響該非基變量檢驗(yàn)數(shù)的變化，而不影響其他檢驗(yàn)數(shù)?；兞考s束系數(shù)aij的變化當(dāng)最優(yōu)單純形表中基變量的約束系數(shù)變化時(shí)，影響最優(yōu)單純形表中幾乎所有的位置。第5節(jié) 靈敏度分析例20：已知線性規(guī)劃問(wèn)題 max z =2x1+5x2+x3+4x4 4x1+3x2+0.5x3+2x48 8x1+4x2+7x3+4x412 7x1+4x2+9x3+3x410 x1-40的最優(yōu)單純形表如下所示。 2 5 1 4 0 0 0CBxBb x1 x2 x3 x4 x5 x6 x7045x5x4 x2121-1 0 27/4 0 1 1/4 -1 1 0 -2 1 0 1 -1 1 1 15/4 0 0 -3/4 1-7 0 -39/4 0 0 -1/4 -1jc j非基變量487 487 362 （1）x1的約束系數(shù) 在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變；（2） x1的約束系數(shù)由 變?yōu)?，最優(yōu)解有什么變化？增加約束條件的變化第5節(jié) 靈敏度分析例21：在例1中，基變量11124502144502xx （1） 的約束系數(shù)由變?yōu)闀r(shí)，最優(yōu)解有什么變化？（2） 的約束系數(shù)由變?yōu)闀r(shí)，最優(yōu)解有什么變化？第5節(jié) 靈敏度分析靈敏度分析之四：增加變量的變化分析方法：在原問(wèn)題的最優(yōu)單純形表中增加一列，計(jì)算檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)0，則原問(wèn)題最優(yōu)解不變，否則，以該增加變量為換入變量，用單純形法繼續(xù)迭代求最