第7章 整数线性规划.ppt

* 第7章 整数线性规划 7.1 整数线性规划的分类 全整数线性规划：所有变量均为整数。 混合整数线性规划：有一些变量是整数而非全部都是。 0-1整数线性规划：整数变量只取0或1。 7.2 全整数线性规划的图解法与计算机解法 (P200) 7.2.1 LP松弛的图解法 7.2.2 近似整数解的获得 T=2, A=3, z=65 T=3, A=3, 不可行 T=2, A=4, 不可行 7.2.3 全整数解的图解法 7.2.4 计算机解法 7.3 含有0-1变量的整数线性规划的应用 7.3.1 资金预算 爱斯柯德冰箱公司的估计净现值、资金需求和4年内的可用资金 （单位：千美元） 35 10 4 5 15 第4年资金需求 40 10 20 20 第3年资金需求 50 10 15 20 第2年资金需求 40 15 10 10 15 第1年资金需求 37 10 40 90 净现值 新产品研发 机器更新 仓库扩建 工厂扩建 可用 资金 总额 项目 工厂扩建方案如果通过，P=1； 如果否决，P取0。 仓库扩建方案如果通过，W=1； 如果否决，W取0。 机器更新方案如果通过，M=1； 如果否决，M取0。 新产品研发方案如果通过，R=1； 如果否决，R取0。 7.3.2 固定成本核算 RMC问题 40 25 50 最大生产量（吨） 400 50 200 固定成本（美元） 50 30 40 利润（美元/吨） 21 0.3 0.3 0.6 原料3 5 0.1 0.2 原料2 20 0.6 0.5 0.4 原料 1 可用吨数 地板清洁剂 溶剂 燃料添加剂 F: 生产的燃料添加剂的吨数 S: 生产的溶剂的吨数 C: 生产的地板清洁剂的吨数 如果生产燃料添加剂，SF=1， 否则，SF=0； 如果生产溶剂，则 SS=1， 否则，SS=0； 如果生产地板清洁剂，SC=1， 否则，SC=0。 7.3.3 分布系统设计 40000 500000 堪萨斯城 30000 375000 丹佛 20000 300000 托莱多 10000 175000 底特律 年生产能力（件） 年固定成本（美元） 目标工厂 20000 休斯敦 20000 亚特兰大 30000 波士顿 年需求量（件） 分销中心 马丁贝克分布系统的单位运输成本 3 4 8 圣路易斯 2 4 10 堪萨斯城 5 7 9 丹佛 4 3 4 托莱多 3 2 5 底特律 休斯敦 亚特兰大 波士顿 分销中心 工厂地点 如果在底特律建厂， 否则， 如果在托莱多建厂， 否则， 如果在丹佛建厂， 否则， 如果在堪萨斯城建厂， 否则， 7.3.4 银行选址 俄亥俄州信托公司的扩展区 11,14,19 20 卡罗尔 3,8,9,11,12,13 10 萨米特 11,18,20 19 塔斯卡卢斯 3,4,7,8,10 9 梅迪纳 7,8,11,17,19 18 霍姆斯 7,9,10,11,18 8 韦恩 6,7,18 17 诺克斯 4,5,6,8,9,17,18 7 阿什兰 1,12,13,15 16 特兰伯尔 5,7,17 6 里奇兰 11,13,14,16 15 马霍宁 4,6,7 5 休伦 11,15,20 14 哥伦比亚纳 3,5,7,9 4 洛雷恩 3,10,11,12,15,16 13 波帝奇 2,4,9,10,12,13 3 凯霍加 1,2,3,10,13,16 12 吉奥特 1,3,12 2 莱克 8,10,13,14,15,18,19,20 11 斯塔克 2,12,16 1 阿什特比拉 临近的郡 考虑的郡 临近的郡 考虑的郡 *