【正文】 3, 4, 5????????????? ???47 1 0 0 0 2 6 Z 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 2 3 1 X4 X2 X3 0 2 0 3 0 2 0 0 4 Z 2 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 2 1 X4 X2 X5 0 2 0 0 0 1/2 3/2 0 5/2 Z 1/2/1/2 3/2/1/2 1 0 1/2 1/2 0 0 1 1/2 1/2 0 0 0 1/2 1/2 1 1/2 3/2 3/2 X1 X2 X5 1 2 0 x1 x2 x3 x4 x5 b XB CB θ 1 2 0 0 0 C 可得最優(yōu)解 ，目標(biāo)函數(shù)值 maxZ=6， 與用大 M法的結(jié)果完全相同。 ? ?X 0 , 3 , 1 , 2 , 0 T? ?48 ?單純形表與線性規(guī)劃問題的討論 ?無可行解 通過大Ｍ法或兩階段法求初始的基本可行解 。 但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量 ， 或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零 ， 那么該線性規(guī)劃就不存在可行解 。 人工變量的值不能取零 ， 說明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程 。 此時(shí)線性規(guī)劃問題的可行域?yàn)榭占?。 49 例 求解下列線性規(guī)劃問題 解： 首先將問題化為標(biāo)準(zhǔn)型 令 ， 則 1 2 31 2 313231 2 3m i n Z = 3 x + 2 x + xx x x 6x x 4 x x 3x ,x ,x 0? ? ????????? ??39。1 2 3 7 81 2 3 41 3 5 72 3 6 8MMm a xZ = 3x 2x x x xx + x + x + x = 6x x x + x = 4 x x x + x = 3xj 0, j=1 ,2 , 8. ?????? ??39。Z = Z故引入人工變量 ， 并利用大 M法求解 78x ,x1 2 31 2 3 41 3 52 3 639。m a xZ = 3x 2x xx +x +x +x = 6x x x =4 x x x = 3xj 0, j=1,2 , 6. ?????? ??50 C 3 2 1 0 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 θ 0 M M x4 x7 x8 6 4 3 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 6/1 3/1 Z’ 7M 64M 15M 3+M 2+M 12M 0 M M 0 0 0 M 2 x4 x7 x2 3 4 3 1 0 2 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 3/1 4/1 Z’ Z’ 3+M 0 3M 0 M 2 0 2M 3 M 2 x1 x7 x2 3 1 3 1 0 2 1 0 1 0 1 0 0 3 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 33M 3M M 1M 0 1 在以上最優(yōu)單純形表中 ， 所有非基變量檢驗(yàn)數(shù)都小于零 ， 但在該表中人工變量 x7=1為基變量 ， 所以原線性規(guī)劃不存在可行解 。 51 ?無最優(yōu)解 無最優(yōu)解與無可行解時(shí)兩個(gè)不同的概念 。 ? 無可行解是指原規(guī)劃不存在可行解 ， 從幾何的角度解釋是指 線性規(guī)劃問題的可行域?yàn)榭占? ? 無最優(yōu)解則是指線性規(guī)劃問題存在可行解 ， 但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值 ， 即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無窮大（ 或者無窮小 ） 。 無最優(yōu)解也稱為有限最優(yōu)解 ， 或無界解 。 ?判別方法： 無最優(yōu)解判別定理 在求解極大化的線性規(guī)劃問題過程中 ， 若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù) ， 但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零 ， 則該線性規(guī)劃問題 無最優(yōu)解 ， 1 1B m + k m + kX = B b B P x 1B m + k m + kZ =C B b+ σxm +k 0? ?1 m + kB P 0? m + kx ? ? ?可以 Z ? ??可以 52 例 試用單純形法求解下列線性規(guī)劃問題： 解：引入松弛變量 x3,x4化為標(biāo)準(zhǔn)型 12121212m a x Z = 2 x + 2 x x x 11 x x 22x 0 ,x 0????????????121 2 31 2 4jm a xZ = 2x + 2x x x x 11 x x + x 22x 0, j 1, 2, 3, 4? ? ????????????C 2 2 0 0 θ C XB B x1 x2 x3 x4 0 X3 1 1 1 1 0 0 X4 2 1/2 1 0 1 Z 0 2 2 0 0 1= 20?因 但 所以原問題 無最優(yōu)解 11P = 012?????????53 ? 退化解 當(dāng)線性規(guī)劃問題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí) ，稱此基本可行解為退化解 。 ? 產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí) ，有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值 θ， 那么在下次迭代中就會(huì)出現(xiàn)一個(gè)甚至多個(gè)基變量等于零 。 ?遇到的問題：當(dāng)某個(gè)基變量為零 ， 且下次迭代以該基變量作為換出變量時(shí) ， 目標(biāo)函數(shù)并不能因此得到任何改變 （ 由旋轉(zhuǎn)變換性質(zhì)可知 ， 任何一個(gè)換入變量只能仍取零值 ， 其它基變量的取值保持不變 ） 。 通過基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同 。 從幾何角度來解釋 ， 這兩個(gè)退化的基本可行解對(duì)應(yīng)線性規(guī)劃可行域的同一個(gè)頂點(diǎn) ， ?解決的辦法：最小比值原則計(jì)算時(shí)存在兩個(gè)及其以上相同的最小比值時(shí) ， 選取下標(biāo)最大的基變量為換出變量 ， 按此方法進(jìn)行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生 （ 攝動(dòng)法原理 ） 。 54 例 求解下述線性規(guī)劃問題： 解： 引入松弛變量 化標(biāo)準(zhǔn)型 1 2 3 41 2 3 41 2 3 4 3jm a xZ =3x 80x +2x 24xx 32x 4x 36x 0x 24x x 6x 0 x 1 x 0,j 1,2,3, 4??????????? ??? 1 2 3 41 2 3 4 51 2 3 4 637jm a xZ = 3x 80 x + 2x 24 xx 32 x 4x 36 x x 0x 24 x x 6 x x 0 x x 1 x 0, j 1, 2, 3, 4, 5, 6, 7? ? ???? ? ??????? ???5 6 7x ,x ,x55 0 0 0 24 2 80 3 0 Z 5 6 0 42 0 8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 24 1 1 x1 3 3 2 1 30 0 8 0 3 x5 0 0 3 0 42 5 8 0 0 Z 1 1 0 0 1 0 0 1 x7 0 0 1 0 6 1 24 1 0 x1 3 0 1 1 30 3 8 0 0 x5 0 1 1 0 0 1 0 0 1 x7 0 0 0 1 0 6 1 24 1 0 x6 0 0 0 0 1 36 4 32 1 0 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 0 0 0 24 2 80 3 C θ 第一次迭代中使用了攝動(dòng)法原理 ， 選擇下標(biāo)為 6的基變量 x6離基 。 可得最優(yōu)解 ，目標(biāo)函數(shù)值 maxZ=５， ? ?X 1 , 0 , 1 , 0 , 3 T? ?56 ? 無窮多最優(yōu)解 無窮多最優(yōu)解判別原理： 若線性規(guī)劃問題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零 ，但其中存在一個(gè)檢驗(yàn)數(shù)等于零 ， 那么該線性規(guī)劃問題有無窮多最優(yōu)解 。 例３：最優(yōu)表： 非基變量檢驗(yàn) 數(shù) ， 所以有無窮多 最優(yōu)解。 最優(yōu)解集為可行域兩個(gè)頂點(diǎn)的凸組合： C 1 2 0 0 0 θ CB XB b x1 x2 x3 x4 x5 0 2 1 x3 x2 x1 2 3 2 0 0 1 2 1 0 1 0 1 0 1 0 0 2 1 2/2 3/1 Z’ 8 0 0 0 0 1 4= 0?? ?X ( 2 , 3 , 2 , 0 , 0 ) ( 1 ) 4 , 2 , 0 , 1 , 0 , 0 1 .TT? ? ?? ? ? ? ? ?57 ?改進(jìn)單純形法的特點(diǎn) 利用單純形表求解線性規(guī)劃時(shí) ， 每一次迭代都把整個(gè)單純形表計(jì)算一遍 ， 事實(shí)上我們關(guān)心的只是以下一些數(shù)據(jù)： ?基本可行解 ， 其相應(yīng)的目標(biāo)函數(shù)值 ， ?非基變量檢驗(yàn)數(shù) ， 及其換入變量