整数规划规划的应用

《整数规划规划的应用》由会员分享，可在线阅读，更多相关《整数规划规划的应用（24页珍藏版）》请在金锄头文库上搜索。

1、选选 址址 问问 题题中央财经大学中央财经大学 信息学院信息学院 吴吴 靖靖 正确地使用方法，并对结果做出恰当地解释。1 选址（运输）一家石油公司，有油田并进口原油，有若干个炼油厂和配送中心，由于市场拓展的需要，公司决定新建炼油厂，管理层需要为新炼油厂选址做出决策。决策的三个主要因素是：1.从油田运送原油到所有炼油厂（含新建炼油厂）的运输成本；2.从所有炼油厂（含新建炼油厂）到每一个配送中心的运输成本；3.新炼油厂的运作成本。例如，劳动力成本、赋税、能源成本、保险成本等。管理层需要的财务数据： 1. 每个新炼油厂地点的选择带来的总原油运输成本；2. 每个新炼油厂地点的选择带来的总石油制品运输成

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 N2

3、5 4 36 N34 3 15 配送中心 需求量1008080100表4 备选地点估计运营成本 地点运营成本 N1620 N2573 N3530例1 Site-Select Problem2 选址-整数规划应用 前面讨论的线性规划问题中，有些最优决策变量 可能是小数，但对于某些具体问题，常有要求解答 必须是整数（称为整数解）。例如，机器的台数、 完成工作的人数等。 为了得到问题的整数解，对得到的小数解四舍五 入化整是不可以的，化整以后不一定是问题的解， 或不一定是问题的最优解。因此，需要专门研究。 整数规划是规划问题的一个分支，是近20年发展 起来的。 整数规划 例2 投资。全整数规划问题。A

4、公司有2000万用来购买租赁财产。经过筛选，已把投资 目标定位在联体别墅和公寓楼。每套联体别墅售价282万，现 有5套空闲。每栋公寓楼售价400万，开发商可根据A公司的需 要建造。A公司项目经理每月用于这些新置财产上的时间是140小 时。每套联体别墅预计每月用时4小时，每栋公寓楼预计每月 用时40小时。扣除抵押偿还和经营成本后，现金流预计每套联体别墅 10万，每栋公寓楼15万。股东需要确定使现金流最大的购买 方案。 例2 投资-全整数规划问题联体别墅公寓楼有限资源售价2824002000项目经理 时间440140现金流1015 例3 选址（0-1规划应用）A公司在L3地区有多个工厂和仓库，由于

5、业务拓展的需要，管理层决定在 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.可用资

6、金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个。投资总

7、额不能超过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企业希望在一个区域建立分销中心，就在该区

8、 域及其接壤的周边区域建立连锁店。现在该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 1

9、21，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项

10、目净现值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项任务

11、，n条航线n艘船只航行等。指派（分配）问题是0-1规划的特例，也是运 输问题的特例，在指派问题模型中，每一个产地 的提供量和每一个目的地的需求量均为1，即n=m, ai=bi=1 。指派问题一般模型例7比赛场地某主办方举办4场比赛,并为每场比赛派出官员,下表给 出每一位官员到每个赛场的距离,举办方希望以总距离 最小的方案派出官员,求派出方案。比赛场 地官员P1P2P3p4 OFFICERA21090180160B10070130200C175105140170 D8065105120例8客户项目A公司分别从3个客户（c1,c2,c3）那里得到了市场调研的项目 ，目前有3个项目经理（m1,m2,

12、m3）可以承担这些项目，完成每 个项目所需的时间与这3位项目经理的经验和能力有关，管理层 估算了每位经理完成各项目的可能时间，如何分配项目给各经 理，可以使项目尽快完成（所用时间最短）？ 预计项目完成时间 项目主管客户c1c2c3m110159m29185m36143例9Assignment Problem Sellmore Co. Assignment Problem 一家公司为一次会议聘用了4位临时工人,需要为4位工人分配四 项工作,每个人由于能力的不同,完成每项工作所用的时间不同, 经过评估,每个人每小时工资也不相同,公司需要确定如何分配工 作,总费用最小.TaskRequired Ti

13、me (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