單純形法的解題步驟

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

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

3、取心.二.心為基變量，目標(biāo)函數(shù)已非基化了，作初始單純形表并“換基迭代”（見表）.X1X2X3X4X5常數(shù)X3101005X41201010X50 (1) 0014S'130000X3101005X4(1) 001-22X2010014S'1000-3-12X3001-123xi1001-22X2010014S'000-1-1-14（3）最終結(jié)果： 數(shù)，線性規(guī)劃問題取得目標(biāo)函數(shù)取得最優(yōu)值原線性規(guī)劃問題的最優(yōu)解 函數(shù)的最優(yōu)值為14,即此時檢驗數(shù)均為非正最優(yōu)解，最優(yōu)解為為：二丄廠二二目標(biāo)max j? = 2-l-3x4 = n4 .例4用單純形方法解線性規(guī)劃問題18 2 11

4、、2 行，3、4 列解此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個二階單位矩陣（ 構(gòu)成），取為基變量，而目標(biāo)函數(shù)沒有非基化 從約束方程找出.二一-，飛 + -，1 -,代入目標(biāo)函數(shù)g 22 +-(2-x1 + x3)-(4 + 3-x2) = -2x1 -3經(jīng)整理后，目標(biāo)函數(shù)非基化了 作單純形表，并進行換基迭代（見表）最大檢驗數(shù) _，由最小比值法知：， 1為主元，對主元所在列施以行初等變換,基變量 仏出基，非基變量門 進基.X1X2X3X4常數(shù)X3X41-110-3(1)0124劃S23000題X3-20116X2-31014S1100-312表目前最大檢驗數(shù)：.，其所在列沒有正分量，所以該線

5、性規(guī)問題沒有最優(yōu)解例5用單純形方法解線性規(guī)劃問求 I I . :'-.+.，一.=解此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了， 其中約束方程含有一個二階單位矩陣，取為基變量,而目標(biāo)函數(shù)沒有非基化從約束方程找出代入目標(biāo)函數(shù)，經(jīng)整理得目標(biāo)函數(shù)已非基化作單純形表，并進行換基迭代（見表.最大檢驗數(shù)：亠：，由最小比值法知：一i二為主元，對主元所在列施以行初等變換， 基變量出基，非基變量X2進基，先將主元；二化為1，然后再將主元所在列的其他元 素化為零至此，檢驗數(shù)均為非 解X1X2X3X4常數(shù)X3-2 (2) 104X431016S-220010X2也。2X440弓14S'00-106正數(shù)，故得基礎(chǔ)可行原問題的最優(yōu)解為：.|1 'I .最優(yōu)值為6，即匚二m + :如果我們再迭代一次，將基變量出基，非基變量.匚進基（見表）可得到另一個基礎(chǔ)可X1X2X3X4常數(shù)X2-11L 022X4(4) 0 14S'00-10 亠6X2cC 1018 43X110-111S'& 4 00- 1 06表行解原冋題的最優(yōu)解為： 亠.，最優(yōu)值仍為6，說明該線性規(guī)劃冋題有無窮多最優(yōu)解，其最優(yōu)解均為6.如何知道線性規(guī)劃問題有無窮