清華大學(xué)運籌學(xué)課件(完整課件)

1、11 1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型1.1 1.1 問題的提出問題的提出 eg.1 生產(chǎn)計劃問題 問：產(chǎn)品、各生產(chǎn)多少件， 使利潤最大？ 限制 設(shè)備臺時128臺時 材料A4016kg材料B0412kg利潤23 分析： 設(shè)：產(chǎn)品生產(chǎn)x1件， 產(chǎn)品生產(chǎn)x2件。這里z為利潤函數(shù)， max z:表示求z的最大值。目標函數(shù)： max z = 2x1 + 3x2約束條件： 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 2 eg.2 污水處理問題 環(huán)保要求河水含污低于2，河水可自身凈化20%。 問：化工廠1、2每天各處理多少污水，使總費用最少？ 分析： 化工廠1處

2、理污水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元/萬m33線性規(guī)劃的數(shù)學(xué)模型：線性規(guī)劃的數(shù)學(xué)模型： max (min)z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn (=, ) b1 a21x1 + a

3、22x2 + + a2nxn (=, ) b2 am1x1 + am2x2 + + amnxn (=, ) bm x1，x2，xn 04說明： (1)決策變量：x1，x2，xn 。 一組決策變量表示為問題的一個方案； (2)目標函數(shù)：max(min)z z為決策變量的線性函數(shù); (3)約束條件 一組線性不等式。cj為價值系數(shù), bi為資源， aij為技術(shù)系數(shù)(i=1,m;j=1,n).51.2 1.2 圖解法圖解法 eg.eg.33用圖解法求用圖解法求eg.eg.1 1。 max max z z = 2x2x1 1 + + 3x3x2 2 1x 1x1 1 + + 2x2x2 2 8 8 4x

4、 4x1 1 16 16 4x4x2 2 12 12 x x1 1，x x2 2 0 0 解： (1)建立x x1 1 - - x x2 2坐標；x2x1 (2)約束條件的幾何表示； Q1Q2Q3Q4 (3)目標函數(shù)的幾何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx3132126 首先取z = 0，然后，使z逐漸增大，直至找到最優(yōu)解所對應(yīng)的點。* 可見，在Q2點z取到最大值。 因此， Q2點所對應(yīng)的解為最優(yōu)解。 Q2點坐標為(4，2)。 即: x1 = 4，x2 = 2 由此求得最優(yōu)解：x x1 1* * = 4 x4 x2 2* * = 2 2 最大值：max

5、max z z = z z* * = 2x2x1 1 + + 3x3x2 2 = 14(14(元元) )x2x1Q1Q2(4,2)Q3Q4*437討論： (1)唯一最優(yōu)解 maxmax z z = z z* *時，解唯一，如上例。 (2)無窮多最優(yōu)解 eg.4 對eg.1，若目標函數(shù) z z = 2x2x1 1 + + 4x4x2 2，此時表示 目標函數(shù)的直線與表示 條件的直線平行， 最優(yōu)點在線段Q3Q2上。 即存在無窮多最優(yōu)解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*8 (3)無界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 則x2 ，z 。

6、即存在無界解。 在實際問題中，可能 是缺少約束條件。o2241x2x9(4)無可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 無公共部分，無可行域。 即無可行解。 在實際問題中，可能是關(guān)系錯。1124x1x2101.3 1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型 1、標準型 max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm x1，x2，xn 0 njx

7、mibxaxczjinjjijnjjj, 10, 1 max11 ，簡記：11用向量表示 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系數(shù)列向量其中12 用矩陣描述為： max z = CX AX = b X 0 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 為系數(shù)矩陣 212222111211 mnmmnnaaaaaaaaaA132 2、標準型的化法標準型的化法 (1) (1)minmax min zminmax

