單純形法基本原理及實例演示

1、整理課件1單純形法求解動態(tài)演示v在求解LP問題時,有人給出了圖解法,但對多維變量時,卻無能為力,于是v美國數(shù)學(xué)家GBDantgig(丹捷格)發(fā)明了一種“單純形法”的代數(shù)算法，尤其是方便于計算機(jī)運算。這是運籌學(xué)史上最輝煌的階段。整理課件2);,(21ncccCTnxxx),(21X一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念整理課件3基矩陣基矩陣 示例:012233. .23max32143214321xxxxxxxtsxxxxz000032020001010 x1 x2x4x3001300321=目標(biāo)函數(shù)約束條件行列式0基矩陣X1,x2,x3為基變量為基變量,x4為非基變量為非

2、基變量整理課件4 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1b 整理課件5 為了矩陣形求逆計算方便，一般將B轉(zhuǎn)化為單位矩陣。整理課件6將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。找出或構(gòu)造一個找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。階單位矩陣作為初始可行基，建立初始單純形表。計算各非基變量計算各非基變量xj的檢驗數(shù)的檢驗數(shù) j=Cj-CBPj ，若所有，若所有 j0，則問題已得到，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。在大于在大于0的檢驗數(shù)中，若某個的檢驗數(shù)中，若某個 k所對應(yīng)的系數(shù)列向

3、量所對應(yīng)的系數(shù)列向量Pk0，則此問題，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步。是無界解，停止計算，否則轉(zhuǎn)入下步。根據(jù)根據(jù)max j j0= k原則，確定原則，確定xk為換入變量為換入變量(進(jìn)基變量進(jìn)基變量)，再按，再按 規(guī)則計算：規(guī)則計算： =minbi/aik| aik0=bl/ aik 確定確定xBl為換出變量。建立新的為換出變量。建立新的單純形表，此時基變量中單純形表，此時基變量中xk取代了取代了xBl的位置。的位置。以以aik為主元素進(jìn)行迭代，把為主元素進(jìn)行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄浚此鶎?yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)樽優(yōu)?，同列中其它元素為，同列中其它元素為

4、0，轉(zhuǎn)第，轉(zhuǎn)第 步。步。 2、單純形法的計算步驟、單純形法的計算步驟 整理課件7線性規(guī)劃的例子子0,40025005 . 2516002234max211212121xxxxxxxxxz整理課件8線性規(guī)劃-標(biāo)準(zhǔn)化v引入變量：s1,s2,s3121231211222312123max501000003002400250,0zxxsssxxsxxsxsx x s s s整理課件925040030032121100100101200111sssxx3020102100150maxsssxxz提取系數(shù)，填入表格：s.t.3212100010050maxsssxxzC向量CBCNXBXN基BN jjjz

5、c Zj=CBNj每個非基變量的檢驗值整理課件10初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1biijbajjjzc 整理課件11初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1biijbajjjzc 目標(biāo)函數(shù)系數(shù)區(qū)目標(biāo)函數(shù)系數(shù)區(qū)約束條件系數(shù)區(qū)右端系數(shù)右端系數(shù)檢驗系數(shù)區(qū)檢驗系數(shù)區(qū)基變量區(qū)基變量區(qū)整理課件12初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001Zj=CBNjZ=CBB-1b2iiabjjjzc 整理課件13初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000

6、111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 整理課件14初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 整理課件15初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 整理課件16初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300

7、S2021010400S3001001250Zj=CBNjZ=02iiabjjjzc 整理課件17初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=02iiabjjjzc 00000整理課件18初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=01000002iiabjjjzc 50整理課件19初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501

8、000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=0501000002iiabjjjzc 125014001300整理課件20初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b2iiabjjjzc 125014001300整理課件21初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiab

9、jjjzc 125014001300整理課件22初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 125014001300整理課件23初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 125014001300整理課件24初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1

10、01010-150S202001-1150 x210001001250Zj=CBNjZ=250002iiabjjjzc 整理課件25初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=250002iiabjjjzc 整理課件26初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 整理

11、課件27初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 整理課件28初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 2150150整理課件29初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000003S101

12、010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc x150 x150整理課件30初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 整理課件31初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 整理課件32初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNjZ=275002iiabjjjzc 整理課件33初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=275002iiabjjjzc 整理課件34初始單純形