線性規(guī)劃 第四講 單純形法的計算步驟

1、四、單純形法的計算步驟 為書寫規(guī)范和便于計算，對單純形法的計算設(shè)計了單純形表。每一次迭代對應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計算線性規(guī)劃問題的步驟?；静襟E1、標(biāo)準(zhǔn)化（構(gòu)造初始可行基）；2、列出初始單純形表；3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解 根據(jù)最大檢驗(yàn)數(shù)原則：if j0 是：計算結(jié)束；否：轉(zhuǎn)入下一步4、從一個基可行解轉(zhuǎn)到相鄰的另一個基可行解，然后轉(zhuǎn)3。要保證目標(biāo)函數(shù)值比原來更優(yōu)。 （1）進(jìn)基 （2）出基 2 1 0 0 0 檢驗(yàn)數(shù)單純形表結(jié)構(gòu) 單純形表 24/65/1C 2 1 0 0 0 24/65/1C檢驗(yàn)數(shù)單純

2、形表結(jié)構(gòu) 單純形表基可行解：單純形表結(jié)構(gòu) 單純形表 2 1 0 0 0 24/65/1C檢驗(yàn)數(shù)基本步驟1、標(biāo)準(zhǔn)化（構(gòu)造初始可行基）；2、列出初始單純形表；3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解 根據(jù)最大檢驗(yàn)數(shù)原則：if j0 是：計算結(jié)束；否：轉(zhuǎn)入下一步4、從一個基可行解轉(zhuǎn)到相鄰的另一個基可行解，然后轉(zhuǎn)3。要保證目標(biāo)函數(shù)值比原來更優(yōu)。 （1）進(jìn)基 （2）出基單純形表結(jié)構(gòu) 4 從一個基可行解轉(zhuǎn)換到相鄰的另一個基可行解 2 1 0 0 0 24/65/1C檢驗(yàn)數(shù)主行單純形表結(jié)構(gòu) 單純形表 2 1 0 0 0 24/65/1C檢驗(yàn)數(shù)主元，主元變成1，主元所在列其他數(shù)變成0用單純形表求解LP問題例、用單純形表

3、求解LP問題解：化標(biāo)準(zhǔn)型 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 24/65/1主元化為1主列單位向量 換出 換入表1：列初始單純形表 （單位矩陣對應(yīng)的變量為基變量）正檢驗(yàn)數(shù)中最大者對應(yīng)的列為主列最小的值對應(yīng)的行為主行 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 15/524/26/4 0*5 2*2/6 +0*4/61- 2/3=表2：換基 （初等行變換，主列化為單位向量，主元為1）檢驗(yàn)數(shù)0確定主列 最小確定主列主元 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 檢驗(yàn)數(shù)=0最優(yōu)解為X=(7/2,3/2,15/2,0,0)目標(biāo)函數(shù)值Z=8.5 2*7/2 1*3/2+0*15/28.5表3：換基 （初等行變換，主列化為單位向量，主元為1）練習(xí)題1解：原問題化為標(biāo)準(zhǔn)型四、單純形法計算步驟列初始單純形表15四、單純形法計算步驟1