西電工程優(yōu)化學習教案

1、會計學1西電工程西電工程(gngchng)優(yōu)化優(yōu)化第一頁，共121頁。產(chǎn)品甲產(chǎn)品乙設備能力（h）設備A3 32 26565設備B2 21 14040設備C0 03 37575利潤（元/件）1500150025002500第2頁/共121頁第二頁，共121頁。l決策變量決策變量(binling)：設變量：設變量(binling)xi為為第第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i1，2）。l約束條件：根據(jù)題意，兩種產(chǎn)品的生產(chǎn)受到約束條件：根據(jù)題意，兩種產(chǎn)品的生產(chǎn)受到設備能力（機時數(shù)）的限制。設備能力（機時數(shù)）的限制。l 對設備對設備A，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)，兩種產(chǎn)品生產(chǎn)

2、所占用的機時數(shù)不能超過不能超過65，于是可以得到不等式：，于是可以得到不等式：3 x1 + 2 x2 65；l 對設備對設備B，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)，兩種產(chǎn)品生產(chǎn)所占用的機時數(shù)不能超過不能超過40，于是可以得到不等式：，于是可以得到不等式：2 x1 + x2 40；第3頁/共121頁第三頁，共121頁。第4頁/共121頁第四頁，共121頁。00第5頁/共121頁第五頁，共121頁。x1 ,x2 的取值。第6頁/共121頁第六頁，共121頁。二二. .一般一般(ybn)(ybn)形式形式 目標函數(shù)：目標函數(shù)：Max(Min)z = c1x1 + c2x2 + + Max(Min)z = c

3、1x1 + c2x2 + + cnxncnxn 約束條件： a a1111x x1 1+ +a a1212x x2 2+ +a+a1n1nx xn n( =, )( =, )b b1 1a a2121x x1 1+ +a a2222x x2 2+ + +a a2n2nx xn n( =, )( =, )b b2 2 . . . . . . a am1m1x x1 1+ +a am2m2x x2 2 + + +a amnmnx xn n( =, )( =, )b bm m x x1 1 ，x x2 2 ， ，x xn n 0 0第7頁/共121頁第七頁，共121頁。三三. .線性規(guī)劃線性規(guī)劃(x

4、in xn(xin xn u u hu)hu)模型的標準形式模型的標準形式目標函數(shù)：目標函數(shù)：Max z = c1x1 + c2x2 + + cnxnMax z = c1x1 + c2x2 + + cnxn 約束條件：a a1111x x1 1 + + a a1212x x2 2 + + + + a a1n1nx xn n = = b b1 1a a2121x x1 1 + + a a2222x x2 2 + + + + a a2n2nx xn n = = b b2 2 . . . . . .a am1m1x x1 1 + a+ am2m2x x2 2 + + + a + amnmnx xn

5、n = = b bm m x x1 1 ，x x2 2 ， ，x xn n 0 0第8頁/共121頁第八頁，共121頁。線性規(guī)劃的標準形式的特點：目標最大化、約束為等式、決策變量均非負、右端項非負。 對于各種非標準形式的線性規(guī)劃問題，我們總可以(ky)通過以下變換，將其轉化為標準形式: 第9頁/共121頁第九頁，共121頁。1.1.極小化目標函數(shù)的問題極小化目標函數(shù)的問題 設目標函數(shù)為設目標函數(shù)為 Min f = c1x1 + c2x2 + + cnxn Min f = c1x1 + c2x2 + + cnxn 則可以令則可以令z z -f -f ，該極小化問，該極小化問 題與下題與下面面(x

6、i mian)(xi mian)的極大化問題有相同的最優(yōu)的極大化問題有相同的最優(yōu) 解，即解，即 Max z = -c1x1 - c2x2 - - cnxn Max z = -c1x1 - c2x2 - - cnxn 注：盡管以上兩個問題的最優(yōu)解相同，但他們注：盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數(shù)值卻相差一個符號，即最優(yōu)解的目標函數(shù)值卻相差一個符號，即 Min f Min f - Max z - Max z第10頁/共121頁第十頁，共121頁。 max z =x1+10 x2 x1 + 2x2 + x3=100 x1、x2 、 0 03X第11頁/共121頁第十一頁，共121頁

