《單純形法基本原理及實例演示【教師助手】》由會員分享，可在線閱讀，更多相關(guān)《單純形法基本原理及實例演示【教師助手】（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單純形法求解動態(tài)演示v在求解LP問題時,有人給出了圖解法,但對多維變量時,卻無能為力,于是v美國數(shù)學(xué)家GBDantgig(丹捷格)發(fā)明了一種“單純形法”的代數(shù)算法，尤其是方便于計算機運算。這是運籌學(xué)史上最輝煌的階段。1學(xué)校課堂);,(21ncccCTnxxx),(21X一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念2學(xué)校課堂基矩陣基矩陣 示例:012233.23max32143214321xxxxxxxtsxxxxz000032020001010 x1 x2x4x3001300321=目標(biāo)函數(shù)約束條件行列式0基矩陣X1,x2,x3為基變量為基變量,x4為非基變量為非基變量3學(xué)校課
2、堂 XT =(XB,XN)T=（B-1b,0)T Z=CB B-1b 4學(xué)校課堂 為了矩陣形求逆計算方便，一般將B轉(zhuǎn)化為單位矩陣。5學(xué)校課堂將線性規(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)閱挝涣邢蛄浚碼ik變?yōu)樽優(yōu)?，同列中其它元素為，同列中其它元素為0，轉(zhuǎn)第，轉(zhuǎn)第 步。步。2、單純形法的計算步驟
4、、單純形法的計算步驟 6學(xué)校課堂線性規(guī)劃的例子子0,40025005.2516002234max211212121xxxxxxxxxz7學(xué)校課堂線性規(guī)劃-標(biāo)準(zhǔn)化v引入變量：s1,s2,s3121231211222312123max501000003002400250,0zxxsssxxsxxsxsx x s s s8學(xué)校課堂25040030032121100100101200111sssxx3020102100150maxsssxxz提取系數(shù)，填入表格：s.t.3212100010050maxsssxxzC向量CBCNXBXN基BN jjjzc Zj=CBNj每個非基變量的檢驗值9學(xué)校課堂初始
5、單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1biijbajjjzc 10學(xué)校課堂初始單純形表迭代次數(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ū)11學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001Zj=CBNjZ=CBB-1b2iiabjjjzc 12學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000111003002101040001001250Zj=
6、CBNjZ=CBB-1b2iiabjjjzc 13學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 14學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 15學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CB
7、NjZ=02iiabjjjzc 16學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=02iiabjjjzc 0000017學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=01000002iiabjjjzc 5018學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000001S1011100300S202101040
8、0S3001001250Zj=CBNj00000Z=0501000002iiabjjjzc 12501400130019學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130020學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130021學(xué)校課堂初始單
9、純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130022學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12501400130023學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x2100
10、01001250Zj=CBNjZ=250002iiabjjjzc 24學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=250002iiabjjjzc 25學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 26學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2
11、S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 27學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 215015028學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2 S3b比值501000003S101010-150S202001-1150 x210001
12、001250Zj=CBNj2iiabjjjzc x150 x15029學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 30學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 31學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150
13、x210001001250Zj=CBNjZ=275002iiabjjjzc 32學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=275002iiabjjjzc 33學(xué)校課堂初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=2750000-500-502iiabjjjzc 34學(xué)校課堂v表格中，檢驗系數(shù)j全部小于或等于0，根據(jù)判斷規(guī)則，Z值為最優(yōu)值（Z=27500），其解：vX1=50,S1=50,X2=250,s2=s3=0為模型的最優(yōu)解。35學(xué)校課堂
單純形法基本原理及實例演示【教師助手】
