资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,设施选址方法,-,启发式算法,启发式算法,整数规划一般是不容易得到最优解的。启发式算法可以在合理的计算时间内得到较优的可行解。局域搜索启发式算法应用广泛。局域搜索的一般步骤如下:,1,、从一个初始可行解出发;,2,、找出相邻的可行解;,3,、从相邻的可行解中找出更好的可行解;,启发式算法则试图一次提供一或全部标。例如它常能发现很不错的解,但也没办法证明它不会得到较坏的解;,一般地,局域搜索启发式算法会得到一个局部最优解,而这个局部最优解有时就是全局最优解。算法的好与坏都决定于步骤,3,。启发式算法在处理许多实际问题时通常可以在合理时间内得到不错的答案。,服务系统经常会面临在一个城市内建立几家销售点等类型的问题,比如在全市范围内建几家超市,该问题较复杂,可以通过启发式算法求解。下面结合一个例子来说明具体的求解方法,某企业拟在某城市建立两家连锁超市,该市一共有四个区,记为甲、乙、丙、丁。各区可能到超市购物的人数、权重已经给出,试求超市设置在哪两个区内,使居民到超市购物最方便(即总距离成本最低)各区距离及权重数据如下表:,各区距离及权重表,各区名称,距 离,各区人口数,/,万人,人口比重,甲,乙,丙,丁,甲,0,21,15,22,15,1.4,乙,21,0,18,12,13,1.3,丙,15,18,0,20,28,1.0,丁,22,12,20,0,22,1.2,求解步骤如下:,1,)将每个区 人口数与 人口比重相乘,再乘以与其他各区之间的距离,得到总距离成本,并将各列相加,结果如下:,场址,甲,乙,丙,丁,甲,0,441,315,462,乙,355,0,304,203,丙,420,504,0,560,丁,581,317,528,0,总计,1356,1262,1147,1225,从上表可以看出,丙区所在的列总成本最低为,1147,,所以一处超市建于丙内,2,)甲乙丁各列数字与丙列队应数字比较,若小于丙列同行数字,则将其保留,偌大于丙列数字,则将原数字改为并丙列数字。如甲与丙相比,,0304,,则取,304,;,4200,,则取,0,;,581528,,则取,528.,得到新表,并将同列数字相加。,距离成本新表,场址,甲,乙,丙,丁,甲,0,315,315,315,乙,304,0,304,203,丙,0,0,0,0,丁,528,317,528,0,总计,832,632,1147,518,如上表,丁区所在列的总成最低,则选丁为另一处超市地点。,3),若要建三个超市,还需要再选一地点,则将丙列数字去掉,将甲乙列所在的数字与丁所在列数字相比较,方法同步骤(,2,)得新表:,距离成本新表,场址,甲,乙,丁,甲,0,315,315,乙,203,0,203,丙,0,0,0,丁,0,0,0,总计,203,315,518,甲列所对应的总成本为,203,,最低,则甲区成为第三个候选地点。,
展开阅读全文