改進單純形法

單純形法的矩陣描述設(shè)線性規(guī)劃問題：給這個線性規(guī)劃問題的約束條件加入松弛變量6.2.6改進單純形法得到標準型設(shè)B是一個可行基，若將系數(shù)矩陣（A，I）分為（B，N），N是非基變量的系數(shù)矩陣。對應(yīng)于B的變量是基變量，用向量表示。其他為非基變量。將C分為于是，約束方程組用矩陣表示為：目標函數(shù)為：這時可將線性規(guī)劃標準型改寫為矩陣形式：將約束方程移項，得：左乘后，得到的表達式代入目標函數(shù)，得到：令非基變量得到一個基可行解目標函數(shù)值：1、非基變量的系數(shù)就是檢驗數(shù)令稱為單純形乘子2、用矩陣描述時，規(guī)則的表達式是：3、單純形表當(dāng)確定為基變量時，經(jīng)過基變換，可得到：用矩陣表示為：

單純形法的迭代過程實質(zhì)上是從一組基到另一組基的變換，每當(dāng)基變量確定后，只要把這個基在初始單純形表中相應(yīng)列的系數(shù)矩陣的逆矩陣求出來，則單純形表上的其它列的數(shù)字也隨著確定。而為了確定一組新的基，關(guān)鍵是要找出換入變量和換出變量。找換入變量是通過求所有非基變量列的檢驗數(shù)，從中找出最大的正檢驗數(shù)來確定。在找出換入變量后，根據(jù)

規(guī)則確定換出變量。而每次迭代中真正有用的數(shù)字是基變量列數(shù)字,基變量的逆矩陣，非基變量的檢驗數(shù)以及最大正檢驗數(shù)對應(yīng)的非基變量的系數(shù)列向量。計算表Ⅰ非基變量基變量icBxBbx1x2x3x4x5x60x31222100012/20x481201008/20x516400010－0x61204*000112/4z

230000

計算表Ⅱ非基變量基變量ibx1x6x3x4x5x20x362-1/210006/20x421-1/201002/10x51600001016/43x2341/40001－j2-3/40000

計算表Ⅲ非基變量基變量ibx4x6x3x1x5x20x32-21/210002/0.52x121-1/20100－0x53-4200108/23x2301/400013/0.25j-21/40000

計算表VI非基變量基變量

bx4x5x3x1x6x20x30-1-1/41000

2x1401/40100

0x64-21/20010

3x221/2-1/30001

j-1.5-1/80000

改進單純形法求解線性規(guī)劃的計算步驟然后計算單純形乘子

第二步：計算非基變量xN的檢驗數(shù)j，j=m+1,…,n。若j≤0，已得到最優(yōu)解，可停止計算。若還存在j＞0，轉(zhuǎn)下步。第一步：根據(jù)給出的線性規(guī)劃問題，在加入松弛變量或人工變量后得到初始基變量。求初始基矩陣B的逆矩陣B-1。于是可以求出初始解。第三步：根據(jù)所對應(yīng)的非基變量，確定為換入變量。計算B-1PK，若B-1PK≤0，那么問題無解，停止計算。否則轉(zhuǎn)入下一步。第四步：根據(jù)

規(guī)則，求出和它對應(yīng)的基變量xl，確定xl為換出變量。于是可給出一組新的基變量以及新的基矩陣B1。第五步：計算新的基矩陣的逆矩陣,求出及。重復(fù)第二步到第五步。6.3靈敏度分析一、系數(shù)變化范圍的確定的最優(yōu)解。要求保持已求得最優(yōu)解不變的條件下，確定aij,bi,cj這些系數(shù)變化的范圍。1．目標函數(shù)中cj的變化范圍的確定。設(shè)cj是變量xj在目標函數(shù)中的系數(shù)。若在其它參數(shù)不變的情況下，cj變化了cj?？梢苑謩e就cj是非基變量和基變量的系數(shù)這兩種情況來討論。設(shè)已求得了線性規(guī)劃問題（1）若cj是非基變量xj的系數(shù)。這時它在計算表中所對應(yīng)的檢驗數(shù)是當(dāng)cj變化cj后，要保證在最終計算表中這個檢驗數(shù)仍然小于或等于零；即其中，單純形乘子（2）若系數(shù)cr是基變量xr在目標函數(shù)中的系數(shù)。當(dāng)cr變化cr，那么在最終計算表中對應(yīng)基變量xr的檢驗數(shù)是

當(dāng)cr沒有變化，這時在最終計算表中xr的檢驗數(shù)

因為cr是屬于cB中的一個數(shù)。所以當(dāng)cr變化了cr時，就引起cB發(fā)生變化，這時是基變量xr在最終計算表中所在行的各系數(shù)值。（j=1,2,…,n），cr可以變化的范圍是若要求原最優(yōu)解不變，即必須滿足，于是可以得到當(dāng)當(dāng)2．在約束條件中bi的變化范圍的確定。若第r個約束條件的br變化了br，并假設(shè)規(guī)劃問題的其它