本科-對(duì)偶理論敏感分析

1、線性規(guī)劃線性規(guī)劃 Linear Programming（LP）第二章第二章線性規(guī)劃的對(duì)偶理論與線性規(guī)劃的對(duì)偶理論與靈敏度分析靈敏度分析線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃對(duì)偶理論線性規(guī)劃對(duì)偶理論線性規(guī)劃線性規(guī)劃 Linear Programming（LP）第第1節(jié)單純形法的矩陣描述節(jié)單純形法的矩陣描述設(shè)線性規(guī)劃問(wèn)題設(shè)線性規(guī)劃問(wèn)題 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I 式式） X 0 X ，XS 0其中其中 b 0 ，I 是是 mm 單位單位矩陣。矩陣。對(duì)上面對(duì)上面（I 式式）經(jīng)過(guò)

2、迭代，并設(shè)最終的最優(yōu)基矩陣為經(jīng)過(guò)迭代，并設(shè)最終的最優(yōu)基矩陣為B（不妨設(shè)（不妨設(shè)B 為為A 的的首首m 列，則將（列，則將（I 式式）改寫后有）改寫后有線性規(guī)劃線性規(guī)劃 Linear Programming（LP）max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0 max Z = CB B -1 b+(CN- CB B -1N)XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0 B 式中式中最優(yōu)最優(yōu)目標(biāo)函數(shù)值目標(biāo)函數(shù)值Z*= CB B -1 b，檢驗(yàn)

3、數(shù)，檢驗(yàn)數(shù) CN - CB B -1 N 0 ， - CB B -1 0單純形方法迭代單純形方法迭代（I 式）式）（B 式式）線性規(guī)劃線性規(guī)劃 Linear Programming（LP）單純形方法的矩陣描述：?jiǎn)渭冃畏椒ǖ木仃嚸枋觯夯饨?XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN - CB B 1N - CB B -1對(duì)應(yīng)對(duì)應(yīng)I 式式的的單純形表單純形表 I 表表對(duì)應(yīng)對(duì)應(yīng)B 式式的的單純形表單純形表 B 表表迭代l練習(xí)：P73頁(yè)習(xí)題2.2的位置。就是置經(jīng)過(guò)迭代運(yùn)算后注：初始單位矩陣的位1-B線性

4、規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃線性規(guī)劃 Linear Programming（LP）第第3節(jié)對(duì)偶問(wèn)題的提出節(jié)對(duì)偶問(wèn)題的提出 對(duì)偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問(wèn)題對(duì)偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問(wèn)題結(jié)構(gòu)的重要理論基礎(chǔ)。同時(shí)，由于問(wèn)題提出本身所具有的經(jīng)濟(jì)意義，使得結(jié)構(gòu)的重要理論基礎(chǔ)。同時(shí)，由于問(wèn)題提出本身所具有的經(jīng)濟(jì)意義，使得它成為對(duì)線性規(guī)劃問(wèn)題系統(tǒng)進(jìn)行經(jīng)濟(jì)分析和敏感性分析的重要工具。那么，它成為對(duì)線性規(guī)劃問(wèn)題系統(tǒng)進(jìn)行經(jīng)濟(jì)分析和敏感性分析的重要工具。那么，對(duì)偶問(wèn)題是怎樣提出的，為什么會(huì)產(chǎn)生這樣一種問(wèn)題呢？對(duì)偶問(wèn)題是

5、怎樣提出的，為什么會(huì)產(chǎn)生這樣一種問(wèn)題呢？且看下面詳解且看下面詳解線性規(guī)劃線性規(guī)劃 Linear Programming（LP）引例引例倆家具制造商間的對(duì)話：倆家具制造商間的對(duì)話：唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋樣？?jī)r(jià)格嘛用。咋樣？?jī)r(jià)格嘛好說(shuō)，好說(shuō)，肯定不會(huì)讓您兄弟吃虧訕?？隙ú粫?huì)讓您兄弟吃虧訕。 王老板做家具賺了王老板做家具賺了 大錢，可惜我老李有大錢，可惜我老李有 高科技產(chǎn)品，卻苦于沒(méi)有高科技產(chǎn)品，卻苦于沒(méi)有足夠的木工和油漆工足夠的木工和油漆工 咋辦？只有租咯。咋辦？只有租咯。Hi：王老板，聽(tīng)說(shuō)：王老板，聽(tīng)說(shuō)近來(lái)家具生意好慘了，近來(lái)家具生意好慘了，也幫幫兄弟我哦也

6、幫幫兄弟我哦! 家具生意還真賺錢，但家具生意還真賺錢，但 是現(xiàn)在的手機(jī)生意這么好，是現(xiàn)在的手機(jī)生意這么好， 不如干脆把我的木工和油漆不如干脆把我的木工和油漆工租給他，又能工租給他，又能收租金又可做生意。收租金又可做生意。價(jià)格嘛價(jià)格嘛好商量，好商量， 好商量。只是好商量。只是. 王王 老老 板板李李 老老 板板線性規(guī)劃線性規(guī)劃 Linear Programming（LP）王老板的王老板的家具生產(chǎn)模型家具生產(chǎn)模型：x1 、 x2是桌、椅生產(chǎn)量。是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤(rùn)）。是家具銷售總收入（總利潤(rùn)）。max Z = 50 x1 + 30 x2s.t. 4x1+3x2 120（木工）

