單純形法解題步驟

1、三、單純形法的解題步驟第一步：作單純形表 .）（ 1）把原線性規(guī)劃問題化為標準形式；）（ 2）找出初始可行基，通常取約束方程組系數(shù)矩陣中的單位矩陣；）（ 3）目標函數(shù)非基化；）（ 4）作初始單純形表 .第二步：最優(yōu)解的判定 .（1） 若所有檢驗數(shù)都是非正數(shù)，即 ， 則此時線性規(guī)劃問題已取 得最優(yōu)解 .（2） 若存在某個檢驗數(shù)是正數(shù)，即 ，而所對應的列向量無正分量，則線性規(guī)劃 問題無最優(yōu)解 .如果以上兩條都不滿足，則進行下一步 .第三步：換基迭代 .（ 1）找到最大正檢驗數(shù)，設為，并確定 所在列的非基變量 為進基變量 .（ 2）對最大正檢驗數(shù)所在列實施最小比值法，確定出主元，并把主元加上小括號主

2、元是最大正檢驗數(shù) 所在列， 用常數(shù)項 與進基變量 所對應的列向 量中正分量的比值 最小者；（ 3）換基：用進基變量替換出基變量 ，從而得到新的基變量 .也就是主元所在列的非基變量進基，所在行的基變量出基；（ 4）利用矩陣的行初等變換，將主元變?yōu)?，其所在列其他元素都變?yōu)榱悖瑥拇说玫叫碌膯渭冃伪?；?）回到第二步，繼續(xù)判定最優(yōu)解是否存在，然后進行新一輪換基迭代，直到問題得 到解決為止 .例 3 求 .解 （1） 化標準型：令，引進松弛變量 ，其標準型為（ 2） 作單純形表：在約束方程組系數(shù)矩陣中的系數(shù)構成單位矩陣，故取為基變量，目標函數(shù)已非基化了，作初始單純形表并“換基迭代” （見表 6.8）表

3、 6.8x1x2x3x4x5常數(shù)x 3101005x 41201010x 50（1）0014S130000x 3101005x 4（1）001-22x2010014S1000-3-12x 3001-123x 11001-22x 2010014S000-1-1-143） 最終結果：此時檢驗數(shù)均為非正數(shù)，線性規(guī)劃問題取得最優(yōu)解，最優(yōu)解為目x1x2x3x4常數(shù)原線x31-1102目標x4-3(1)014S23000題.x3-20116x2-31014S1100-312標函數(shù)取得最優(yōu)值 .性規(guī)劃問題的最優(yōu)解為： . 函 數(shù) 的 最 優(yōu) 值 為 14 ， 即.例 4 用單純形方法解線性規(guī)劃問1、2 行，

4、 3、4解 此數(shù)學模型已是標準型了，其中約束方程含有一個二階單位矩陣（ 列構成），取 為基變量，而目標函數(shù)沒有非基化 .從約束方程找出，,代入目標函數(shù)經(jīng)整理后，目標函數(shù)非基化了作單純形表，并進行換基迭代（見表 6.9）為主元，對主元所在列施以行初等變最大檢驗數(shù) ，由最小比值法知： 換，基變量 出基，非基變量 進基 .表 6.9目前最大檢驗數(shù) ，其所在列沒有正分量，所以該線性規(guī)劃問題沒有最優(yōu)解例 5 用單純形方法解線性規(guī)劃問題解此數(shù)學模型已是標準型了， 其中約束方程含有一個二階單位矩陣， 取 為基變 量，而目標函數(shù)沒有非基化 .從約束方程找出，,代入目標函數(shù)，經(jīng)整理得,目標函數(shù)已非基化 .作單純

5、形表，并進行換基迭代 （見表 6.10）.最大檢驗數(shù) ，由最小比值法知： 為主元，對主元所在列施以行初等變 換，基變量 出基，非基變量 x2進基，先將主元化為 1，然后再將主元所在列的其他元素化為零 .表 6.10x 1x2x3x4常數(shù)x 3-2（2）104x 431016S-220010x 2-1102x 440-14S00-106至此，檢驗數(shù)均為非正數(shù)，故得基礎可行解原問題的最優(yōu)解為： .最優(yōu)值為 6，即.如果我們再迭代一次，將基變量 出基，非基變量 進基（見表 6.11）表 6.11x1x2x3x4常數(shù)x2-1102x4（4）014S00-106x2013x1101S00106可得到另一個基礎可行解原問題的最優(yōu)解為： ，最優(yōu)值仍為 6，說明該線性規(guī)劃問題有 無窮多最優(yōu)解，其最優(yōu)解均為 6.如何知道線性規(guī)劃問題有無窮多最優(yōu)解呢？這主要反映在單