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

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

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

3、問題的最優(yōu)解。在第一階段已求得原問題的一個初始基本可行解的基礎上，繼續(xù)用單純形法求原問題的最優(yōu)解3單純形表與線性規(guī)劃問題的討論 無可行解 通過大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。 人工變量的值不能取零，說明了原線性規(guī)劃的數(shù)學模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時線性規(guī)劃問題的可行域為空集。4例1、求解下列線性規(guī)劃問題解：首先將問題化為標準型令，則 故引入人工變量，并利用大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)單純形表中，所有非基變量檢驗數(shù)都小于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解。6無界解 無最優(yōu)解與無可行解時兩個不同的概念。 無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指 線性規(guī)劃問題的可行域為空集； 無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目 標函數(shù)達不到最優(yōu)值，即目標函數(shù)在可行域內(nèi)可以趨于無窮大（或者無窮?。o最優(yōu)解也稱為有限最優(yōu)解，或無界解。 判別方法：無最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗 行存在某個大于零的檢驗數(shù)，但是該

6、檢驗數(shù)所對應的非基變量 的系數(shù)列向量的全部系數(shù)都為負數(shù)或零，則該線性規(guī)劃問題 無最優(yōu)解，可以可以7例2、試用單純形法求解下列線性規(guī)劃問題：解：引入松弛變量x3,x4化為標準型C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z02200因但所以原問題無最優(yōu)解8 退化解 當線性規(guī)劃問題的基本可行解中有一個或多個基變量取零值時，稱此基本可行解為退化解。 產(chǎn)生的原因：在單純形法計算中用最小比值原則確定換出變量時，有時存在兩個或兩個以上相同的最小比值，那么在下次迭代中就會出現(xiàn)一個甚至多個基變量等于零。遇到的問題：當某個基變量為零，且下次迭代以該基變量作

7、為換出變量時，目標函數(shù)并不能因此得到任何改變（由旋轉變換性質(zhì)可知，任何一個換入變量只能仍取零值，其它基變量的取值保持不變）。通過基變換以后的前后兩個退化的基本可行解的坐標形式完全相同。從幾何角度來解釋，這兩個退化的基本可行解對應線性規(guī)劃可行域的同一個頂點，解決的辦法：最小比值原則計算時存在兩個及其以上相同的最小比值時，選取下標最大的基變量為換出變量，按此方法進行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動法原理）。9例3、求解下述線性規(guī)劃問題：解：引入松弛變量化標準型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 第一次迭代中使用了攝動法原理，選擇下標為6的基變量x6離基?？傻米顑?yōu)解 ，目標函數(shù)值maxZ=，11 無窮多最優(yōu)解 無窮多最優(yōu)解判別原理：若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數(shù)都小于等于零，但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例4：最優(yōu)表：非基變量檢驗數(shù)，所以有無