單純形法的解題步驟

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

2、到最大正檢驗(yàn)數(shù)，設(shè)為，并確定所在列的非基變量為進(jìn)基變量.（2）對最大正檢驗(yàn)數(shù)所在列實(shí)施最小比值法，確定出主元，并把主元加上小括號.主元是最大正檢驗(yàn)數(shù)所在列，用常數(shù)項(xiàng)與進(jìn)基變量所對應(yīng)的列向量中正分量的比值最小者；（3）換基：用進(jìn)基變量替換出基變量，從而得到新的基變量.也就是主元所在列的非基變量進(jìn)基，所在行的基變量出基；（4）利用矩陣的行初等變換，將主元變?yōu)?，其所在列其他元素都變?yōu)榱?，從此得到新的單純形表；?）回到第二步，繼續(xù)判定最優(yōu)解

3、是否存在，然后進(jìn)行新一輪換基迭代，直到問題得到解決為止.例3求.（3）最終結(jié)果：此時(shí)檢驗(yàn)數(shù)均為非正數(shù)，線性規(guī)劃問題取得最優(yōu)解，最優(yōu)解為目標(biāo)函數(shù)取得最優(yōu)值.原線性規(guī)劃問題的最優(yōu)解為：.目標(biāo)函數(shù)的最優(yōu)值為14，即.例4用單純形方法解線性規(guī)劃問題.求.解此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個(gè)二階單位矩陣（1、2行，3、4列構(gòu)成），取為基變量，而目標(biāo)函數(shù)沒有非基化.從約束方程找出，代入目標(biāo)函數(shù)經(jīng)整理后，目標(biāo)函數(shù)非基化了.作單純形表，并進(jìn)行