單純型法精品課件

1、單純型法第1頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二非基變量 基變量=1、線性規(guī)劃的矩陣表示第2頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=BNIIB-1b非基變量基變量=CBB-1B-CB=0第3頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=Z+( CBB-1N-CN) XN= CBB-1b XB+B-1N XN=B-1b Z+（CBB-1A-C）X= CBB-1b B-1AX= B-1b X右端ZCBB-1A-CCBB-1bXBB-1AB-1b第4頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二基變量在目標(biāo)函數(shù)中的系數(shù)等于0，基變量在約束條

2、件中的系數(shù)是一個(gè)單位矩陣約束條件的右端B非負(fù)2、單純形表的結(jié)構(gòu)和性質(zhì)第5頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二注意：Z行中有m 個(gè)0，它們與基變量相對(duì)應(yīng)。一般情況下，這m個(gè)0分散在Z行的各列中，并與基變量相對(duì)應(yīng)。其余m行中有一個(gè)m階單位矩陣I，其各列與基變量相對(duì)應(yīng)。一般情況下，組成I的各列分散在表的各列中，它們與基變量相對(duì)應(yīng)。單純形表的結(jié)構(gòu)第6頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二我們將用單純形表解決以下三個(gè)問題：如何找出第一個(gè)（初始的）基可行解？如何判斷這個(gè)初始基可行解是不是最優(yōu)解？如果不是，怎樣將它調(diào)整成一個(gè)“更好的”基可行解，以致最終求出最優(yōu)解？3、單

3、純形表的運(yùn)算第7頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二當(dāng)線性規(guī)劃問題的約束條件全為“小于等于約束”，并且右邊常數(shù)全部“大于等于0”，化標(biāo)準(zhǔn)問題時(shí)在每個(gè)約束中添加的松弛變量恰構(gòu)成一個(gè)單位矩陣，這單位矩陣可作為初始可行基。添加的松弛變量即為基變量，其他變量為非基變量。對(duì)于不能直接獲得初始可行基的問題，可以用引入人工變量的方法構(gòu)造一初始可行基。這將在“人工變量法”中作介紹。（1）初始基可行解的確定第8頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二用檢驗(yàn)數(shù)j=Zj Cj 進(jìn)行判斷，若所有檢驗(yàn)數(shù)j0，則X是最優(yōu)解。若存在某個(gè)檢驗(yàn)數(shù)j 0,它所對(duì)應(yīng)的列向量全部分量為非正，則所給

4、問題的目標(biāo)函數(shù)值無下界，因而無最優(yōu)解。若存在j 0,且它（們）所對(duì)應(yīng)的列向量中都有正分量，則這時(shí)可進(jìn)行基變換。 （2）基可行解的判別和改進(jìn)第9頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二若存在j 0,且它（們）所對(duì)應(yīng)的列向量中都有正分量，則這時(shí)可進(jìn)行基變換。取max=1.。j 所對(duì)應(yīng)的非基變量為進(jìn)基變量。將“右端”列中各數(shù)分別和“進(jìn)基變量列”的各數(shù)作比式（只對(duì)進(jìn)基變量列中的正數(shù)作比式），并以記這些比式中最小一個(gè)。獲得行所對(duì)應(yīng)的基變量即為離基變量。進(jìn)基變量列和離基變量行相交處的元素成為“主元”，在其上加以圓圈。進(jìn)行單純形變換，即令主元為1，主元所在列的其他元素為0。即得一新的單純形表

5、，繼續(xù)進(jìn)行判斷。（3）基可行解的基變換第10頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=目標(biāo)函數(shù)約束條件基矩陣右邊常數(shù) 進(jìn)基變量、離基變量、基變換=基變量第11頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=進(jìn)基變量離基變量目標(biāo)函數(shù)約束條件右邊常數(shù)=第12頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=目標(biāo)函數(shù)約束條件新的基矩陣右邊常數(shù)=第13頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=進(jìn)基變量離基變量目標(biāo)函數(shù)約束條件基矩陣=第14頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二=目標(biāo)函數(shù)約束條件新的基矩陣右邊常數(shù)=第15頁(yè)，共35頁(yè)，2

