运筹学整数规划案例.pptVIP

整数规划建模 应用最广泛的整数规划问题是各种类型的决策问 题，决策者希望模型能回答诸如：是否要执行某些项 目（或某些活动），在什么时候或什么地点执行等决 策问题，回答这类“是否”或“有无”问题可借助整 数规划中的0-1整数变量。 0-1整数变量只有两个选择，0由于它在数学上的 特性可以很好的代表“无”或“否”，而1则可以很好地代 表“有”或“是”。0-1变量由于它的特殊性也被称为二进 制变量、决策变量或逻辑变量。 0-1变量的作用 1. xj 1方案j被选中 0方案j未被选中 2. 从n个方案中必须选中一个： 3. 从n个方案中最多选中m个： 4. 方案i只有在方案j选中时，才可能被选中： 5. 方案i与方案j是否选中是同时的： 与01变量相关的几个实际问题 1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可 供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j 1，2，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行 投资？ 先引入01变量xj，令 xj 1对项目j投资 0否则 则可得到如下整数规划问题： 例1：华美公司有5个项目被列入投资计划，各项目的投 资额和期望的投资收益见下表： 项目投资额（万元）投资收益（万元） 1210150 2300210 310060 413080 5260180 该公司只有600万元资金可用于投资，由于技术上 的原因，投资受到以下约束：在项目1、2和3中必须 有一项被选中；项目3和4只能选一项；项目5被选 中的前提是项目1必须被选中。问如何在上述条件下选 择一个最好的投资方案，使投资收益最大。 令0-1变量为决策变量，即xi1表示选中项目i， 否则xi0表示项目i未被选中。则模型可以表示为： 解： 2. 背包问题 背包问题由来以久，它是从旅行者如何选择放在 背包中的用品引出的。 旅行者可背负的重量有限，但旅行者需要携带的 物品很多，如：食品、水、衣物、帐篷、急救用品等 等，旅行者不可能将所有想携带的物品都统统背上， 他只能选择那些最重要的物品随身携带，又不超过他 可能负担的最大重量，为解决这个问题，旅行者可给 每种物品指定一个重要性系数，他的目标是在小于一 定重量的前提下，使所携带的物品的重要性系数之和 最大。 例2 ：一登山队员做登山准备，他需要携带的物品有： 食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备 每种物品的重要系数和重量如下表所示，假定登山队 员可携带的最大重量为25千克。问他如何抉择？ 序号 1234567 物品食品氧气冰镐绳索帐篷照相 器材 通讯 设备 重量 （千克） 55261224 重要系数 201518148410 令xi1表示登山队员携带物品i，xi0表示 不带物品i。则问题可写为： Max z =20x1+15x2+18x3 +14x4+8x5+4x6+10x7 s.t. 5x1+ 5x2 + 2x3 +6x4+12x5+2x6+4x725 xi=1或0，i=1,2,7 解： 背包问题应用（作业） 要把7种规格的包装箱装到两辆铁路平板车上去，包装 箱的宽和高相同，但厚度和重量不同，见下表： 每辆车有10.2m长的地方可以用来装箱（类似面包片） ，载重为40吨。C5， C6 ， C7 ，三类包箱所占总空间（ 厚度）不超过302.7cm，试建立数学模型，尽量将这些 包装箱装到平板车上去，使浪费的空间最小。 例3.一公司考虑在四个城市：北京、上海、广州和武汉设立库房。 这些库房负责向三个地区：华北、华中和华南地区发运货物，每 个库房每月可处理货物1000件。在北京设库房每月的成本为4.5万 元。上海为5万元，广州为7万元，武汉为4万元。每个地区的月平 均需求量为：华北每月600件，华中每月700件，华南每月800件。 发运货物的费用（元/件）见下表： 华华北华华中华华南 北京200400500 上海300250450 广州600400250 武汉汉300150350 公司希望在满足地区需要的前提下使平均月成本最小，且还 要满足以下条件：如果在上海设立库房，则必须也在武汉设库 房；最多设立三个库房；武汉和广州不能同时设立库房。 请建立一个满足上述要求的整数规划模型。 3. 工厂选址运输问题 设每个月从仓库i运往地区j的产品的货物数量为xij，引入0 1变量yi= 1表示在Ai设立仓库，否则不设。 设每个月的总花费为z，则上述问题的数学模型为 Min z200x11+400x12+500x13+300x21+250x22+450x23 +600x31+400x32+250x33+300x41+150x42+350x43+45000y1+50000 y2+70000y3+40000y4 s.t. x11+x12+x131000y1 x21+x22+x231000y2 x31+x32+x331000y3 x41+x42+x431000y4 x11+x21+x31+x41600 x12+x22+x32+x42700 x13+x23+x33+x43800 y2-y40 y1+y2+y3+y43 y3+y4 1 xij0；yi0或1；i=1,2,3,4；j=1,2,3 工厂选址运输问题 设有n个需求点，有m个可供选择的厂址， 每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。 设在单位时间内，从厂址i运往需 求点j的产品数量为xij， 引入01变量yi= 1在i地建厂 0否则 设在单位时间内的总花费为z，则 上述问题的数学模型为 4.集合覆盖和布点问题 集合覆盖问题也是典型的整数规划问题，在集合 覆盖问题中，一个给定集合（集合一）的每一个元素 必须被另一个集合（集合二）的元素所覆盖。在满足 覆盖集合一所有元素的前提下，集合覆盖问题的目标 是求需要的集合二的元素最少，该问题之所以又称为 布点问题，是因为它常被用于一些公共设施，如：学 校、医院、商业区、消防队等设施的布点问题，解决 如何既满足公共要求，又使布的点最少，以节约投资 费用。 例4：解决某市消防站的布点问题：某城市共有6个区 ，每个都可以建消防站。市政府希望建设的消防站最 少，但必须满足在城市任何地区发生火警时，消防车 要在15分钟内赶到现场。据实地测定，各区之间消防 车行驶的时间见下表：请帮助该市制定一个最节省的 计划。 表3.5消防车在各区行驶距离表 地区1 地区2 地区3 地区4 地区5 地区6 地区1 0 10 16 28 27 20 地区2 10 0 24 32 17 10 地区3 16 24 0 12 27 21 地区4 28 32 12 0 15 25 地区5 27 17 27 15 0 14 地区6 20 10 21 25 14 0 解：Xj=1表地区设消防站， Xj=0表地区不设消 防站。Z消防站总数，则模型如下： MinZ=X1+X2+X3+X4+X5+X6 s.t： X1+X21 X1+X2+X61 X3+X41 X3+X4+X51 X4+X5+X61 X2+X5+X61 Xj=0，1；j=1，2，3，4，5，6。 作业 某市有8个区，救护车从一个区开往另一个区所需时间： 区号12345678人口（万人） 102468981040 220548612930 34502235735 46420325420 58823022415 69632203250 781255230245 810974422060 该市只有两辆救护车，且希望救护车，所在的位置能使 尽可能多的人口位于救护车在两分钟内可达到的范围内 ，请帮助该市构造一个整数规划模型来解决这个问题。 5. 指派问题 在生活中经常遇到这样的问题，某单位需要 完成n项任务，恰好有n个人可以承担这些任务， 由于每个人的专长不同，个人完成不同任务的效 率（时间、费用等）也不同。 于是产生了指派哪个人去完成哪项任务，使总 效率最高，称为指派问题（Assignment Problem） 。 已知上