1、1,第三章線性規(guī)劃的對(duì)偶原理,單純形法的矩陣描述 A為mn階矩陣 RankA=m,取B為可行基,N為非基，,2,求解步驟：,3,4,現(xiàn)在不再生產(chǎn)，將設(shè)備材料出租出讓?zhuān)_定租費(fèi)及轉(zhuǎn)讓費(fèi)？ 設(shè)y1為設(shè)備單位臺(tái)時(shí)的租金，y2,y3為材料A、B轉(zhuǎn)讓附加費(fèi)(kg-1) 目標(biāo)函數(shù)，約束條件？,則M2為M1的對(duì)偶問(wèn)題， 反之亦然。,5,一般的，原問(wèn)題：max z = CX AX b X 0,對(duì)偶問(wèn)題：min w = Yb YA C Y 0,比較： max z min w 決策變量為n個(gè) 約束條件為n個(gè) 約束條件為m個(gè) 決策變量為m個(gè) “” “” 約束條件的限定向量 目標(biāo)函數(shù)的價(jià)值向量 目標(biāo)函數(shù)的價(jià)值向量 約

2、束條件的限定向量,6,二、 對(duì)偶問(wèn)題的化法 1、典型情況（對(duì)稱(chēng)形式） 例2max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0,7,2、含等式的情況 例3max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,一般，原問(wèn)題第i個(gè)約束取等式，對(duì)偶問(wèn)題第i個(gè)變量自由變量。,8,3、含“”的max問(wèn)題 例4max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,9,一般: max問(wèn)題

3、第i個(gè)約束取“”，則min問(wèn)題第i個(gè)變量 0 ；, min問(wèn)題第i個(gè)約束取“”，則max問(wèn)題第i個(gè)變量 0 ；, 原問(wèn)題第i個(gè)約束取等式，對(duì)偶問(wèn)題第i個(gè)變量 自由變量；, max問(wèn)題第j個(gè)變量 0 ,則min問(wèn)題第j個(gè)約束取“” ；, min問(wèn)題第j個(gè)變量 0 ，則max問(wèn)題第j個(gè)約束取“” ；, 原問(wèn)題第j個(gè)變量自由變量，對(duì)偶問(wèn)題第j個(gè)約束取等式。,10,例5 min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4自由變量,11,2 對(duì)偶問(wèn)題的基本性

4、質(zhì)和基本定理,1、對(duì)稱(chēng)性定理 對(duì)偶問(wèn)題的對(duì)偶為原問(wèn)題.,原問(wèn)題：max z = CX AX b X 0 (1),對(duì)偶問(wèn)題：min w = Yb YA C Y 0 (2),證：,(2)作變換：,(2)等價(jià)于：,對(duì)偶,令z=w,即為(1), (2)的對(duì)偶問(wèn)題為(1)。,12,證：,推論： (1)max問(wèn)題任一可行解的目標(biāo)值為min問(wèn)題目標(biāo)值的一個(gè)下界； (2)min問(wèn)題任一可行解的目標(biāo)值為max問(wèn)題目標(biāo)值的一個(gè)上界。,13,3、無(wú)界性（性質(zhì)2的推論） 若原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)界解，則對(duì)偶問(wèn)題(原問(wèn)題)為無(wú)可行解。,注：該性質(zhì)的逆不存在。若原(對(duì)偶)問(wèn)題為無(wú)可行解，對(duì)偶(原問(wèn)題)問(wèn)題或?yàn)闊o(wú)界解，或?yàn)?/p>

5、無(wú)可行解。,14,4、最優(yōu)性 設(shè)X*，Y*分別為原問(wèn)題和對(duì)偶問(wèn)題可行解， 當(dāng)CX*=Y*b時(shí)， X*，Y*分別為最優(yōu)解。,證：,X*為最優(yōu)解,Y*為最優(yōu)解,15,5、對(duì)偶定理 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)值相等。,證：,16,5、對(duì)偶定理 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)值相等。,推論（單純形乘子Y的定理）： 原問(wèn)題有一個(gè)對(duì)應(yīng)于基B的最優(yōu)解，則此時(shí)的Y是對(duì)偶問(wèn)題的一個(gè)最優(yōu)解。,例：書(shū)P25,17,對(duì)偶問(wèn)題中，解的情況有： 1.都有有限最優(yōu)解 2.都無(wú)可行解 3.一個(gè)有無(wú)界解，另一個(gè)無(wú)可行解,18,6、松弛性 若X*，Y*分別為原問(wèn)題及對(duì)偶問(wèn)題的可行解， 那么