6、022年，5月20日，3點(diǎn)17分，星期二 單純形表法的運(yùn)算步驟單純形表的運(yùn)算Step 0 獲得一個(gè)初始的單純形表，確定基變量和非基變量Step 1 檢查基變量在目標(biāo)函數(shù)中的系數(shù)是否等于0，在約束條件中的系數(shù)是否是一個(gè)單位矩陣Step 2 如果表中非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，則已得到最優(yōu)解。停止。否則選擇系數(shù)為正數(shù)且絕對(duì)值最大的變量進(jìn)基。Step 3 如果進(jìn)基變量在約束條件中的系數(shù)全為負(fù)數(shù)或0，可行域開放，目標(biāo)函數(shù)無界。停止。否則選取右邊常數(shù)和正的系數(shù)的最小比值，對(duì)應(yīng)的基變量離基。Step 4 確定進(jìn)基變量的列和離基變量的行交叉的元素為“主元”，對(duì)單純形表進(jìn)行行變換，使主元變?yōu)?，主元所

7、在列的其他元素變?yōu)?。將離基的基變量的位置用進(jìn)基的非基變量代替。轉(zhuǎn)Step 1。第16頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二 設(shè)X1表示I型餅干日產(chǎn)量，X2表示II型餅干日產(chǎn)量（單位為噸），z表示I型和II型餅干所創(chuàng)造的日總利潤(rùn)目標(biāo)： max z = 5X1 +4X2約束條件： 3X1 +5X2 15 （攪拌機(jī)的限制） 2X1 + X2 5 （成形機(jī)的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0 例題：餅干生產(chǎn)問題第17頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二 轉(zhuǎn)化為標(biāo)準(zhǔn)模型 設(shè)z= - z, 引入松弛變量X3 , X4 , X5 0

8、 目標(biāo)： min z = -5X1 -4X2約束條件： 3X1 +5X2 + X3 = 15 （攪拌機(jī)的限制） 2X1 + X2 + X4 = 5 （成形機(jī)的限制） 2X1 +2X2 + X5 = 11 （烘箱的限制） X1, X2, X3 , X4 , X5 0 第18頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二寫出初始單純形表15/35/2x4離基x1進(jìn)基x1x2X3X4X5右端Z540000 x33510015x4210105X5220011111/2x1x2X3X4X5右端Z540000 x33510015x4210105X52200111x101/205/21/210-5

9、/20-25/23/201-3/2015/27/200-1161015/75 6x2進(jìn)基x3離基第19頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二得到最優(yōu)解，最優(yōu)解為：（x1，x2，x3，x4，x5）=（10/7，15/7，0，0，0，27/7）min z=-110/7，max z=110/7x1x2X3X4X5RHSZ03/20-5/20-25/2x307/21-3/2015/2X111/201/205/2X5010-116x22/7-3/7015/710-3/7-13/70-110/700-1/75/7010/701-2/7-4/7127/700第20頁(yè)，共35頁(yè)，2022年，

10、5月20日，3點(diǎn)17分，星期二產(chǎn)品A產(chǎn)品B產(chǎn)品C利潤(rùn)（萬(wàn)元/噸） 941耗用原料（噸/噸） 425排放污染（m3/噸） 213銷售價(jià)格（萬(wàn)元/噸） 301020總產(chǎn)量（噸） 111某工廠生產(chǎn)A、B、C三種產(chǎn)品，目標(biāo)是這三種產(chǎn)品的總利潤(rùn)最大化。和利潤(rùn)有關(guān)的因素有原材料的消耗、排放的污染，產(chǎn)品的銷售總額和三種產(chǎn)品的產(chǎn)量。有關(guān)數(shù)據(jù)如下表所示。設(shè)生產(chǎn)的產(chǎn)品全部銷售，要求安排使總利潤(rùn)最大的生產(chǎn)計(jì)劃，使得耗用原料不超過38噸，排放污染不超過25立方米，銷售總額不低于100萬(wàn)元，三種產(chǎn)品的總產(chǎn)量不低于12噸。這是一個(gè)利潤(rùn)目標(biāo)最大化的單目標(biāo)線性規(guī)劃問題。兩階段法舉例第21頁(yè)，共35頁(yè)，2022年，5月20日，

