第5章 單純形法

1、管管 理理 運運 籌籌 學學1第五章第五章 單單 純純 形形 法法n1 單純形法的基本思路和原理單純形法的基本思路和原理n2 單純形法的表格形式單純形法的表格形式n3 求目標函數(shù)值最小的線性規(guī)劃的問題的求目標函數(shù)值最小的線性規(guī)劃的問題的 單純形表解法單純形表解法n4 幾種特殊情況幾種特殊情況管管 理理 運運 籌籌 學學21 單純形法的基本思路和原理單純形法的基本思路和原理 基礎(chǔ)知識準備基礎(chǔ)知識準備 1、單純形法的基本思路：、單純形法的基本思路： 從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是,則再找另一個使得則再找另一個使得其目

2、標函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解。直到找到一個頂點其目標函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解。直到找到一個頂點為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。止。 通過第二章例通過第二章例1的求解來介紹單純形法的求解來介紹單純形法: 在加上松弛變量之后我們可得到標準型如下：在加上松弛變量之后我們可得到標準型如下： 目標函數(shù)：目標函數(shù)： max z= 50 x1+100 x2 約束條件：約束條件：x1+x2+s1300 2x1+x2+s2400 x2+

3、s3250. xj0 （j=1，2）,sj0 （j=1，2,3）1 單純形法的基本思路和原理單純形法的基本思路和原理管管 理理 運運 籌籌 學學3它的系數(shù)矩陣它的系數(shù)矩陣 , 其中其中pj為系數(shù)矩陣為系數(shù)矩陣A第第j列的向量。列的向量。A的秩為的秩為3,A的秩的秩m小于此方程組的小于此方程組的變變量的個數(shù)量的個數(shù)n，為了找到一個初始基本可行解，先介紹以下幾個線性規(guī)劃的，為了找到一個初始基本可行解，先介紹以下幾個線性規(guī)劃的基本概念?；靖拍?。100100101200111),(54321pppppA管管 理理 運運 籌籌 學學4 B管管 理理 運運 籌籌 學學5管管 理理 運運 籌籌 學學6nm

4、n1n1m1mm11mm1mmm1m2m2121m111xaa-xaa-bbxaaxaaxaam1nmn1n1m1mm11mmmm1m2m2121m111bbxaaxaaxaaxaaxaa管管 理理 運運 籌籌 學學7mn管管 理理 運運 籌籌 學學8管管 理理 運運 籌籌 學學9在此例中我們不妨找到了在此例中我們不妨找到了 為為A的一個基，的一個基，令這個基的非基變量令這個基的非基變量x，s2為零。這時約束方程就變?yōu)榛兞康募s束方程為零。這時約束方程就變?yōu)榛兞康募s束方程：x2+s1300 x2=400 x2+s3=250. 求解得到此線性規(guī)劃的一個基本解：求解得到此線性規(guī)劃的一個基本解：x

5、1=0，x2=400，s1=100，s2=0，s3=150 由于在這個基本解中由于在這個基本解中s1=100，s3=150，不滿足該線性規(guī)劃，不滿足該線性規(guī)劃s10，s30的約束條件，顯然不是此線性規(guī)劃的可行解，的約束條件，顯然不是此線性規(guī)劃的可行解，一個基本解可以是可行一個基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足非負的條件。非負的條件。我們把滿足非負條件的一個基本解叫做基本可行解，并把這樣我們把滿足非負條件的一個基本解叫做基本可行解，并把這樣的基叫做可行基。的基叫做可行基。 10100

6、10113B管管 理理 運運 籌籌 學學10管管 理理 運運 籌籌 學學11管管 理理 運運 籌籌 學學12n x x1 1 , x, x2 2 , , x x3 3, x, x4 4 , , x x5 5 00管管 理理 運運 籌籌 學學13100400100400121100010001管管 理理 運運 籌籌 學學14T T管管 理理 運運 籌籌 學學15管管 理理 運運 籌籌 學學16， 管管 理理 運運 籌籌 學學172 2 1 14x4x5 5管管 理理 運運 籌籌 學學18管管 理理 運運 籌籌 學學193 3nX X(3)(3) = ( 4, 2, 0, 0, 4 ) = ( 4

7、, 2, 0, 0, 4 ) T T (4,2) (4,2) Q Q2 2管管 理理 運運 籌籌 學學20管管 理理 運運 籌籌 學學21管管 理理 運運 籌籌 學學22 一般來說判斷一個基是否是可行基，只有在求出其基本解以后，當其基本解一般來說判斷一個基是否是可行基，只有在求出其基本解以后，當其基本解所有變量的解都是大于等于零，才能斷定這個解是基本可行解，這個基是可行所有變量的解都是大于等于零，才能斷定這個解是基本可行解，這個基是可行基?；?。那么我們能否在求解之前，就找到一個可行基呢？那么我們能否在求解之前，就找到一個可行基呢？也就是說我們找到的一個也就是說我們找到的一個基能保證在求解之后得

8、到的解一定是基本可行解呢？由于在線性規(guī)劃的標準型中基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標準型中要求要求bj都大于等于零，如果我們能找到一個基是單位矩陣，或者說一個基是由單都大于等于零，如果我們能找到一個基是單位矩陣，或者說一個基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如，位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如，那么顯然所求得的基本解一定是基本可行解，這個單位矩陣或由單位矩陣各列向那么顯然所求得的基本解一定是基本可行解，這個單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實際上這個基本可行解中的各個變量或等于某