7、。max z=2x1+2x24x3+4x3”s.t. x1 + 3x23x3+3x3” x4 = 30 x1 + 2x24x3+ 4x3” + x5 = 80 x1、x2 、x3、x3” 、x4、x5 0第12頁/共121頁第十二頁，共121頁。b b RmRm A: A: m mn n 矩陣矩陣第13頁/共121頁第十三頁，共121頁。第14頁/共121頁第十四頁，共121頁。第15頁/共121頁第十五頁，共121頁。第16頁/共121頁第十六頁，共121頁。x2x1z* =27500z1=50 x1+100 x2=0BOACDz2=14000該問題該問題(wnt)有唯一最優(yōu)有唯一最優(yōu)解解x

8、1=50；x2=250 x1 + x23002x1 + x2400 x2250第17頁/共121頁第十七頁，共121頁。x2x1z1=50 x1+50 x2=0B點和點和C點所代表的坐點所代表的坐標同時標同時(tngsh)為最為最優(yōu)解，即該問題有無優(yōu)解，即該問題有無窮多最優(yōu)解窮多最優(yōu)解BOACDx1 + x23002x1 + x2400 x2250z* =27500z2=15000第18頁/共121頁第十八頁，共121頁。111z=32z=5OA2x1xx1x2 1x1 + 2x20第19頁/共121頁第十九頁，共121頁。第20頁/共121頁第二十頁，共121頁。第21頁/共121頁第二十一

9、頁，共121頁。第22頁/共121頁第二十二頁，共121頁。第23頁/共121頁第二十三頁，共121頁。第24頁/共121頁第二十四頁，共121頁。0，0）T稱稱X0為該線性規(guī)劃對應與基為該線性規(guī)劃對應與基B的一個基的一個基本解。本解。若一個可行解若一個可行解x又是基本解，則稱又是基本解，則稱x為基為基本可行解。本可行解。第25頁/共121頁第二十五頁，共121頁。第26頁/共121頁第二十六頁，共121頁。ABCDEOx1x22x1+3x2 =1004x1 + 2x2 =120基本解如下表基本解如下表 基基基本解基本解可行可行否否目標值目標值對應圖對應圖中的點中的點B1=(P1，P2)B2=

10、(P1，P3)B3=(P1，P4)B4=(P2，P3)B5=(P2，P4)B6=(P3，P4)X1=(20，20，0，0)TX2=(30，0，40，0)TX3=(50，0，0，80)TX4=(0，60，80，0)TX5=(0，100/3，0，160/3)TX6=(0，0，100，120)T 200180400/30BCDEAO第27頁/共121頁第二十七頁，共121頁。第28頁/共121頁第二十八頁，共121頁。第29頁/共121頁第二十九頁，共121頁。第30頁/共121頁第三十頁，共121頁。第31頁/共121頁第三十一頁，共121頁。第32頁/共121頁第三十二頁，共121頁。 1111

11、11111111,0,BNBBNBBNBBBBBNBBBBNBNBNBNBTTTTTTNNNTTTNTTTTTTTBNBTTTTNXAXbB NbXBXNXbXB bB NXXZC XCCC B b C B NXC XXC B bC B NCXC B B CZC B B CXC B NCXC B bXZC B B CC B NCX 11111111,BBBBNBBBNBBBTBTTTTTNBTTTTNTTTC B bXZC B B C B NCCC B bXXZC BB NCCC B bXZC B A CXC B b 第33頁/共121頁第三十三頁，共121頁。 11BBNTTTNZC B b

12、C B NCX10BNTTC B NC 0BX檢驗數(shù)檢驗數(shù)(evaluation index) 用非基變量表示目標函數(shù)用非基變量表示目標函數(shù)(hnsh)后，非基變量在目標函數(shù)后，非基變量在目標函數(shù)(hnsh)中的系數(shù)中的系數(shù)判別定理：判別定理：1）B為為LP的一個基，的一個基， 2） 則：對應于則：對應于B的基本解的基本解 必為必為LP的最優(yōu)解。的最優(yōu)解。1BTTC B AC 10B b 10BTTC B AC 10B b 第34頁/共121頁第三十四頁，共121頁。111111111111AX=1Z=X0A A( )BBBBBBTTTTTTTTTZC B ACXC B bBB bC B AC

