运筹帷幄之中决胜千里之外运筹学课件绪论

第1页运筹帷幄之中决胜千里之外运筹学课件绪论Introduction第2页线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容第3页线性规划模型（1）线性(linearprogramming)规划主要解决：如何利用现有的资源，使得预期目标达到最优。某公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？第4页项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1解：设公司制造Ⅰ、Ⅱ两种家电分别为件。,1x2x问题：x1=?x2=?利润Z最大？线性规划模型（1）第5页线性规划模型设备A工时限制：1552x设备B工时限制：242621xx项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1第6页项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1线性规划模型调试工序时间限制：521xx利润：212xxZ即要求：212maxxxZ第7页212maxxxZ目标函数约束条件资源约束非负约束0,524261552121212xxxxxxx线性规划模型（1）第8页初试LINDO解如下LP问题:LINDO中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO也不区分变量中的大小写字符(实际上任何小写字符都将被转换为大写字符);约束条件中的“=”及“=”可用“”及“”代替.上述问题用键盘输入如下线性规划模型（1）212maxxxZ0,524261552121212xxxxxxx第9页：MAX2X1+3X2?ST(说明:也可写成S.T.,SUCHTHAT或SUBJECTTO等）?5X215?6X1+2X224?X1+X25?END：GO线性规划模型（1）第10页线性规划模型（3）LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)8.500000VARIABLEVALUEREDUCEDCOSTX13.5000000.000000X21.5000000.000000ROWSLACKORSURPLUSDUALPRICES2)7.5000000.0000003)0.0000000.2500004)0.0000000.500000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?第11页线性规划模型（2）捷运公司在下一年度的1～4月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。第12页线性规划模型（2）月份1234所需仓库面积15102012表1-2表1-3合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300单位：100m2单位；元/100m2解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。ijx第13页ⅠⅡⅢⅣⅤ11x12x13x14x21x22x23x31x32x41x∑≥15∑≥10∑≥20∑≥121514131211xxxx10232221141312xxxxxx1241322314xxxx20323123221413xxxxxx2800Z)(41312111xxxx4500)(322212xxx6000)(2313xx147300x第14页)4,,1;4,,1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij)(4500)(2800min32221241312111xxxxxxxZ1423137300)(6000xxx目标函数约束条件线性规划模型（2）第15页:min2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13+6000x23+7300x14?st?x11+x12+x13+x1415?x12+x13+x14+x21+x22+x2310?x13+x14+x22+x23+x31+x3220?x14+x23+x32+x4112?end:go线性规划模型（2）第16页LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)118400.0VARIABLEVALUEREDUCEDCOSTX113.0000000.000000X210.0000002800.000000X318.0000000.000000X410.0000001100.000000X120.0000001700.000000X220.0000001700.000000X320.0000000.000000X130.000000400.000000X230.0000001500.000000X1412.0000000.000000线性规划模型（2）第17页整数规划在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等.对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题.整数规划(integerprogramming)简称为IP问题.这里主要讨论的是整数线性规划问题,简称为ILP问题.第18页例2.0.1某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见表2.1.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413表2.1第19页表2.1货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱2413解设分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题.其数学模型为:21,xx211020maxxxZ整数,0,13522445.212121xxxxxxts第20页求解整数规划IP（整数规划）问题的输入与LP类似，但在END标志后需定义整型变量。0-1型整数变量可用INTEGER（可简写为INT）命令来标示；其它整数变量可用GIN命令来标示.标示方法有两种：1）INTEGERVname或GINVname表示将变量Vname标示为0-1型或为一般整数变量。2）INTn或GINn表示将当前模型中前n个变量标示为0-1型变量或为一般整数变量。第21页例3求解0-1整数规划1,0,,6434422.523max3213221321321321xxxxxxxxxxxxxtsxxxz第22页:max3x1-2x2+5x3?st?x1+2x2-x32?x1+4x2+x34?x1+x23?4x2+x36?end:intx1:intx2:intx3:goInt3LINDO输出下列结果：第23页LPOPTIMUMFOUNDATSTEP2OBJECTIVEVALUE=8.00000000NEWINTEGERSOLUTIONOF8.00000000ATBRANCH0PIVOT2RE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)8.000000VARIABLEVALUEREDUCEDCOSTX11.000000-3.000000X20.0000002.000000X31.000000-5.000000ROWSLACKORSURPLUSDUALPRICES2)2.0000000.0000003)2.0000000.0000004)2.0000000.0000005)5.0000000.000000第24页例4求解0-1整数规划1,0,,,53584612.73min4321421432143214321xxxxxxxxxxxxxxxtsxxxxz在LINDO中输入下列命令：第25页:min3x1+7x2-x3+x4?st?2x1-x2+x3-x41?x1-x2+6x3+4x48?5x1+3x2+x45?end:int4:goLINDO输出下列结果：第26页LPOPTIMUMFOUNDATSTEP4OBJECTIVEVALUE=2.10526323NEWINTEGERSOLUTIONOF3.00000000ATBRANCH0PIVOT4RE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)3.000000VARIABLEVALUEREDUCEDCOSTX11.0000003.000000X20.0000007.000000X31.000000-1.000000X41.0000001.000000ROWSLACKORSURPLUSDUALPRICES2)1.0000000.0000003)3.0000000.0000004)1.0000000.000000第27页例5求解下列整数线性规划问题egersxxxxxxxxxxxxxtsxxxxxxfjint,0200006*0542332516100006554433221*0..654321min在LINDO中输入下列命令：第28页:MINX1+X2+X3+X4+X5+X6?ST?X2+2X3+3X4+4X5+5X610000?6X1+5X2+3X3+2X4+X520000?END:GIN6:GOLINDO运行后输出以下结果：STATUS：OPTIMALLPOPTIMUMFOUNDATSTEP3OBJECTIVEVALUE=5200.00000第29页FIXALLVARS.(4)WITHRC0.400000E-01NEWINTEGERSOLUTIONOF5200.00000ATBRANCH0PIVOT3BOUNDONOPTIMUM:5200.000ENUMERATIONCOMPLETE.BRANCHES=0PIVOTS=3LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)5200.000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X24000.0000001.000000X30.0000001.000000X40.0000001.000000X50.0000001.000000X61200.0000001.000000第30页•何坚勇，运筹学基础，清华大学出版社，北京，2000年•现代应用数学手册，运筹学与最优化理论卷清华大学出版社，北京，1999年•罗荣桂，新编运筹学题解，华中科技大学出版社，武汉，2002年•梁工谦，运