9、個量組成的基一定是可行基。實際上這個基本可行解中的各個變量或等于某個bj或或等于零。等于零。 010001100一、找到一個初始基本可行解一、找到一個初始基本可行解管管 理理 運運 籌籌 學學23 在本例題中我們就找到了一個基是單位矩陣。在本例題中我們就找到了一個基是單位矩陣。 在第一次找可行基時，所找到的基或為單位矩陣或為由單位矩陣的各在第一次找可行基時，所找到的基或為單位矩陣或為由單位矩陣的各列向量所組成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行列向量所組成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行解。如果

10、找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細講述?；?，我們將構(gòu)造初始可行基，具體做法在以后詳細講述。1000100012B管管 理理 運運 籌籌 學學24 所謂最優(yōu)性檢驗就是判斷已求得的基本可行解是否是最優(yōu)解。所謂最優(yōu)性檢驗就是判斷已求得的基本可行解是否是最優(yōu)解。1. 最優(yōu)性檢驗的依據(jù)最優(yōu)性檢驗的依據(jù)檢驗數(shù)檢驗數(shù)j 一般來說目標函數(shù)中既包括基變量，又包括非基變量。現(xiàn)在我們要求一般來說目標函數(shù)中既包括基變量，又包括非基變量?，F(xiàn)在我們要求只用非基變量來表示目標函數(shù)，這只要在約束等式中通過移項等處理就可只用非基變量來表示目標函數(shù)，這只要在約束等

11、式中通過移項等處理就可以用非基變量來表示基變量，然后用非基變量的表示式代替目標函數(shù)中基以用非基變量來表示基變量，然后用非基變量的表示式代替目標函數(shù)中基變量，這樣目標函數(shù)中只含有非基變量了，或者說目標函數(shù)中基變量的系變量，這樣目標函數(shù)中只含有非基變量了，或者說目標函數(shù)中基變量的系數(shù)都為零了。此時目標函數(shù)中所有變量的系數(shù)即為各變量的檢驗數(shù)，把變數(shù)都為零了。此時目標函數(shù)中所有變量的系數(shù)即為各變量的檢驗數(shù)，把變量量xi的檢驗數(shù)記為的檢驗數(shù)記為i。顯然所有基變量的檢驗數(shù)必為零。顯然所有基變量的檢驗數(shù)必為零。在本例題中目標在本例題中目標函數(shù)為函數(shù)為50 x1+100 x2。由于初始可行解中。由于初始可行解

12、中x1，x2為非基變量，所以此目標函為非基變量，所以此目標函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知1=50，2=100，3=0，4=0，5=0。二、二、 最優(yōu)性檢驗最優(yōu)性檢驗管管 理理 運運 籌籌 學學25jn1mjijiixa-bxjijm1iin1mjjim1iix)ac-(cbcz管管 理理 運運 籌籌 學學26n1mjjjj0 x)z-(czzm1iijijjjjac-cz-cn1mjjj0 xzz管管 理理 運運 籌籌 學學27j j，nm+km+k0，則則LP有無窮多最優(yōu)解。有無窮多最優(yōu)解。管管 理理

13、 運運 籌籌 學學28管管 理理 運運 籌籌 學學29判斷最優(yōu)解的基本過程初始基本可行解初始基本可行解j 0 ? ?結(jié)束結(jié)束找新的基本可行解找新的基本可行解NYYN是否為是否為無界解？無界解？唯一最優(yōu)解唯一最優(yōu)解無無窮窮多最優(yōu)解多最優(yōu)解管管 理理 運運 籌籌 學學30n2.最優(yōu)解判別定理最優(yōu)解判別定理 對于求最大目標函數(shù)的問題中對于求最大目標函數(shù)的問題中，對于某個基本可行，對于某個基本可行解，如果所有檢驗數(shù)解，如果所有檢驗數(shù) 0，則這個基本可行解是最優(yōu)，則這個基本可行解是最優(yōu)解。解。下面我們用通俗的說法來解釋最優(yōu)解判別定理。設(shè)用下面我們用通俗的說法來解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標函

14、數(shù)為如下形式非基變量表示的目標函數(shù)為如下形式 由于所有的由于所有的xj的取值范圍為大于等于零，當所有的的取值范圍為大于等于零，當所有的 都都小于等于零時，可知小于等于零時，可知 是一個小于等于零的數(shù)，是一個小于等于零的數(shù)，要使要使z的值最大，顯然的值最大，顯然 只有為零。我們把這些只有為零。我們把這些xj取為非基變量取為非基變量(即令這些即令這些xj的值為零的值為零)，所求得的基本可，所求得的基本可行解就使目標函數(shù)值最大為行解就使目標函數(shù)值最大為z0。*對于求目標函數(shù)最小值的情況，只需把對于求目標函數(shù)最小值的情況，只需把 0改為改為 0j0jjjJzzxjjjj Jxjjj Jxjj管管 理理

15、 運運 籌籌 學學31三、三、 基變換基變換 通過檢驗，我們知道這個初始基本可行解不是最優(yōu)解。下面介紹如何進通過檢驗，我們知道這個初始基本可行解不是最優(yōu)解。下面介紹如何進行基變換找到一個新的可行基，具體的做法是從可行基中換一個列向量，行基變換找到一個新的可行基，具體的做法是從可行基中換一個列向量，得到一個新的可行基，使得求解得到的新的基本可行解，其目標函數(shù)值得到一個新的可行基，使得求解得到的新的基本可行解，其目標函數(shù)值更優(yōu)。更優(yōu)。為了換基就要確定換入變量與換出變量。為了換基就要確定換入變量與換出變量。管管 理理 運運 籌籌 學學321. 入基變量的確定入基變量的確定 從最優(yōu)解判別定理知道，當某

16、個從最優(yōu)解判別定理知道，當某個j0時，非基變量時，非基變量xj變?yōu)榛兞坎蛔優(yōu)榛兞坎蝗×阒悼梢允鼓繕撕瘮?shù)值增大，故我們?nèi)×阒悼梢允鼓繕撕瘮?shù)值增大，故我們要選基檢驗數(shù)大于要選基檢驗數(shù)大于0的非基變的非基變量換到基變量中去（稱之為入基變量）。量換到基變量中去（稱之為入基變量）。若有兩個以上的若有兩個以上的j0，則，則為了使目標函數(shù)增加得更大些，為了使目標函數(shù)增加得更大些，一般選其中的一般選其中的j最大者的非基變量為最大者的非基變量為入基變量，在本例題中入基變量，在本例題中2=100是檢驗數(shù)中最大的正數(shù)，故選是檢驗數(shù)中最大的正數(shù)，故選x2為入為入基變量?；兞俊若有兩個以上的若有兩個以上的j0，