8、min z = cxcx = -max(-z)-max(-z) max(-z) max(-z) = -min z-min z = -cx-cx 令令zz = -z -z 則則max zmax z = -cx-cx (2)(2)不等式不等式(，) 對于對于“”情況：在情況：在“”“”左邊加上一個松弛變量（非左邊加上一個松弛變量（非負）負），變?yōu)榈仁?；變?yōu)榈仁剑?對于對于“”“”情況：在情況：在“”“”左邊減去一個剩余變量（非左邊減去一個剩余變量（非負），變?yōu)榈仁?。負），變?yōu)榈仁健?注意：松弛變量、剩余變量在目標函數(shù)中的價值系數(shù)為注意：松弛變量、剩余變量在目標函數(shù)中的價值系數(shù)為0 0。 (3)(3

9、)無約束變量無約束變量 令令x xk k = x xk k - - x xk k”，x xk k,x,xk k” 0 0，代入即可。代入即可。 14 eg.eg.77將下述問題化為標準型將下述問題化為標準型 min zmin z = -x-x1 1+2x+2x2 2-3x-3x3 3 x x1 1+ x+ x2 2+ x+ x3 3 7 7 x x1 1- x- x2 2+ x+ x3 3 2 2 -3x-3x1 1+ x+ x2 2+2x+2x3 3 = 5 5 x x1 1,x,x2 2 0 0，x x3 3無約束無約束 解：令解：令x x3 3 = x x3 3-x-x3 3”，x x3

10、 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 + + 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

11、 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 151.4 1.4 線性規(guī)劃解的概念線性規(guī)劃解的概念 設(shè)線性規(guī)劃為 maxmax z z = CX CX AX AX = b b X X 0 0 A A為為m m n n矩陣矩陣, , n n m, Rankm, Rank A A = m (Am (A為行滿秩矩陣）為行滿秩矩陣） 1 1、可行解：滿足條件、可行解：滿足條件、的的X X； 2 2、最優(yōu)解：滿足、最優(yōu)解：滿足條件條件的可行解；的可行解； 3

12、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為基變量，其它為非基變量。為基變量，其它為非基變量。164 4、基解：取、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m) ) a a1111, ,a,a1m1m x x1 1 a a1m+11m+1

