3.4指派问题(经典运筹学).ppt

0-1整数规划
1
精选版课件ppt
一、决策问题与0-1变量
1
0
做第i件事
不做第i件事
n件事中必须做k件并只做k件事
n件事中最多做k件事
n件事中至少做k件事
做第i件事的充要条件是做第j件事
做第i件事的充要条件是不做第j件事
只在做了第i件事前提下才考虑是否做第j件事
2
精选版课件ppt
该公司只有600万资金可用于投资，由于技术上的
原因，投资受到以下约束：
1、在项目1、2和3中必须有一项被选中
2、项目3和4只能选中一项
3、项目5被选中的前提是项目1被选中;如何
在 满足上述条件下选择一个最好的投资
方 案，使投资收益最大
例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：
项目
投资额
（万元）
投资收益
（万元）
1
210
150
2
300
210
3
100
60
4
130
80
5
260
180
1
0
投资第i个项目
不投资第i个项目
Z表示投资效益
投资项目模型：
3
精选版课件ppt
例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。
地区
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
请为该市制定一个
最节省的计划
在第i个地区建站
Z表示全区消防站总数
不在第i个地区建站
i=1,2, …,6
布点问题模型：
最优解
x2=1, x4=1
最优值
Z=2
4
精选版课件ppt
二、过滤隐枚举法
（适合于变量个数较少的0-1规划）
（x1 x2 x3)
Z值
约束条件
（1）（2）（3）（4）
过滤条件
（0 0 0）
（0 0 1）
（0 1 0）
（1 0 0）
（1 0 1）
（1 1 0）
（0 1 1）
（1 1 1）
√ √ √ √
0
Z≥0
枚举法：
检验可行解：
32次运算
-2
5
√ √ √ √
Z≥5
3
1
8
×
3
6
运算次数：21
计算目标
函数值：8次
√ √ √ √
5
精选版课件ppt
三、指派问题与匈牙利法
6
精选版课件ppt
设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。
费用
1 2 … j … n
1
2
…
i
…
n
指派问题模型：
i=1,2, …,n
j=1,2, …,n
第i个人做第j 人件事
Z表示总费用
i=1,2, …,n; j=1,2, …,n
第i个人不做第j 人件事
1、指派问题的数学模型
7
精选版课件ppt
i=1,2, …,n
j=1,2, …,n
当n=4时，
有16变量，
8个约束方程
8
精选版课件ppt
例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。
工作
人
费用
1 2 3 4
1
2
3
4
3 5 4 5
6 7 6 8
8 9 8 10
10 10 9 11
1
0
第i人做第j 件事
Z表示总费用
i=1,2, 3,4; j=1,2, 3,4
第i人不做第j 件事
9
精选版课件ppt
2、费用矩阵
设有n个工作，要由 n个人来承担，每个工