[經(jīng)濟(jì)學(xué)]第二章new 對偶理論與靈敏度分析ppt課件

1、Chapter 2對偶實際與靈敏度分析對偶實際與靈敏度分析上海工程技術(shù)大學(xué)上海工程技術(shù)大學(xué)管理學(xué)院管理學(xué)院Chapter 2 靈敏度分析靈敏度分析 對偶問題提出對偶問題提出問題一：某公司在方案期內(nèi)要安排消費問題一：某公司在方案期內(nèi)要安排消費I、 II兩種產(chǎn)兩種產(chǎn)品，知消費單位產(chǎn)品所需的設(shè)備臺時及品，知消費單位產(chǎn)品所需的設(shè)備臺時及A B兩種兩種原資料的耗費如表所示，該工廠每消費一件產(chǎn)品原資料的耗費如表所示，該工廠每消費一件產(chǎn)品I可獲利可獲利2元，每消費一件產(chǎn)品元，每消費一件產(chǎn)品II可獲利可獲利3元，問應(yīng)元，問應(yīng)該如何安排方案使該工廠獲利最多？該如何安排方案使該工廠獲利最多？ 如何安排方案？如何安

2、排方案？舉例Chapter 2 靈敏度分析靈敏度分析 先根據(jù)圖表來列出模型 Max Z= 2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1, X2 0 舉例我們從另一個角度來討論這個問題我們從另一個角度來討論這個問題.假設(shè)該工假設(shè)該工廠的決策者決議不消費產(chǎn)品廠的決策者決議不消費產(chǎn)品I II，而將其一，而將其一切資源出租或外售切資源出租或外售.這時工廠的決策者就要這時工廠的決策者就要思索給每種資源如何定價的問題思索給每種資源如何定價的問題.設(shè)用設(shè)用Y1, Y2, Y3分別表示出租單位設(shè)備臺時的租金分別表示出租單位設(shè)備臺時的租金和出讓單位原資料和出讓單位原資料A,B的附加額的附加

3、額.從工廠決策者的角度來看從工廠決策者的角度來看f f當(dāng)然是越大越好當(dāng)然是越大越好, ,但從接受者目光來說但從接受者目光來說f f是越少越好是越少越好, ,所以工所以工廠決策者只可以在滿足廠決策者只可以在滿足 一切產(chǎn)品的利一切產(chǎn)品的利潤條件下潤條件下, ,使其總收入盡能夠的小使其總收入盡能夠的小. .因此可因此可以列出如下線性規(guī)劃問題以列出如下線性規(guī)劃問題 min f= min f= 8Y1+16Y2+12Y38Y1+16Y2+12Y3 Y1+4Y2 2Y1+4Y2 2 2Y1+4Y3 32Y1+4Y3 3 Yi 0, Yi 0, i = 1,2,3 i = 1,2,3 Chapter 2 靈

4、敏度分析靈敏度分析v 各模型中有關(guān)數(shù)據(jù)的各模型中有關(guān)數(shù)據(jù)的“位置表示圖如下。位置表示圖如下。 v由上面的例子我們可以知道原問題與由上面的例子我們可以知道原問題與對偶問題的關(guān)系對偶問題的關(guān)系v1線性規(guī)劃問題是對稱方式線性規(guī)劃問題是對稱方式v Max z = CX Min f = Ybv s.t. Ax b s.t. YA cv x 0 y 0 v “Max - “Min- 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW對對偶偶問問題題：

5、Chapter 2 靈敏度分析靈敏度分析v如上面例題所示一對對稱方式的對偶規(guī)劃如上面例題所示一對對稱方式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系之間具有下面的對應(yīng)關(guān)系v(1)假設(shè)一個模型為目的求假設(shè)一個模型為目的求“極大，約束為極大，約束為“小于等于的不等式，那么它的對偶模型小于等于的不等式，那么它的對偶模型為目的求為目的求“極小，約束是極小，約束是“大于等于的大于等于的不等式。即不等式。即“max，和和“min，相對應(yīng)。相對應(yīng)。(2)從約束系數(shù)矩陣看：一個模型中為，那從約束系數(shù)矩陣看：一個模型中為，那么另一個模型中為么另一個模型中為AT。一個模型是。一個模型是m個約個約束，束，n個變量，那么它的對偶

