清華運籌學(xué)學(xué)習(xí)教案

1、會計學(xué)1清華運籌學(xué)清華運籌學(xué)第一頁，編輯于星期二：二點 四十六分。2 分析： 化工廠1處理污水x1萬m3, 化工廠2處理污水x2萬m3。 min z = 1000 x1 + 800 x2 (2 - x1)/500 2/1000 (1 - 0.2)(2 - x1) + 1.4 - x2/(500 + 200) 2/1000 x1 2 x2 1.4 x1，x2 0 這里min z:表示求z的最小值。200萬m3500萬m32萬m31.4萬m3化工廠1化工廠21000元/萬m3800元/萬m3第1頁/共45頁第二頁，編輯于星期二：二點 四十六分。3第2頁/共45頁第三頁，編輯于星期二：二點 四十六分

2、。4 (1)決策變量：x1，x2，xn 。 一組決策變量表示為問題的一個方案； (2)目標(biāo)函數(shù)：max(min)z z為決策變量的線性函數(shù); (3)約束條件 一組線性不等式。cj為價值系數(shù), bi為資源， aij為技術(shù)系數(shù)(i=1,m;j=1,n).第3頁/共45頁第四頁，編輯于星期二：二點 四十六分。5 解： (1)建立x x1 1 - - x x2 2坐標(biāo)；x2x1 (2)約束條件的幾何表示； Q1Q2Q3Q4 (3)目標(biāo)函數(shù)的幾何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx313212第4頁/共45頁第五頁，編輯于星期二：二點 四十六分。6* 可見，在Q2

3、點z取到最大值。 因此， Q2點所對應(yīng)的解為最優(yōu)解。 Q2點坐標(biāo)為(4，2)。 即: x1 = 4，x2 = 2 由此求得最優(yōu)解：x x1 1* * = 4 x4 x2 2* * = 2 2 最大值：maxmax z z = z z* * = 2x2x1 1 + + 3x3x2 2 = 14(14(元元) )x2x1Q1Q2(4,2)Q3Q4*43第5頁/共45頁第六頁，編輯于星期二：二點 四十六分。7 (2)無窮多最優(yōu)解 eg.4 對eg.1，若目標(biāo)函數(shù) z z = 2x2x1 1 + + 4x4x2 2，此時表示 目標(biāo)函數(shù)的直線與表示 條件的直線平行， 最優(yōu)點在線段Q3Q2上。 即存在無窮

4、多最優(yōu)解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*第6頁/共45頁第七頁，編輯于星期二：二點 四十六分。8o2241x2x第7頁/共45頁第八頁，編輯于星期二：二點 四十六分。91124x1x2第8頁/共45頁第九頁，編輯于星期二：二點 四十六分。10njxmibxaxczjinjjijnjjj, 10, 1 max11 ，簡記：第9頁/共45頁第十頁，編輯于星期二：二點 四十六分。11 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系數(shù)列向量其中第10頁/共

5、45頁第十一頁，編輯于星期二：二點 四十六分。12為系數(shù)矩陣 212222111211 mnmmnnaaaaaaaaaA第11頁/共45頁第十二頁，編輯于星期二：二點 四十六分。13 (2)(2)不等式不等式(，) 對于對于“”情況：在情況：在“”“”左邊加上一個松弛變量（非負）左邊加上一個松弛變量（非負），變?yōu)榈仁?；變?yōu)榈仁剑?對于對于“”“”情況：在情況：在“”“”左邊減去一個剩余變量（非負），變?yōu)榈茸筮厹p去一個剩余變量（非負），變?yōu)榈仁?。式?注意：松弛變量、剩余變量在目標(biāo)函數(shù)中的價值系數(shù)為注意：松弛變量、剩余變量在目標(biāo)函數(shù)中的價值系數(shù)為0 0。 (3)(3)無約束變量無約束變量 令令x

