最優(yōu)化方法課件：2-3 單純形法

1、13 單純形法 單純形法的一般原理 表格單純形法 借助人工變量求初始的基本可行解2 單純形法的一般步驟如下： 1947年，Dantzig提出的單純形法把尋優(yōu)的目標集中在所有基本可行解（即可行域頂點）中。 （1）尋找一個初始的基本可行解。 （2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)， 則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。 （3）移至目標函數(shù)值有所改善的另一個基本可行解， 然后轉(zhuǎn)回到步驟（2）。 3一、引例用單純形方法求解下列線性規(guī)劃： min z=6x14x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化為標準型 min z=6x14x2+0 x3+0 x4 2x

2、1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 04基本解如下表 基 基本解 可行否 目標值對應圖中的點B1=（P1，P2） X1=（20，20，0，0）T 200 BB2=（P1，P3） X2=（30，0，40，0）T 180 CB3=（P1，P4） X3=（50，0，0，80）T DB4=（P2，P3） X4=（0，60，80，0）T EB5=（P2，P4） X5=（0，100/3，0，160/3）T 400/3 AB6=（P3，P4） X6=（0，0，100，120）T 0 OABCDEOx1x22x1+3x2 =1004x1 + 2x2

3、 =120 min z=6x14x2 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 05（1）找初始可行基：B1=（P3，P4）現(xiàn)成的初始可行基；此時， XB=（x3，x4）T，XN=（x1，x2）T用XN表示Z和XB有： min z=6x14x2 x3 =1002x13x2 +x4 =1204x12x2令 XN=(0,0)T有 XB=(100,120)T則有： X（1）=（0，0，100，120）T為對應于基B1的基可行解。問： X（1）是否最優(yōu)呢？否 稱非基變量在目標函數(shù)中的系數(shù)為檢驗數(shù)。min z=6x14x2 2x1 + 3x2

4、+ x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0因為： x1和x2在目標函數(shù)中的系數(shù)為負，當x1，z ；x2，z 。6（2）尋找可行基B2，使其對應的基可行解X（2）能使目標函數(shù)值增加。選： x10則有： X（2）=（x1，0，x3，x4）Tmin z=6x14x2 x3 =1002x13x2 +x4 =1204x12x2要使為X（2）基可行解，x3，x4中必有一個為零，而另一個大等于零。只要取 x1=min100/2，120/4=30就有 x3=40，x4=0這樣 X（2）=（30，0，40，0）T因為 P1，P3線性無關，因此，B2=（P1，P3）為一個

5、基而 X（2）為對應于B2的基可行解此時 XB=（x1，x3）T，XN=（x2，x4）T用XN表示Z和XB有： min z=180 x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4問： X（2）是否最優(yōu)呢？否因為： x2在目標函數(shù)中的系數(shù)為正，當x2，z 。7（3）尋找可行基B3，使其對應的基可行解X（3）能使目標函數(shù)值增加。選： x20則有： X（3）=（x1，x2，x3，0）T min z=180 x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4要使為X（3）基可行解，x1，

6、x3中必有一個為零，而另一個大等于零。只要取 x2=min30/（1/2），40/2=20就有 x1=20，x3=0這樣 X（3）=（20，20，0，0）T因為 P1，P2線性無關，因此，B3=（P1，P2）為一個基而 X（3）為對應于B3的基可行解此時 XB=（x1，x2）T，XN=（x3，x4）T用XN表示Z和XB有： min z=200+ （1/2）x3+（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4問： X（3）是否最優(yōu)呢？是，8從引例可以總結(jié)出求解過程：（1）確定初始基及其基可行解；（2）判斷是否為最優(yōu)解，是停止，否則轉(zhuǎn)

7、下一步；（3）轉(zhuǎn)換可行基，并求出相應的基可行解，使目標函數(shù)值有所改進，轉(zhuǎn)（2）。9 確定初始的基本可行解 確定初始的基本可行解等價于確定初始的可行基. 在線性規(guī)劃標準型中設法得到一個m階單位矩陣I作為初始可行基。 若在化標準形式前，m個約束方程都是“”的形式，那么在化標準形時只需在一個約束不等式左端都加上一個松弛變量xn+i (i=12m)。10判斷現(xiàn)行的基本可行解是否最優(yōu) 設有標準形式的線性規(guī)劃問題：min z=C T X；AX=b，X0；假定 A中存在一可行基B, 且B為單位陣x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2

