lp案例ab鋼鐵配礦問題教學用

§3單純形法

(SimplexMethod)本節(jié)重點：檢驗數(shù)的概念和計算最優(yōu)性判別基變換（換入變量和換出變量的確定）旋轉變換2023/10/27管理運籌學課程組3923．1基本思想

對于一個標準型LP問題，從一個初始基可行解出發(fā)，判斷其是否為最優(yōu)解，若是則結束；否則求一個與其“相鄰”的、改進的基可行解。再判斷這個解是否最優(yōu)，若是則結束，否則再求一個“相鄰”的、改進的基可行解……如此迭代下去，直到找到基最優(yōu)解或判定問題無解為止。x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例1，OQ1Q2或OQ4Q3Q22023/10/27管理運籌學課程組393單純形法要解決的三方面的問題：（1）如何確定初始的基可行解？（2）如何進行解的最優(yōu)性判別？（3）如何尋找改進的基可行解？2023/10/27管理運籌學課程組3943．2確定初始基可行解

定義：線性規(guī)劃規(guī)范型，當線性規(guī)劃標準型：

Maxz=CX2023/10/27管理運籌學課程組395其中系數(shù)矩陣A=[P1，P2，…，Pn]中含有一單位矩陣I，不妨設單位矩陣I即為一初始可行基。令非基變量取值為零，便得到一組基可行解。

2023/10/27管理運籌學課程組3963.2最優(yōu)性檢驗和解的判別

對標準型的一般線性規(guī)劃問題，經(jīng)過變換、迭代，總可將線性規(guī)劃約束條件中非基變量移至方程右邊，得如下形式：即：其中i=1，2，…，m2023/10/27管理運籌學課程組397是常數(shù)，故可以用將上述表述式代入目標函數(shù)式中，整理得：令于是

再令

其中稱為檢驗數(shù)，則有

由于檢驗數(shù)表示目標函數(shù)中的價值系數(shù)。2023/10/27管理運籌學課程組398為對應于基B的一個基可若行解，對于一切有檢驗數(shù)則

為最優(yōu)解。定理5:（最優(yōu)解的判別定理）2023/10/27管理運籌學課程組399

定理6（無窮多最優(yōu)解的判別定理）

若對應于基B的一個基可行解，對于一切，有檢驗數(shù)且存在某個非基變量對應的檢驗數(shù)=0，則該線性規(guī)劃問題有無窮多個最優(yōu)解。2023/10/27管理運籌學課程組3910無窮多最優(yōu)解判別定理：若B的一個基可行解，且對一切的j=m+1,...,n有為對應于基又存在某個非基變量的檢驗數(shù)則線性規(guī)劃問題又無窮多最優(yōu)解。證明：非基變量新基可行解新的目標函數(shù)值不變換入兩個最優(yōu)解，連線上的所有點均是最優(yōu)解。2023/10/27管理運籌學課程組3911定理7

（無界解的判別定理）若為對應于基B的一個基可行解，存在某個非基變量對應的檢驗數(shù)>0，并且對應的變量系數(shù)，則該線性規(guī)劃問題有無界解（或無最優(yōu)解）。2023/10/27管理運籌學課程組3912無界解的判別定理：若一個基可行解，有一個為對應于基B的并且對i=1,...,m有那么線性規(guī)劃問題具有無界解（無最優(yōu)解）。證明：構造新的解++===>-=++kmjnmjabxjkmkmiii且,,1,0,0,)1()1(',')1(Llllxxi=1,2,…m2023/10/27管理運籌學課程組3913驗證可行性：因為i,m,+00><=lka將代入到目標函數(shù)中得無可行解的判別：待以后將完人工變量法以后再講。x1+a1,m+1’xm+1+…+a1n’xn=b1’x2+a2,m+1’xm+1+…+a2n’xn=b2’……xm+am,m+1’xm+1+…+amn’xn=bm’xj≥0，j=1,2,…,n每一個aij和bi均帶“撇”2023/10/27管理運籌學課程組39142023/10/27管理運籌學課程組3915

2.換出變量的確定在中，令xk>0，而xj=0(m+1

j

n，j

k)，要保持xi

0(i=1，2，…,m)，即必須

于是，當為換出變量。若所有則xk

可取無窮大，問題無最優(yōu)解。2023/10/27管理運籌學課程組39162023/10/27管理運籌學課程組39173迭代

確定換入變量：當，確定換入變量；確定換出變量：當，確定換入變量；將交叉元素（主軸元素）單位化，(旋轉)2023/10/27管理運籌學課程組3918即乘以初等矩陣。重復上述步驟直到所有的檢驗數(shù)