7、木工） 2x1+ x2 50 （油漆工）（油漆工） x1，x2 0原始線性規(guī)劃問(wèn)題，記為（原始線性規(guī)劃問(wèn)題，記為（LP）王老板的王老板的資源出租模型資源出租模型：y1、 y2單位木、漆工出租價(jià)格。單位木、漆工出租價(jià)格。W是資源出租租金總收入。是資源出租租金總收入。min W =120y1 + 50y2s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0對(duì)偶線性規(guī)劃問(wèn)題，記為（對(duì)偶線性規(guī)劃問(wèn)題，記為（DLP）線性規(guī)劃線性規(guī)劃 Linear Programming（LP）王老板按（王老板按（DLP）的解）的解 y1 、y2出租其擁有的木、漆工資源，既保證了自己出租其擁有的木、漆工資

8、源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時(shí)的銷售收入），又使得出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金出租價(jià)格對(duì)李老板有極大的吸引力（李老板所付出的總租金W最少）。最少）。 0, 502 1203 4 . 3050max 21212121xxxxxxtsxxZ ( LP) (DLP)1 23 41A、系數(shù)矩陣1 32 4TA2、價(jià)值系數(shù)資源系數(shù)3、資源系數(shù)價(jià)值系數(shù)4、約束方程 約束方程 5、目標(biāo)函數(shù) max目標(biāo)函數(shù) min0,3035024. .50120min21212121yyyyyytsyyW原

9、始問(wèn)題max z=CXs.t.AXbX 0對(duì)偶問(wèn)題min w=Ybs.t. YACY 0maxbACCTATbminmnmn(LP)(DLP)第第4節(jié)線性規(guī)劃的對(duì)偶理論節(jié)線性規(guī)劃的對(duì)偶理論線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)稱形式下對(duì)偶問(wèn)題的一般形式對(duì)稱形式下對(duì)偶問(wèn)題的一般形式 項(xiàng)目項(xiàng)目原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題AbC目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件決策變量決策變量約束系數(shù)矩陣約束系數(shù)矩陣約束條件的右端項(xiàng)向量約束條件的右端項(xiàng)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量max Z = CXAX bX 0其約束系數(shù)矩陣的轉(zhuǎn)

10、置其約束系數(shù)矩陣的轉(zhuǎn)置目標(biāo)函數(shù)中的價(jià)格系數(shù)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束條件的右端項(xiàng)向量約束條件的右端項(xiàng)向量min W = YbYA CY 0線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 非對(duì)稱形式下對(duì)偶問(wèn)題的一般形式非對(duì)稱形式下對(duì)偶問(wèn)題的一般形式 原始（原始（對(duì)偶對(duì)偶）對(duì)偶（）對(duì)偶（原始原始）關(guān)系表關(guān)系表項(xiàng)目項(xiàng)目原問(wèn)題原問(wèn)題（對(duì)偶問(wèn)題）（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題對(duì)偶問(wèn)題（原問(wèn)題）（原問(wèn)題）目標(biāo)函數(shù)類型目標(biāo)函數(shù)類型maxmin目標(biāo)函數(shù)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)目標(biāo)函數(shù)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系關(guān)系約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的

11、系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)原問(wèn)題變量個(gè)數(shù)、類型與對(duì)偶原問(wèn)題變量個(gè)數(shù)、類型與對(duì)偶問(wèn)題約束條件個(gè)數(shù)、類型的對(duì)問(wèn)題約束條件個(gè)數(shù)、類型的對(duì)應(yīng)關(guān)系應(yīng)關(guān)系 n個(gè)個(gè) 0變量變量 0 自由自由 n個(gè)個(gè) 約束條件約束條件 =原問(wèn)題約束條件個(gè)數(shù)、類型與原問(wèn)題約束條件個(gè)數(shù)、類型與對(duì)偶問(wèn)題變量個(gè)數(shù)類型的對(duì)應(yīng)對(duì)偶問(wèn)題變量個(gè)數(shù)類型的對(duì)應(yīng)關(guān)系關(guān)系 m個(gè)個(gè) 約束條件約束條件 =m個(gè)個(gè) 0 變量變量 0 自由自由 min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15=x10, x20,

12、x3無(wú)非負(fù)要求例：線性規(guī)劃線性規(guī)劃 Linear Programming（LP）min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3: unrq原始問(wèn)題變量的個(gè)數(shù)原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)； 原始問(wèn)題約束條件的個(gè)

