清華 運(yùn)籌學(xué)ppt課件

1、1 1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型1.1 1.1 問題的提出問題的提出 eg.1 eg.1 消費(fèi)方案問題消費(fèi)方案問題 問：產(chǎn)品問：產(chǎn)品、各消費(fèi)多少件，各消費(fèi)多少件， 使利潤最大？使利潤最大？ 限制 設(shè)備臺時(shí)128臺時(shí) 材料A4016kg材料B0412kg23 分析： 設(shè)：產(chǎn)品生產(chǎn)x1件， 產(chǎn)品生產(chǎn)x2件。這里z為利潤函數(shù)， max z:表示求z的最大值。目標(biāo)函數(shù)： max z = 2x1 + 3x2約束條件： 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 1eg.2eg.2污水處置問題污水處置問題 環(huán)保要求河水含污低于環(huán)保要求河水含污低于22，河水可

2、本身凈化，河水可本身凈化20%20%。 問：化工廠問：化工廠1 1、2 2每天各處置多少污水，使總費(fèi)用最少？每天各處置多少污水，使總費(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萬m3500萬m32萬m31.4萬m3化工廠1化工廠21000元/萬m3800元/萬m32線性規(guī)劃的數(shù)學(xué)模型：線性規(guī)劃的數(shù)

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

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

5、= 4，x2 = 2 由此求得最優(yōu)解：x1* = 4 x2* = 2 最大值：max z = z* = 2x1 + 3x2 = 14(元)x2x1Q1Q2(4,2)Q3Q4*436討論： (1)獨(dú)一最優(yōu)解 max z = z*時(shí)，解獨(dú)一，如上例。 (2)無窮多最優(yōu)解 eg.4 對eg.1，假設(shè)目的函數(shù) z = 2x1 + 4x2，此時(shí)表示 目的函數(shù)的直線與表示 條件的直線平行， 最優(yōu)點(diǎn)在線段Q3Q2上。 即存在無窮多最優(yōu)解。x2x1Q1 Q2(4,2)Q3(2,3)Q4o43*7 (3)無界解 eg.5 max z = 2x1 + 3x2 4x1 16 x1，x2 0 那么x2 ，z 。 即存

6、在無界解。 在實(shí)踐問題中，能夠 是短少約束條件。o2241x2x8(4)無可行解 eg.6 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 無公共部分，無可行域。 即無可行解。 在實(shí)踐問題中，能夠是關(guān)系錯(cuò)。1124x1x291.3 1.3 線性規(guī)劃的規(guī)范型線性規(guī)劃的規(guī)范型 1 1、規(guī)范型、規(guī)范型 max z = c1x1 + c2x2 + + cnxn max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22

7、x2 + + a2nxn = b2 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bm am1x1 + am2x2 + + amnxn = bm x1 x1，x2x2，xn 0 xn 0 njxmibxaxczjinjjijnjjj, 10, 1 max11 ，簡記：10用向量表示 njxbxptsCXzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapcccCxxxX) ( :) ( ) ( ) (:21212121 的系數(shù)列向量其中11 用矩陣描畫為： max z = CX AX = b X 0 其中

8、: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 為系數(shù)矩陣 212222111211 mnmmnnaaaaaaaaaA122 2、規(guī)范型的化法、規(guī)范型的化法 (1)minmax min z = cx = -max(-z) (1)minmax min z = cx = -max(-z) max(-z) = -min z = -cx max(-z) = -min z = -cx 令令z = -z z = -z 那么那么max z = -cxmax z = -cx (2)不等式(，) 對于“情況：在“左邊加上一個(gè)松弛變量非負(fù)，變?yōu)榈仁剑?對于“情況：

9、在“左邊減去一個(gè)剩余變量非負(fù)，變?yōu)榈仁健?留意：松弛變量、剩余變量在目的函數(shù)中的價(jià)值系數(shù)為0。 (3)無約束變量 令xk = xk - xk，xk,xk 0，代入即可。 13eg.7eg.7將下述問題化為規(guī)范型將下述問題化為規(guī)范型 min z = -x1+2x2-3x3 min z = -x1+2x2-3x3 x1+ x2+ x3 7 x1+ x2+ x3 7 x1- x2+ x3 2 x1- x2+ x3 2 -3x1+ x2+2x3 = 5 -3x1+ x2+2x3 = 5 x1,x2 0 x1,x2 0，x3x3無約束無約束 解：令解：令x3 = x3x3 = x3-x3-x3，x3x3

