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

1、Operational Research( OR )|启发式方法的概念|应用问题举例一、一、 启发式方法的提出启发式方法的提出良性结构的问题：问题的结构比较清晰，所含各元素之间的关系明确，边界清楚，容易为人们所认识，能够比较方便地通过建模和使用一定的算法求得解决。概括地说良性结构问题具有以下特征：(1) 能建立起反映该问题性质的一种“可接受”模型，与问题有关的主要信息可纳入模型之中。(2) 模型所需要的数据能够得到。(3) 有判定解的可行性和最优性(或满意性)的明确准则。(4) 模型可解，能拟定出求解模型的程序性步骤，而且得出的解能反映解决问题的可行方案。(5) 求解工作所需的计算量不过大，所

2、需费用不过多。启启发发式式方方法法的的提提出出 在解决非良性结构的问题时，保持问题的本来面目，建立基本符合问题实际情况的非标准模型。由于模型涉及因素多，结构复杂，而与传统的标准模型相去甚远，难以套用已有的标准算法，为得到可用的近似解，分析人员必须运用自己的感知和洞察力，从与其有关而较基本的模型及算法中寻求其中的联系，从中得到启发，去发现和构想可用于解决该问题的思路和途径，人们称这种方法为启发式方法，用这种方法建立的算法为启发式算法启发式算法。启发式方法有下述优点：(1) 计算步骤简单，易于实施。(2) 常不需要高深和复杂的理论知识，因而可由未 经高级训练的人员实现。(3) 与应用优化方法相比，

3、常可以减少大量的计算 工作量，从而显著节约开支和节省时间。(4) 易于将定量分析与定性分析相结合。三、 启发式方法的策略1. 逐步构解策略2. 分解合成策略3. 改进策略4. 搜索学习策略|启发式方法的概念|应用问题举例一、一、 多个工件在设备上加工的排序问题多个工件在设备上加工的排序问题问题描述：在A、B两台设备上顺序加工n个工件(工件j=1,2,n)时，应如何排列这些工件的顺序，才能使总加工时间(从在A上开始加工第一个工件起到在B上加工完最后一个工件止)尽可能短。此处要求每个工件都先在A上加工，然后再在B上加工。例例1 下表中列出了6个工件分别在设备A和B上的加工时间Aj（min）和Bj(

4、min),所有工件都先在A上加工，再在B上加工。要求确定使总加工时间最短的工件加工顺序。解解 由于B1=B2，A1A2，故将工件1排在前面进行加工所需的总加工时间较少。现再看工件2和工件3，由于A2=A3,B30(i,j=1,2,m)，计算11min|0min|0ijijiijjijmi m nmj m ncbcbc 其中：(0)1(0)1miiijjmiiijjbbxbbxi=m+1,.,m+nj=m+1,.,m+n算出的ij值为按下述方法调整xij (0) 一个单位引起的空驶里程增加量。若ij来自k行和l列(k,lm+1,m+n),则把xij (0) 扩展至x kj (0)和xil (0)

5、,这时，将xij (0) 、xkj (0) 和xil (0) 三个变量的值分别调整为：(0)(0)(0)(0)(0)(0):min,:min,:min,ijijijklkjkjijklililijklxxxb bxxxb bxxxb b解的这种扩展工作按ij的大小，由小到大依次进行，直至找出要求的可接受可行解。(2) 解的收缩本步骤是步骤(1)的逆过程。对每一对xkj (1) 0和xil (1) 0(k,lm+1,m+n；i,j1,m)，计算(1)(1)min|00ijijkjilkjilcccxx，(1)(1)(1)(1)(1)(1)(1)(1)(1):min,:min,:min,kjkjkjilililkjilijijkjilxxxxxxxxxxxx进行下述解的调整：如上调整后得到的解记为X(2)=(xij (2)4. 安排行车路线经上述调整得到的解X(2)(或X(1)，当不需进行解的收缩步骤时)，可以它作为安排行车路线的依据。安排行车路线时先在可接受可行解X=(xij)的非零分量中寻求下述序列：1 22 33 40000p qk kk kk kk kxxxx，.，依据解的序列式，可得到某条初始行车路线如下：1234pqkkkkkkAAAAAA车场车场重载点