清華大學(xué)運(yùn)籌學(xué)課件(完整課件)匯編

1、 2 eg.2 污水處理問題 環(huán)保要求河水含污低于2，河水可自身凈化20%。 問：化工廠1、2每天各處理多少污水，使總費(fèi)用最少？ 分析： 化工廠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萬m3 500萬m3 2萬m3 1.4萬m3 化工廠1 化工廠21000元/萬m3 800元/萬m3 3 線性規(guī)劃的數(shù)學(xué)模型：線性規(guī)劃

2、的數(shù)學(xué)模型： max (min)z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn (=, ) b1 a21x1 + a22x2 + + a2nxn (=, ) b2 am1x1 + am2x2 + + amnxn (=, ) bm x1，x2，xn 0 4 說明： (1)決策變量：x1，x2，xn 。 一組決策變量表示為問題的一個(gè)方案； (2)目標(biāo)函數(shù)：max(min)z z為決策變量的線性函數(shù); (3)約束條件 一組線性不等式。 cj為價(jià)值系數(shù), bi為資源， aij為技術(shù)系數(shù)(i=1,m;j=1,n) . 5 1.2 1.2 圖解法圖解法 e

3、g.eg.33用圖解法求用圖解法求eg.eg.1 1。 max max z z = 2x2x1 1 + + 3x3x2 2 1x 1x1 1 + + 2x2x2 2 8 8 4x 4x1 1 16 16 4x4x2 2 12 12 x x1 1，x x2 2 0 0 解： (1)建立x x1 1 - - x x2 2坐標(biāo)； x2 x1 (2)約束條件的幾何表示； Q1 Q2 Q3Q4 (3)目標(biāo)函數(shù)的幾何表示； * z z = 2x2x1 1 + + 3x3x2 2 o 4 3 zxx 3 1 3 2 12 6 首先取z = 0，然后，使z逐 漸增大，直至找到最優(yōu)解所對(duì) 應(yīng)的點(diǎn)。 * 可見，在

4、Q2點(diǎn)z取到最大值。 因此， Q2點(diǎn)所對(duì)應(yīng)的解為最優(yōu)解。 Q2點(diǎn)坐標(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(元元) ) x2 x1 Q1 Q2(4,2) Q3Q4 * 4 3 7 討論： (1)唯一最優(yōu)解 maxmax z z = z z* *時(shí)，解唯一，如上例。 (2)無窮多最優(yōu)解 eg.4 對(duì)eg.1，若目標(biāo)函數(shù) z z = 2x2x1 1 + + 4x4x2 2，此時(shí)表示 目標(biāo)函數(shù)的直線與表示

5、條件的直線平行， 最優(yōu)點(diǎn)在線段Q3Q2上。 即存在無窮多最優(yōu)解。 x2 x1 Q1 Q2(4,2) Q3(2,3)Q4 o 4 3 * 8 (3)無界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 則x2 ，z 。 即存在無界解。 在實(shí)際問題中，可能 是缺少約束條件。 o 2 2 41 x 2 x 9 (4)無可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 無公共部分，無可行域。 即無可行解。 在實(shí)際問題中，可能是關(guān)系錯(cuò)。 1 1 2 4 x1 x2 10 1.3 1.3 線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃

6、的標(biāo)準(zhǔn)型 1、標(biāo)準(zhǔn)型 max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm x1，x2，xn 0 njx mibxa xcz j i n j jij n j jj , 10 , 1 max 1 1 ， 簡(jiǎn)記： 11 用向量表示 njx bxp ts CXz j n j jj , 1, 0 . max 1 T m j T mjjjj n T n bbbb xaaap cccC xxxX ) ( :) ( ) ( ) (:

7、 21 21 21 21 的系數(shù)列向量 其中 12 用矩陣描述為： max z = CX AX = b X 0 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 為系數(shù)矩陣 21 22221 11211 mnmm n n aaa aaa aaa A 13 2 2、標(biāo)準(zhǔn)型的化法標(biāo)準(zhǔn)型的化法 (1) (1)minmax min zminmax min z = cxcx = -max(-z)-max(-z) max(-z) max(-z) = -min z-min z = -cx-cx 令令zz = -z -z 則則max zmax z = -cx

8、-cx (2)(2)不等式不等式(，) 對(duì)于對(duì)于“”情況：在情況：在“”“”左邊加上一個(gè)松弛變量（非左邊加上一個(gè)松弛變量（非 負(fù)）負(fù)），變?yōu)榈仁?；變?yōu)榈仁剑?對(duì)于對(duì)于“”“”情況：在情況：在“”“”左邊減去一個(gè)剩余變量（非左邊減去一個(gè)剩余變量（非 負(fù)），變?yōu)榈仁?。?fù)），變?yōu)榈仁健?注意：松弛變量、剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為注意：松弛變量、剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為0 0。 (3)(3)無約束變量無約束變量 令令x xk k = x xk k - - x xk k”， ，x xk k ,x ,xk k” ” 0 0，代入即可。代入即可。 14 eg.eg.77將下述問題化為標(biāo)準(zhǔn)型將下

