單純型法的計算步驟

1、 單純形法的計算步驟由于單純形的目標(biāo)函數(shù)和約束函數(shù)中含有基變量和非基變量,為了設(shè)計出方便,有效的計算方法,我們將簡化單純形的表達(dá)形式,稱其為單純形表格。比如,下述單純形:的簡化單純形表格如下(參見表)。這種格式使得我們非常容易識別基變量,我們只要將僅表:簡單單純形表 基解     有個的列(和)為基變量。 標(biāo)準(zhǔn)最大化線性規(guī)劃的單純型法為了設(shè)計標(biāo)準(zhǔn)最大化線性規(guī)劃問題的初始單純形表,我們首先將它的等價問題改寫為:那么標(biāo)準(zhǔn)最大化線性規(guī)劃問題的初始單純形表被表示為(參見表):表:標(biāo)準(zhǔn)最大化線性規(guī)劃的初始單純形表          其

2、中:,為原問題目標(biāo)函數(shù)的系數(shù),為基變量下標(biāo)集合,為非基變量下標(biāo)集合,為基變量,為基變量在原問題目標(biāo)函數(shù)系數(shù),為基變量的解,那么初始基可行解為,為對應(yīng)初始目標(biāo)函數(shù)值。 我們將解釋表中和行的計算方法和經(jīng)濟涵義。由于標(biāo)準(zhǔn)最大化線性規(guī)劃問題可被看成是利用種資源生產(chǎn)種產(chǎn)品,決策變量在線性規(guī)劃約束條件中的系數(shù)可以被理解為,為了生產(chǎn)一件產(chǎn)品需要消耗原材料的數(shù)量;決策變量在目標(biāo)函數(shù)中的系數(shù)是一件產(chǎn)品的利潤;松弛變量則表示第種原材料的剩余量?；谏鲜雒枋?我們引入下面兩個概念:生產(chǎn)一件產(chǎn)品的單位邊際損失值其中,是對應(yīng)基變量在目標(biāo)函數(shù)中的系數(shù),顯然或表示某件產(chǎn)品的單位利潤或等于。乘積項有四種經(jīng)濟解釋:如果,代表產(chǎn)

3、品且,代表尚未使用的原材料,表示生產(chǎn)一件產(chǎn)品所消耗原材料的數(shù)量,則,表示生產(chǎn)一件產(chǎn)品沒有產(chǎn)生邊際損失;如果,代表產(chǎn)品且,也代表產(chǎn)品,表示產(chǎn)品與產(chǎn)品的替代關(guān)系,表示未了生產(chǎn)一件產(chǎn)品而放棄生產(chǎn)產(chǎn)品所產(chǎn)生的利潤損失,所以是生產(chǎn)一件產(chǎn)品而發(fā)生的邊際損失;如果,代表剩余原材料且,代表剩余原材料,表示剩余原材料與剩余原材料的之間的替代關(guān)系,則,表示這種替代不產(chǎn)生邊際損失;如果,代表剩余原材料且,代表產(chǎn)品,表示剩余原材料增加一個單位導(dǎo)致產(chǎn)品的產(chǎn)量減少,則是剩余原材料增加一個單位所引起的邊際損失;所以,我們將為了生產(chǎn)一件產(chǎn)品的所有邊際損失值相加,即,它就是為了生產(chǎn)單位產(chǎn)品而放棄生產(chǎn)其他產(chǎn)品所產(chǎn)生的利潤損失之和

4、。如果代表剩余原材料, 的經(jīng)濟涵義是種剩余原材料增加了一個單位而引起所有產(chǎn)品產(chǎn)量減少引起的利潤損失之和。我們將稱為單位邊際損失值。生產(chǎn)一件產(chǎn)品的邊際收益由于生產(chǎn)一件產(chǎn)品的單位邊際損失值是,而生產(chǎn)一件產(chǎn)品獲得的單位利潤是,那么代表生產(chǎn)單位產(chǎn)品的實際收益。對于利潤最大化的線性規(guī)劃問題,的經(jīng)濟學(xué)含義就是產(chǎn)品的邊際收益。只有當(dāng)大于時,生產(chǎn)產(chǎn)品才能夠增加收益。如果代表剩余原材料,則,這時,如果大于,這意味著當(dāng)種剩余原材料增加一個單位反而引起實際收益增加?？傊?是否大于作為單純形法是否繼續(xù)迭代的判別條件或檢驗準(zhǔn)則。是單純形中的,它可用于單純形是否繼續(xù)迭代的準(zhǔn)則。按當(dāng)前計劃生產(chǎn)的利潤單純形迭代是從初始表開始

