單純形法解題步驟

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è)為，并確定 所在列的非基變量 為進(jìn)基變量 .（ 2）對(duì)最大正檢驗(yàn)數(shù)所在列實(shí)施最小比值法，確定出主元，并把主元加上小括號(hào)主

2、元是最大正檢驗(yàn)數(shù) 所在列， 用常數(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） 化標(biāo)準(zhǔn)型：令，引進(jìn)松弛變量 ，其標(biāo)準(zhǔn)型為（ 2） 作單純形表：在約束方程組系數(shù)矩陣中的系數(shù)構(gòu)成單位矩陣，故取為基變量，目標(biāo)函數(shù)已非基化了，作初始單純形表并“換基迭代” （見(jiàn)表 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） 最終結(jié)果：此時(shí)檢驗(yàn)數(shù)均為非正數(shù)，線性規(guī)劃問(wèn)題取得最優(yōu)解，最優(yōu)解為目x1x2x3x4常數(shù)原線x31-1102目標(biāo)x4-3(1)014S23000題.x3-20116x2-31014S1100-312標(biāo)函數(shù)取得最優(yōu)值 .性規(guī)劃問(wèn)題的最優(yōu)解為： . 函 數(shù) 的 最 優(yōu) 值 為 14 ， 即.例 4 用單純形方法解線性規(guī)劃問(wèn)1、2 行，

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

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