17、n1mjjj0 xzzkjj0)x(aM管管 理理 運運 籌籌 學學33管管 理理 運運 籌籌 學學34 我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項的值，程中的正的系數(shù)除以其所在約束方程中的常數(shù)項的值，把其中最小比值所把其中最小比值所在的約束方程中的原基變量確定為出基變量。在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變這樣在下一步迭代的矩陣變換中可以確保新得到的換中可以確保新得到的bj值都大于等于零。值都大于等于零。 在本例題中約束方程為在本例題中約束方

18、程為 在第二步中已經(jīng)知道在第二步中已經(jīng)知道x2為入基變量，我們把各約束方程中為入基變量，我們把各約束方程中x2的為正的系數(shù)除的為正的系數(shù)除對應(yīng)的常量，得對應(yīng)的常量，得121122233 0 0,24 0 0,2 5 0 .xxsxxsxs3121 22 23 23 0 04 0 02 5 03 0 0,4 0 0,2 5 0 .111bbbaaa管管 理理 運運 籌籌 學學35 其中其中 的值最小，所以可以知道在原基變量中系數(shù)向量為的值最小，所以可以知道在原基變量中系數(shù)向量為 的基變量的基變量s3為出基變量，這樣可知為出基變量，這樣可知x2，s1，s2為基變量，為基變量，x1，s3為非基為非基

19、變量。變量。 令非基變量為零，得令非基變量為零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的基本可行解求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150. 這時目標函數(shù)值為這時目標函數(shù)值為 50 x1+100 x2=500+100250=25000。 顯然比初始基本可行解顯然比初始基本可行解x1=0,x2=0,s1=300,s3=250時的目標函時的目標函數(shù)值為數(shù)值為0要好得多。要好得多。 下面我們再進行檢驗其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進行基變下面我們再進行檢驗其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進行基變換，直至找到最優(yōu)解，或者能夠判斷出線性

20、規(guī)劃無最優(yōu)解為止。換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無最優(yōu)解為止。33 2ba30,0,1Te 管管 理理 運運 籌籌 學學362 單純形法的表格形式單純形法的表格形式 上面假設(shè)上面假設(shè)x1,x2,xm是基變量，即第是基變量，即第i行約束方程的基變量正好是行約束方程的基變量正好是xi，而經(jīng)過迭代后，基將發(fā)生變化，計算而經(jīng)過迭代后，基將發(fā)生變化，計算zj的式子也會發(fā)生變化。如果迭代的式子也會發(fā)生變化。如果迭代后的第后的第i行約束方程中的基變量為行約束方程中的基變量為xBi，與，與xBi相應(yīng)的目標函數(shù)系數(shù)為相應(yīng)的目標函數(shù)系數(shù)為cBi，系數(shù)列向量為系數(shù)列向量為 則則 其中，其中，(cB)是由

21、第是由第1列第列第m行各約束方程中的基變量相應(yīng)的目標函數(shù)行各約束方程中的基變量相應(yīng)的目標函數(shù)依次組成的有序行向量。依次組成的有序行向量。 單純形法的表格形式是把用單純形法求出基本可行解、檢驗其最優(yōu)性、單純形法的表格形式是把用單純形法求出基本可行解、檢驗其最優(yōu)性、迭代某步驟都用表格的方式來計算求出，其表格的形式有些像增廣矩陣，迭代某步驟都用表格的方式來計算求出，其表格的形式有些像增廣矩陣，而其計算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格而其計算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解第二章的例來求解第二章的例1。 max 50 x1+100 x2+0s1+0s2

22、+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的數(shù)據(jù)填入如下的單純形表格把上面的數(shù)據(jù)填入如下的單純形表格1, 2,jpjn1,jBBmjBjzccpcp管管 理理 運運 籌籌 學學372 單純形法的表格形式單純形法的表格形式n按照線性規(guī)劃模型在表中填入相對應(yīng)的值，如上表所示；按照線性規(guī)劃模型在表中填入相對應(yīng)的值，如上表所示；n在上表中有一個在上表中有一個m*m的單位矩陣，對應(yīng)的基變量為的單位矩陣，對應(yīng)的基變量為s1,s2,s3；n在在zj行中填入第行中填入第j列與列與cB列中對應(yīng)的元素相乘相加所得的值

23、，如列中對應(yīng)的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在，所在zi行中的第行中的第2位數(shù)填入位數(shù)填入0；n在在 行中填入行中填入cj-zj所得的值，如所得的值，如 ；nz表示把初始基本可行解代入目標函數(shù)求得的目標函數(shù)值，即表示把初始基本可行解代入目標函數(shù)求得的目標函數(shù)值，即b列列*cB列；列；n初始基本可行解為初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0;n由于由于 ，因此確定，因此確定x2為入基變量。為入基變量。n由于由于250/1最小，因此確定最小，因此確定s3為出基變量；為出基變量；n出基變量所在行，入基變量所在列的交匯處為出基變量所在

24、行，入基變量所在列的交匯處為主元主元，這里是，這里是a32=1，在表中畫，在表中畫圈以示區(qū)別。圈以示區(qū)別。jjjcz迭代次數(shù)基變量 cB x1 x2 s1 s2 s3 b比值Bi/ai2 50 100 0 0 00 s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1300400250300/1400/1250/1 zj 0 0 0 0 0 50 100 0 0 0z=0jjjcz15 005 0210選最小值所在的行選正數(shù)且最大值所在的列基變量的系數(shù)cB對應(yīng)乘以b，求和為z管管 理理 運運 籌籌 學學382 單純形法的表格形式單純形法的表格形式n以下進行第

25、一次迭代，其變量為以下進行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向的系數(shù)向量量p2變換成單位向量，由于主元在變換成單位向量，由于主元在p2的第的第3 分量上，所以這個單位向分量上，所以這個單位向量是量是 也就是主元素變成也就是主元素變成1。這樣我們又得到的第。這樣我們又得到的第1次迭代的次迭代的單純表如下所示。單純表如下所示。n在上表中第在上表中第3個基變量個基變量s1已被已被x2代替，故基變量列中的第代替，故基變量列中的第3個基變量應(yīng)個

26、基變量應(yīng)變?yōu)樽優(yōu)閤2。由于第。由于第0次迭代表中的主元次迭代表中的主元a32已經(jīng)為已經(jīng)為1，因此第，因此第3行不變。為行不變。為了使第了使第1行的行的a12為為0，只需把第，只需把第3行行*(-1)加到第加到第1行即可。同樣可以行即可。同樣可以求得第求得第2行。行。n求得第求得第1次迭代的基本可行解為次迭代的基本可行解為s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.30, 0,1Tejjjcz迭代次數(shù)基變量 cB x1 x2 s1 s2 s3 b 比值 bi/aij 50 100 0 0 01 s1 s2 x2 0 0 100 1 0 1 0 -1 2 0 0 1