9、述問題化為標(biāo)準(zhǔn)型 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 3 ,x ,x3 3” ” 0 0； 式加上一個(gè)松弛變量式加上一個(gè)松弛變量x x4 4；式減去一個(gè)剩余變量式減去一個(gè)剩余變量x x5 5； 令令z z = -z -z max

10、zmax z = x x1 1- - 2x 2x2 2 + + 3(x3(x3 3 - - x x3 3”) ) + + 0 x 0 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 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” ”,

11、x ,x4 4,x,x5 5 0 0 15 1.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 3、基：取、基：取B B為為A A中的中的m m m m子矩陣，子矩陣，RankRank B B = m m，則稱則稱B B為線性為線性 規(guī)規(guī) 劃問題的

12、一個(gè)基。劃問題的一個(gè)基。 取取B B = (p(p1 1,p,p2 2, ,p,pm m) p) pj j = (a(a1j 1j,a ,a2j 2j, , ,a,amj mj) )T T 則稱則稱x x1 1,x,x2 2, ,x,xm m為基變量，其它為非基變量。為基變量，其它為非基變量。 16 4 4、基解：取、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m) ) a a11 11, ,a ,a1m 1m x x1 1 a a1m+1 1m+1,a ,a1n 1n x xm+1 m+1 b b1 1 + + = a am1 m1,a ,amm mm x xm m a

13、amm+1 mm+1,a ,amn mn x xn n b bm m 基基 基變量基變量 非基非基 非基變量非基變量 令令 x xm+1 m+1 = = x xn n = 0 (0 (非基變量為非基變量為0)0) 則則 BXBXB B = b b )!( ! ! mnm n C m n 基解個(gè)數(shù) T mn m T mB xxxX xxxbBX )0 , 0,( ),( m )0()0( 2 )0( 1 )0()0( 2 )0( 1 1 個(gè) 個(gè) 基解： 17 5、基可行解 滿足式要求的基解。 如右圖所示，各邊交點(diǎn)O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4 均為基可行解；而其延長(zhǎng)

14、線的交點(diǎn)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、可行基 基可行解對(duì)應(yīng)的B為可行基。 可行解可行解 基可行解基可行解非可行解非可行解 基解基解 18 2 2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 2.1 2.1 基本概念基本概念 1 1、凸集：設(shè)、凸集：設(shè)K K為為E En n(n(n維歐式空間維歐式空間) )的一點(diǎn)集，的一點(diǎn)集，X X(1) (1) K K，X X(2) (2) K K。 若若XX(1

15、) (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、頂點(diǎn)：、頂點(diǎn)：X XK K，X X(1) (1) K K，X X(2) (2) K (K (任意兩點(diǎn)任意兩點(diǎn)) )。若。若X X不能用不能用 XX(1) (1)+(1-)X +(1-)X(2) (2)表示，則稱 表示，則稱X X為為K K的一個(gè)頂點(diǎn)。的一個(gè)頂點(diǎn)。(0(01)1) 注：頂

16、點(diǎn)所對(duì)應(yīng)的解是基可行解。注：頂點(diǎn)所對(duì)應(yīng)的解是基可行解。 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)的凸組合。的凸組合。 1 k 1i i k 1i ) i ( iX X 2.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)

17、=( =(x1 1(1) (1), ,x2 2(1)(1), , ,xn n(1) (1) )T 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ī)劃的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)。 3、定理

