模型决策法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 模型决策法,线性规划等,时序与路径规划,分派问题,最短路问题,最大流问题,模型决策法,优化模型,max(min),目标函数,s.t.,约束条件,线性规划模型的建立,实例,1,两种产品的生产。已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗，资源限制及市场价格如下表：,资源限制,设备,11300,台时,原材料,A21400,千克,原材料,B01250,千克,市场价格,50100,问题：如何安排生产，才能使工厂获利最多？,规划与决策,分析：,（,1,）设,x,1,生产产品,的数量；,x,2,生产产品,的数量。,（,2,）目标函数：,MAX 50 x,1,+100 x,2,（,3,）,约束条件：,subject to(s.t.):,x,1,+x,2,300,2x,1,+x,2,400,x,2,250,x,1,x,2,0,规划与决策,线性规划模型：,max 50 x,1,+100 x,2,s.t.x,1,+x,2,300,2x,1,+x,2,400,x,2,250,x,1,x,2,0,规划与决策,线性规划模型的一般形式,max c,1,x,1,+c,2,x,2,+,c,n,x,n,s.t.a,11,x,1,+a,1n,x,n,(,=)b,1,a,21,x,1,+a,2n,x,n,(,=)b,2,a,m1,x,1,+,a,mn,x,n,(,=),b,m,x,ij,0,i=,1,n,j=1,m,规划与决策,线性规划应用领域,：,合理利用板、线材问题；,配料问题；,投资问题；,生产计划问题、劳动力安排问题；,运输问题、电子商务配送问题；,企业决策问题；企业或商业竞争对策问题等。,规划与决策,一,般线性规划建模过程,Step 1.,理解及分析实际问题，资源状况，解决问题实现的目标；,Step 2.,确定决策变量（,x,1,，,x,n,）,解决问题的具体方案（量化方案）；,Step 3.,确定目标函数及约束条件；,Step 4.,应用线性规划软件求解；,Step 5.,检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转,Step 1,或,Step2,修改模型。,规划与决策,案例,2,：,（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工，亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：,规划与决策,工时与成本甲乙丙总工时,每件铸造工时（小时）,51078000,每件机加工工时（小时）,64812000,每件装配工时（小时）,32210000,自产铸件每件成本（元）,354,外协铸件每件成本（元）,56-,机加工每件成本（元）,213,装配每件成本（元）,322,每件产品售价（元）,231816,问题：如何安排生产计划，使公司获利最大？,规划与决策,分析：,设,x,i,公司加工,甲、乙、丙三种产品数量，,i=1,2,3,。,x,4,、,x,5,由外协铸造后再由本公司,机加工和装配的甲、乙两种产品数量；,目标函数：,每件产品利润分别是：,每件,x,1,产品利润,:23-,（,3+2+3,）,=15,元,每件,x,2,产品利润,:18-,（,5+1+2,）,=10,元,每件,x,3,产品利润,:16-,（,4+3+2,）,=7,元,每件,x,4,产品利润,:23-,（,5+2+3,）,=13,元,每件,x,5,产品利润,:18-,（,6+1+2,）,=9,元,目标函数为：,max 15 x,1,+10 x,2,+7 x,3,+13 x,4,+9 x,5,规划与决策,约束条件：,5,x,1,+10 x,2,+7 x,3,8000,6 x,1,+4 x,2,+8 x,3,+6 x,4,+4 x,5,12000,3 x,1,+2 x,2,+2 x,3,+3 x,4,+2 x,5,10000,x,i,0 i=1,5,规划与决策,图解法,:,Step 1.,确定可行域,D=,x|x,满足上述约束条件,如下图,2-1,：,Step 2.,确定直线,50,x,1,+100 x,2,=0,如下图,2-2,：,Step 3.,向上移动直线,50,x,1,+100 x,2,=0,如图,2-2,，,z,=,50 x,1,+100 x,2,的值不断地增加，达到,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 x,1,+100 x,2,图,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,时序规划问题,时序规划问题,分派问题,如何以总成本最低为目标将操作员分派到各台机器上。,原则：,每个操作员只能分派给一项任务，每项任务只能由一人完成。,C,ij,第,i,个操作员完成第,j,项任务的成本,X,ij,min,C,ij,X,ij,X,ij,=1,X,ij,=1,X,ij,=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),