13、數(shù)原始問(wèn)題約束條件的個(gè)數(shù)(4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(4)。q原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)，用原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)，用 表示表示 原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)，用原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)，用 表示表示原問(wèn)題對(duì)偶問(wèn)題原問(wèn)題對(duì)偶問(wèn)題l練習(xí)：P74頁(yè)2.3（1）4.2 對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì)1、對(duì)稱性對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題0 )( max XLPbAXCXz0 )( min YDLPCYAYbw0 )( - max YLPCYAYbw0 )( - min XDLPbAXCXz2、弱對(duì)偶性。

14、可行解，則有為任一對(duì)偶原問(wèn)題的任一可行解，為若XCbYYLPXbYXAYYbXA , 0,XCXAYXCAY , 0，zXCbYw 推論： 1）極大化極大化問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題 最優(yōu)值的下界。2）極小化極小化問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題 最優(yōu)值的上界。例：4 , 3 , 2 , 1, 0 (LP) 20232 20322 . 432max432143214321jxxxxxxxxxtsxxxxzj12 . 2020min2121yytsyyw2221 yy0,423332212121yyyyyy1）原問(wèn)題任一可行解 X=（1 1 1 1）（DLP）目標(biāo)值 z=101

15、0是DLP問(wèn)題最優(yōu)目標(biāo)值的下界2）對(duì)偶問(wèn)題任一可行解 Y=（1 1） 目標(biāo)值 w=40 40是LP問(wèn)題最優(yōu)目標(biāo)值的上界 28 56 5128z 4 4 0 0*wYXTl3、無(wú)界性若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。l證：由弱對(duì)偶性顯然可得。l注：這個(gè)性質(zhì)的逆命題不成立，即當(dāng)原問(wèn)題（對(duì)偶問(wèn)題）無(wú)可行解時(shí)，其對(duì)偶問(wèn)題（原問(wèn)題）或具有無(wú)界解或無(wú)可行解。線性規(guī)劃線性規(guī)劃 Linear Programming（LP）最優(yōu)解。為最優(yōu)解，為，則且的可行解和對(duì)偶可行解分別為和若、最優(yōu)性DLPYLPXbYXCLPYX 4XCbYCXX ,由弱對(duì)偶性證明：對(duì)任意可行解為最優(yōu)解則有XXC

16、CX為對(duì)偶最優(yōu)解解同理，對(duì)任意對(duì)偶可行YbYbYbYXCbYY ,原始對(duì)偶問(wèn)題目標(biāo)值之間的關(guān)系1、可行解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)X、Y分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解z=CX YAX Yb=w2、最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)X*、Y*分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解 z=CX*=Y*AX*=Y*b=w5、對(duì)偶定理： 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。為原問(wèn)題的最優(yōu)解證明：設(shè)*X0,*1*YCAYBCYB，得令為最優(yōu)基）（則BABCCB 0I 0 100 011BCABCCBB，即：為對(duì)偶可行解，得*YbBCbYwB1*（松弛變量檢驗(yàn)數(shù)的相反數(shù)松弛變量檢驗(yàn)數(shù)的相反

17、數(shù)）對(duì)偶可行對(duì)偶可行最優(yōu)性最優(yōu)性代入目標(biāo)函數(shù)為對(duì)偶最優(yōu)解*YXCBss6.X,YYX0YX0X,Y互補(bǔ)松馳性：若分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解。那么和當(dāng)且僅當(dāng)為最優(yōu)解。min w=Ybs.t. YA-YS=C Y, YS0max z=CXs.t. AX+XS=b X, XS0min w=Ybs.t. YAC X 0max z=CXs.t. AXb X0對(duì)偶引進(jìn)松弛變量引進(jìn)剩余變量YSX=0, YXS=0互補(bǔ)松弛關(guān)系X，XsY，Ysl練習(xí)：P90頁(yè)3.8小結(jié)原問(wèn)題原問(wèn)題(max) 對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系 對(duì)偶問(wèn)題對(duì)偶問(wèn)題(min) 有最優(yōu)解有最優(yōu)解無(wú)界解不可行不可行無(wú)界解0, 1- (LP) 1 .

18、max 12122112121xxlxxlxxtsxxz：例（無(wú)可行解）0, 1- (DLP) 1 . min2122112121yylyylyytsyyw（無(wú)可行解）0, 1 (LP) 1 . max 22122112121xxlxxlxxtsxxz：例 （無(wú)界解）0, 1 (DLP) 1 . min2122112121yylyylyytsyyw（無(wú)可行解）1,2,3 0 974 3 32max 3321321321jxxxxxxx s.t xxxzj：例 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/

