运筹学优化建摸.ppt

第*页 运 筹 帷 幄 之 中 决 胜 千 里 之 外 运 筹 学 课 件 绪 论 Introduction 线性规划 数 学 规 划 非线性规划 整数规划 动态规划 学 科 内 容 多目标规划 双层规划 组 合 优 化 最优计数问题 网络优化 排序问题 统筹图 随 机 优 化 对策论 排队论 库存论 决策分析 可靠性分析 运筹学的主要内容 线性规划模型（1） 线性(linear programming)规划主要解决：如何利用现有的 资源，使得预期目标达到最优。 某公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件 时分别占用的设备A、B的台时、调试工序及每天可用于 这两种家电的能力、各售出一件时的获利情况，如表1-1 所示。问该公司应制造两种家电各多少件，使获取的利 润最大？ 1 2 利润（元） 15 24 5 5 2 1 0 6 1 设备A (h) 设备B (h) 调试工序(h) 每天可用能力 Ⅱ Ⅰ 项目 表1-1 解：设公司制造Ⅰ、Ⅱ两种家电分别为 件。 问题：x1=? x2=? 利润Z 最大？ 线性规划模型（1） 线性规划模型 设备A工时限制： 设备B工时限制： 1 2 利润（元） 15 24 5 5 2 1 0 6 1 设备A (h) 设备B (h) 调试工序(h) 每天可用能力 Ⅱ Ⅰ 项目 表1-1 1 2 利润（元） 15 24 5 5 2 1 0 6 1 设备A (h) 设备B (h) 调试工序(h) 每天可用能力 Ⅱ Ⅰ 项目 表1-1 线性规划模型 调试工序时间限制： 利润： 即要求： 目标函数 约束条件 资源约束 非负约束 线性规划模型（1） 初试 LINDO 解如下LP 问题 : LINDO 中己假设所有的变量都是非负的,所以非负约束条件不 必再输入到计算机中;LINDO 也不区分变量中的大小写字符 (实际上任何小写字符都将被转换为大写字符);约束条件中的 “=”及“=” 可用“” 及 “” 代替.上述问题用键盘输入如下 线性规划模型（1） ：MAX 2X1+3X2 ? ST ( 说明:也可写成S.T., SUCH THAT 或 SUBJECT TO 等） ? 5X215 ? 6X1+2X224 ? X1+X25 ? END ：GO 线性规划模型（1） 线性规划模型（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? 线性规划模型（2） 捷运公司在下一年度的1～4月份的4个月内拟租用仓库堆放物 资。已知各月份所需仓库面积列于下表1-2。仓库租借费用 随合同期而定，期限越长，折扣越大，具体数字见表1-3。 租借仓库的合同每月初都可办理，每份合同具体规定租用面 积和期限。因此该厂可根据需要，在任何一个月初办理租借 合同。每次办理时可签一份合同，也可签若干份租用面积和 租用期限不同的合同。试确定该公司签订租借合同的最优决 策，目的是使所租借费用最少。 线性规划模型（2） 15 10 20 12 所需仓库面积 1 2 3 4 月份 表1-2 表1-3 2800 4500 6000 7300 合同期内的租费 1个月 2个月 3个月 4个月 合同租借期限 单位：100m2 单位；元/100m2 解：设 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ ∑≥15