8、 xm + am,m+1xm+1 + + amnxn=bm得到對應于基B的基可行解X=（b1，b2，bm，0，0）T1112 假如已求得一個基本可行解相應的目標函數(shù)值13要判定是否已經(jīng)達到最小值，只需將 代入目標函數(shù)，即： 其中 稱為非基變量N的檢驗向量，它的各個分量稱為檢驗數(shù)。若N的每一個檢驗數(shù)均大于等于0，即N0，那么現(xiàn)在的基本可行解就是最優(yōu)解。14定理1：最優(yōu)解判別定理 對于線性規(guī)劃問題若某個基本可行解所對應的檢驗向量，則這個基本可行解就是最優(yōu)解。定理2：無窮多最優(yōu)解判別定理 若是一個基本可行解，所對應的檢驗向量，其中存在一個檢驗數(shù)m+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。15 如果現(xiàn)行

9、的基本可行解不是最優(yōu)解，即在檢驗向量 中存在負的檢驗數(shù)，則需在原基本可行解的基礎上尋找一個新的基本可行解，并使目標函數(shù)值有所改善。 基本可行解的改進 具體做法是：先從檢驗數(shù)為負的非基變量中確定一個換入變量，使它從非基變量變成基變量（將它的值從零增至正值），再從原來的基變量中確定一個換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。由此可得一個新的基本可行解，由 可知，這樣的變換一定能使目標函數(shù)值有所減少。16換入變量的確定 最大減少原則 假設檢驗向量 ， 選取最小負檢驗數(shù)所對應的非基變量為換入變量，即若 則選取對應的 為換入變量， 由于且為最小，可使目標函數(shù)值 最大限度的減少。17如

10、果確定為換入變量，方程其中為中與對應的系數(shù)列向量?，F(xiàn)在需在 中確定一個基變量為換出變量。 換出變量的確定 最小比值原則 當由零慢慢增加到某個值時， 的非負性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量： 若則選取對應的基變量 為換出變量。 18 定理3：無最優(yōu)解（無界）判別定理 若 是一個基本可行解，有一個檢驗數(shù) ，但是 ，則該線性規(guī)劃問題無最優(yōu)解。證：令 ，則得新的可行解將上式代入因為 , 故當+時，Z。19 可將這些計算設計成一個簡單的表格，即單純形表來完成：C CBTCNT CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1C2.Cm X1X2.Xm b1

11、b2.bm I N 12.m 0 CN T- CB TN 表格單純形法20BNbCBTCNTIB-1NB-1b0CNT -CBT B-1N21例1：用單純形法求解 min z=6x14x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化為標準型 min z=6x14x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0找初始可行基：B1=（P3，P4）現(xiàn)成的初始可行基；22列初始單純形表從表中有：X（1）=（0，0，100，120）T為對應于基B1的基可行解，顯然不是最優(yōu)解；根據(jù)minj|j0=

12、120/4，對應的x4為換出變量；Cj6 4 0 0b CBXBx1 x2 x3 x4 0 0 x3x4 2 3 1 04 2 0 1100120100/2120/4(min)z-6 -4 0 0023以4為主元素進行迭代，得新的單純形表：從表中有：X（2）=（30，0，40，0）T為對應于基B2的基可行解，顯然不是最優(yōu)解；根據(jù)maxj|j0=2，確定x2為換入變量； 按規(guī)則確定換出變量，即：=bi/aik|aik0=40/2，對應的x3為換出變量； Cj 6400b CBXB x1 x2x3x4 0 x3021-1/24040/2(min) 6x111/201/43030/(1/2)Z0-1

13、03/218024以2為主元素進行迭代，得新的單純形表： Cj 6400b CBXB x1x2x3x4 4 x2011/2-1/420 6x110-1/43/820 Z001/25/4 - 200表中j 0，j=1，4，因此得最優(yōu)解： X*=（20，20，0，0）T，Z*=200 25例2、用單純形方法求解線性規(guī)劃問題解：26 0 1 0 1 03x2-2 0 0 1 2 -12x30-0 1 0 1 03x2-24/11 0 1 0 04x303/10 1 0 1 03x40_1 0 1 0 04x30 0 0 0 0 1 1 0 0 -2 12x1-1 -1 0 0 2 02/11 0 0