5、,通過選擇主元素,進行高斯變換,產(chǎn)生新的單純形表。所以我們將單純形法的計算步驟總結(jié)如下:第一步:轉(zhuǎn)換標(biāo)準(zhǔn)最大化線性規(guī)劃問題為標(biāo)準(zhǔn)格式對標(biāo)準(zhǔn)最大化線性規(guī)劃問題引進松弛變量,消除小于等于不等式約束,構(gòu)造初始單純形表,并以松弛變量為初始基變量,以決策變量為初始非基變量。第二步:計算單純形表的和行利用公式和,我們分別計算單純形表中和行的數(shù)值。并利用,的符號判斷是否繼續(xù)進行迭代。如果對所有都有:,則當(dāng)前單純形表對應(yīng)的基可行解就是標(biāo)準(zhǔn)最大化線性規(guī)劃問題的最優(yōu)解。第三步:確定換入變量根據(jù),來決定換入變量,我們的目標(biāo)是選擇對目標(biāo)函數(shù)(利潤)貢獻最大的那個邊際收益,即確定換入變量的準(zhǔn)則為:下標(biāo)所對應(yīng)的變量就是換

6、入變量。第四步: 確定換出變量根據(jù)換入變量,所在的列,計算換出比例:,由于變量,的非負(fù)符號限制,換出變量的選擇規(guī)則為:或者:選擇,以,表示換出變量,那么稱變量與變量的交換系數(shù)為迭代的主元素。第五步:構(gòu)造一個新的單純形表以主元素進行迭代,把所對應(yīng)的列變換為:,在列中,用換入變量替代換出變量,在列中,用替代,得到一個新的單純形表?；氐降诙接嬎阈聠渭冃伪碇泻托械臄?shù)值,如果,那么當(dāng)前基可行解就是最優(yōu)解,否則繼續(xù)進行迭代。我們用例來說明單純形法的計算步驟。第一步:對例的約束條件引進松弛變量,那么例的標(biāo)準(zhǔn)格式為:然后,根據(jù)式構(gòu)造例初始單純形表(參見表):表: 例初始單純形表    

7、  第二步:計算和行如下:由于基變量下標(biāo)集為:,非基變量下標(biāo)集為:,對于任意,有,所以,對于非基變量的計算如下:同樣原理,對于,。對于基變量的的計算如下:同理,。根據(jù),行的各列計算結(jié)果參見表的行。第三步:確定換入變量: 由于選擇換入變量的標(biāo)準(zhǔn)是,根據(jù)表的行,可以確定為換入變量的下標(biāo),而為本次迭代的換入變量。第四步:確定換出變量根據(jù)換入變量所在的列,計算換出比例:,即:由于它們的最小值為,所以為換出變量的下標(biāo),同時變量被確定為換出變量。第五步:構(gòu)造一個新的單純形表以為主元素對所在列進行高斯變換:根據(jù)表,換出變量與非基變量的關(guān)系為:,將其兩端同時除以后,則有: 考慮下面二個方程: (表的

8、第3行) (表的第4行)希望消去變量,所以:再考慮下面二個方程: (表的第3行) (表的第5行) 為了消去變量,有:更新基變量下標(biāo)集:和非基變量下標(biāo)集:,再將變量用替換, 用替換,就獲得一張新單純形表(參見表)。若令所有非基變量等于,即:,基變量就分別為:,及,它們共同組成了一個基可行解,最后根據(jù)式,目標(biāo)函數(shù)。表: 例第二張單純形表   對表重復(fù)單純形算法第二步第五步。計算表中的和行。從表的行看到,對應(yīng)非基變量的,需要繼續(xù)迭代。確定換入變量:由于只有,那么確定換入變量的下標(biāo)為:,而為換入變量。確定換出變量:根據(jù)換入變量所在的列,計算換出比例:,即:,它們的最小值為,對應(yīng)的下標(biāo)為,所以

9、被確定為換出變量。構(gòu)造下一個新的單純形表:我們首先以為主元素對所在列(表的第五列)進行高斯變換,。然后再更新基變量下標(biāo)集:和非基變量下標(biāo)集:,再用變量替換,用替換,就獲得一張新單純形表(參見表)。若令所有非基變量等于,即:,基變量就分別為:,及,它們共同組成了一個基可行解,目標(biāo)函數(shù)為。表: 例第三張單純形表   對表重復(fù)單純形法的第二步第五步。計算表的行和行。從表的行看到,對于所有非基變量,均有:,停止迭代。所以表的基可行解是例的最優(yōu)解。 利用單純形法求解最小化問題利用單純形法求解最小化線性規(guī)劃問題的方法有兩種,我們將通過例來說明它們的應(yīng)用。 例 考慮下述最小化線性規(guī)劃問題:方法一如

