《第十四章运筹学中的启发式方法课件.ppt》由会员分享,可在线阅读,更多相关《第十四章运筹学中的启发式方法课件.ppt(34页珍藏版)》请在三一办公上搜索。
1、第十四章运筹学中的启发式方法,Operational Research( OR ),运筹学中的启发式方法,启发式方法的概念应用问题举例,启发式方法的概念,一、 启发式方法的提出,良性结构的问题:问题的结构比较清晰,所含各元素之间的关系明确,边界清楚,容易为人们所认识,能够比较方便地通过建模和使用一定的算法求得解决。概括地说良性结构问题具有以下特征:(1) 能建立起反映该问题性质的一种“可接受”模型,与问题有关的主要信息可纳入模型之中。(2) 模型所需要的数据能够得到。(3) 有判定解的可行性和最优性(或满意性)的明确准则。(4) 模型可解,能拟定出求解模型的程序性步骤,而且得出的解能反映解决问
2、题的可行方案。(5) 求解工作所需的计算量不过大,所需费用不过多。,启发式方法的提出,在解决非良性结构的问题时,保持问题的本来面目,建立基本符合问题实际情况的非标准模型。由于模型涉及因素多,结构复杂,而与传统的标准模型相去甚远,难以套用已有的标准算法,为得到可用的近似解,分析人员必须运用自己的感知和洞察力,从与其有关而较基本的模型及算法中寻求其中的联系,从中得到启发,去发现和构想可用于解决该问题的思路和途径,人们称这种方法为启发式方法,用这种方法建立的算法为启发式算法。,启发式方法的特点,启发式方法有下述优点:计算步骤简单,易于实施。(2) 常不需要高深和复杂的理论知识,因而可由未 经高级训练
3、的人员实现。(3) 与应用优化方法相比,常可以减少大量的计算 工作量,从而显著节约开支和节省时间。(4) 易于将定量分析与定性分析相结合。,启发式方法的策略,三、 启发式方法的策略,1. 逐步构解策略,2. 分解合成策略,3. 改进策略,4. 搜索学习策略,运筹学中的启发式方法,启发式方法的概念应用问题举例,应用问题举例,一、 多个工件在设备上加工的排序问题,问题描述:在A、B两台设备上顺序加工n个工件(工件j=1,2,n)时,应如何排列这些工件的顺序,才能使总加工时间(从在A上开始加工第一个工件起到在B上加工完最后一个工件止)尽可能短。此处要求每个工件都先在A上加工,然后再在B上加工。,例1
4、 下表中列出了6个工件分别在设备A和B上的加工时间Aj(min)和Bj(min),所有工件都先在A上加工,再在B上加工。要求确定使总加工时间最短的工件加工顺序。,应用问题举例,解 由于B1=B2,A1A2,故将工件1排在前面进行加工所需的总加工时间较少。现再看工件2和工件3,由于A2=A3,B3B2,故将工件3排在工件2的后面加工所需的总加工时间较少。,工件,设备,应用问题举例,考虑工件1和工件2:,应用问题举例,考虑工件2和工件3:,应用问题举例,多工件在两台设备上加工排序的启发式迭代步骤如下:(1) 令i=1,k=0。(2) 找出最小加工时间:tr=minA1,A2,An,B1,B2,Bn
5、 (14.1)(3) 若tr=Aj,则将工件j安排为第i个加工工件,并置 i:=i+1;若tr=Bj,则把工件j安排为第(n-k)个加工工 件,并置k:=k+1。(4) 将Aj和Bj从式(14.1)表示的工件加工时间表中删去, 即不再考虑已排好加工顺序的工件j。(5) 返回步骤(2),直至式(14.1)中的工件加工时间表变 成空集。,应用问题举例,用迭代步骤求解例1:已知:n=6,开始迭代时i=1,k=0。由式(14.1),tr=20=A4,故将工件4排为第1,删去A4和B4,并置i=1+1=2。此时tr=30=A1=B5,将工件1排为第2,工件5排为第6(n-k=6-0=6),删去A1,B1
6、,A5和B5,置i=2+1=3,k=0+1=1。如此继续,可得所有6个工件的加工顺序为:412365总加工时间等于370分钟,具体情况参见:,应用问题举例,旅行售货员问题(TSP|traveling salesman problem)指的是: 一个售货员从某一城市出发,访问n个城市(去售货)各一次且仅一次,然后回到原城市,问他走什么样的路线才能使走过的总路程最短(或旅行费用最低)。这个问题就是寻求总权最小的哈密尔顿(Hamilton)回路问题。到目前为止,对TSP问题还没有提出多项式算法,对于较大的这种问题(例如n大于40)常需借助于启发式算法求解。,二、 旅行售货员(旅行商)问题,应用问题举
7、例,1. C|W节约算法,迭代步骤如下:选取基点,例如选取点1为基点。 将基点与其他各 点连接,得到n-1条子回路1j1(j=2,3,n)。(2) 对不违背限制条件的所有可连接点对(i,j)计算节约值(i,j不为基点)s(i,j)=c1i+c1j-cij(3) 将所有s(i,j)按其值由大到小排列。(4) 按s(i,j)的上述顺序,逐个考察其端点i和j,若满足以下条件,就将弧(i,j)插入到旅行线路中。其条件是: 点i和点j不在一条线路上; 点i和点j均与基点相邻。(5) 返回步骤(4),直至考察完所有可插入弧(i,j)为止。,应用问题举例,例2 用C-W节约算法求解下述旅行售货员问题,已知访
8、问点的位置如图中所示。,应用问题举例,解 (1)先按图中给出的数据计算各点之间的欧氏距离c(i,j),计算结果列入距离表中。因假设cij=cji,故各元素的值以主对角线为对称。,至,从,应用问题举例,(2)取A为基点,构成初始旅行线路图。,应用问题举例,(3)计算将弧(i,j)(i,jA)插入到线路中时引起的路程节约值,并由大到小排列,如下表:,应用问题举例,(4)依节约值从大到小的次序,对每条弧加以考察,看是否应将其插入线路中去。若将其插入,就要对线路作相应的改变。,应用问题举例,当插入弧(D,G)之后,线路已包含所有要访问的点,算法终止。用该方法得到的线路是:AGDEFCBA该线路的总长度
9、:z=2(14.14+24.70+23.71+19.24+17.03+13.00) -(34.70+33.44+30.07+25.80+23.11) =76.52,应用问题举例,2. 几何法基于对各访问点构成的几何图形的分析,以此确定初始线路和不在初始线路上的各点的插入顺序和插入位置。,根据一般几何观察可知,最短访问线路应具有以下直观性质: (1)线路自身不相交; (2)各段线路应处于由所有访问点形成的凸包上或其凸包内部(这里所说的凸包(convex hull)是包含所有访问点的最小凸集)。,应用问题举例,求解旅行售货员问题的迭代步骤:找出由欲访问各点构成的凸包。(2) 在凸包上的点,按其出现
10、的自然顺序访问(不要使访问线路自交),从而形成一初始访问线路。(3) 将不在初始访问线路上的各个点I(位于凸包内的访问点),与已在访问线路上的所有点相连。设P与Q为已在访问线路上的任两个相邻点,P0I0Q0为所有PIQ角度中的最大者,则将I0插入到P0和Q0之间。(4) 重复进行步骤(3),每次在访问线路上增加一个新点,直至所有欲访问点都被引入到访问线路中为止。这时就构成了一条哈密尔顿回路。,应用问题举例,用几何法求解例2:,应用问题举例,三、车辆调度问题(vehicle scheduling problem,简记为VSP),所谓VSP问题,一般指的是: 对一系列发货点和收货点,组织调用一定的
11、车辆,安排适当的行车路线,使车辆有序地通过它们,在满足指定的约束条件下(例如: 货物的需求量与发货量,交发货时间,车辆可载量限制,行驶里程限制,行驶时间限制等),力争实现一定的目标(如车辆空驶总里程最短,运输总费用最低,车辆按一定时间到达,使用的车辆数最小等)。,应用问题举例,问题说明 设某运输企业要完成的货运业务(例如指某一天或某半天)有m项:A1,A2,Am,其货运量分别是g1,g2,gm,完成各项运输业务所需的车辆数(根据货物类型和车辆状况而定)分别为a1,a2,am; 此外,该企业有n个车场可以使用,即可从车场Am+1,Am+2,Am+n发出空车和接收空车,这些车场与各货运业务的发货点
12、和收货点位于同一个连通道路网上,各车场可派出的空车数分别是bm+1,bm+2,bm+n,可接收的空车数分别是bm+1,bm+2,bm+n。,应用问题举例,2. 数学模型按照每项运输业务的要求将货物由发货点运送到收货点,这显然均为重车行驶,且必须完成,在分析使总空驶里程极小化这一问题时,它的安排对目标函数值不产生影响,可不予考虑。因此,可将每一项货运业务工作i,即从其发货点i将货物运送到收货点i,看成一个压缩了的点重载点i。,应用问题举例,设由点i发往点j(i,j为车场或重载点)的空车数为xij,其空驶里程为cij,则使总空驶里程极小化的空车调度问题的数学模型可描述如下:,i=1,2,.,mi=
13、m+1,m+2,.m+nj=1,2,.,mj=m+1,m+2,.m+n,其中ai(aj)为:,Q为一辆车的可载量。,应用问题举例,运输问题式的运输表如表所示。表中将重载点和车场分开,形成了4个区域:CC,CF,FC和FF,应用问题举例,3.算法,首先仅考虑重载点部分:,i=1,2,.mj=1,2,.m,应用问题举例,(1) 解的扩展对解X(0)中的每一个非零分量xij (0) 0(i,j=1,2,m),计算,其中:,i=m+1,.,m+nj=m+1,.,m+n,应用问题举例,算出的ij值为按下述方法调整xij (0) 一个单位引起的空驶里程增加量。若ij来自k行和l列(k,lm+1,m+n),
14、则把xij (0) 扩展至x kj (0)和xil (0),这时,将xij (0) 、xkj (0) 和xil (0) 三个变量的值分别调整为:,解的这种扩展工作按ij的大小,由小到大依次进行,直至找出要求的可接受可行解。,应用问题举例,(2) 解的收缩本步骤是步骤(1)的逆过程。对每一对xkj (1) 0和xil (1) 0(k,lm+1,m+n;i,j1,m),计算,进行下述解的调整:,如上调整后得到的解记为X(2)=(xij (2),应用问题举例,4. 安排行车路线,经上述调整得到的解X(2)(或X(1),当不需进行解的收缩步骤时),可以它作为安排行车路线的依据。,安排行车路线时先在可接受可行解X=(xij)的非零分量中寻求下述序列:,依据解的序列式,可得到某条初始行车路线如下:,车场,车场,重载点,