Excel-Module-3-整数规划0-1规划的应用.ppt

Business Statistics: A Decision-Making Approach, 6e ? 2005 Prentice-Hall, Inc. 选 址 问 题 中央财经大学 信息学院吴 靖  正确地使用方法，并对结果做出恰当地解释。 §1 选址（运输） 一家石油公司，有油田并进口原油，有若干个炼油厂和配送中心，由于市场拓展的需要，公司决定新建炼油厂，管理层需要为新炼油厂选址做出决策。决策的三个主要因素是： 1.从油田运送原油到所有炼油厂（含新建炼油厂）的运输成本； 2.从所有炼油厂（含新建炼油厂）到每一个配送中心的运输成本； 3.新炼油厂的运作成本。例如，劳动力成本、赋税、能源成本、保险成本等。 管理层需要的财务数据： 1. 每个新炼油厂地点的选择带来的总原油运输成本； 2. 每个新炼油厂地点的选择带来的总石油制品运输成本。 表1 公司生产数据(要求炼油厂满负荷运转) （百万桶） 炼油厂 年所需原油量 油田 年原油产量 R1 100 F1 80 R2 60 F2 60 R3 80 F3 100 R4(新建) 120 F4(进口) 120 SUM 360 　 360 表2 从油田到炼油厂--原油运输成本数据 油田 R1 R2 R3 N1 N2 N3 年原油产量 F1 2 4 5 3 1 1 80 F2 4 5 3 1 3 4 60 F3 5 7 3 4 5 7 100 F4(进口) 2 3 5 4 3 4 120 炼油厂需求量 100 60 80 120 表3 从炼油厂到配送中心 -- 石油制品运输成本数据 炼油厂 D1 D2 D3 D4 炼油厂产量 R1 7 6 6 8 100 R2 7 5 4 7 60 R3 7 8 4 3 80 N1 8 6 3 2 120 N2 5 4 3 6 N3 4 3 1 5 配送中心需求量 100 80 80 100 表4 备选地点估计运营成本 地点 运营成本 N1 620 N2 573 N3 530 例1 Site-Select Problem §2 选址--整数规划应用 前面讨论的线性规划问题中，有些最优决策变量可能是小数，但对于某些具体问题，常有要求解答必须是整数（称为整数解）。例如，机器的台数、完成工作的人数等。 为了得到问题的整数解，对得到的小数解四舍五入化整是不可以的，化整以后不一定是问题的解，或不一定是问题的最优解。因此，需要专门研究。 整数规划是规划问题的一个分支，是近20年发展起来的。 整数规划 例2 投资。全整数规划问题。 A公司有2000万用来购买租赁财产。经过筛选，已把投资目标定位在联体别墅和公寓楼。每套联体别墅售价282万，现有5套空闲。每栋公寓楼售价400万，开发商可根据A公司的需要建造。 A公司项目经理每月用于这些新置财产上的时间是140小时。每套联体别墅预计每月用时4小时，每栋公寓楼预计每月用时40小时。 扣除抵押偿还和经营成本后，现金流预计每套联体别墅10万，每栋公寓楼15万。股东需要确定使现金流最大的购买方案。 例2 投资--全整数规划问题 　 联体别墅 公寓楼 有限资源 售价 282 400 2000 项目经理 时间 4 40 140 现金流 10 15 　 例3 选址（0-1规划应用） A公司在L3地区有多个工厂和仓库，由于业务拓展的需要，管理层决定在L1和L2地区建厂。需要决策的问题是在L1还是在L2建厂，或在2个地区都建厂；并同时考虑至多建1个新仓库，如果建新仓库，该仓库应该与新建厂在同一个地点。可用资金：10百万。 相关数据 百万 决策 序列号 是非问题 决策 变量 所需资金 净现值 决策变量 可能取值 1 L1建厂 x1 6 8 0 / 1 2 L2建厂 x2 3 5 0 / 1 3 L1建仓库 x3 5 6 0 / 1 4 L2建仓库 x4 2 4 0 / 1 模型—问题的解析描述 约 束 1. 可用资金10 2. 互斥决策变量--至多只建1个仓库 3. 相依决策变量--建厂才建仓库 目标函数：净现值最大 目标函数：Max z=8x1+5x2+6x3+4x4 约束： 1.可用资金10 6*x1+3*x2+5*x3+2*x4=10 2.互斥决策变量--至多只建1个仓库， x3+x4=1（互斥决策变量的和=1） 3.相依决策变量--建厂才建仓库， x1=x3，x2=x4 4.决策变量 xi = 0,1 (i = 1,2,3,4) 例3 模型和Excel求解过程 目标函数：Max z=8x1+5x2+