10、果點是例的最優(yōu)解,則一定是問題的可行域中使得目標(biāo)函數(shù):達(dá)到最小值的可行解。這等價于是問題的可行域中使得函數(shù)達(dá)到最大值的可行解。所以為了求問題的最優(yōu)解,我們只需要求解下述線性規(guī)劃問題:在對問題引進松弛變量之后,我們可獲得其初始單純形表(參見表):表: 例初始單純形表-方法一   選擇非基變量為換入變量,換出比例說明為換出變量,迭代后的單純形(表參見表)為: 表: 例最優(yōu)單純形表-方法一   因為非基變量對應(yīng)的和都小于,所以表是例的最優(yōu)單純形表。那么,問題的最優(yōu)解為:, ,。而問題的最優(yōu)解為:, ,。或者將和代入問題的目標(biāo)函數(shù),有:總而言之,對于最小化線性規(guī)劃問題,可對它的目標(biāo)

11、函數(shù)成,然后按最大化線性規(guī)劃問題進行求解。方法二我們對求解最大化線性規(guī)劃問題的單純形法略作修改,就可獲得求解最小化線性規(guī)劃問題的單純形法。修改第二步:計算單純形表的和行,選擇,中絕對值最大的非基變量作為換入變量,如果所有,對應(yīng)單純形表上的基可行解就是最小化線性規(guī)劃問題的最優(yōu)解。這是因為增加非基變量的值只能能夠使目標(biāo)函數(shù)值增大。在對問題直接引進松弛變量之后,我們可獲得其初始單純形表(參見表):表: 例初始單純形表-方法二   因為對應(yīng)于非基變量的檢驗數(shù)為,選擇為換入變量,換出比例說明為換出變量,迭代后的單純形表參見表:表: 例最優(yōu)單純形表-方法二   因為非基變量對應(yīng)的檢驗數(shù)

12、和都大于,所以表是例的最優(yōu)單純形表。那么,問題的最優(yōu)解為:, ,。多重最優(yōu)解我們將說明如何利用單純形法確定一個線性規(guī)劃問題是否存在多重最優(yōu)解。我們在節(jié)中利用圖解法說明當(dāng)電視機生產(chǎn)問題的目標(biāo)函數(shù)為時的線性規(guī)劃具有多重最優(yōu)解。例 重新考慮電視機生產(chǎn)的線性規(guī)劃問題:對問題引進松弛變量,和之后,我們獲得初始單純形(參見表)表: 例初始單純形表       因為在檢驗行中,具有最大值,所以選擇非基變量為換入變量,比例值表明為換出變量,進行迭代后,獲得一新單純形表(參見表):表: 例最優(yōu)單純形表一       因為對應(yīng)于非基變量和的檢驗數(shù)和均不大

13、于,表是例的最優(yōu)單純形表,最優(yōu)解為:,。然而,在最優(yōu)單純形表中,非基變量的檢驗數(shù)等于,如果選擇為換入變量,對應(yīng)的比例值為,則為換出變量,迭代后的單純形表(參見表)為:表: 例最優(yōu)單純形表二       因為對應(yīng)于非基變量和的檢驗數(shù)和均不大于,表是例的另一個最優(yōu)單純形表,最優(yōu)解為:,。由于基可行解對應(yīng)可行域的一個頂點,那么我們可以說明連接上述兩個最優(yōu)頂點線段上的所有點都是例的最優(yōu)解。為此,我們設(shè):最優(yōu)頂點: 最優(yōu)頂點:那么,對于任意,也都是例的最優(yōu)解。比如,選擇,我們獲得一最優(yōu)解,。 無界解我們在節(jié)中討論了判斷標(biāo)準(zhǔn)最大化線性規(guī)劃問題是無界的條件,即:對于可行解,如果

14、存在某個使,并且對任意,都有。在本節(jié)中,我們將討論如何利用單純形來判斷線性規(guī)劃問題是無界的。例考慮下述線性規(guī)劃問題:對問題引進松弛變量和后,獲其初始單純形表(參見):表: 例初始單純形表     因為對應(yīng)非基變量的檢驗數(shù)中絕對值最大的為,選擇為換入變量。比例值表明為換出變量。迭代后的新單純形表(參見表)為:表: 例的第二張單純形表     選擇非基變量作為換入變量,比例值說明為換出變量。迭代后的新單純形表(參見表)為:表: 例的第三張單純形表     選擇非基變量作為換入變量,保持其他非基變量,和為,基變量,與的關(guān)系為：將它們代入問題的目標(biāo)函數(shù)中,則有：當(dāng)?shù)娜≈挡粩嘣龃髸r,比如,目標(biāo)值也不