單純形法大M法求解線性規(guī)劃問(wèn)題

1、班級(jí)：物流113 隊(duì)員：陳祥娟 馮雪萍 張獻(xiàn)獻(xiàn) 李起平線性規(guī)劃各種解的情況1 大M法 大M法首先將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。 為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。 以后的計(jì)算與單純形表解法相

2、同，只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問(wèn)題的初始基本可行解。2兩階段法 兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟： 求解一個(gè)輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化；約束條件為原問(wèn)題中引入人工變量后包含一個(gè)單位矩陣的標(biāo)準(zhǔn)型的約束條件。 如果輔助線性規(guī)劃存在一個(gè)基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問(wèn)題已經(jīng)得了一個(gè)初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計(jì)算；否則說(shuō)明原問(wèn)題沒(méi)有可行解，可停止計(jì)算。 求原

3、問(wèn)題的最優(yōu)解。在第一階段已求得原問(wèn)題的一個(gè)初始基本可行解的基礎(chǔ)上，繼續(xù)用單純形法求原問(wèn)題的最優(yōu)解3單純形表與線性規(guī)劃問(wèn)題的討論 無(wú)可行解 通過(guò)大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。 人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占?例1、求解下列線性規(guī)劃問(wèn)題解：首先將問(wèn)題化為標(biāo)準(zhǔn)型令，則 故引入人工變量，并利用大M法求解5C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x

4、3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6/1-3/1 Z -7M -6-4M -15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1- Z Z -3+M 0 -3-M 0 -M -2 0 2-M -3-M-2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1

5、 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 在以上最優(yōu)單純形表中，所有非基變量檢驗(yàn)數(shù)都小于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解。6無(wú)界解 無(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ù)，但是該

6、檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量 的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題 無(wú)最優(yōu)解，可以可以7例2、試用單純形法求解下列線性規(guī)劃問(wèn)題：解：引入松弛變量x3,x4化為標(biāo)準(zhǔn)型C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z02200因但所以原問(wèn)題無(wú)最優(yōu)解8 退化解 當(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è)基變量為零，且下次迭代以該基變量作

7、為換出變量時(shí)，目標(biāo)函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可知，任何一個(gè)換入變量只能仍取零值，其它基變量的取值保持不變）。通過(guò)基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同。從幾何角度來(lái)解釋?zhuān)@兩個(gè)退化的基本可行解對(duì)應(yīng)線性規(guī)劃可行域的同一個(gè)頂點(diǎn)，解決的辦法：最小比值原則計(jì)算時(shí)存在兩個(gè)及其以上相同的最小比值時(shí)，選取下標(biāo)最大的基變量為換出變量，按此方法進(jìn)行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動(dòng)法原理）。9例3、求解下述線性規(guī)劃問(wèn)題：解：引入松弛變量化標(biāo)準(zhǔn)型10000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 0

8、0-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代中使用了攝動(dòng)法原理，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解 ，目標(biāo)函數(shù)值maxZ=，11 無(wú)窮多最優(yōu)解 無(wú)窮多最優(yōu)解判別原理：若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。例4：最優(yōu)表：非基變量檢驗(yàn)數(shù)，所以有無(wú)