6、模型為個變量，那么它的對偶模型為n個約個約束，束，m個變量。個變量。(3)從數(shù)據(jù)從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，的位置看：在兩個規(guī)劃模型中，b和和C的位置對換。的位置對換。(4)兩個規(guī)劃模型中的變量皆非負(fù)。兩個規(guī)劃模型中的變量皆非負(fù)。Chapter 2 靈敏度分析靈敏度分析v然而在普通線性規(guī)劃問題中遇到非對稱方然而在普通線性規(guī)劃問題中遇到非對稱方式時我們的處置如下：式時我們的處置如下：v 非對稱方式的對偶規(guī)劃非對稱方式的對偶規(guī)劃普通稱不具普通稱不具有對稱方式的一對線性規(guī)劃為非對稱方式有對稱方式的一對線性規(guī)劃為非對稱方式的對偶規(guī)劃。的對偶規(guī)劃。v對于非對稱方式的規(guī)劃，可以按照下面的對于非

7、對稱方式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系直接給出其對偶規(guī)劃。對應(yīng)關(guān)系直接給出其對偶規(guī)劃。v1將模型一致為將模型一致為“max，或或“min， 的方式，對于其中的等式約束按下面的方式，對于其中的等式約束按下面2、3中的方法處置；中的方法處置；2假設(shè)原規(guī)劃的某個約束條件為等式約束，假設(shè)原規(guī)劃的某個約束條件為等式約束，那么在對偶規(guī)劃中與此約束對應(yīng)的那個變那么在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負(fù)限制；量取值沒有非負(fù)限制；3假設(shè)原規(guī)劃的某個變量的值沒有非負(fù)限假設(shè)原規(guī)劃的某個變量的值沒有非負(fù)限制，那么在對偶問題中與此變量對應(yīng)的那制，那么在對偶問題中與此變量對應(yīng)的那個約束為等式。個約束為等式。Cha

8、pter 2 靈敏度分析靈敏度分析v非對稱型對偶問題非對稱型對偶問題 0XbAX max CXZP矩矩陣陣形形式式： 無無符符號號限限制制（無無約約束束） min YCYAYbWDChapter 2 靈敏度分析靈敏度分析舉例 0,5643732532432max321321321321321xxxxxxxxxxxxxxxZ Chapter 2 靈敏度分析靈敏度分析 無無約約束束解解：對對偶偶問問題題為為 ,467534 3 2 32 532min 321321321321321yyyyyyyyyyyyyyyW原問題（或?qū)ε紗栴}）原問題（或?qū)ε紗栴}）對偶問題（或原問題）對偶問題（或原問題）目標(biāo)函

9、數(shù)目標(biāo)函數(shù) max目標(biāo)函數(shù)目標(biāo)函數(shù) min約約束束條條件件m個個m個個變變量量0 00= =無約束無約束變變量量n個個n個個約約束束條條件件0 00 0無約束無約束= =約束條件右端項約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項約束條件右端項Chapter 2 靈敏度分析靈敏度分析 小練習(xí)寫出以下問題的對偶問題寫出以下問題的對偶問題Chapter 2 靈敏度分析靈敏度分析對偶問題的根本性質(zhì)對偶問題的根本性質(zhì) 性質(zhì)性質(zhì)1:對稱性對稱性規(guī)范原始，對偶問題的對偶是原問題。規(guī)范原始，對偶問題的對偶是原問題。 Max z = CX Min f =

10、Yb s.t. AX b s.t. YA C X 0 Y 0 “Max - “Min- Chapter 2 靈敏度分析靈敏度分析性質(zhì)性質(zhì)2:2:弱對偶原理弱對偶性：設(shè)弱對偶原理弱對偶性：設(shè) 和和 分別是分別是 問題問題P P和和D D的可行解，那么必有的可行解，那么必有_X_Y njmiiijjbyxcbYXC11_ , 即即性質(zhì)性質(zhì)3:無界性無界性假設(shè)原問題對偶問題的解為無界解，那假設(shè)原問題對偶問題的解為無界解，那么其對偶問題原問題無可行解。無么其對偶問題原問題無可行解。無界性界性性質(zhì)性質(zhì)4:可行解是最優(yōu)解的性質(zhì)：可行解是最優(yōu)解的性質(zhì)：假設(shè)假設(shè) X* 和和 Y* 分別是分別是 P 和和 D

