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

單純形法基本原理及實例演示第1頁，共34頁，2023年，2月20日，星期一線性規(guī)劃問題標準型的矩陣形式：

MaxZ=CX（a）

s.t.AX=b（b）

X0（c）

a11a12….a1nb1A=a21a22….a2nb

=b2………am1am2….amnbm一、關(guān)于標準型解的若干基本概念第2頁，共34頁，2023年，2月20日，星期一基矩陣

示例:000032020001010x1x2x4x3001300321=目標函數(shù)約束條件行列式≠0基矩陣X1,x2,x3為基變量,x4為非基變量第3頁，共34頁，2023年，2月20日，星期一因為B為基,故有XB+B-1NXN=B-1b，解得可行解XB=B-1b-B-1NXN，代入目標函數(shù)Z，Z=

CBB-1b+(CN-

CBB-1N)

XN

令非基變量XN=0，則有XT=(XB,XN)T=（B-1b,0)T

Z=

CBB-1bAX=bZ=CX設(shè)A=（B,N）（B為一個基，即線性無關(guān)向量組R(A)=R(B)）

XT=(XB,XN)T（XB為基變量，XN為非基變量）C=(CB,CN)（CB為基變量系數(shù)，CN為非基變量系數(shù)）則有：Z=

(CB,CN)(XB,XN)T=CBXB+CNXNAX=（B,N）(XB,XN)T=B

XB+N

XN=b1、單純形法原理：第4頁，共34頁，2023年，2月20日，星期一Z=

CBB-1b+(CN-

CBB-1N)

XN如果CN-

CBB-1N小于0，無論XN取任何大于0值，只會讓Z變小，因此我們可以通過CN-

CBB-1N來判斷Z取得是不是最大值。如果存在一個CN-

CBB-1N大于0，則說明Z的值會隨著XN增大而增大，說明Z有調(diào)整的余地。定理一：若某個基本可行解所對應(yīng)的檢驗向量CN-

CBB-1N<=0,則這個基本可行解就是最優(yōu)解。定理二：若某個基本可行解所對應(yīng)的檢驗向量CN-

CBB-1N存在一個檢驗數(shù)=0,則該問題有無數(shù)多個最優(yōu)解。定理三：若某個基本可行解所對應(yīng)的檢驗向量Cj-

CBB-1Nj大于0，且aij,都小于0，則無解。為了矩陣形求逆計算方便，一般將B轉(zhuǎn)化為單位矩陣。第5頁，共34頁，2023年，2月20日，星期一①將線性規(guī)劃問題化成標準型。②找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。③計算各非基變量xj的檢驗數(shù)j=Cj-CBPj′，若所有j≤0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。④在大于0的檢驗數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk≤0，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步。⑤根據(jù)max{j｜j＞0}=k原則，確定xk為換入變量(進基變量)，再按規(guī)則計算：=min{bi/aik|aik＞0}=bl/aik

確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。⑥以aik為主元素進行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。2、單純形法的計算步驟

第6頁，共34頁，2023年，2月20日，星期一線性規(guī)劃的例子第7頁，共34頁，2023年，2月20日，星期一線性規(guī)劃--標準化引入變量：s1,s2,s3第8頁，共34頁，2023年，2月20日，星期一提取系數(shù)，填入表格：s.t.1x1+1x2+1s1+0s2+0s3=3002x1+1x2+0s1+1s2+0s3=400x1≥0,x2≥0,si≥00x1+1x2+0s1+0s2+1s3=250C向量CBCNXBXN基BN=

CBB-1b+(CN-

CBB-1N)

XNZj=CBNj每個非基變量的檢驗值第9頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1b第10頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1b目標函數(shù)系數(shù)區(qū)約束條件系數(shù)區(qū)右端系數(shù)檢驗系數(shù)區(qū)基變量區(qū)第11頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001Zj=CBNjZ=CBB-1b第12頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000000111003002101040001001250Zj=CBNjZ=CBB-1b第13頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001111003002101040001001250Zj=CBNjZ=CBB-1b第14頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1x2s1s2s3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=CBB-1b第15頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=0第16頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=000000第17頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=010000050第18頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=050100000①可行解XB=B-1b-B-1NXN>=0第19頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400x201001250Zj=CBNjZ=CBB-1b①可行解XB=B-1b-B-1NXN>=0第20頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400x210001001250Zj=CBNjZ=CBB-1b①第21頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400x210001001250Zj=CBNjZ=CBB-1b①第22頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S1011100300S2021010400x210001001250Zj=CBNjZ=CBB-1b①第23頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150x210001001250Zj=CBNjZ=25000第24頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150x210001001250Zj=CBNj010000100Z=25000第25頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150x210001001250Zj=CBNj010000100Z=2500050000-100第26頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150x210001001250Zj=CBNj010000100Z=2500050000-100第27頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150x210001001250Zj=CBNj010000100Z=2500050000-100①第28頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1X2s1s2S3b比值501000003S101010-150S202001-1150x210001001250Zj=CBNj①x150x150第29頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)基變量CBx1x2s1s2S3b比值501000003x1501010-150S202001-1150x210001001250Zj=CBNj①第30頁，共34頁，2023年，2月20日，星期一初始單純形表迭代次數(shù)