- 1. 第六章 模型决策法线性规划等
时序与路径规划
分派问题
最短路问题
最大流问题
- 2. 模型决策法优化模型
max (min) 目标函数
s. t. 约束条件
- 3. 线性规划模型的建立实例 1
两种产品的生产。已知生产单位产品所需的设备台时及A、B两种原材料的消耗,资源限制及市场价格如下表:
Ⅰ Ⅱ 资源限制
设备 1 1 300台时
原材料A 2 1 400千克
原材料B 0 1 250千克
市场价格 50 100
问题:如何安排生产,才能使工厂获利最多?
- 4. 规划与决策分析:
(1)设 x1 — 生产产品Ⅰ的数量;
x2 — 生产产品Ⅱ的数量。
(2)目标函数:MAX 50x1+100x2
(3)约束条件:subject to (s.t.):
x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
- 5. 规划与决策线性规划模型:
max 50x1+100x2
s.t. x1+x2 ≤300
2x1+x2 ≤400
x2 ≤250
x1,x2 ≥0
- 6. 规划与决策线性规划模型的一般形式
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
- 7. 规划与决策线性规划应用领域:
合理利用板、线材问题;
配料问题;
投资问题;
生产计划问题、劳动力安排问题;
运输问题、电子商务配送问题;
企业决策问题;企业或商业竞争对策问题等。
- 8. 规划与决策一般线性规划建模过程
Step 1. 理解及分析实际问题,资源状况,解决问题实现的目标;
Step 2. 确定决策变量(x1, …,xn)— 解决问题的具体方案(量化方案);
Step 3. 确定目标函数及约束条件;
Step 4. 应用线性规划软件求解;
Step 5. 检验所求得的解决方案是否可行:如可行,则开始具体实施;否则,转Step 1 或 Step2 修改模型。
- 9. 规划与决策案例2:(生产计划问题)某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品,这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工,亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表:
- 10. 规划与决策工时与成本 甲 乙 丙 总工时
每件铸造工时(小时) 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
问题:如何安排生产计划,使公司获利最大?
- 11. 规划与决策分析:设 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
- 12. 规划与决策约束条件:
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
- 13. 规划与决策图解法:
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。
- 14. 规划与决策0 100 200 300300200100D图 2-1
- 15. 规划与决策0 100 200 300300200100DB(50,250)Z= 50x1+100x2图 2-2
- 16. 时序与路径规划讨论各种时序规划问题
介绍时序规划原则
分派问题
运输问题
网络的最短路径
网络的最大流
- 17. 时序规划问题ABEFDC机器机器DEFCAB等待处理的一批工作按最优次序排队一台机器工作的时序规划
- 18. 时序规划问题原则:
(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
- 19. 时序规划问题
- 20. 时序规划问题
- 21. 时序规划问题以“加工时间最短者优先”为原则
- 22. 时序规划问题以“加工时间最短者优先”为原则
- 23. 时序规划问题(3) 到期日最近者原则
- 24. 时序规划问题(3) 到期日最近者原则
- 25. 时序规划问题(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
- 26. 时序规划问题第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。
- 27. 时序规划问题第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天。
- 28. 时序规划问题(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
机器2 14 7 3 10 5 6 6
- 29. 时序规划问题
- 30. 时序规划问题
- 31. 分派问题如何以总成本最低为目标将操作员分派到各台机器上。
原则:每个操作员只能分派给一项任务,每项任务只能由一人完成。
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)ji
- 32. 最短路问题最短路问题
G(V,E) 为 连通图,边(vi,vj)的权为lij,求一条道路,使它从vs到vt的总权最少?
方法:1 动态规划法
2 Dijkstra算法
引例:某一配送中心要给一个快餐店送快餐原料,应按什么路线送货才能使送货时间最短?
- 33. V2 16 v4 7 v64 6V1 12 2 8 v718 5V3 6 v5(配送中心)(快餐店)
- 34. 最大流问题最大流问题
引例:某石油公司拥有一个管道网络(如图),使用这个网络可以把石油从采地运送到一些销售地。弧上的数字为该管道的容量, 问如果使用这个网络系统从v1向销地v7运送石油, 每小时能运送多少石油?
- 35. v1V2 ( 3,0) v5(6,0) (2,0) (2,0) (5,0)v3V6 v7(6,0) (3,0) (1,0) (2,0)v4(2,0) (4,0)