物流系统优化与仿真.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,物流系统优化与仿真,彭扬 伍蓓,/,著,内容提要,物流系统优化是实现物流管理目标、体现物流管理效率与效益的必要过程和手段。物流系统优化主要有运筹学方法、智能优化方法和模拟仿真法等三种方法。,系统仿真是根据被研究的系统模型，利用计算机进行实验研究的方法,.,目前仿真技术是分析、研究复杂物流系统的重要工具，也成为物流工程技术人员的一项重要技能。,内容提要,本书即强调优化和仿真的方法学和技术，又立足于物流系统的管理决策问题的解决。,在知识体系上，“横向”方面从传统的运筹规划方法、排队存储论方法、系统动力学方法到现代智能优化方法以及,Petri,网、多,Agent,、面向对象等仿真方法的介绍；“纵向”方面主要是物流系统的一些应用问题，如物流网络布局问题、车辆路径问题、装卸搬运问题、区域物流宏观规划问题以及供应链系统设计问题等。,目录,第,1,章 物流系统优化概述,第,2,章 物流系统模型,第,3,章 物流系统优化的运筹规划方法,第,4,章 物流系统模型的智能优化方法,第,5,章 物流系统仿真应用基础,第,6,章 物流系统动力学仿真,第,7,章 排队模型与存储模型及应用,第,8,章,Petri,网模型及仿真,第,9,章 物流系统仿真方法的发展,第,10,章 供应链系统仿真优化,第,11,章 博弈论及其在供应链中的应用,第,12,章 仿真工具与软件应用,第,1,章 物流系统优化概述,本章概述了物流系统优化的相关概念，并就物流优化的主要方法进行了综合性的介绍。,1.1,物流系统,1.2,物流系统优化问题,1.3,物流系统优化的方法,1.1,物流系统,1.1.1,系统及其特征,1,我国系统科学界对系统的通用定义是,(,钱学森,):,系统是由相互作用和相互依赖的若干组成部分结合而成的、具有特定功能的有机整体，而且这个整体又是它从属的更大的系统的组成部分。输入、处理（转换）、输出是组成系统的三大要素,.,(,输入,),处理（转换）,(,输出,),(,约束和干扰,),图,1.1,系统的一般模式,整体性,相关性,目的性,环境适应性,2,系统的特征,1.1.2,物流系统的概念和要素,1,物流系统的概念,:,和一般系统一样，具有输入、转换、输出三要素。通过输入和输出使系统与社会环境进行交换，使系统和环境相依存,.,环境,（,1,),原材料设备,（,2,),劳动力,（,3,）,能源,（,4,）,资金,（,5,）,信息等,（,1,）,产品位置转移,（,2,）各种劳务,（,3,）,能源,（,4,）,信息,（,5,）好的服务,（,1,）,物流设施与设备,（,2,）,物流业务活动,（,3,）,信息处理,（,4,）,管理工作,输入,系统转换,输出,环境,干扰,反馈,图,1.2,物流系统的一般模型,2,物流系统的特点,是一个大跨度系统,是一个可分系统,是一个动态系统,:,是一个复杂系统物流系统运行对象一“物”，遍及全部社会物质资源，资源的大量化和多样化带来了物流的复杂化,是一个多目标函数系统,3,物流系统的目标,将货物按照规定的时间、规定的数量送达到目的地,合理配置物流中心，维持适当的库存,实现装卸、保管、包装等物流作业的省力化、效率化,维持合适的物流成本,实现从订货到出货全过程信息的顺畅流动等,4,物流系统的要素,一般要素,功能要素,支撑要素,物质基础要素,5,物流系统中的制约关系,物流服务和物流成本间的制约关系,如图,1.3,构成物流服务子系统功能之间的约束关系,构成物流成本的各个环节费用之间的关系,各子系统的功能和所耗费用的关系,图,1.3,服务与成本的制约关系,1.1.3,物流系统化,1.,物流系统化的目标,总体目标,目标体系,服务目标,快速、及时目标,节约目标,规模优化目标,库存调节目标,2,系统目标关系的协调,原则,层次间的目标发生冲突时，通常要以较低层次的目标服从于较高层次目标的要求为前提协商解决。,于同一层次上的目标发生冲突时，应该在分析的基础上确定一定的取舍和补偿标准进行协调与决策。,3.,物流系统设计要素,Products,Quantity,Route,Service,Time,Cost,1.2,物流系统优化问题,1.2.1,物流系统的效益目标,物流的宏观经济效益是指物流系统的建立对社会经济效益的影响，直接表现为物流对整个社会流通及全部国民经济效益的影响。,物流系统的微观经济效益是指该系统本身在运行后所获得的效益。其直接表现形式是物流系统本身所耗与所得之比。,1.2.2,物流系统优化的必要性,1,要素目标冲突,要素之间的目标冲突,要素内部的目标冲突,物流系统与其它系统的目标冲突,2,要素产权冲突,物流系统是由不同产权组织共同完成的，产权边界不清晰。,必须克服这种产权的分散性与物流系统的统一性之间的矛盾。,3,要素运作冲突,1.2.3,系统优化设计,1.,优化设计的概念,实现问题的优化必须具备两个条件：一是存在一个优化目标；另一是具有多个方案可供选择。,2,优化设计的数学模型,优化设计三要素,设计变量,目标函数,设计约束与可行域,3,优化方法的分类,有多种类型，有不同的分类方法,4,优化设计步骤,设计对象的分析,设计变量和设计约束条件的确定,目标函数的建立,合适的优化算法的选择,优化结果分析,1.2.4,物流系统优化的原则,美货运计划解决方案供应商,Velant,公司的总裁和,Don Ratliff,博士在,2002,年美国物流管理协会（,CLM,）年会上提出了“物流优化的,10,项基本原则，并认为通过物流决策和运营过程的优化，企业可以获得降低物流成本,10%-40%,的商业机会。,物流优化的,10,项基本原则,目标（,Objectives,）：设定的目标必须是定量的和可测评的。,模型（,Models,）：模型必须忠实地反映实际的物流过程。,数据（,Data,）：数据必须准确、及时和全面。,集成（,Integration,）：系统集成必须全面支持数据的自动传递。,表述（,Delivery,）：系统优化方案必须以一种便于执行、管理和控制的形式来表述。,算法（,Algorithms,）：算法必须灵活地利用独特的问题结构。,计算（,Computing,）：计算平台必须具有足够的容量在可接受的时间段内给出优化方案。,人员（,People,）：负责物流系统优化的人员必须具备支持建模、数据收集和优化方案所需的领导和技术专长。,过程（,Process,）：商务过程必须支持优化并具有持续的改进能力。,回报（,ROI,）：投资回报必须是可以证实的，必须考虑技术、人员和操作的总成本。,要证实物流系统优化的投资回报率，必须把握两件事情：,诚实地估计全部的优化成本,将优化技术给出的解决方案逐条与标杆替代方案进行比较,要确定物流优化技术系统的使用效果，必须做三件事,在实施优化方案之前根据关键绩效指标（,Key Performance Indicators,）测定基准状态,将实施物流优化技术解决方案以后的结果与基准状态进行比较,对物流优化技术系统的绩效进行定期的评审,1.2.5,物流系统优化的层次,可以依照以下几个层次,决策层,中间层,执行层,1.3,物流系统优化的方法,物流系统优化方法主要有,运筹学方法,智能优化方法,模拟仿真法,1.3.1,运筹学方法,1,线性规划,一般线性规划模型的表达形式,线性规划的求解,线性规划可能是非可行的,可能只有无界的解,在大多数情况下，线性规划至少有一个有限的最优解，有时它还会有多重的最优解。,整数规划,非线性规划,线性规划的性质,对于现实生活中的问题必须把其中基本部分抽出来构成数学模型,研究解的结构和系统化的求解程序,产生了所期望的系统的最优解，或者至少是得到了通过对客观需要的评价，经过比较的行动方针,2,网络与图论法,3,库存论,4,排队论,1.3.2,智能优化方法,1,智能优化算法的概念,优点,与精确算法相比的明显优势在于,:,能显著的节省时间开支；,灵活，在不能用定量表示的约束集合中，用它制订计划；,比较简单，常能由缺乏高级训练的实践者来实现；,3,、几种常用的智能优化技术,1.3.3,模拟仿真法,1,仿真模型,系统仿真的目的在于利用人为控制的环境条件，改变某些特定的参数，观察模型的反应，研究真实系统的现象或过程，是一种间接的研究方法。,优势,符合人们的思维习惯，有助于系统分析,系统仿真可以是一种非解析的分析方法，对各种复杂的系统具有很好的适应性,系统仿真有利于解决随机因素的影响,系统仿真可以帮助系统优化,不单纯追求最优解，而寻求改善系统行为的途径和方法。系统仿真方法正是提供了这种环境。,利用仿真模型进行系统分析,利用仿真模型进行系统的综合,结构的几何性质,力的相互作用,构件特性,尺寸、强度、形状,输入变量,荷载、风力、流量、地震等,桥模型,反馈,构件的应力、就变等,输出系统响应,决定下一组输入变量值,图,1.4,用仿真进行系统分析,结构的几何性质,力的相互作用,构件特性,尺寸、强度、形状,输入变量,荷载、风力、流量、地震等,桥模型,反馈,构件的应力、就变等,输出系统响应,改变系统单元的性质,图,1.5,用仿真进行系统综合,3,系统仿真在物流系统研究中的作用,物流系统规划与设计,仓储规模与库存管理,物料运输调度,物流成本估算,1.3.4,物流系统优化方法的比较,运筹学方法和智能优化方法可以统称为解析法。,1,解析法的优势,解析法是建立在数学模型的基础上的。数学模型是定量化的，可以产生更高的精确度。,模拟仿真活动有时要耗费大量的时间和物资，花费高昂的代价才能够取得成果；而某些物流系统活动则不能或者很难做仿真实验。,2,仿真方法的优势,动态的、瞬时的影响,随机因素,非标准分布,随机活动的交互作用,第,2,章 物流系统模型,本章首先概述了几类主要的模型及其特点，并对常用的物流系统建模技术进行讨论。,2.1,模型概述,2.2,物流系统模型,2.3,建模方法与步骤,2.4,物流系统建模技术,2.1,模型概述,2.1.1,模型的分类,1.,实体模型,2.,图形模型,流程图,方框图,结构图,流图,3.,数学模型,广义：凡是一切数学概念、数学理论体系、各种数学公式、各种方程式以及由公式系列构成的算法系统等都被称为数学模型。,狭义：凡是将具体现象、事物的特征和性质给以数学表达的数学结构，如各种等式、不等式、图、表或框图等，也叫数学模型。,数学模型，包括原始系统数学模型和仿真系统数学模型。仿真系统数学建模过程称为二次建模过程。,模拟模型,模拟模型和原系统的物理元素完全不同，但动作相似。,2.1.2,数学模型的意义,2.1.4,系统模型模拟的特殊作用,过程系统流程复杂、投资巨大、生产连续性强，一般不允许在真实系统上进行试验研究。,计划中或设计中的过程系统尚不存在。,高质量的模拟模型具有预测性。,实际过程系统根本不允许作的试验。,大大节省原材料、能源消耗和人力资源等。,模型的预测性。,传递复制极为方便。,2.2,物流系统模型,2.2.1,物流系统模拟技术的应用,1.,物流系统规划与设计,2.,物料控制,3.,物料运输调度,4.,物流成本估算,2.2.2,物流系统模型的特点,1.,三个特征：,是实体的抽象或模仿,是由与分析问题有关的因素所组成,是用来表明这些因素间的关系,主要参数：,周期数、库存量、初始库存、库存价格、库存成本、进,(,出,),货量,2.2.3,物流系统常用的数学模型,1.,资源分配型,2.,存储型,3.,输送型,4.,等待服务型,5.,指配型,6.,决策型,7.,其他模型,2.2.4,物流模型构建的原则,1,模型构造的系统化,2,物流模型简单化,3,物流研究多方位化,4,物流模型构建的规范化,2.3,建模方法与步骤,2.3.1,系统建模方法,U,代表目标值，一般希望达到最大值,(,如利润、效益等,),或最小值,(,如成本、支付、亏损等,),，加上约束条件就形成一个系统模型。,模型思路,1.,直接分析法,例,2.1,流通加工中的下料问题。试求面积为一定值的矩形中，周长和为最小时的各边长度。,2.,数据分析法,通过分析系统功能的已有数据或新做的试验所获取的数据可以建立系统的模型。,3.,实验分析法,例,2.2,4.,主观想象法,5.,人工实现法,2.3.2,物流系统模型建立步骤,弄清问题，掌握真实情况,搜集资料,确定因素之间的关系,构造模型,求解模型,检验模型的正确性,2.3.3,系统模拟遵循的总体工作流程,系统定义,数学建模,模拟建模,装载,试验,结果分析,图,2.4,系统模拟的工作流程,2.3.4,物流系统建模应注意的几个问题,1.,对研究对象的了解,经常遇到以下情况,片面性、偏离了实际,无法获得完备的、有关过程系统的数据源,数学方法不正确,建模效率低,2.,对于模型构建者提出的要求,面向实际,具备跨学科多专业的知识及扎实的数学功底,意志、善于合作,注意外部环境,3,物流系统建模应注意的问题,明确目的，确定构成要素,模型的简单化和高精度模型,没有固定不变的建模方法,2.4,物流系统建模技术,2.4.1,形式化建模与非形式化建模技术,1.,形式化建模技术,排队网络法、极大代数法、扰动分析法,2.,非形式化建模技术,活动循环图、流程图法、面向对象的建模技术,3.Petri,网络物流系统模型,图,2.5 Petri,网示意图,4.,系统动力学建模技术,动力学系统涵义,组成部分的子结构及其相互间的关系,系统内部的反馈回路结构及其相互作用,5.Agent,与,Multi-Agent,模型应用,Agent,与多,Agent,系统,Agent,的特征,自治,智能,交互,基于,Agent,的建模思想,无论在现在还是在将来的计算机科学及其应用领域中，由,Agent,组成的,RAS,有能力扮演重要的角色。,在建立和分析人类社会中的交互模型和理论方面，,MAS,也可以扮演重要的角色。,在物流供应链系统建模中的应用,第,3,章 物流系统优化的运筹规划方法,本章将就物流系统中常见的规划模型形式及求解方法进行研究，并以一个物流网络布局问题的建模与求解作为实例说明该方法的一般应用过程。,3.1,概述,3.2,求解方法,3.3,物流网络布局问题的建模与求解,3.1,概述,3.1.1,物流系统数学模型构建和模拟过程,3.1.2,运筹学规划论模型,1.,线性规划模型,基本结构,决策变量,约束条件,决策目标,标准型的特点,目标函数是最大化类型,约束条件均由等式组成,决策变量均为非负,模型隐含的假设,比例性假定,可加性假定,连续性假定,确定性假定,图,3.2 LP,问题的解之间的关系图,LP,问题的解的概念,可行解和最优解,基、退化解、最优基,可行解,基本解,基可行解,建立线性规划模型的基本步骤,明确管理问题，确定决策目标，分析约束因素,建立包含一组线性约束条件等式或不等式和最优线性目标函数表达式的数学模型,数学模型的求解与检验,优化后的分析,整数规划,纯整数规划,混合整数规划,纯,01,整数规划,混合,01,整数规划,2,非线性规划模型,特征,每个问题都可用一组决策变量,(x1,，,x2,，,xn),表示某一方案,存在一组线性等式或不等式的约束条件,目标函数,3.1.3,几个物流系统数学模型的例子,1.,运输问题的数学模型,2.,物流配送计划的制定问题,3.,集装箱拼箱及装箱问题,4.,物流网络布局问题的数学模型,3.2,求解方法,3.2.1,单目标优化问题求解算法,1,无约束优化问题的牛顿法及其修正方法,牛顿法,阻尼牛顿法,2,拉格朗日乘子法,拉格朗日乘子法求约束优化问题的计算步骤如下,3,单纯形法,基本思想,单纯形法是描述可行解从可行域的一个极点沿着可行域的边界移到另一个相邻的极点时，目标函数和基变量随之变化的方法。,步骤,图,3.3,单纯形法的求解过程,4,非线性规划及求解,乘子法,3.2.2,多目标函数的优化方法,1,统一目标法,极小化“统一目标函数”，为了使各个目标函数能均匀一致地趋向各自的最优值，可采用的方法,2,主要目标法,3.2.3,整数规划及求解,1,割平面法,2,分枝定界法,3,求解,0-1,规划的隐枚举法,隐枚举法的基本原理与步骤,4,求解指派问题的匈牙利法,3.2.4,动态规划法,1,动态规划的基本概念,2,动态规划模型的构成,3,基本原理和基本方程,3.2.5,图与网络优化算法,1,、求最小生成树的,Kruskal,算法,2,、求最短路径的,Dijkstra,算法,：,3.,求二部图最大匹配（指派问题）的匈牙利算法：,最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。,增广链,截集（割集）,最大流最小截量定理,4,求最大流的方法,(Ford-Fulkerson,标号法,),5.,贪心法与拟阵,贪心法的思想是：,从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。,该算法存在问题：,不能保证求得的最后解是最佳的；,不能用来求最大或最小解问题；,只能求满足某些约束条件的可行解的范围。,实现该算法的基本思路是：,从问题的某一初始解出发，重复判断如果能朝给定总目标前进一步，则求出可行解的一个解元素，直到由所有解元素组合成问题的一个可行解为止。,组合算法：,提前判断出某些情况不可能取到最优解。,3.3,物流网络布局问题的建模与求解,3.3.1,概述,1.,物流网络布局问题的意义与主要内容,2.,物流网络规划的步骤,找出物流网络规划的约束条件,根据约束条件构造物流网络符合的模型,将物流网络符合的模型转化成数学模型求出多组可行解,利用可行的评估方法或准则，对以上求出的多组可行解进行评估，将各可行解进行排序，以选取最适合的规划方案,3.,选址问题的一个简单实例,3.3.2,多元网点布局问题,1,问题描述,多元网点布局问题通常有如图,3-5,所示的系统结构。图中有,m,个资源点,A,i,(,i,=1,，,2,，,，,m,),，各点的资源量为；有个需求点，各点的需求量为；有个可能设置网点的备选地址；需求点可以从设置的网点中转进货，也可以从资源点直接进货。假定各备选地址设置网点的基建投资、仓储费用和运费率均为已知，以总成本最低为目标确定网点布局的最佳方案。,图,3-5,网点布局结构示意图,2,多元单品种物流网点布局的建模方法,3,多元多品种物流网点布局的建模方法,3.3.3,设施容量问题（,CFLP,法）,CELP,法的基本思想是：,首先假定网点布局方案已经确定，即给出一组初始网点设置地址。根据初始方案按运输规划模型求出各初始网点的供货范围，然后在各供货范围内分别移定网点到其他备选地址上，以使各供货范围内的总成本下降，找到各供货范围内总成本最小的新网点设置地址，再将新网点设置地址代替初始方案，重复上述过程直至各供货范围内总成本不能再下降时为止。,以图,3-6,所示的物流网络结构为对象来介绍,CFLP,方法的处理过程,CFLP,法的基本步骤,给出网点地址初始方案,确定各网点的供货范围,寻求网点地址的新方案,新旧方案对比,图,3-6,网络结构图,数例：在某计划区域内，物流网络结构如图,3-6,所示，其中有,12,个需求点，“”中的数字为各点需求量，弧线旁的数字为运价系数。现需要在,12,个需求点的位置上选取,3,个点作为网点设置地址。假定网点的最大规模为,13,，设定每个网点的固定成本为,10,。,图,3-7,物流网络结构图,步骤,2,以,4,，,6,，,9,为发货点，各点发货量均为,13,；以需求点为收货点，需求量为已知；收、发货点之间的费用系数用最短路线法求得构成运输规划模型，如表,3-1,所示。,表,3-1,运输模型,步骤,3,寻找各子区域内使区域总费用最小的网点位置。,表,3-2,初始方案,上面讨论的是网点数目有限的情况，如果网点数目没有限制，则只需对网点数目为,1,，,2,，,3,，,，,12,诸情况分别进行讨论，找出使系统总费用最低的网点数目作为最佳方案即可。,第,4,章 物流系统模型的智能优化方法,本章介绍常见的一些智能优化方法及其在物流系统中的应用。,4.1,智能优化方法概述,4.2,人工神经网络,4.3,禁忌搜索,4.4,遗传算法,4.5,模拟退火算法,4.6,群体智能方法,4.7,车辆路径问题模型及求解,4.1,智能优化方法概述,4.1.1,优化算法及其分类,目前工程中常用的优化算法,经典算法,构造型算法,邻域搜索算法,局部搜索法,指导性搜索法,基于系统动态演化的方法,混合型算法,4.1.2,智能优化算法的概念,智能优化算法的基本概念,搜索空间（,Search Space,）,计算复杂性与,NP,难题,(NP-hard),按照计算复杂性理沦研究问题求解的难易程度，可把问题分为,P,类、,NP,类和,NP,完全类。其性质如下：,1,、这类问题中任何一个问题至今未找到多项式时间算法。,2,、如果这类问题中存在一个问题有多项式时间算法，那么这类问题都有多项式时间算法。,4.2,人工神经网络,4.2.1,人工神经网络概述,神经元及其特性,人工神经网络的基本特性和结构,x,1,x,2,x,n,V,1,V,2,V,n,x,1,x,2,x,n,输入,输出,图,4.3,递归（反馈）网络,x,1,x,2,x,n,w,1m,输入层,隐层,图,4.4,前馈（多层）网络,w,11,y,1,y,n,输出层,人工神经网络的简单原理,人工神经网络是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。,4.2.2,人工神经网络的数学模型及应用,1.BP,神经网络的数学模型,2.BP,算法的实现步骤,3,神经网络模型的运行,神经网络的运行包括两个阶段：,训练或学习阶段（,training or learning phase,）。,预测（应用）阶段（,generalization phase,）。,4.3,禁忌搜索,4.3.1,禁忌搜索算法的主要构成,1,、初始解,2,、邻域移动,3,、禁忌表和禁忌移动,4,、选择策略,5,、破禁策略,两个准则：,基于适值是准则：若某个禁忌侯选解的适值优于以往搜索最优解，则解禁此候选解为当前解；,基于搜索方向的准则：按有效的搜索途径进行。,6,、禁忌频数,7,、停止规则,给定最大迭代步数：,当总迭代次数达到一个给定的最大迭代步数，或在一个给定的连续迭代步数内当前的最好解没有改善时，则算法终止。,禁忌频率数控制原则：,达到一定禁忌频数要求时，即当不能使当前最好解改善的循环次数超过了预先设定的阈值时，则算法终止；,目标值变化控制原则：,当目标值偏离最优值的程度超过了预先设定的阈值时，则算法终止。,目标值偏离程度原则：,当目标值偏离最优值的程度超过了预先设定的阈值时，则算法终止。,4.3.2,禁忌搜索算法流程,主要步骤如下：,给定算法参数，随机产生初始解，置禁忌表为空；,设当前解,Xcurrent,=,Xint,，当前最好解,Xbest=Xint,；,判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继 续以下步骤。,Xint,的邻域内产生,Ns,个测试解,Xi,，,1i,Ns,；,求出目标函数,f,(,Xi,),；,判断测试解是否在禁忌表中，若不在禁忌表或在禁忌表中但在其目标函数值比,Xbest,还好，则把它作为新的当前解,Xcurrent,，并转到；否则，继续测试下一个测试解。若所有的测试解都在禁忌表中，则转到；,Xbest,=,Xcurrent,；若禁忌表已满，则按先进先出的原则更新禁忌表；把当前解,Xcurrent,插入禁忌表；,记下最优解,Xbest,，结束算法。,4.4,遗传算法,4.4.1,进化计算与遗传算法概述,进化算法,（,Evolutionary Computation,）是指一类以达尔文进化论为依据来设计、控制和优化人工系统的技术和方法的总称，包括遗传算法（,genetic algorithm,）、进化策略（,evolutionary strategy,）和进化规划（,evolutionary programming,）。,遗传算法,中处理的是染色体，或者叫基因型个体。一定数量的个体组成丁群体,(population),。群体中个体的数目称为群体规模,(population size),。而各个体对环境的适 应程度叫作适应度,(fitness),。,两个必要的数据转换操作，一个是表现型到基因型的转换，另一个是基因型到表现型的转换。,主要特点,直接对结构对象进行操作，不存在求导和函数连续性的限定；,具有内在的隐并行性和较好的全局寻优能力；,采用概率化的寻优方法,4.4.2,基本遗传算法,1.,染色体编码方法,2.,适应度函数,3.,遗传算子,选择算子：,交叉算子,变异算子,4.,基本遗传算法的运行参数,N,：群体大小，即群体中所含个体的数量，一般取,20,100,；,T,：遗传算法的终止进化代数，一般取为,100,500,Pc,：交叉概率，一般取为,0.4,0.99,Pm,：变异概率，一般取为,0.000l,0.1,4.4.3,基本遗传算法的一般框架,问题求解的过程,编码,初始群体的生成,适应性值评估检测,选择,交叉,变异,基本遗传算法可定义为一个八元组：,SGA,(C,，,E,，,P0,，,M,，,，,，,，,T),式中各元素的意义为：,C,个体的编码方法；,E,个体适应度评价函数；,P0,初始群体；,M,群体大小；,选择算子；,交叉算子；,变异算子；,T,遗传运算终止条件。,GEN,0,计算群体中每个个体的适应值,随机创建初始群体,概率地选择遗传操作,是否满足选中标准,i,0,i,M,完成杂交,GEN,GEN,1,根据适应值,选择两个个体,根据适应值,选择一个个体,根据适应值,选择一个个体,i=i+1,完成变异,完成繁殖,把新的孩子,加入到群体中,把变异后个体,加入到群体中,把变异后个体,加入到群体中,把新的两个孩子,加入到群体中,i=i+1,指定结果,结果,Y,Y,N,N,其中：变量,GEN,是当前进化,代数：,N,是群体规模；,M,是算法执行的最大次数,图,4.4,基本遗传算法流程图,4.4.4,遗传算法的应用,1.,遗传算法的应用步骤,确定决策变量及其各种约束条件，即确定个体的表现型和问题的解空间。,建立优化模型，即确定出目标函数的类型及其数学描述形式或量化方法。,确定表示可行解的染色体编码方法，也即确定出个体的基因型及遗传算法的搜索空间。,确定解码方法，即确定出由个体基因型到个体表现型的对应关系或转换方法。,确定个体适应度的量化评价方法，即确定由目标函数值,f,(X),到个体适应度,F(X),的转换规则。,设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。,确定遗传算法的有关运行参数，即确定出遗传算法的群体规模,popSize,，终止进化代数,maxGen,，交叉概率,pc,和变异概率,pm,。,2.,遗传算法的特点,优点,遗传算法可以直接根据目标函数值进行搜索，而无需其它信息，如导数信息；,遗传算法同时使用多个搜索点的搜索信息，隐含并行搜索特性；,遗传算法使用概率搜索特性，其选择、交叉和变异等运算都是以一种概率的方式来进行的，增加了其搜索过程的灵活性；,遗传算法具有全局搜索能力，善于搜索复杂问题和非线性问题；,遗传算法同求解问题的其它启发式算法有较好的兼容性，可以与其它优化算法进行结合，改进算法性能。如模拟退火遗传算法。,缺点,编码不规范及编码存在表示的不准确性。,单一的遗传算法编码不能全面地将优化问题的约束表示出来。,易于陷入局部最优点，导致早熟。,4.5,模拟退火算法,4.5.1,模拟退火算法的模型,1.,基本思想,初始化：初始温度,T(,充分大,),，初始解状态,S(,是算法迭代的起点,),，每个,T,值的迭代次数,L,。,对,k=1,，,，,L,做第,(3),至第,6,步。,产生新解,S,。,计算增量,t=C(S)-C(S),，其中,C(S),为评价函数。,若,t0,，然后转第,2,步。,2.,模拟退火算法新解的产生和接受可分为如下四个步骤,由一个产生函数从当前解产生一个位于解空间的新解。,计算与新解所对应的目标函数差。,断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是,Metropo1is,准则,:,若,t3,，表示该解是一个可行解；若,m0,，,B0,，分别表示变量,A,、,B,的改变量。若满足下列条件之一：,A,加到,B,中；,A,是,B,的乘积因子；,A,变到,AA,，有,B,变到,BB,，即,A,、,B,的变化方向相同。,则称,A,到,B,具有正因果关系，简称正关系，用“”号标在因果链上。,若满足下列条件之一：,A,从,B,中减去；,1/A,是,B,的乘积因子；,A,变到,AA,，有,B,变到,BB,，即,A,、,B,的变化方向相反。,则称,A,到,B,具有负因果关系，简称负关系，用“”号标在因果链上。,图,6.1,因果链,当这种关系从某一变量出发经过一个闭合回路的传递，最后导致该变量本身的增加，这样的回路就称为正反馈环，反之则称为负反馈环。,实际的复杂社会系统都是由许多相互联系的非线性反馈回路组成。,实际的复杂社会系统都是由许多相互联系的非线性反馈回路组成。,系统动力学了解系统动态特性的主要方法是回路分析法（即因果关系和反馈思想）。,反馈分为正反馈与负反馈，一般原则是：若反馈回路包含偶数个负的因果链，则其极性为正，叫正反馈回路；若反馈回路包含奇数个负的因果链，则其极性为负，叫负反馈回路。,图,6.2,因果反馈回路（环）,3.,流位与流率,每一个反馈环中至少包含着两种基本的变量即流位与流率。,流位是系统内流量的积累，它是系统的状态变量。,流率从物理概念上将流位变化定量化，根据对流位的关系分成入流率和出流率,(,可能有多个,),。它是单位时间内流入或流出流位的流量。,4.,流程图,图,6.3,常用流程图符号,6.1.4,系统动力学流程,为了进一步明确表示系统各元素之间的数量关系，并建立相应的动力学模型，系统动力学方法通过广义的决策反馈机构来描述上述机制，如图,6.4,所示。,任何决策反馈回路一定要包含两种基本变量。,状态变量（或称为流位变量,Lever,）,决策变量，也称变化率（或称流率变量,Rate,）,决策,系统状态,源或汇（环境）,有关系统,状态,的信息,图,6.4,决策反馈,6.1.5,系统动力学模型方程体系,主要方程包括以下五类：,水平方程,(L,方程,),速率方程,(R,方程,),辅助方程,(A,方程,),常量方程,(C,方程,),初值方程,(N,方程,),6.2,物流系统动力学应用,6.2.1,概述,物流系统动力学就是系统动力学与物流系统科学相结合形成的一门新的交叉学科。,物流系统动力学的基本特点在于它从物流系统复杂的基本构造出发，充分考虑到系统与环境、系统内部各因素间的关系，构造出一种能够比较全面刻画复杂物流系统的模型。这种模型 也被誉为“战略与策略的实验室”。,系统动力学本身亦有其固有的缺陷，需要结合采用多种方法互相补充，互相完善。,6.2.2,物流系统动力学因果分析,1.,由于社会系统的复杂性，以至于无法仅凭借语言和文字对它的行为和结构做准确地描述。,2.,在研究模型中，不仅要准确地描述现实领域，也是合理地描述控制领域。,现实领域,经济水平。,人口水平。,消费水平。,物流系统需求。,物流系统供给等。,控制领域,国民收入分配政策。,人口控制政策。,物流系统政策。,经济发展政策等。,3.,基本因果关系图,6.2.3,物流系统动力学结构方程式。,表,6.1,时间标号表,6.2.4 DYNAMO,仿真计算,图,6.6,一阶正反馈回路流程图,表,6.2,仿真表,图,6.7,仿真结果示意图,图,6.8,一阶负反馈回路流程图,表,6.3,仿真表,图,6.9,仿真结果示图,表,6.4,仿真表,图,6.11,仿真结果示意图,图,6.10,两阶负反馈回路示意图,6.2.5,物流系统动力学模型建模步骤,确定系统的边界，画出因果图。,选择模型的基本变量水准。,以水准为中心构造各自的子系统。,根据因果图，连接各子系统。,根据以上的描述，写出方程式。,进行仿真运算，并做出真实性检验与政策分析。,图,6.12 DYNAMO,仿真程序框图,6.3,区域物流系统动力学模型设计,1.,物流系统的因果关系图,图,6.12,地区物流系统基本因果关系图,图,6.13,基本因果关系环,2.,经济增长子构造,图,6.14,经济增长子构造,3.,物流需求子构造,图,6.15,物流需求子构造,4,、物流供给子构造,图,6.16,物流供给子构造,6.,结果分析,不同的物流发展战略对经济的影响差别显著。,政府必须保证对物流有足够的投入。,要逐步完成物流市场，增强物流企业活动，,要重视物流价格对物流结构的调整作用。,图,6.17,超前发展战略仿真曲线,图,6.18,同步发展战略仿真曲线,图,6.19,滞后发展战略仿真曲线,图,6.20,自我发展仿真曲线,第,7,章 排队模型与存储模型及应用,本章介绍了一些排队系统模型的相关知识，并主要探讨排队模型及仿真在物流系统中的应用问题。,7.1,排队系统模型,7.2,基于排队系统的建模与仿真,7.3,存储论模型及应用,7.4,应用库存模型进行库存规模决策,7.1,排队系统模型,7.1.1,排队系统的特征,顾客总体,系统容量,顾客到达模式,排队特性及规则,服务机构,7.1.2,排队系统模型符号,1.,排队论中常用的记号,n,：系统中的顾客数；,：顾客到达的平均速率，即单位时间内平均到达的顾客数；,：平均服务速率，即单位时间内服务完毕离去的顾客数；,Pn(t),：时刻,t,系统中有,n,个顾客的概率；,c,：服务台的个数；,M,：顾客相继到达的时间间隔服从负指数分布；,D,：顾客相继到达的时间间隔服从定长分布；,Ek,：顾客相继到达的时间间隔服从,k,阶,Erlang,分布。,2.,排队系统的符号表示,一个排队系统的特征可以用六个参数表示，形式为：,A,B,C,：,d,e,f,其中,A,：顾客到达的概率分布，可取,M,、,D,、,Ek,等；,B,：服务时间的概率分布，可取,M,、,D,、,Ek,等；,C,：服务台个数，取正整数；,d,：排队系统的最大容量，可取正整数或,；,e,：顾客源的最大容量，可取正整数或,；,f,：排队规则，可取,FCFS,、,LCFS,等。,7.1.3,顾客到达和服务的时间分布,7.2,基于排队系统的建模与仿真,7.2.1,排队系统的常用模型,2,多服务台模型,M/M/c,图,7.4 M/M/C:/FCFS,排队模型的图示,图,7.5 M/M/c:/m/FCFS,排队模型的图示,7.2.2,物流排队系统仿真应用处理过程,图,7.6,离开事件执行流程,图,7.7,到达事件执行流程,7.3,存储论模型及应用,7.3.1,存储论的基本思想,费用,需求,补充订货或再生产,存储策略,t0,循环策略,(s,，,S),混合策略,(t,，,S,，,S),混合策略,7.3.2,确定型存储控制模型,2.,模型二,:,不允许缺货，生产,(,补充,),需一定时间,设生产,(,补充,),批量为,Q,，所需生产,(,补充,),时间为,T,，则生产速度为,P,=,Q,/,T,。己知需求速度为,R,，,R,P,，生产,(,补充,),的产品一部分满足需求，剩余部分才作为存储，此时存储变化如下,3.,模型三,:,允许缺货,(,缺货祝补足,),，生产时间很短,图,7.10,允许缺货（缺货需补足），,生产时间很短的确定型存储模型,设单位存储费用为,C,，每次订购费为,C3,，缺货费为,C2(,单位缺货损失,),，,R,为需求速度。求最佳存储策略，使平均总费用最小。,假设最