11、3點(diǎn)17分，星期二人工變量法如果約束條件全為“”，且右邊常數(shù)全為非負(fù)，則引進(jìn)的松弛變量就可以作為初始的基變量，得到一個(gè)初始的基礎(chǔ)可行解。如果約束條件有“=” ，右邊常數(shù)全為非負(fù)，則需要加上非負(fù)人工變量，建立輔助問題。如果約束條件有“”，右邊常數(shù)全為非負(fù)，則需要減去非負(fù)人工變量，建立輔助問題。4、人工變量法第22頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二人工變量法舉例思路人為構(gòu)造一個(gè)單位矩陣人工變量人工變量第23頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二大M法的步驟引進(jìn)松弛變量，使約束條件全為等式。引進(jìn)人工變量，令人工變量在目標(biāo)函數(shù)中的系數(shù)為大M （任意大的正數(shù)）用單

12、純形法求解，得到原問題的最優(yōu)解。若基變量中有非零的人工變量，則該LP無可行解。(1)大M法的步驟第24頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二求解以下LP問題(大M法)第25頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二化為標(biāo)準(zhǔn)型后加入人工變量，得到輔助問題Minz=x1+3x2s.t. 2x1+x2 =4 3x1+4x2-x3 =6 x1+3x2+x4 =3 x1,x2,x3,x4 0+mr1+mr2,r1,r2+r2+r1第26頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二X1X2X3r1r2X4rhs比Z-1-30-m-m00r12101004r234

13、-10106X41300013X1 X2X3r1r2X4rhs比Z5m-15m-3-m00010mr121010044/2r234-101066/3X413000133/1第27頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二X1X2X3r1r2X4rhs比Z00-1-1-m1-m02X1101/5 2-1/502X201-2/5-3/52/500X40011-111X1X2X3r1r2X4rhs比Z05/2m-5/2-m1/2-5/2m002X111/201/20024r205/2-1-3/21000X4000-1/20112/5最優(yōu)解x1=2, x2=0, x4=1,r1=r2=x

14、3=0, minz=2第28頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二練習(xí)：用大m法求解下列線性規(guī)劃問題第29頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二引進(jìn)松弛變量，使約束條件全為等式。引進(jìn)人工變量，建立輔助問題。輔助問題的目標(biāo)函數(shù)為各人工變量之和（僅含人工變量）。用人工變量作為輔助問題的初始基變量，用單純形法求解輔助問題，得到輔助問題的最優(yōu)解和最優(yōu)解的目標(biāo)函數(shù)值。如果輔助問題最優(yōu)解的目標(biāo)函數(shù)值大于0，原問題可行域?yàn)榭占瑹o可行解。如果輔助問題最優(yōu)解的目標(biāo)函數(shù)值等于0，輔助問題的最優(yōu)解是原問題的初始基礎(chǔ)可行解。將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換

15、原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表，用單純形法求解，得到原問題的最優(yōu)解。(2)兩階段法的步驟第30頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二求解以下LP問題(兩階段法)第31頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二minZ=X1+3X2s.t. 2x1+ x2 =4 3x1+4x2-x3 =6 x1+3x2+ x4 =3 x1,x2,x3,x40化成標(biāo)準(zhǔn)型第一階段：作輔助問題minf=r1+r2s.t. 2x1+x2+r1 =4 3x1+4x2-x3+r2 =6 x1+3x2+ x4 =3 x1,x2,x3,x4,r1,r20第32頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二X1X2X3r1r2x4右端比f(wàn)000-1-100r12101004r234-10106x41300013X1X2X3r1r2x4右端比f(wàn)55-100010r121010044/2r234-101066/3x413000133/1第33頁(yè)，共35頁(yè)，2022年，5月20日，3點(diǎn)17分，星期二X1X2X3r1r2x4右端比f(wàn)05/2-1-5/2000X111/201/20024r205/2-1-3/21000 x405/20-1/20112/5X1X2X3