18、3 若線性規(guī)劃有解，則一定存在基可行解 為最優(yōu)解。 21 3 3 單純形法單純形法 基本思路：基本思路：從可行域的一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)迭代求最優(yōu)解。 3.1 3.1 初始基可行解的確定初始基可行解的確定 1、松弛基（松弛變量對(duì)應(yīng)的B） eg.8 max z = x1 + 3x2 x1 + 2x2 3 2x1 + 3x2 4 x1,x2 0 max 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

19、0 3 4)T B , 1 0 3 2 0 1 2 1 434321 ppppppA 則系數(shù)矩陣 22 2、觀察法 eg.9 max z = 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 0 0 3 2 1 : 414321 ppppppA 則 解 23 3、人工基 eg.10 max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1

20、+ x2 + x3 = 4 x1,x2,x3 0 分析： A = 1 3 2 2 1 1 找不到單位矩陣基 引入人工變量為初始基變量（2個(gè)） 24 3.2 3.2 最優(yōu)性的檢驗(yàn)與解的判別最優(yōu)性的檢驗(yàn)與解的判別 mnjx mibxxa xcxcz j n j iinjij m i inin n j jj , 1 0 , 1 max 1 11 對(duì)于 代入目標(biāo)函數(shù) 為非基變量 可行為基變量設(shè) , 1, , 1, 1 n j jijiin j in xabx njx mix 25 則 n j jj n j jjj n j m i jijinj m i iin n j m i n j jijiinjj

