第1章 線性規(guī)劃與單純形法-第4節(jié)課件

運(yùn)籌學(xué)

（第三版）

《運(yùn)籌學(xué)》教材編寫組編

第1章線性規(guī)劃與單純形法第4節(jié)單純型法的計(jì)算步驟第1章線性規(guī)劃與單純形法-第4節(jié)第1章線性規(guī)劃與單純形法第4節(jié)單純型法的計(jì)算步驟第1章線性規(guī)劃與單純形法-第4節(jié)第4節(jié)單純型法的計(jì)算步驟

根據(jù)以上討論的結(jié)果，將求解線性規(guī)劃問(wèn)題的單純形法的計(jì)算步驟歸納如下如利用單純型表，求解線性規(guī)劃問(wèn)題。

第1章線性規(guī)劃與單純形法-第4節(jié)4.1單純型表為了便于理解計(jì)算關(guān)系，現(xiàn)設(shè)計(jì)一種計(jì)算表，稱為單純形表，其功能與增廣矩陣相似，下面來(lái)建立這種計(jì)算表。將(1-22)式與目標(biāo)函數(shù)組成n+1個(gè)變量，m+1個(gè)方程的方程組。第1章線性規(guī)劃與單純形法-第4節(jié)線性規(guī)劃的方程組第1章線性規(guī)劃與單純形法-第4節(jié)為了便于迭代運(yùn)算，可將上述方程組寫成增廣矩陣形式

第1章線性規(guī)劃與單純形法-第4節(jié)

若將z看作不參與基變換的基變量，它與x1,x2,…,xm的系數(shù)構(gòu)成一個(gè)基，這時(shí)可采用行初等變換將c1,c2,…,cm變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣。得到

第1章線性規(guī)劃與單純形法-第4節(jié)可根據(jù)上述增廣矩陣設(shè)計(jì)計(jì)算表，

表1-2。

第1章線性規(guī)劃與單純形法-第4節(jié)表1-2的說(shuō)明XB列中填入基變量，這里是x1，x2,…，xm；CB列中填入基變量的價(jià)值系數(shù)，這里是c1,c2,…,cm；它們是與基變量相對(duì)應(yīng)的；b列中填入約束方程組右端的常數(shù)；cj行中填入基變量的價(jià)值系數(shù)c1,c2,…,cn；θi列的數(shù)字是在確定換入變量后，按θ規(guī)則計(jì)算后填入；最后一行稱為檢驗(yàn)數(shù)行，對(duì)應(yīng)各非基變量xj的檢驗(yàn)數(shù)是第1章線性規(guī)劃與單純形法-第4節(jié)

4.2計(jì)算步驟

表1-2稱為初始單純形表，每迭代一步構(gòu)造一個(gè)新單純形表。計(jì)算步驟：(1)按數(shù)學(xué)模型確定初始可行基和初始基可行解，建立初始單純形表。(2)計(jì)算各非基變量xj的檢驗(yàn)數(shù)，檢查檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)則已得到最優(yōu)解，可停止計(jì)算。否則轉(zhuǎn)入下一步。

第1章線性規(guī)劃與單純形法-第4節(jié)(3)在σj＞0,j=m+1,…,n中，若有某個(gè)σk對(duì)應(yīng)xk的系數(shù)列向量Pk≤0，則此問(wèn)題是無(wú)界，停止計(jì)算。否則，轉(zhuǎn)入下一步。(4)根據(jù)max(σj＞0)=σk，確定xk為換入變量，按θ規(guī)則計(jì)算第1章線性規(guī)劃與單純形法-第4節(jié)(5)以alk為主元素進(jìn)行迭代(即用高斯消去法或稱為旋轉(zhuǎn)運(yùn)算)，把xk所對(duì)應(yīng)的列向量將XB列中的xl換為xk，得到新的單純形表。重復(fù)(2)～(5)，直到終止。第1章線性規(guī)劃與單純形法-第4節(jié)現(xiàn)用例1的標(biāo)準(zhǔn)型來(lái)說(shuō)明上述計(jì)算步驟。

(1)取松弛變量x3,x4,x5為基變量，它對(duì)應(yīng)的單位矩陣為基。這就得到初始基可行解X(0)=(0,0,8,16,12)T將有關(guān)數(shù)字填入表中，得到初始單純形表，見表1-3。表中左上角的cj是表示目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)。在CB列填入初始基變量的價(jià)值系數(shù)，它們都為零。

第1章線性規(guī)劃與單純形法-第4節(jié)

目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)。1.計(jì)算檢驗(yàn)數(shù)，由它確定為換人變量2.計(jì)算θ，由它確定為換出變量3.確定主元素表1-3基變量第1章線性規(guī)劃與單純形法-第4節(jié)計(jì)算非基變量的檢驗(yàn)數(shù)各非基變量的檢驗(yàn)數(shù)為σ1=c1-z1=2-(0×1+0×4+0×0)=2σ2=c2-z2=3-(0×2+0×0+0×4)=3填入表1-3的底行對(duì)應(yīng)非基變量處。第1章線性規(guī)劃與單純形法-第4節(jié)進(jìn)行（2），（3）

它所在行對(duì)應(yīng)的x5為換出變量，x2所在列和x5所在行的交叉處[4]稱為主元素或樞元素(pivotelement)第1章線性規(guī)劃與單純形法-第4節(jié)

進(jìn)行（4）(4)以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算或迭代運(yùn)算，即初等行變換，使P2變換為（0,0,1）T,在XB

列中將x2

替換x5,于是得到新表1-4.

換人變量換出變量主元素第1章線性規(guī)劃與單純形法-第4節(jié)

(5)檢查表1-4的所有cj-zj,這時(shí)有c1-z1=2；說(shuō)明x1應(yīng)為換入變量。重復(fù)(2)～(4)的計(jì)算步驟，得表1-5。

還存在檢驗(yàn)數(shù)〉0，繼續(xù)進(jìn)行。換人變量換出變量主元素第1章線性規(guī)劃與單純形法-第4節(jié)(6)表1-6最后一行的所有檢驗(yàn)數(shù)都已為負(fù)或零。這表示目標(biāo)函數(shù)值已不可能再增大，于是得到最優(yōu)解

第1章線性規(guī)劃與單純形法-第4節(jié)

最優(yōu)解

X*=X(3)=(4,2,0,0,4)