27、 -1 0 1 0 0 1 50 150 250 50/1 150/2 zj 0 100 0 0 100 50 0 0 0 -10025000管管 理理 運運 籌籌 學學392 單純形法的表格形式單純形法的表格形式n從上表可以看出，第一次迭代的從上表可以看出，第一次迭代的 ，因此不是最優(yōu)，因此不是最優(yōu)解。設(shè)解。設(shè)x1為入基變量，從此值可知為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，為最小正數(shù)，因此，s1為出基變量，為出基變量，a11為主元，繼續(xù)迭代如下表所示。為主元，繼續(xù)迭代如下表所示。n從上表中可知第二次迭代得到的基本可行解為從上表中可知第二次迭代得到的基本可行解為x1=50,

28、x2=250,s1=0,s2=50, s3=0,這時這時z=27500。n由于檢驗數(shù)都由于檢驗數(shù)都0，因此所求得的基本可行解為最優(yōu)解，因此所求得的基本可行解為最優(yōu)解， z=27500為最優(yōu)目標函數(shù)值。為最優(yōu)目標函數(shù)值。n實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。表頭。1500jjjcz迭代次數(shù)基變量 cB x1 x2 s3 s4 s5 b 比值 bi/aij 50 100 0 0 02 x1 s2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50 250 zj

29、50 100 50 0 50 0 0 -50 0 -5027500管管 理理 運運 籌籌 學學403 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法一、大一、大M法法n以第二章的例以第二章的例2來講解如何用單純形表的方法求來講解如何用單純形表的方法求解目標函數(shù)值最小的線性規(guī)劃問題。解目標函數(shù)值最小的線性規(guī)劃問題。n目標函數(shù)：目標函數(shù)：n約束條件：約束條件：n加入松弛變量和剩余變量變?yōu)闃藴市?，得到新的加入松弛變量和剩余變量變?yōu)闃藴市停玫叫碌募s束條件如下約束條件如下：12m in23.fxx12112123 5 0,1 2 5,26 0 0,0 .x

