第3章 北理工運(yùn)籌學(xué)課件

1、1第三章 線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶與靈敏度分析w線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題概念、理論及經(jīng)濟(jì)意義w線(xiàn)性規(guī)劃的對(duì)偶單純形法w線(xiàn)性規(guī)劃的靈敏度分析本章內(nèi)容重點(diǎn)21.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題 對(duì)偶原理 對(duì)偶問(wèn)題定義 線(xiàn)性規(guī)劃問(wèn)題寫(xiě)出其對(duì)偶問(wèn)題，要掌握在對(duì)稱(chēng)形式和非對(duì)稱(chēng)情況下由原問(wèn)題寫(xiě)出對(duì)偶問(wèn)題的方法。 對(duì)偶定理 只需了解原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系，證明從略。3 1.對(duì)偶問(wèn)題： 若第二章例2.1問(wèn)題的設(shè)備都用于外協(xié)加工，工廠收取加工費(fèi)。試問(wèn)：設(shè)備 A、B、C 每工時(shí)各如何收費(fèi)才最有競(jìng)爭(zhēng)力？ 設(shè) y1 ，y2 ，y3 分別為每工時(shí)設(shè)備 A、B、C 的收取費(fèi)用。1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題4線(xiàn)性規(guī)劃

2、原問(wèn)題線(xiàn)性規(guī)劃原問(wèn)題 例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ù)如下表所示。求獲最大利潤(rùn)的方案。 產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3 32 26565設(shè)備B2 21 14040設(shè)備C0 03 37575利潤(rùn)（元/件）1500150025002500 5 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原問(wèn)題原問(wèn)題 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1

3、500 （不少于甲產(chǎn)品的利潤(rùn)） 2y1+y2+3y3 2500 對(duì)偶問(wèn)題對(duì)偶問(wèn)題 （不少于乙產(chǎn)品的利潤(rùn)） y1, y2 , y3 01.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題6 2、對(duì)偶定義 對(duì)稱(chēng)形式： 互為對(duì)偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題7 一對(duì)對(duì)稱(chēng)形式的對(duì)偶規(guī)劃之間具有下面的對(duì)應(yīng)關(guān)系。 (1)若一個(gè)模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對(duì)偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max

4、，”和“min，”相對(duì)應(yīng)。1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題8 (2)從約束系數(shù)矩陣看：一個(gè)模型中為，則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束，n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè)變量。 (3)從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型中，b和C的位置對(duì)換。 (4)兩個(gè)規(guī)劃模型中的變量皆非負(fù)。1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題9 非對(duì)稱(chēng)形式的對(duì)偶規(guī)劃 一般稱(chēng)不具有對(duì)稱(chēng)形式的一對(duì)線(xiàn)性規(guī)劃為非對(duì)稱(chēng)形式的對(duì)偶規(guī)劃。 對(duì)于非對(duì)稱(chēng)形式的規(guī)劃，可以按照下面 的對(duì)應(yīng)關(guān)系直接給出其對(duì)偶規(guī)劃。 （1）將模型統(tǒng)一為“max，”或“min，” 的形式，對(duì)于其中的等式約束按下面（2）、（3）中的方法處理；

5、（2）若原規(guī)劃的某個(gè)約束條件為等式約束，則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取值沒(méi)有非負(fù)限制；1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c10 （3）若原規(guī)劃的某個(gè)變量的值沒(méi)有非負(fù)限

6、制，則在對(duì)偶問(wèn)題中與此變量對(duì)應(yīng)的那個(gè) 約束為等式。 下面對(duì)關(guān)系（2）作一說(shuō)明。對(duì)于關(guān)系（3） 可以給出類(lèi)似的解釋。 設(shè)原規(guī)劃中第一個(gè)約束為等式： a11x1 + + a1nxn = b1 那么，這個(gè)等式與下面兩個(gè)不等式等價(jià)1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題111.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題1111111111.bxaxabxaxannnn這樣，原規(guī)劃模型可以寫(xiě)成mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn, 2 , 1, 0max11111111111111121.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題 此時(shí)已轉(zhuǎn)化為對(duì)稱(chēng)形式，直接寫(xiě)出對(duì)偶規(guī)劃沒(méi)有非負(fù)限制

