运筹学-整数规划案例策划推广方案

整数规划建模应用最广泛的整数规划问题是各种类型的决策问题，决策者希望模型能回答诸如：是否要执行某些项目（或某些活动），在什么时候或什么地点执行等决策问题，回答这类“是—否”或“有—无”问题可借助整数规划中的0-1整数变量。0-1整数变量只有两个选择，0由于它在数学上的特性可以很好的代表“无”或“否”，而1则可以很好地代表“有”或“是”。0-1变量由于它的特殊性也被称为二进制变量、决策变量或逻辑变量。1整数规划建模应用最广泛的整数规划问题是各种类0-1变量的作用1.xj＝1…方案j被选中0…方案j未被选中2.从n个方案中必须选中一个：3.从n个方案中最多选中m个：4.方案i只有在方案j选中时，才可能被选中：5.方案i与方案j是否选中是同时的：20-1变量的作用1.xj＝1…方案j被选中2.从n个方案与0－1变量相关的几个实际问题1.投资问题

现有总额为b的资金可用于投资，共有n个项目可供投资者选择，已知项目j所需投资额为aj，投资后可得利润cj（j＝1，2，…，n），不妨设b，aj，cj均是整数，试问为使所得利润最大，应选取那些项目进行投资？先引入0－1变量xj，令

xj＝1…对项目j投资0…否则则可得到如下整数规划问题：3与0－1变量相关的几个实际问题1.投资问题例1：华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收益（万元）121015023002103100604130805260180该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：①在项目1、2和3中必须有一项被选中；②项目3和4只能选一项；③项目5被选中的前提是项目1必须被选中。问如何在上述条件下选择一个最好的投资方案，使投资收益最大。4例1：华美公司有5个项目被列入投资计划，各项目的投项目投资额令0-1变量为决策变量，即xi＝1表示选中项目i，否则xi＝0表示项目i未被选中。则模型可以表示为：解：5令0-1变量为决策变量，即xi＝1表示选中项2.背包问题背包问题由来以久，它是从旅行者如何选择放在背包中的用品引出的。旅行者可背负的重量有限，但旅行者需要携带的物品很多，如：食品、水、衣物、帐篷、急救用品等等，旅行者不可能将所有想携带的物品都统统背上，他只能选择那些最重要的物品随身携带，又不超过他可能负担的最大重量，为解决这个问题，旅行者可给每种物品指定一个重要性系数，他的目标是在小于一定重量的前提下，使所携带的物品的重要性系数之和最大。62.背包问题背包问题由来以久，它是从旅行者例2：一登山队员做登山准备，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备每种物品的重要系数和重量如下表所示，假定登山队员可携带的最大重量为25千克。问他如何抉择？序号1234567物品食品氧气冰镐绳索帐篷照相器材通讯设备重量（千克）55261224重要系数2015181484107例2：一登山队员做登山准备，他需要携带的物品有：序号123

令xi＝1表示登山队员携带物品i，xi＝0表示不带物品i。则问题可写为：Maxz=20x1+15x2+18x3

+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25

xi=1或0，i=1,2,…,7解：8令xi＝1表示登山队员携带物品i，xi＝0表背包问题应用（作业）

要把7种规格的包装箱装到两辆铁路平板车上去，包装箱的宽和高相同，但厚度和重量不同，见下表：

每辆车有10.2m长的地方可以用来装箱（类似面包片），载重为40吨。C5，C6，

C7，三类包箱所占总空间（厚度）不超过302.7cm，试建立数学模型，尽量将这些包装箱装到平板车上去，使浪费的空间最小。9背包问题应用（作业）要把7种规格的包装箱装到两辆铁例3.一公司考虑在四个城市：北京、上海、广州和武汉设立库房。这些库房负责向三个地区：华北、华中和华南地区发运货物，每个库房每月可处理货物1000件。在北京设库房每月的成本为4.5万元。上海为5万元，广州为7万元，武汉为4万元。每个地区的月平均需求量为：华北每月600件，华中每月700件，华南每月800件。发运货物的费用（元/件）见下表：华北华中华南北京200400500上海300250450广州600400250武汉300150350公司希望在满足地区需要的前提下使平均月成本最小，且还要满足以下条件：①如果在上海设立库房，则必须也在武汉设库房；②最多设立三个库房；③武汉和广州不能同时设立库房。请建立一个满足上述要求的整数规划模型。3.工厂选址运输问题10例3.一公司考虑在四个城市：北京、上海、广州和武汉设立库房。

设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－1变量yi=1表示在Ai设立仓库，否则不设。

设每个月的总花费为z，则上述问题的数学模型为Minz＝200x11+400x12+500x13+300x21+250x22+450x23+600x31+400x32+250x33+300x41+150x42+350x43+45000y1+50000y2+70000y3+40000y4s.t.x11+x12+x13≤1000y1x21+x22+x23≤1000y2x31+x32+x33≤1000y3x41+x42+x43≤1000y4x11+x21+x31+x41≥600x12+x22+x32+x42≥700x13+x23+x33+x43≥800y2-y4≤0y1+y2+y3+y4≤3y3+y4≤

