單純形法基本原理及實例演示（課堂PPT）

1、1單純形法求解動態(tài)演示v在求解LP問題時,有人給出了圖解法,但對多維變量時,卻無能為力,于是v美國數(shù)學(xué)家GBDantgig(丹捷格)發(fā)明了一種“單純形法”的代數(shù)算法，尤其是方便于計算機運算。這是運籌學(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為非基變量為非基變量4 XT = (X

2、B , 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ù)列向量所對應(yīng)的系數(shù)列向量Pk0，則此問題，則此問題是

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

4、、單純形法的計算步驟 7線性規(guī)劃的例子子0,40025005 . 2516002234max211212121xxxxxxxxxz8線性規(guī)劃-標(biāo)準(zhǔn)化v引入變量：s1,s2,s3121231211222312123max501000003002400250,0zxxsssxxsxxsxsx x s s s925040030032121100100101200111sssxx3020102100150maxsssxxz提取系數(shù)，填入表格：s.t.3212100010050maxsssxxzC向量CBCNXBXN基BN jjjzc Zj=CBNj每個非基變量的檢驗值10初始單純形表迭代次數(shù)基變量CB

5、x1X2s1s2S3b比值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比值501000000111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 14

6、初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 15初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 16初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=02iiabjjjzc 17初始單純形表迭代次數(shù)基變量CBx1X2

7、s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=02iiabjjjzc 0000018初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=01000002iiabjjjzc 5019初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=0501000002iiabjjjzc 125

8、01400130020初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130021初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130022初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x21

9、0001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130023初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130024初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNjZ=250002iiabjjjzc 25初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值50100

10、0002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=250002iiabjjjzc 26初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 27初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1

11、002iiabjjjzc 28初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 215015029初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000003S101010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc x150 x15030初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202

12、001-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初始單純形表迭代