6、Ys*X*=0，Y*Xs*=0， 當(dāng)且僅當(dāng)X*，Y*分別為最優(yōu)解。,證：,將b，C代入目標(biāo)函數(shù)，,19,7、檢驗(yàn)數(shù)與解的關(guān)系 原問(wèn)題附加變量最優(yōu)檢驗(yàn)數(shù)的值為對(duì)偶問(wèn)題的最優(yōu)解。,檢驗(yàn)數(shù)： = (C 0)- CBB-1(A -I) = (C- CBB-1A CBB-1) = (c s) c = C - CBB-1A X對(duì)應(yīng)的檢驗(yàn)數(shù) s = CBB-1 Xs對(duì)應(yīng)的檢驗(yàn)數(shù),例：書(shū)P25,4 =2，5 =3,20,求對(duì)偶問(wèn)題的最優(yōu)解: 1.單純形乘子Y的定理 2.松弛性 3.檢驗(yàn)數(shù)與解的關(guān)系,21,例6已知：min w = 20y1 + 20y2 的最優(yōu)解為y1*=1.2,y2*=0.2 -ys1 y1

7、 + 2y2 1 試用松弛性求對(duì)偶 -ys2 2y1 + y2 2 問(wèn)題的最優(yōu)解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0,y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 0,22,y1*=1.2,y2*0.2 0 xs1* = xs2* = 0 由 y1* + 2y2* = 1.6 1 ys1* 0 x1* = 0 由 2y1* + y2* = 2.6 2 ys2* 0 x2* = 0 由 2y1* + 3y2* = 3 =右邊 ys3* = 0 x3*待定

8、 由 3y1* + 2y2* = 4 =右邊 ys4* = 0 x4*待定,最優(yōu)解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*,y1*=1.2, y2*=0.2 ys1*x1* =0 ys2*x2* =0 ys3*x3* =0 ys4*x4* =0 y1*xs1* =0 y2*xs2* =0,y1 + 2y2 - ys1* = 1 2y1 + y2 - ys2* = 2 2y1 + 3y2 - ys3* =3 3y1 + 2y2 - ys4* = 4 x1 + 2x2 + 2x3 + 3x4 +xs1 =

9、 20 2x1 + x2 + 3x3 + 2x4 +xs2 = 20,23,8、對(duì)偶問(wèn)題的經(jīng)濟(jì)含義影子價(jià)格 最優(yōu)情況：z* = w* = b1y1* + + biyi* + + bmym*,b1： 8 9 Q2(4，2.5) z* = 15.5 z* = z*- z* = 3/2 = y1* b2：16 17 Q2”(4.25，1.875) z*” = 14.125 z* = z*”- z* = 1/8 = y2* b3：12 13 z* = 0 = y3*,Q2,Q2”,Q2（4，2） z =14,條件3未滿足，再增加b，不會(huì)帶來(lái)z的增加， 故該資源價(jià)值為0.,24,3 對(duì)偶單純形法 單純形

10、法：由 XB = B-1b 0，使j 0，j = 1,m 對(duì)偶單純形法：由j 0(j= 1,n)，使XB = B-1b 0 相同點(diǎn)：都用于求解原問(wèn)題 對(duì)偶單純形法：從一個(gè)原始不可行而對(duì)偶可行的基出發(fā)，進(jìn)行基變換，每次基變換時(shí)都保持基的對(duì)偶可行性，一旦獲得一個(gè)原始可行基，則該基必定是最優(yōu)基。,步驟：(1)保持j 0，j= 1,n，確定XB，建立計(jì)算表格；,(2)判別XB = B-1b 0是否成立？ 若成立，XB為最優(yōu)基變量； 若不成立，轉(zhuǎn)(3)；,25,(4)取主變換，得到新的XB。,(3)基變換 換出變量，,換入變量（最大負(fù)比值規(guī)則），,重復(fù)（2）-（4）步，求出結(jié)果。,26,例8用對(duì)偶單純形

11、法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0,min w = 2x1 + 3x2 + 4x3 + 0 x4 + 0 x5 x1 + 2x2 + x3 - x4 1 2x1 - x2 + 3x3 x5 4 x1,x2,x3,x4,x5 0,27,min w = 2x1 + 3x2 + 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 - 1 - 2x1 + x2 - 3x3 + x5 - 4 x1,x2,x3,x4,x5 0,28,*,-4,-2.5,2,-0.5,0.5

