單純形法的解題步驟

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

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

3、x 41201010x 50（1） 00 14S130000x 3101005x 4（ 1） 001-22x 20100141000-3-12Sx 3001-123x 11001-22x 2010014S000-1 -1-14（ 3） 最終結(jié)果：此時檢驗數(shù)均為非正數(shù)，線性規(guī)劃問題取得最優(yōu)解，最優(yōu)解為目標(biāo)函數(shù)取得最優(yōu)值.原線性規(guī)劃問題的最優(yōu)解為：例 4用單純形方法解線性規(guī)劃問題. 目標(biāo)函數(shù)的最優(yōu)值為 14，即.求.解 此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個二階單位矩陣（1、2 行， 3、4列構(gòu)成），取為基變量，而目標(biāo)函數(shù)沒有非基化. 從約束方程找出，,代入目標(biāo)函數(shù),經(jīng)整理后，目標(biāo)函數(shù)非基化

4、了.作單純形表，并進行換基迭代（見表）.最大檢驗數(shù)，由最小比值法知：為主元，對主元所在列施以行初等變換，基變量出基，非基變量進基 .表x1xx3x4常數(shù)2x31-1102x4-3(1)014S23000x3-20116x2-31014S1100-3目前最大檢驗數(shù)，其12所在列沒有正分量，所以該線性規(guī)劃問題沒有最優(yōu)解.例 5 用單純形方法解線性規(guī)劃問題.求解 此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個二階單位矩陣，取為基變量，而目標(biāo)函數(shù)沒有非基化. 從約束方程找出，,代入目標(biāo)函數(shù)，經(jīng)整理得,目標(biāo)函數(shù)已非基化.作單純形表，并進行換基迭代(見表.最大檢驗數(shù)，由最小比值法知：為主元，對主元所在列施以

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