部件
ABC DE 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 最紧迫的优先2 Nhomakorabea3 数据
4 项目
A
5 当前存货
72
6 平均需求
10
7 存货用完的时间 7,20
8
9 经整理的数据
时序与路径规划
❖ 讨论各种时序规划问题 ❖ 介绍时序规划原则 ❖ 分派问题 ❖ 运输问题 ❖ 网络的最短路径 ❖ 网络的最大流
时序规划问题
F
C
A
B D
E
等待处理的一批工作 D F CEA B 按最优次序排队
机器 机器
一台机器工作的时序规划
时序规划问题
原则：
(1) 最紧迫的优先
实例 1：
6种部件作为一批等待一台机器加工。每一部件的平均周需求量、 当前的存货水平以及加工一批所需时间如下表，你将如何安排各 种部件的生产次序？
优化模型
模型决策法
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
规划与决策
分析：设 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
z=50x1+100x2 的值不断地增加，达到B点时， 达到最大； Step 4. 最优解为B=(50,250), z最大=27500。
规划与决策
300
200
D
100
0
100
200
300
图 2-1
规划与决策
300
200
D
100
B(50,250)
0
100
200
300
Z= 50x1+100x2
图 2-2
10 存货用完的时间 1,85
11 项目
C
12 当前存货
48
13 平均需求
26
14
15 生产时间
0,5
16 开始生产时间
0,0
17 完成生产时间
0,5
18 容余时.间 （.. .. .） 1,4
B 21 4 5,25
2,71 D 92 34
0,5 0,5 1,0 1,7
C 48 26 1,85
4,00 E 28 7
1,0 1,0 2,0 2,0
D 92 34 2,71
5,25 B 21 4
1,5 2,0 3,5 1,8
E 28 7 4,00
7,20 A 72 10
2,0 3,5 5,5 1,7
F 23 3 7,67
7,67 F 23 3
1,5 5,5 7,0 0,7
时序规划问题
2
3 数据
4 项目
A
B
C
D
E
5 当前存货
72
21
48
92
28
6 平均需求
10
4
案例2：（生产计划问题）某公司面临一个外协 加工还是自行生产问题。该公司生产甲、乙、 丙三种产品，这三种产品都需要经过铸造、 机加工和装配三个车间。甲、乙两种产品的 铸造可以外协加工，亦可以自行生产。但丙 产品的铸造必须自行生产才能保证质量。有 关数据见下表：
规划与决策
工时与成本 甲 乙 丙 总工时
规划与决策
线性规划模型的一般形式
max c1x1+c2x2+ …+ cn xn s. t. a11x1 + …+ a1nx n≤ (≥,=) b1
a21x1 + …+ a2nx n≤ (≥,=) b2 …
am1x1 + …+ amnx n≤ (≥,=) bm xij ≥ 0 i = 1, …,n, j =1, …,m
Step 2. 确定决策变量（x1, …，xn）— 解决问题的 具体方案（量化方案）；
Step 3. 确定目标函数及约束条件； Step 4. 应用线性规划软件求解； Step 5. 检验所求得的解决方案是否可行：如可行，
则开始具体实施；否则，转Step 1 或 Step2 修改 模型。
规划与决策
每件铸造工时（小时） 5 10 7 8000
每件机加工工时（小时） 6 4 8 12000
每件装配工时（小时） 3 2 2 10000
自产铸件每件成本（元） 3 5 4
外协铸件每件成本（元） 5 6 -
机加工每件成本（元） 2 1 3
装配每件成本（元）
322
每件产品售价（元）
23 18 16
问题：如何安排生产计划，使公司获利最大？
规划与决策
约束条件：
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，
规划与决策
线性规划应用领域：
† 合理利用板、线材问题； † 配料问题； † 投资问题； † 生产计划问题、劳动力安排问题； † 运输问题、电子商务配送问题； † 企业决策问题；企业或商业竞争对策问题等。
规划与决策
一般线性规划建模过程
Step 1. 理解及分析实际问题，资源状况，解决问题 实现的目标；