1xij≥0；yi＝0或1；i=1,2,3,4；j=1,2,311设每个月从仓库i运往地区j的产品的货物数量为xij工厂选址运输问题

设有n个需求点，有m个可供选择的厂址，每个厂址只能建一个工厂，在i处建厂，生产能力为Di，单位时间的固定成本为ai，需求点j的需求量为bj，从厂址i到需求点j的单位运费为Cij，问应如何选择厂址才能获得经济上的总花费最小的方案。12工厂选址运输问题设有n个需求点，有m个可供选

设在单位时间内，从厂址i运往需求点j的产品数量为xij，

引入0－1变量yi=1…在i地建厂0…否则设在单位时间内的总花费为z，则上述问题的数学模型为13设在单位时间内，从厂址i运往需1…在i地建厂4.集合覆盖和布点问题集合覆盖问题也是典型的整数规划问题，在集合覆盖问题中，一个给定集合（集合一）的每一个元素必须被另一个集合（集合二）的元素所覆盖。在满足覆盖集合一所有元素的前提下，集合覆盖问题的目标是求需要的集合二的元素最少，该问题之所以又称为布点问题，是因为它常被用于一些公共设施，如：学校、医院、商业区、消防队等设施的布点问题，解决如何既满足公共要求，又使布的点最少，以节约投资费用。144.集合覆盖和布点问题集合覆盖问题也是典型的例4：解决某市消防站的布点问题：某城市共有6个区，每个都可以建消防站。市政府希望建设的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见下表：请帮助该市制定一个最节省的计划。

表3.5消防车在各区行驶距离表地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区62010212514015例4：解决某市消防站的布点问题：某城市共有6个区，每个都可以解：Xj=1表地区设消防站，Xj=0表地区不设消防站。Z＝消防站总数，则模型如下：

MinZ=X1+X2+X3+X4+X5+X6s.t：X1+X2≥1

X1+X2+X6≥1X3+X4≥1X3+X4+X5≥1X4+X5+X6≥1X2+X5+X6≥1Xj=0，1；j=1，2，3，4，5，6。16解：Xj=1表地区设消防站，Xj=0表地区作业某市有8个区，救护车从一个区开往另一个区所需时间：区号12345678人口（万人）10246898104022054861293034502235735464203254205882302241569632203250781255230245810974422060该市只有两辆救护车，且希望救护车，所在的位置能使尽可能多的人口位于救护车在两分钟内可达到的范围内，请帮助该市构造一个整数规划模型来解决这个问题。17作业某市有8个区，救护车从一个区开往另一个区所需时间：区号15.指派问题

在生活中经常遇到这样的问题，某单位需要完成n项任务，恰好有n个人可以承担这些任务，由于每个人的专长不同，个人完成不同任务的效率（时间、费用等）也不同。于是产生了指派哪个人去完成哪项任务，使总效率最高，称为指派问题（AssignmentProblem）。185.指派问题18

已知上面5名运动员各种姿势游泳成绩（50m），试问如何从中选拔一个200m混合泳的接力队，使预期比赛成绩最好。（列出整数规划模型）ABCDE仰泳37.732.933.837.035.4蛙泳43.333.142.234.941.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.15.指派问题（作业）19已知上面5名运动员各种姿势游泳成绩（50m），20202121222223232424整数规划建模应用最广泛的整数规划问题是各种类型的决策问题，决策者希望模型能回答诸如：是否要执行某些项目（或某些活动），在什么时候或什么地点执行等决策问题，回答这类“是—否”或“有—无”问题可借助整数规划中的0-1整数变量。0-1整数变量只有两个选择，0由于它在数学上的特性可以很好的代表“无”或“否”，而1则可以很好地代表“有”或“是”。0-1变量由于它的特殊性也被称为二进制变量、决策变量或逻辑变量。25整数规划建模应用最广泛的整数规划问题是各种类0-1变量的作用1.xj＝1…方案j被选中0…方案j未被选中2.从n个方案中必须选中一个：3.从n个方案中最多选中m个：4.方案i只有在方案j选中时，才可能被选中：5.方案i与方案j是否选中是同时的：260-1变量的作用1.xj＝1…方案j被选中2.从n个方案与0－1变量相关的几个实际问题1.投资问题

现有总额为b的资金可用于投资，共有n个项目可供投资者选择，已知项目j所需投资额为aj，投资后可得利润cj（j＝1，2，…，n），不妨设b，aj，cj均是整数，试问为使所得利润最大，应选取那些项目进行投资？先引入0－1变量xj，令