21、xZ xzcZ xaccbc xabcxcz 1 0 1 0 111 111 )( )( )( m i ijinjjjj m i iin aczzcbcZ 11 0 , , 其中 26 解的判別： 1. 若 ，則此時(shí)的基可行解為最優(yōu)解； 2. 若存在某個(gè)非基變量 的檢驗(yàn)數(shù) ，且 ， 則該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）； 3. 若所有 ，又，對(duì)于某個(gè)非基變量 有 ， 則該線性規(guī)劃問題具有無窮多最優(yōu)解。 . .的檢驗(yàn)數(shù)為稱 jj x k x0 k nj j , 1, 0 0 k p 0 j 0 k k x 27 為主元 出基行對(duì)應(yīng)的變量則 若 、出基變量 0minmin0 2 lk l l

22、k l ik ik i i i i ik ik i i a xl a b a a b a a b 為入基變量。則，若 、入基變量 kkj j x 0max 1 3.3 3.3 基變換基變換 28 3.4 3.4 旋轉(zhuǎn)運(yùn)算（消元運(yùn)算）旋轉(zhuǎn)運(yùn)算（消元運(yùn)算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重復(fù)3.23.4， 求出最優(yōu)解。 29 3.5 3.5 單純形表單純形表 展開如下： a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a21x1 + a22x2 + + a2nxn + xn+2 = b2 -

23、 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 = Z0 mn, 2 , 1j0 x bxxa xczmax j iin n 1j jij mn 1j jj ， 設(shè) 30 建立單純形表 cBxBb c1 cncn+1 cn+m x1 xnxn+1 xn+m cn+1xn+1b1a11 a1n1 01 cn+mxn+mbmam1 amn0 1m -z -z01

24、 n 0 0j eg.11 用單純形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0 31 解：標(biāo)準(zhǔn)化，建立單純形表 引入松弛變量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 0 cBxBbx1x2x3x4x5 13000 cBxBbx1x2x3x4x5 0 x3812100 0 x41640010 0 x51204001 此時(shí)的解： x(0) = (0 0

25、 8 16 12)T z(0) = 0 32 解的判別 1=1 2=3 0 x(0)非最優(yōu)解 基變換 max1,2 = 3 = 2 x2入基 min8/2,-,12/4 = 12/4 x5出基 13000 cBxBbx1x2x3x4x5 0 x3812100 0 x41640010 0 x51204001 13000 cBxBbx1x2x3x4x5 0 x38121008/2 0 x41640010- 0 x5120400112/4 13000 33 此時(shí)的解： x(1)=(0 3 2 16 0)T z(1)=9 x(1)非最優(yōu) x1入基 x3出基 0 x321010-1/22/1 0 x41

26、64001016/4 3x2301001/4- 1000-3/4 1x121010-1/2 0 x4800-412 3x2301001/4 00-10-1/4 13000 此時(shí)的解： x(2)=(2 3 0 8 0)T z(2)=11 x(2)為最優(yōu)解 即： 最優(yōu)解：x* = (2 3 0 8 0)T 最大值：z* = 11 34 X(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) x2 x1 Q1 Q2(4,2) Q3(2,3)Q4 * O(0,0) 35 4 4 單純形法的進(jìn)一步討論

27、單純形法的進(jìn)一步討論 4.1 4.1 人工變量法人工變量法 1、大M法（M為很大的正數(shù)） 法則：對(duì)于max問題，人工變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為-M； 對(duì)于min問題，人工變量在目標(biāo)函數(shù)中的價(jià)值系數(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 列單純形表求解。

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

29、 2426 1553 2max) 1 ( 21 21 21 21 xx xx xx xxz 0, 1823 122 4 52max)2( 21 21 2 1 21 xx xx x x xxz 46 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析 1 1 單純形法的矩陣描述單純形法的矩陣描述 設(shè)max z = CX AX = b X 0 A為mn階矩陣 RankA=m ,取B為可行基, N為非基， NB N B CCCNBA X X X , , 0, max NB NB NNBB XX bNXBX XCXCz 47 bBC bBNBI BN 1 11 - 1 0 0 : 矩陣單純形表 0 zXCXC

30、bNXBX NNBB NB bBCzXNBCCX bBNXBBXB BNBNB NB 11 111 )(0 bBCzXX bBNXBIX BNNB NB 1 11 0 48 bBCzXX bBNXBIX BNNB NB 1 11 0 NBCC bBCz bBX X BNN B B N 1 1 1 , , 0 得 令 ., ,0 ! 出則最優(yōu)解直接由上式求若能找到最優(yōu) 為最優(yōu)基的使注 B B N bBCz bB X B 1 1 0 目標(biāo)函數(shù) 基可行解 49 求解步驟： .42 .,. 4 . , )( )( 0)( )( )( min ,)(0)(max . 3 ., 0. 2 ,. 1 1 1

31、 1 1 1 1 1 1 步直到求出結(jié)果重復(fù) 的求出此得到新的 出基行對(duì)應(yīng)的則 若 入基則若 基變換 否則轉(zhuǎn)下一步則得最優(yōu)解若 求取可行基 BBB xl PB bB PB PB bB x NBCC BB l lk l ik ik i i kkNjN j BNN 50 32利潤(rùn) 12kg40材料B 16kg04材料A 8臺(tái)時(shí) 21設(shè)備臺(tái)時(shí) 限制 2 2 對(duì)偶問題的提出對(duì)偶問題的提出 eg.1 制定生產(chǎn)計(jì)劃 M1: max z = 2x1 + 3x2 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 51 現(xiàn)在出租，設(shè)y1為設(shè)備單位臺(tái)時(shí)的租金 y2,y3為材料A、B轉(zhuǎn)讓附加費(fèi)(k

32、g-1) 則M2為M1的對(duì)偶問題， 反之亦然。 M2: min w = 8y1 + 16y2 + 12y3 y1 + 4y2 2 2y1 + 4y3 3 y1,y2,y3 0 32利潤(rùn) 12kg40材料B 16kg04材料A 8臺(tái)時(shí) 21設(shè)備臺(tái)時(shí) 限制 0, 124 16 4 82 32max 21 2 1 21 211 xx x x xx xxzM 52 一般的，原問題：max z = CX AX b X 0 對(duì)偶問題：min w = Yb YA C Y 0 比較： max z min w 決策變量為n個(gè) 約束條件為n個(gè) 約束條件為m個(gè) 決策變量為m個(gè) “” “” 53 3 3 對(duì)偶問題的化

33、法對(duì)偶問題的化法 1、典型情況 eg.2 max z = x1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0 對(duì)偶：min w = 6y1 + 8y2 2y1 1 y1 + 2y2 2 y2 1 y1,y2 0 54 2、含等式的情況 eg.3 max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0 對(duì)偶：min w = 3y1-3y1”+4y2 2y1-2y1”+ y2 1 y1- y1”+2y2 2 3y1-3y1”+5y2 4 y1,y1”,y2 0 令y1=y1

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

35、min w = 3y1 + 4y2 2y1 + y2 1 y1 + 2y2 2 3y1 + 5y2 4 y1 0,y2 0 -2x1 - x2 - 3x3 -3 56 一般: max問題第i個(gè)約束取“”，則min問題第i個(gè)變量 0 ； min問題第i個(gè)約束取“”，則max問題第i個(gè)變量 0 ； 原問題第i個(gè)約束取等式，對(duì)偶問題第i個(gè)變量 無約束； max問題第j個(gè)變量 0 ,則min問題第j個(gè)約束取 “” ； min問題第j個(gè)變量 0 ，則max問題第j個(gè)約束取 “” ； 原問題第j個(gè)變量無約束，對(duì)偶問題第j個(gè)約束取等式。 57 eg.5 min z = 2x1 + 3x2 - 5x3 + x

36、4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4無約束 對(duì)偶：max w = 5y1 + 4y2 + 6y3 y1 + y2 2 y1 + y3 3 -3y1 + 2y2 + y3 -5 y1 - y2 + y3 = 1 y1 0,y2 0,y3無約束 58 4 4 對(duì)偶問題的性質(zhì)對(duì)偶問題的性質(zhì) 1、對(duì)稱性 對(duì)偶問題的對(duì)偶為原問題. 0 )max( 0; ,min)max( Y CYA Ybw YCYACYA Ybww 即 0 )min( X bAX CXw 0 , ,min 0 , ,max YC

37、YAYbw XbAXCXz 59 0 )min( X bAX CXw 證畢 令 0 max maxmax)min( X bAX CXz wz CXwww 60 ., : 的可行解分別為原問題和對(duì)問題設(shè) 證明 YX XCXAYCAYCYA bYXAYbXAbAX 證畢 bYXC bYXAYXC bYXC YX , . 2 則存在為對(duì)偶問題的可行解為原問題的可行解設(shè) 弱對(duì)偶性 61 推論： (1) max問題任一可解的目標(biāo)值為min問題目標(biāo)值的一個(gè)下界； (2) min問題任一可解的目標(biāo)值為max問題目標(biāo)值的一個(gè)上界。 3、無界性 若原問題(對(duì)偶問題)為無界解，則對(duì)偶問題(原問題)為 無可行解。

38、注：該性質(zhì)的逆不存在。若原(對(duì)偶)問題為無可行解，對(duì)偶 (原問題)問題或?yàn)闊o界解，或?yàn)闊o可行解。 62 4、最優(yōu)性 設(shè)X*，Y*分別為原問題和對(duì)偶問題可行解，當(dāng) CX*=Y*b時(shí)， X*，Y*分別為最優(yōu)解。 證畢 為最優(yōu)解 即 為最優(yōu)解 即 由弱對(duì)偶性 題的任一可行解分別為原問題和對(duì)偶問設(shè) 證明 * )2( ) 1 ( ., : * * * Y bYbYbYCXbY X CXXCCXbYXC YX 63 5、對(duì)偶定理 若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解， 且目標(biāo)值相等。 *1 1 * 1* 1* 1* 11 * 0 )( :, , 0 . : wbYbBC bB CCCXz bBX bB

39、CbYwY BCYCAY CABCABCC X BNB B B BB 則其目標(biāo)值為因原問題最優(yōu)解 則為對(duì)偶問題的可行解若 其中 全部檢驗(yàn)數(shù)可表示為 則其對(duì)應(yīng)的基矩陣存在為原問題的最優(yōu)解設(shè) 證明 64 Y*為對(duì)偶問題的最優(yōu)解，且原問題和對(duì)偶問題 的目標(biāo)值相等。 證畢 6、松弛性 若X*，Y*分別為原問題及對(duì)偶問題的可行解， 那么Ys*X*=0，Y*Xs*=0，當(dāng)且僅當(dāng)X*，Y*分別為 最優(yōu)解。 證明： 0, 0max : S S S XX bXAX XCXz 設(shè)原問題為 0, 0min : S S S YY CYYA YYbw 設(shè)對(duì)偶問題為 65 0, 0max S S S XX bXAX XC

40、Xz 0, 0min S S S YY CYYA YYbw XYYAXXYYACXz SS )( SS YXYAXXAXYYbw)( 將b,Cb,C分別代入目標(biāo)函數(shù)： ;, ,0, 0, * * 為最優(yōu)解 時(shí)當(dāng)為可行解若 YX zwXYXYYX SS 證畢 必有 則分別為最優(yōu)解若另一方面 0 , 0 , * * SS XYXY zwYX 66 T SmSSS T n xxxX xxxX ) ( ) ( * 2 * 1 * * 2 * 1 * ) ( ) ( * 2 * 1 * * 2 * 1 * snSSS m yyyY yyyY 其中： 用分量表示： mixy njxy Sii jSj ,

41、2 , 1 , 0 ;, 2 , 1 , 0 * * 67 7、檢驗(yàn)數(shù)與解的關(guān)系 (1)原問題非最優(yōu)檢驗(yàn)數(shù)的負(fù)值為對(duì)偶問題的一個(gè)基解。 (2)原問題最優(yōu)檢驗(yàn)數(shù)的負(fù)值為對(duì)偶問題的最優(yōu)解。 分析：max z = CX + 0Xs = (C 0)(X Xs)T AX + Xs = b X,Xs 0 min w = Yb + YS0 YA - Ys = C Y,Ys 0 檢驗(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ù) 68 eg.6 已知：min w =

42、 20y1 + 20y2 的最優(yōu)解為y1*=1.2,y2*=0.2 -ys1 y1 + 2y2 1 試用松弛性求對(duì)偶 -ys2 2y1 + y2 2 問題的最優(yōu)解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0 解：對(duì)偶問題 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*

43、 = 0 69 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*待定 由 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*

44、= 28 = w* 70 5 5 對(duì)偶問題的經(jīng)濟(jì)含義對(duì)偶問題的經(jīng)濟(jì)含義影子價(jià)格影子價(jià)格 最優(yōu)情況：z* = w* = b1y1* + + biyi* + + bmym* 的影子價(jià)格為稱 i * i * ib z byy i * x2 x1 Q2 eg.7 max z = 2x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 0 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

45、13 z* = 0 = y3* Q2 Q2” 71 6 6 對(duì)偶單純形法對(duì)偶單純形法 單純形法：由 XB = B-1b 0，使j 0，j = 1,m 對(duì)偶單純形法：由j 0(j= 1,n)，使XB = B-1b 0 步驟：步驟：(1)保持j 0，j= 1,n，確定XB，建立計(jì)算 表格； (2)判別XB = B-1b 0是否成立？ 若成立，XB為最優(yōu)基變量； 若不成立，轉(zhuǎn)(3)； 72 (4)消元運(yùn)算，得到新的XB。 (3)基變換 出基變量， 出基；，則若 llii i xmibbb, 10min 入基變量， 入基。則若 k a lj a j xa lk k lj j 0min 重復(fù)（2）-（4

46、）步，求出結(jié)果。 73 eg.8 用對(duì)偶單純形法求解 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 - 3x3 + x5 = -4 x1,x2,x3,x4,x5 0 74 -2-3-400 CBXBbx1x2x3x4X5 0 x4-1 0 x5-4 出出出 x4,x5 0 最優(yōu) 最優(yōu)解：最優(yōu)解：x1* = 2，x2* = 0，x3* = 0，x4* =

47、1，x5* = 0 目標(biāo)值：目標(biāo)值：w* = -z* = 4 75 7 7 靈敏度分析靈敏度分析 njpBCc ABCC NBCC jBjj B BNN , 2 , 1, 0 0 0 : 1 1 1 或 或 最優(yōu)性條件 分析 變化對(duì)最優(yōu)解的影響。 j , iji acb 0 : 1 bBX B 可行性條件 76 的變化資源 i b 1 . 7 T i T mi iii b bbbbb bbb bbb )0b 0 0( ) ( 21 bBbBbbBbBX B 1111 )( . ., 0 11 這里用到可行性條件 保持問題的最優(yōu)性不變的變化范圍求出 由 i b bBbB 77 例1 已知下述問題

48、的最優(yōu)解及最優(yōu)單純形表, 0, 124 164 82 00032max 54321 52 41 321 54321 xxxxx xx xx xxx xxxxxz ., ) 1 2 使最優(yōu)基不變的變化范圍求 b . 4 )2 1 時(shí)的最優(yōu)解求b 78 最優(yōu)單純形表如下: 0-1/8-3/200 0-1/81/21023 11/2-20040 01/400142 00032 b B X B C 5 x 4 x 3 x 2 x 1 x 1 x 5 x 2 x 14 Z)4 0 0 2 4(, * T X此時(shí) 79 222 16 1) :bbb解 08/12/1 12/12 04/10 1 B 2 4