6、 xk k = x xk k - - x xk k”，x xk k,x,xk k” 0 0，代入即可。代入即可。 第12頁/共45頁第十三頁，編輯于星期二：二點 四十六分。14解：令解：令x x3 3 = x x3 3-x-x3 3”，x x3 3,x,x3 3” 0 0； 式加上一個松弛變量式加上一個松弛變量x x4 4；式減去一個剩余變量式減去一個剩余變量x x5 5； 令令z z = -z-z max zmax z = x x1 1- - 2x2x2 2 + + 3(x3(x3 3 - - x x3 3”) ) + + 0 x0 x4 4 + + 0 x0 x5 5 x x1 1 + +

7、 x x2 2 + (x+ (x3 3 - - x x3 3”) ) + + x x4 4 = 7 7 x x1 1 - - x x2 2 + (x+ (x3 3 - - x x3 3”) ) - - x x5 5 = 2 2 -3x -3x1 1 + + x x2 2 + + 2(x2(x3 3 - - x x3 3”) ) = 5 5 x x1 1,x,x2 2,x,x3 3,x,x3 3”,x,x4 4,x,x5 5 0 0 第13頁/共45頁第十四頁，編輯于星期二：二點 四十六分。15 1 1、可行解：滿足條件、可行解：滿足條件、的的X X； 2 2、最優(yōu)解：滿足、最優(yōu)解：滿足條件條件

8、的可行解；的可行解； 3 3、基：取、基：取B B為為A A中的中的m m m m子矩陣，子矩陣，RankRank B B = m m，則稱則稱B B為線性規(guī)為線性規(guī) 劃問題的一個基。劃問題的一個基。 取取B B = (p(p1 1,p,p2 2, ,p,pm m) p) pj j = (a(a1j1j,a,a2j2j, ,a,amjmj) )T T 則稱則稱x x1 1,x,x2 2, ,x,xm m為基變量，其它為非基變量。為基變量，其它為非基變量。第14頁/共45頁第十五頁，編輯于星期二：二點 四十六分。16)!( !mnmnCmn基解個數(shù)TmnmTmBxxxXxxxbBX)0 , 0,

