第六章 模型决策法
线性规划等
时序与路径规划
分派问题
最短路问题
最大流问题模型决策法优化模型
max (min) 目标函数
s,t,约束条件线性规划模型的建立实例 1
两种产品的生产。已知生产单位产品所需的设备台时及 A,B两种原材料的消耗，资源限制及市场价格如下表：
Ⅰ Ⅱ 资源限制设备 1 1 300台时原材料 A 2 1 400千克原材料 B 0 1 250千克市场价格 50 100
问题：如何安排生产，才能使工厂获利最多？
规划与决策分析：
（ 1）设 x1 — 生产产品 Ⅰ 的数量；
x2 — 生产产品 Ⅱ 的数量。
（ 2）目标函数,MAX 50x1+100x2
（ 3）约束条件,subject to (s.t.):
x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
规划与决策线性规划模型：
max 50x1+100x2
s.t,x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
规划与决策线性规划模型的一般形式
max c1x1+c2x2+ …+ c n xn
s,t,a11x1 + …+ a 1nx n≤ (≥,=) b1
a21x1 + …+ a 2nx n≤ (≥,=) b2
…
am1x1 + …+ a mnx n≤ (≥,=) bm
xij ≥ 0 i =1,…,n,j =1,…,m
规划与决策线性规划应用领域,
合理利用板、线材问题；
配料问题；
投资问题；
生产计划问题、劳动力安排问题；
运输问题、电子商务配送问题；
企业决策问题；企业或商业竞争对策问题等。
规划与决策一 般线性规划建模过程
Step 1,理解及分析实际问题，资源状况，解决问题实现的目标；
Step 2,确定决策变量（ x1,…,xn） — 解决问题的具体方案（量化方案）；
Step 3,确定目标函数及约束条件；
Step 4,应用线性规划软件求解；
Step 5,检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转 Step 1 或
Step2 修改模型。
规划与决策案例 2,（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。
甲、乙两种产品的铸造可以外协加工，
亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：
规划与决策工时与成本 甲 乙 丙 总工时每件铸造工时（小时） 5 10 7 8000
每件机加工工时（小时） 6 4 8 12000
每件装配工时（小时） 3 2 2 10000
自产铸件每件成本（元） 3 5 4
外协铸件每件成本（元） 5 6 -
机加工每件成本（元） 2 1 3
装配每件成本（元） 3 2 2
每件产品售价（元） 23 18 16
问题：如何安排生产计划,使公司获利最大？
规划与决策分析,设 xi — 公司加工 甲,乙,丙三种产品数量,
i=1,2,3。 x4,x5— 由外协铸造后再由本公司 机加工和装配的甲,乙两种产品数量；
目标函数：
每件产品利润分别是：
每件 x1产品利润,23-（ 3+2+3） =15元每件 x2产品利润,18-（ 5+1+2） =10元每件 x3产品利润,16-（ 4+3+2） =7元每件 x4产品利润,23-（ 5+2+3） =13元每件 x5产品利润,18-（ 6+1+2） =9元目标函数为,max 15 x1+10 x2+7 x3+13 x4+9 x5
规划与决策约束条件：
5 x1+10 x2+7 x3 ≤ 8000
6 x1+4 x2+8 x3+6 x4+4 x5 ≤ 12000
3 x1+2 x2+2 x3+3 x4+2 x5 ≤ 10000
xi ≥ 0 i=1,…,5
规划与决策图解法,
Step 1,确定可行域 D = {x | x 满足上述约束条件 }如下图 2-1：
Step 2,确定直线 50x1+100x2=0如下图 2-2：
Step 3,向上移动直线 50x1+100x2=0如图 2-2，
z=50x1+100x2 的值不断地增加,达到 B点时,达到最大；
Step 4,最优解为 B=(50,250),z最大 =27500。
规划与决策
0 100 200 300
300
200
100 D
图 2-1
规划与决策
0 100 200 300
300
200
100 D
B(50,250)
Z= 50x1+100x2 图 2-2
时序与路径规划
讨论各种时序规划问题
介绍时序规划原则
分派问题
运输问题
网络的最短路径
网络的最大流时序规划问题
A
B
E
F
D
C
机器机器D EF C A B
等待处理的一批工作按最优次序排队一台机器工作的时序规划时序规划问题原则：
(1) 最紧迫的优先实例 1：
6种部件作为一批等待一台机器加工。每一部件的平均周需求量、
当前的存货水平以及加工一批所需时间如下表，你将如何安排各种部件的生产次序？
部 件 A B C D E F
平均需求量 10 4 26 34 7 3
当前存货量 72 21 48 92 28 23
加工时间 2.0 1.5 0.5 0.5 1.0 1.5
时序规划问题
1 3è μ? óè
2
3 êy?Y
4 A B C D E F
5 μ±? °′ 72 21 48 92 28 23
6 Dè?ó 10 4 26 34 7 3
7 ′ ó? íê μ? ê± 7,20 5,25 1,85 2,71 4,00 7,67
8
9?- àí μ? êy?Y
10 ′ ó? íê μ? ê± 1,85 2,71 4,00 5,25 7,20 7,67
11 C D E B A F
12 μ±? °′ 48 92 28 21 72 23
13 Dè?ó 26 34 7 4 10 3
14
15 é? 2? ê± 0,5 0,5 1,0 1,5 2,0 1,5
16?a ê? é? 2? ê± 0,0 0,5 1,0 2,0 3,5 5,5
17 íê 3é é? 2? ê± 0,5 1,0 2,0 3,5 5,5 7,0
18 èY ó′ ê± 1,4 1,7 2,0 1,8 1,7 0,7
时序规划问题
2
3 êy?Y
4 A B C D E F
5 μ±? °′ 72 21 48 92 28 23
6 Dè?ó 10 4 26 34 7 3
7 ′ ó? íê μ? ê± 7,20 5,25 1,85 2,71 4,00 7,67
8
9?- àí μ? êy?Y
10 ′ ó? íê μ? ê± 1,85 2,71 4,00 5,25 7,20 7,67
11 C D E B A F
12 μ±? °′ 48 92 28 21 72 23
13 Dè?ó 26 34 7 4 10 3
14
15 é? 2? ê± 0,5 0,5 1,0 1,5 2,0 1,5
16?a ê? é? 2? ê± 0,0 0,5 1,0 2,0 3,5 5,5
17 íê 3é é? 2? ê± 0,5 1,0 2,0 3,5 5,5 7,0
18 èY ó′ ê± 1,35 1,71 2 1,75 1,7 0,67
时序规划问题
A B C D E F G H I
1?ó 1¤ê± 3ì óè
2
3 êy?Y
4 1¤3? A B C D E F G H
5?ó 1¤ê± 2 5 3 8 4 7 2 3
6
7 àí oó êy?Y
8 1¤3? A G C H E B F D
9?ó 1¤ê± 2 2 3 3 4 5 7 8
10
11?a êó 1¤ê± 0,0 2,0 4,0 7,0 10,0 14,0 19,0 26,0
12 íê 3é?ó 1¤ê± 2,0 4,0 7,0 10,0 14,0 19,0 26,0 34,0
以“加工时间最短者优先”为原则时序规划问题
2
3 êy?Y
4 1¤3? A B C D E F G H
5?ó 1¤ê± 2 5 3 8 4 7 2 3
6
7 àí oó êy?Y
8 1¤3? A G C H E B F D
9?ó 1¤ê± 2 2 3 3 4 5 7 8
10
11?a êó 1¤ê± 0,0 2,0 4,0 7,0 10,0 14,0 19,0 26,0
12 íê 3é?ó 1¤ê± 2,0 4,0 7,0 10,0 14,0 19,0 26,0 34,0
以“加工时间最短者优先”为原则时序规划问题
(3) 到期日最近者原则
B C D E F G H I
A B C D E F G H
13 7 8 30 14 20 2 36
G B C A E F D H
2 7 8 13 14 20 30 36
2 5 3 2 4 7 8 3
0,0 2,0 7,0 10,0 12,0 16,0 23,0 31,0
2,0 7,0 10,0 12,0 16,0 23,0 31,0 34,0
0,0 0,0 2,0 0,0 2,0 3,0 1,0 0,0
时序规划问题
(3) 到期日最近者原则
B C D E F G H I
A B C D E F G H
13 7 8 30 14 20 2 36
G B C A E F D H
2 7 8 13 14 20 30 36
2 5 3 2 4 7 8 3
0,0 2,0 7,0 10,0 12,0 16,0 23,0 31,0
2,0 7,0 10,0 12,0 16,0 23,0 31,0 34,0
0,0 0,0 2,0 0,0 2,0 3,0 1,0 0,0
时序规划问题
(4) 延误的工作项目最少第 1步,运用先到期者优先的原则排出工作的初始次序。如果已经没有工作被延误，这便是最优解，否则，则进行第 2步。
第 2步,在安排的时序中找到 1项延误的工作。
第 3步,找出第 2步所找工作之前（包括这一工作本身）加工时间最长的工作。
第 4步,将这一工作从时序安排中抽出来，并更新相应的时间。如果仍然有被延误的工作，再转向第 2步，否则转向第 5步。
第 5步,将第 4步抽出的工作放到时序的末尾。
实例 3,沿用上述实例的 8项工作，求解工作延误项数最少的时序。
为此我们采用上述五个步骤。
工 作 A B C D E F G H
加工时间 2 5 3 8 4 7 2 3
到期时间 13 7 8 30 14 20 2 36
时序规划问题第 1步,将工作按到期时间排序。
工 作 G B C A E F D H
到期时间 2 7 8 13 14 20 30 36
开始加工时间 0 2 7 10 12 16 23 31
加工时间 2 5 3 2 4 7 8 3
完成加工时间 2 7 10 12 16 23 31 34
延误工作 * * * *
第 2步,在上述时序中，第 1项被延误的工作是 C。
第 3步,到 C之前，包括 C在内，加工时间最长的工作是 B，加工时间为 5。
时序规划问题第 4步,抽出工作 B，更新相关的时间：
工 作 G C A E F D H
到期时间 2 8 13 14 20 30 36
开始加工时间 0 2 5 7 11 18 26
加工时间 2 3 2 4 7 8 3
完成加工时间 2 5 7 11 18 26 29
第 5步,现在已经没有工作被延误了，所以我们将工作 B加到时序的最后。
工 作 G C A E F D H B
到期时间 2 8 13 14 20 30 36 7
开始加工时间 0 2 5 7 11 18 26 29
加工时间 2 3 2 4 7 8 3 5
完成加工时间 2 5 7 11 18 26 29 34
现在只有一项工作被延误，平均排队时间为 98/8=12.25，平均延误时间为
27/8=3.375天。
时序规划问题
(5) Johnson’s rule(约翰逊原则 )
步骤 1,列出各项工作及它们在每台机器上的加工时间。
步骤 2,找出下一个在各台机器上加工时间最短的工作。
步骤 3,如果这是在机器 1上，尽量将这一工作安排在前面；如果这是在机器 2上，尽量将这一工作安排在后面。在重复做这些的时候，总是从时序的两端向内进行，新安排的工作离时序的中间更近。
步骤 4,不必再考虑这一工作，回到步骤 2。如果再找不到这样的任务，这就是最优解。
实例 4：
有 7项工作要顺序经过机器 1和机器 2加工。每项工作在每台机器上所需的加工时间如下，如何安排时序才能使机器利用率最高。
工作 A B C D E F G
机器 1 2 5 10 8 4 12 9
时序规划问题
A B C D E F G H
1 o2?2?-?ò
2
3 1¤3? A B C D E F G
4?ú 1 é? μ? ê± 2 5 10 7 4 12 9
5?ú 2 é? μ? ê± 14 7 3 10 5 6 6
6
7 3? ó? ê±D ò A E B D G F C
8?ú 1 éa ê? μ? ê± 0 2 6 11 19 28 40
9?ú 1 é? íê 3é μ? ê± 2 6 11 19 28 40 50
10?ú 2 éa ê? μ? ê± 2 16 21 28 38 44 50
11?ú 2 é? íê 3é μ? ê± 16 21 28 38 44 50 53
时序规划问题
2
3 1¤3? A B C D E F G
4?ú 1 é? μ? ê± 2 5 10 7 4 12 9
5?ú 2 é? μ? ê± 14 7 3 10 5 6 6
6
7 3? ó? ê±D ò A E B D G F C
8?ú 1 éa ê? μ? ê± 0 2 6 11 19 28 40
9?ú 1 é? íê 3é μ? ê± 2 6 11 19 28 40 50
10?ú 2 éa ê? μ? ê± 2 16 21 28 38 44 50
11?ú 2 é? íê 3é μ? ê± 16 21 28 38 44 50 53
分派问题如何以总成本最低为目标将操作员分派到各台机器上。
原则,每个操作员只能分派给一项任务，每项任务只能由一人完成。
Cij 第 i个操作员完成第 j项任务的成本
Xij
min ΣΣCijXij
Σ Xij=1
Σ Xij=1
Xij=0,1 i=1,…,n,j=1,…,m
=1 (分派操作员 i完成任务 j)
=0 (不分派操作员 i完成任务 j)
j
i
最短路问题最短路问题
G(V,E) 为 连通图，边（ vi,vj)的权为 lij，求一条道路，使它从 vs到 vt的总权最少？
方法,1 动态规划法
2 Dijkstra算法引例：某一配送中心要给一个快餐店送快餐原料，应按什么路线送货才能使送货时间最短？
V2 16 v4 7 v6
4 6
V1 12 2 8 v7
18 5
V3 6 v5
（配送中心） （快餐店）
最大流问题最大流问题引例,某石油公司拥有一个管道网络（如图），使用这个网络可以把石油从采地运送到一些销售地。弧上的数字为该管道的容量,问如果使用这个网络系统从
v1向销地 v7运送石油,每小时能运送多少石油？
v1
V2 ( 3,0) v5
(6,0) (2,0) (2,0) (5,0)
v3 V6 v7
(6,0) (3,0) (1,0) (2,0)
v4
(2,0) (4,0)
线性规划等
时序与路径规划
分派问题
最短路问题
最大流问题模型决策法优化模型
max (min) 目标函数
s,t,约束条件线性规划模型的建立实例 1
两种产品的生产。已知生产单位产品所需的设备台时及 A,B两种原材料的消耗，资源限制及市场价格如下表：
Ⅰ Ⅱ 资源限制设备 1 1 300台时原材料 A 2 1 400千克原材料 B 0 1 250千克市场价格 50 100
问题：如何安排生产，才能使工厂获利最多？
规划与决策分析：
（ 1）设 x1 — 生产产品 Ⅰ 的数量；
x2 — 生产产品 Ⅱ 的数量。
（ 2）目标函数,MAX 50x1+100x2
（ 3）约束条件,subject to (s.t.):
x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
规划与决策线性规划模型：
max 50x1+100x2
s.t,x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
规划与决策线性规划模型的一般形式
max c1x1+c2x2+ …+ c n xn
s,t,a11x1 + …+ a 1nx n≤ (≥,=) b1
a21x1 + …+ a 2nx n≤ (≥,=) b2
…
am1x1 + …+ a mnx n≤ (≥,=) bm
xij ≥ 0 i =1,…,n,j =1,…,m
规划与决策线性规划应用领域,
合理利用板、线材问题；
配料问题；
投资问题；
生产计划问题、劳动力安排问题；
运输问题、电子商务配送问题；
企业决策问题；企业或商业竞争对策问题等。
规划与决策一 般线性规划建模过程
Step 1,理解及分析实际问题，资源状况，解决问题实现的目标；
Step 2,确定决策变量（ x1,…,xn） — 解决问题的具体方案（量化方案）；
Step 3,确定目标函数及约束条件；
Step 4,应用线性规划软件求解；
Step 5,检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转 Step 1 或
Step2 修改模型。
规划与决策案例 2,（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。
甲、乙两种产品的铸造可以外协加工，
亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：
规划与决策工时与成本 甲 乙 丙 总工时每件铸造工时（小时） 5 10 7 8000
每件机加工工时（小时） 6 4 8 12000
每件装配工时（小时） 3 2 2 10000
自产铸件每件成本（元） 3 5 4
外协铸件每件成本（元） 5 6 -
机加工每件成本（元） 2 1 3
装配每件成本（元） 3 2 2
每件产品售价（元） 23 18 16
问题：如何安排生产计划,使公司获利最大？
规划与决策分析,设 xi — 公司加工 甲,乙,丙三种产品数量,
i=1,2,3。 x4,x5— 由外协铸造后再由本公司 机加工和装配的甲,乙两种产品数量；
目标函数：
每件产品利润分别是：
每件 x1产品利润,23-（ 3+2+3） =15元每件 x2产品利润,18-（ 5+1+2） =10元每件 x3产品利润,16-（ 4+3+2） =7元每件 x4产品利润,23-（ 5+2+3） =13元每件 x5产品利润,18-（ 6+1+2） =9元目标函数为,max 15 x1+10 x2+7 x3+13 x4+9 x5
规划与决策约束条件：
5 x1+10 x2+7 x3 ≤ 8000
6 x1+4 x2+8 x3+6 x4+4 x5 ≤ 12000
3 x1+2 x2+2 x3+3 x4+2 x5 ≤ 10000
xi ≥ 0 i=1,…,5
规划与决策图解法,
Step 1,确定可行域 D = {x | x 满足上述约束条件 }如下图 2-1：
Step 2,确定直线 50x1+100x2=0如下图 2-2：
Step 3,向上移动直线 50x1+100x2=0如图 2-2，
z=50x1+100x2 的值不断地增加,达到 B点时,达到最大；
Step 4,最优解为 B=(50,250),z最大 =27500。
规划与决策
0 100 200 300
300
200
100 D
图 2-1
规划与决策
0 100 200 300
300
200
100 D
B(50,250)
Z= 50x1+100x2 图 2-2
时序与路径规划
讨论各种时序规划问题
介绍时序规划原则
分派问题
运输问题
网络的最短路径
网络的最大流时序规划问题
A
B
E
F
D
C
机器机器D EF C A B
等待处理的一批工作按最优次序排队一台机器工作的时序规划时序规划问题原则：
(1) 最紧迫的优先实例 1：
6种部件作为一批等待一台机器加工。每一部件的平均周需求量、
当前的存货水平以及加工一批所需时间如下表，你将如何安排各种部件的生产次序？
部 件 A B C D E F
平均需求量 10 4 26 34 7 3
当前存货量 72 21 48 92 28 23
加工时间 2.0 1.5 0.5 0.5 1.0 1.5
时序规划问题
1 3è μ? óè
2
3 êy?Y
4 A B C D E F
5 μ±? °′ 72 21 48 92 28 23
6 Dè?ó 10 4 26 34 7 3
7 ′ ó? íê μ? ê± 7,20 5,25 1,85 2,71 4,00 7,67
8
9?- àí μ? êy?Y
10 ′ ó? íê μ? ê± 1,85 2,71 4,00 5,25 7,20 7,67
11 C D E B A F
12 μ±? °′ 48 92 28 21 72 23
13 Dè?ó 26 34 7 4 10 3
14
15 é? 2? ê± 0,5 0,5 1,0 1,5 2,0 1,5
16?a ê? é? 2? ê± 0,0 0,5 1,0 2,0 3,5 5,5
17 íê 3é é? 2? ê± 0,5 1,0 2,0 3,5 5,5 7,0
18 èY ó′ ê± 1,4 1,7 2,0 1,8 1,7 0,7
时序规划问题
2
3 êy?Y
4 A B C D E F
5 μ±? °′ 72 21 48 92 28 23
6 Dè?ó 10 4 26 34 7 3
7 ′ ó? íê μ? ê± 7,20 5,25 1,85 2,71 4,00 7,67
8
9?- àí μ? êy?Y
10 ′ ó? íê μ? ê± 1,85 2,71 4,00 5,25 7,20 7,67
11 C D E B A F
12 μ±? °′ 48 92 28 21 72 23
13 Dè?ó 26 34 7 4 10 3
14
15 é? 2? ê± 0,5 0,5 1,0 1,5 2,0 1,5
16?a ê? é? 2? ê± 0,0 0,5 1,0 2,0 3,5 5,5
17 íê 3é é? 2? ê± 0,5 1,0 2,0 3,5 5,5 7,0
18 èY ó′ ê± 1,35 1,71 2 1,75 1,7 0,67
时序规划问题
A B C D E F G H I
1?ó 1¤ê± 3ì óè
2
3 êy?Y
4 1¤3? A B C D E F G H
5?ó 1¤ê± 2 5 3 8 4 7 2 3
6
7 àí oó êy?Y
8 1¤3? A G C H E B F D
9?ó 1¤ê± 2 2 3 3 4 5 7 8
10
11?a êó 1¤ê± 0,0 2,0 4,0 7,0 10,0 14,0 19,0 26,0
12 íê 3é?ó 1¤ê± 2,0 4,0 7,0 10,0 14,0 19,0 26,0 34,0
以“加工时间最短者优先”为原则时序规划问题
2
3 êy?Y
4 1¤3? A B C D E F G H
5?ó 1¤ê± 2 5 3 8 4 7 2 3
6
7 àí oó êy?Y
8 1¤3? A G C H E B F D
9?ó 1¤ê± 2 2 3 3 4 5 7 8
10
11?a êó 1¤ê± 0,0 2,0 4,0 7,0 10,0 14,0 19,0 26,0
12 íê 3é?ó 1¤ê± 2,0 4,0 7,0 10,0 14,0 19,0 26,0 34,0
以“加工时间最短者优先”为原则时序规划问题
(3) 到期日最近者原则
B C D E F G H I
A B C D E F G H
13 7 8 30 14 20 2 36
G B C A E F D H
2 7 8 13 14 20 30 36
2 5 3 2 4 7 8 3
0,0 2,0 7,0 10,0 12,0 16,0 23,0 31,0
2,0 7,0 10,0 12,0 16,0 23,0 31,0 34,0
0,0 0,0 2,0 0,0 2,0 3,0 1,0 0,0
时序规划问题
(3) 到期日最近者原则
B C D E F G H I
A B C D E F G H
13 7 8 30 14 20 2 36
G B C A E F D H
2 7 8 13 14 20 30 36
2 5 3 2 4 7 8 3
0,0 2,0 7,0 10,0 12,0 16,0 23,0 31,0
2,0 7,0 10,0 12,0 16,0 23,0 31,0 34,0
0,0 0,0 2,0 0,0 2,0 3,0 1,0 0,0
时序规划问题
(4) 延误的工作项目最少第 1步,运用先到期者优先的原则排出工作的初始次序。如果已经没有工作被延误，这便是最优解，否则，则进行第 2步。
第 2步,在安排的时序中找到 1项延误的工作。
第 3步,找出第 2步所找工作之前（包括这一工作本身）加工时间最长的工作。
第 4步,将这一工作从时序安排中抽出来，并更新相应的时间。如果仍然有被延误的工作，再转向第 2步，否则转向第 5步。
第 5步,将第 4步抽出的工作放到时序的末尾。
实例 3,沿用上述实例的 8项工作，求解工作延误项数最少的时序。
为此我们采用上述五个步骤。
工 作 A B C D E F G H
加工时间 2 5 3 8 4 7 2 3
到期时间 13 7 8 30 14 20 2 36
时序规划问题第 1步,将工作按到期时间排序。
工 作 G B C A E F D H
到期时间 2 7 8 13 14 20 30 36
开始加工时间 0 2 7 10 12 16 23 31
加工时间 2 5 3 2 4 7 8 3
完成加工时间 2 7 10 12 16 23 31 34
延误工作 * * * *
第 2步,在上述时序中，第 1项被延误的工作是 C。
第 3步,到 C之前，包括 C在内，加工时间最长的工作是 B，加工时间为 5。
时序规划问题第 4步,抽出工作 B，更新相关的时间：
工 作 G C A E F D H
到期时间 2 8 13 14 20 30 36
开始加工时间 0 2 5 7 11 18 26
加工时间 2 3 2 4 7 8 3
完成加工时间 2 5 7 11 18 26 29
第 5步,现在已经没有工作被延误了，所以我们将工作 B加到时序的最后。
工 作 G C A E F D H B
到期时间 2 8 13 14 20 30 36 7
开始加工时间 0 2 5 7 11 18 26 29
加工时间 2 3 2 4 7 8 3 5
完成加工时间 2 5 7 11 18 26 29 34
现在只有一项工作被延误，平均排队时间为 98/8=12.25，平均延误时间为
27/8=3.375天。
时序规划问题
(5) Johnson’s rule(约翰逊原则 )
步骤 1,列出各项工作及它们在每台机器上的加工时间。
步骤 2,找出下一个在各台机器上加工时间最短的工作。
步骤 3,如果这是在机器 1上，尽量将这一工作安排在前面；如果这是在机器 2上，尽量将这一工作安排在后面。在重复做这些的时候，总是从时序的两端向内进行，新安排的工作离时序的中间更近。
步骤 4,不必再考虑这一工作，回到步骤 2。如果再找不到这样的任务，这就是最优解。
实例 4：
有 7项工作要顺序经过机器 1和机器 2加工。每项工作在每台机器上所需的加工时间如下，如何安排时序才能使机器利用率最高。
工作 A B C D E F G
机器 1 2 5 10 8 4 12 9
时序规划问题
A B C D E F G H
1 o2?2?-?ò
2
3 1¤3? A B C D E F G
4?ú 1 é? μ? ê± 2 5 10 7 4 12 9
5?ú 2 é? μ? ê± 14 7 3 10 5 6 6
6
7 3? ó? ê±D ò A E B D G F C
8?ú 1 éa ê? μ? ê± 0 2 6 11 19 28 40
9?ú 1 é? íê 3é μ? ê± 2 6 11 19 28 40 50
10?ú 2 éa ê? μ? ê± 2 16 21 28 38 44 50
11?ú 2 é? íê 3é μ? ê± 16 21 28 38 44 50 53
时序规划问题
2
3 1¤3? A B C D E F G
4?ú 1 é? μ? ê± 2 5 10 7 4 12 9
5?ú 2 é? μ? ê± 14 7 3 10 5 6 6
6
7 3? ó? ê±D ò A E B D G F C
8?ú 1 éa ê? μ? ê± 0 2 6 11 19 28 40
9?ú 1 é? íê 3é μ? ê± 2 6 11 19 28 40 50
10?ú 2 éa ê? μ? ê± 2 16 21 28 38 44 50
11?ú 2 é? íê 3é μ? ê± 16 21 28 38 44 50 53
分派问题如何以总成本最低为目标将操作员分派到各台机器上。
原则,每个操作员只能分派给一项任务，每项任务只能由一人完成。
Cij 第 i个操作员完成第 j项任务的成本
Xij
min ΣΣCijXij
Σ Xij=1
Σ Xij=1
Xij=0,1 i=1,…,n,j=1,…,m
=1 (分派操作员 i完成任务 j)
=0 (不分派操作员 i完成任务 j)
j
i
最短路问题最短路问题
G(V,E) 为 连通图，边（ vi,vj)的权为 lij，求一条道路，使它从 vs到 vt的总权最少？
方法,1 动态规划法
2 Dijkstra算法引例：某一配送中心要给一个快餐店送快餐原料，应按什么路线送货才能使送货时间最短？
V2 16 v4 7 v6
4 6
V1 12 2 8 v7
18 5
V3 6 v5
（配送中心） （快餐店）
最大流问题最大流问题引例,某石油公司拥有一个管道网络（如图），使用这个网络可以把石油从采地运送到一些销售地。弧上的数字为该管道的容量,问如果使用这个网络系统从
v1向销地 v7运送石油,每小时能运送多少石油？
v1
V2 ( 3,0) v5
(6,0) (2,0) (2,0) (5,0)
v3 V6 v7
(6,0) (3,0) (1,0) (2,0)
v4
(2,0) (4,0)