14、 -2 12x50 -1 -2 0 0 08/21 2 0 0 18x50 x1 x2 x3 x4 x5bXBCB -1 - 2 0 0 0C最優(yōu)解最優(yōu)值2/23/1-27 因為非基變量x4的檢驗數(shù)4=0，由無窮多最優(yōu)解判別定理，本例的線性規(guī)劃問題存在無窮多最優(yōu)解。事實上若以x4為換入變量，以x3為換出變量，再進行一次迭代，可得一下單純形表：最優(yōu)解 最優(yōu)值最優(yōu)解的一般表示式C -1 -2 0 0 0CBXBb x1 x2 x3 x4 x50-2-1x4x2x1124 0 0 1/2 1 -1/2 0 1 -1/2 0 1/2 1 0 1 0 0 0 0 0 0 128無最優(yōu)解 無最優(yōu)解與無可行

15、解時兩個不同的概念。 無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問題的可行域為空集； 無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標函數(shù)達不到最優(yōu)值，即目標函數(shù)在可行域內(nèi)可以趨于無窮?。ɑ蛘邿o窮大）。無最優(yōu)解也稱為無有限最優(yōu)解，或無界解。 29因但所以原問題無最優(yōu)解解：引入松弛變量x3,x4化為標準型C -2 -2 0 0 CXB b x1 x2 x3 x4 0X3 1-11100X4 2-1/2101-2-200例3、試用單純形法求解下列線性規(guī)劃問題：31對于極大化的線性規(guī)劃問題的處理：檢驗是否最優(yōu)的準則有所不同，即： 若某個基本可行解的所有非基變量對應的檢驗數(shù) （

16、而不是），則基本可行解為最優(yōu)解否則采用最大增加原則（而非最大減少原則）確定換入變量，即： 若則選取對應的非基變量xm+k為換入變量確定了換入變量以后，換出變量仍采用最小比值原則來確定。 32借助人工變量求初始的基本可行解 假定我們下面研究的線性規(guī)劃都是非退化的，將線性規(guī)劃問題化為標準型,如果約束方程組中包含有一個單位矩陣I，那么已經(jīng)得到了一個初始可行基。 否則在約束方程組的左邊加上若干個非負的人工變量，使人工變量對應的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個單位矩陣。以單位矩陣為初始基，即可求得一個初始的基本可行解。 33 首先將原問題化為標準型添加人工變量 例4: 線性規(guī)劃問題:34加入

17、人工變量后的約束方程組與原約束方程組是不等價的。加上人工變量以后，線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問題的基本可行解。 只有當基本可行解中所有人工變量都為取零值的非基變量時，該基本可行解對原線性規(guī)劃才有意義。因為此時只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規(guī)劃的一個基本可行解而這正是我們引入人工變量的主要目的。35初始基本可行解 對原線性規(guī)劃沒有意義的,但是我們可以從X(0)出發(fā)進行迭代，迭代結(jié)果有兩種：1.一旦所有的人工變量都從基變量迭代出來，變成只能取零值的非基變量，那么我們實際上已經(jīng)求得了原線性規(guī)劃問題的一個初始的基本可行解。此時可以把所有人工變量剔除，開始正式進入求

18、原線性規(guī)劃最優(yōu)解的過程。2. 如果最優(yōu)單純形表的基變量中仍含有人工變量，那么該線性規(guī)劃就不存在可行解。36 大M法 以后的計算與單純形表解法相同，只需認定是一個很大的正數(shù)即可。 1.假如在單純形最優(yōu)表的基變量中不包含人工變量，則最優(yōu)解中剔除人工變量即為原問題的最優(yōu)基本可行解。 2.否則說明原問題無可行解。為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量。為此可以在目標函數(shù)中賦予人工變量一個絕對值很大的系數(shù)。3738解： 首先將原問題化為標準型添加人工變量，并在目標函數(shù)中分別賦予 例5、用大M法求解下面的線性規(guī)劃問題:39- 0 1 -1/2 -1/2