49、 4 12 16 8 08/12/1 12/12 04/10 1* bBX B 由最優(yōu)單純形表得: 80 )(0 1 2 bbBb 22 111 8/1 2/1 4/1 2 4 4 0 0 08/12/1 12/12 04/10 2 4 4 )( bb bBbBbbB 0 0 0 8/2 2/4 4/4 2 2 2 b b b 08/2 02/4 04/4 2 2 2 b b b . 168 2 最優(yōu)基不變 b 81 TT bb)0 0 4()0 0 ( )2 1 4 4 4 2 8 0 2 4 4 0 0 4 08/12/1 12/12 04/10 2 4 4 )( 111 bBbBbbB

50、不可行! 用對(duì)偶單純形法計(jì)算 82 -3/4-1/2000 1/400103 x2 3 -1/2-1/41002 x3 0 01/40014 x1 2 0-1/8-3/200 0-1/81/2102+23 11/2-2004-8 x5 0 01/40014+0 x1 2 ix5x4x3x2x1bXBCB 00032 x2 3/4 -2 )(17 : . 0, 0, 2, 3, 4 : * * 5 * 4 * 3 * 2 * 1 元目標(biāo)值 最優(yōu)解 z xxxxx 83 的變化價(jià)值系數(shù) j c 2 . 7 . .0 1 分兩種情況討論 進(jìn)行分析根據(jù)最優(yōu)性條件 NBCC BNN 的變化非基變量?jī)r(jià)值系

