金融學院管理運籌學線性規(guī)劃與單純型法

管理運籌學線性規(guī)劃與單純型法第二講由實踐問題引出數學模形。產品A產品B資源限量勞動力設備原材料9434510360200300利潤元/KG701201.確定決策變量:設消費A,B分別為x1,x22.確定目的函數:3.確定約束條件:一、LP問題的根本概念12/31/20233典型的LP問題:一、LP問題的根本概念12/31/20234用向量符號表示為:用向量和矩陣表示為:一、LP問題的根本概念12/31/202351.基、基向量、基變量、非基變量設A為約束方程組的m×n階系數矩陣，其秩為m，B是A中的一個m階滿秩子矩陣，稱B為LP問題的一個基。B中每一個列向量稱為基向量，對于的變量xj為基變量，其他的變量稱為非基變量。一、LP問題的根本概念12/31/202361.基、基向量、基變量、非基變量一、LP問題的根本概念12/31/20237滿足約束方程(包括非負約束)的一切解，稱為可行解。對于某組選定的基，令非基變量為0，與約束方程求得的獨一解，稱為基解。2.可行解、基解、基可行解、可行基一、LP問題的根本概念12/31/20238基解中滿足一切變量非負約束的解，稱為基可行解。2.可行解、基解、基可行解、可行基與基可行解對應的基稱為可行基。一、LP問題的根本概念12/31/20239概念練習:找出以下LP問題的全部基解。1234512345一、LP問題的根本概念12/31/202310組合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045////55-120452175541010-5415////52.51.517.554-32224319

×

××××

一、LP問題的根本概念12/31/2023111.連線:二、重要定理與引理在n維Euclid空間中，點X與Y連線上的點，是指如下方式的點T:當α跑遍區(qū)間[0,1]時,相應的點T的集合就構成點X與Y之間的連線。12/31/2023122.凸集:一個由n維點所構成的集合K，假設對于K中恣意兩點X,Y∈K，恒有:那么n維點集K稱為凸集，即K中恣意兩點的連線上的點也在K中。3.凸組合:假定有k個n維Euclid空間的點它們的凸組合是指如下方式的點X:特別，兩個點X與Y的凸組合，叫做它們連線上的點。二、重要定理與引理12/31/2023134.頂點:設K是凸集，點X∈K；假設對K中任何兩個不同的點X,Y，以下等式恒不成立:就稱X為凸集K的頂點。換句話說，凸集的頂點，就是不在凸集中恣意兩點連線上的點。二、重要定理與引理12/31/202314定理1.假設LP問題的可行域非空,那么可行域為凸集定理2.LP問題的基可行解X對應LP問題可行域的頂點定理3.假設LP問題有最優(yōu)解，那么一定存在至少一個基可行解為最優(yōu)解二、重要定理與引理LP問題的規(guī)范型，見P2012/31/202315(1)列初始單純形表三、單純形法的計算步驟cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b110…aij…a1nc2x2b200…a2j…a2n...............cmxmbm01…amj…amnб=cj-zj00012/31/202316(2)從一個基可行解轉換為相鄰的另一個基可行解不失普通性，設初始基可行解中的前m個為基變量，設單位矩陣的列向量為Pi，增廣矩陣中單位矩陣以外的某個列向量為Pj，那么Pj可以成為Pi的線性表達：111a1j.amj三、單純形法的計算步驟12/31/202317兩式相加：三、單純形法的計算步驟對于一個正數：θ12/31/202318除了X(0)，還有其他解嗎？111a1j.amj只需：問題：X(1)是基可行解嗎？三、單純形法的計算步驟12/31/202319要使X(1)成為基可行解，必需滿足：且，至少一個等式成立！顯然，對于小于等于0的aij，上述不等式無條件成立；對于大于0的aij，那么令：三、單純形法的計算步驟12/31/202320111a1j.amj111以上的系數矩陣的初等行變換，成為換基變換；假設僅且變換一個基變量，稱對應的兩個基可行解為相鄰的基可行解。對應的頂點稱為相鄰的頂點，簡稱鄰點。三、單純形法的計算步驟12/31/202321將X(0),X(1)分別代入目的函數：(3)最優(yōu)性判別三、單純形法的計算步驟12/31/202322其中：稱為檢驗數，也可表達為：或：三、單純形法的計算步驟12/31/202323【例】用單純型法解以下LP問題：用矩陣方式表示為：四、運用舉例12/31/202324首先構造初始單純型表如下：cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001四、運用舉例12/31/202325cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001x1四、運用舉例12/31/202326cj21000CB基bx1x2x3x4x50x315051002x124620100x5511001cj-zj20001x1四、運用舉例12/31/202327cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3第一次迭代終了四、運用舉例12/31/202328cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3x2四、運用舉例12/31/202329cj21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj-1/2-1/4000四、運用舉例12/31/202330化為規(guī)范方式：五、單純型法的進一步討論—人工變量法(大M法)【例】用單純型法求解以下LP問題：12/31/202331構造初始單純型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、單純型法的進一步討論—人工變量法(大M法)12/31/202332第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1+4M五、單純型法的進一步討論—人工變量法(大M法)12/31/202333第2次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj-M-3/2-M+1/20003/23五、單純型法的進一步討論—人工變量法(大M法)12/31/202334第3次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-M+3/4-M+1/4-9/2-3/4000五、單純型法的進一步討論—人工變量法(大M法)12/31/202335同樣標題六、單純型法的進一步討論—兩階段法為了保證人工變量為0，可講目的函數設為：12/31/202336構造初始單純型表：cj00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-20004-11六、單純型法的進一步討論—兩階段法12/31/202337第1次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-1x7660403-31cj-zj6-400034六、單純型法的進一步討論—兩階段法12/31/202338第2次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj-1-100000即，當X(1)=(1,3,0,0,0,0,0)時，可使目的函數x6+x7獲得最小，當x6=x7=0時六、單純型法的進一步討論—兩階段法12/31/202339上述獲得最優(yōu)的單純型迭代中止的表，等價于一個約束方程組I：而約束方程組I又等價于約束方程組II：故，構造新的初始單純型表如下：六、單純型法的進一步討論—兩階段法12/31/202340cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj六、單純型法的進一步討論—兩階段法12/31/202341cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj第1次迭代：0003/23六、單純型法的進一步討論—兩階段法12/31/202342cj-30100CB基bx1x2x3x4x50x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj-zj第1次迭代：-9/2-3/4000六、單純型法的進一步討論—兩階段法12/31/202343七、單純型法解的討論補充定理1.假設LP問題有最優(yōu)解，那么基可行解中必有最優(yōu)解。補充定理2.假設X(1),X(2),...,X(K)皆為某LP問題的最優(yōu)解，那么它們的凸組合也是該LP問題的最優(yōu)解。補充定理3.假設LP問題的可行域有界，而它的基可行解中的一切最優(yōu)解為:X(1),X(2),...,X(K),那么它們的一切凸組合包括了該LP問題的所有