运筹学优化建摸课件

1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件绪绪 论论IntroductionIntroduction第第2页页线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析运筹学的主要内容第第3页页线性规划模型（1）线性(linear programming)规划主要解决：如何利用现有的资

2、源，使得预期目标达到最优。某公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利 润最大？第第4页页项目每天可用能力设备A (h)设备B (h)调试工序(h)06152115245利润（元）21表1-1解：设公司制造、两种家电分别为 件。 ,1x2x问题：x1=? x2=? 利润Z 最大？线性规划模型（1）第第5页页线性规划模型设备A工时限制：1552x设备B工时限制：242621 xx项目每天可用能力设备A (h)设备B (h)调试工序(h)061521

3、15245利润（元）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 也不区分变量中的大小写字符 (实际上任何小写字符都将被转换为大写字符);约束条件中的“=” 可用“” 代

4、替.上述问题用键盘输入如下 线性规划模型（1）212maxxxZ0,524261552121212xxxxxxx第第9页页：MAX 2X1+3X2? ST( 说明:也可写成S.T., SUCH THAT 或 SUBJECT TO 等）? 5X215? 6X1+2X224 ? X1+X215? x12+x13+x14+x21+x22+x2310? x13+x14+x22+x23+x31+x3220? x14+x23+x32+x4112? end: go线性规划模型（2）第第16页页LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 118

5、400.0 VARIABLE VALUE REDUCED COST X11 3.000000 0.000000 X21 0.000000 2800.000000 X31 8.000000 0.000000 X41 0.000000 1100.000000 X12 0.000000 1700.000000 X22 0.000000 1700.000000 X32 0.000000 0.000000 X13 0.000000 400.000000 X23 0.000000 1500.000000 X14 12.000000 0.000000线性规划模型（2）第第17页页整 数 规 划 在许多线性规

6、划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等. 对于一个规划问题,如果要求全部决策变量都取整数,称为纯(或全)整数规划;如果仅要求部分决策变量取整数,称为混合整数规划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规划问题. 整数规划(integer programming)简称为IP问题.这里主要讨论的是整数线性规划问题,简称为ILP问题.第第18页页例2.0.1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见表2.1.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510

7、托运限制/集装箱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）INTEGER Vname 或GIN Vname表示将变量Vname标示为0-

8、1型或为一般整数变量。2）INT n 或GIN n表示将当前模型中前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+x31? x1-x2+6x3+4x48? 5x1+3x2+x45? end: int 4: goLINDO输出下列结果： 第第26页页 LP OPTIMUM FOUND AT STEP 4 OBJECTIVE V

9、ALUE = 2.10526323 NEW INTEGER SOLUTION OF 3.00000000 AT BRANCH 0 PIVOT 4 RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 3.000000 VARIABLE VALUE REDUCED COST X1 1.000000 3.000000 X2 0.000000 7.000000 X3 1.000000 -1.000000 X4 1.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.0

10、00000 3) 3.000000 0.000000 4) 1.000000 0.000000第第27页页例例5 求解下列整数线性规划问题egersxxxxxxxxxxxxxt sxxxxxxfjint, 0200006*0542332516100006554433221*0. .654321min在LINDO中输入下列命令：第第28页页: MIN X1+X2+X3+X4+X5+X6? ST? X2+2X3+3X4+4X5+5X610000? 6X1+5X2+3X3+2X4+X520000? END: GIN 6: GOLINDO运行后输出以下结果：STATUS：OPTIMALLP OPTIM

11、UM FOUND AT STEP 3OBJECTIVE VALUE = 5200.00000第第29页页FIX ALL VARS.(4) WITH RC 0.400000E-01 NEW INTEGER SOLUTION OF 5200.00000 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 5200.000 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 5200.000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4000.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 0.000000 1.000000 X6 1200.000000 1.000