西电工程优化学习教案

1、会计学1西电工程西电工程(gngchng)优化优化第一页，共121页。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500第2页/共121页第二页，共121页。l决策变量决策变量(binling)：设变量：设变量(binling)xi为为第第i种（甲、乙）产品的生产件数（种（甲、乙）产品的生产件数（i1，2）。l约束条件：根据题意，两种产品的生产受到约束条件：根据题意，两种产品的生产受到设备能力（机时数）的限制。设备能力（机时数）的限制。l 对设备对设备A，两种产品生产所占用的机时数，两种产品生产

2、所占用的机时数不能超过不能超过65，于是可以得到不等式：，于是可以得到不等式：3 x1 + 2 x2 65；l 对设备对设备B，两种产品生产所占用的机时数，两种产品生产所占用的机时数不能超过不能超过40，于是可以得到不等式：，于是可以得到不等式：2 x1 + x2 40；第3页/共121页第三页，共121页。第4页/共121页第四页，共121页。00第5页/共121页第五页，共121页。x1 ,x2 的取值。第6页/共121页第六页，共121页。二二. .一般一般(ybn)(ybn)形式形式 目标函数：目标函数：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页。三三. .线性规划线性规划(x

4、in xn(xin xn u u hu)hu)模型的标准形式模型的标准形式目标函数：目标函数：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页。线性规划的标准形式的特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以(ky)通过以下变换，将其转化为标准形式: 第9页/共121页第九页，共121页。1.1.极小化目标函数的问题极小化目标函数的问题 设目标函数为设目标函数为 Min f = c1x1 + c2x2 + + cnxn Min f = c1x1 + c2x2 + + cnxn 则可以令则可以令z z -f -f ，该极小化问，该极小化问 题与下题与下面面(x

6、i mian)(xi mian)的极大化问题有相同的最优的极大化问题有相同的最优 解，即解，即 Max z = -c1x1 - c2x2 - - cnxn Max z = -c1x1 - c2x2 - - cnxn 注：尽管以上两个问题的最优解相同，但他们注：尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即最优解的目标函数值却相差一个符号，即 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)有唯一最优有唯一最优解解x

8、1=50；x2=250 x1 + x23002x1 + x2400 x2250第17页/共121页第十七页，共121页。x2x1z1=50 x1+50 x2=0B点和点和C点所代表的坐点所代表的坐标同时标同时(tngsh)为最为最优解，即该问题有无优解，即该问题有无穷多最优解穷多最优解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为该线性规划对应与基为该线性规划对应与基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检验数检验数(evaluation index) 用非基变量表示目标函数用非基变量表示目标函数(hnsh)后，非基变量在目标函数后，非基变量在目标函数(hnsh)中的系数中的系数判别定理：判别定理：1）B为为LP的一个基，的一个基， 2） 则：对应于则：对应于B的基本解的基本解 必为必为LP的最优解。的最优解。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的基本解的的基本解的目标函数值目标函数值检验数检验数(记为记为j)基基变变量量的的值值原约束方程用原约束方程用非基变量非基变量表示基变量表示基变量后后xj的新系数的新系数第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构造如下形式的线性规划

18、问题（问构造如下形式的线性规划问题（问题题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页。 利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本

21、可行解，即是从可行域的一个(y )极点出发，沿着可行域的边界移到另一个(y )相邻的极点，要求新极点的目标函数值不比原目标函数值差。 第60页/共121页第六十页，共121页。单单 纯纯 形形 法法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯形法的基本(jbn)过程第61页/共121页第六十一页，共121页。 例：用单纯形法的基本思路解前例(qinl)的线性规划问题 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页。最优解最优解 x1 = 5 x2 = 25 x4 = 5（松弛（松弛(sn ch)标量，标量，表示表示B设备有设备有5个机时的剩余）个机时的剩余） 最优值最优值 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页。 结论：若得到的最优解满足结论：若得到的最优解满足 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)最优解：

26、(25/3，10/3，0，11)T 最优目标值：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)原问题的最优解:(25/3，10/3，0，11)

28、T最优目标值：112/3第76页/共121页第七十六页，共121页。第77页/共121页第七十七页，共121页。第78页/共121页第七十八页，共121页。产品甲产品乙设备能力（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)为“”形式没有非负限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxz第86页/共121页第八十六页，共121页。没有非负限制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx再根据(gnj)非对称形式的对应关系，直接写出对偶规划第87页/共121页第八十七页，共121页。0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf

30、没有非负限制第88页/共121页第八十八页，共121页。 定理3-1 (弱对偶(du u)定理） 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx bTy。 推论 若（LP）可行，那么（LP）无有限(yuxin)最优解的充分必要条件是（LD）无可行解。第89页/共121页第八十九页，共121页。 定理3-3 (主对偶(du u)定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等。 以上定理、推论对任意形式的相应性规划(guhu)的对偶均有效第90页/共121页第九十页，共121页。第91页/共121页第九十一页，共121页。第92页/共121页第九十

31、二页，共121页。灵敏度分析一节中讨论。第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最优解 x1 = 50 x2 = 250 x4 = 50影子价格 y1 = 50 y2 = 0 y3 = 50 , B-1对应(duyng)的检验数 T = cBTB-1 。第95页/共121页第九十五页，共121页。 对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验(jinyn)数非正），所以也可以说是从一个对偶可行解出发；然后检验(jinyn)原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可

33、行解（检验(jinyn)数非正）。第96页/共121页第九十六页，共121页。 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验(jinyn)数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原 规划的最优解。第97页/共121页第九十七页，共121页。 对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应(xingyng)变量取值均为非负数即得到最优单纯形表。第

34、98页/共121页第九十八页，共121页。 对偶对偶(du u)(du u)单纯形法求解线性单纯形法求解线性规划问题规划问题过程：过程：第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页。是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法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