第2步：在安排的时序中找到1项延误的工作。 第3步：找出第2步所找工作之前（包括这一工作本身）加工时间最长的工作
。 第4步：将这一工作从时序安排中抽出来，并更新相应的时间。如果仍然有被
延误的工作，再转向第2步，否则转向第5步。 第5步：将第4步抽出的工作放到时序的末尾。
规划与决策
线性规划模型的一般形式 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
每件产品售价（元）
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. 确定目标函数及约束条件； Step 4. 应用线性规划软件求解； Step 5. 检验所求得的解决方案是否可行：如可
行，则开始具体实施；否则，转Step 1 或 Step2 修改模型。
规划与决策
案例2：（生产计划问题）某公司面临一个 外协加工还是自行生产问题。该公司生 产甲、乙、丙三种产品，这三种产品都 需要经过铸造、机加工和装配三个车间 。甲、乙两种产品的铸造可以外协加工 ，亦可以自行生产。但丙产品的铸造必 须自行生产才能保证质量。有关数据见 下表：
•机器 •机器
•一台机器工作的时序规划
时序规划问题
原则： (1) 最紧迫的优先 实例 1：
6种部件作为一批等待一台机器加工。每一部件的平均周需求量、 当前的存货水平以及加工一批所需时间如下表，你将如何安排各 种部件的生产次序？
部件 A B C D E F 平均需求量 10 4 26 34 7 3 当前存货量 72 21 48 92 28 23
规划与决策
分析： （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
规划与决策
工时与成本 甲 乙 丙 总工时
每件铸造工时（小时） 5 10 7 8000
每件机加工工时（小时） 6 4 8 12000
每件装配工时（小时） 3 2 2 10000
自产铸件每件成本（元） 3 5 4
外协铸件每件成本（元） 5 6 -
机加工每件成本（元） 2 1 3
装配每件成本（元）
322
•200
•D
•100
•B(50,250)
•0
100
200
300
•Z= 50x1+100x2 •图 2-2
时序与路径规划
• 讨论各种时序规划问题 • 介绍时序规划原则 • 分派问题 • 运输问题 • 网络的最短路径 • C
•A
•D
•B
•E
•等待处理的一批工作 •D •F •C •E •A •B •按最优次序排队
加工时间 2.0 1.5 0.5 0.5 1.0 1.5
时序规划问题
时序规划问题
时序规划问题
•以“加工时间最短者优先”为原则
时序规划问题
•以“加工时间最短者优先”为原则
时序规划问题
(3) 到期日最近者原则
时序规划问题
(3) 到期日最近者原则
时序规划问题
(4) 延误的工作项目最少
第1步：运用先到期者优先的原则排出工作的初始次序。如果已经没有工作被 延误，这便是最优解，否则，则进行第2步。
第六章 模型决策法
• 线性规划等 • 时序与路径规划 • 分派问题 • 最短路问题 • 最大流问题
模型决策法
优化模型
max (min) 目标函数 s. t. 约束条件
线性规划模型的建立
实例 1
两种产品的生产。已知生产单位产品所需的设备台时 及A、B两种原材料的消耗，资源限制及市场价格如下 表：
Ⅰ Ⅱ 资源限制 设备 1 1 300台时 原材料A 2 1 400千克 原材料B 0 1 250千克 市场价格 50 100 • 问题：如何安排生产，才能使工厂获利最多？
： Step 3. 向上移动直线 50x1+100x2=0如图2-2
，z=50x1+100x2 的值不断地增加，达到B 点时， 达到最大； Step 4. 最优解为B=(50,250), z =27500。
规划与决策
•300
•200
•D
•100
•0
100
200
300
•图 2-1
规划与决策
•300
规划与决策
线性规划应用领域： • 合理利用板、线材问题； • 配料问题； • 投资问题； • 生产计划问题、劳动力安排问题； • 运输问题、电子商务配送问题； • 企业决策问题；企业或商业竞争对 策问题等。
规划与决策
一般线性规划建模过程 Step 1. 理解及分析实际问题，资源状况，解决
问题实现的目标； Step 2. 确定决策变量（x1, …，xn）— 解决问