運籌學(xué)_7 特殊問題+總流程

1、運籌學(xué) Operational Research Lec. 7 特殊問題 & 總流程 & Excel實現(xiàn)目錄l特殊情況l大M方法l單純形方法解LP問題的總流程l計算機求解單純形中的特殊問題 l單純形中的特殊問題l存在四種特殊問題l過程中的退化；結(jié)果的無解與無窮多解；找不到初始最優(yōu)解l如何處理l退化問題l終止計算的判斷：無界與無窮，P20l初始基可行解的問題，引出人工初始解退化問題與Bland規(guī)則l進基出基時，若進基出基變量不唯一，選擇下標(biāo)小者進、出基。l稱為Bland規(guī)則l裘宗滬解線性規(guī)劃的單純形算法中避免循環(huán)的幾種方法終止條件l最優(yōu)解l多重解l無界解終止條件之一：最優(yōu)解l對最

2、大問題，若檢驗數(shù)均0，則已經(jīng)得到最優(yōu)解；否則繼續(xù)迭代運算終止條件之二：多重最優(yōu)解l對最大問題，若基變量檢驗數(shù)均0，又存在非基變量的檢驗數(shù)0，則具有多重最優(yōu)解。終止條件之三：無界解l對最大問題，若至少有一個檢驗數(shù)0，對某個大于零的檢驗數(shù)對應(yīng)的xk的系數(shù)均0，則問題無界解，停止計算單純形表案例（3）lmax z3x12x2ls.t. -2x1x2 2 x1 -3x2 3 x1，x2 0單純形表案例（3）lmax z3x12x2ls.t. -2x1x2 x3 = 2 x1 -3x2 x4 3 x1-4 0單純形表案例（3）基變量原始價值系數(shù)基變量Cj3 2 0 0 bCBXB變量系數(shù)00 x3x4-

3、2 1 1 0 1 -3 0 1 23檢驗行3 2 0 00 填表檢驗單純形表案例（3）基變量原始價值系數(shù)基變量Cj3 2 0 0 bCBXB變量系數(shù)00 x3x4-2 1 1 0 1 -3 0 1 23檢驗行3 2 0 00 進基 離基單純形表案例（3）基變量原始價值系數(shù)基變量Cj3 2 0 0 bCBXB變量系數(shù)03x3x1-2 1 1 0 1 -3 0 1 23檢驗行3 2 0 00 進基 離基單純形表案例（3）基變量原始價值系數(shù)基變量Cj3 2 0 0 bCBXB變量系數(shù)03x3x10 -5 1 2 1 -3 0 1 83檢驗行0 11 0 -39 進基 離基人工初始解l為什么需要人工

4、初始解？l前面例子中的約束條件：左側(cè)右側(cè)l因此，松弛變量系數(shù)均為“1”，很容易找到基，其他非基變量均為零（解在原點處），一定是一個可行解。這樣，很容易找到初始”基本可行解“。l約束條件為“=”,“”的情況下，卻不能保證是“基本可行解”，該如何處理？人工初始解l人工初始解包括兩種處理辦法l大M法：考察重點l兩階段法大M法思想l基本方法：l在上述情況下，加入人工變量：Rl但是，人工變量是虛擬的，最終不應(yīng)影響結(jié)果，也就是必須要離基l因此，目標(biāo)函數(shù)中增加項：MR（系數(shù)M是充分大的正數(shù)）。當(dāng)?shù)K了，如果仍有人工變量R為非零基變量，則目標(biāo)函數(shù)不可能實現(xiàn)最大化，無可行解。大M法案例l原題lmin z3x1

5、x2 x3ls.t. x12x2 x3 11 -4x1 +x2 2x3 3 -2x1 + x3 1 x1，x2 ，x3 0大M法案例l加入松弛變量、剩余變量和人工變量lmax z3x1x2 x3 0 x4 0 x5 Mx6 Mx7 ls.t. x12x2 x3 x4 11 -4x1 +x2 x5 x6 3 -2x1 + x3 x7 1 x17 0大M法案例價值系數(shù)基變量Cjb31100M MCBXBx1x2x3x4x5x6x70 x4121100011Mx641201103MX720100011（最?。z驗行3-6M 1M1+3M（最大）0M00？大M法案例價值系數(shù)基變量Cjb31100MMC

