优化建摸

nullnull运 筹 学 课 件Introductionnull线性规划数 学 规 划非线性规划整数规划动态规划学 科 内 容多目标规划双层规划组 合 优 化最优计数问网络优化排序问题统筹图随 机 优 化对策论排队论库存论决策可靠性分析运筹学的主要内容null线性规划模型（1）线性(linear programming)规划主要解决：如何利用现有的 资源，使得预期目标达到最优。某公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件 时分别占用的设备A、B的台时、调试工序及每天可用于 这两种家电的能力、各售出一件时的获利情况，如1-1 所示。问该公司应制造两种家电各多少件，使获取的利 润最大？null表1-1解：设公司制造Ⅰ、Ⅱ两种家电分别为 件。 问题：x1=? x2=? 利润Z 最大？线性规划模型（1）null线性规划模型设备A工时限制：设备B工时限制：表1-1null表1-1线性规划模型调试工序时间限制：利润：即要求：null目标函数约束条件资源约束非负约束线性规划模型（1）null初试 LINDO解如下LP 问题 : LINDO 中己假设所有的变量都是非负的,所以非负约束条件不 必再输入到计算机中;LINDO 也不区分变量中的大小写字符 (实际上任何小写字符都将被转换为大写字符);约束条件中的 “<=”及“>=” 可用“<” 及 “>” 代替.上述问题用键盘输入如下 线性规划模型（1）null：MAX 2X1+3X2 ? ST( 说明:也可写成S.T., SUCH THAT 或 SUBJECT TO 等）? 5X2<15 ? 6X1+2X2<24 ? X1+X2<5 ? END ：GO线性规划模型（1）null线性规划模型（3）LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 8.500000 VARIABLE VALUE REDUCED COST X1 3.500000 0.000000 X2 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 7.500000 0.000000 3) 0.000000 0.250000 4) 0.000000 0.500000 NO. ITERATIONS= 2 DO RANGE(SENSITIVITY) ANALYSIS? null线性规划模型（2）捷运公司在下一年度的1～4月份的4个月内拟租用仓库堆放物 资。已知各月份所需仓库面积列于下表1-2。仓库租借费用 随合同期而定，期限越长，折扣越大，具体数字见表1-3。 租借仓库的合同每月初都可办理，每份合同具体规定租用面 积和期限。因此该厂可根据需要，在任何一个月初办理租借 合同。每次办理时可签一份合同，也可签若干份租用面积和 租用期限不同的合同。试确定该公司签订租借合同的最优决 策，目的是使所租借费用最少。null线性规划模型（2）表1-2表1-3单位：100m2单位；元/100m2解：设 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。 nullⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12null目标函数约束条件线性规划模型（2）null: min2800x11+2800x21+2800x31+2800x41+4500x12 +4500x22+4500x32+6000x13+6000x23+7300x14 ? st ? x11+x12+x13+x14>15 ? x12+x13+x14+x21+x22+x23>10 ? x13+x14+x22+x23+x31+x32>20 ? x14+x23+x32+x41>12 ? end : go线性规划模型（2）nullLP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 118400.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）null整 数 规 划 在许多线性规划问题中,要求最优解必须取整数.例如 所求的解是机器的台数、人数车辆船只数等. 对于一个规 划问题,如果要求全部决策变量都取整数,称为纯(或全)整 数规划;如果仅要求部分决策变量取整数,称为混合整数规 划问题.有的问题要求决策变量仅取0或l两个值,称为0-l规 划问题. 整数规划(integer programming)简称为IP问题.这里主 要讨论的是整数线性规划问题,简称为ILP问题.null例2.0.1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、 重量、可获利润以及托运所受限制见表2.1.问每集装箱中 两种货物各装多少箱,可使所获利润最大?表2.1null解 设 分别为甲、乙两种货物的托运箱数.则这是一个 纯整数规划问题 .其数学模型为:null求解整数规划IP（整数规划）问题的输入与LP类似，但在END标志后 需定义整型变量。0-1型整数变量可用INTEGER（可简写为INT）命令来标 示；其它整数变量可用GIN命令来标示.标示方法有两种：1）INTEGER Vname 或GIN Vname 表示将变量Vname标示为0-1型或为一般整数变量。2）INT n 或GIN n表示将当前模型中前n个变量标示为0-1型变量或为一般整数变量。null例3 求解0-1整数规划null: max3x1-2x2+5x3 ? st ? x1+2x2-x3<2 ? x1+4x2+x3<4 ? x1+x2<3 ? 4x2+x3<6 ? end : int x1 : int x2 : int x3 : goInt 3LINDO输出下列结果： null LP OPTIMUM FOUND AT STEP 2 OBJECTIVE VALUE = 8.00000000 NEW INTEGER SOLUTION OF 8.00000000 AT BRANCH 0 PIVOT 2 RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 8.000000 VARIABLE VALUE REDUCED COST X1 1.000000 -3.000000 X2 0.000000 2.000000 X3 1.000000 -5.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 2.000000 0.000000 3) 2.000000 0.000000 4) 2.000000 0.000000 5) 5.000000 0.000000null例4 求解0-1整数规划在 LINDO 中输入下列命令：null: min3x1+7x2-x3+x4 ? st ? 2x1-x2+x3-x4>1 ? x1-x2+6x3+4x4>8 ? 5x1+3x2+x4>5 ? end : int 4 : goLINDO输出下列结果： null LP OPTIMUM FOUND AT STEP 4 OBJECTIVE VALUE = 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.000000 3) 3.000000 0.000000 4) 1.000000 0.000000null例5 求解下列整数线性规划问题在LINDO中输入下列命令：null: MIN X1+X2+X3+X4+X5+X6 ? ST ? X2+2X3+3X4+4X5+5X6>10000 ? 6X1+5X2+3X3+2X4+X5>20000 ? END : GIN 6 : GOLINDO运行后输出以下结果：STATUS：OPTIMAL LP OPTIMUM FOUND AT STEP 3 OBJECTIVE VALUE = 5200.00000nullFIX 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.000000null何坚勇，运筹学基础， 清华大学出版社，北京，2000年 现代应用数学手册，运筹学与最优化理论卷 清华大学出版社，北京，1999年 罗荣桂，新编运筹学题解， 华中科技大学出版社，武汉，2002年 梁工谦，运筹学典型解析及测， 西北工业大学出版社，西安，2002年 徐永仁，运筹学试题精选与答题技巧， 哈尔滨工业大学出版社，哈尔滨，2000年参 考 资 料