xj＝1…对项目j投资0…否则则可得到如下整数规划问题：27与0－1变量相关的几个实际问题1.投资问题例1：华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收益（万元）121015023002103100604130805260180该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：①在项目1、2和3中必须有一项被选中；②项目3和4只能选一项；③项目5被选中的前提是项目1必须被选中。问如何在上述条件下选择一个最好的投资方案，使投资收益最大。28例1：华美公司有5个项目被列入投资计划，各项目的投项目投资额令0-1变量为决策变量，即xi＝1表示选中项目i，否则xi＝0表示项目i未被选中。则模型可以表示为：解：29令0-1变量为决策变量，即xi＝1表示选中项2.背包问题背包问题由来以久，它是从旅行者如何选择放在背包中的用品引出的。旅行者可背负的重量有限，但旅行者需要携带的物品很多，如：食品、水、衣物、帐篷、急救用品等等，旅行者不可能将所有想携带的物品都统统背上，他只能选择那些最重要的物品随身携带，又不超过他可能负担的最大重量，为解决这个问题，旅行者可给每种物品指定一个重要性系数，他的目标是在小于一定重量的前提下，使所携带的物品的重要性系数之和最大。302.背包问题背包问题由来以久，它是从旅行者例2：一登山队员做登山准备，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备每种物品的重要系数和重量如下表所示，假定登山队员可携带的最大重量为25千克。问他如何抉择？序号1234567物品食品氧气冰镐绳索帐篷照相器材通讯设备重量（千克）55261224重要系数20151814841031例2：一登山队员做登山准备，他需要携带的物品有：序号123

令xi＝1表示登山队员携带物品i，xi＝0表示不带物品i。则问题可写为：Maxz=20x1+15x2+18x3

+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25

xi=1或0，i=1,2,…,7解：32令xi＝1表示登山队员携带物品i，xi＝0表背包问题应用（作业）

要把7种规格的包装箱装到两辆铁路平板车上去，包装箱的宽和高相同，但厚度和重量不同，见下表：

每辆车有10.2m长的地方可以用来装箱（类似面包片），载重为40吨。C5，C6，

C7，三类包箱所占总空间（厚度）不超过302.7cm，试建立数学模型，尽量将这些包装箱装到平板车上去，使浪费的空间最小。33背包问题应用（作业）要把7种规格的包装箱装到两辆铁例3.一公司考虑在四个城市：北京、上海、广州和武汉设立库房。这些库房负责向三个地区：华北、华中和华南地区发运货物，每个库房每月可处理货物1000件。在北京设库房每月的成本为4.5万元。上海为5万元，广州为7万元，武汉为4万元。每个地区的月平均需求量为：华北每月600件，华中每月700件，华南每月800件。发运货物的费用（元/件）见下表：华北华中华南北京200400500上海300250450广州600400250武汉300150350公司希望在满足地区需要的前提下使平均月成本最小，且还要满足以下条件：①如果在上海设立库房，则必须也在武汉设库房；②最多设立三个库房；③武汉和广州不能同时设立库房。请建立一个满足上述要求的整数规划模型。3.工厂选址运输问题34例3.一公司考虑在四个城市：北京、上海、广州和武汉设立库房。

设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－1变量yi=1表示在Ai设立仓库，否则不设。

设每个月的总花费为z，则上述问题的数学模型为Minz＝200x11+400x12+500x13+300x21+250x22+450x23+600x31+400x32+250x33+300x41+150x42+350x43+45000y1+50000y2+70000y3+40000y4s.t.x11+x12+x13≤1000y1x21+x22+x23≤1000y2x31+x32+x33≤1000y3x41+x42+x43≤1000y4x11+x21+x31+x41≥600x12+x22+x32+x42≥700x13+x23+x33+x43≥800y2-y4≤0y1+y2+y3+y4≤3y3+y4≤

1xij≥0；yi＝0或1；i=1,2,3,4；j=1,2,335设每个月从仓库i运往地区j的产品的货物数量为xij工厂选址运输问题

设有n个需求点，有m个可供选择的厂址，每个厂址只能建一个工厂，在i处建厂，生产能力为Di，单位时间的固定成本为ai，需求点j的需求量为bj，从厂址i到需求点j的单位运费为Cij，问应如何选择厂址才能获得经济上的总花费最小的方案。36工厂选址运输问题设有n个需求点，有m个可供选

设在单位时间内，从厂址i运往需求点j的产品数量为xij，

引入0－1变量yi=1…在i地建厂0…否则设在单位时间内的总花费为z，则上述问题的数学模型为37设在单位时间内，从厂址i运往需1…在i地建厂4.集合覆盖和布点问题集合覆盖问题也是典型的整数规划问题，在集合覆盖问题中，一个给定集合（集合一）的每一个元素必须被另一个集合（集合二）的元素所覆盖。在满足覆盖集合一所有元素的前提下，集合覆盖问题的目标是求需要的集合二的元素最少，该问题之所以又称为布点问题，是因为它常被用于一些公共设施，如：学校、医院、商业区、消防队等设施的布点问题，解决如何既满足公共要求，又使布的点最少，以节约投资费用。384.集合覆盖和布点问题集合覆盖问题也是典型的例4：解决某市消防站的布点问题：某城市共有6个区，每个都可以建消防站。市政府希望建设的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见下表：请帮助该市制定一个最节省的计划。

表3.5消防车在各区行驶距离表地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区62010212514039例4：解决某市消防站的布点问题：某城市共有6个区，每个都可以解：Xj=1表地区设消防站，Xj=0表地区不设消防站。Z＝消防站总数，则模型如下：

MinZ=