9、(),(m )0()0(2)0(1)0()0(2)0(11 個個基解：第15頁/共45頁第十六頁，編輯于星期二：二點 四十六分。17O(0,0)O(0,0)Q Q1 1(4,0)(4,0)Q Q2 2(4,2)(4,2)Q Q4 4(0,3)(0,3)Q Q3 3(2,3)(2,3)Q Q5 5(4,3)(4,3)6、可行基 基可行解對應(yīng)的B為可行基?？尚薪饪尚薪饣尚薪饣尚薪夥强尚薪夥强尚薪饣饣獾?6頁/共45頁第十七頁，編輯于星期二：二點 四十六分。18非凸集X X(1)(1)X X(1)(1)X X(2)(2)X X(2)(2)凸集X X(1)(1)X X(2)(2)X X(2)(

10、2)X X(1)(1)第17頁/共45頁第十八頁，編輯于星期二：二點 四十六分。191k1iik1i) i (iXX2.2 2.2 基本定理基本定理 1 1、定理、定理1 1 若線性規(guī)劃存在可行域，則若線性規(guī)劃存在可行域，則: : 可行域可行域 D D = X|AXX|AX = b,Xb,X 00為凸集。為凸集。第18頁/共45頁第十九頁，編輯于星期二：二點 四十六分。20 2、定理2 線性規(guī)劃的基可行解對應(yīng)于可行域的頂點。 3、定理3 若線性規(guī)劃有解，則一定存在基可行解為最優(yōu)解。第19頁/共45頁第二十頁，編輯于星期二：二點 四十六分。213.1 3.1 初始基可行解的確定初始基可行解的確定

11、 1、松弛基（松弛變量對應(yīng)的B） eg.8 max z = x1 + 3x2 x1 + 2x2 3 2x1 + 3x2 4 x1,x2 0max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 0 化標(biāo)準(zhǔn)型 取x3、x4為基變量,令非基變量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA則系數(shù)矩陣第20頁/共45頁第二十一頁，編輯于星期二：二點 四十六分。22 選 XB = (x1 x4)T 令x2 = x3

12、 = 0 則 初始基可行解：X(0) = (3 0 0 4)T B , 1 1 3 00 3 2 1 :414321ppppppA則解第21頁/共45頁第二十二頁，編輯于星期二：二點 四十六分。23 分析： A = 1 3 2 2 1 1 找不到單位矩陣基 引入人工變量為初始基變量（2個）第22頁/共45頁第二十三頁，編輯于星期二：二點 四十六分。24 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111對于代入目標(biāo)函數(shù)為非基變量可行為基變量設(shè) , 1, , 1, 1 njjijiinjinxabxnjxmix第23頁/共45頁第二十四頁，編輯于

13、星期二：二點 四十六分。25njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中第24頁/共45頁第二十五頁，編輯于星期二：二點 四十六分。26. .的檢驗數(shù)為稱jjxkx0knjj, 1, 0 0kp0j0kkx第25頁/共45頁第二十六頁，編輯于星期二：二點 四十六分。27 為主元出基行對應(yīng)的變量則若、出基變量 0minmin02lkllklikikiiiiikikiiaxlabaabaab為入基變量。則，若、入基變量kkjj

14、x 0max13.3 3.3 基變換基變換第26頁/共45頁第二十七頁，編輯于星期二：二點 四十六分。28第27頁/共45頁第二十八頁，編輯于星期二：二點 四十六分。29mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，設(shè)第28頁/共45頁第二十九頁，編輯于星期二：二點 四十六分。30cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11 用單純形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x

15、2 0第29頁/共45頁第三十頁，編輯于星期二：二點 四十六分。31cBxBbx1x2x3x4x5 13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x51204001此時的解：x(0) = (0 0 8 16 12)Tz(0) = 0第30頁/共45頁第三十一頁，編輯于星期二：二點 四十六分。32 1=1 2=3 0 x(0)非最優(yōu)解 基變換 max1,2 = 3 = 2 x2入基 min8/2,-,12/4 = 12/4 x5出基13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x5120400113000cBxB

16、bx1x2x3x4x5 0 x38121008/20 x41640010-0 x5120400112/413000第31頁/共45頁第三十二頁，編輯于星期二：二點 四十六分。330 x321010-1/22/10 x4164001016/43x2301001/4-1000-3/41x121010-1/20 x4800-4123x2301001/400-10-1/413000此時的解：x(2)=(2 3 0 8 0)Tz(2)=11x(2)為最優(yōu)解 即： 最優(yōu)解：x* = (2 3 0 8 0)T 最大值：z* = 11第32頁/共45頁第三十三頁，編輯于星期二：二點 四十六分。34x2x1Q1

17、Q2(4,2)Q3(2,3)Q4*O(0,0)第33頁/共45頁第三十四頁，編輯于星期二：二點 四十六分。35第34頁/共45頁第三十五頁，編輯于星期二：二點 四十六分。361500McBxBbx1x2x3x4x5 0 x36231006/2Mx51210-111/21-2M5-M0M0第35頁/共45頁第三十六頁，編輯于星期二：二點 四十六分。371500McBxBbx1x2x3x4x5 0 x350211-11x11/211/20-1/21/209/201/2M+1/21500McBxBbx1x2x3x4x5 0 x36231006/2Mx51210-111/21-2M5-M0M0第36頁

18、/共45頁第三十七頁，編輯于星期二：二點 四十六分。38第37頁/共45頁第三十八頁，編輯于星期二：二點 四十六分。39 mnjxmibxxaxxwjiinnjjijmnn, 1, 0, 1,min11第38頁/共45頁第三十九頁，編輯于星期二：二點 四十六分。40第39頁/共45頁第四十頁，編輯于星期二：二點 四十六分。41CBXBb0 x10 x20 x30 x41x5i0 x36231006/21x51210-111/2-2-10100 x350211-10 x11/211/20-1/2-1/21/200001第40頁/共45頁第四十一頁，編輯于星期二：二點 四十六分。42CBXBb1x15x20 x30 x40 x3502111x11/211/20-1/2-1/209/201/2第41頁/共45頁第四十二頁，編輯于星期二：二點 四十六分。43?；话氵x下標(biāo)小的變量入基可任取其中一個變量入值，有兩個或兩