30、xxxxxx1211212312123350,125,2600,0.xxsxsxxsx x s s s管管 理理 運運 籌籌 學學413 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法 為了使單純形表解法有一個統(tǒng)一的解法，我們把所有求目標函數(shù)最小值的為了使單純形表解法有一個統(tǒng)一的解法，我們把所有求目標函數(shù)最小值的問題化成求目標函數(shù)最大值的問題。具體做法只要把目標函數(shù)乘以（問題化成求目標函數(shù)最大值的問題。具體做法只要把目標函數(shù)乘以（1）。）。 要注意到人工變量是與松弛、剩余變量不同的。松弛變量、剩余變量它要注意到人工變量是與松弛、剩余變量不同的。松弛

31、變量、剩余變量它們可以取零值，也可以取正值，們可以取零值，也可以取正值，而人工變量只能取零值。而人工變量只能取零值。一旦人工變量取一旦人工變量取正值，那么有人工變量的約束方程和原始的約束方程就不等價了，這樣所正值，那么有人工變量的約束方程和原始的約束方程就不等價了，這樣所求得的解就不是原線性規(guī)劃的解了。為了竭盡全力地要求人工變量為零，求得的解就不是原線性規(guī)劃的解了。為了竭盡全力地要求人工變量為零，我們規(guī)定人工變量在目標函數(shù)中的系數(shù)為我們規(guī)定人工變量在目標函數(shù)中的系數(shù)為M，這里，這里M為任意大的數(shù)。這樣為任意大的數(shù)。這樣只要人工變量只要人工變量M0，所求的目標函數(shù)最大值就是一個任意小的數(shù)。這樣，

32、所求的目標函數(shù)最大值就是一個任意小的數(shù)。這樣為了使目標函數(shù)實現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到為了使目標函數(shù)實現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，也就是說人工變量仍不為零，則最后，人工變量仍不能從基變量中換出，也就是說人工變量仍不為零，則該問題無可行解。該問題無可行解。管管 理理 運運 籌籌 學學423 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法 此例的數(shù)學模型如下所示：此例的數(shù)學模型如下所示： 目標函數(shù)：目標函數(shù)： max z=2x13x2Ma1Ma2 約束條件：約束條件：x1+x

33、2s1+a1=350， x1s2+a2=125， 2x1+x2+s3=600， x1，x2，s1，s2，s3，a1，a20. 像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量“強行強行”地地 加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來就令就令人工變量在求最大值的目標函數(shù)里的系數(shù)為人工變量在求最大值的目標函數(shù)里的系數(shù)為M，這個方法叫做大，這個方法叫做大M法，法，M叫做罰因子。叫做罰因子。 管管 理理 運運 籌籌 學學433 求目標函數(shù)值最小的線性規(guī)劃的問題

34、的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法下面我們就用大下面我們就用大M法來求解此題法來求解此題:迭代次迭代次數(shù)數(shù)基變量基變量cB x1 x2 s1 s2 s3 a1 a2b比值比值 -2 -3 0 0 0 -M 0a1a2a3-M-M0 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2M -M M M 0 -M -M-2+2M -3+M -M -M 0 0 0-475M1a1x2s3-M-20 0 1 -1 0 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0

35、-2225125350225-350/2 zj -2 -M M -M+2 0 -M -M-2 0 -3+M -M M-2 0 0 2-2M-225M-2502a1x1s2-M-20 0 1/2 -1 0 -1/2 1 0 1 1/2 0 0 1/2 0 0 0 1/2 0 1 1/2 0 1/2300/1/2175/1/2 zj -2 -1/2M-1 M 0 1/2M-1 -M 0 0 1/2M-2 -M 0 - 1/2M+1 0 -M-50M-600jjjczjjjczjjjcz管管 理理 運運 籌籌 學學443 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標

36、函數(shù)值最小的線性規(guī)劃的問題的單純形表解法 從上表中可知檢驗數(shù)都小于零。已求得最優(yōu)解為：從上表中可知檢驗數(shù)都小于零。已求得最優(yōu)解為： x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0，其最優(yōu)值為其最優(yōu)值為 f=-z=-(-800)=800。jjjcz迭迭代代次次數(shù)數(shù)基變量基變量 cB x1 x2 s1 s2 s3 a1 a2 b 比值比值 -2 -3 0 0 0 -M -M3 x2 x1 s2 -3 -2 0 0 1 -2 0 -1 2 0 1 0 1 0 1 -1 0 0 0 1 1 1 -1 -1 100 250 125 zj -2 -3 4 0 1 -4

37、0 0 0 -4 0 -1 -M+4 -M -800管管 理理 運運 籌籌 學學453 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法二、兩階段法二、兩階段法 兩階段法是處理人工變量的另一種方法，這種方法是兩階段法是處理人工變量的另一種方法，這種方法是將加入人工變量后的線性規(guī)劃劃分兩階段求解，仍以上面的將加入人工變量后的線性規(guī)劃劃分兩階段求解，仍以上面的例題為例，闡述兩階段法的求解過程。例題為例，闡述兩階段法的求解過程。 第一階段：要判斷原線性規(guī)劃是否有基可行解，方法第一階段：要判斷原線性規(guī)劃是否有基可行解，方法是先求解下列線性規(guī)劃問題：是先求解下