10、,x3,x3 0 0； 式加上一個(gè)松弛變量式加上一個(gè)松弛變量x4x4；式減去一個(gè)剩余變量；式減去一個(gè)剩余變量x5x5； 令令z z = -z = -z max zmax z = x1- 2x2 + 3(x3 = x1- 2x2 + 3(x3 - x3 - x3) + 0 x4 + 0 x5) + 0 x4 + 0 x5 x1 + x2 + (x3 x1 + x2 + (x3 - x3 - x3) + x4 = 7) + x4 = 7 x1 - x2 + (x3 x1 - x2 + (x3 - x3 - x3) - x5 = 2) - x5 = 2 -3x1 + x2 + 2(x3 -3x1 +

11、 x2 + 2(x3 - x3 - x3) = 5) = 5 x1,x2,x3 x1,x2,x3,x3,x3,x4,x5 0 ,x4,x5 0 141.4 1.4 線性規(guī)劃解的概念線性規(guī)劃解的概念 設(shè)線性規(guī)劃為設(shè)線性規(guī)劃為 max z = CX max z = CX AX = b AX = b X 0 X 0 A A為為m m n n矩陣矩陣, n m, Rank A = m (A, n m, Rank A = m (A為行滿秩矩陣為行滿秩矩陣 1、可行解：滿足條件、的X； 2、最優(yōu)解：滿足條件的可行解； 3、基：取B為A中的m m子矩陣，Rank B = m，那么稱B為線性規(guī) 劃問題的一個(gè)基

12、。 取B = (p1,p2,pm) pj = (a1j,a2j,amj)T 那么稱x1,x2,xm為基變量，其它為非基變量。154 4、基解：取、基解：取B = (p1,p2,pm)B = (p1,p2,pm) a11,a1m x1 a1m+1,a1n xm+1 b1 a11,a1m x1 a1m+1,a1n xm+1 b1 + = + = am1,amm xm amm+1,amn xn bm am1,amm xm amm+1,amn xn bm 基基 基變量基變量 非基非基 非基變量非基變量 令令 xm+1 = = xn = 0 ( xm+1 = = xn = 0 (非基變量為非基變量為0)

13、0) 那么那么 BXB = b BXB = b )!( !mnmnCmn基解個(gè)數(shù)TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 個(gè)個(gè)基解：165、基可行解 滿足式要求的基解。 如右圖所示，各邊交點(diǎn)O,Q1,Q2,Q3,Q4均為基可行解；而其延伸線的交點(diǎn)Q5為基解，但不是基可行解。O(0,0)O(0,0)Q1(4,0)Q1(4,0)Q2(4,2)Q2(4,2)Q4(0,3)Q4(0,3)Q3(2,3)Q3(2,3)Q5(4,3)Q5(4,3)6、可行基 基可行解對應(yīng)的B為可行基?？尚薪饪尚薪饣尚薪饣尚薪夥强尚薪夥强尚薪饣饣?72

14、 2 線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義2.1 2.1 根本概念根本概念 1 1、凸集：設(shè)、凸集：設(shè)K K為為En(nEn(n維歐式空間維歐式空間) )的一點(diǎn)集，的一點(diǎn)集，X(1)KX(1)K，X(2)KX(2)K。假設(shè)假設(shè)X(1)+(1-)X(2)KX(1)+(1-)X(2)K，那么稱，那么稱K K為凸集。為凸集。0101 非凸集X(1X(1) )X(1X(1) )X(2X(2) )X(2X(2) )凸集X(1X(1) )X(2X(2) )X(2X(2) )X(1X(1) )18 2、頂點(diǎn)：XK，X(1)K，X(2)K (恣意兩點(diǎn))。假設(shè)X不能用X(1)+(1-)X(2)表示，那么

15、稱X為K的一個(gè)頂點(diǎn)。(01) 注：頂點(diǎn)所對應(yīng)的解是基可行解。 3、凸組合：設(shè)X(i)En，假設(shè)存在0i1，i = 1,2,k，使 ,那么稱X為X(i)(i=1,2,k)的凸組合。1k1iik1i) i (iXX2.2 2.2 根本定理根本定理 1 1、定理、定理1 1 假設(shè)線性規(guī)劃存在可行域，那么假設(shè)線性規(guī)劃存在可行域，那么: : 可行域可行域 D = X|AX = b,X 0 D = X|AX = b,X 0為凸集。為凸集。19 證明： 設(shè) X(1)=(x1(1),x2(1),xn(1)T D； X(2)=(x1(2),x2(2),xn(2)T D； (X(1) X(2) 有 AX(1) =

16、 b， AX(2) = b 令 X = X(1) + (1 - )X(2) (0 0 1 0 X 0， 即D為凸集 2、定理2 線性規(guī)劃的基可行解對應(yīng)于可行域的頂點(diǎn)。 3、定理3 假設(shè)線性規(guī)劃有解，那么一定存在基可行解為最優(yōu)解。203 3 單純形法單純形法 根本思緒：從可行域的一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)迭代求最優(yōu)解。根本思緒：從可行域的一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)迭代求最優(yōu)解。3.1 3.1 初始基可行解確實(shí)定初始基可行解確實(shí)定 1 1、松弛基松弛變量對應(yīng)的、松弛基松弛變量對應(yīng)的B B eg.8max z = x1 + 3x2 eg.8max z = x1 + 3x2 x1 + 2x2 3 x1 + 2x2

17、 3 2x1 + 3x2 4 2x1 + 3x2 4 x1,x2 0 x1,x2 0max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 0 化規(guī)范型 取x3、x4為基變量,令非基變量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA則系數(shù)矩陣21 2、察看法 eg.9max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,

18、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則解223、人工基 eg.10max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 0 分析： A = 1 3 2 2 1 1 找不到單位矩陣基 引入人工變量為初始基變量2個(gè)233.2 3.2 最優(yōu)性的檢驗(yàn)與解的判別最優(yōu)性的檢驗(yàn)與解的判別 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0,

19、 1 max 111對于代入目標(biāo)函數(shù)為非基變量可行為基變量設(shè) , 1, , 1, 1 njjijiinjinxabxnjxmix24那么njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )( )(miijinjjjjmiiinaczzcbcZ110 , , 其中25解的判別：1. 假設(shè) ，那么此時(shí)的基可行解為最優(yōu)解；2. 假設(shè)存在某個(gè)非基變量 的檢驗(yàn)數(shù) ，且 ，那么該線性規(guī)劃問題具有無界解或稱無最優(yōu)解；3. 假設(shè)一切 ，又，對于某個(gè)非基變量 有 ，那么該線性規(guī)劃問題具有無窮多最優(yōu)解。. .的檢驗(yàn)數(shù)為稱j

20、jxkx0knjj, 1, 0 0kp0j0kkx26 為主元出基行對應(yīng)的變量則若、出基變量 0minmin02lkllklikikiiiiikikiiaxlabaabaab為入基變量。則，若、入基變量kkjjx 0max13.3 3.3 基變換基變換273.4 3.4 旋轉(zhuǎn)運(yùn)算消元運(yùn)算旋轉(zhuǎn)運(yùn)算消元運(yùn)算 a1k a1k 0 0 al-1k al-1k 0 0 pk pk = = alkalk 1 1 al+1k al+1k 0 0 amk amk 0 0 得到基可行解，反復(fù)得到基可行解，反復(fù)3.23.43.23.4， 求出最優(yōu)解。求出最優(yōu)解。283.5 3.5 單純形表單純形表 展開如下：展開

21、如下： a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a11x1 + a12x2 + + a1nxn + xn+1 = b1 - cn+1 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 a21x1 + a22x2 + + a2nxn + xn+2 = b2 - cn+2 am1x1 + am2x2 + + amnxn + xn+m = bm - cn+m am1x1 + am2x2 + + amnxn + xn+m = bm - cn+m c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn

22、+mxn+m - z = 0 c1x1 + c2x2 + + cnxn + cn+1xn+1 + + cn+mxn+m - z = 0 1x1 + 1x1 + 2x2 + + 2x2 + + nxn + 0 xn+1 + + 0 xn+m - z = Z0 nxn + 0 xn+1 + + 0 xn+m - z = Z0mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，設(shè)29 建立單純形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j eg.11用單

23、純形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 030 解：規(guī)范化，建立單純形表 引入松弛變量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 13000cBxBbx1x2x3x4x5 0 x38121000 x416400100 x51204001此時(shí)的解：x(0) = (0 0 8 16 12)Tz(0) = 031 解的

24、判別 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/41300032此時(shí)的解：x(1)=(0 3 2 16 0)Tz(1)=9x(1)非最優(yōu)x1入基 x3出基0 x321010-1/22/10 x4164001016/43x2301001/4-1000-3/41x121010-1/2

25、0 x4800-4123x2301001/400-10-1/413000此時(shí)的解：x(2)=(2 3 0 8 0)Tz(2)=11x(2)為最優(yōu)解 即： 最優(yōu)解：x* = (2 3 0 8 0)T 最大值：z* = 1133X(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)344 4 單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論4.1 4.1 人工變量法人工變量法 1 1、大、大M M法法M M為很大的正數(shù)為很大的正數(shù) 法那么：對于法那么：對于maxmax問題，人工變量在目的函數(shù)中的價(jià)值系數(shù)為問題，人工變量在目的函數(shù)中的價(jià)值系數(shù)為