運籌學(xué)線性規(guī)劃單純形法

1、教案要點文 件 名：062OR05.PPT；Simlex1.XLS授課時間：2007年10月11日授課內(nèi)容：LP問題的單純形法預(yù)備知識：初等變換、凸集合、Excel復(fù)習(xí)可行解、基可行解，基及非基變量。難 點：單純形法的步驟重 點：單純形法的思路；步驟：初始表，檢驗數(shù)，判優(yōu)，進(jìn)基、比值、出基、迭代，表上操作；利用Excel。下節(jié)預(yù)習(xí)：教材單純形，運輸問題。8/27/2022運籌學(xué)第五講元培學(xué)院05級8/27/20222解LP問題單純形法LP問題的最優(yōu)解唯一解無窮多解有解無解無可行解無有限最優(yōu)解8/27/2022是若干個半平面之交是一個凸集。LP的可行解集：8/27/2022D是n維歐氏空間Rn的

2、一個集合: 對任意兩點：X(1), X(2)D, 任,若滿足 0 , 1, +=1則總有 X= X(1)+X(2) D；或任一個若滿足 0 1則總有 X= X(1)+(1-) X(2) D。X是連結(jié)X(1), X(2)的線段上任意一點則稱D是一個凸集。定義3：凸集8/27/2022定理：n維歐氏空間Rn的任兩個凸集合A、B之交也是一個凸集合 : 證明：對任意X(1), X(2)AB,則： X(1), X(2)A,X(1), X(2)B, 任,若滿足 0 , 1, +=1則總有 X= X(1)+X(2)AA凸,同理X= X(1)+X(2)B,即XAB,AB是一個凸集。凸集的性質(zhì)：凸集之并必凸嗎？

3、8/27/2022LP問題的標(biāo)準(zhǔn)型LP問題標(biāo)準(zhǔn)化：矩陣形式目標(biāo)函數(shù)是求最大：Max Z=CX可能有的不等式約束通過引入松弛變量或剩余變量全化為等式約束：AX =b決策變量全有非負(fù)約束：X0 m為約束個數(shù),n為決策變量個數(shù),Amn滿秩。 X = (x1 , , xn)T ，每個分量有非負(fù)約束。8/27/2022標(biāo)準(zhǔn)型LP問題的解標(biāo)準(zhǔn)化了的LP問題：Max Z=CX AX =b（全為等式約束）s.t. X0 （決策變量全有非負(fù)約束）Amn 滿秩,m為約束個數(shù),n為決策變量個數(shù)。 X = (x1 , , xn)T ，每個分量有非負(fù)約束。注：通常說：m 0,它,則z ,它可以大到多少?50 x1與x3

4、換位，做初等變換：1 0 1 0 -1 502 0 0 1 -1 1500 1 0 0 1 250 x1進(jìn)基x3出基。1 0 1 0 -1 502 0 0 1 -1 1500 1 0 0 1 250 1 0 1 0 -1 50 0 0 -2 1 1 50 0 1 0 0 1 250目標(biāo)函數(shù) z = 50 x1+100 x2 =27500-50 x3-50 x58/27/2022此線性規(guī)劃問題圖解法2x1+x2=400最優(yōu)解(50,250)目標(biāo)函數(shù) f = 50 x1+100 x2 =27500 x1+x2=300 x2=250可行解區(qū)域 x1+ x23002x1+x2400 x2250 x10

5、 , x20max f=50 x1+100 x28/27/2022LP問題的代數(shù)解法實際上這是在可行域的頂點中搜索最優(yōu)解：從一個頂點開始，是否好？不好如何尋找出更好的一個？第一個可行域的頂點初始基可行解；一個基可行解是否是最優(yōu)的判斷判優(yōu)；不是最優(yōu)解時如何尋找出更好的一個迭代。Dantzig在20世紀(jì)40年代，把上述想法歸納成“單純形法(Simplex Method)”。它被公認(rèn)為20世紀(jì)十大算法之一。可操作性強，可以方便地編制相應(yīng)的計算機程序。是本課程的重點。8/27/2022解LP的單純形法此法的證明不作要求。先標(biāo)準(zhǔn)化,列表操作,借助Excel 實現(xiàn)。第一個可行域的頂點初始基可行解，列初始表

