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

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

2、1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 04基本解如下表 基 基本解 可行否 目標(biāo)值對(duì)應(yīng)圖中的點(diǎn)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)成的初始可行基；此時(shí)， 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為對(duì)應(yīng)于基B1的基可行解。問(wèn)： X（1）是否最優(yōu)呢？否 稱非基變量在目標(biāo)函數(shù)中的系數(shù)為檢驗(yàn)數(shù)。min z=6x14x2 2x1 + 3x2

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

5、基而 X（2）為對(duì)應(yīng)于B2的基可行解此時(shí) 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問(wèn)： X（2）是否最優(yōu)呢？否因?yàn)椋?x2在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)x2，z 。7（3）尋找可行基B3，使其對(duì)應(yīng)的基可行解X（3）能使目標(biāo)函數(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中必有一個(gè)為零，而另一個(gè)大等于零。只要取 x2=min30/（1/2），40/2=20就有 x1=20，x3=0這樣 X（3）=（20，20，0，0）T因?yàn)?P1，P2線性無(wú)關(guān)，因此，B3=（P1，P2）為一個(gè)基而 X（3）為對(duì)應(yīng)于B3的基可行解此時(shí) 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問(wèn)： X（3）是否最優(yōu)呢？是，8從引例可以總結(jié)出求解過(guò)程：（1）確定初始基及其基可行解；（2）判斷是否為最優(yōu)解，是停止，否則轉(zhuǎn)

7、下一步；（3）轉(zhuǎn)換可行基，并求出相應(yīng)的基可行解，使目標(biāo)函數(shù)值有所改進(jìn)，轉(zhuǎn)（2）。9 確定初始的基本可行解 確定初始的基本可行解等價(jià)于確定初始的可行基. 在線性規(guī)劃標(biāo)準(zhǔn)型中設(shè)法得到一個(gè)m階單位矩陣I作為初始可行基。 若在化標(biāo)準(zhǔn)形式前，m個(gè)約束方程都是“”的形式，那么在化標(biāo)準(zhǔn)形時(shí)只需在一個(gè)約束不等式左端都加上一個(gè)松弛變量xn+i (i=12m)。10判斷現(xiàn)行的基本可行解是否最優(yōu) 設(shè)有標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：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得到對(duì)應(yīng)于基B的基可行解X=（b1，b2，bm，0，0）T1112 假如已求得一個(gè)基本可行解相應(yīng)的目標(biāo)函數(shù)值13要判定是否已經(jīng)達(dá)到最小值，只需將 代入目標(biāo)函數(shù)，即： 其中 稱為非基變量N的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若N的每一個(gè)檢驗(yàn)數(shù)均大于等于0，即N0，那么現(xiàn)在的基本可行解就是最優(yōu)解。14定理1：最優(yōu)解判別定理 對(duì)于線性規(guī)劃問(wèn)題若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。定理2：無(wú)窮多最優(yōu)解判別定理 若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)m+k=0，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。15 如果現(xiàn)行

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

10、果確定為換入變量，方程其中為中與對(duì)應(yīng)的系數(shù)列向量?，F(xiàn)在需在 中確定一個(gè)基變量為換出變量。 換出變量的確定 最小比值原則 當(dāng)由零慢慢增加到某個(gè)值時(shí)， 的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量： 若則選取對(duì)應(yīng)的基變量 為換出變量。 18 定理3：無(wú)最優(yōu)解（無(wú)界）判別定理 若 是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù) ，但是 ，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。證：令 ，則得新的可行解將上式代入因?yàn)?, 故當(dāng)+時(shí)，Z。19 可將這些計(jì)算設(shè)計(jì)成一個(gè)簡(jiǎn)單的表格，即單純形表來(lái)完成：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解：化為標(biāo)準(zhǔn)型 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為對(duì)應(yīng)于基B1的基可行解，顯然不是最優(yōu)解；根據(jù)minj|j0=

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

13、03/218024以2為主元素進(jìn)行迭代，得新的單純形表： 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ī)劃問(wèn)題解：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 因?yàn)榉腔兞縳4的檢驗(yàn)數(shù)4=0，由無(wú)窮多最優(yōu)解判別定理，本例的線性規(guī)劃問(wèn)題存在無(wú)窮多最優(yōu)解。事實(shí)上若以x4為換入變量，以x3為換出變量，再進(jìn)行一次迭代，可得一下單純形表：最優(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無(wú)最優(yōu)解 無(wú)最優(yōu)解與無(wú)可行

15、解時(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)解也稱為無(wú)有限最優(yōu)解，或無(wú)界解。 29因但所以原問(wèn)題無(wú)最優(yōu)解解：引入松弛變量x3,x4化為標(biāo)準(zhǔn)型C -2 -2 0 0 CXB b x1 x2 x3 x4 0X3 1-11100X4 2-1/2101-2-200例3、試用單純形法求解下列線性規(guī)劃問(wèn)題：31對(duì)于極大化的線性規(guī)劃問(wèn)題的處理：檢驗(yàn)是否最優(yōu)的準(zhǔn)則有所不同，即： 若某個(gè)基本可行解的所有非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) （

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

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

18、原線性規(guī)劃最優(yōu)解的過(guò)程。2. 如果最優(yōu)單純形表的基變量中仍含有人工變量，那么該線性規(guī)劃就不存在可行解。36 大M法 以后的計(jì)算與單純形表解法相同，只需認(rèn)定是一個(gè)很大的正數(shù)即可。 1.假如在單純形最優(yōu)表的基變量中不包含人工變量，則最優(yōu)解中剔除人工變量即為原問(wèn)題的最優(yōu)基本可行解。 2.否則說(shuō)明原問(wèn)題無(wú)可行解。為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的系數(shù)。3738解： 首先將原問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量，并在目標(biāo)函數(shù)中分別賦予 例5、用大M法求解下面的線性規(guī)劃問(wèn)題: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無(wú)可行解 通過(guò)大法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，那么該線性規(guī)劃就不存在可行解。 人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占?2解：故引入人工變量，并利用大M法求解例6、求解下列線性規(guī)劃問(wèn)題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)單純形表中，所有非基變量檢驗(yàn)數(shù)都大于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解

23、。44兩階段法 兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟： 1. 求解一個(gè)輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化； 2. 如果輔助線性規(guī)劃存在一個(gè)基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問(wèn)題已經(jīng)得了一個(gè)初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計(jì)算； 否則說(shuō)明原問(wèn)題沒(méi)有可行解，可停止計(jì)算。 45解：首先將問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：例7、用兩階段法求解線性規(guī)劃問(wèn)題。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ī)劃所有檢驗(yàn)數(shù)：原問(wèn)題已得一個(gè)初始基本可行解，47由上表可知，通過(guò)若干次旋轉(zhuǎn)變換，

25、原問(wèn)題的約束方程組已變換成包含一個(gè)單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問(wèn)題的目標(biāo)函數(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)解 ，目標(biāo)函數(shù)值maxZ=-6，與用大M法的結(jié)果完全相同。49無(wú)可行解 通過(guò)兩階段法求初始的基本可行解。但是如果兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線