11、的可行解且的可行解且 CX* = Y* b，那么那么X*. Y*分別是問題分別是問題 P和和D 的最優(yōu)解。的最優(yōu)解。Chapter 2 靈敏度分析靈敏度分析性質(zhì)性質(zhì)5:5:對偶定理對偶定理假設(shè)原問題有最優(yōu)解，那么對偶問題也有最假設(shè)原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且二者最優(yōu)值相等。強(qiáng)對偶性優(yōu)解，而且二者最優(yōu)值相等。強(qiáng)對偶性性質(zhì)性質(zhì)6:6:互補(bǔ)松弛定理互補(bǔ)松弛定理設(shè)設(shè)X X* *和和Y Y* *分別是問題分別是問題 P P 和和 D D 的可行解，那的可行解，那么它們分別是最優(yōu)解的充要條件是么它們分別是最優(yōu)解的充要條件是剩剩余余變變量量或或或或ssssYXXYXCAYXYAXbY.00)

12、(00)( 同時成立同時成立Chapter 2 靈敏度分析靈敏度分析例題判別下例說法能否正確，為什么？例題判別下例說法能否正確，為什么？ A 假設(shè)線性規(guī)劃的原問題存在可行解，那么其假設(shè)線性規(guī)劃的原問題存在可行解，那么其對偶對偶 問題也一定存在可行解問題也一定存在可行解 B 假設(shè)線性規(guī)劃的對偶問題無可行解，那么原假設(shè)線性規(guī)劃的對偶問題無可行解，那么原問題也一定無可行解。問題也一定無可行解。 C 在互為對偶的一對原問題和對偶問題中，不在互為對偶的一對原問題和對偶問題中，不論原問題是求極大或者極小，原問題可行解的目論原問題是求極大或者極小，原問題可行解的目的函數(shù)值都一定不超越其對偶問題可行解的目的的

13、函數(shù)值都一定不超越其對偶問題可行解的目的函數(shù)值。函數(shù)值。 Chapter 2 靈敏度分析靈敏度分析v解：解：vA不對。由于原問題為無界解時它當(dāng)然有可行不對。由于原問題為無界解時它當(dāng)然有可行解，其對偶問題無可行解。解，其對偶問題無可行解。vB此句為此句為A的逆否命題，所以也不對。的逆否命題，所以也不對。vC不對。由于哪個問題是原問題，哪個問題是對不對。由于哪個問題是原問題，哪個問題是對偶問題是相對而言的。偶問題是相對而言的。 Chapter 2 靈敏度分析靈敏度分析例題例題: :知原問題的最優(yōu)解為知原問題的最優(yōu)解為X X* * = =0,0,40,0,4，Z=12,Z=12,試求對偶問題的最優(yōu)解

14、。試求對偶問題的最優(yōu)解。 無無約約束束321321321321321,0,04 16 3253234maxxxxxxxxxxxxxxxxZChapter 2 靈敏度分析靈敏度分析 無無約約束束321321321321321,0,03654 3 132 42minyyyyyyyyyyyyyyyW解解: :將將X X* * = =0 , 0 , 40 , 0 , 4代入原問題中，有下式：代入原問題中，有下式：Chapter 2 靈敏度分析靈敏度分析 4 4 1 246 32 20532321321321xxxxxxxxx所以，根據(jù)互補(bǔ)松弛條件，必有所以，根據(jù)互補(bǔ)松弛條件，必有y y* *1= y1

15、= y* *2=02=0，代入對偶問題代入對偶問題 3 3式，式， y3 =3 y3 =3。因此，對偶。因此，對偶問題的最優(yōu)解為問題的最優(yōu)解為 Y Y* *= =0 . 0 . 30 . 0 . 3，W=12W=12。第二節(jié)第二節(jié) 影子價錢影子價錢Chapter 2 靈敏度分析靈敏度分析第三節(jié)第三節(jié) 對偶單純形法對偶單純形法對偶單純形法是求解線性規(guī)劃的另一的對偶單純形法是求解線性規(guī)劃的另一的根本方法。它是根據(jù)對偶原理和單純根本方法。它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的，因此稱為形法的原理而設(shè)計出來的，因此稱為對偶單純形法。對偶單純形法并不是對偶單純形法。對偶單純形法并不是求解對偶問題解

16、的方法，而是利用對求解對偶問題解的方法，而是利用對偶實際求解原問題的解的方法。偶實際求解原問題的解的方法。由單純形方法，我們可以得到，由單純形方法，我們可以得到，LPLP問題問題的最優(yōu)解應(yīng)該是可行的；的最優(yōu)解應(yīng)該是可行的； 最優(yōu)的；最優(yōu)的；由對偶性可知，由對偶性可知， LP LP問題的最優(yōu)性相當(dāng)問題的最優(yōu)性相當(dāng)于于DLPDLP的可行性，的可行性， LP LP問題的可行性相問題的可行性相當(dāng)于當(dāng)于DLPDLP的最優(yōu)性的最優(yōu)性. .(3) 對偶單純形法因此單純形方法可以解釋為它是在堅持一個原因此單純形方法可以解釋為它是在堅持一個原始問題可行解的前提下，向?qū)ε伎尚薪獾姆较蚴紗栴}可行解的前提下，向?qū)ε伎?/p>