6、；基、基變量、非基變量一個基可行解是否是最優(yōu)的判斷判優(yōu)，求非基變量的檢驗數(shù)，是否有正的；不是最優(yōu)解時如何尋找出更好的一個迭代，確定進(jìn)基變量，求比值，確定出基變量，然后用行初等變換迭代。Excel8/27/2022 a11 a1m a1m+1 a1n a21 a2m a2m+1 a2n am1 amm amm+1 amn P1 Pm Pm+1 PnBN設(shè)：mn，記 r(A)=m , 至少有一個m階子矩陣如 B=(P1,P2,Pm) 的行列式不為 0 ?；?/27/2022A= (P1 Pm Pm+1 Pn )=(BN) 基向量 非基向量X= (x1 xmxm+1 xn )T=(XBXN)T 基變

7、量 非基變量 對應(yīng)變量 XB XN定義4：基 若A中一個子矩陣B是可逆矩陣|B|0，則方陣B稱為LP問題的一個基。B中的任一列成為LP問題的一個基向量(共有m個)。A中其他列向量叫基B的非基向量(共有n-m個)。8/27/2022A=(B,N) X=(XB , XN )T移項 BXB =b-NXN 同左乘B-1XB = B-1 b - B-1N XN如果B=I(單位矩陣)，b0, XN =0則XB = b,即:X=(b,0)是基可行解。AX=b的求解8/27/2022 基本解對應(yīng)于基B，X=為AX=b的一個解。B-1 b 0定義6：基本可行解基B，基本解X=若B-1 b0，稱基B為可行基。類似

8、可以定義：最優(yōu)解、最優(yōu)基。 B-1 b 0 基本解中最多有m個非零分量。 基本解的數(shù)目不超過Cnm = 個。n!m!(n-m)!定義5：8/27/2022X(1) , X(2) , ,X(k) 是n維歐氏空間中的k點,若有一組數(shù)1,2 , , k 滿足 0 i 1 (i=1, ,k)點 X= 1 X(1) + + k X(k) 為一個線性組合,則稱點X為 X(1) , X(2) , ,X(k) 的一個凸組合。凸組合定義7：8/27/2022頂點凸集D, 點 XD，若找不到040 ，選 x2從0“進(jìn)基”，x1 =0還留作非基變量，誰“出基”？x3 =30-2x2 0 x2 30/2 x4 =60

9、-2x2 0 x2 60/2 x5 =24-2x2 0 x2 24/2 x2=min(30/2 , 60/2 , 24/2 ) =12x2進(jìn)基變量， x5出基變量。、改進(jìn)：由一個基可行解另一個基可行解目標(biāo)函數(shù)值變大一點。8/27/2022第一次迭代得的基為：B2=(P3 P4 P2)Z =0 +40 x1+50 x2x3 =30-( x1+ 2x2 )x4=60-( 3x1+ 2x2)x5 =24 -2x2由Z=0+40 x1+50 x2 x3 +2x2 =30-x1 x4+2x2 =60-3x1 2x2=24-x5 移項-,-,式兩邊同除以2,代入式8/27/2022Z = 600 +40

10、x1 - 25x5x3 = 6 - x1 + x5 x4 = 36 -3 x1 + x5 x2=12 - 1/2x5令x1 =x5 =0 得 X(2) =(0, 12, 6, 36, 0)T為第二個基可行解：Z(2) =600-,-,式兩邊同除以2,代入式,整理得：8/27/2022Z中x1的系數(shù)：400 ， x1從0， Z可以增加，X(2)不是最優(yōu)解。 選x1 “進(jìn)基”，x5 =0還留作非基變量，誰“出基”呢？x3 = 6 - x1 0 x4 = 36 - 3x1 0 x2 = 12 0 x1 = min( 6/1 , 36/3 ) = 6x1進(jìn)基，x3出基。 判斷8/27/2022X(3)

11、 =(6, 12, 0, 18, 0)T為第三個基可行解：Z(3) =840第二次迭代得的基為: B3 =(P1 P4 P2 )Z = 600 +40 x1 - 25x5x3 = 6 - x1 + x5 x4 = 36 -3 x1 + x5 x2=12 - 1/2x5由Z=840-40 x3+15x5x1=6 - x3 + x5 x4= 18+3x3 - 2x5x2=12 -1/2x5整理得8/27/2022選x5從0進(jìn)基，x3 =0留作非基，誰出基？ x1=6 +x5 0 x4= 18 -2x5 0 x2=12-1/2 x5 0 x5=min( 18/2 , 12/1/2 ) =9x5進(jìn)基，