38、列線性規(guī)劃問題： 目標函數(shù)：目標函數(shù)： 約束條件：約束條件：12max;zaa 12111221231212312350,125,2600,0.xxsaxsaxxsx x s s s a a管管 理理 運運 籌籌 學學463 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法 注意：此線性規(guī)劃的約束條件與原線性規(guī)劃一樣，注意：此線性規(guī)劃的約束條件與原線性規(guī)劃一樣，而目標函數(shù)是求人工變量的相反數(shù)之和的最大值。如果此而目標函數(shù)是求人工變量的相反數(shù)之和的最大值。如果此值大于零，則不存在使所有人工變量都為零的可行解，停值大于零，則不存在使所有人工變量都為零的可

39、行解，停止計算。如果此值為零，即說明存在一個可行解，使得所止計算。如果此值為零，即說明存在一個可行解，使得所有的人工變量都為零。有的人工變量都為零。 第二階段：將第一階段的最終單純形表中的人工變量第二階段：將第一階段的最終單純形表中的人工變量取消，將目標函數(shù)換成原問題的目標函數(shù)，把此可行解作取消，將目標函數(shù)換成原問題的目標函數(shù)，把此可行解作為初始可行解進行計算。為初始可行解進行計算。管管 理理 運運 籌籌 學學473 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法迭代迭代次數(shù)次數(shù)基變基變量量cB x1 x2 s1 s2 s3 a1 a2b比值比值

40、-2 -3 0 0 0 -1 -10a1a2s3-1-10 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2 -1 1 1 0 -1 -1-2 1 -1 -1 0 0 0-4701a1x1s3-100 0 1 -1 1 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -2225125350 zj 0 -1 1 -1 0 -1 1 0 1 -1 1 0 0 22252x2x1s3000 0 1 -1 1 0 1 0 1 0 0 -1 0 0 1 0 0 1 1 1 -1 -1225

41、125125 zj 0 0 0 0 0 0 0 0 0 0 0 0 -1 -10管管 理理 運運 籌籌 學學483 求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法迭迭代代次次數(shù)數(shù)基基變變量量cB x1 x2 s1 s2 s3b比值比值 -2 -3 0 0 0 0 x2x1s3-3-20 0 1 -1 1 0 1 0 0 -1 0 0 1 0 2 1225125125225/1125/2 zj-2 -3 3 -1 0 0 0 -3 1 0-9251x2x1s2-3-20 0 1 -2 0 -1 1 0 1 0 1 0 0 1 1 1100250125

42、 zj -2 -3 4 0 1 0 0 -4 0 -1-800 從表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最優(yōu)解，其最優(yōu)值為z=-(-800)=800。管管 理理 運運 籌籌 學學494 幾種特殊情況幾種特殊情況 .0,40,30,1501033020max212112121xxxxxxxxxz約束條件目標函數(shù)一、無可行解一、無可行解 例例1、用單純形表求解下列線性規(guī)劃問題、用單純形表求解下列線性規(guī)劃問題解：在上述問題的約束條件中加入松馳變量、剩余變量、人工變量得到：解：在上述問題的約束條件中加入松馳變量、剩余變量、人工變量得到： 1211211

43、21231121231m ax2 03 031 01 5 0,3 0,4 0,0 .zxxM axxsxsxxsaxxsssa目 標 函 數(shù)約 束 條 件 填入單純形表計算得：填入單純形表計算得：管管 理理 運運 籌籌 學學504 幾種特殊情況幾種特殊情況迭迭代代次次數(shù)數(shù)基變基變量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1zjcj-zj-M -M 0 0 M -M20+M 30+M 0 0 -M 0-40M1x2s2a1300-M3/

44、10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M 30 3+M/10 0 M -M11+7/10M 0 -3-M/10 0 -M 0 450-25M2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304zjcj-zj20 30 3+M/10 11+7M/10 M -M0 0 -3-M/10 -11-7M/10 -M 0780-4M管管 理理 運運 籌籌 學學514 幾種特殊情況幾種特殊情況

45、 從第二次迭代的檢驗數(shù)都小于零來看，可知第從第二次迭代的檢驗數(shù)都小于零來看，可知第2次迭代所得的基本可次迭代所得的基本可行解已經(jīng)是最優(yōu)解了，其最大的目標函數(shù)值為行解已經(jīng)是最優(yōu)解了，其最大的目標函數(shù)值為780-4M。我們把最優(yōu)解。我們把最優(yōu)解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三個約束方程得代入第三個約束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640. 并不滿足原來的約束條件并不滿足原來的約束條件3，可知原線性規(guī)劃問題無可行解，或者說，可知原線性規(guī)劃問題無可行解，或者說其可行解域為空集，當然更不可能有最優(yōu)解了。其可行解域為空集，當然更不可能有最優(yōu)

46、解了。 像這樣只要求線性規(guī)劃的像這樣只要求線性規(guī)劃的最優(yōu)解里有人工變量大于零，則此線性規(guī)劃最優(yōu)解里有人工變量大于零，則此線性規(guī)劃無可行解。無可行解。二、無界解二、無界解 在求目標函數(shù)最大值的問題中，所謂無在求目標函數(shù)最大值的問題中，所謂無界解是指在約束條件下目標函數(shù)值可以取界解是指在約束條件下目標函數(shù)值可以取任意的大。下面我們用單純形表來求第二任意的大。下面我們用單純形表來求第二章中的例子。章中的例子。例例2 2、用單純形表求解下面線性、用單純形表求解下面線性規(guī)劃問題。規(guī)劃問題。 12121212m ax1,326,0 .zxxxxxxxx目 標 函 數(shù)約 束 條 件管管 理理 運運 籌籌 學