13、C B bBB bC B b C B ACB bBT B 對應于對應于B的基本解的的基本解的目標函數(shù)值目標函數(shù)值檢驗數(shù)檢驗數(shù)(記為記為j)基基變變量量的的值值原約束方程用原約束方程用非基變量非基變量表示基變量表示基變量后后xj的新系數(shù)的新系數(shù)第35頁/共121頁第三十五頁，共121頁。第36頁/共121頁第三十六頁，共121頁。CjC1C2CmCm+1CnbCBXBx1x2xmxm+1xnc1x1100a1,m+1a1nb1c2x2010a2,m+1a2nb2cmxm001am,m+1amnbm -z0000m+1n-z0第37頁/共121頁第三十七頁，共121頁。第38頁/共121頁第三十八

14、頁，共121頁。第39頁/共121頁第三十九頁，共121頁。Cj6 4 0 0b CBXBx1 x2 x3 x4 0 0 x3x4 2 3 1 04 2 0 1100120100/2120/4(min) z6 4 0 00 列初始列初始(ch sh)單純形表單純形表第40頁/共121頁第四十頁，共121頁。 Cj 6400b CBXB x1 x2x3x4 0 x3021-1/24040/2 6x111/201/43030/(1/2)Z010-3/8180 第41頁/共121頁第四十一頁，共121頁。Cj6400bCBXBx1x2x3x446x1x2011/2-1/410-1/4 3/82020

15、Z00-1/2-5/4200以以2為主元素為主元素(yun s)進行迭代，得新的單純形表：進行迭代，得新的單純形表：第42頁/共121頁第四十二頁，共121頁。第43頁/共121頁第四十三頁，共121頁。第44頁/共121頁第四十四頁，共121頁。Cj50100000b CBXB x1 x2X3x4x5 0 x311100300300/1 0 x421010400400/1 0 x501001250250/1(min) z501000000 0 x31010-15050/1(min) 0 x42001-1150150/2 100 x201001250 Z50000-10025000 50 x1

16、1010-1500 0 x400-21150 100 x2010-01250 Z00-500-5027500 第45頁/共121頁第四十五頁，共121頁。Cj2100b CBXB x1x2x3x4 0 x3-11105100/2 0 x42-50110120/4(min) z21000 0 x30-3/211/21040/2(min) 2x11-5/201/2530/(1/2) Z060-110 第46頁/共121頁第四十六頁，共121頁。第47頁/共121頁第四十七頁，共121頁。Cj62108000bCBXB x1x2x3x4x5x6x70 x556-4-4100200 x63-32801

17、0250 x74-21300110 z6210800000 x521-208104600 x6-510201-2510 x34-21300110 Z-34220-2200-101000 x5110012120702x2-510201-2510 x3-601702-320 Z7600-660-2234210第48頁/共121頁第四十八頁，共121頁。第49頁/共121頁第四十九頁，共121頁。五、人工五、人工(rngng)變量法變量法(Artificial Variable Method)第50頁/共121頁第五十頁，共121頁。工工(rngng)變量變量xn+1，xn+m構造如下形式的線性規(guī)劃

18、問題（問構造如下形式的線性規(guī)劃問題（問題題B） max z=c1x1+c2x2+cnxnMxn+1Mxn+ma11x1+a12x2+a1nxn+xn+1 = b1a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0第51頁/共121頁第五十一頁，共121頁。第52頁/共121頁第五十二頁，共121頁。第53頁/共121頁第五十三頁，共121頁。Cj3-1-100-M-Mb CBXB x1 x2x3x4x5x6x70 x41-21100011-Mx6-4120-1103-Mx7-20100011

19、 z3-6M-1+M-1+3M0-M00 0 x43-20100-110-Mx60100-11-21-1x3-20100011 Z1-1+M00-M0-3M+1 0 x43001-22-512-1x20100-11-21-1x3-20100011 z1000-1-M+1-M-1 3x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39 Z000-1/3-1/3-M+1/3-M+2/32第54頁/共121頁第五十四頁，共121頁。第55頁/共121頁第五十五頁，共121頁。第56頁/共121頁第五十六頁，共121頁。第57頁/共121頁第五

20、十七頁，共121頁。Cj0000011b CBXB x1x2x3x4x5x6x70 x41-211000111x6-4120-11031x7-20100011 -w6-1-30100-40 x43-20100-1101x60100-11-210 x3-20100011 -w0-100103-10 x43001-22-512-1x20100-11-21-1x3-20100011 -w00000110第58頁/共121頁第五十八頁，共121頁。第59頁/共121頁第五十九頁，共121頁。 利用求解線性規(guī)劃問題基本可行解（極點）的方法來求解較大規(guī)模的問題是不可行的。單純形法的基本思路是有選擇地取基本