51、數(shù) k c. 1 kBkk pBCc 1 : 原檢驗(yàn)數(shù) / : kkkkk ccccc變化 kkkBkkk cpBCcc 1/ ., 0 : / 此時(shí)最優(yōu)解不變 令 kk kkk c c 84 例2 求例1 c4的變化范圍,使最優(yōu)解不變. 0-1/8-3/200 0-1/81/21023 11/2-2004 x5 0 01/40014 x1 2 ix5x4x3x2x1bXBCB 00032 x2 0 4 c 8/1)8/1(8/1 444 c由 解: . 8/1 4 時(shí)最優(yōu)解不變即c 85 的變化基變量?jī)r(jià)值系數(shù) r c. 2 NBCC BNN 1 原 BBB CCC 若 NBC NBCNBCC

52、 NBCCC BN BBN BBNN 1 11 1/ )( 則 分析: )0 0 0( ) ( : 21 rB mrB cC ccccC 其中 .變化影響所有可見 jr c 86 方法: . 0 1/ 的變化范圍求出 令 r BNN c NBC 例3 求例1 c2的變化范圍,使最優(yōu)解不變. 0-1/8-3/200 0-1/81/21023 11/2-2004 x5 0 01/40014 x1 2 ix5x4x3x2x1bXBCB 00032 x2 87 解: 0-1/8-3/200 0-1/81/21023 11/2-2004 x5 0 01/40014 x1 2 ix5x4x3x2x1bXB

53、CB 00032 x2 ) 0 0( ),3 0 2( 2 cCC BB 1/8)- (-3/2) ( 43 N ) ( / 4 / 3 / n 444 1 4 / 4 333 1 3 / 3 pcpBc pcpBc BB BB 88 0 22 3 2/1 2 0 )c 0 0( 2 3 2 2 33 / 3 c pcB 0 88 1 8/1 2/1 4/1 )c 0 0( 8 1 2 2 44 / 4 c pcB 1 3 2 2 c c . 13 2 時(shí)最優(yōu)解不變即c 89 的變化技術(shù)系數(shù) ji a 3 . 7 kBkk pBCc 1 原 T 1 k k k 0) a 0( ) ( , lk

54、k T mklkkk kkklll p aaap pppaaaa 若 分析: . k 的變化討論非基變量技術(shù)系數(shù) l a 90 lklk a kBkBk kkBkK pBCpBCc ppBCc 11 1 )( 則 T lkmlk kBk a pBC )00)( 1 1 0 lklkk a令 ., 最優(yōu)解不變時(shí)當(dāng) l k kl a 91 例4 求例1 a24的變化范圍,使最優(yōu)解不變. 解: 24242424 1, 1aaaa ) (0) 1/8 2/3( 3) 0 2( 321 11 BBCB 242424 4 8 1 8 1 aa 0 8 1 8 1 24 4 a令 . , 1 24 此時(shí)最優(yōu)

55、解不變a 92 例5 在例1的基礎(chǔ)上，企業(yè)要增加一個(gè) 新產(chǎn)品,每件產(chǎn)品需2個(gè)臺(tái)時(shí)，原材料A 6kg， 原材料B 3kg，利潤(rùn) 5元/件，問如何安排各產(chǎn) 品的產(chǎn)量，使利潤(rùn)最大？ 解： 0, 1234 1664 822 532max 321 32 31 321 321 xxx xx xx xxx xxxz 532利潤(rùn) 12340料B 16604料A 8221設(shè)備 b 則有為新產(chǎn)品生產(chǎn)的件數(shù)設(shè), 3 x 93 3 1 )2pB 計(jì)算 25. 0 2 5 . 1 3 6 2 08/12/1 12/12 04/10 3 1 pB 0 4 5 3 6 2 0 8 1 2 3 5 3 1 3 3 pBCc