47、學524 幾種特殊情況幾種特殊情況 迭迭代代次次數(shù)數(shù)基基變變量量CBx1 x2 s1 s2b比值比值1 1 0 00s1s2001 -1 1 0-3 2 0 1161zjcj-zj0 0 0 0 1 1 0 001x1s2101 -1 1 0 0 -1 3 119zjcj-zj1 -1 1 00 2 -1 01填入單純形表計算得：填入單純形表計算得：解：在上述問題的約束條件中加入松馳變量，得標準型如下：解：在上述問題的約束條件中加入松馳變量，得標準型如下：121211221212m ax1,326,0 .zxxxxsxxsxxss目 標 函 數(shù)約 束 條 件管管 理理 運運 籌籌 學學534

48、幾種特殊情況幾種特殊情況 1 2a 從單純形表中，從第一次迭代的檢驗數(shù)等于從單純形表中，從第一次迭代的檢驗數(shù)等于2，可知所得的基本可行解，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最優(yōu)解。同時我們也知道如果進行第不是最優(yōu)解。同時我們也知道如果進行第2次迭代，那么次迭代，那么就選就選x2為入基變量，但是在選擇為入基變量，但是在選擇出基變量時遇到了問題：出基變量時遇到了問題： =-1, =-1,找不找不到大于零的到大于零的 來確定出基變量。事實上如果我們碰到這種情況就可以斷定來確定出基變量。事實上如果我們碰到這種情況就可以斷定這個線性規(guī)劃問題是無界的，這個線性規(guī)劃問題是無界的，

49、也就是說在此線性規(guī)劃的約束條件下，此目也就是說在此線性規(guī)劃的約束條件下，此目標函數(shù)值可以取得無限大。從標函數(shù)值可以取得無限大。從1次迭代的單純形表中，得到約束方程：次迭代的單純形表中，得到約束方程：22a12a 移項可得：移項可得：1212121,39.xxsxss121221211212121,39.,0,1,0,9.121.xxssxsxM sxMxMssMzxxMMM 不妨設(shè)可得一組解：顯然這是線性規(guī)劃的可行解，此時目標函數(shù)管管 理理 運運 籌籌 學學544 幾種特殊情況幾種特殊情況 ij 由于由于M可以是任意大的正數(shù)，可知此目標函數(shù)值無界?？梢允侨我獯蟮恼龜?shù)，可知此目標函數(shù)值無界。 上

50、述的例子告訴了我們在單純形表中識別線性規(guī)劃問題是無界的方法：上述的例子告訴了我們在單純形表中識別線性規(guī)劃問題是無界的方法：在某次迭代的單純形表中，在某次迭代的單純形表中，如果存在著一個大于零的檢驗數(shù)如果存在著一個大于零的檢驗數(shù) ，并且該列，并且該列的系數(shù)向量的每個元素的系數(shù)向量的每個元素aij(i=1,2,m)都小于或等于零，則此線性規(guī)劃問題都小于或等于零，則此線性規(guī)劃問題是無界的，是無界的，一般地說此類問題的出現(xiàn)是由于建模的錯誤所引起的。一般地說此類問題的出現(xiàn)是由于建模的錯誤所引起的。三、無窮多最優(yōu)解三、無窮多最優(yōu)解例例3、用單純形法表求解下面的線性規(guī)劃問題。、用單純形法表求解下面的線性規(guī)劃

51、問題。121212212m ax5 05 03 0 0,24 0 0,2 5 0,0 .zxxxxxxxxx目 標 函 數(shù)約 束 條 件管管 理理 運運 籌籌 學學554 幾種特殊情況幾種特殊情況 解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來求解。解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來求解。123121211222312123,m a x5 05 03 0 0 ,24 0 0 ,2 5 0 ,0 .ssszxxxxsxxsxsxxsss加 入 松 弛 變 量， 我 們 得 到 標 準 形 ：目 標 函 數(shù)約 束 條 件填入單純形表計算得：填入單純形表計算得：管管 理理 運運 籌籌 學

52、學564 幾種特殊情況幾種特殊情況迭迭代代次次數(shù)數(shù)基變基變量量CBx1 x2 s1 s2 s3b比值比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zjcj-zj0 0 0 0 050 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 01150/2zjcj-zj0 50 0 0 5050 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1z

53、jcj-zj50 50 50 0 00 0 -50 0 015000管管 理理 運運 籌籌 學學574 幾種特殊情況幾種特殊情況 124, 這樣我們求得了最優(yōu)解為這樣我們求得了最優(yōu)解為x1=50,x2=250,s1=0,s2=50,s3=0,此線性規(guī)劃的此線性規(guī)劃的最優(yōu)值為最優(yōu)值為15000。這個最優(yōu)解是否是惟一的呢？由于在第。這個最優(yōu)解是否是惟一的呢？由于在第2次迭代的檢驗數(shù)次迭代的檢驗數(shù)中除了基變量的檢驗數(shù)中除了基變量的檢驗數(shù) 等于零外，等于零外，非基變量非基變量s3的檢驗數(shù)也等的檢驗數(shù)也等于零，這樣我們可以斷定此線性規(guī)劃問題有無窮多最優(yōu)解。于零，這樣我們可以斷定此線性規(guī)劃問題有無窮多最優(yōu)

