資源描述：
《單純形法大M法兩階段法.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、目錄單純形算法計算步驟初始可行基的確定大M法兩階段法4231線性規(guī)劃的單純形算法計算流程初始基本可行解是否最優(yōu)解或無限最優(yōu)解?結束沿邊界找新的基本可行解NY線性規(guī)劃解的概念1.初始基本可行解的確定線性規(guī)劃標準型：minZ=CXAX=bX≥0從系數(shù)矩陣A中找到一個可行基B，不妨設B由A的前m列組成，即B=(P1,P2,……Pm)。進行等價變換－－約束方程兩端分別左乘B－1.2.最優(yōu)性檢驗3.基變換取某一非基變量xk→換入基（即讓xk>0，其余非基變量仍為0），同時再從基變量中換出一個變量xBr→作為非基
2、變量。如何求換入變量xk和換出變量xBr？3.基變換從目標函數(shù)看xk越小越好，但從可行性看xk又不能任意小。若aik≤0,i=1,…，m,xk可任意取值，此時問題是無界的；若aik>0,為保證可行性，即xBi=bi-aikxk≥0，應取重復上述過程，直至所有的σj均≥0，得到最優(yōu)解。注意：xBr=0總結計算步驟：給定初始基步1.令xN=0,，xB=B-1b=b，z0=cBxB；步2.檢驗數(shù)σj=cj-cBB-1Pj，σj≥0，停止，得最優(yōu)解，否則取σk＝min{σj}，轉步3；步3.解ak=B-1Pk
3、，若ak≤0，停止,不存在有限最優(yōu)解.否則轉步4.計算xk進基，xBr離基，用Pk替代PBr得新的可行基B步5.以ark為主元素進行迭代.轉步2新可行解：x=(xB1,…xBr-1,0,xBr+1,…,xBm,0,…，0,xk,0,…，0)單純形法流程圖初始可行基開始以ark為主元素進行迭代得到最優(yōu)解得到最優(yōu)解YYNN所有σj≥0？所有ark≤0?計算σk＝min{σj
4、σj<0}單純形法例題例3.2求解線性規(guī)劃問題?將線性規(guī)劃問題化為標準形式?作初始單純形表，按單純形法計算步驟進行迭代，結果如下：C
5、BXBb－2－3000x1x2x3x4x50x381210040x41640010－0x5120[4]00130－2－3000單純形法例題0x32[1]010－1/220x416400104－3x2301001/4－9－20003/4－2x121010－1/2－0x4800－41[2]4－3x2301001/412130020－1/4－2x141001/400x５400－21/21－3x22011/2－1/8014003/21/80表最后一行的檢驗數(shù)均為正，這表示目標函數(shù)值已不可能再減小，于是得到最優(yōu)
6、解，目標函數(shù)值．初始可行基的確定若系數(shù)矩陣A中含有一個子矩陣是單位矩陣Im,則取Im為初始可行基。對于約束條件是“≤”形式的不等式，引入松弛變量將其轉換為標準型，再將系數(shù)矩陣中松弛變量對應的單位矩陣取為初始可行基。對于約束條件是“≥”形式的不等式及等式約束情況，若不存在單位矩陣時，可采用人工變量，即對不等式約束就減去一個非負的剩余變量后，再加入一個非負的人工變量；對等式約束再加入一個非負的人工變量，總可得到一個單位矩陣作為初始可行基。大M法和兩階段法如果線性規(guī)劃模型中約束條件系數(shù)矩陣中不存在單位向量組
7、，解題時應先加入人工變量，人工地構成一個單位向量組。人工變量只起過渡作用，不應影響決策變量的取值。兩種方法可控制人工變量取值使用，盡快地把人工變量減小到零。大M法兩階段法大M法minz=-3X1+X2+X3x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0minz=-3X1+X2+X3+0x4+0x5–Mx6–Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，x2，x3，x4，x5，x6，x7≥0大M單純形法要
8、求將目標函數(shù)中的人工變量被指定一個很大的目標函數(shù)系數(shù)（人工變量與松弛剩余變量不同之處）。兩階段法minz=-3X1+X2+X3x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0minz=x6+x7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，x2，x3，x4，x5，x6，x7≥0第一階段，構筑一個只包括人工變量的目標函數(shù),在原約束條件下求解，如果計算結果是人工變量均為0，則繼續(xù)求解；進入第二階段，如果人工變量不為
9、0，說明原問題無解。目的是為原問題求初始基可行解。第二階段，在此基可行解基礎上對原目標函數(shù)進行優(yōu)化。習題三2.(1)用單純形法求解線性規(guī)劃問題：?將線性規(guī)劃問題化為標準形式?作初始單純形表，按單純形法計算步驟進行迭代，結果如下：習題三?作初始單純形表，按單純形法計算步驟進行迭代，結果如下：此時，σ均為正，目標函數(shù)已不能再減小，于是得到最優(yōu)解為：x*=(1,1.5,0,0)T目標函數(shù)值為：f(x*)=17.5習題三3.(1)分別用單純形法中的大M法和兩階段