12、 x4出基。 x5的系數(shù)150,X(3)還不是最優(yōu)解8/27/2022Z=975- 35/2x3 - 15/2x4x1= 15 + 1/2x3 - 1/2x4x5= 9 + 3/2x3 - 1/2x4x2= 15/2 -3/4x3 + 1/4x4令x3 =x4 =0 ,X(4) =(15, 15/2 , 0, 0 ,9 )T為第四個基可行解, Z(4) =975,是最優(yōu)解。第三次迭代得的基為：B4=(P1 P5 P2 )8/27/2022也可以選 x1從0“進(jìn)基”，x2 =0還留作非基變量，誰“出基”？x3 =30- x1 0 x1 30 x4 =60-3x1 0 x1 20 x5 =24 0

13、 x2=min(30/1 , 60/3) =20 x1進(jìn)基變量， x4出基變量。、改進(jìn)：由一個基可行解另一個基可行解目標(biāo)函數(shù)值變大一點。8/27/2022第二次選的基為：B2=(P3 P1 P5)Z =0 +40 x1+50 x2x3 =30-( x1+ 2x2 )x4=60-( 3x1+ 2x2)x5 =24 -2x2由Z=0+40 x1+50 x2 x3+x1 =30-2x2 3x1 =60-2x2- x4 x5=24-2x2 移項式兩邊同除以3, -, 代入式8/27/2022Z = 800 -40/3x4+ 70/3x2x1 = 20 - 1/3 x4 - 2/3x2 x3 = 10

14、+ 1/3x4 - 4/3x2 x5=24 - 2x2令x2 =x4 =0 得 X(2) =(20, 0, 10, 0, 24)T為第二個基可行解：Z(2) =800式兩邊同除以3, -, 代入式,整理得：8/27/2022Z中x2的系數(shù)：70/30 ， x2從0， Z可以增加，X(2)不是最優(yōu)解。 選x2“進(jìn)基”，x4 =0還留作非基變量，誰“出基”呢？x1 = 20- 2/3x2 0 x3 = 10- 4/3x2 0 x5 = 24- 2 x2 0 x1 = min( 20/2/3 , 10/4/3 , 24/2 ) = 7.5x2進(jìn)基，x3出基。 判斷8/27/2022Z=975- 35

15、/2x3 - 15/2x4x1= 15 + 1/2x3 - 1/2x4x2= 15/2 -3/4x3 + 1/4x4x5= 9 + 3/2x3 - 1/2x4令x3 =x4 =0 ,X(3) =(15, 15/2 , 0, 0 ,9 )T為第三個基可行解, Z(3) =975,是最優(yōu)解。第三次選的基為：B4=(P1 P2 P5 )8/27/2022我們前面得到的四個基可行解是：X(1)=(0, 0 , 30, 60 ,24 )T X(2)=(0, 12 , 6, 36 , 0 )TX(3)=(6, 12 , 0, 18 , 0 )T X(4)=(15,15/2, 0, 0 ,9 )T 它們分別

16、對應(yīng)了可行域的四個頂點：O、A、B、C。0(0,0)x2x1A DB(0,12)(6,12)(15,7.5)C(0,20)后面的迭代則是：O,D,C。8/27/2022、分離系數(shù)列成表；、用類似矩陣初等變換的操作；、找出第一個可行基；、判斷可行基是否是最優(yōu)基？是則結(jié)束。、還不是最優(yōu)基，決定進(jìn)基變量、出基變量迭代；、找到好一點的可行基，回。 單純形法算法8/27/2022、定初始基，初始基本可行解、對應(yīng)于非基變量檢驗數(shù)j全 0？若是，停，得到最優(yōu)解；若否，轉(zhuǎn)(3)。、若有k 0，Pk全 0，停， 沒有有限最優(yōu)解； 否則轉(zhuǎn)(4)、求解資源有約束求Max的LP問題單純形法基本步驟= min ai m+k 0 =biAi m+kbrar m+k定xr為換出變量，ar m+k為主元。由最小比值法求：maxj =m+kXm+k 換入變量j08/27/2022例:Max Z = x1 + 2x2x1 4x2 3x1+2x2 8 x1 , x2 0 x1-x3 = 4x2 -x4 = 3x1+2x2 -x5= 8 x1 , x5 0幾點說明：(P3P4P5)是基，但不是可行基。第一個可行基如何找？8/27/20221、LP問題約束的常數(shù)項b0,全是“”的約束標(biāo)準(zhǔn)化；2、列出初始單純形表