13、,a,a1n1n x xm+1m+1 b b1 1 + + = a am1m1,a,ammmm x xm m a amm+1mm+1,a,amnmn x xn n b bm m 基基 基變量基變量 非基非基 非基變量非基變量 令令 x xm+1m+1 = = x xn n = 0 (0 (非基變量為非基變量為0)0) 則則 BXBXB B = b b )!( !mnmnCmn基解個數(shù)TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 個個基解：175、基可行解 滿足式要求的基解。 如右圖所示，各邊交點O,QO,Q1 1,Q,Q2 2,Q,

14、Q3 3,Q,Q4 4均為基可行解；而其延長線的交點Q5為基解，但不是基可行解。O(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為可行基?？尚薪饪尚薪饣尚薪饣尚薪夥强尚薪夥强尚薪饣饣?82 2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義2.1 2.1 基本概念基本概念 1 1、凸集：設(shè)、凸集：設(shè)K K為為E En n(n(n維歐式空間維歐式空間) )的一點集，的一點集，X X(1)(1)K K，X X(2)(2)K K。若

15、若XX(1)(1)+(1-)X+(1-)X(2)(2)K K，則稱則稱K K為凸集。（為凸集。（0 01 1） 非凸集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)(2)X X(1)(1)19 2 2、頂點：、頂點：X XK K，X X(1)(1)K K，X X(2)(2)K (K (任意兩點任意兩點) )。若。若X X不能用不能用XX(1)(1)+(1-)X+(1-)X(2)(2)表示，則稱表示，則稱X X為為K K的一個頂點。的一個頂點。(0(01)1) 注：頂點所對應(yīng)的解是基可行解。注：頂點所對應(yīng)的解是基可行解

16、。 3 3、凸組合：設(shè)、凸組合：設(shè)X X(i)(i)E En n，若存在若存在0 0i i1 1，i i = 1,2,1,2,k,k，使使 , ,則稱則稱X X為為X X(i)(i)(i=1,2,(i=1,2,k),k)的凸組合。的凸組合。1k1iik1i) i (iXX2.2 2.2 基本定理基本定理 1 1、定理、定理1 1 若線性規(guī)劃存在可行域，則若線性規(guī)劃存在可行域，則: : 可行域可行域 D D = X|AXX|AX = b,Xb,X 00為凸集。為凸集。20 證明：證明： 設(shè)設(shè) X X(1)(1)=(=(x1 1(1)(1), ,x2 2(1)(1), ,xn n(1)(1) )T

17、 T D D； X X(2)(2)=(=(x1(2)(2), ,x2 2(2)(2), ,xn n(2)(2) )T T D D； (X (X(1)(1) X X(2)(2) ) 有有 AXAX(1)(1) = b b， AX AX(2)(2) = b b 令令 X X = XX(1)(1) + + (1(1 - - )X)X(2)(2) (0(0 0 10 1 0 0 X X 0 0， 即即D D為凸集為凸集 2、定理2 線性規(guī)劃的基可行解對應(yīng)于可行域的頂點。 3、定理3 若線性規(guī)劃有解，則一定存在基可行解為最優(yōu)解。213 3 單純形法單純形法 基本思路：基本思路：從可行域的一個頂點到另一個

18、頂點迭代求最優(yōu)解。3.1 3.1 初始基可行解的確定初始基可行解的確定 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 化標準型 取x3、x4為基變量,令非基變量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA則系數(shù)矩陣22 2、觀察法 eg.9 max z =

19、x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 0 選 XB = (x1 x4)T 令x2 = x3 = 0 則 初始基可行解：X(0) = (3 0 0 4)T B , 1 1 3 00 3 2 1 :414321ppppppA則解233、人工基 eg.10 max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 0 分析： A = 1 3 2 2 1 1 找不到單位矩陣基 引入人工變量為初始基變量（2個）243.2 3.

20、2 最優(yōu)性的檢驗與解的判別最優(yōu)性的檢驗與解的判別 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111對于代入目標函數(shù)為非基變量可行為基變量設(shè) , 1, , 1, 1 njjijiinjinxabxnjxmix25則njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中26解的判別：1. 若 ，則此時的基可行解為最優(yōu)解；2. 若存在某個非基變量 的檢驗數(shù) ，且 ，則該線性規(guī)劃問題具有無

21、界解（或稱無最優(yōu)解）；3. 若所有 ，又，對于某個非基變量 有 ，則該線性規(guī)劃問題具有無窮多最優(yōu)解。. .的檢驗數(shù)為稱jjxkx0knjj, 1, 0 0kp0j0kkx27 為主元出基行對應(yīng)的變量則若、出基變量 0minmin02lkllklikikiiiiikikiiaxlabaabaab為入基變量。則，若、入基變量kkjjx 0max13.3 3.3 基變換基變換283.4 3.4 旋轉(zhuǎn)運算（消元運算）旋轉(zhuǎn)運算（消元運算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重復(fù)3.23.4， 求出最優(yōu)解。293.5 3.5 單純形表單純形

22、表 展開如下： a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 am1x1 + am2x2 + + amnxn + xn+m = bm - cn+m c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn+mxn+m - z = 0 1x1 + 2x2 + + nxn + 0 xn+1 + + 0 xn+m - z = Z0mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，設(shè)30 建立單純形表cBxBbc1cncn+1c

23、n+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,x2 031 解：標準化，建立單純形表 引入松弛變量x3，x4，x5為初始基變量 max z = x1 + 3x2 + 0 x3 + 0 x4 + 0 x5 x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1,x2,x3,x4,x5 0cBxBbx1x2x3x4x5 13000cBxBbx1x2x3

24、x4x5 0 x38121000 x416400100 x51204001此時的解：x(0) = (0 0 8 16 12)Tz(0) = 032 解的判別 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 x5120400113000cBxBbx1x2x3x4x5 0 x38121008/20 x41640010-0 x5120400112/41300033此時的解：x(1)=(0 3 2 16 0)Tz(1)=9x(1

25、)非最優(yōu)x1入基 x3出基0 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* = 1134X(0)=(0 0 8 16 12)T O(0,0)X(1)=(0 3 2 16 0)T Q4(0,3)X(2)=(2 3 0 8 0)T Q3(2,3)x2x1Q1Q2(4,2)Q3(2,3)Q4*O(0,0)354 4

26、單純形法的進一步討論單純形法的進一步討論4.1 4.1 人工變量法人工變量法 1、大M法（M為很大的正數(shù)） 法則：對于max問題，人工變量在目標函數(shù)中的價值系數(shù)為-M； 對于min問題，人工變量在目標函數(shù)中的價值系數(shù)為M。 eg.12 min z = x1 + 5x2 + 0 x3+0 x4 2x1 + 3x2 + x3 = 6 2x1 + x2 x4 = 1 x1,x2,x3, x4 0 解：min z = x1 + 5x2 + 0 x3 + 0 x4 +Mx5 ：x5為人工變量 2x1 + 3x2 + x3 = 6 2x1 + x2 x4 + x5 = 1 x1,x2,x3,x4,x5 0

27、 列單純形表求解。36min z = x1 + 5x2 + 0 x3 + 0 x4 +Mx5 2x1 + 3x2 + x3 = 6 2x1 + x2 x4 + x5 = 1 x1,x2,x3,x4,x5 0對于min問題，若 minj0中，選下標小的非基變量入基； 對相同的最小比值，選下標小的基變量出基。., , 2 , 10,minmin3得問題的最優(yōu)解時數(shù)滿足當(dāng)所有非基變量的檢驗問題對于問題最優(yōu)解的判別、njzcjjj第二章j與i的計算同max問題。45習(xí)題P45，1.4分別用圖解法和單純形法求解下列線性規(guī)劃,并指出單純形法迭代的每一步相當(dāng)于圖形上的哪一個頂點？0,24261553 2ma

28、x) 1 (21212121xxxxxxxxz0,18231224 52max)2(21212121xxxxxxxxz46對偶理論與靈敏度分析對偶理論與靈敏度分析1 1 單純形法的矩陣描述單純形法的矩陣描述 設(shè)max z = CX AX = b X 0 A為mn階矩陣 RankA=m ,取B為可行基, N為非基， NBNBCCCNBAXXX , ,0, maxNBNBNNBBXXbNXBXXCXCz47bBCbBNBIBN111- 1 0 0 :矩陣單純形表0zXCXCbNXBXNNBBNBbBCzXNBCCXbBNXBBXBBNBNBNB11111)(0bBCzXXbBNXBIXBNNBNB

29、111048bBCzXXbBNXBIXBNNBNB1110NBCCbBCzbBXXBNNBBN111 , , 0 得令.,0 !出則最優(yōu)解直接由上式求若能找到最優(yōu)為最優(yōu)基的使注BBNbBCzbBXB11 0 目標函數(shù)基可行解49求解步驟：.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出結(jié)果重復(fù)的求出此得到新的出基行對應(yīng)的則若入基則若基變換否則轉(zhuǎn)下一步則得最優(yōu)解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklikikiikkNjNjBNN5032利潤12kg40材料B16kg04材料A8臺時 21設(shè)備

30、臺時限制 2 2 對偶問題的提出對偶問題的提出 eg.1 制定生產(chǎn)計劃 M1: max z = 2x1 + 3x2 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 51 現(xiàn)在出租，設(shè)y1為設(shè)備單位臺時的租金 y2,y3為材料A、B轉(zhuǎn)讓附加費(kg-1) 則M2為M1的對偶問題，反之亦然。M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 032利潤12kg40材料B16kg04材料A8臺時 21設(shè)備臺時限制 0,124 16 482 32max 212121211xxxxxxxxzM52 一般的，原問題

31、：max z = CX AX b X 0 對偶問題：min w = Yb YA C Y 0 比較： max z min w 決策變量為n個 約束條件為n個 約束條件為m個 決策變量為m個 “” “”533 3 對偶問題的化法對偶問題的化法 1、典型情況 eg.2 max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0對偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 054 2、含等式的情況 eg.3 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 +

32、2x2 + 5x3 4 x1,x2,x3 0對偶：min w = 3y1-3y1”+4y2 2y1-2y1”+ y2 1 y1- y1”+2y2 2 3y1-3y1”+5y2 4 y1,y1”,y2 0令y1=y1-y1”,則： min w = 3y1+4y2 2y1 + y2 1 y1 +2y2 2 3y1 +5y2 4 y2 0，y1無約束一般，原問題第i個約束取等式，對偶問題第i個變量無約束。 2x1 + x2 + 3x3 3-2x1 - x2 - 3x3 -355 3、含“”的max問題 eg.4 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 +

33、 2x2 + 5x3 4 x1,x2,x3 0對偶：min w = -3y1 + 4y2 -2y1 + y2 1 -y1 + 2y2 2 -3y1 + 5y2 4 y1,y2 0令y1 = -y1，則： min w = 3y1 + 4y2 2y1 + y2 1 y1 + 2y2 2 3y1 + 5y2 4 y1 0,y2 0-2x1 - x2 - 3x3 -356一般: max問題第i個約束取“”，則min問題第i個變量 0 ； min問題第i個約束取“”，則max問題第i個變量 0 ； 原問題第i個約束取等式，對偶問題第i個變量 無約束； max問題第j個變量 0 ,則min問題第j個約束取

34、“” ； min問題第j個變量 0 ，則max問題第j個約束取“” ； 原問題第j個變量無約束，對偶問題第j個約束取等式。57 eg.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無約束對偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 = 1 y1 0,y2 0,y3無約束 584 4 對偶問題的性質(zhì)對偶問題的性質(zhì) 1、對稱性 對偶問

35、題的對偶為原問題.0 )max(0;,min)max(YCYAYbwYCYACYAYbww即0)min(XbAXCXw0 , ,min 0 , ,maxYCYAYbwXbAXCXz590)min(XbAXCXw證畢令0 max maxmax)min(XbAXCXzwzCXwww60.,:的可行解分別為原問題和對問題設(shè)證明YXXCXAYCAYCYAbYXAYbXAbAX證畢bYXCbYXAYXC bYXCYX ,. 2則存在為對偶問題的可行解為原問題的可行解設(shè)弱對偶性61推論：(1) max問題任一可解的目標值為min問題目標值的一個下界；(2) min問題任一可解的目標值為max問題目標值的一

36、個上界。3、無界性 若原問題(對偶問題)為無界解，則對偶問題(原問題)為無可行解。注：該性質(zhì)的逆不存在。若原(對偶)問題為無可行解，對偶(原問題)問題或為無界解，或為無可行解。62 4、最優(yōu)性 設(shè)X*，Y*分別為原問題和對偶問題可行解，當(dāng) CX*=Y*b時， X*，Y*分別為最優(yōu)解。證畢為最優(yōu)解即為最優(yōu)解即由弱對偶性題的任一可行解分別為原問題和對偶問設(shè)證明 * )2( ) 1 (.,:*YbYbYbYCXbYXCXXCCXbYXCYX63 5、對偶定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解， 且目標值相等。*11*1*1*1*11*0)(:, 0.:wbYbBCbBCCCXzbBXbBCb

37、YwYBCYCAYCABCABCCXBNBBBBB則其目標值為因原問題最優(yōu)解則為對偶問題的可行解若其中全部檢驗數(shù)可表示為則其對應(yīng)的基矩陣存在為原問題的最優(yōu)解設(shè)證明64Y*為對偶問題的最優(yōu)解，且原問題和對偶問題的目標值相等。證畢6、松弛性 若X*，Y*分別為原問題及對偶問題的可行解， 那么Ys*X*=0，Y*Xs*=0，當(dāng)且僅當(dāng)X*，Y*分別為 最優(yōu)解。證明：0,0max:SSSXXbXAXXCXz設(shè)原問題為0,0min:SSSYYCYYAYYbw設(shè)對偶問題為650,0maxSSSXXbXAXXCXz0,0minSSSYYCYYAYYbwXYYAXXYYACXzSS)(SSYXYAXXAXYYb

38、w)(將b,Cb,C分別代入目標函數(shù)：;,0, 0,*為最優(yōu)解時當(dāng)為可行解若YXzwXYXYYXSS證畢必有則分別為最優(yōu)解若另一方面0 , 0,*SSXYXYzwYX66TSmSSSTnxxxXxxxX) () (*2*1*2*1* ) ( ) ( *2*1*2*1*snSSSmyyyYyyyY 其中：用分量表示： mixynjxySiijSj, 2 , 1 , 0;, 2 , 1 , 0*67 7、檢驗數(shù)與解的關(guān)系 (1)原問題非最優(yōu)檢驗數(shù)的負值為對偶問題的一個基解。 (2)原問題最優(yōu)檢驗數(shù)的負值為對偶問題的最優(yōu)解。 分析：max z = CX + 0Xs = (C 0)(X Xs)T AX

39、 + Xs = b X,Xs 0 min w = Yb + YS0 YA - Ys = C Y,Ys 0 檢驗數(shù)： = (C 0)- CBB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X對應(yīng)的檢驗數(shù) s = - CBB-1 Xs對應(yīng)的檢驗數(shù) 68 eg.6 已知：min w = 20y1 + 20y2 的最優(yōu)解為y1*=1.2,y2*=0.2-ys1 y1 + 2y2 1 試用松弛性求對偶-ys2 2y1 + y2 2 問題的最優(yōu)解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0 解：對偶問題

40、max z = x1 + 2x2 + 3x3 + 4x4 x1 + 2x2 + 2x3 + 3x4 20 +xs1 2x1 + x2 + 3x3 + 2x4 20 +xs2 x1,x2,x3,x4 0 y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 069 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 =右

41、邊 ys3* = 0 x3*待定 由 3y1* + 2y2* = 4 =右邊 ys4* = 0 x4*待定 有 2x3* + 3x4* = 20 3x3* + 2x4* = 20 x3* = 4 x4* = 4 最優(yōu)解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*705 5 對偶問題的經(jīng)濟含義對偶問題的經(jīng)濟含義影子價格影子價格 最優(yōu)情況：z* = w* = b1y1* + + biyi* + + bmym*的影子價格為稱i*i*ibzbyyi*x2x1Q2 eg.7 max z = 2x1 + 3x2 x1

42、 + 2x2 8 4x1 16 4x2 12 x1,x2 0b1： 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*Q2Q2”716 6 對偶單純形法對偶單純形法 單純形法：由 XB = B-1b 0，使j 0，j = 1,m對偶單純形法：由j 0(j= 1,n)，使XB = B-1b 0 步驟：步驟：(1)保持j 0，j= 1,n，確定XB，建立計算表格； (2)判別XB = B-1

43、b 0是否成立？ 若成立，XB為最優(yōu)基變量； 若不成立，轉(zhuǎn)(3)； 72 (4)消元運算，得到新的XB。(3)基變換 出基變量， 出基；，則若lliiixmibbb, 10min入基變量， 入基。則若kaljajxalkkljj0min重復(fù)（2）-（4）步，求出結(jié)果。73 eg.8 用對偶單純形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0解：max z = -2x1 - 3x2 - 4x3 + 0 x4 + 0 x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x

44、3 + x5 = -4 x1,x2,x3,x4,x5 074-2-3-400CBXBbx1x2x3x4X50 x4-10 x5-4出出出x4,x5 0 最優(yōu)最優(yōu)解：最優(yōu)解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0目標值：目標值：w* = -z* = 4757 7 靈敏度分析靈敏度分析njpBCcABCCNBCCjBjjBBNN, 2 , 1, 0 0 0 :111 或或最優(yōu)性條件分析 變化對最優(yōu)解的影響。j ,ijiacb0 :1bBXB可行性條件76的變化資源ib 1 . 7TiTmiiiibbbbbbbbbbbb)0b 0 0() ( 21 bBbBb

45、bBbBXB1111)(.,0 11這里用到可行性條件保持問題的最優(yōu)性不變的變化范圍求出由ibbBbB77例1 已知下述問題的最優(yōu)解及最優(yōu)單純形表,0,124 164 82 00032max54321524132154321xxxxxxxxxxxxxxxxxz., ) 12使最優(yōu)基不變的變化范圍求 b. 4 )21時的最優(yōu)解求b78最優(yōu)單純形表如下:0-1/8-3/2000-1/81/2102311/2-2004001/40014200032bBXBC5x4x3x2x1x1x5x2x14 Z)4 0 0 2 4(,*TX此時7922216 1) :bbb解08/12/112/1204/101B

46、2441216808/12/112/1204/101*bBXB由最優(yōu)單純形表得:80)(012bbBb221118/12/14/12440008/12/112/1204/10244)(bbbBbBbbB0008/22/44/4222bbb08/202/404/4222bbb.1682最優(yōu)基不變b81TTbb)0 0 4()0 0 ( )214 44 28024400408/12/112/1204/10244)(111bBbBbbB不可行!用對偶單純形法計算82-3/4-1/20001/400103x23-1/2-1/41002x3001/40014x120-1/8-3/2000-1/81/21

47、02+2311/2-2004-8x5001/40014+0 x12ix5x4x3x2x1bXBCB00032x23/4-2)(17 : . 0, 0, 2, 3, 4 :*5*4*3*2*1元目標值最優(yōu)解zxxxxx83的變化價值系數(shù)jc 2 . 7.01分兩種情況討論進行分析根據(jù)最優(yōu)性條件NBCCBNN的變化非基變量價值系數(shù)kc. 1kBkkpBCc1:原檢驗數(shù)/ :kkkkkccccc變化kkkBkkkcpBCcc1/., 0 :/此時最優(yōu)解不變令kkkkkcc84例2 求例1 c4的變化范圍,使最優(yōu)解不變.0-1/8-3/2000-1/81/2102311/2-2004x5001/400

48、14x12ix5x4x3x2x1bXBCB00032x204c8/1)8/1(8/1444c由解:. 8/1 4時最優(yōu)解不變即c85的變化基變量價值系數(shù)rc. 2NBCCBNN1 原BBBCCC 若NBCNBCNBCCNBCCCBNBBNBBNN1111/ )( 則分析:)0 0 0( ) ( :21 rBmrBcCccccC其中.變化影響所有可見jrc86方法:.0 1/的變化范圍求出令rBNNcNBC例3 求例1 c2的變化范圍,使最優(yōu)解不變.0-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x287解:0

49、-1/8-3/2000-1/81/2102311/2-2004x5001/40014x12ix5x4x3x2x1bXBCB00032x2) 0 0( ),3 0 2(2cCCBB 1/8)- (-3/2) (43N ) (/4/3/n44414/433313/3pcpBcpcpBcBBBB8802232/120)c 0 0(232233/3cpcB08818/12/14/1)c 0 0(812244/4cpcB1322cc. 13 2時最優(yōu)解不變即c89的變化技術(shù)系數(shù)jia 3 . 7kBkkpBCc1 原T1k k k 0) a 0( ) ( , lkkTmklkkkkkklllpaaapp

50、ppaaaa若分析:.k 的變化討論非基變量技術(shù)系數(shù)la90lklkakBkBkkkBkKpBCpBCcppBCc111 )( 則TlkmlkkBkapBC)00)(11 0lklkka令., 最優(yōu)解不變時當(dāng)lkkla91例4 求例1 a24的變化范圍,使最優(yōu)解不變.解:242424241, 1aaaa) (0) 1/8 2/3( 3) 0 2(32111BBCB24242448181aa08181 244a令. , 1 24此時最優(yōu)解不變a92 例5 在例1的基礎(chǔ)上，企業(yè)要增加一個新產(chǎn)品,每件產(chǎn)品需2個臺時，原材料A 6kg，原材料B 3kg，利潤 5元/件，問如何安排各產(chǎn)品的產(chǎn)量，使利潤最

51、大？解：0,1234 1664 822 532max3213231321321xxxxxxxxxxxxxz532利潤12340料B16604料A8221設(shè)備b則有為新產(chǎn)品生產(chǎn)的件數(shù)設(shè),3x9331 )2pB計算25. 025 . 136208/12/112/1204/1031pB0453620 81 2353133pBCcB3 ) 1計算表明生產(chǎn)新品有利。94., ) 3331加入原最優(yōu)表計算將pB2 ,53出基主元為入基 xx5/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x2ix395

