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)解.如果以上兩條都不滿足，則進(jìn)行下一步.第三步：換基迭代.（1） 找到最大正檢驗數(shù)，設(shè)為山，并確定，1|所在列的非基變量:為進(jìn)基變量.（2） 對最大正檢驗數(shù)所在列實施最小比值法，確定出主元，并把主元加上小括號主元是最大正檢驗數(shù).：所在列

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

3、基變量，目標(biāo)函數(shù)已非基化了，作初始單純形表并“換基迭代”（見表6.8）表6.8xiX2X3X4X5常數(shù)x 3101005x 41201010x 50(1)0014S'130000x 3101005X 4(1)001-22X2010014S'1000-3-12x 3001-123x 11001-22x 2010014S'000-1-1-14（3）最終結(jié)果：此時檢驗數(shù)均為非正數(shù)，線性規(guī)劃問題取得最優(yōu)解，最優(yōu)解為X = 2 4 3 0 Of目標(biāo)函數(shù)取得最優(yōu)值1_ .原線性規(guī)劃問題的最優(yōu)解為： .J 目標(biāo)函數(shù)的最優(yōu)值為14,即 mazS 二 2+3x4 = 14.例4用單純形方

4、法解線性規(guī)劃問題 .+r1821求一 . 15 3 5 3 5 *可乃+心=2一 3心十兀2 +才4二4勺 > 0Q = 1.234）1、2 行，3、4解此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個二階單位矩陣（ 列構(gòu)成），取 I T為基變量，而目標(biāo)函數(shù)沒有非基化從約束方程找出+.二，二二 4 巧二,代入目標(biāo)函數(shù)g2- - 7 : 一 '1 1 -. - :-.,經(jīng)整理后，目標(biāo)函數(shù)非基化了作單純形表，并進(jìn)行換基迭代（見表6.9）最大檢驗數(shù)= 3 ，由最小比值法知:換，基變量 二出基，非基變量 .進(jìn)基.-1為主元，對主元所在列施以行初等變表6.9目前最大檢驗數(shù)；二】1,其所在列沒有

5、正分量，所以該線性規(guī)劃問題沒有最優(yōu)解例5用單純形方法解線性規(guī)劃問題求一-二+一 +二+.=4心(廠1234)解此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了， 其中約束方程含有一個二階單位矩陣, 量，而目標(biāo)函數(shù)沒有非基化從約束方程找出代入目標(biāo)函數(shù)，經(jīng)整理得二1'，目標(biāo)函數(shù)已非基化.作單純形表，并進(jìn)行換基迭代（見表6.10）.法知：為主以行初等變換，基變 x2進(jìn)基，先將主元X1X2X3X4常數(shù)X31-1102再將主兀所在列的其X4-3(1)014表 6.10S23000X3-20116X2-31014S1100-312最大檢驗數(shù):亠 二，由最小比值 元，對主元所在列施 量爲(wèi)；：出基，非基變量 冷-二2化為1,然

6、后 他元素化為零.X 1X2X3X4常數(shù)X 3-2（2）104X 431016S-220010X 2-111202X 4401_14S'00-106至此，檢驗數(shù)均為非正數(shù)，故得基礎(chǔ)可行解/ = 0 2 0 4f.原問題的最優(yōu)解為：丄-.最優(yōu)值為6，即如果我們再迭代一次，將基變量二出基，非基變量爲(wèi)進(jìn)基（見表6.11）表 6.11X1X2X3X4常數(shù)X2-111202X4（4）0I=r14S'00-106X20138I1413X110J1S'00-106可得到另一個基礎(chǔ)可行解: :",原問題的最優(yōu)解為：.-/- : ； - .-，最優(yōu)值仍為6,說明該線性規(guī)劃問題有 無窮多最優(yōu)解，其最優(yōu)解均為亠6.'如何知道線性規(guī)劃