21、可行解，即是從可行域的一個(y )極點出發(fā)，沿著可行域的邊界移到另一個(y )相鄰的極點，要求新極點的目標函數(shù)值不比原目標函數(shù)值差。 第60頁/共121頁第六十頁，共121頁。單單 純純 形形 法法初始基本可行解初始基本可行解是否最優(yōu)解或是否最優(yōu)解或無限最優(yōu)解無限最優(yōu)解? ?結束結束沿邊界找新沿邊界找新的基本可行解的基本可行解NY單純形法的基本(jbn)過程第61頁/共121頁第六十一頁，共121頁。 例：用單純形法的基本思路解前例(qinl)的線性規(guī)劃問題 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4

22、= 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0第62頁/共121頁第六十二頁，共121頁。最優(yōu)解最優(yōu)解 x1 = 5 x2 = 25 x4 = 5（松弛（松弛(sn ch)標量，標量，表示表示B設備有設備有5個機時的剩余）個機時的剩余） 最優(yōu)值最優(yōu)值 z* = 70000 第63頁/共121頁第六十三頁，共121頁。第64頁/共121頁第六十四頁，共121頁。第65頁/共121頁第六十五頁，共121頁。第66頁/共121頁第六十六頁，共121頁。 . . . . am1 x1 + am2 x2 + + amn xn + am1 x1 + am2 x2

23、+ + amn xn + xn+m = bmxn+m = bm x1 x1 ，x2 x2 ， ，xn xn ，xn+1 xn+1 ， ，xn+m 0 xn+m 0第67頁/共121頁第六十七頁，共121頁。單單 純純 形形 法法第68頁/共121頁第六十八頁，共121頁。n .n am1x1+am2x2+ +amnxn+xn+m = bmn x1,x2 . xn ,xn+1,xn+m 0單單 純純 形形 法法第69頁/共121頁第六十九頁，共121頁。 結論：若得到的最優(yōu)解滿足結論：若得到的最優(yōu)解滿足 xn+i=0 xn+i=0 i=1 , , m i=1 , , m 則是原問題的基本可行則是

24、原問題的基本可行(kxng)(kxng)解解; ;否則，原問題無可行否則，原問題無可行(kxng)(kxng)解。解。 得到原問題的基本可行得到原問題的基本可行(kxng)(kxng)解后，解后，第二階段求解原問題。第二階段求解原問題。單單 純純 形形 法法第70頁/共121頁第七十頁，共121頁。第71頁/共121頁第七十一頁，共121頁。第72頁/共121頁第七十二頁，共121頁。523-1-M-MCB XB x1x2x3x4x5x6i -Mx5151230105-Mx62021(5)0014-1x4261241006.5-z35M+263M+63M+48M+7000-Mx53-1/5(7

25、/5)001-3/515/73x342/51/51001/520-1x410-3/56/5010-4/525/3-z3M-2-M/5+16/5 7/5M+13/5000-8/5M-7/52x215/7-1/71005/7-3/73x325/7(3/7)010-1/72/725/3-1x452/7-3/7001-6/7-2/7-z-53/725/7000-M-13/7-M-2/72x210/3011/302/3-1/35x125/3107/30-1/32/3-1x4110011-10-z-112/300-25/30-M-2/3-M+8/3大大M M法法 （LP - M） 得到(d do)最優(yōu)解：

26、(25/3，10/3，0，11)T 最優(yōu)目標值：112/3第73頁/共121頁第七十三頁，共121頁。第74頁/共121頁第七十四頁，共121頁。0000-1-1CB XB x1x2x3x4x5x6i -1x5151230105-1x62021(5)00140 x4261241006.5-z35338000-1x53-1/5(7/5)001-3/515/70 x342/51/51001/5200 x410-3/56/5010-4/525/3-z3-1/57/5000-8/50 x215/7-1/71005/7-3/70 x325/73/7010-1/72/725/30 x452/7-3/700

