單純形法圖解法及原理實用教案

1、1決策(juc)(juc)變量：XiXi為第i i班開始上班的人數(shù) i=1,6 i=1,6目標函數(shù)：Min Z= X1+X2+X3+X4+X5+X6Min Z= X1+X2+X3+X4+X5+X6約束條件： X6 + X1 = 60 X6 + X1 = 60 X1 + X2 = 70 X1 + X2 = 70 X2 + X3 = 60 X2 + X3 = 60 X3 + X4 = 50 X3 + X4 = 50 X4 + X5 = 20 X4 + X5 = 20 X5 + X6 = 30 X5 + X6 = 30 Xi=0,1=1,6 Xi=0,1=1,6第1頁/共35頁第一頁，共36頁。2線

2、性規(guī)劃模型隱含的假設(shè)：比例性： 決策變量變化引起目標的改變量與決策變量改變量成正比?？杉有裕?每個決策變量對目標和約束(yush)(yush)的影響獨立于其它變量。連續(xù)性： 每個決策變量取連續(xù)值。確定性： 線性規(guī)劃中的參數(shù)aij , bi , ciaij , bi , ci為確定值。 第2頁/共35頁第二頁，共36頁。3第二節(jié) 單純形法原理(yunl)-圖解法 圖解法：是用畫圖的方式求解線性規(guī)劃的一種方法。 只能用于求解兩個變量(binling)(binling)的LPLP問題第3頁/共35頁第三頁，共36頁。41 1）作出可行域2 2）作出一條目標(mbio)(mbio)函數(shù)的等值線3 3）

3、平行移動目標(mbio)(mbio)函數(shù)的等值線，求出最優(yōu)解圖解法基本(jbn)步驟：第4頁/共35頁第四頁，共36頁。5第5頁/共35頁第五頁，共36頁。6x2504030201010203040 x1第6頁/共35頁第六頁，共36頁。7x2504030201010203040 x12x1+x2 504x1+3x2 120第7頁/共35頁第七頁，共36頁。8x2504030201010203040 x1O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）第8頁/共35頁第八頁，共36頁。9x2504030201010203040 x1第9頁/共35頁第九頁，共36頁。10 x250

4、4030201010203040 x1第10頁/共35頁第十頁，共36頁。11x2504030201010203040 x1Q2（15，20）有唯一(wi y)(wi y)最優(yōu)解 第11頁/共35頁第十一頁，共36頁。12例2 解線性規(guī)劃(xin xn u hu) 0, 052222.max2121212121xxxxxxxxtsxxz1x2x01A2A3A4A2221 xx3 z5 . 1 z0 z521 xx2221 xxD Tx4 , 1 有唯一(wi y)(wi y)最優(yōu)解 第12頁/共35頁第十二頁，共36頁。13對于線性規(guī)劃問題，我們定義：可行解：滿足全部約束條件的決策向量 XRn

5、?？尚杏颍喝靠尚薪鈽?gòu)成的集合(jh)。（它是 n 維歐 氏空間Rn 中的點集，而且是一個“凸 多面體”)最優(yōu)解：使目標函數(shù)達到最優(yōu)值（最大值或最小 值，并且有界）的可行解。無界解：若求極大化則目標函數(shù)在可行域中無上 界；若求極小化則目標函數(shù)在可行域中 無下界。 第13頁/共35頁第十三頁，共36頁。144 z21,AA1x2x01A2A3A4A2221 xx521 xx2221 xxD 0, 052222.max2121212121xxxxxxxxtsxxz2124minxxz 有無窮(wqing)(wqing)多最優(yōu)解 例3 解線性規(guī)劃(xin xn u hu)Z=0Z=0Z=-2Z=-2

6、第14頁/共35頁第十四頁，共36頁。15例4 解線性規(guī)劃(xin xn u hu)1x2x0 0, 0331.2min21212121xxxxxxtsxxz121 xxAB3321 xx212xxz D有無(yu w)(yu w)界解 第15頁/共35頁第十五頁，共36頁。16例5 5： MaxZ=3XMaxZ=3X1 1-2X-2X2 2 X X1 1 + X+ X2 2 =1 =8 =8 X X1 1,X,X2 2 =0 =0無可行(kxng)解1x2x082221 xx121xx第16頁/共35頁第十六頁，共36頁。17結(jié)論： 1 1、線性規(guī)劃問題的可行域為凸集 2 2、若有最優(yōu)解一定

7、可以(ky)(ky)在其可行域的頂點上得到線性規(guī)劃問題解的幾種情況(qngkung)(qngkung)： 1 1、有唯一最優(yōu)解 2 2、有無窮多最優(yōu)解 3 3、無可行解 4 4、無最優(yōu)解第17頁/共35頁第十七頁，共36頁。18第三節(jié) 單純形法 -原理(yunl) 單純形法：單純形法是求解線性規(guī)劃(xin (xin xn u hu)xn u hu)的主要算法，19471947年由美國斯坦福大學教授丹捷格（G.B.DanzigG.B.Danzig）提出。盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實用的特色始終保持著絕對 的“市場”占有率。 第18頁/共35頁第十八頁，共36頁。1