19、3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8請(qǐng)確定對(duì)偶問(wèn)題的最優(yōu)解31 35*Y構(gòu)成最優(yōu)解用對(duì)偶性質(zhì)說(shuō)明）（：例4343214314321,)4 , 3 , 2 , 1( 0 12222 LP 8 2 . 652max 4xxjxxxxxxxxtsxxxxzj1222121212min812.2221526,01 2 (DLP) wyyst yyyyyyyy y2 11 1B1 1-1- 2 1B（是可行解） 441281 1-1- 2 1bBX對(duì)偶可行）( 1 41 1-1- 26) 5( 1BCYBB為最優(yōu)基目標(biāo)函數(shù)值目標(biāo)函數(shù)值相同相同(44)(44)第第5節(jié)節(jié) 對(duì)偶問(wèn)

20、題的經(jīng)濟(jì)解釋影子價(jià)格對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋影子價(jià)格一、原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題一、原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題0. .max212122112222221211112121112211mnnnnmmnnmnmmnnnnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxatsxcxcxcz單位產(chǎn)品的利潤(rùn)單位產(chǎn)品的利潤(rùn)產(chǎn)品產(chǎn)量產(chǎn)品產(chǎn)量總利潤(rùn)總利潤(rùn)資源限量資源限量單位產(chǎn)品消耗的資源單位產(chǎn)品消耗的資源剩余的資源剩余的資源消耗的資源消耗的資源二、二、對(duì)偶問(wèn)題對(duì)偶問(wèn)題0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmm

21、mmyyyyyycyyayayacyyayayacyyayayatsybybybw資源限量資源限量資源價(jià)格資源價(jià)格總利潤(rùn)總利潤(rùn)對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解y1、y2、.、ym稱為稱為m種資源的影子價(jià)格（種資源的影子價(jià)格（Shadow Price）原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，最大利潤(rùn)原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，最大利潤(rùn) max z=min w三、影子價(jià)格三、影子價(jià)格 *優(yōu)值的變化量。目標(biāo)函數(shù)最都保持不變時(shí)所產(chǎn)生的一個(gè)單位，而其他數(shù)據(jù)每增加端項(xiàng)是表示對(duì)應(yīng)約束條件右某種資源的影子價(jià)格iiby種資源的邊際利潤(rùn)第種資源的增量第最大利潤(rùn)的增量iibz

22、yii*影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子 價(jià)格一定等于價(jià)格一定等于0如果資源的影子價(jià)格大于如果資源的影子價(jià)格大于0，最優(yōu)生產(chǎn)計(jì)劃下該種資源全，最優(yōu)生產(chǎn)計(jì)劃下該種資源全部用完部用完bYAXYCXbYXAYXC* ,最優(yōu)性：弱對(duì)偶性：0)(0 00)(,0)(*iiiibAXyybAXbAXY，則若，則若第第i種資源全部用完種資源全部用完第第i種資源的影子價(jià)格大于種資源的影子價(jià)格大于0第第

23、i種資源有剩余種資源有剩余第第i種資源的影子價(jià)格為種資源的影子價(jià)格為0例：下面是一張最優(yōu)單純形表（極大化問(wèn)題，其中約束條件 均為，x4,x5,x6為松弛變量）： xB x1 x2 x3 x4 x5 x6 bx1x3x5 1 1 0 2 0 1 0 0 1 1 0 4 0 -2 0 1 1 0 2 3/2 1 j 0 0 0 -4 0 -9Z=51)寫出對(duì)偶問(wèn)題的最優(yōu)解；2)若現(xiàn)在以代價(jià)2增加第一種資源一個(gè)單位是否合算？為什么？3)是否有其它最優(yōu)解？若有，求出另一最優(yōu)解。線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法思路對(duì)偶單純形

24、法思路max Z =2x1+x2s.t. x1+ x2+ x3 = 5 2x2+ x3 5 4x2+6x3 9 x1 ，x2 ，x3 0max Z =2x1+x2s.t. x1+ x2+ x3 = 5 2x2+ x3+ x4 = 5 4x2+6x3 -x5= 9 x1 ，x2 ，x3 ， x4 ， x5 0準(zhǔn)典式：準(zhǔn)典式：max Z = -1x2 -2x3s.t. x1+ x2+ x3 = 5 2x2+ x3+ x4 = 5 - 4x2 -6x3 +x5 = -9 x1 ，x2 ，x3 ， x4 ， x5 0標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化化化典典式式準(zhǔn)典式準(zhǔn)典式1、顯含基可行解、顯含基可行解2、目標(biāo)函數(shù)中不含基

25、變量，且、目標(biāo)函數(shù)中不含基變量，且Max化目標(biāo)函數(shù)中非基變量的系化目標(biāo)函數(shù)中非基變量的系數(shù)均非正數(shù)均非正線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法思路對(duì)偶單純形法思路 對(duì)偶單純形法基本思路：對(duì)偶單純形法基本思路： 如果線性規(guī)劃原問(wèn)題標(biāo)準(zhǔn)化之后不能簡(jiǎn)單得出一個(gè)初始基可行如果線性規(guī)劃原問(wèn)題標(biāo)準(zhǔn)化之后不能簡(jiǎn)單得出一個(gè)初始基可行解（典式），但卻能容易得到該問(wèn)題的對(duì)偶問(wèn)題的一個(gè)初始基可行解（典式），但卻能容易得到該問(wèn)題的對(duì)偶問(wèn)題的一個(gè)初始基可行解（準(zhǔn)典式），此時(shí)我們就可以通過(guò)保持對(duì)偶基可行解的可行性的解（準(zhǔn)典式），此時(shí)我們就可以通過(guò)保

26、持對(duì)偶基可行解的可行性的方法進(jìn)行迭代，逐步消除原問(wèn)題基本解的不可行性，最終，當(dāng)對(duì)偶方法進(jìn)行迭代，逐步消除原問(wèn)題基本解的不可行性，最終，當(dāng)對(duì)偶基可行解迭代到對(duì)偶最優(yōu)解的同時(shí)原問(wèn)題也得到了最優(yōu)的基可行解?；尚薪獾綄?duì)偶最優(yōu)解的同時(shí)原問(wèn)題也得到了最優(yōu)的基可行解。線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法的計(jì)算方法對(duì)偶單純形法的計(jì)算方法基基解解 X1 X2 X3 X4 X5X1X4X555-9 1 1 1 0 0 0 2 1 1 0 0 -4 -6 0 1檢驗(yàn)數(shù)檢驗(yàn)數(shù) 0 -1 -2 0 0比值比值 - 1/4 1/3 - -基

