北大光华-规划与决策(2)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 模型决策法,线性规划等,时序与路径规划,分派问题,最短路问题,最大流问题,模,型,型,决,决,策,策,法,法,优,化,化,模,模,型,型,max(min),目,目,标,标,函,函,数,数,s.t.,约,约,束,束,条,条,件,件,线,性,性,规,规,划,划,模,模,型,型,的,的,建,建,立,立,实,例,例1,两,种,种,产,产,品,品,的,的,生,生,产,产,。,。,已,已,知,知,生,生,产,产,单,单,位,位,产,产,品,品,所,所,需,需,的,的,设,设,备,备,台,台,时,时,及,及A,、,、B,两,两,种,种,原,原,材,材,料,料,的,的,消,消,耗,耗,，,，,资,资,源,源,限,限,制,制,及,及,市,市,场,场,价,价,格,格,如,如,下,下,表,表,：,：,资,资,源,源,限,限,制,制,设,备,备11300,台,台,时,时,原,材,材,料,料A21400,千,千,克,克,原,材,材,料,料B01250,千,千,克,克,市,场,场,价,价,格,格50100,问,题,题,：,：,如,如,何,何,安,安,排,排,生,生,产,产,，,，,才,才,能,能,使,使,工,工,厂,厂,获,获,利,利,最,最,多,多,？,？,规,划,划,与,与,决,决,策,策,分,析,析,：,：,（1,）,）,设,设x,1,生,生,产,产,产,产,品,品,的,的,数,数,量,量,；,；,x,2,生,生,产,产,产,产,品,品,的,的,数,数,量,量,。,。,（2,）,）,目,目,标,标,函,函,数,数,：,：MAX50 x,1,+100 x,2,（3,）,）,约,约,束,束,条,条,件,件,：,：subjectto(s.t.):,x,1,+x,2,300,2x,1,+x,2,400,x,2,250,x,1,x,2,0,规,划,划,与,与,决,决,策,策,线,性,性,规,规,划,划,模,模,型,型,：,：,max50 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,规,划,划,与,与,决,决,策,策,线,性,性,规,规,划,划,模,模,型,型,的,的,一,一,般,般,形,形,式,式,maxc,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,规,划,划,与,与,决,决,策,策,线,性,性,规,规,划,划,应,应,用,用,领,领,域,域：,合,理,理,利,利,用,用,板,板,、,、,线,线,材,材,问,问,题,题,；,；,配,料,料,问,问,题,题,；,；,投,资,资,问,问,题,题,；,；,生,产,产,计,计,划,划,问,问,题,题,、,、,劳,劳,动,动,力,力,安,安,排,排,问,问,题,题,；,；,运,输,输,问,问,题,题,、,、,电,电,子,子,商,商,务,务,配,配,送,送,问,问,题,题,；,；,企,业,业,决,决,策,策,问,问,题,题,；,；,企,企,业,业,或,或,商,商,业,业,竞,竞,争,争,对,对,策,策,问,问,题,题,等,等,。,。,规划与决,策,策,一,般线性规,划,划建模过,程,程,Step1.理解及分,析,析实际问,题,题，资源,状,状况，解,决,决问题实,现,现的目标,；,；,Step2.确定决策变量,（,（x,1,，x,n,）,解决问题,的,的具体方案（,量,量化方案）；,Step 3.确定目标函数,及,及约束条件；,Step 4.应用线性规划,软,软件求解；,Step 5.检验所求得的,解,解决方案是否,可,可行：如可行,，,，则开始具体,实,实施；否则，,转,转Step1 或 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,0i=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,。,。,规划与决策,0100200300,300,200,100,D,图 2-1,规划与决策,0100200300,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种部件作为,一,一批等待一台,机,机器加工。每,一,一部件的平均,周,周需求量、当,前,前的存货水平,以,以及加工一批,所,所需时间如下,表,表，你将如何,安,安排各种部件,的,的生产次序？,部 件ABCDEF,平均需求量104263473,当前存货量722148922823,加工时间2.0 1.50.50.51.01.5,时序规划问题,时序规划问题,时序规划问题,以“加工时间,最,最短者优先”,为,为原则,时序规划问题,以“加工时间,最,最短者优先”,为,为原则,时序规划问题,(3)到期,日,日最近者原则,时序规划问题,(3)到期,日,日最近者原则,时序规划问题,(4)延误,的,的工作项目最,少,少,第1步：运用先到期者,优,优先的原则排,出,出工作的初始,次,次序。如果已,经,经没有工作被,延,延误，这便是,最,最优解，否则,，,，则进行第2,步,步。,第2步：在安排的时序,中,中找到1项延,误,误的工作。,第3步：找出第2步所,找,找工作之前（,包,包括这一工作,本,本身）加工时,间,间最长的工作,。,。,第4步：将这一工作从,时,时序安排中抽,出,出来，并更新,相,相应的时间。,如,如果仍然有被,延,延误的工作，,再,再转向第2步,，,，否则转向第5步。,第5步：将第4步抽,出,出的工作放,到,到时序的末,尾,尾。,实例 3：,沿用上述实,例,例的8项工,作,作，求解工,作,作延误项数,最,最少的时序,。,。,为此我们采,用,用上述五个,步,步骤。,工,作,作ABCDEFGH,加工时间25384723,到期时间1378301420236,时序规划问,题,题,第1步：将工作按到,期,期时间排序,。,。,工 作GBCAEFDH,到期时间2781314203036,开始加工时,间,间0271012162331,加工时间25324783,完成加工时,间,间27101216233134,延误工作*,第2步：在上述时序,中,中，第1项,被,被延误的工,作,作是C。,第3步：到C之前，,包,包括C在内,，,，加工时间,最,最长的工作,是,是B，加工,时,时间为5。,时序规划问,题,题,第4步：抽出工作B,，,，更新相关,的,的时间：,工,作,作GCAEFDH,到期时间281314203036,开始加工时,间,间0257111826,加工时间2324783,完成加工时,间,间25711182629,第5步：现在已经没,有,有工作被延,误,误了，所以,我,我们将工作B加到时序,的,的最后。,工,作,作GCAEFDHB,到期时间2813142030367,开始加工时,间,间025711182629,加工时间23247835,完成加工时,间,间2571118262934,现在只有一,项,项工作被延,误,误，平均排,队,队时间为98/8=12.25，,平,平均延误时,间,间为27/8=3.375天。,时序规划问,题,题,(5)Johnsons rule(约,翰,翰逊原则),步骤1：列出各项工,作,作及它们在,每,每台机器上,的,的加工时间,。,。,步骤2：找出下一个,在,在各台机器,上,上加工时间,最,最短的工作,。,。,步骤3：如果这是在,机,机器1上，,尽,尽量将这一,工,工作安排在,前,前面；如果,这,这是在机器2上，尽量,将,将这一工作,安,安排在后面,。,。在重复做,这,这些的时候,，,，总是从时,序,序的两端向,内,内进行，新,安,安排的工作,离,离时序的中,间,间更近。,步骤4：不必再考虑,这,这一工作，,回,回到步骤2,。,。如果再找,不,不到这样的,任,任务，这就,是,是最优解。,实例 4：,有7项工作,要,要顺序经过,机,机器1和机,器,器2加工。,每,每项工作在,每,每台机器上,所,所需的加工,时,时间如下，,如,如何安排时,序,序才能使机,器,器利用率最,高,高。,工作ABCDEFG,机器1251084129,机器2147310566,时序规划问,题,题,时序规划问,题,题,分派问题,如何以总成,本,本最低为目,标,标将操作员,分,分派到各台,机,机器上。,原则：,每个操作员,只,只能分派给,一,一项任务，,每,每项任务只,能,能由一人完,成,成。,C,ij,第i个操作,员,员完成第j,项,项任务的成,本,本,X,ij,min,C,ij,X,ij,X,ij,=1,X,ij,=1,X,ij,=0,1i=1,n,j=1,m,=1(分派操作,员,员i完成任,务,务j),=0(,不分派操作,员,员i完成任,务,务j),j,i,最短路问题,最短路问题,G(V,E)为 连,通,通图，边（vi,vj)的权为lij，求一,条,条道路，使,它,它从vs到vt的总权,最,最少？,方法：1,动,动态规划法,2 Dijkstra,