选选 址址 问问 题题中央财经大学中央财经大学 信息学院信息学院 吴吴 靖靖 正确地使用方法，并对结果做出恰当地解释。1 选址（运输）一家石油公司，有油田并进口原油，有若干个炼油厂和配送中心，由于市场拓展的需要，公司决定新建炼油厂，管理层需要为新炼油厂选址做出决策。决策的三个主要因素是：1.从油田运送原油到所有炼油厂（含新建炼油厂）的运输成本；2.从所有炼油厂（含新建炼油厂）到每一个配送中心的运输成本；3.新炼油厂的运作成本。例如，劳动力成本、赋税、能源成本、保险成本等。管理层需要的财务数据： 1. 每个新炼油厂地点的选择带来的总原油运输成本；2. 每个新炼油厂地点的选择带来的总石油制品运输成本。表1 公司生产数据(要求炼油厂满负荷运转) （百万桶）炼油厂年所需原油量油田年原油产量R1100F180 R260F260 R380F3100 R4(新建)120F4(进口)120SUM360 360表2 从油田到炼油厂-原油运输成本数据油田R1R2R3N1N2N3年原油产 量 F124531180 F245313460 F3573457100 F4(进口)235434120 炼油厂 需求量1006080120表3 从炼油厂到配送中心 - 石油制品运输成本数据 炼油厂D1D2D3D4炼油厂产量 R17 6 68100 R27 5 4760 R37 8 4380 N18 6 32120 N25 4 36 N34 3 15 配送中心 需求量1008080100表4 备选地点估计运营成本 地点运营成本 N1620 N2573 N3530例1 Site-Select Problem2 选址-整数规划应用 前面讨论的线性规划问题中，有些最优决策变量 可能是小数，但对于某些具体问题，常有要求解答 必须是整数（称为整数解）。例如，机器的台数、 完成工作的人数等。 为了得到问题的整数解，对得到的小数解四舍五 入化整是不可以的，化整以后不一定是问题的解， 或不一定是问题的最优解。因此，需要专门研究。 整数规划是规划问题的一个分支，是近20年发展 起来的。 整数规划 例2 投资。全整数规划问题。A公司有2000万用来购买租赁财产。经过筛选，已把投资 目标定位在联体别墅和公寓楼。每套联体别墅售价282万，现 有5套空闲。每栋公寓楼售价400万，开发商可根据A公司的需 要建造。A公司项目经理每月用于这些新置财产上的时间是140小 时。每套联体别墅预计每月用时4小时，每栋公寓楼预计每月 用时40小时。扣除抵押偿还和经营成本后，现金流预计每套联体别墅 10万，每栋公寓楼15万。股东需要确定使现金流最大的购买 方案。 例2 投资-全整数规划问题联体别墅公寓楼有限资源售价2824002000项目经理 时间440140现金流1015 例3 选址（0-1规划应用）A公司在L3地区有多个工厂和仓库，由于业务拓展的需要，管理层决定在 L1和L2地区建厂。需要决策的问题是在L1还是在L2建厂，或在2个地区都 建厂；并同时考虑至多建1个新仓库，如果建新仓库，该仓库应该与新建厂在同一个地点。可用资金：10百万。相关数据百万 决策 序列号是非问题决策 变量所需资金净现值决策变量 可能取值1L1建厂x1680 / 12L2建厂x2350 / 13L1建仓库x3560 / 14L2建仓库x4240 / 1模型问题的解析描述约 束 1. 可用资金10 2. 互斥决策变量-至多只建1个仓库 3. 相依决策变量-建厂才建仓库目标函数：净现值最大目标函数：Max z=8x1+5x2+6x3+4x4约束：1.可用资金106*x1+3*x2+5*x3+2*x4=x3，x2=x44.决策变量xi = 0,1 (i = 1,2,3,4)例3 模型和Excel求解过程目标函数：Max z=8x1+5x2+6x3+4x4约束：1.可用资金106*x1+3*x2+5*x3+2*x4=x3，x2=x44.决策变量xi = 0,1 (i = 1,2,3,4)例4 连锁店选址某连锁店计划在城区的东南西北部建店。有10个位置可供参考。每个位置的预计投资额和利润如表。并有如下条件：A1,A2,A3三个点至多选择2个；A4,A5两个点中至少选择1个；A6,A7两个点中至少选择1个；A8,A9,A10三个点中至少选择2个。投资总额不能超过720万。A1A2A3A4A5A6A7A8A9A10 投资 额10012015080709080140160180利润36405022203025485861目标函数：约束：问题建模目标函数： H15：=SUMPRODUCT(C5:L5,C9:L9)约束： C15：=SUMPRODUCT(C4:L4,C9:L9) C17：=SUM(C9:E9) C18：=SUM(F9:G9) C19：=SUM(H9:I9) C20：=SUM(J9:L9)Excel求解过程例5 分销中心选址A企业需要在B地区建立分销中心和连锁店。由于建立分销中心 的成本较高，A企业希望在一个区域建立分销中心，就在该区 域及其接壤的周边区域建立连锁店。现在该B地区有20个相邻 的区域（以数字标示），它们之间的相邻关系如表所示。建立 分销中心是需要复杂的审批手续的，至少应该建立多少个分销 中心、在哪些区域建立，能够使分销中心和连锁店覆盖整个B 地区，而且分销中心的数量最小。例5 分销中心选址图示例5 相邻关系数据表区域相邻区域 12，12，16 21，3，12 32，4，9，10，12，13 43，5，7，9 54，6，7 65，7，17 74，5，6，8，9，17，18 87，9，10，11，18 93，4，7，8，10 103，8，9，11，12，13 118，10，13，14，15，18，19，20 121，2，3，10，13，16 133，10，11，12，15，16 1411，15，20 1511，13，14，16 161，12，13，15 176，7，18 187，8，11，17，19 1911，18，20 2011，14，19例6 资金预算A冰箱公司正在考虑今后4年的投资方案。面对 每年有限的资金，管理者需要选择最好的方案，每 种方案的净现金流、资金需求和4年内的可用资金如 表所示。求能使净现值最大的投资方案。例6 资金预算 数据项目年度工厂 扩张 P仓库 扩张 W机器 更新 M新产品 研究 R可用资金1151010154022015010503202001040415541035项目净现值90401037目标函数：Max z=90x1+40x2+10x3+37x4 约束：15x1 + 10x2 + 10x3 + 15x4 = 4020x1 + 15x2 + 0x3 + 10x4 = 50 .xi = 0,1 (i=1,2,3,4,)优化模型和求解过程目标函数： I13：=SUMPRODUCT(C10:F10,C13:F13)约束： G6：=SUMPRODUCT(C6:F6,$C$13:$F$13) G7： G8： G9：3 指 派 指派问题讨论的是n项工作分配给n个人去完 成，每个人的工作效率不同，如何分配任务，能 够使总的工作效率最高。类似的有：n台机器加工 n项任务，n条航线n艘船只航行等。指派（分配）问题是0-1规划的特例，也是运 输问题的特例，在指派问题模型中，每一个产地 的提供量和每一个目的地的需求量均为1，即n=m, ai=bi=1 。指派问题一般模型例7比赛场地某主办方举办4场比赛,并为每场比赛派出官员,下表给 出每一位官员到每个赛场的距离,举办方希望以总距离 最小的方案派出官员,求派出方案。比赛场 地官员P1P2P3p4 OFFICERA21090180160B10070130200C175105140170 D8065105120例8客户项目A公司分别从3个客户（c1,c2,c3）那里得到了市场调研的项目 ，目前有3个项目经理（m1,m2,m3）可以承担这些项目，完成每 个项目所需的时间与这3位项目经理的经验和能力有关，管理层 估算了每位经理完成各项目的可能时间，如何分配项目给各经 理，可以使项目尽快完成（所用时间最短）？ 预计项目完成时间 项目主管客户c1c2c3m110159m29185m36143例9Assignment Problem Sellmore Co. Assignment Problem 一家公司为一次会议聘用了4位临时工人,需要为4位工人分配四 项工作,每个人由于能力的不同,完成每项工作所用的时间不同, 经过评估,每个人每小时工资也不相同,公司需要确定如何分配工 作,总费用最小.TaskRequired Time (Hours)part timeWord ProcessingGraphicsPacketsRegistrationsHourly WageAnn35412740$14AssigneeIan47453251$12Joan39563643$13Sean32512546$15例10 Machine-Location ProblemJob Shop Co. Machine-Location Problem某公司购买了3种不同的设备,但是车间里却有5个不同的地点需要安装.每一个需要安装新设备的地点处理物料的小时成本列于表中,公司寻求总物料处理成本最小的安装方案.其中,设备2不能安装在地点2.Cost ($/hour)Location 1Location 2Location 3Location 4Location 5Machine 11316121415Machine 215-132016Machine 3471067