27、基解解 X1 X2 X3 X4 X5X1X4X211/4 1/2 9/4 1 0 -1/2 0 1/4 0 0 -2 1 1/2 0 1 3/2 0 -1/4檢驗(yàn)數(shù)檢驗(yàn)數(shù) 0 0 -1/2 0 -1/4比值比值 迭迭代代準(zhǔn)典式：準(zhǔn)典式：max Z = -1x2 -2x3s.t. x1+ x2+ x3 = 5 2x2+ x3+ x4 = 5 - 4x2 -6x3 +x5 = -9 x1 ，x2 ，x3 ， x4 ， x5 0準(zhǔn)典式特點(diǎn)：準(zhǔn)典式特點(diǎn)：1 1、目標(biāo)函數(shù)不含基變量、目標(biāo)函數(shù)不含基變量2 2、最大化目標(biāo)函數(shù)中非基變量、最大化目標(biāo)函數(shù)中非基變量的系數(shù)均非正的系數(shù)均非正3 3、約束方程中顯含

28、基本解、約束方程中顯含基本解線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法的計(jì)算方法對(duì)偶單純形法的計(jì)算方法min W =120y1 + 50y2s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0max W = 120y1 50y2s.t. 4y1 + 2y2 y3 = 50 3y1 + y2 y4 = 30 y1 ，y2 ， y3 ， y4 0 max W = 120y1 50y2s.t. 4y1 2y2 + y3 = 50 3y1 y2 + y4 = 30 y1 ，y2 ， y3 ， y4 0 線性規(guī)劃線性規(guī)

29、劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法的計(jì)算方法對(duì)偶單純形法的計(jì)算方法max W = 120y1 50y2s.t. 4y1 2y2 + y3 = 50 3y1 y2 + y4 = 30 y1 ，y2 ， y3 ， y4 0 基基解解y1y2y3y4y3- 50- 4- 210y4- 30- 3- 101檢驗(yàn)數(shù)檢驗(yàn)數(shù) j- 120- 5000 - 120/- 4- 50/- 2-線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法的計(jì)算方法對(duì)偶單純形法的計(jì)算方法基基解解y1y2

30、y3y4y3- 50- 4- 210y4- 30- 3- 101檢驗(yàn)數(shù)檢驗(yàn)數(shù) j- 120- 5000 y22521-1/20y4- 5- 10-1/21檢驗(yàn)數(shù)檢驗(yàn)數(shù) j- 200- 250 20-50-線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論 對(duì)偶單純形法的計(jì)算方法對(duì)偶單純形法的計(jì)算方法練習(xí)練習(xí). 2.8(1)基基解解y1y2y3y4y22521- 1/20y4- 5- 10- 1/21檢驗(yàn)數(shù)檢驗(yàn)數(shù) j- 200- 250 y15101/2- 1y21501- 3/2- 2檢驗(yàn)數(shù)檢驗(yàn)數(shù) j00- 15- 20一、思路單純形法：迭代過(guò)程