8、9定義1：基(基陣) 由A中一個子矩陣B是可逆矩陣，則方陣B稱為(chn wi)LP問題的一個基。A= (P1 Pm Pm+1 Pn )=(BN) 基向量 非基向量X= (X1 Xm Xm+1 Xn )T=(XB XN)T 基變量 非基變量 XB XN線性規(guī)劃問題(wnt)解的概念第19頁/共35頁第十九頁，共36頁。20例1、 X1+2X2 +X3 =30=30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=第20頁/共35頁第二十頁，共36頁。21AX=b的求解(qi ji)A=

9、(BN)X=(XB XN )T XB XN(BN) = bBXB +NXN=bBXB =b-NXNXB = B-1 b - B-1N XN第21頁/共35頁第二十一頁，共36頁。22定義2：基本解對應于基B，X=為AX=b的一個解。B-1 b 0定義3：基本可行解基B，基本解X=若B-1 b 0 0，稱基B B為可行基。 最優(yōu)解、最優(yōu)基 B-1 b 0 基本解中最多有m m個非零分量。 基本解的數(shù)目不超過Cnm = 個。n!m!(n-m)!第22頁/共35頁第二十二頁，共36頁。23X1X2X3X4X5X=b=306024B=(P3 P4 P5)=I 可逆 基 N=(P1 P2)X3=30-(

10、 X1+2 X2)X4=60-(3X1+2 X2)X5 =24 -2 X2例1 1：第23頁/共35頁第二十三頁，共36頁。24令X1 = X2 =0, X3=30, X4=60, X5=24X= = = XN 0 XB B-1 b00306024 1 2 1又：1 =(P1 P2 P3 )= 3 2 0 0 2 0|B1|=60, B可逆第24頁/共35頁第二十四頁，共36頁。25X1=12-(1/3 X4 -1/3 X5)X2=12-(1/2 X5 )X3 =-6-(- 1/3 X4 -2/3 X5 )令X4=X5=0 X=(12, 12, -6, 0, 0)TZ=40X1 +50X2 =

11、4012-(1/3 X4 -1/3 X5) +5012- 1/2 X5 = 1080+(- 40/3 X4 -35/3 X5 )基本(jbn)解，但不可行第25頁/共35頁第二十五頁，共36頁。26例2：給定約束條件 -X3+X4 =0=0 X2 +X3 +X4 =3 -X1 +X2 +X3+X4 =2 Xj 0 0 ( j=1,2,3,4 )求出基變量(binling)是X1 , X3 , X4的基本解，是不是可行解？第26頁/共35頁第二十六頁，共36頁。27 0 -1 1解：B=(P1 P3 P4)= 0 1 1 -1 1 1 0 1 -1 0B-1= -1/2 1/2 0 3 1/2

12、1/2 0 2b=第27頁/共35頁第二十七頁，共36頁。28 X1 X3 = B-1 b X4 XB = 0 1 -1 0 1 = -1/2 1/2 0 3 = 3/2 1/2 1/2 0 2 3/2X=(1, 0, 3/2, 3/2)T 是 第28頁/共35頁第二十八頁，共36頁。29定義1：凸集D是n維歐氏空間的一個集合(jh) X(1), X(2)D,若任一個滿足 X= X(1)+(1-) X(2) (0 1) 有XD線性規(guī)劃(xin xn u hu)(xin xn u hu)問題的幾何意義( (例2)2)第29頁/共35頁第二十九頁，共36頁。30 X(1) , X(2) , ,X(

13、k) 是n維歐氏空間(kngjin)中的k個點，若有一組數(shù) 1 , 2 , , k 滿足 0 i 1 (i=1, ,k)定義(dngy)2 i =1ki=1有點(yudin) x= 1 X(1) + + k X(k)則稱點X為 X(1) , X(2) , ,X(k) 的凸組合。凸組合第30頁/共35頁第三十頁，共36頁。31 凸集D, 點 XD，若找不到兩個(lin )不同的點X(1) , X(2) D 使得 X= X(1) +(1- ) X(2) (0 1) 則稱X為 D的頂點。定義(dngy)3頂點(dngdin)第31頁/共35頁第三十一頁，共36頁。32定理1 1：LPLP問題的可行(

14、kxng)(kxng)解域一定是凸集。？第32頁/共35頁第三十二頁，共36頁。33定理2 2：線性規(guī)劃問題(wnt)(wnt)的基可行解對應線性 規(guī)劃問題(wnt)(wnt)可行域（凸集）的頂點。引理2 2：D D為有界凸多面集， X XD D，X X必可表 為D D的頂點(dngdin)(dngdin)的凸組合 。定理(dngl)3：可行域有界，最優(yōu)值必可在頂點得到第33頁/共35頁第三十三頁，共36頁。34定理2：LP有最優(yōu)解，必定可以在可行域(凸多面集)的頂點(dngdin)得到。定理3：可行域中點X是頂點 X是基本可行解?？尚薪饣窘舛ɡ?：LP問題(wnt)的可行域一定是凸集(凸多面集)第34頁/共35頁第三十四頁，共36頁。35感謝您的觀賞(gunshng)第35頁/共35頁第三十五頁，共36頁。