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

管理運籌學(xué)5/13/20251線性規(guī)劃與單純型法第二講5/13/20252由實際問題引出數(shù)學(xué)模形。產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè)備原材料9434510360200300利潤元/KG701201.確定決策變量:設(shè)生產(chǎn)A,B分別為x1,x22.確定目標(biāo)函數(shù):3.確定約束條件:一、LP問題的基本概念5/13/20253典型的LP問題:一、LP問題的基本概念5/13/20254用向量符號表示為:用向量和矩陣表示為:一、LP問題的基本概念5/13/202551.基、基向量、基變量、非基變量設(shè)A為約束方程組的m×n階系數(shù)矩陣，其秩為m，B是A中的一個m階滿秩子矩陣，稱B為LP問題的一個基。B中每一個列向量稱為基向量，對于的變量xj為基變量，其余的變量稱為非基變量。一、LP問題的基本概念5/13/202561.基、基向量、基變量、非基變量一、LP問題的基本概念5/13/20257滿足約束方程(包括非負(fù)約束)的所有解，稱為可行解。對于某組選定的基，令非基變量為0，與約束方程求得的唯一解，稱為基解。2.可行解、基解、基可行解、可行基一、LP問題的基本概念5/13/20258基解中滿足所有變量非負(fù)約束的解，稱為基可行解。2.可行解、基解、基可行解、可行基與基可行解對應(yīng)的基稱為可行基。一、LP問題的基本概念5/13/20259概念練習(xí):找出下列LP問題的全部基解。1234512345一、LP問題的基本概念5/13/202510組合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045////55-120452175541010-5415////52.51.517.554-32224319

×

××××

一、LP問題的基本概念5/13/2025111.連線:二、重要定理與引理在n維Euclid空間中，點X與Y連線上的點，是指如下形式的點T:當(dāng)α跑遍區(qū)間[0,1]時,相應(yīng)的點T的集合就構(gòu)成點X與Y之間的連線。

5/13/2025122.凸集:一個由n維點所構(gòu)成的集合K，如果對于K中任意兩點X,Y∈K，恒有:則n維點集K稱為凸集，即K中任意兩點的連線上的點也在K中。

3.凸組合:假定有k個n維Euclid空間的點它們的凸組合是指如下形式的點X:特別，兩個點X與Y的凸組合，叫做它們連線上的點。二、重要定理與引理5/13/2025134.頂點:設(shè)K是凸集，點X∈K；若對K中任何兩個不同的點X,Y，以下等式恒不成立:就稱X為凸集K的頂點。換句話說，凸集的頂點，就是不在凸集中任意兩點連線上的點。