6、BXBx1x2x3x4x5x6x70 x4320100110Mx601001121min1X320100011檢驗行11M（max）00M03M+1？大M法案例價值系數(shù)基變量Cjb31100MMCBXBx1x2x3x4x5x6x73x1300122512min1x2010011211X320100011檢驗行1max0001M+1M1？大M法案例價值系數(shù)基變量Cjb31 100MMCBXBx1x2x3x4x5X6x73x11001/32/32/35/341x20100-11211X30012/3-4/34/3-7/39檢驗行000-1/3 1/3 M+1/3 M+2/3？大M法案例價值系數(shù)基變

7、量Cjb31100MMCBXBx1x2x3x4x5X6x73x11001/32/32/35/341x20100-11211X30012/3-4/34/3-7/39檢驗行000-1/31/3M+1/3M+2/3解為解為(4,1,9) 值為值為2兩階段法思想l大M法的問題：計算機計算中的誤差問題l兩階段法的思想：l第一階段：構(gòu)造人工變量目標(biāo)函數(shù)，求目標(biāo)最小。l若目標(biāo)最小為零，則有可行解l否則無可行解，停止計算l求解原問題兩階段法案例l原題lmin z3x1x2 x3ls.t. x12x2 x3 11 -4x1 +x2 2x3 3 -2x1 + x3 1 x1，x2 ，x3 0兩階段法案例l加入松弛

8、變量、剩余變量和人工變量lmin wx6x7ls.t. x12x2 x3 x4 11 -4x1 +x2 x5 x6 3 -2x1 + x3 x7 1 x17 0max z3x1x2 x3 0 x4 0 x5 Mx6 Mx7兩階段法案例價值系數(shù)基變量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x4121100011-1x641201103-1X720100011min檢驗行-613max0-100兩階段法案例價值系數(shù)基變量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x4320100-110-1x6010011-21min0X3-20100011檢驗行01m

9、ax00-10-3兩階段法案例價值系數(shù)基變量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x43001-22-5120 x2010011-210X3-20100011檢驗行00000-1-1第一階段結(jié)束，解為（0,1,1,12,0,0,0），目標(biāo)值為0。進入第二階段兩階段法案例價值系數(shù)基變量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x43001-22-5120 x2010011-210X3-20100011檢驗行0000011去掉人工變量列，恢復(fù)目標(biāo)函數(shù)，繼續(xù)迭代兩階段法案例價值系數(shù)基變量Cjb31100CBXBX1x2x3x4x50X43001-212

10、min1X20100111X3-201001檢驗行1max0001min z3x1x2 x3兩階段法案例價值系數(shù)基變量Cjb31100CBXBx1x2x3x4x53X11001/3-2/341X20100111X30012/3-4/39檢驗行000-1/3 -1/3min z3x1x2 x3兩階段法案例價值系數(shù)基變量Cjb31100CBXBx1x2x3x4x53X11001/3-2/341X20100111X30012/3-4/39檢驗行000-1/3 -1/3解為（解為（4,1,9,0,0）；值為）；值為3x1x2 x32計算機求解：ExcellExcell見附件計算機求解：Matlabl%

11、 x,fval,exitflag,output,lambda即最優(yōu)解,最優(yōu)值, 輸出標(biāo)記,迭代次數(shù),存儲情況l% linprog(f,a,b,lb)即（目標(biāo)函數(shù),系數(shù)矩陣,約束常數(shù)向量,等式系數(shù)矩陣,等式常數(shù)向量,決策變量下界,決策變量上界）l% min z=fl% s.t. a*xbl aeq*x=beql lbxub計算機求解：Matlab f=-2,-3;% 目標(biāo)函數(shù) a=1 1; 1 2;0 1;% 系數(shù)矩陣 b=6 8 3;% 約束常數(shù)向量 lb=zeros(2,1);% 決策變量下界x,fval,exitflag,output,lambda=linprog(f,a,b,lb)lmax z2x13x2ls.t. x1x2 6 x1 +2x2 8 x2 3 x1，x2 0計算機求解：MatlablOptimization terminated.lx =l 4.0000l 2.0000lfval =l -20.0000lexitflag =l 1loutput = l iterations: 7l algorithm: large-scale: interior pointl cgiterations: 0l message: Optimizat