31、始終保持單純形法：迭代過(guò)程始終保持B的可行性（最小的可行性（最小規(guī)則），規(guī)則）， 逐步滿足最優(yōu)性。逐步滿足最優(yōu)性。2. 對(duì)偶單純形法：迭代過(guò)程始終保持最優(yōu)性（對(duì)偶可行對(duì)偶單純形法：迭代過(guò)程始終保持最優(yōu)性（對(duì)偶可行性），再逐步滿足可行性。性），再逐步滿足可行性。二、計(jì)算步驟1. 化標(biāo)準(zhǔn)型化標(biāo)準(zhǔn)型,建立初始單純形表建立初始單純形表，則已得到最優(yōu)解、判斷，若021bB3、換基迭代為換出變量）確定換出變量，liilxbBbBbB,0)()(min)(1111為換入變量計(jì)算）（若存在停止計(jì)算；無(wú)可行解則該若所有的）（所在行的各系數(shù)純形表中檢查）確定換入變量，在單klkkljljjjljljljlxaaa

32、,n,jaa,n,jax,0min,210,LP0,212為主元素）換基迭代，lka34、回到第2步對(duì)偶單純形法有以下優(yōu)點(diǎn)：l(1) 初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算。l(2) 當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問(wèn)題用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。l(3) 在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時(shí)需要用對(duì)偶單純形法，這樣可使問(wèn)題的處理簡(jiǎn)化。對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可行基，因而這種方

33、法在求解線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)應(yīng)用。 練習(xí)123123123min354 . 3260 2330 0,1,2,3jLPzxxxstxxxxxxxj求解：12312341235max354 . - 3260 -2330 0,1,2,3,4,5jzxxxstxxxxxxxxxj * 對(duì)偶單純形法的適用前提能解決形如以下的LP問(wèn)題：min (0)max - ( ) ( ) 0 0zCXCzCXAXbAXbXX 判斷下列LP問(wèn)題適合那種方法求解:0, 188 639 1065 532max) 1 (321321321321321xxxxx xxxxxxxs.t xxxz0, 188 639 1065

34、532min)2(321321321321321xxxxx xxxxxxxs.t xxxz0, 188 639 1065 532min) 3(321321321321321xxxxx xxxxxxxs.t xxxz0, 188 639 1065 532max)4(321321321321321xxxxx xxxxxxxs.t xxxz（大M法）（大M法） （對(duì)偶單純形法） （單純形法）線性規(guī)劃線性規(guī)劃 Linear Programming（LP）靈敏度分析靈敏度分析線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析 靈

35、敏度（敏感性）分析靈敏度（敏感性）分析 敏感性分析的重要性在于向決策者提供線性規(guī)劃問(wèn)題的最優(yōu)解所能適敏感性分析的重要性在于向決策者提供線性規(guī)劃問(wèn)題的最優(yōu)解所能適應(yīng)的環(huán)境條件變化的范圍，環(huán)境條件變化時(shí)可能對(duì)經(jīng)營(yíng)狀況帶來(lái)何種影響，應(yīng)的環(huán)境條件變化的范圍，環(huán)境條件變化時(shí)可能對(duì)經(jīng)營(yíng)狀況帶來(lái)何種影響，產(chǎn)生影響后的解決途徑。產(chǎn)生影響后的解決途徑。敏感性分析的類型：敏感性分析的類型： 1、模型中各個(gè)模型中各個(gè)參數(shù)在什么范圍變化時(shí)，最優(yōu)基不發(fā)生改變。參數(shù)在什么范圍變化時(shí)，最優(yōu)基不發(fā)生改變。 2、模型中模型中參數(shù)變化已經(jīng)超出上述范圍時(shí)，如何快速確定新的最優(yōu)參數(shù)變化已經(jīng)超出上述范圍時(shí)，如何快速確定新的最優(yōu) 基和基

36、和最優(yōu)解最優(yōu)解新的最優(yōu)決策方案。新的最優(yōu)決策方案。敏感性分析的方法：敏感性分析的方法： 敏感性分析方法的關(guān)鍵是從單純形法對(duì)應(yīng)的敏感性分析方法的關(guān)鍵是從單純形法對(duì)應(yīng)的 I 表表中參數(shù)的變化來(lái)分析中參數(shù)的變化來(lái)分析B 表表中對(duì)應(yīng)參數(shù)的變化情況來(lái)回答決策者所關(guān)心問(wèn)題。中對(duì)應(yīng)參數(shù)的變化情況來(lái)回答決策者所關(guān)心問(wèn)題。線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析 靈敏度（敏感性）分析靈敏度（敏感性）分析 線性規(guī)劃原問(wèn)題單純形法對(duì)應(yīng)的線性規(guī)劃原問(wèn)題單純形法對(duì)應(yīng)的 I 表表中參數(shù)的變化將引起中參數(shù)的變化將引起B(yǎng) 表表中對(duì)應(yīng)中對(duì)應(yīng)參

37、數(shù)的變化情況表：參數(shù)的變化情況表：原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解問(wèn)題的最優(yōu)解或最優(yōu)基不變問(wèn)題的最優(yōu)解或最優(yōu)基不變可以用單純形法繼續(xù)迭代求最優(yōu)解可以用單純形法繼續(xù)迭代求最優(yōu)解可以用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解可以用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新的單純形表重新計(jì)算引進(jìn)人工變量，編制新的單純形表重新計(jì)算54靈敏度分析目的靈敏度分析目的靈敏度分析所要解決的問(wèn)題：靈敏度分析所要解決的問(wèn)題：系數(shù)在什么范圍內(nèi)變化，不會(huì)影響已系數(shù)在什么范圍內(nèi)變

38、化，不會(huì)影響已獲得的最優(yōu)基獲得的最優(yōu)基。如果系數(shù)的變化超過(guò)以上范圍，如何如果系數(shù)的變化超過(guò)以上范圍，如何在原來(lái)最優(yōu)解的基礎(chǔ)上求得新的最優(yōu)解在原來(lái)最優(yōu)解的基礎(chǔ)上求得新的最優(yōu)解當(dāng)線性規(guī)劃問(wèn)題增加一個(gè)新的變量或當(dāng)線性規(guī)劃問(wèn)題增加一個(gè)新的變量或新的約束，如何在原來(lái)最優(yōu)解的基礎(chǔ)上新的約束，如何在原來(lái)最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解。獲得新的最優(yōu)解。55靈敏度分析內(nèi)容靈敏度分析內(nèi)容目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)cj的改變的改變常數(shù)項(xiàng)常數(shù)項(xiàng)bi的改變的改變技術(shù)系數(shù)技術(shù)系數(shù)aij的改變的改變線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析 靈

39、敏度（敏感性）分析靈敏度（敏感性）分析一、分析一、分析 C 的變化的變化 當(dāng)當(dāng) Ci 是是基變量基變量 Xi 的目標(biāo)的目標(biāo)系數(shù)時(shí)，若要保持系數(shù)時(shí)，若要保持最優(yōu)解（或基）最優(yōu)解（或基）不變，則必須滿足：不變，則必須滿足：CN CB B 1N 0- CB B -1 0基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1對(duì)應(yīng)對(duì)應(yīng)I 式式的的單純形表單純形表 I 表表對(duì)應(yīng)對(duì)應(yīng)B 式式的的單純形表單純形表 B 表表線性規(guī)劃線性規(guī)劃 Linear Programming（L

