三單純形法的解題步驟

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

2、數(shù)項(xiàng)與進(jìn)基變量、所對(duì)應(yīng)的列向量中正分量的比值匸最小者；%（3）換基：用進(jìn)基變量;替換出基變量從而得到新的基變量.也就是主元所在列的非基變量進(jìn)基，所在行的基變量出基；（4）利用矩陣的行初等變換，將主元變?yōu)?，其所在列其他元素都變?yōu)榱?，從此得到新的單純形表；?）回到第二步，繼續(xù)判定最優(yōu)解是否存在，然后進(jìn)行新一輪換基迭代，直到問(wè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為基變量，目標(biāo)函數(shù)已非基化了，作初始

3、單純形表并“換基迭代”（見(jiàn)表6.8）表6.8xiX2X3X4X5常數(shù)x3101005x41201010x50(1)0014S'130000x3101005X4(1)001-22X2010014S'1000-3-12x3001-123x11001-22x2010014S'000-1-1-14（3）最終結(jié)果：此時(shí)檢驗(yàn)數(shù)均為非正數(shù)，線性規(guī)劃問(wèn)題取得最優(yōu)解，最優(yōu)解為X=2430Of目標(biāo)函數(shù)取得最優(yōu)值1_.原線性規(guī)劃問(wèn)題的最優(yōu)解為：.J目標(biāo)函數(shù)的最優(yōu)值為14,即mazS二2+3x4=14.例4用單純形方法解線性規(guī)劃問(wèn)題.+r1821求一.153535*可乃+心=2一3心十兀2+才

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

5、二+.=4心(廠1234)解此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個(gè)二階單位矩陣,量，而目標(biāo)函數(shù)沒(méi)有非基化從約束方程找出代入目標(biāo)函數(shù)，經(jīng)整理得二1'，目標(biāo)函數(shù)已非基化.作單純形表，并進(jìn)行換基迭代（見(jiàn)表6.10）.法知：為主以行初等變換，基變x2進(jìn)基，先將主元X1X2X3X4常數(shù)X31-1102再將主兀所在列的其X4-3(1)014表6.10S23000X3-20116X2-31014S1100-312最大檢驗(yàn)數(shù):亠二，由最小比值元，對(duì)主元所在列施量爲(wèi)；：出基，非基變量冷-二2化為1,然后他元素化為零.X1X2X3X4常數(shù)X3-2（2）104X431016S-220010X2-111202X4401_14S'00-106至此，檢驗(yàn)數(shù)均為非正數(shù)，故得基礎(chǔ)可行解/=0204f.原問(wèn)題的最優(yōu)解為：丄-.最優(yōu)值為6，即如果我們?cè)俚淮?，將基變量二出基，非基變量?wèi)進(jìn)基（見(jiàn)表6.11）表6.11X1X2X3X4常數(shù)X2-111202X4（4）0I=r14S'00-106X20138I1413X110J1S'00-106可得到另一個(gè)基礎(chǔ)可行解:",原問(wèn)題的最優(yōu)解為：.-/-:；-.-，最優(yōu)值仍為6,說(shuō)明該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解，其最優(yōu)解均為亠6.'如何知道線性規(guī)劃問(wèn)題有無(wú)