52、5/40-1/8-3/2001/40-1/81/21023211/2-2004x503/201/40014x12x5x4x3x2x1bXBCB500032x28/34/28ix320-5/8-7/16-1/4000-1/8-3/163/4103/2311/21/4-10020-3/4-1/83/2011x12x5x4x3x2x1bXBCB500032x2ix3x35)(5 . 2 )(5 .16 . 2 , 2/3 , 1*3*2*1元增加元zxxx96小結(jié)0 maxXbAXCXz1、對偶問題及其化法0 minYCYAYbw原問題決策變量決定對偶問題約束條件關(guān)系原問題約束條件決定對偶問題決策變

53、量取值方向。972、檢驗數(shù)的計算方法njpCcpBCcjBjjBjj, 2 , 1 , 1 或NBCCBNN1 ABCCB1 或階矩陣階矩陣 :, :1mmBmnnmAjjpBp1983、對偶問題的性質(zhì)4、對偶單純形法弱對偶性無界性最優(yōu)性松弛性檢驗數(shù)與對偶問題的解99njpBCcjBjj, 2 , 1, 01 變化對最優(yōu)解的影響分析ijjiacb,0 :1NBCCBNN最優(yōu)性條件0 1ABCCB0 :1bBXB可行性條件5、靈敏度分析100的變化技術(shù)系數(shù)jia )3(的變化基變量價值系數(shù)rc 2的變化非基變量價值系數(shù)kc 1的變化價值系數(shù)jc )2(的變化資源ib ) 1 (的變化分析非基變量

54、技術(shù)系數(shù)101整數(shù)規(guī)劃整數(shù)規(guī)劃Integer Programming1 1 問題的提出問題的提出 eg.1 用集裝箱托運貨物 問：甲乙貨物托運多少箱，使總利潤最大？貨物m3/箱百斤/箱百元/箱甲5220乙4510限制2413 分析：設(shè)x1為甲貨物托運箱數(shù)，x2為乙貨物托運箱數(shù)。 則 max z = 20 x1 + 10 x2 5x1 + 4x2 24 2x1 + 5x2 13 x1,x2 0 x1,x2取整數(shù)102圖解法：x1x243210124.82.6(4,1) x1* = 4 x2* = 1 zI* = 90 103 一般，整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于相應(yīng)線性規(guī)劃的最優(yōu)解。 對于max問題，

55、 zI* zl* 對于min問題， zI* zl* 數(shù)學(xué)模型：取整數(shù)jjnjiijijnjjjxnjxmibxaxcz, 10, 1max111042 2 分枝定界法分枝定界法 用單純形法，去掉整數(shù)約束IP LP xl* 判別是否整數(shù)解xI* = xl*Yes去掉非整數(shù)域No多個LP1053 0-13 0-1規(guī)劃（規(guī)劃（x xi i = 0 0或或1 1的規(guī)劃）的規(guī)劃） eg.2 選擇投資場所 Ai投資Bi元，總投資B， 收益Ci元. 問：如何選擇Ai，使收益最大？A6A7A4A5A3A2A1最多選2個最少選1個最少選1個 分析：引入 xi = 1 Ai選中 0 Ai落選 max z = C1

56、x1 + C2x2 + + C7x7 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 B1x1 + B2x2 + + B7x7 B xi = 0或1南區(qū)西區(qū)東區(qū)106 eg.3 求解如下0-1規(guī)劃 max z = 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1 + x2 3 4x2 + x3 6 x1,x2,x3 = 0或1 解：(1)觀察一個可行解x1 = 1 x2 = x3 = 0 此時，z = 3 (2)增加一個過濾條件 3x1-2x2+5x33 *107(3)列表計算x1x2x3*可行？zx1x2x3*可行？z

57、000001010011100101110111x1x2x3*可行？z0000001010011100101110111x1x2x3*可行？z00000015-11015010011100101110111x1x2x3*可行？z00000015-11015010-2011100101110111x1x2x3*可行？z00000015-11015010-2011315100101110111x1x2x3*可行？z00000015-11015010-2011315100311103101110111x1x2x3*可行？z00000015-11015010-201131510031110310180

58、2118110111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111x1x2x3*可行？z00000015-11015010-20113151003111031018021181101111626 最優(yōu)解：x1* = 1 x2* = 0 x3* = 1 此時，z* = 8第四章108非線性數(shù)規(guī)劃非線性數(shù)規(guī)劃 Nonlinear Programming1 1 問題的提出問題的提出 eg.1 某單位擬建一排廠房，廠房建筑平面如圖所示。由于資金及材料的限制，圍墻及隔墻的總長度不能超過80米。為使建筑面積最大，應(yīng)如何選擇長寬尺寸

59、？1x2x0,8052)(max212121xxxxxxxf分析：設(shè)長為 米，寬為 米，則有1x2x f(x)為非線性函數(shù)109例2 設(shè)某物理過程具有如下規(guī)律 用試驗法 。 現(xiàn)要確定參數(shù) 使所得試驗點構(gòu)成的曲線與理論曲線誤差平方和為最小，且滿足 txexxt321)(mittii, 2 , 1,)( 值時的求得,321xxx., 1321非負xxx110非線性規(guī)劃： 目標函數(shù)或（和）約束條件為非線性函數(shù)的規(guī)劃。031)()()(min2112213xxxexxtxfmitxii分析： f(x)為非線性函數(shù)，求最小。1112 2 基本概念2.1非線性規(guī)劃的數(shù)學(xué)模型數(shù)學(xué)模型的一般描述 約束條件目標

60、函數(shù) (2) ,1,2,j , 0)( (1) )(minxgxfjTnjxxxxxgxf) ( )(),(:21 為非線性函數(shù)其中112或 (3) ,1,2,j , 0)( (2) , , 2 , 1 , 0)(1) )(minxgmixhxfji.)(),(),(:為非線性函數(shù)其中xgxhxfji1132.2非線性規(guī)劃的圖示例1 求解如下非線性規(guī)劃問題06)2()2()(min212221xxxxxf解. 2)()(min, 3,),()(,)(*2*1xfxfxxDDcxfxf最小值得到最優(yōu)解點在點等值線與直線相切于常數(shù)即的等值線作o2 22 26 66 61x2x)3 , 3(D114