27、1-6/7-2/7-z00000-1-1第一階段第一階段 (LP - 1）得到原問題(wnt)的基本可行解:(0，15/7，25/7，52/7)T第75頁/共121頁第七十五頁，共121頁。523-1CB XB x1x2x3x4i 2x215/7-1/71003x325/7(3/7)01025/3-1x452/7-3/7001-z-53/725/70002x210/3011/305x125/3107/30-1x4110011-z-112/300-25/30第二階段第二階段 把基本把基本(jbn)(jbn)可行解填可行解填入表中入表中得到(ddo)原問題的最優(yōu)解:(25/3，10/3，0，11)

28、T最優(yōu)目標值：112/3第76頁/共121頁第七十六頁，共121頁。第77頁/共121頁第七十七頁，共121頁。第78頁/共121頁第七十八頁，共121頁。產(chǎn)品甲產(chǎn)品乙設備能力（h）設備A3 32 26565設備B2 21 14040設備C0 03 37575利潤（元/件）1500150025002500第79頁/共121頁第七十九頁，共121頁。第80頁/共121頁第八十頁，共121頁。第81頁/共121頁第八十一頁，共121頁。第82頁/共121頁第八十二頁，共121頁。第83頁/共121頁第八十三頁，共121頁。第84頁/共121頁第八十四頁，共121頁。第85頁/共121頁第八十五頁，

29、共121頁。解 先將約束條件變形(bin xng)為“”形式?jīng)]有非負限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxz第86頁/共121頁第八十六頁，共121頁。沒有非負限制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx再根據(jù)(gnj)非對稱形式的對應關系，直接寫出對偶規(guī)劃第87頁/共121頁第八十七頁，共121頁。0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf

30、沒有非負限制第88頁/共121頁第八十八頁，共121頁。 定理3-1 (弱對偶(du u)定理） 若 x, y 分別為（LP) 和（DP）的可行解，那么cTx bTy。 推論 若（LP）可行，那么（LP）無有限(yuxin)最優(yōu)解的充分必要條件是（LD）無可行解。第89頁/共121頁第八十九頁，共121頁。 定理3-3 (主對偶(du u)定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。 以上定理、推論對任意形式的相應性規(guī)劃(guhu)的對偶均有效第90頁/共121頁第九十頁，共121頁。第91頁/共121頁第九十一頁，共121頁。第92頁/共121頁第九十

31、二頁，共121頁。靈敏度分析一節(jié)中討論。第93頁/共121頁第九十三頁，共121頁。第94頁/共121頁第九十四頁，共121頁。50100000CB XB x1x2x3x4x5i 0 x3300111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50- -c cB BT TB B-1-1I IB B=(p p1

32、1, p, p4 4,p,p2 2 )oTB B-1-1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價格 y1 = 50 y2 = 0 y3 = 50 , B-1對應(duyng)的檢驗數(shù) T = cBTB-1 。第95頁/共121頁第九十五頁，共121頁。 對偶單純形法的基本思想 對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應著一個對偶可行解（檢驗(jinyn)數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗(jinyn)原規(guī)劃的基本解是否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應著另一個對偶可

33、行解（檢驗(jinyn)數(shù)非正）。第96頁/共121頁第九十六頁，共121頁。 如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗(jinyn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，當同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原 規(guī)劃的最優(yōu)解。第97頁/共121頁第九十七頁，共121頁。 對偶單純形法在什么情況下使用 ： 應用前提：有一個基，其對應的基滿足: 單純形表的檢驗數(shù)行全部非正（對偶可行）； 變量取值可有負數(shù)（非可行解）。 注：通過矩陣行變換運算，使所有相應(xingyng)變量取值均為非負數(shù)即得到最優(yōu)單純形表。第

34、98頁/共121頁第九十八頁，共121頁。 對偶對偶(du u)(du u)單純形法求解線性單純形法求解線性規(guī)劃問題規(guī)劃問題過程：過程：第99頁/共121頁第九十九頁，共121頁。 標準化：標準化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 第100頁/共121頁第一百頁，共121頁。ci -2-3-400cb xbb

35、x1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301j -2-3-4000 x4-10-5/2 1/21-1/2-2x121-1/2 3/20-1/2j 0-4-10-1-3x2 2/501-1/5 -2/5 1/5-2x1 11/5107/5 -1/5 -2/5j 00-9/5 -8/5 -1/5第101頁/共121頁第一百零一頁，共121頁。是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應原規(guī)劃的基本解是可行的典式對應原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0 第110頁/共121頁第一百一十頁，共121頁。s.t.s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5