40、P）線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析 靈敏度（敏感性）分析靈敏度（敏感性）分析一、分析一、分析 C 的變化的變化 當(dāng)當(dāng) Cj 是是非基變量非基變量 Xj 的目標(biāo)的目標(biāo)系數(shù)時(shí)，若要保持系數(shù)時(shí)，若要保持最優(yōu)解（或基）最優(yōu)解（或基）不變，則必須滿足：不變，則必須滿足：CN CB B -1N 0基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1對(duì)應(yīng)對(duì)應(yīng)I 式式的的單純形表單純形表 I 表表對(duì)應(yīng)對(duì)應(yīng)B 式式的的單純形表單純形表 B 表表5

41、8非基變量在目標(biāo)函數(shù)中系數(shù)的靈敏度分析非基變量在目標(biāo)函數(shù)中系數(shù)的靈敏度分析maxz=-x1-x2+4x3 s.t. x1+x2+2x39 x1+x2-x32 -x1+x2+x34 x1,x2,x30在線性規(guī)劃問(wèn)題中，對(duì)在線性規(guī)劃問(wèn)題中，對(duì)c2進(jìn)行靈敏度分析進(jìn)行靈敏度分析 。59得到以上問(wèn)題的最優(yōu)單純形表：得到以上問(wèn)題的最優(yōu)單純形表： 60當(dāng)當(dāng)c2=c2+ 時(shí)，相應(yīng)的單純形表為：時(shí)，相應(yīng)的單純形表為： 6101247要使原來(lái)的解仍保持最優(yōu)解，就要要使原來(lái)的解仍保持最優(yōu)解，就要zj-cj0（j=1,2,3,4,5），即），即 1247由此得到，由此得到， ，即當(dāng)，即當(dāng)c2 35/12時(shí)，最優(yōu)解保持

42、不變時(shí)，最優(yōu)解保持不變 124762基變量在目標(biāo)函數(shù)中系數(shù)的靈敏度分析基變量在目標(biāo)函數(shù)中系數(shù)的靈敏度分析maxz=-x1-x2+4x3 s.t. x1+x2+2x39 x1+x2-x32 -x1+x2+x34 x1,x2,x30在線性規(guī)劃問(wèn)題中，對(duì)在線性規(guī)劃問(wèn)題中，對(duì)c1進(jìn)行靈敏度分析進(jìn)行靈敏度分析 。63得到以上問(wèn)題的最優(yōu)單純形表：得到以上問(wèn)題的最優(yōu)單純形表： 64當(dāng)當(dāng)c1=c1+ 時(shí)，相應(yīng)的單純形表為：時(shí)，相應(yīng)的單純形表為： 6501 1/3022/30-47/12+1/4 要使原來(lái)的基仍保持最優(yōu)基，就要要使原來(lái)的基仍保持最優(yōu)基，就要zj-cj0（j=1,2,3,4,5），即），即 47/

43、333 由此得到，由此得到，-33，即當(dāng)，即當(dāng)-4 c1 2時(shí)，最優(yōu)基保持不變時(shí)，最優(yōu)基保持不變 注：若當(dāng)注：若當(dāng)c改變導(dǎo)致檢驗(yàn)數(shù)存在大于改變導(dǎo)致檢驗(yàn)數(shù)存在大于0時(shí)，則可用單純形時(shí)，則可用單純形法繼續(xù)求解得新的最優(yōu)解。法繼續(xù)求解得新的最優(yōu)解。66線性規(guī)劃線性規(guī)劃 Linear Programming（LP）線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析線性規(guī)劃問(wèn)題的參數(shù)變化靈敏度分析 靈敏度（敏感性）分析靈敏度（敏感性）分析二、分析二、分析 b 的變化的變化當(dāng)當(dāng)I 表中表中b變化為變化為b時(shí)，在時(shí)，在B 表中將只有解列表中將只有解列B -1b發(fā)生變化，為保證發(fā)生變化，為保證最優(yōu)基最優(yōu)基不變則不變則必須滿足：

44、必須滿足： B -1b 0基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B -1N B -1 j 0 CN CB B -1 - CB B -1對(duì)應(yīng)對(duì)應(yīng)I 式式的的單純形表單純形表 I 表表對(duì)應(yīng)對(duì)應(yīng)B 式式的的單純形表單純形表 B 表表67例例maxz=-x1-x2+4x3 s.t. x1+x2+2x39 x1+x2-x32 -x1+x2+x34 x1,x2,x30在線性規(guī)劃問(wèn)題中，對(duì)在線性規(guī)劃問(wèn)題中，對(duì)b1進(jìn)行靈敏度分析進(jìn)行靈敏度分析 。68最最優(yōu)優(yōu)單單純純形形表表初初始始單單純純形形表表69對(duì)于上述最優(yōu)解，最優(yōu)基為：對(duì)于上述最

45、優(yōu)解，最優(yōu)基為：B11 302 30111 301 3/bB b11 302 30111 301 39241 3613 3/101111201B70當(dāng)當(dāng)b1=b1+ =9+ 時(shí)，最后一張單純形表中的右邊常數(shù)將成為時(shí)，最后一張單純形表中的右邊常數(shù)將成為 3/3/1363/3/14293/103/11103/203/1 1 bBb最后一張單純形表中的右邊常數(shù)將成為：最后一張單純形表中的右邊常數(shù)將成為：71原始可行條件原始可行條件為：為：1 31 3013 31 30/ 113-1，b1=b1+8時(shí)，原來(lái)的最優(yōu)基仍為原始可行基時(shí)，原來(lái)的最優(yōu)基仍為原始可行基 注：當(dāng)注：當(dāng)b改變導(dǎo)致右端項(xiàng)小于改變導(dǎo)致右

