现代设施规划与物流分析 教学课件 作者 戢守峰 第10章 设施布置问题的模型、算法与量化技术.ppt

《现代设施规划与物流分析 教学课件 作者 戢守峰 第10章 设施布置问题的模型、算法与量化技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章设施布置问题的模型、算法与量化技术10.1设施布置问题模型的基本概念10.2设施布置设计的图论方法10.3二次分配问题(QAP)的模型与算法10.4遗传算法在设施布置问题中的应用《设施规划与物料搬运》课程之：目标：实现时间和成本最小化布置模型：10.1.1设施布置问题概述单列布置多列布置10.1设施布置问题模型的基本概念图10-1单列布置和多列布置机场中飞机停靠门的分配问题D终端候机大厅图10-2机场中飞机停靠门的分配步骤：◎建模◎求解◎确定位置◎修正形状10.1.2单列布置问题模型假设：(1)设施形状是长方形或正方形,均为已知;(2)设

2、施排列在一直线上;(3)设施方位是已知的。模型分析：决策变量：xi设施中心与垂直参考线间的距离目标函数：两设施间的往复行程数在内的总成本最小约束条件：不能重叠可以用公式表示成等长度和不等长度设施的布置问题10.1.3ABSMODEL1假设：(1)设施形状是长方形或正方形,均为已知;(2)设施排列在一直线上;(3)设施方位是已知的。模型分析：决策变量：xi设施中心与垂直参考线间的距离目标函数：两设施间的往复行程数在内的总成本最小约束条件：不能重叠可以用公式表示成等长度和不等长度设施的布置问题图10-4单列布置中各变量与决策变量的表示先决定用于ABSM

3、ODEL1中各参数的符号：10.1.3ABSMODEL110-110-210-1通常非线性规划（NLP）问题的优化解是难求出的，属于NP-hard问题。10.1.4不等面积设施的多列布置模型10.1.5多列布置问题模型——ABSMODEL3假设：(1)设施之间水平和垂直方向间距相等(2)设施非排列在一直线上;(3)设施方位是已知的。模型分析：决策变量：xi、yi设施中心与垂直参考线间的水平和垂直距离目标函数：设施之间的行程数在内的总成本最小约束条件：保证设施间水平和垂直方向不会重叠可以用公式表示不等面积设施的布置问题10.1.3多列布置问题模型——

4、ABSMODEL3先决定用于ABSMODEL3中各参数的符号：图10-9不等面积多列布置决策变量与参数的表示10-410-510-610-710.1.6模型问题的探讨设施位置问题的模型ABSMODEL直观、方便、容易理解，并能用简单的启发式解题。这一模型的主要缺点是要求设施的外形只能是方形或长方形，还要假定已知设施的方位。因为模型ABSMODEL是非线性的，因而期解经常是次优的或远离优化。对于真正在实际中应用的多列布置模型，除ABSMODEL3外还有和其相当的二次分配模型（QAP）。10.2.1图论方法10.2设施布置设计的图论方法基于对关系密

5、切程度量化的方法对改进类型的构造方法计算机布置规划程序的类别计算机布置设计和量化技术的价值在于，当需要建立一个总体规划而非为满足制造规划和控制要求而进入详细设计时，提供一个设施布置的静态结构。关键词：10.2.2布置设计中应用图论方法的实例10.2设施布置设计的图论方法计算机布置设计和量化技术的价值在于，当需要建立一个总体规划而非为满足制造规划和控制要求而进入详细设计时，提供一个设施布置的静态结构。关键词：方法-----部门位置的交换面积相仿的部门具有共同边界的部门相互交换或三方交换降低运输费用10.2.4MultiPLEMulti-floorPl

6、antLayoutEvaluation类似于Craft,输入数据为物流从至表，目标函数为基于距离的函数，距离计算采用中心点直线距离。部门间的交换采用2部门交换区别在于：交换不局限于相邻部门，这通过空间填充曲线（SFC，SpaceFillingCurve)实现。10.3二次分配问题（QAP）的模型与算法10.3.1二次分配问题（QAP）的概念在设施布置问题中，有n个设施被分配到m个给定位置，分配一词意味着将每一设施与一特定的位置相匹配或相反。QAP（quadraticassignmentproblem）的明确表达需要相同数目的设施和位置。假如有少于m

7、的n个设施被分配到n位置上（m

8、的解题思路：将现存设施也视为新设施，问题变为如何将n个新设施放入m个场址中，使其相互联系的费用最少。10.3.2二次分配问