7、121111112211211211111111221111,0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm這里，把 y1 看作是 y1 = y1 - y1，于是 y1 沒(méi)有非負(fù)限制，關(guān)系（2）的說(shuō)明完畢。131.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題 例3.1 寫(xiě)出下面線(xiàn)性規(guī)劃的對(duì)偶規(guī)劃模型解 先將約束條件變形為“”形式?jīng)]有非負(fù)限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ141.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題沒(méi)有非負(fù)限制432144321

8、4314321,0,051030422602722523xxxxxxxxxxxxxxxx 再根據(jù)非對(duì)稱(chēng)形式的對(duì)應(yīng)關(guān)系，直接寫(xiě)出對(duì)偶規(guī)劃151.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf沒(méi)有非負(fù)限制16 3.對(duì)偶定理(原問(wèn)題與對(duì)偶問(wèn)題解的關(guān)系）考慮（LP）和（DP） 定理3-1 (弱對(duì)偶定理） 若 x, y 分別為（LP) 和（DP）的可行解，那么cTx bTy。 推論 若（LP）可行，那么（LP）無(wú)有限最優(yōu)解的充分必要條件是（LD）無(wú)可行解。1.1.線(xiàn)性規(guī)劃對(duì)

9、偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題17 定理3-2 (最優(yōu)性準(zhǔn)則定理) 若x,y分別(LP),(DP)的可行解,且cTx=bTy ，那么x,y分別為(LP)和(DP)的最優(yōu)解。 定理3-3 (主對(duì)偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。 以上定理、推論對(duì)任意形式的相應(yīng)性規(guī)劃的對(duì)偶均有效1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題18 4. 4.影子價(jià)格影子價(jià)格 是一個(gè)向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。 若x*,y* 分別為（LP）和（DP）的最優(yōu)解， 那么， cT x* = bT y* 。 根據(jù) f = bTy*=b1y1*+b2y2*+bm

10、ym* 可知 f / bi = yi* yi* 表示 bi 變化1個(gè)單位對(duì)目標(biāo) f 產(chǎn)生的影響，稱(chēng) yi* 為 bi的影子價(jià)格。 注意：注意：若 B 是最優(yōu)基， y* = (BT)-1 cB 為影子價(jià)格向量。1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題19 影子價(jià)格的經(jīng)濟(jì)含義 (1)影子價(jià)格是對(duì)現(xiàn)有資源實(shí)現(xiàn)最大效益時(shí)的一種估價(jià) 企業(yè)可以根據(jù)現(xiàn)有資源的影子價(jià)格，對(duì)資源的使用有兩種考慮：第一，是否將設(shè)備用于外加工或出租，若租費(fèi)高于某設(shè)備的影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租。第二，是否將投資用于購(gòu)買(mǎi)設(shè)備，以擴(kuò)大生產(chǎn)能力，若市價(jià)低于某設(shè)備的影子價(jià)格，可考慮買(mǎi)進(jìn)該設(shè)備，否則不宜買(mǎi)進(jìn)。1.1.線(xiàn)性規(guī)劃對(duì)

11、偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題201.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題 （2） 影子價(jià)格表明資源增加對(duì)總效益產(chǎn)生的影響。根據(jù)推論推論“設(shè)x0和y0分別為原規(guī)劃（P）和對(duì)偶規(guī)劃（D）的可行解，當(dāng)cx0=bTy0時(shí)，x0、y0分別是兩個(gè)問(wèn)題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關(guān)系 因此，可以將z*看作是bi,i=1,2， ,m的函數(shù)，對(duì)bi求偏導(dǎo)數(shù)可得到 這說(shuō)明，如果右端常數(shù)增加一個(gè)單位，則目標(biāo)函數(shù)值的增量將是*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,*21 影子價(jià)格反映了不同的局部或個(gè)體的增量可以獲得不同的整體經(jīng)濟(jì)效益。如果為了擴(kuò)大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從

12、影子價(jià)格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題22 需要指出，影子價(jià)格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤(rùn)等發(fā)生變化時(shí)，有可能使影子價(jià)格發(fā)生變化。另外，影子價(jià)格的經(jīng)濟(jì)含義（2），是指資源在一定范圍內(nèi)增加時(shí)的情況，當(dāng)某種資源的增加超過(guò)了這個(gè)“一定的范圍”時(shí)，總利潤(rùn)的增加量則不是按照影子價(jià)格給出的數(shù)值線(xiàn)性地增加。這個(gè)問(wèn)題還將在靈敏度分析一節(jié)中討論。1.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題23 5.由最優(yōu)單純形表求對(duì)偶問(wèn)題最優(yōu)解 標(biāo)準(zhǔn)形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x

13、1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題2450100000CBXBx1x2x3x4x5i0 x3300111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-c-cB BT TB B-1-1I IB B=(

14、p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價(jià)格影子價(jià)格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1對(duì)應(yīng)的檢驗(yàn)數(shù)對(duì)應(yīng)的檢驗(yàn)數(shù) T T = = c cB BT TB B-1-1 。 1. 1.線(xiàn)性規(guī)劃對(duì)偶問(wèn)題線(xiàn)性規(guī)劃對(duì)偶問(wèn)題25 對(duì)偶單純形法的基本思想 對(duì)偶單純形法的基本思想是：從原規(guī)劃的一個(gè)基本解基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶對(duì)偶可行解可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是

15、否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。2.2.對(duì)偶單純形法對(duì)偶單純形法26 如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校?dāng)同時(shí)得到對(duì)偶規(guī)劃與原 規(guī)劃的可行解時(shí)，便 得到原規(guī)劃的最優(yōu)解。2.2.對(duì)偶單純形法對(duì)偶單純形法27 對(duì)偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿(mǎn)足: 單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）； 變量取值可有負(fù)數(shù)（非可行解）。 注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)

16、變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形表。2.2.對(duì)偶單純形法對(duì)偶單純形法28w 1.建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2； 2.若b0,則得到最優(yōu)解,停止;否則,若有bk0則選k行的基變量為出基變量,轉(zhuǎn)3 3.若所有akj0( j = 1,2,n )，則原問(wèn)題無(wú)可行解,停止;否則,若有akj0 則選 =minj / akjakj0=r/akr那么 xr為進(jìn)基變量,轉(zhuǎn)4； 4.以akr為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。 對(duì)偶單純形法求解線(xiàn)性規(guī)劃問(wèn)題對(duì)偶單純形法求解線(xiàn)性規(guī)劃問(wèn)題過(guò)程：過(guò)程：2.2.對(duì)偶單純形法對(duì)偶單純形法29例3.2：求解線(xiàn)性規(guī)劃問(wèn)題：

17、求解線(xiàn)性規(guī)劃問(wèn)題： 標(biāo)準(zhǔn)化：標(biāo)準(zhǔn)化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.對(duì)偶單純形法對(duì)偶單純形法30w表格對(duì)偶單純形法CI-2-3-400CBXBbX1X2X3X4X50 X4-3-1-2-1100 X5-4-21-301j-2-3-4000 X4-10-5/21/21-1/2-2 X121-1/23/2

18、0-1/2j0-4-10-1-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5-8/5-1/52.2.對(duì)偶單純形法對(duì)偶單純形法31單純形法和對(duì)偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計(jì)算計(jì)算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒(méi)有最優(yōu)解沒(méi)有最優(yōu)解單純形法對(duì)偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0brMin-bi/airair03.3.

19、靈敏度分析靈敏度分析46 例3.5: 上例最優(yōu)單純形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/80j00-1.5-1/803.3.靈敏度分析靈敏度分析47 0 0.25 0 這里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對(duì)應(yīng) b1、b2、b3 的單一變化因此，設(shè) b1 增加 4，則 x1 ,x5 ,x2分別變?yōu)椋?+04=4, 4+(-2)4=-40, 2+0.54=4用對(duì)偶單純形法進(jìn)一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 173.3.靈敏度分析靈敏度分析48 增加一個(gè)變量 增加變量 xn+1 則有相應(yīng)的pn+1 ,cn+1 。 那么 計(jì)算出B B-1pn+1 , n+1=cn+1-cri ari n+1 填入最優(yōu)單純形表, 若 n+1 0 則 最優(yōu)解不變； 否則，進(jìn)一步用單純形法求解。3.3.靈敏度分析靈敏度分析49例3.6:例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 計(jì)算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2