19、 0 1/2 1/23/2X2-2 1 0 -1/2 1/2 0 1/2 -1/21/2X11- -1 1 0 -1 0 0 11X2-21/2 2 0 -1 1 0 1 -11X6M1/1 -1 1 0 -1 0 0 11X7M2/1 1 1 -1 0 0 1 02X6M 0 0 -1/2 -3/2 0 +M 3/2+M 0 0 1/2 1/2 1 -1/2 -1/23/2X50 -1-2M 0 M -2-M 0 0 2+2M2/1 1 0 0 1 1 0 -12X50 1 -2-2M M M 0 0 03/1 0 1 0 0 1 0 03X50 X1 x2 x3 x4 x5 x6 x7bX

20、BCB 1 -2 0 0 0 M MC40 0 1 0 0 1 0 03X2-2 1 0 0 1 1 0 -12X40 1 1 -1 0 0 1 02X2-2 2 0 -1 1 0 1 -11X40- 0 1 -1/2 -1/2 0 1/2 1/23/2X2-21/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2X11 1 0 0 0 2 M M -1 0 1 0 1 -1 01X30 3 0 -2 0 0 2M M -1 0 1 0 1 -1 01X50 0 0 -1/2 -3/2 0 +M 3/2+M3/2 /1/2 0 0 1/2 1/2 1 -1/2 -1/23/2X5

21、0 X1 x2 x3 x4 x5 x6 x7bXBCB 1 -2 0 0 0 M MC最優(yōu)解 最優(yōu)值41無可行解 通過大法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，那么該線性規(guī)劃就不存在可行解。 人工變量的值不能取零，說明了原線性規(guī)劃的數(shù)學模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時線性規(guī)劃問題的可行域為空集。42解：故引入人工變量，并利用大M法求解例6、求解下列線性規(guī)劃問題43C 3 2 1 0 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0MM x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0

22、 1 00 1 -1 0 0 -1 0 1 6/1-3/1 3-M 2-M 1+2M 0 M M 0 0 0M2 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- 3-M 0 3+M 0 M 2 0 -2+M 3M2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 -3+3M -3+M M -1+M 0 1 在以上最優(yōu)單純形表中，所有非基變量檢驗數(shù)都大于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解

23、。44兩階段法 兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟： 1. 求解一個輔助線性規(guī)劃。目標函數(shù)取所有人工變量之和，并取極小化； 2. 如果輔助線性規(guī)劃存在一個基本可行解，使目標函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問題已經(jīng)得了一個初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計算； 否則說明原問題沒有可行解，可停止計算。 45解：首先將問題化為標準型添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：例7、用兩階段法求解線性規(guī)劃問題。46 0 1 -1/2 -1/2 0 1/2 1/23/2X20 1 0 -1/2 1/2 0 1/2 -

24、1/21/2X10- -1 1 0 -1 0 0 11X201/2 2 0 -1 1 0 1 -11X611/1 -1 1 0 -1 0 0 11X712/1 1 1 -1 0 0 1 02X61 0 0 0 0 0 1 1 0 0 1/2 1/2 1 -1/2 -1/23/2X50 -2 0 1 -1 0 0 22/1 1 0 0 1 1 0 -12X50 0 -2 1 1 0 0 03/1 0 1 0 0 1 0 03X50 x1 x2 x3 x4 x5 x6 x7bXBCB 0 0 0 0 0 1 1C輔助規(guī)劃所有檢驗數(shù)：原問題已得一個初始基本可行解，47由上表可知，通過若干次旋轉(zhuǎn)變換，

25、原問題的約束方程組已變換成包含一個單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標函數(shù)則還原成原問題的目標函數(shù)，可繼續(xù)利用單純形表求解。48 1 0 0 0 2 1 0 0 1 1 0 1 0 0 1 -1 0 1 0 1231X4X2X30-20 3 0 -2 0 0 2 0 -1 1 0 1 1 -1 0 0 -1 0 1 0 1121X4X2X50-200 0 -1/2 -3/2 01/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 11/23/23/2X1X2X51-20 x1 x2 x3 x4 x5 bXBCB1 -2 0 0 0C可得最優(yōu)解 ，目標函數(shù)值maxZ=-6，與用大M法的結(jié)果完全相同。49無可行解 通過兩階段法求初始的基本可行解。但是如果兩階段法的輔助線性規(guī)劃的目標函數(shù)的極小值大于零，那么該線