54、解。不妨我們把檢不妨我們把檢驗數(shù)也為零的非基變量選為入基變量進行第驗數(shù)也為零的非基變量選為入基變量進行第3次迭代?？汕蟮昧硪粋€基本次迭代?？汕蟮昧硪粋€基本可行解，如下表所示：可行解，如下表所示：迭代迭代次數(shù)次數(shù)基基變變量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50 50 50 0 00 0 -50 0 015000管管 理理 運運 籌籌 學學584 幾種特殊情況幾種特殊情況 從檢驗數(shù)可知此基本可行解從檢驗數(shù)可知此基本可行解x1=100,x2=200,s1=0,s2

55、=0,s3=50,也是最優(yōu)解，也是最優(yōu)解，從圖解法可知連接這兩點的線段上的任一點都是此線性規(guī)劃的最優(yōu)解，不從圖解法可知連接這兩點的線段上的任一點都是此線性規(guī)劃的最優(yōu)解，不妨用向量妨用向量Z1，Z2表示上述兩個最優(yōu)解即表示上述兩個最優(yōu)解即Z1 =（50，250，0，50，0），）， Z2 =（100，200，0，0，50），則此線段上的任一點，即可表示為），則此線段上的任一點，即可表示為Z1+（1- ）Z2，其中，其中01。如圖。如圖5-1所示：所示：100100200200300300100100200200300300250250Z Z1Z Z2圖圖5-1管管 理理 運運 籌籌 學學594

56、幾種特殊情況幾種特殊情況 s 在一個已得到最優(yōu)解的單純形表中，如果存在一個非基變量的檢驗數(shù)在一個已得到最優(yōu)解的單純形表中，如果存在一個非基變量的檢驗數(shù) 為零，為什么我們把這個非基變量為零，為什么我們把這個非基變量xs作為入基變量進行迭代時，得到的最作為入基變量進行迭代時，得到的最優(yōu)解仍為最優(yōu)解呢？優(yōu)解仍為最優(yōu)解呢？ 不妨設(shè)出基變量為不妨設(shè)出基變量為xk，則原最優(yōu)單純形表可表示如下：，則原最優(yōu)單純形表可表示如下：111111,111,1122100100000,0ksksskkkskkk skkksmmm sjjjmsssmmsssiisixxccxcaxcaxcaxcaxcaczc ac ac

57、 accc a從此表可知即有，也就是。管管 理理 運運 籌籌 學學604 幾種特殊情況幾種特殊情況 通過迭代，我們得到了新的單純形表，其中通過迭代，我們得到了新的單純形表，其中xs為基變量了，而為基變量了，而xk為非為非基變量了。我們可得到下表?；兞苛恕Ｎ覀兛傻玫较卤?。111111111111101101111000ksksskskmkiisiissiikksksksmkkksiiskkssikskssskskskkksmsmmksjksjjjkxxccaxcazc ac acaaaxcac ac acaaxcacaxcaaxcazzcczcz 在此表中把111.0.msiisikskkss

58、kksksjkjkc azcc accaaczcz，代入上式得：即又可得到：管管 理理 運運 籌籌 學學614 幾種特殊情況幾種特殊情況 又顯然在又顯然在新的單純形表中，基變量的檢驗數(shù)為零，用同樣的方法可證新的單純形表中，基變量的檢驗數(shù)為零，用同樣的方法可證明其他的非基變量的檢驗數(shù)不變，仍然小于零，這樣就證明了新得到的基明其他的非基變量的檢驗數(shù)不變，仍然小于零，這樣就證明了新得到的基本可行解仍然是最優(yōu)解。本可行解仍然是最優(yōu)解。 這樣我們得到了判斷線性規(guī)劃有無窮多最優(yōu)解的方法：對于某個最優(yōu)這樣我們得到了判斷線性規(guī)劃有無窮多最優(yōu)解的方法：對于某個最優(yōu)的基本可行解，如果存在某個非基變量的檢驗數(shù)為零，

59、則此線性規(guī)劃問題的基本可行解，如果存在某個非基變量的檢驗數(shù)為零，則此線性規(guī)劃問題有無窮多最優(yōu)解。有無窮多最優(yōu)解。四、退化問題四、退化問題 在單純形法計算過程中，確定出基變量時有時存在兩個以上的相同的在單純形法計算過程中，確定出基變量時有時存在兩個以上的相同的最小比值，這樣在下一次迭代中就有了一個或幾個基變量等于零，這稱之最小比值，這樣在下一次迭代中就有了一個或幾個基變量等于零，這稱之為退化。為退化。例例4.用單純形表，求解下列線性規(guī)劃問題。用單純形表，求解下列線性規(guī)劃問題。解：加上松馳變量解：加上松馳變量s1,s2,s3化為標準形式后，化為標準形式后，填入單純形表計算得：填入單純形表計算得：1312131231233m ax222,24,3,0 .zxxxxxxxxxxxx目 標 函 數(shù)約 束 條 件管管 理理 運運 籌籌 學學624