第十四章运筹学中的启发式方法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十四章运筹学中的启发式方法,Operational Research,( OR ),第十四章运筹学中的启发式方法Operational R,1,运筹学中的启发式方法,启发式方法的概念,应用问题举例,运筹学中的启发式方法启发式方法的概念,启发式方法的概念,一、 启发式方法的提出,良性结构的问题：问题的结构比较清晰，所含各元素之间的关系明确，边界清楚，容易为人们所认识，能够比较方便地通过建模和使用一定的算法求得解决。,概括地说良性结构问题具有以下特征：,(1),能建立起反映该问题性质的一种“可接受”模型，与问题有关的主要信息可纳入模型之中。,(2),模型所需要的数据能够得到。,(3),有判定解的可行性和最优性,(,或满意性,),的明确准则。,(4),模型可解，能拟定出求解模型的程序性步骤，而且得出的解能反映解决问题的可行方案。,(5),求解工作所需的计算量不过大，所需费用不过多。,启发式方法的概念一、 启发式方法的提出良性结构的问题：问题的,启发式方法的提出,在解决非良性结构的问题时，保持问题的本来面目，建立基本符合问题实际情况的非标准模型。由于模型涉及因素多，结构复杂，而与传统的标准模型相去甚远，难以套用已有的标准算法，为得到可用的近似解，分析人员必须运用自己的感知和洞察力，从与其有关而较基本的模型及算法中寻求其中的联系，从中得到启发，去发现和构想可用于解决该问题的思路和途径，人们称这种方法为启发式方法，用这种方法建立的算法为,启发式算法,。,启发式方法的提出 在解决非良性结构的问题时，,启发式方法的特点,启发式方法有下述优点：,计算步骤简单，易于实施。,(2),常不需要高深和复杂的理论知识，因而可由未,经高级训练的人员实现。,(3),与应用优化方法相比，常可以减少大量的计算,工作量，从而显著节约开支和节省时间。,(4),易于将定量分析与定性分析相结合。,启发式方法的特点启发式方法有下述优点：,启发式方法的策略,三、 启发式方法的策略,1.,逐步构解策略,2.,分解合成策略,3.,改进策略,4.,搜索学习策略,启发式方法的策略三、 启发式方法的策略1. 逐步构解策略2.,运筹学中的启发式方法,启发式方法的概念,应用问题举例,运筹学中的启发式方法启发式方法的概念,应用问题举例,一、 多个工件在设备上加工的排序问题,问题描述：,在,A,、,B,两台设备上顺序加工,n,个工件,(,工件,j=1,2,n),时，应如何排列这些工件的顺序，才能使总加工时间,(,从在,A,上开始加工第一个工件起到在,B,上加工完最后一个工件止,),尽可能短。此处要求每个工件都先在,A,上加工，然后再在,B,上加工。,应用问题举例一、 多个工件在设备上加工的排序问题问题描述：,例,1,下表中列出了,6,个工件分别在设备,A,和,B,上的加工时间,A,j,（,min,）和,B,j,(min),所有工件都先在,A,上加工，再在,B,上加工。要求确定使总加工时间最短的工件加工顺序。,应用问题举例,解,由于,B,1,=B,2,，,A,1,A,2,，故将工件,1,排在前面进行加工所需的总加工时间较少。现再看工件,2,和工件,3,，由于,A,2,=A,3,B,3,0(i,j=1,2,m),，计算,其中：,i=m+1,.,m+n,j=m+1,.,m+n,应用问题举例(1) 解的扩展其中：i=m+1,.,m+n,应用问题举例,算出的,ij,值为按下述方法调整,x,ij,(0),一个单位引起的空驶里程增加量。若,ij,来自,k,行和,l,列,(k,l,m+1,m+n,),则把,x,ij,(0),扩展至,x,kj,(0),和,x,il,(0),这时，将,x,ij,(0),、,x,kj,(0),和,x,il,(0),三个变量的值分别调整为：,解的这种扩展工作按,ij,的大小，由小到大依次进行，直至找出要求的可接受可行解。,应用问题举例算出的ij值为按下述方法调整xij (0) 一,应用问题举例,(2),解的收缩,本步骤是步骤,(1),的逆过程。,对每一对,x,kj,(1),0,和,x,il,(1),0(k,lm+1,m+n,；,i,j1,m),，计算,进行下述解的调整：,如上调整后得到的解记为,X,(2),=(x,ij,(2),),应用问题举例(2) 解的收缩进行下述解的调整：如上调整后得到,应用问题举例,4.,安排行车路线,经上述调整得到的解,X,(2),(,或,X,(1),，当不需进行解的收缩步骤时,),，可以它作为安排行车路线的依据。,安排行车路线时先在可接受可行解,X=(x,ij,),的非零分量中寻求下述序列：,依据解的序列式，可得到某条初始行车路线如下：,车场,车场,重载点,应用问题举例4. 安排行车路线经上述调整得到的解X(2)(或,