17、行解的方向迭代迭代. .原始算法原始算法我們可以從一個對偶可行解開場，堅持對偶問我們可以從一個對偶可行解開場，堅持對偶問題的可行性，向原始可行解的方向迭代題的可行性，向原始可行解的方向迭代 對偶單純形法對偶單純形法0jjjzc01bBb對偶問題的可行解對偶問題的可行解對偶問題對偶問題最優(yōu)解判別最優(yōu)解判別 也就是說，求解原問題也就是說，求解原問題P P時，可以從時，可以從P P的一的一個根本解非基可行解開場，逐漸迭代，使目的函個根本解非基可行解開場，逐漸迭代，使目的函數(shù)值數(shù)值Z=Y b= CB B-1b =CXZ=Y b= CB B-1b =CX減少，當(dāng)?shù)綔p少，當(dāng)?shù)絏B=B-1b0XB=

18、B-1b0時，即找到了時，即找到了P P的最優(yōu)解，這就是對偶的最優(yōu)解，這就是對偶單純形法。單純形法。 同原始單純形求法一樣，求解對偶問題同原始單純形求法一樣，求解對偶問題D D，也可，也可以從以從D D的一個根本可行解開場，從一個根本可行解的一個根本可行解開場，從一個根本可行解迭代到另一個根本可行解，使目的函數(shù)值減少。迭代到另一個根本可行解，使目的函數(shù)值減少。4 對偶單純形法對偶單純形法對偶單純形法的根本思緒是：對偶單純形法的根本思緒是： 在迭代過程中，一直堅持對偶問題解的可行性，而原問題的解由不可行逐漸向可行性轉(zhuǎn)化，一旦原問題的解也滿足了可行性條件,也就到達(dá)了最優(yōu)解。也即在堅持正那么解的正那

19、么性不變條件下，在迭代過程中，使原問題解的不可行性逐漸消逝，一旦迭代到可行解時，即到達(dá)了最優(yōu)解。v這樣的優(yōu)點在于，這樣的優(yōu)點在于，v一是當(dāng)問題的模型中存在一是當(dāng)問題的模型中存在“=的約束條件時，的約束條件時，不需求引入人工變量，只需在約束條件方程的兩不需求引入人工變量，只需在約束條件方程的兩邊乘以邊乘以“-1后參與松弛變量，再按單純形法求解。后參與松弛變量，再按單純形法求解。v二是當(dāng)約束條件方程個數(shù)二是當(dāng)約束條件方程個數(shù)m大于變量個數(shù)大于變量個數(shù)n的時候，的時候，將原問題變換成對偶問題求解，計算量普通會小將原問題變換成對偶問題求解，計算量普通會小些。些。Chapter 2 靈敏度分析靈敏度分析

