《單純形法基本原理及實例演示【教師助手】》由會員分享，可在線閱讀，更多相關《單純形法基本原理及實例演示【教師助手】（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、堂 XT =(XB,XN)T=（B-1b,0)T Z=CB B-1b 4學校課堂 為了矩陣形求逆計算方便，一般將B轉(zhuǎn)化為單位矩陣。5學校課堂將線性規(guī)劃問題化成標準型。將線性規(guī)劃問題化成標準型。找出或構造一個找出或構造一個m階單位矩陣作為初始可行基，建立初始單純形表。階單位矩陣作為初始可行基，建立初始單純形表。計算各非基變量計算各非基變量xj的檢驗數(shù)的檢驗數(shù) j=Cj-CBPj，若所有，若所有 j0，則問題已得到，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。在大于在大于0的檢驗數(shù)中，若某個的檢驗數(shù)中，若某個 k所對應的系數(shù)列向量所對應的系數(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ōu)閱挝涣邢蛄?，即所對應的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)樽優(yōu)?，同列中其它元素為，同列中其它元素為0，轉(zhuǎn)第，轉(zhuǎn)第 步。步。2、單純形法的計算步驟

4、、單純形法的計算步驟 6學校課堂線性規(guī)劃的例子子0,40025005.2516002234max211212121xxxxxxxxxz7學校課堂線性規(guī)劃-標準化v引入變量：s1,s2,s3121231211222312123max501000003002400250,0zxxsssxxsxxsxsx x s s s8學校課堂25040030032121100100101200111sssxx3020102100150maxsssxxz提取系數(shù)，填入表格：s.t.3212100010050maxsssxxzC向量CBCNXBXN基BN jjjzc Zj=CBNj每個非基變量的檢驗值9學校課堂初始

5、單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1biijbajjjzc 10學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1biijbajjjzc 目標函數(shù)系數(shù)區(qū)目標函數(shù)系數(shù)區(qū)約束條件系數(shù)區(qū)右端系數(shù)右端系數(shù)檢驗系數(shù)區(qū)檢驗系數(shù)區(qū)基變量區(qū)基變量區(qū)11學校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001Zj=CBNjZ=CBB-1b2iiabjjjzc 12學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000111003002101040001001250Zj=

6、CBNjZ=CBB-1b2iiabjjjzc 13學校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 14學校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 15學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CB

7、NjZ=02iiabjjjzc 16學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=02iiabjjjzc 0000017學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=01000002iiabjjjzc 5018學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S202101040

8、0S3001001250Zj=CBNj00000Z=0501000002iiabjjjzc 12501400130019學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130020學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130021學校課堂初始單

9、純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130022學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130023學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x2100

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

11、S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 27學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 215015028學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000003S101010-150S202001-1150 x210001

12、001250Zj=CBNj2iiabjjjzc x150 x15029學校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 30學校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 31學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150

13、x210001001250Zj=CBNjZ=275002iiabjjjzc 32學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=275002iiabjjjzc 33學校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=2750000-500-502iiabjjjzc 34學校課堂v表格中，檢驗系數(shù)j全部小于或等于0，根據(jù)判斷規(guī)則，Z值為最優(yōu)值（Z=27500），其解：vX1=50,S1=50,X2=250,s2=s3=0為模型的最優(yōu)解。35學校課堂