改進(jìn)單純形法

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

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

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

230000

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

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

計(jì)算表VI非基變量基變量

bx4x5x3x1x6x20x30-1-1/41000

2x1401/40100

0x64-21/20010

3x221/2-1/30001

j-1.5-1/80000

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

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

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

當(dāng)cr沒(méi)有變化，這時(shí)在最終計(jì)算表中xr的檢驗(yàn)數(shù)

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