资源预览内容
第1页 / 共36页
第2页 / 共36页
第3页 / 共36页
第4页 / 共36页
第5页 / 共36页
第6页 / 共36页
第7页 / 共36页
第8页 / 共36页
第9页 / 共36页
第10页 / 共36页
亲,该文档总共36页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第六章 模型决策法,线性规划等 时序与路径规划 分派问题 最短路问题 最大流问题,模型决策法,优化模型 max (min) 目标函数 s. t. 约束条件,线性规划模型的建立,实例 1 两种产品的生产。已知生产单位产品所需的设备台时及A、B两种原材料的消耗,资源限制及市场价格如下表: 资源限制 设备11300台时 原材料A21400千克 原材料B01250千克 市场价格50100 问题:如何安排生产,才能使工厂获利最多?,规划与决策,分析: (1)设 x1 生产产品的数量; x2 生产产品的数量。 (2)目标函数:MAX 50 x1+100 x2 (3)约束条件:subject to (s.t.): x1+x2 300 2x1+x2 400 x2 250 x1,x2 0,规划与决策,线性规划模型: max 50 x1+100 x2 s.t. x1+x2 300 2x1+x2 400 x2 250 x1,x2 0,规划与决策,线性规划模型的一般形式 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 1. 理解及分析实际问题,资源状况,解决问题实现的目标; Step 2. 确定决策变量(x1, ,xn) 解决问题的具体方案(量化方案); Step 3. 确定目标函数及约束条件; Step 4. 应用线性规划软件求解; Step 5. 检验所求得的解决方案是否可行:如可行,则开始具体实施;否则,转Step 1 或 Step2 修改模型。,规划与决策,案例2:(生产计划问题)某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品,这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工,亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表:,规划与决策,工时与成本甲乙丙总工时 每件铸造工时(小时)51078000 每件机加工工时(小时)64812000 每件装配工时(小时)32210000 自产铸件每件成本(元)354 外协铸件每件成本(元)56- 机加工每件成本(元)213 装配每件成本(元)322 每件产品售价(元)231816 问题:如何安排生产计划,使公司获利最大?,规划与决策,分析:设 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. 确定直线 50 x1+100 x2=0如下图2-2: Step 3. 向上移动直线 50 x1+100 x2=0如图2-2,z=50 x1+100 x2 的值不断地增加,达到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= 50 x1+100 x2,图 2-2,时序与路径规划,讨论各种时序规划问题 介绍时序规划原则 分派问题 运输问题 网络的最短路径 网络的最大流,时序规划问题,A,B,E,F,D,C,机器,机器,D,E,F,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,时序规划问题,时序规划问题,时序规划问题,以“加工时间最短者优先”为原则,时序规划问题,以“加工时间最短者优先”为原则,时序规划问题,(3) 到期日最近者原则,时序规划问题,(3) 到期日最近者原则,时序规划问题,(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) Johnsons 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,时序规划问题,时序规划问题,分派问题,如何以总成本最低为目标将操作员分派到各台机器上。 原则:每个操作员只能分派给一项任务,每项任务只能由一人完成。 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),演讲完毕,谢谢观看!,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号