二、重要定理與引理5/13/202514定理1.若LP問題的可行域非空,則可行域為凸集定理2.LP問題的基可行解X對應(yīng)LP問題可行域的頂點定理3.若LP問題有最優(yōu)解，則一定存在至少一個基可行解為最優(yōu)解二、重要定理與引理LP問題的標(biāo)準(zhǔn)型，見P205/13/202515(1)列初始單純形表三、單純形法的計算步驟cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b110…aij…a1nc2x2b200…a2j…a2n...............cmxmbm01…amj…amnб=cj-zj0005/13/202516(2)從一個基可行解轉(zhuǎn)換為相鄰的另一個基可行解不失一般性，設(shè)初始基可行解中的前m個為基變量，設(shè)單位矩陣的列向量為Pi，增廣矩陣中單位矩陣以外的某個列向量為Pj，則Pj可以成為Pi的線性表達：111a1j.amj三、單純形法的計算步驟5/13/202517兩式相加：三、單純形法的計算步驟對于一個正數(shù)：θ5/13/202518除了X(0)，還有其他解嗎？111a1j.amj只需：問題：X(1)是基可行解嗎？三、單純形法的計算步驟5/13/202519要使X(1)成為基可行解，必須滿足：且，至少一個等式成立！顯然，對于小于等于0的aij，上述不等式無條件成立；對于大于0的aij，則令：三、單純形法的計算步驟5/13/202520111a1j.amj111以上的系數(shù)矩陣的初等行變換，成為換基變換；如果僅且變換一個基變量，稱對應(yīng)的兩個基可行解為相鄰的基可行解。對應(yīng)的頂點稱為相鄰的頂點，簡稱鄰點。三、單純形法的計算步驟5/13/202521將X(0),X(1)分別代入目標(biāo)函數(shù)：(3)最優(yōu)性判斷三、單純形法的計算步驟5/13/202522其中：稱為檢驗數(shù)，也可表達為：或：三、單純形法的計算步驟5/13/202523【例】用單純型法解下列LP問題：用矩陣形式表示為：四、應(yīng)用舉例5/13/202524首先構(gòu)造初始單純型表如下：cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001四、應(yīng)用舉例5/13/202525cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001x1四、應(yīng)用舉例5/13/202526cj21000CB基bx1x2x3x4x50x315051002x124620100x5511001cj-zj20001x1四、應(yīng)用舉例5/13/202527cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3第一次迭代結(jié)束四、應(yīng)用舉例5/13/202528cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3x2四、應(yīng)用舉例5/13/202529cj21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj-1/2-1/4000四、應(yīng)用舉例5/13/202530化為標(biāo)準(zhǔn)形式：五、單純型法的進一步討論—人工變量法(大M法)【例】用單純型法求解下列LP問題：5/13/202531構(gòu)造初始單純型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、單純型法的進一步討論—人工變量法(大M法)5/13/202532第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1+4M五、單純型法的進一步討論—人工變量法(大M法)5/13/202533第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法)5/13/202534第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法)5/13/202535同樣題目六、單純型法的進一步討論—兩階段法為了保證人工變量為0，可講目標(biāo)函數(shù)設(shè)為：5/13/202536構(gòu)造初始單純型表：cj00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-20004-11六、單純型法的進一步討論—兩階段法5/13/202537第1次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-1x7660403-31cj-zj6-400034六、單純型法的進一步討論—兩階段法5/13/202538第2次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj-1-100000即，當(dāng)X(1)=(1,3,0,0,0,0,0)時，可使目標(biāo)函數(shù)x6+x7取得最小，當(dāng)x6=x7=0時六、單純型法的進一步討論—兩階段法5/13/202539上述取得最優(yōu)的單純型迭代中止的表，等價于一個約束方程組I：而約束方程組I又等價于約束方程組II：故，構(gòu)造新的初始單純型表如下：六、單純型法的進一步討論—兩階段法5/13/202540cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj六、單純型法的進一步討論—兩階段法5/13/202541cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj第1次迭代：0003/23六、單純型法的進一步討論—兩階段法5/13/202542cj-30100CB基bx1x2x3x4x50x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj-zj第1次迭代：-9/2-3/4000六、單純型法的進一步討論—兩階段法5/13/202543七、單純型法解的討論補充定理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問題的所有最優(yōu)解。(證明略)以下給出三個補充定理，可看作是求解線性規(guī)劃問題的基本依據(jù)。5/13/202544情況1:唯一最優(yōu)解只需非基變量的檢驗數(shù)全為負(fù)，且基變量中不含人工變量，該解即為唯一最優(yōu)解。情況2:無解1.當(dāng)非基變量的檢驗數(shù)全為負(fù)，且基變量中含有人工變量，則該LP問題無解。2.可行域為空集。七、單純型法解的討論5/13/202545情況3:解無界對于某個正檢驗數(shù)，其對應(yīng)的Pj有非正的分量，該LP問題的解無界。七、單純型法解的討論5/13/202546看以下例子:cj1100CB基bx1x2x3x40x34-21100x421-101cj-zj1100請同學(xué)們用圖解加以驗證，加深印象。七、單純型法解的討論5/13/202547情況4:多重最優(yōu)解--無窮最優(yōu)解存在非基變量的檢驗數(shù)為0，該LP問題存在多重最優(yōu)解。七、單純型法解的討論5/13/202548八、算法的有限步中止特別地，指迭代循環(huán)的中止。按最小比值θ來確定出基變量時，有時會出現(xiàn)多個相同的最小值--θ，從而有下一輪迭代中，基可行解會出現(xiàn)一個或多個基變量=0解，這種情況稱為解的退化。退化解的出現(xiàn)，是