【導(dǎo)讀】單純形法的一般原理。借助人工變量求初始的基本可行解。單純形表與線性規(guī)劃問(wèn)題的討論。向量，Ｃ為n維行向量，Ｘ為n維列向量。如果可行域Ｄ={Ｘ∈Ｒn/ＡＸ=ｂ，Ｘ≥0}非空有界，則Ｄ上的最優(yōu)目標(biāo)函數(shù)值Ｚ=ＣＸ一定可以在Ｄ的一個(gè)頂點(diǎn)上達(dá)到。這個(gè)重要的定理啟發(fā)了Dantzig的單純形法，即將尋優(yōu)的目標(biāo)集中在D的各個(gè)頂點(diǎn)上。最優(yōu)基本可行解的最佳途徑。檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解，然后轉(zhuǎn)會(huì)到步驟。Ｂ=（Ｐ1，Ｐ2，…Ｐm）為基變量x1，x2，…Ｎ=(Ｐm+1，Pm+2，…Pn)為非基變量xm+1，xm+2，…系數(shù)列向量構(gòu)成的矩陣。因?yàn)椴荒鼙ＷC基變量ＸB=Ｂ-1b≥0。為了求得基本可行解，必須求基Ｂ的逆陣Ｂ-1。但是求逆陣Ｂ-1也是一件麻煩的事。若在化標(biāo)準(zhǔn)形式前，約束方程中有“≥”不等式，的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。因此當(dāng)由零增至正值，最大限度的增加。

　　

【正文】 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ī)劃問(wèn)題的討論 ?無(wú)可行解 通過(guò)大Ｍ法或兩階段法求初始的基本可行解 。 但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量 ， 或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零 ， 那么該線性規(guī)劃就不存在可行解 。 人工變量的值不能取零 ， 說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程 。 此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占?。 49 例 求解下列線性規(guī)劃問(wèn)題 解： 首先將問(wèn)題化為標(biāo)準(zhǔn)型 令 ， 則 1 2 31 2 313231 2 3m inZ =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 x Z = 3 x 2 x x x xx + x + x + x = 6x x x + x = 4 x x x + x = 3x j 0 , j= 1 ,2 , 8 . ?????? ??39。Z = Z故引入人工變量 ， 并利用大 M法求解 78x ,x1 2 31 2 3 41 3 52 3 639。m a x Z = 3 x 2 x xx +x +x +x = 6x x x =4 x x x =3x j 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 ?無(wú)最優(yōu)解 無(wú)最優(yōu)解與無(wú)可行解時(shí)兩個(gè)不同的概念 。 ? 無(wú)可行解是指原規(guī)劃不存在可行解 ， 從幾何的角度解釋是指 線性規(guī)劃問(wèn)題的可行域?yàn)榭占? ? 無(wú)最優(yōu)解則是指線性規(guī)劃問(wèn)題存在可行解 ， 但是可行解的目 標(biāo)函數(shù)達(dá)不到最優(yōu)值 ， 即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（ 或者無(wú)窮小 ） 。 無(wú)最優(yōu)解也稱為有限最優(yōu)解 ， 或無(wú)界解 。 ?判別方法： 無(wú)最優(yōu)解判別定理 在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中 ， 若某單純形表的檢驗(yàn) 行存在某個(gè)大于零的檢驗(yàn)數(shù) ， 但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零 ， 則該線性規(guī)劃問(wèn)題 無(wú)最優(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ī)劃問(wèn)題： 解：引入松弛變量 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?因 但 所以原問(wèn)題 無(wú)最優(yōu)解 11P = 012?????????53 ? 退化解 當(dāng)線性規(guī)劃問(wèn)題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí) ，稱此基本可行解為退化解 。 ? 產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí) ，有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值 θ， 那么在下次迭代中就會(huì)出現(xiàn)一個(gè)甚至多個(gè)基變量等于零 。 ?遇到的問(wèn)題：當(dāng)某個(gè)基變量為零 ， 且下次迭代以該基變量作為換出變量時(shí) ， 目標(biāo)函數(shù)并不能因此得到任何改變 （ 由旋轉(zhuǎn)變換性質(zhì)可知 ， 任何一個(gè)換入變量只能仍取零值 ， 其它基變量的取值保持不變 ） 。 通過(guò)基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同 。 從幾何角度來(lái)解釋 ， 這兩個(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ī)劃問(wèn)題： 解： 引入松弛變量 化標(biāo)準(zhǔn)型 1 2 3 41 2 3 41 2 3 4 3jm a xZ = 3x 80 x + 2x 24 xx 32 x 4x 36 x 0x 24 x 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 ? 無(wú)窮多最優(yōu)解 無(wú)窮多最優(yōu)解判別原理： 若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零 ，但其中存在一個(gè)檢驗(yàn)數(shù)等于零 ， 那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解 。 例３：最優(yōu)表： 非基變量檢驗(yàn) 數(shù) ， 所以有無(wú)窮多 最優(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ù) ， 及其換入變量 ， 設(shè) 主元列元素 ， 及其換出變量 ， 設(shè) 利用它們可得到一組新的基變量以及新的可行基Ｂ 1。 111iki 1 1k i k( B b )( B b )m in /(