20、對偶單純形法求解線性規(guī)劃問題過程：對偶單純形法求解線性規(guī)劃問題過程： 1.建立初始對偶單純形表建立初始對偶單純形表,對應(yīng)一個根本解對應(yīng)一個根本解,一切檢驗數(shù)均非正一切檢驗數(shù)均非正 ,轉(zhuǎn)轉(zhuǎn)2； 2.假設(shè)假設(shè)b0,那么得到最優(yōu)解那么得到最優(yōu)解,停頓停頓; 3.假設(shè)有假設(shè)有bi0,換出變量：設(shè)換出變量：設(shè)minbi|bi0=bk,，那么選，那么選k行行的基變量為換出變量的基變量為換出變量,轉(zhuǎn)轉(zhuǎn)40j 4. 4.假設(shè)一切假設(shè)一切akj0( j = akj0( j = 1,2,n )1,2,n )，那么原問題無可行解，那么原問題無可行解, ,停停頓頓; ;否那么否那么, ,假設(shè)有假設(shè)有akj0 akj0

21、 那么選那么選 =min=min j / j / akjakj0=akjakj0brMin-bi/airair0Chapter 2 靈敏度分析靈敏度分析例題: Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0Chapter 2 靈敏度分析靈敏度分析C i23000CBX BBX 1X 2X 3X 4X 52 X 141001 /400 X 5400-21 /213 X 22011 /2-1 /80j00-1 .5-1

22、/80最終單純形表為最終單純形表為: 0 0.25 0 這里 B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對應(yīng)各列分別對應(yīng) b1 b1、b2b2、b3 b3 的單一變化的單一變化因此，設(shè)因此，設(shè) b1 b1 添加添加 4 4，那么，那么 x1 ,x5 ,x2 x1 ,x5 ,x2分別變?yōu)椋悍謩e變?yōu)椋?+04+04=4, 4+(-2)4=4, 4+(-2)4=-40, 2+0.54=-40asj0 csMincsMin j/asjj/asjasj0 asj0 v Chapter 2 靈敏度分析靈敏度分析例題例題: : Max z = 2x1 + 3x2 + 0 x3 + 0

23、x4+ 0 x5 Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 s.t. x1 + 2x2 + x3 = 8 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x1 + x4 = 16 4x2 + x5 = 12 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0 x1 , x2 , x3 , x4 , x5 0下表為最優(yōu)單純形表下表為最優(yōu)單純形表,思索基變量系數(shù)思索基變量系數(shù)c2發(fā)生變化發(fā)生變化 Chapter 2 靈敏度分析靈敏度分析C i23000CBXBBX1X2X3X4X52 X141001/400 X

24、5400-21/213 X22011/2-1/80j00-1.5-1/80Ci23+ C2000CBXBBX1X2X3X4X52 X141001/400 X5400-21/213+ C2 X22011/2-1/80j00-1.5 - C2/2-1/8+ C2/80從表中可得到從表中可得到 -3c21 -3c21時，原最優(yōu)解時，原最優(yōu)解不變。不變。例：某企業(yè)利用三種資源消費兩種產(chǎn)品的最優(yōu)方案例：某企業(yè)利用三種資源消費兩種產(chǎn)品的最優(yōu)方案問題歸結(jié)為以下線性規(guī)劃問題歸結(jié)為以下線性規(guī)劃 0,45 802903 45 max2121212121xxxxxxxxxxZ知最優(yōu)表如下。知最優(yōu)表如下。1 1確定確

25、定x2x2的系數(shù)的系數(shù)c2c2的變化范圍，使原最優(yōu)的變化范圍，使原最優(yōu)解堅持最優(yōu)；解堅持最優(yōu)；2 2假設(shè)假設(shè)c2=6c2=6，求新，求新的最優(yōu)方案。的最優(yōu)方案。 一、 價值系數(shù)cj的變化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3 0,45 802903 45 max2121212121xxxxxxxxxxZ4 = c25 05 = 52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2 - 55 - 2c2最優(yōu)解最優(yōu)解X X* *= =3535，1010，2525，0 0，0 0堅