46、端項(xiàng)小于0時(shí)，可用對(duì)偶單純形法時(shí)，可用對(duì)偶單純形法繼續(xù)求解得新的最優(yōu)解。繼續(xù)求解得新的最優(yōu)解。72線性規(guī)劃線性規(guī)劃 Linear Programming（LP）問(wèn)題問(wèn)題 某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，都要在某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，都要在 A ，B 兩種設(shè)備上加兩種設(shè)備上加工，有關(guān)數(shù)據(jù)如下表：工，有關(guān)數(shù)據(jù)如下表：n如何充分發(fā)揮設(shè)備的能力，使產(chǎn)品總利潤(rùn)最大？如何充分發(fā)揮設(shè)備的能力，使產(chǎn)品總利潤(rùn)最大？n若為了提高產(chǎn)量，以每臺(tái)時(shí)若為了提高產(chǎn)量，以每臺(tái)時(shí) 350 元租用外廠元租用外廠 A 設(shè)備，是否合算？設(shè)備，是否合算？n分別確定甲產(chǎn)品單位利潤(rùn)、分別確定甲產(chǎn)品單位利潤(rùn)、B 設(shè)備量各自的影響范圍。設(shè)備量

47、各自的影響范圍。1.若能以若能以 39 萬(wàn)元租用外廠萬(wàn)元租用外廠 B 設(shè)備設(shè)備 300 臺(tái)時(shí)，應(yīng)否租用？為什么？臺(tái)時(shí)，應(yīng)否租用？為什么？ 產(chǎn)品產(chǎn)品設(shè)備設(shè)備單耗（臺(tái)時(shí)單耗（臺(tái)時(shí)/件）件）設(shè)備有效臺(tái)時(shí)設(shè)備有效臺(tái)時(shí)（每月）（每月）甲甲乙乙丙丙A121400B212500利潤(rùn)（元利潤(rùn)（元/件）件）30002000100073增加一個(gè)新的變量增加一個(gè)新的變量- -分析在原計(jì)劃中是否應(yīng)該安排一種新產(chǎn)品分析在原計(jì)劃中是否應(yīng)該安排一種新產(chǎn)品。增加一個(gè)新的變量增加一個(gè)新的變量x7，它在目標(biāo)函數(shù)中的系數(shù)，它在目標(biāo)函數(shù)中的系數(shù)c7=1，在約束，在約束條件中的系數(shù)向量為條件中的系數(shù)向量為 ：1117a求新的最優(yōu)基和最

48、優(yōu)解。求新的最優(yōu)基和最優(yōu)解。 maxz=-x1-x2+4x3 s.t. x1+x2+2x39 x1+x2-x32 -x1+x2+x34 x1,x2,x3074-1-14000 x1x2x3x4x5x6RHS0 x411210090 x511-101020 x6-1110014-1-14000最最優(yōu)優(yōu)單單純純形形表表-1-14000 x1x2x3x4x5x6RHS-1x11-1/401/30-2/31/30 x502001164x302/311/301/313/30-47/120-10-2初初始始單單純純形形表表75對(duì)于上述最優(yōu)解，最優(yōu)基為：對(duì)于上述最優(yōu)解，最優(yōu)基為：B11 302 30111

49、301 3/101111201B單純形表中單純形表中x7對(duì)應(yīng)的系數(shù)：對(duì)應(yīng)的系數(shù)：023/1 1113/103/11103/203/171aB76加入加入x7后的單純形表為：后的單純形表為：77增加一個(gè)新的約束增加一個(gè)新的約束- -例例增加工藝流程增加工藝流程 增加一個(gè)新的約束增加一個(gè)新的約束：-x1+2x22，求新的最優(yōu)基和最優(yōu)解。，求新的最優(yōu)基和最優(yōu)解。 maxz=-x1-x2+4x3 s.t. x1+x2+2x39 x1+x2-x32 -x1+x2+x34 x1,x2,x30-x1+2x22-x1+2x2-x7= =2x1-2x2+x7=-=-278在原最優(yōu)單純形表中加入新方程信息：在原最

50、優(yōu)單純形表中加入新方程信息：-1-140000 x1x2x3x4x5x6x7RHS-1x11-1/401/30-2/301/30 x5020011064x302/311/301/3013/30 x71-200001-279變成單純形表：變成單純形表：-1-140000 x1x2x3x4x5x6x7RHS-1x11-1/401/30-2/301/30 x5020011064x302/311/301/3013/30 x70-7/40-1/302/31-7/30-47/120-10-2080工藝流程系數(shù)改變工藝流程系數(shù)改變- -例例l某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，單位利潤(rùn)分別為2、3,已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表1-1所示。資源 產(chǎn) 品 擁有量設(shè) 備1 2 8臺(tái)時(shí)原材料 A 40 16 kg原材料 B04 12 kg81l最終單純形表為：82l分析原計(jì)劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化。分析原計(jì)劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化。若原計(jì)劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)有關(guān)它的技術(shù)系數(shù)向量變?yōu)镻1=(2,5,2)T，每件利潤(rùn)為4元，試分析對(duì)原最優(yōu)計(jì)劃有什么影響? 83解 把改進(jìn)工