Page:1
QSC华东理工大学 工商经济学院 运筹学运筹学目标规划
Page:2
QSC华东理工大学 工商经济学院 运筹学多目标决策问题实际问题决策经常面临的问题：
方案优劣并不以单一准则为目标,而是以多重准则为目标
约束条件并不完全符合严格的刚性条件,具有一定的弹性可能的弹性约束,
最好等于
最好不大于
最好不小于
Page:3
QSC华东理工大学 工商经济学院 运筹学弹性约束的处理方法实际量＋ d－ － d+ = 目标值负偏差变量 正偏差变量
ddM in 最好等于：
dM in 最好不大于：
dM in 最好不小于：
Page:4
QSC华东理工大学 工商经济学院 运筹学顾客访问策略老顾客 新顾客 正常可用访问时间访问每一顾客所需时间 2 3 640 小时平均可获销售利润 250 125
目标：
访问时间最好不超过 680小时；
访问时间最好不少于 600小时；
销售收入尽量不少于 70,000；
访问老顾客数最好不少于 200个；
访问新顾客数最好不少于 120个
Page:5
QSC华东理工大学 工商经济学院 运筹学模型－ 顾客访问策略
0
120
200
000,70125250
60032
68032
552
441
3321
2221
1121
5544332211
所有变量
ddx
ddx
ddxx
ddxx
ddxx
St
dPdPdPdPdPZM i n
Page:6
QSC华东理工大学 工商经济学院 运筹学目标规划解的几何分析
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
(4)
4d?4d
(5)
5d
5d
Page:7
QSC华东理工大学 工商经济学院 运筹学
0
120
200
000,70125250
60032
68032
552
441
3321
2221
1121
5544332211
所有变量
ddx
ddx
ddxx
ddxx
ddxx
St
dPdPdPdPdPZM i n
目标规划的求解 ---序贯算法
Page:8
QSC华东理工大学 工商经济学院 运筹学
0
68 032
1121
1
所有变量
ddxx
St
dZM in
0
68 032
0
21
1
所有变量
xx
d
第一级目标
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
Page:9
QSC华东理工大学 工商经济学院 运筹学
0
60032
68032
2221
21
2
所有变量
ddxx
xx
St
dZM in
第二级目标
0
60 032
68 032
0
21
21
2
所有变量
xx
xx
d
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
Page:10
QSC华东理工大学 工商经济学院 运筹学第三级目标
0
000,70125250
60032
68032
0
21
21
21
3
所有变量
xx
xx
xx
d X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
0
000,70125250
60032
68032
3321
21
21
3
所有变量
ddxx
xx
xx
St
dZM i n
Page:11
QSC华东理工大学 工商经济学院 运筹学
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
(4)
4d?4d
0
200
000,70125250
60032
68032
441
21
21
21
4
所有变量
ddx
xx
xx
xx
St
dZM in
第四级目标
0
200
000,70125250
60032
68032
0
1
21
21
21
4
所有变量
x
xx
xx
xx
d
Page:12
QSC华东理工大学 工商经济学院 运筹学
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
(4)
4d?4d
(5)
5d
5d
第五级目标
…………
Page:13
QSC华东理工大学 工商经济学院 运筹学目标规划的求解 ---多阶段算法
0
120
200
000,70125250
60032
68032
552
441
3321
2221
1121
5544332211
所有变量
ddx
ddx
ddxx
ddxx
ddxx
St
dPdPdPdPdPZM i n
Page:14
QSC华东理工大学 工商经济学院 运筹学初始单纯形表
0 0 0 P
1
P
2
0 P
3
0 P
4
0 P
5
0
x
1
x
2 d
1
-
d
1
+
d
2
-
d
2
+
d
3
-
d
3
+
d
4
-
d
4
+
d
5
-
d
5
+
R H S 比值
0 2 3 1 -1 0 0 0 0 0 0 0 0 680 6 8 0 / 3
P
2
2 3 0 0 1 -1 0 0 0 0 0 0 600 6 0 0 / 3
P
3
250 125 0 0 0 0 1 -1 0 0 0 0 70000 7 0 0 0 0 / 1 2 5
P
4
1 0 0 0 0 0 0 0 1 -1 0 0 200 -
P
5
0 1 0 0 0 0 0 0 0 0 1 -1 120 1 2 0 / 1
P
1
0 0 0 1 0 0 0 0 0 0 0 0
P
2
-2 -3 0 0 0 1 0 0 0 0 0 0
P
3
-2 5 0 -1 2 5 0 0 0 0 0 1 0 0 0 0
P
4
-1 0 0 0 0 0 0 0 0 1 0 0
P
5
0 -1 0 0 0 0 0 0 0 0 0 1
d
3
-
d
1
-
d
2
-
d
4
-
d
5
-
检验数
Page:15
QSC华东理工大学 工商经济学院 运筹学单纯形表运算
0 0 0 P
1
P
2
0 P
3
0 P
4
0 P
5
0
x
1
x
2 d
1
-
d
1
+
d
2
-
d
2
+
d
3
-
d
3
+
d
4
-
d
4
+
d
5
-
d
5
+
R H S 比值
0 2 0 1 -1 0 0 0 0 0 0 -3 3 320 3 2 0 / 3
P
2
2 0 0 0 1 -1 0 0 0 0 -3 3 240 2 4 0 / 3
P
3
250 0 0 0 0 0 1 -1 0 0 -1 2 5 125 55000 5 5 0 0 0 / 1 2 5
P
4
1 0 0 0 0 0 0 0 1 -1 0 0 200 -
0 0 1 0 0 0 0 0 0 0 0 1 -1 120 -
P
1
0 0 0 1 0 0 0 0 0 0 0 0
P
2
-2 0 0 0 0 1 0 0 0 0 3 -3
P
3
-2 5 0 0 0 0 0 0 0 1 0 0 125 -1 2 5
P
4
-1 0 0 0 0 0 0 0 0 1 0 0
P
5
0 0 0 0 0 0 0 0 0 0 1 0
d
3
-
d
1
-
d
2
-
d
4
-
x
2
检验数
Page:16
QSC华东理工大学 工商经济学院 运筹学单纯形表运算
0 0 0 P
1
P
2
0 P
3
0 P
4
0 P
5
0
x
1
x
2 d
1
-
d
1
+
d
2
-
d
2
+
d
3
-
d
3
+
d
4
-
d
4
+
d
5
-
d
5
+
R H S 比值
0 0 0 1 -1 -1 1 0 0 0 0 0 0 80 -
0 2 / 3 0 0 0 1 / 3 -1 / 3 0 0 0 0 -1 1 80 8 0 / (2 / 3 )
P
3
500/ 3
0 0 0
-125/ 3 -125/ 3
1 -1 0 0 0 0 45000 4 5 0 0 0 / ( 5 0 0 / 3
)
P
4
1 0 0 0 0 0 0 0 1 -1 0 0 200 2 0 0 / 1
0 2 / 3 1 0 0 1 / 3 -1 / 3 0 0 0 0 0 0 200 2 0 0 / (2 / 3 )
P
1
0 0 0 1 0 0 0 0 0 0 0 0
P
2
0 0 0 0 1 1 0 0 0 0 0 0
P
3
-500/ 3
0 0 0
125/ 3 125/ 3
0 1 0 0 0 0
P
4
-1 0 0 0 0 0 0 0 0 1 0 0
P
5
0 0 0 0 0 0 0 0 0 0 1 0
d
3
-
d
1
-
d
5
+
d
4
-
x
2
检验数
…
Page:17
QSC华东理工大学 工商经济学院 运筹学运筹学整数线性规划
Page:18
QSC华东理工大学 工商经济学院 运筹学整数线性规划问题的一般形式
m a x ( m i n ) z c x c x c xn n1 1 2 2?
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
).(
).(
).(
..
2211
22222121
11212111
中部分或全部取整数nxxx,,11?
Page:19
QSC华东理工大学 工商经济学院 运筹学整数线性规划问题的分类
全整数线性规划
混合整数线性规划
0-1整数线性规划
Page:20
QSC华东理工大学 工商经济学院 运筹学整数规划与其松弛问题当放弃整数约束时得到的线性规划称为整数规划的松弛问题。
整数规划的可行域是松弛问题的可行域，反之不成立。
Page:21
QSC华东理工大学 工商经济学院 运筹学全整数规划的求解 ---Gomory割平面方法
为整数x,x
0x,x
5x2x
104x5x
3x23x
,,
x3xzm ax
21
21
21
21
21
21
ts
1
3
2
X 2
X
1 2 2.5 1
5
4
整数点松弛问题最优解
Page:22
QSC华东理工大学 工商经济学院 运筹学松弛问题的最优解
3 -1 0 0 0
x
1
x
2
x
3
x
4
x
5
R H S
3 1 0 1 / 7 0 2 / 7 1 3 / 7
-1 0 1 -2 / 7 0 3 / 7 9 / 7
0 0 0 -3 / 7 1 2 2 / 7 3 1 / 7
0 0 -5 / 7 0 -3 / 7
x
4
x
1
x
2
检验数
Page:23
QSC华东理工大学 工商经济学院 运筹学
Gomory定理
000,ijjii bxax
在松弛问题的最优单纯形表中，假如有一常数项 不是整数，且对应的方程为：
0ib
000
000,,
iii
jijiji
fNb
fNa
分解 和 成最大整数与正分数之和：
jia,0 0ib
Page:24
QSC华东理工大学 工商经济学院 运筹学
000,ijjii bxax
00000 )(,,iijjijii fNxfNx
jjiiijjii xffNxNx,,00000
0,00 jjii xff
则包含了整数规划的所有整数可行解，但不包括松弛问题的最优解
Page:25
QSC华东理工大学 工商经济学院 运筹学例题求解选择第一个方程：
7
13
7
2
7
1
531 xxx
分解为：
531 7
2
7
1
7
6
1 xxx
Page:26
QSC华东理工大学 工商经济学院 运筹学
0
7
2
7
1
7
6
53 xx
在原松弛问题中加入约束：
7
6
7
2
7
1
653 xxx
即形成松弛问题 2
Page:27
QSC华东理工大学 工商经济学院 运筹学
3 -1 0 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
3 1 0 1 / 7 0 2 / 7 0 1 3 / 7
-1 0 1 -2 / 7 0 3 / 7 0 9 / 7
0 0 0 -3 / 7 1 2 2 / 7 0 3 1 / 7
0 0 0 -1 / 7 0 -2 / 7 1 -6 / 7
0 0 -5 / 7 0 -3 / 7 0
x 4
x 1
x 2
检验数
x 6
3 -1 0 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
3 1 0 0 0 0 1 1
-1 0 1 0 -1 / 4 0 -5 / 4 5 / 4
0 0 0 1 -1 / 2 0 -1 1 / 2 5 / 2
0 0 0 0 1 / 4 1 -3 / 4 7 / 4
0 0 0 -1 / 4 0 -1 7 / 4
x 3
x 1
x 2
检验数
x 5
Page:28
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
X
1 2 2.5 1
5
4
整数点松弛问题 2的最优解
01
0
7
2
7
1
7
6
1
53
x
xx
或：
割平面
Page:29
QSC华东理工大学 工商经济学院 运筹学选择第四个方程（具有最大分数部分）：
4
7
4
3
4
1
645 xxx
分解为：
6465 4
1
4
1
4
31 xxxx
Page:30
QSC华东理工大学 工商经济学院 运筹学在松弛问题 2中加入约束：
即形成松弛问题 3
0
4
1
4
1
4
3
64 xx
4
3
4
1
4
1
764 xxx
Page:31
QSC华东理工大学 工商经济学院 运筹学
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 -1 / 4 0 -5 / 4 0 5 / 4
0 0 0 1 -1 / 2 0 -1 1 / 2 0 5 / 2
0 0 0 0 1 / 4 1 -3 / 4 0 7 / 4
0 0 0 0 -1 / 4 0 -1 / 4 1 -3 / 4
0 0 0 -1 / 4 0 -1 7 / 4 0
x
3
x
1
x
2
检验数
x
5
x
7
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 0 0 -1 -1 2
0 0 0 1 0 0 -5 -2 4
0 0 0 0 0 1 -1 1 1
0 0 0 0 1 0 1 -4 3
0 0 0 0 0 -4 0
x
3
x
1
x
2
检验数
x
5
x
7
得到最优解
Page:32
QSC华东理工大学 工商经济学院 运筹学割平面：
52
1045
323
7
6
7
2
7
1
4
3
4
1
4
1
521
421
321
653
64
xxx
xxx
xxx
xxx
xx
32 21 xx
1
3
2
X 2
X
1 2 2.5 1
5
4
松弛问题 3
的最优解松弛问题 2
的最优解
Page:33
QSC华东理工大学 工商经济学院 运筹学如果选择第二个方程：
4
5
4
5
4
1
642 xxx
分解为：
64642 4
3
4
3
4
112 xxxxx
Page:34
QSC华东理工大学 工商经济学院 运筹学在松弛问题 2中加入约束：
即形成松弛问题 3
0
4
3
4
3
4
1
64 xx
4
1
4
3
4
3
764 xxx
Page:35
QSC华东理工大学 工商经济学院 运筹学
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 -1 / 4 0 -5 / 4 0 5 / 4
0 0 0 1 -1 / 2 0 -1 1 / 2 0 5 / 2
0 0 0 0 1 / 4 1 -3 / 4 0 7 / 4
0 0 0 0 -3 / 4 0 -3 / 4 1 -1 / 4
0 0 0 -1 / 4 0 -1 7 / 4 0
x
3
x
1
x
2
检验数
x
5
x
7
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 0 0 -1 0 4 / 3
0 0 0 1 0 0 -5 0 8 / 3
0 0 0 0 0 1 -1 0 5 / 3
0 0 0 0 1 0 1 -4 / 3 1 / 3
0 0 0 0 0 -4 0
x
3
x
1
x
2
检验数
x
5
x
4
没有找到整数解，
继续做下去
Page:36
QSC华东理工大学 工商经济学院 运筹学混合整数规划的求解 ---分枝定界方法分枝,当 不符合整数要求时，构造两个约束条件,ii
bx?
1 iiii bxbx 和加入松弛问题分别形成两个子问题（分枝）
定界,当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限
Page:37
QSC华东理工大学 工商经济学院 运筹学例
取整数
21
21
21
21
21
,
0,
3
1
2
14
51
14
9
x
,.
xz m ax
xx
xx
xx
x
ts
x
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S解 S得：
9
41
3
10
,
2
3
,21
z
xxA
Page:38
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S2
对 S分枝：
构造约束：
21?x
和
11?x
形成分枝问题 S1
和 S2，得解 B和 C
S1
)37,1(C )9
23,2(B
941923 );( 2,,?zB
31037 );( 1,,?zC
Page:39
QSC华东理工大学 工商经济学院 运筹学
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
11?x 21?x
Page:40
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S2
对 S1分枝：
构造约束：
32?x
和
22?x
形成分枝问题 S11
和 S12，得解 D
S12
)2,( 1433D
14611433 );,2(,?zD
S11无可行解
Page:41
QSC华东理工大学 工商经济学院 运筹学
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
S11 无可行解S12 D:x1=33/14,x2=2
Z=61/14
11?x
32?x22?x
21?x
Page:42
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S2
对 S12分枝：
构造约束：
31?x
和
21?x
形成分枝问题 S121
和 S122，得解 E和 F
S121
)1,3(E4);( 3,1,?zE
S122
)2,2(F
4);( 2,2,?zF
Page:43
QSC华东理工大学 工商经济学院 运筹学
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
S11 无可行解S12
D:
x1=33/14,x2=2
Z=61/14
11?x
32?x22?x
21?x
S122
F:
x1=2,x2=2
Z=4
S121
E:
x1=3,x2=1
Z=4
31?x2
1?x
Page:44
QSC华东理工大学 工商经济学院 运筹学
0-1整数规划变量只能取 0或 1
的整数线性规划
Page:45
QSC华东理工大学 工商经济学院 运筹学
0-1规划的应用 -项目投资预算资金需求 ( 1000 $)
项 目 估计现值 第一年 第二年 第三年 第四年工厂扩建 90 15 20 20 15
销售网点扩建 40 10 15 20 5
新生产流水线 10 10 0 0 4
新产品研究 37 15 10 10 10
可用资金 40 50 40 35
Page:46
QSC华东理工大学 工商经济学院 运筹学模型变量假设,
项目没有选中如果第选中目项第果如
i
i
x i
0
1
ma x z= 90 x 1 + 40 x 2 + 10 x 3 + 37 x 4
s.t,15 x 1 + 10 x 2 + 10 x 3 + 15 x 4 ≤ 40
20 x 1 + 15 x 2 + 1 0 x 4 ≤ 50
20 x 1 + 20 x 2 + 1 0 x 4 ≤ 40
15 x 1 + 5 x 2 + 4 x 3 + 10 x 4 ≤ 35
x 1,x 2,x 3,x 4,= 0,1
模型,
Page:47
QSC华东理工大学 工商经济学院 运筹学
0-1规划的应用 -工厂 -销售点配置问题生产厂 顾客需求销售点
4
5 D
C
B
A
7
II
III
2
1
3
I
Page:48
QSC华东理工大学 工商经济学院 运筹学工厂 -销售点配置问题 -问题描述
I II III 生产能力
1 800 1,000 1,200 300 35,000
2 400 500 700 200 45,000
3 800 600 500 300 40,000
4 500 600 700 200 42,000
5 700 600 500 400 40,000
A B C D
I 40 80 90 50 40,000
II 70 40 60 80 20,000
III 80 30 50 60 60,000
需求量 200 300 150 250
运输成本,工厂 - 销售点开设的固定成本开设的固定成本运输成本,销售点 - 客户问题,为使经营成本最低,应开设那些工厂及销售点?
Page:49
QSC华东理工大学 工商经济学院 运筹学工厂 -销售点配置问题 -模型参数
销售点不开设第销售点开设第厂不开设第厂开设第
j
jv
i
iu
ji 0
1
0
1
客户运输量销售点到第第销售点运输量厂到第第客户需求量第厂供应能力第销售点开设成本第厂开设成本第客户运价销售点到第第销售点运价厂到第第
kjy
jix
kD
iB
jc
ic
kjc
jic
jk
ij
k
i
j
i
jk
ij
Page:50
QSC华东理工大学 工商经济学院 运筹学工厂 -销售点配置问题 -模型
KkDy
,N,,jvyx
MiuBx
St
vcucycxcZM i n
k
N
j
jk
K
k
jjk
M
i
ij
ii
N
j
ij
j
N
j
ji
N
j
M
i
ijk
K
k
jk
M
i
ij
N
j
ij
,,2,1,
21,)(
,,2,1,
1
11
1
11 111 1
客户需求：
＝供销平衡：
供应能力：
Page:51
QSC华东理工大学 工商经济学院 运筹学
0-1规划的求解 — 隐枚举方法
10,,x
6 4
3 x
44x
22x
,.
523xz m ax
321
32
21
321
321
321
或xx
xx
x
xx
xx
ts
xx
Page:52
QSC华东理工大学 工商经济学院 运筹学
(x
1
,x
2
,x
3
) z 值 过滤条件
（ 1 ） （ 2 ） （ 3 ） （ 4 ）
（ 0,0,0 ） 0 z ≥ 0
（ 0,0,1 ） 5 z ≥ 5
（ 0,1,0 ） -2
（ 0,1,1 ） 3
（ 1,0,0 ） 3
（ 1,0,1 ） 8 z ≥ 8
（ 1,1,0 ） 1
（ 1,1,1 ） 6
约束条件最优解（ x1,x2,x3)=(1,0,1); z=8
隐枚举方法求解过程
Page:53
QSC华东理工大学 工商经济学院 运筹学经典指派问题
n个员工分配作 n项工作，一致的 i个员工作的 j项工作的成本为
cij,i=1,…,n; j=1,…,n 。求最佳分配方案。
Page:54
QSC华东理工大学 工商经济学院 运筹学指派问题的数学模型
0
1
否则项工作员工分配做第第 jix
ij
n
1i
n
1j
ijijc=zM in x
n,1,2,=i 1x
n
1j
ij
n,1,2,=j 1x
n
1i
ij
n,1,=jn;,1,2,=i 1,0x ij或?
s.t.
Page:55
QSC华东理工大学 工商经济学院 运筹学
nnnnn
n
n
n
cccc
cccc
cccc
cccc
C
321
3333231
2232221
1131211
指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小
Page:56
QSC华东理工大学 工商经济学院 运筹学例
B
1
B
2
B
3
B
4
B
5
A
1
4 8 7 15 12
A
2
7 9 17 14 10
A
3
6 9 12 8 7
A
4
6 7 14 6 10
A
5
6 9 12 10 6cij
Page:57
QSC华东理工大学 工商经济学院 运筹学指派问题的性质定理,对于指派问题，成本矩阵的任一行 (或列 )减去 (或加上 )一个相同的数得到的新指派问题与原问题同解
Page:58
QSC华东理工大学 工商经济学院 运筹学
s)(
s)(xcxc
xs)(xcxc
s ) x(cxc=z
n
1j
kjkj
n
ki
1i
n
1j
ijij
n
1j
kj
n
1j
kjkj
n
ki
1i
n
1j
ijij
n
1j
kjkj
n
ki
1i
n
1j
ijij
z
Page:59
QSC华东理工大学 工商经济学院 运筹学指派问题的求解 -匈牙利方法成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个 0。
如果划去这些 0所需要的直线数不少于 n，
则此时就可以求得最优解。
Page:60
QSC华东理工大学 工商经济学院 运筹学例题求解
6101296
1061476
781296
10141797
1215784
6
6
6
7
4
31
04630
40810
12630
371020
811340
04320
40500
12320
37710
811030
04320
40500
12320
37710
811030
Page:61
QSC华东理工大学 工商经济学院 运筹学
04320
40500
12320
37710
811030
04321
40501
01210
21100
811031
04321
40501
01210
21100
811031
Page:62
QSC华东理工大学 工商经济学院 运筹学一般指派问题
最大化指派问题
人数和工作数不等的指派问题
一个人可做几项工作的指派问题
某项工作一定不能由某人做的指派问题
Page:63
QSC华东理工大学 工商经济学院 运筹学最大化指派问题
6101296
10617711
781296
10142912
1215784最大化指派问题最大值
61710171217917617
101761717177171117
7178171217917617
101714172179171217
12171517717817417
1175811
7110106
1095811
731585
5210913
最小化指派问题
Page:64
QSC华东理工大学 工商经济学院 运筹学人数和工作数不等的指派问题
101296
617711
81296
142912
15784
101296
617711
81296
142912
15784
0
0
0
0
0
Page:65
QSC华东理工大学 工商经济学院 运筹学一个人可做几项工作的指派问题
78329
82476
31952
3
2
1
54321
BBBBB
A
A
A
31952
31952
78329
82476
31952
54321
1
1
3
2
1
BBBBB
A
A
A
A
AA1可同时做三项工作
Page:66
QSC华东理工大学 工商经济学院 运筹学某项工作一定不能由某人做的指派问题
45278
29461
7829
82476
3952
54321
5
4
3
2
1
BBBBB
A
A
A
A
A
4 5 2 78
2 9 4 61
7829
82476
3952
54321
5
4
3
2
1
M
M
A
A
A
A
A
BBBBB
A1不能做 B4;
A3不能做 B3
QSC华东理工大学 工商经济学院 运筹学运筹学目标规划
Page:2
QSC华东理工大学 工商经济学院 运筹学多目标决策问题实际问题决策经常面临的问题：
方案优劣并不以单一准则为目标,而是以多重准则为目标
约束条件并不完全符合严格的刚性条件,具有一定的弹性可能的弹性约束,
最好等于
最好不大于
最好不小于
Page:3
QSC华东理工大学 工商经济学院 运筹学弹性约束的处理方法实际量＋ d－ － d+ = 目标值负偏差变量 正偏差变量
ddM in 最好等于：
dM in 最好不大于：
dM in 最好不小于：
Page:4
QSC华东理工大学 工商经济学院 运筹学顾客访问策略老顾客 新顾客 正常可用访问时间访问每一顾客所需时间 2 3 640 小时平均可获销售利润 250 125
目标：
访问时间最好不超过 680小时；
访问时间最好不少于 600小时；
销售收入尽量不少于 70,000；
访问老顾客数最好不少于 200个；
访问新顾客数最好不少于 120个
Page:5
QSC华东理工大学 工商经济学院 运筹学模型－ 顾客访问策略
0
120
200
000,70125250
60032
68032
552
441
3321
2221
1121
5544332211
所有变量
ddx
ddx
ddxx
ddxx
ddxx
St
dPdPdPdPdPZM i n
Page:6
QSC华东理工大学 工商经济学院 运筹学目标规划解的几何分析
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
(4)
4d?4d
(5)
5d
5d
Page:7
QSC华东理工大学 工商经济学院 运筹学
0
120
200
000,70125250
60032
68032
552
441
3321
2221
1121
5544332211
所有变量
ddx
ddx
ddxx
ddxx
ddxx
St
dPdPdPdPdPZM i n
目标规划的求解 ---序贯算法
Page:8
QSC华东理工大学 工商经济学院 运筹学
0
68 032
1121
1
所有变量
ddxx
St
dZM in
0
68 032
0
21
1
所有变量
xx
d
第一级目标
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
Page:9
QSC华东理工大学 工商经济学院 运筹学
0
60032
68032
2221
21
2
所有变量
ddxx
xx
St
dZM in
第二级目标
0
60 032
68 032
0
21
21
2
所有变量
xx
xx
d
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
Page:10
QSC华东理工大学 工商经济学院 运筹学第三级目标
0
000,70125250
60032
68032
0
21
21
21
3
所有变量
xx
xx
xx
d X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
0
000,70125250
60032
68032
3321
21
21
3
所有变量
ddxx
xx
xx
St
dZM i n
Page:11
QSC华东理工大学 工商经济学院 运筹学
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
(4)
4d?4d
0
200
000,70125250
60032
68032
441
21
21
21
4
所有变量
ddx
xx
xx
xx
St
dZM in
第四级目标
0
200
000,70125250
60032
68032
0
1
21
21
21
4
所有变量
x
xx
xx
xx
d
Page:12
QSC华东理工大学 工商经济学院 运筹学
X
100
300
200
600
500
400
X 2
100 200 300 400 500 1
(1)
1d
1d
(2)
2d
2d
(3)
3d
3d
(4)
4d?4d
(5)
5d
5d
第五级目标
…………
Page:13
QSC华东理工大学 工商经济学院 运筹学目标规划的求解 ---多阶段算法
0
120
200
000,70125250
60032
68032
552
441
3321
2221
1121
5544332211
所有变量
ddx
ddx
ddxx
ddxx
ddxx
St
dPdPdPdPdPZM i n
Page:14
QSC华东理工大学 工商经济学院 运筹学初始单纯形表
0 0 0 P
1
P
2
0 P
3
0 P
4
0 P
5
0
x
1
x
2 d
1
-
d
1
+
d
2
-
d
2
+
d
3
-
d
3
+
d
4
-
d
4
+
d
5
-
d
5
+
R H S 比值
0 2 3 1 -1 0 0 0 0 0 0 0 0 680 6 8 0 / 3
P
2
2 3 0 0 1 -1 0 0 0 0 0 0 600 6 0 0 / 3
P
3
250 125 0 0 0 0 1 -1 0 0 0 0 70000 7 0 0 0 0 / 1 2 5
P
4
1 0 0 0 0 0 0 0 1 -1 0 0 200 -
P
5
0 1 0 0 0 0 0 0 0 0 1 -1 120 1 2 0 / 1
P
1
0 0 0 1 0 0 0 0 0 0 0 0
P
2
-2 -3 0 0 0 1 0 0 0 0 0 0
P
3
-2 5 0 -1 2 5 0 0 0 0 0 1 0 0 0 0
P
4
-1 0 0 0 0 0 0 0 0 1 0 0
P
5
0 -1 0 0 0 0 0 0 0 0 0 1
d
3
-
d
1
-
d
2
-
d
4
-
d
5
-
检验数
Page:15
QSC华东理工大学 工商经济学院 运筹学单纯形表运算
0 0 0 P
1
P
2
0 P
3
0 P
4
0 P
5
0
x
1
x
2 d
1
-
d
1
+
d
2
-
d
2
+
d
3
-
d
3
+
d
4
-
d
4
+
d
5
-
d
5
+
R H S 比值
0 2 0 1 -1 0 0 0 0 0 0 -3 3 320 3 2 0 / 3
P
2
2 0 0 0 1 -1 0 0 0 0 -3 3 240 2 4 0 / 3
P
3
250 0 0 0 0 0 1 -1 0 0 -1 2 5 125 55000 5 5 0 0 0 / 1 2 5
P
4
1 0 0 0 0 0 0 0 1 -1 0 0 200 -
0 0 1 0 0 0 0 0 0 0 0 1 -1 120 -
P
1
0 0 0 1 0 0 0 0 0 0 0 0
P
2
-2 0 0 0 0 1 0 0 0 0 3 -3
P
3
-2 5 0 0 0 0 0 0 0 1 0 0 125 -1 2 5
P
4
-1 0 0 0 0 0 0 0 0 1 0 0
P
5
0 0 0 0 0 0 0 0 0 0 1 0
d
3
-
d
1
-
d
2
-
d
4
-
x
2
检验数
Page:16
QSC华东理工大学 工商经济学院 运筹学单纯形表运算
0 0 0 P
1
P
2
0 P
3
0 P
4
0 P
5
0
x
1
x
2 d
1
-
d
1
+
d
2
-
d
2
+
d
3
-
d
3
+
d
4
-
d
4
+
d
5
-
d
5
+
R H S 比值
0 0 0 1 -1 -1 1 0 0 0 0 0 0 80 -
0 2 / 3 0 0 0 1 / 3 -1 / 3 0 0 0 0 -1 1 80 8 0 / (2 / 3 )
P
3
500/ 3
0 0 0
-125/ 3 -125/ 3
1 -1 0 0 0 0 45000 4 5 0 0 0 / ( 5 0 0 / 3
)
P
4
1 0 0 0 0 0 0 0 1 -1 0 0 200 2 0 0 / 1
0 2 / 3 1 0 0 1 / 3 -1 / 3 0 0 0 0 0 0 200 2 0 0 / (2 / 3 )
P
1
0 0 0 1 0 0 0 0 0 0 0 0
P
2
0 0 0 0 1 1 0 0 0 0 0 0
P
3
-500/ 3
0 0 0
125/ 3 125/ 3
0 1 0 0 0 0
P
4
-1 0 0 0 0 0 0 0 0 1 0 0
P
5
0 0 0 0 0 0 0 0 0 0 1 0
d
3
-
d
1
-
d
5
+
d
4
-
x
2
检验数
…
Page:17
QSC华东理工大学 工商经济学院 运筹学运筹学整数线性规划
Page:18
QSC华东理工大学 工商经济学院 运筹学整数线性规划问题的一般形式
m a x ( m i n ) z c x c x c xn n1 1 2 2?
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
).(
).(
).(
..
2211
22222121
11212111
中部分或全部取整数nxxx,,11?
Page:19
QSC华东理工大学 工商经济学院 运筹学整数线性规划问题的分类
全整数线性规划
混合整数线性规划
0-1整数线性规划
Page:20
QSC华东理工大学 工商经济学院 运筹学整数规划与其松弛问题当放弃整数约束时得到的线性规划称为整数规划的松弛问题。
整数规划的可行域是松弛问题的可行域，反之不成立。
Page:21
QSC华东理工大学 工商经济学院 运筹学全整数规划的求解 ---Gomory割平面方法
为整数x,x
0x,x
5x2x
104x5x
3x23x
,,
x3xzm ax
21
21
21
21
21
21
ts
1
3
2
X 2
X
1 2 2.5 1
5
4
整数点松弛问题最优解
Page:22
QSC华东理工大学 工商经济学院 运筹学松弛问题的最优解
3 -1 0 0 0
x
1
x
2
x
3
x
4
x
5
R H S
3 1 0 1 / 7 0 2 / 7 1 3 / 7
-1 0 1 -2 / 7 0 3 / 7 9 / 7
0 0 0 -3 / 7 1 2 2 / 7 3 1 / 7
0 0 -5 / 7 0 -3 / 7
x
4
x
1
x
2
检验数
Page:23
QSC华东理工大学 工商经济学院 运筹学
Gomory定理
000,ijjii bxax
在松弛问题的最优单纯形表中，假如有一常数项 不是整数，且对应的方程为：
0ib
000
000,,
iii
jijiji
fNb
fNa
分解 和 成最大整数与正分数之和：
jia,0 0ib
Page:24
QSC华东理工大学 工商经济学院 运筹学
000,ijjii bxax
00000 )(,,iijjijii fNxfNx
jjiiijjii xffNxNx,,00000
0,00 jjii xff
则包含了整数规划的所有整数可行解，但不包括松弛问题的最优解
Page:25
QSC华东理工大学 工商经济学院 运筹学例题求解选择第一个方程：
7
13
7
2
7
1
531 xxx
分解为：
531 7
2
7
1
7
6
1 xxx
Page:26
QSC华东理工大学 工商经济学院 运筹学
0
7
2
7
1
7
6
53 xx
在原松弛问题中加入约束：
7
6
7
2
7
1
653 xxx
即形成松弛问题 2
Page:27
QSC华东理工大学 工商经济学院 运筹学
3 -1 0 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
3 1 0 1 / 7 0 2 / 7 0 1 3 / 7
-1 0 1 -2 / 7 0 3 / 7 0 9 / 7
0 0 0 -3 / 7 1 2 2 / 7 0 3 1 / 7
0 0 0 -1 / 7 0 -2 / 7 1 -6 / 7
0 0 -5 / 7 0 -3 / 7 0
x 4
x 1
x 2
检验数
x 6
3 -1 0 0 0 0
x 1 x 2 x 3 x 4 x 5 x 6 R H S
3 1 0 0 0 0 1 1
-1 0 1 0 -1 / 4 0 -5 / 4 5 / 4
0 0 0 1 -1 / 2 0 -1 1 / 2 5 / 2
0 0 0 0 1 / 4 1 -3 / 4 7 / 4
0 0 0 -1 / 4 0 -1 7 / 4
x 3
x 1
x 2
检验数
x 5
Page:28
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
X
1 2 2.5 1
5
4
整数点松弛问题 2的最优解
01
0
7
2
7
1
7
6
1
53
x
xx
或：
割平面
Page:29
QSC华东理工大学 工商经济学院 运筹学选择第四个方程（具有最大分数部分）：
4
7
4
3
4
1
645 xxx
分解为：
6465 4
1
4
1
4
31 xxxx
Page:30
QSC华东理工大学 工商经济学院 运筹学在松弛问题 2中加入约束：
即形成松弛问题 3
0
4
1
4
1
4
3
64 xx
4
3
4
1
4
1
764 xxx
Page:31
QSC华东理工大学 工商经济学院 运筹学
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 -1 / 4 0 -5 / 4 0 5 / 4
0 0 0 1 -1 / 2 0 -1 1 / 2 0 5 / 2
0 0 0 0 1 / 4 1 -3 / 4 0 7 / 4
0 0 0 0 -1 / 4 0 -1 / 4 1 -3 / 4
0 0 0 -1 / 4 0 -1 7 / 4 0
x
3
x
1
x
2
检验数
x
5
x
7
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 0 0 -1 -1 2
0 0 0 1 0 0 -5 -2 4
0 0 0 0 0 1 -1 1 1
0 0 0 0 1 0 1 -4 3
0 0 0 0 0 -4 0
x
3
x
1
x
2
检验数
x
5
x
7
得到最优解
Page:32
QSC华东理工大学 工商经济学院 运筹学割平面：
52
1045
323
7
6
7
2
7
1
4
3
4
1
4
1
521
421
321
653
64
xxx
xxx
xxx
xxx
xx
32 21 xx
1
3
2
X 2
X
1 2 2.5 1
5
4
松弛问题 3
的最优解松弛问题 2
的最优解
Page:33
QSC华东理工大学 工商经济学院 运筹学如果选择第二个方程：
4
5
4
5
4
1
642 xxx
分解为：
64642 4
3
4
3
4
112 xxxxx
Page:34
QSC华东理工大学 工商经济学院 运筹学在松弛问题 2中加入约束：
即形成松弛问题 3
0
4
3
4
3
4
1
64 xx
4
1
4
3
4
3
764 xxx
Page:35
QSC华东理工大学 工商经济学院 运筹学
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 -1 / 4 0 -5 / 4 0 5 / 4
0 0 0 1 -1 / 2 0 -1 1 / 2 0 5 / 2
0 0 0 0 1 / 4 1 -3 / 4 0 7 / 4
0 0 0 0 -3 / 4 0 -3 / 4 1 -1 / 4
0 0 0 -1 / 4 0 -1 7 / 4 0
x
3
x
1
x
2
检验数
x
5
x
7
3 -1 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
R H S
3 1 0 0 0 0 1 0 1
-1 0 1 0 0 0 -1 0 4 / 3
0 0 0 1 0 0 -5 0 8 / 3
0 0 0 0 0 1 -1 0 5 / 3
0 0 0 0 1 0 1 -4 / 3 1 / 3
0 0 0 0 0 -4 0
x
3
x
1
x
2
检验数
x
5
x
4
没有找到整数解，
继续做下去
Page:36
QSC华东理工大学 工商经济学院 运筹学混合整数规划的求解 ---分枝定界方法分枝,当 不符合整数要求时，构造两个约束条件,ii
bx?
1 iiii bxbx 和加入松弛问题分别形成两个子问题（分枝）
定界,当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限
Page:37
QSC华东理工大学 工商经济学院 运筹学例
取整数
21
21
21
21
21
,
0,
3
1
2
14
51
14
9
x
,.
xz m ax
xx
xx
xx
x
ts
x
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S解 S得：
9
41
3
10
,
2
3
,21
z
xxA
Page:38
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S2
对 S分枝：
构造约束：
21?x
和
11?x
形成分枝问题 S1
和 S2，得解 B和 C
S1
)37,1(C )9
23,2(B
941923 );( 2,,?zB
31037 );( 1,,?zC
Page:39
QSC华东理工大学 工商经济学院 运筹学
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
11?x 21?x
Page:40
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S2
对 S1分枝：
构造约束：
32?x
和
22?x
形成分枝问题 S11
和 S12，得解 D
S12
)2,( 1433D
14611433 );,2(,?zD
S11无可行解
Page:41
QSC华东理工大学 工商经济学院 运筹学
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
S11 无可行解S12 D:x1=33/14,x2=2
Z=61/14
11?x
32?x22?x
21?x
Page:42
QSC华东理工大学 工商经济学院 运筹学
1
3
2
X 2
5
4
X
1 2 3 1
)310,23(A
S2
对 S12分枝：
构造约束：
31?x
和
21?x
形成分枝问题 S121
和 S122，得解 E和 F
S121
)1,3(E4);( 3,1,?zE
S122
)2,2(F
4);( 2,2,?zF
Page:43
QSC华东理工大学 工商经济学院 运筹学
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
S11 无可行解S12
D:
x1=33/14,x2=2
Z=61/14
11?x
32?x22?x
21?x
S122
F:
x1=2,x2=2
Z=4
S121
E:
x1=3,x2=1
Z=4
31?x2
1?x
Page:44
QSC华东理工大学 工商经济学院 运筹学
0-1整数规划变量只能取 0或 1
的整数线性规划
Page:45
QSC华东理工大学 工商经济学院 运筹学
0-1规划的应用 -项目投资预算资金需求 ( 1000 $)
项 目 估计现值 第一年 第二年 第三年 第四年工厂扩建 90 15 20 20 15
销售网点扩建 40 10 15 20 5
新生产流水线 10 10 0 0 4
新产品研究 37 15 10 10 10
可用资金 40 50 40 35
Page:46
QSC华东理工大学 工商经济学院 运筹学模型变量假设,
项目没有选中如果第选中目项第果如
i
i
x i
0
1
ma x z= 90 x 1 + 40 x 2 + 10 x 3 + 37 x 4
s.t,15 x 1 + 10 x 2 + 10 x 3 + 15 x 4 ≤ 40
20 x 1 + 15 x 2 + 1 0 x 4 ≤ 50
20 x 1 + 20 x 2 + 1 0 x 4 ≤ 40
15 x 1 + 5 x 2 + 4 x 3 + 10 x 4 ≤ 35
x 1,x 2,x 3,x 4,= 0,1
模型,
Page:47
QSC华东理工大学 工商经济学院 运筹学
0-1规划的应用 -工厂 -销售点配置问题生产厂 顾客需求销售点
4
5 D
C
B
A
7
II
III
2
1
3
I
Page:48
QSC华东理工大学 工商经济学院 运筹学工厂 -销售点配置问题 -问题描述
I II III 生产能力
1 800 1,000 1,200 300 35,000
2 400 500 700 200 45,000
3 800 600 500 300 40,000
4 500 600 700 200 42,000
5 700 600 500 400 40,000
A B C D
I 40 80 90 50 40,000
II 70 40 60 80 20,000
III 80 30 50 60 60,000
需求量 200 300 150 250
运输成本,工厂 - 销售点开设的固定成本开设的固定成本运输成本,销售点 - 客户问题,为使经营成本最低,应开设那些工厂及销售点?
Page:49
QSC华东理工大学 工商经济学院 运筹学工厂 -销售点配置问题 -模型参数
销售点不开设第销售点开设第厂不开设第厂开设第
j
jv
i
iu
ji 0
1
0
1
客户运输量销售点到第第销售点运输量厂到第第客户需求量第厂供应能力第销售点开设成本第厂开设成本第客户运价销售点到第第销售点运价厂到第第
kjy
jix
kD
iB
jc
ic
kjc
jic
jk
ij
k
i
j
i
jk
ij
Page:50
QSC华东理工大学 工商经济学院 运筹学工厂 -销售点配置问题 -模型
KkDy
,N,,jvyx
MiuBx
St
vcucycxcZM i n
k
N
j
jk
K
k
jjk
M
i
ij
ii
N
j
ij
j
N
j
ji
N
j
M
i
ijk
K
k
jk
M
i
ij
N
j
ij
,,2,1,
21,)(
,,2,1,
1
11
1
11 111 1
客户需求：
＝供销平衡：
供应能力：
Page:51
QSC华东理工大学 工商经济学院 运筹学
0-1规划的求解 — 隐枚举方法
10,,x
6 4
3 x
44x
22x
,.
523xz m ax
321
32
21
321
321
321
或xx
xx
x
xx
xx
ts
xx
Page:52
QSC华东理工大学 工商经济学院 运筹学
(x
1
,x
2
,x
3
) z 值 过滤条件
（ 1 ） （ 2 ） （ 3 ） （ 4 ）
（ 0,0,0 ） 0 z ≥ 0
（ 0,0,1 ） 5 z ≥ 5
（ 0,1,0 ） -2
（ 0,1,1 ） 3
（ 1,0,0 ） 3
（ 1,0,1 ） 8 z ≥ 8
（ 1,1,0 ） 1
（ 1,1,1 ） 6
约束条件最优解（ x1,x2,x3)=(1,0,1); z=8
隐枚举方法求解过程
Page:53
QSC华东理工大学 工商经济学院 运筹学经典指派问题
n个员工分配作 n项工作，一致的 i个员工作的 j项工作的成本为
cij,i=1,…,n; j=1,…,n 。求最佳分配方案。
Page:54
QSC华东理工大学 工商经济学院 运筹学指派问题的数学模型
0
1
否则项工作员工分配做第第 jix
ij
n
1i
n
1j
ijijc=zM in x
n,1,2,=i 1x
n
1j
ij
n,1,2,=j 1x
n
1i
ij
n,1,=jn;,1,2,=i 1,0x ij或?
s.t.
Page:55
QSC华东理工大学 工商经济学院 运筹学
nnnnn
n
n
n
cccc
cccc
cccc
cccc
C
321
3333231
2232221
1131211
指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小
Page:56
QSC华东理工大学 工商经济学院 运筹学例
B
1
B
2
B
3
B
4
B
5
A
1
4 8 7 15 12
A
2
7 9 17 14 10
A
3
6 9 12 8 7
A
4
6 7 14 6 10
A
5
6 9 12 10 6cij
Page:57
QSC华东理工大学 工商经济学院 运筹学指派问题的性质定理,对于指派问题，成本矩阵的任一行 (或列 )减去 (或加上 )一个相同的数得到的新指派问题与原问题同解
Page:58
QSC华东理工大学 工商经济学院 运筹学
s)(
s)(xcxc
xs)(xcxc
s ) x(cxc=z
n
1j
kjkj
n
ki
1i
n
1j
ijij
n
1j
kj
n
1j
kjkj
n
ki
1i
n
1j
ijij
n
1j
kjkj
n
ki
1i
n
1j
ijij
z
Page:59
QSC华东理工大学 工商经济学院 运筹学指派问题的求解 -匈牙利方法成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个 0。
如果划去这些 0所需要的直线数不少于 n，
则此时就可以求得最优解。
Page:60
QSC华东理工大学 工商经济学院 运筹学例题求解
6101296
1061476
781296
10141797
1215784
6
6
6
7
4
31
04630
40810
12630
371020
811340
04320
40500
12320
37710
811030
04320
40500
12320
37710
811030
Page:61
QSC华东理工大学 工商经济学院 运筹学
04320
40500
12320
37710
811030
04321
40501
01210
21100
811031
04321
40501
01210
21100
811031
Page:62
QSC华东理工大学 工商经济学院 运筹学一般指派问题
最大化指派问题
人数和工作数不等的指派问题
一个人可做几项工作的指派问题
某项工作一定不能由某人做的指派问题
Page:63
QSC华东理工大学 工商经济学院 运筹学最大化指派问题
6101296
10617711
781296
10142912
1215784最大化指派问题最大值
61710171217917617
101761717177171117
7178171217917617
101714172179171217
12171517717817417
1175811
7110106
1095811
731585
5210913
最小化指派问题
Page:64
QSC华东理工大学 工商经济学院 运筹学人数和工作数不等的指派问题
101296
617711
81296
142912
15784
101296
617711
81296
142912
15784
0
0
0
0
0
Page:65
QSC华东理工大学 工商经济学院 运筹学一个人可做几项工作的指派问题
78329
82476
31952
3
2
1
54321
BBBBB
A
A
A
31952
31952
78329
82476
31952
54321
1
1
3
2
1
BBBBB
A
A
A
A
AA1可同时做三项工作
Page:66
QSC华东理工大学 工商经济学院 运筹学某项工作一定不能由某人做的指派问题
45278
29461
7829
82476
3952
54321
5
4
3
2
1
BBBBB
A
A
A
A
A
4 5 2 78
2 9 4 61
7829
82476
3952
54321
5
4
3
2
1
M
M
A
A
A
A
A
BBBBB
A1不能做 B4;
A3不能做 B3
