运筹学 整数规划案例

m
x ij
b
，
j
j
1,2 ,
,n
i1
x ij 0， y i 0 或 1
4.集合覆盖和布点问题
集合覆盖问题也是典型的整数规划问题，在集合 覆盖问题中，一个给定集合（集合一）的每一个元素 必须被另一个集合（集合二）的元素所覆盖。在满足 覆盖集合一所有元素的前提下，集合覆盖问题的目标 是求需要的集合二的元素最少，该问题之所以又称为 布点问题，是因为它常被用于一些公共设施，如：学 校、医院、商业区、消防队等设施的布点问题，解决 如何既满足公共要求，又使布的点最少，以节约投资 费用。
y2-y4≤0
y1+y2+y3+y4≤3
2020/4/1
y3+y4 ≤ 1
工厂选址运输问题 设有n个需求点，有m个可供选择的厂址，
每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。
2020/4/1
0-1变量的作用
1…方案j被选中 1. xj＝
0…方案j未被选中
n
2. 从n个方案中必须选中一个： x j 1 j 1 n
3. 从n个方案中最多选中m个： x j m j 1
4. 方案i只有在方案j选中时，才可能被选中：
x xj
2020/4/1
设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－ 1变量yi= 1表示在Ai设立仓库，否则不设。
设每个月的总花费为z，则上述问题的数学模型为
Min z＝200x11+400x12+500x13+300x21+250x22+450x23
+600x31+400x32+250x33+300x41+150x42+350x43+45000y1+5000
于是产生了指派哪个人去完成哪项任务，使 总效率最高，称为指派问题（Assignment Problem）。
2020/4/1
2020/4/1
s.t.
210x1 +300x2 +100x3 +130x4 +260x5 ≤600
x1
+x2
+x3
=1
x3
+x4
=1
x1
-x5 ≥0
x1,
x2,
x 3,
x 4, x 5＝0 或 1
2020/4/1
2. 背包问题
背包问题由来以久，它是从旅行者如何选择放在 背包中的用品引出的。
旅行者可背负的重量有限，但旅行者需要携带的 物品很多，如：食品、水、衣物、帐篷、急救用品等 等，旅行者不可能将所有想携带的物品都统统背上， 他只能选择那些最重要的物品随身携带，又不超过他 可能负担的最大重量，为解决这个问题，旅行者可给 每种物品指定一个重要性系数，他的目标是在小于一 定重量的前提下，使所携带的物品的重要性系数之和 最大。
2020/4/1
例4：解决某市消防站的布点问题：某城市共有6个区，
每个都可以建消防站。市政府希望建设的消防站最少，
但必须满足在城市任何地区发生火警时，消防车要在
15分钟内赶到现场。据实地测定，各区之间消防车行 驶的时间见下表：请帮助该市制定一个最节省的计划。
地区1 地区2 地区3 地区4 地区5 地区6
整数规划建模
应用最广泛的整数规划问题是各种类型的决策问 题，决策者希望模型能回答诸如：是否要执行某些项 目（或某些活动），在什么时候或什么地点执行等决 策问题，回答这类“是—否”或“有—无”问题可借助整 数规划中的0-1整数变量。
0-1整数变量只有两个选择，0由于它在数学上的 特性可以很好的代表“无”或“否”，而1则可以很好地 表“有”或“是”。0-1变量由于它的特殊性也被称为二 制变量、决策变量或逻辑变量。
表3.5消防车在各区行驶距离表
地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0
2020/4/1
解：Xj=1表地区设消防站， Xj=0表地区不设消 防站。Z＝消防站总数，则模型如下：
2020/4/1
与0－1变量相关的几个实际问题
1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可
供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j ＝ 1，2，…，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行
投资？
1…对项目j投资
先引入0－1变量xj，令 xj＝ 0…否则 n max c j x j
j 1
则可得到如下整数规划问题：
n
a
j
x
j
b
j 1
2020/4/1
x j 0或 1， j 1，2， ， n
2020/4/1
解：
令0-1变量为决策变量，即xi＝1表示选中项目i， 否则xi＝0表示项目i未被选中。则模型可以表示为：
max z= 150x1 +210x2 +60x3 +80x4 +180x5
2020/4/1
设在单位时间内，从厂址i运往需 求点j的产品数量为xij，
1…在i地建厂 引入0－1变量yi=
0…否则
设在单位时间内的总花费为z，则
mn
m
min z
c ij x ij a i y i
i1 j1
i1
上述问题的数学模型为
n
x ij
D
i
y
，
i
i
1,2 ,
，
m
j1
2020/4/1
2020/4/1
2020/4/1
解： 令xi＝1表示登山队员携带物品i，xi＝0表示
不带物品i。则问题可写为：
Max z =20x1+15x2+18x3 +14x4+8x5+4x6+10x7
s.t. 5x1+ 5x2 + 2x3 +6x4+12x5+2x6+4x7≤25 xi=1或0，i=1,2,…,7
0y2+70000y3+40000y4
s.t.
x11+x12+x13≤1000y1
x21+x22+x23≤1000y2
x31+x32+x33≤1000y3
x41+x42+x43≤1000y4
x11+x21+x31+x41≥600
x12+x22+x32+x42≥700
x13+x23+x33+x43≥800
2020/4/1
背包问题应用（作业） 要把7种规格的包装箱装到两辆铁路平板车上去，包装 箱的宽和高相同，但厚度和重量不同，见下表：
每辆车有10.2m长的地方可以用来装箱（类似面包片 ），载重为40吨。C5， C6 ， C7 ，三类包箱所占总空 间（厚度）不超过302.7cm，试建立数学模型，尽量将 这2些020/4/包1 装箱装到平板车上去，使浪费的空间最小。
MinZ=X1+X2+X3+X4+X5+X6 s.t： X1+X2≥1
X1+X2+X6≥1 X3+X4≥1 X3+X4+X5≥1 X4+X5+X6≥1 X2+X5+X6≥1 Xj=0，1；j=1，2，3，4，5，6。
2020/4/1
2020/4/1
5. 指派问题
在生活中经常遇到这样的问题，某单位需要 完成n项任务，恰好有n个人可以承担这些任务， 由于每个人的专长不同，个人完成不同任务的效率 （时间、费用等）也不同。