56、B 3 ) 1計(jì)算 表明生產(chǎn)新品有利。 94 ., )3 3 3 1 加入原最優(yōu)表計(jì)算將pB 2 , 5 3 出基主元為入基 xx 5/40-1/8-3/200 1/40-1/81/21023 2 11/2-2004 x5 0 3/201/40014 x1 2 x5x4x3x2x1bXBCB 500032 x2 ix3 95 5/40-1/8-3/200 1/40-1/81/21023 2 11/2-2004 x5 0 3/201/40014 x1 2 x5x4x3x2x1bXBCB 500032 x2 8/3 4/2 8 ix3 2 0-5/8 -7/16-1/400 0-1/8 -3/16

57、3/4103/23 1 1/21/4-1002 0-3/4-1/83/2011 x1 2 x5x4x3x2x1bXBCB 500032 x2 ix3 x3 5 )(5 . 2 )(5 .16 . 2 , 2/3 , 1 * * 3 * 2 * 1 元增加元 z xxx 96 小結(jié) 0 max X bAX CXz 1、對(duì)偶問題及其化法 0 min Y CYA Ybw 原問題決策變量決定對(duì)偶問題約束條件關(guān)系 原問題約束條件決定對(duì)偶問題決策變量取值方向。 97 2、檢驗(yàn)數(shù)的計(jì)算方法 njpCc pBCc jBj jBjj , 2 , 1 , 1 或 NBCC BNN 1 ABCC B 1 或 階矩陣

58、 階矩陣 : , : 1 mmB mnnmA jj pBp 1 98 3、對(duì)偶問題的性質(zhì) 4、對(duì)偶單純形法 弱對(duì)偶性 無界性 最優(yōu)性 松弛性 檢驗(yàn)數(shù)與對(duì)偶問題的解 99 njpBCc jBjj , 2 , 1, 0 1 變化對(duì)最優(yōu)解的影響分析 ijji acb, 0 : 1 NBCC BNN 最優(yōu)性條件 0 1 ABCC B 0 : 1 bBX B 可行性條件 5、靈敏度分析 100 的變化技術(shù)系數(shù) ji a )3( 的變化基變量?jī)r(jià)值系數(shù) r c 2 的變化非基變量?jī)r(jià)值系數(shù) k c 1 的變化價(jià)值系數(shù) j c )2( 的變化資源 i b ) 1 ( 的變化分析非基變量技術(shù)系數(shù) 101 整數(shù)規(guī)劃

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

60、ax問題， zI* zl* 對(duì)于min問題， zI* zl* 數(shù)學(xué)模型： 取整數(shù) j j n j iijij n j jj x njx mibxa xcz , 10 , 1 max 1 1 104 2 2 分枝定界法分枝定界法 用單純形法，去掉整數(shù)約束 IP LP xl* 判別是否整數(shù)解 xI* = xl* Yes 去掉非整數(shù)域 No 多個(gè)LP 105 3 0-13 0-1規(guī)劃（規(guī)劃（x xi i = 0 0或或1 1的規(guī)劃）的規(guī)劃） eg.2 選擇投資場(chǎng)所 Ai投資Bi元，總投資B， 收益Ci元. 問：如何選擇Ai，使收益最大？ A6 A7 A4 A5 A3A2A1 最多選2個(gè) 最少選1個(gè)最