金融學(xué)院管理運(yùn)籌學(xué)線(xiàn)性規(guī)劃與單純型法

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

×

××××

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