12、,0,1,0,1,1.5,4,-0.5,x1,-0.5,1,x4,0,2,0,0,1,1,29,初始檢驗(yàn)數(shù)中有負(fù)數(shù)？對(duì)偶不可行,1、構(gòu)造擴(kuò)充問(wèn)題 增加一個(gè)變量和一個(gè)約束條件 2、求基本解（初始對(duì)偶可行） 檢驗(yàn)數(shù)中最小的負(fù)數(shù) 換入變量 新增變量為換出變量 取主變換后全部檢驗(yàn)數(shù)非負(fù) 3、用對(duì)偶單純形法求解擴(kuò)充問(wèn)題 擴(kuò)充問(wèn)題無(wú)可行解，則原問(wèn)題無(wú)可行解 擴(kuò)充問(wèn)題有最優(yōu)解，則原問(wèn)題有可行解，且如擴(kuò)充問(wèn)題的目標(biāo)函數(shù)值與M無(wú)關(guān)，則為原問(wèn)題最優(yōu)解。,30,例：,標(biāo)準(zhǔn)型：,擴(kuò)充問(wèn)題：,31,*,2M,-3,6-M,1,0,0,0,0,1,1,4,1,x1,0,M-8,x4,0,-2,0,0,2,2,0,x5,1

13、 1 1 0 0 1 M,0,1,-1,32,作業(yè) P81 1.12(1),33,4 靈敏度分析,分析 變化對(duì)最優(yōu)解的影響。,1、保持原最優(yōu)基的變化范圍； 2、原最優(yōu)基不再最優(yōu)時(shí)，求新的最優(yōu)解的最簡(jiǎn)便方法,34,35,例1 已知下述問(wèn)題的最優(yōu)解及最優(yōu)單純形表,36,最優(yōu)單純形表如下:,37,由最優(yōu)單純形表得:,38,39,不可行!,用對(duì)偶單純形法計(jì)算,40,4,20,4,41,42,43,例2 求例1 c4的變化范圍,使最優(yōu)解不變.,解:,44,分析:,45,方法:,例3 求例1 c2的變化范圍,使最優(yōu)解不變.,46,解:,0,1/8,3/2,0,0,0,-1/8,1/2,1,0,2,-3,1

14、,1/2,-2,0,0,4,x5,0,0,1/4,0,0,1,4,x1,-2,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-3,-2,x2,47,48,改變C，求新的最優(yōu)解? 只需修改最終表上的C及檢驗(yàn)數(shù)，得到新的迭代表，繼續(xù)求解。,例3 c2=1,求新的最優(yōu)解.,-2,-2,1,1/4,c2=-3，若c2=4？,最優(yōu)解不變.,0 0 -1/2 5/8 0,1,1,繼續(xù)用單純形法求解.,49,分析:,50,51,例4 求例1 a24的變化范圍,使最優(yōu)解不變.,解:,x4為非基變量，故只影響x4的檢驗(yàn)數(shù)。,52,基變量約束系數(shù)的變化 會(huì)導(dǎo)致問(wèn)題變得相當(dāng)復(fù)雜，所以重新計(jì)算。,53,四

15、、增加一個(gè)新變量 例5 在例1的基礎(chǔ)上，企業(yè)要增加一個(gè) 新產(chǎn)品,每件產(chǎn)品需2個(gè)臺(tái)時(shí)，原材料A 6kg， 原材料B 3kg，利潤(rùn) 5元/件，問(wèn)如何安排各產(chǎn) 品的產(chǎn)量，使利潤(rùn)最大？ 解：,54,表明生產(chǎn)新品有利。,55,56,-5/4,0,1/8,3/2,0,0,1/4,0,-1/8,1/2,1,0,2,-3,2,1,1/2,-2,0,0,4,x5,0,3/2,0,1/4,0,0,1,4,x1,-2,x5,x4,x3,x2,x1,b,XB,CB,-5,0,0,0,-3,-2,x2,8/3,4/2,8,i,x3,2,14,57,五、增加一個(gè)新的約束條件 1、原最優(yōu)解滿足新約束，則最優(yōu)解不變。 2、若不滿足，則需求新的最優(yōu)解。 例:原問(wèn)題： 加條件：,58,需求新