單純形法的解題步驟

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

2、大正檢驗(yàn)數(shù) 人 所在列，用常數(shù)項(xiàng) 4Q = 12閱 與進(jìn)基變量 力所對應(yīng)的列向 be量中正分量的比值 最小者；口或(3)換基：用進(jìn)基變量先替換出基變量 白,從而得到新的基變量.也就是主元所在列的非基變量進(jìn)基，所在行的基變量出基；(4)利用矩陣的行初等變換，將主元變?yōu)?,其所在列其他元素都變?yōu)榱?，從此得到新的單純形表?5)回到第二步，繼續(xù)判定最優(yōu)解是否存在，然后進(jìn)行新一輪換基迭代，直到問題得 到解決為止.例 3 求 max S = a + 3x解（1）化標(biāo)準(zhǔn)型：令 s'二y ,引進(jìn)松弛變量 為 Q網(wǎng) 。,公之0,其標(biāo)準(zhǔn)型為金+工三=5Xj + 2 盯 +1*-10Xq +x = 4打之

3、 0。二 123,4。）（2）作單純形表：在約束方程組系數(shù)矩陣中句, &的系數(shù)構(gòu)成單位矩陣，故取匹力向?yàn)榛兞浚繕?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é)果：此時檢驗(yàn)數(shù)均為非正數(shù)，線性規(guī)劃問題取得最優(yōu)解，最優(yōu)解為X = 2 4 3 0 Of目標(biāo)函數(shù)取得最優(yōu)值二 1-

4、.原線性規(guī)劃問題的最優(yōu)解為：用二2,5=4 .目標(biāo)函數(shù)的最優(yōu)值為14,即 一 二：例4用單純形方法解線性規(guī)劃問題 .仃 1821求 _ -_ -.1、2 行，3、4解 此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了，其中約束方程含有一個二階單位矩陣（列構(gòu)成），取 工j可為基變量，而目標(biāo)函數(shù)沒有非基化 .從約束方程找出窗=2一 a +陽，a =4+Mf,代入目標(biāo)函數(shù)02,經(jīng)整理后，目標(biāo)函數(shù)非基化了作單純形表，并進(jìn)行換基迭代（見表6.9）.最大檢驗(yàn)數(shù) = 3,由最小比值法知：的?二1為主元，對主元所在列施以行初等變換，基變量 工出基，非基變量 內(nèi)進(jìn)基.表6.9X1X2X3X4常數(shù)X31-1102X4-3(1)014S23

5、000X3-20116X2-31014S1100-312目前最大檢驗(yàn)數(shù) 1=11 ,其所在列沒有正分量，所以該線TIe規(guī)劃問題沒有最優(yōu)解例5用單純形方法解線性規(guī)劃問題 .求二.I. +. +-24 + 2勺 + x3= 4s.L< 3/ + x2 + a4 = 6勺之 0(J = 123,4)kJ解 此數(shù)學(xué)模型已是標(biāo)準(zhǔn)型了， 其中約束方程含有一個二階單位矩陣， 取 網(wǎng)J %為基變 量，而目標(biāo)函數(shù)沒有非基化.從約束方程找出網(wǎng)=4 + 2可- 2% , a=6- 3瓦-馬,代入目標(biāo)函數(shù)，經(jīng)整理得'T-：< 11",目標(biāo)函數(shù)已非基化作單純形表，并進(jìn)行換基迭代（見表6.1

6、0）.最大檢驗(yàn)數(shù)= 2,由最小比值法知：= 2為主元，對主元所在列施以行初等變換，基變量 也出基,非基變量X2進(jìn)基，先將主元 口心二2化為1,然后再將主元所在列的 其他元素化為零一.一表 6.10X 1X2X3X4常數(shù)X 3-2(2)104X 431016S-220010X 2-11 202X 4401-另14S'00-106至此，檢驗(yàn)數(shù)均為非正數(shù)，故得基礎(chǔ)可行解/ = 0 2 0 4.原問題的最優(yōu)解為：. .最優(yōu)值為 6,即 mmS=3xO+2+0+4=6.如果我們再迭代一次，將基變量工出基，非基變量進(jìn)基（見表6.11）表 6.11X1X2X3X4常數(shù)X2-111022X4(4)01=14S'00-106X201J1384X110111一,<S'00106可得到另一個基礎(chǔ)可行解二，原問題的最優(yōu)解為：否二1再= 3j3 = 0j4 = 0,最優(yōu)值仍為6,說明該線性規(guī)劃問題有無窮多最優(yōu)解，其最優(yōu)解均為 .一如何知道線性規(guī)