物流系统优化与仿真

1、物流系统优化与仿真物流系统优化与仿真 彭扬彭扬 伍蓓伍蓓/著著内容提要内容提要n物流系统优化是实现物流管理目标、体现物流管理效率与效益的必要过程和手段。物流系统优化主要有运筹学方法、智能优化方法和模拟仿真法等三种方法。 n系统仿真是根据被研究的系统模型，利用计算机进行实验研究的方法.目前仿真技术是分析、研究复杂物流系统的重要工具，也成为物流工程技术人员的一项重要技能。 内容提要内容提要n本书即强调优化和仿真的方法学和技术，又立足于物流系统的管理决策问题的解决。n在知识体系上， “横向”方面从传统的运筹规划方法、排队存储论方法、系统动力学方法到现代智能优化方法以及Petri网、多Agent、面向

2、对象等仿真方法的介绍；“纵向”方面主要是物流系统的一些应用问题，如物流网络布局问题、车辆路径问题、装卸搬运问题、区域物流宏观规划问题以及供应链系统设计问题等。目录目录n第第1章章 物流系统优化概述物流系统优化概述 n第第2章章 物流系统模型物流系统模型n第第3章章 物流系统优化的运筹规划方法物流系统优化的运筹规划方法 n第第4章章 物流系统模型的智能优化方法物流系统模型的智能优化方法 n第第5章章 物流系统仿真应用基础物流系统仿真应用基础n第第6章章 物流系统动力学仿真物流系统动力学仿真n第第7章章 排队模型与存储模型及应用排队模型与存储模型及应用n第第8章章 Petri网模型及仿真网模型及仿

3、真n第第9章章 物流系统仿真方法的发展物流系统仿真方法的发展n第第10章章 供应链系统仿真优化供应链系统仿真优化n第第11章章 博弈论及其在供应链中的应用博弈论及其在供应链中的应用n第第12章章 仿真工具与软件应用仿真工具与软件应用第第1章章 物流系统优化概述物流系统优化概述 n本章概述了物流系统优化的相关概念，并就物流优化的主要方法进行了综合性的介绍。n1.1 物流系统物流系统n1.2 物流系统优化问题物流系统优化问题n1.3 物流系统优化的方法物流系统优化的方法1.1 物流系统物流系统 1.1.1 系统及其特征系统及其特征n1我国系统科学界对系统的通用定义是(钱学森): 系统是由相互作用和

4、相互依赖的若干组成部分结合而成的、具有特定功能的有机整体，而且这个整体又是它从属的更大的系统的组成部分。输入、处理（转换）、输出是组成系统的三大要素 .(输入)处理（转换）(输出)(约束和干扰)图图1.1 系统的一般模式系统的一般模式 n整体性 n相关性 n目的性 n环境适应性 2系统的特征系统的特征1.1.2 物流系统的概念和要素物流系统的概念和要素n1物流系统的概念物流系统的概念: 和一般系统一样，具有输入、转换、输出三要素。通过输入和输出使系统与社会环境进行交换，使系统和环境相依存 .环境环境 （1)原材料设备 （2) 劳动力 （3）能源 （4）资金 （5）信息等（1）产品位置转移 （2

5、）各种劳务 （3）能源 （4）信息 （5）好的服务 （1）物流设施与设备 （2）物流业务活动 （3）信息处理 （4）管理工作 输入输入 系统转换系统转换 输出输出 环境环境 干扰干扰反馈反馈 图图1.2 物流系统的一般模型物流系统的一般模型 n2物流系统的特点物流系统的特点是一个大跨度系统是一个可分系统是一个动态系统: 是一个复杂系统物流系统运行对象一“物”，遍及全部社会物质资源，资源的大量化和多样化带来了物流的复杂化 是一个多目标函数系统n3物流系统的目标物流系统的目标将货物按照规定的时间、规定的数量送达到目的地 合理配置物流中心，维持适当的库存 实现装卸、保管、包装等物流作业的省力化、效率

6、化 维持合适的物流成本 实现从订货到出货全过程信息的顺畅流动等 n4物流系统的要素物流系统的要素一般要素 功能要素 支撑要素 物质基础要素 n5物流系统中的制约物流系统中的制约关系关系 物流服务和物流成本间的制约关系 ,如图1.3构成物流服务子系统功能之间的约束关系 构成物流成本的各个环节费用之间的关系 各子系统的功能和所耗费用的关系 图图1.3 服务与成本的制约关系服务与成本的制约关系 1.1.3 物流系统化物流系统化n1.物流系统化的目标物流系统化的目标 总体目标 目标体系 n 服务目标 n快速、及时目标 n 节约目标 n规模优化目标 n库存调节目标 n2系统目标关系的协调系统目标关系的协

7、调原则 n层次间的目标发生冲突时，通常要以较低层次的目标服从于较高层次目标的要求为前提协商解决。 n于同一层次上的目标发生冲突时，应该在分析的基础上确定一定的取舍和补偿标准进行协调与决策 。 3. 物流系统设计要素物流系统设计要素nProducts nQuantity nRoute nService nTime nCost 1.2 物流系统优化问题物流系统优化问题 1.2.1 物流系统的效益目标物流系统的效益目标n物流的宏观经济效益是指物流系统的建立对社会经济效益的影响，直接表现为物流对整个社会流通及全部国民经济效益的影响。 n物流系统的微观经济效益是指该系统本身在运行后所获得的效益。其直接表

8、现形式是物流系统本身所耗与所得之比。 1.2.2 物流系统优化的必要性物流系统优化的必要性n1要素目标冲突要素目标冲突要素之间的目标冲突 要素内部的目标冲突 物流系统与其它系统的目标冲突 n2要素产权冲突要素产权冲突物流系统是由不同产权组织共同完成的，产权边界不清晰。必须克服这种产权的分散性与物流系统的统一性之间的矛盾。 n3要素运作冲突要素运作冲突 1.2.3 系统优化设计系统优化设计n1. 优化设计的概念优化设计的概念实现问题的优化必须具备两个条件：一是存在一个优化目标；另一是具有多个方案可供选择。 n2优化设计的数学模型优化设计的数学模型优化设计三要素 n设计变量 n目标函数 n设计约束

9、与可行域 n3优化方法的分类优化方法的分类有多种类型，有不同的分类方法 n4优化设计步骤优化设计步骤1.设计对象的分析 2.设计变量和设计约束条件的确定 3.目标函数的建立 4.合适的优化算法的选择 5.优化结果分析 1.2.4 物流系统优化的原则物流系统优化的原则n美货运计划解决方案供应商Velant公司的总裁和Don Ratliff博士在2002年美国物流管理协会（CLM）年会上提出了“物流优化的10项基本原则，并认为通过物流决策和运营过程的优化，企业可以获得降低物流成本10%-40%的商业机会。n物流优化的物流优化的10项基本原则项基本原则目标（Objectives）：设定的目标必须是定

10、量的和可测评的。 模型（Models）：模型必须忠实地反映实际的物流过程。 数据（Data）：数据必须准确、及时和全面。 集成（Integration）：系统集成必须全面支持数据的自动传递。 表述（Delivery）：系统优化方案必须以一种便于执行、管理和控制的形式来表述。 算法（Algorithms）：算法必须灵活地利用独特的问题结构。 计算（Computing）：计算平台必须具有足够的容量在可接受的时间段内给出优化方案。 人员（People）：负责物流系统优化的人员必须具备支持建模、数据收集和优化方案所需的领导和技术专长。 过程（Process）：商务过程必须支持优化并具有持续的改进能力。

11、回报（ROI）：投资回报必须是可以证实的，必须考虑技术、人员和操作的总成本。n要证实物流系统优化的投资回报率，必须把握两件事情： 诚实地估计全部的优化成本 将优化技术给出的解决方案逐条与标杆替代方案进行比较 n要确定物流优化技术系统的使用效果，必须做三件事 在实施优化方案之前根据关键绩效指标（Key Performance Indicators）测定基准状态 将实施物流优化技术解决方案以后的结果与基准状态进行比较 对物流优化技术系统的绩效进行定期的评审 1.2.5 物流系统优化的层次物流系统优化的层次n可以依照以下几个层次 决策层 中间层 执行层 1.3 物流系统优化的方法物流系统优化的方法n

12、物流系统优化方法主要有运筹学方法智能优化方法模拟仿真法1.3.1 运筹学方法运筹学方法n1线性规划n一般线性规划模型的表达形式 n线性规划的求解 线性规划可能是非可行的 可能只有无界的解 在大多数情况下，线性规划至少有一个有限的最优解，有时它还会有多重的最优解。 n整数规划 n非线性规划 n线性规划的性质 对于现实生活中的问题必须把其中基本部分抽出来构成数学模型研究解的结构和系统化的求解程序 产生了所期望的系统的最优解，或者至少是得到了通过对客观需要的评价，经过比较的行动方针 n2网络与图论法n3库存论n4排队论1.3.2 智能优化方法智能优化方法n1智能优化算法的概念智能优化算法的概念n优点

13、 n与精确算法相比的明显优势在于:能显著的节省时间开支；灵活，在不能用定量表示的约束集合中，用它制订计划；比较简单，常能由缺乏高级训练的实践者来实现； n3、几种常用的智能优化技术、几种常用的智能优化技术1.3.3 模拟仿真法模拟仿真法n1仿真模型仿真模型系统仿真的目的在于利用人为控制的环境条件，改变某些特定的参数，观察模型的反应，研究真实系统的现象或过程，是一种间接的研究方法。 n优势 符合人们的思维习惯，有助于系统分析 系统仿真可以是一种非解析的分析方法，对各种复杂的系统具有很好的适应性系统仿真有利于解决随机因素的影响 系统仿真可以帮助系统优化 n不单纯追求最优解，而寻求改善系统行为的途径

14、和方法 。系统仿真方法正是提供了这种环境。 利用仿真模型进行系统分析 利用仿真模型进行系统的综合结构的几何性质力的相互作用构件特性尺寸、强度、形状输入变量荷载、风力、流量、地震等桥模型反馈构件的应力、就变等输出系统响应决定下一组输入变量值图图1.4 用仿真进行系统分析用仿真进行系统分析 结构的几何性质力的相互作用构件特性尺寸、强度、形状输入变量荷载、风力、流量、地震等桥模型反馈构件的应力、就变等输出系统响应改变系统单元的性质图图1.5 用仿真进行系统综合用仿真进行系统综合 n3系统仿真在物流系统研究中的作用系统仿真在物流系统研究中的作用物流系统规划与设计 仓储规模与库存管理 物料运输调度 物流

15、成本估算1.3.4 物流系统优化方法的比较物流系统优化方法的比较n运筹学方法和智能优化方法可以统称为解析法。n1解析法的优势解析法是建立在数学模型的基础上的 。数学模型是定量化的，可以产生更高的精确度 。模拟仿真活动有时要耗费大量的时间和物资，花费高昂的代价才能够取得成果；而某些物流系统活动则不能或者很难做仿真实验 。n2仿真方法的优势动态的、瞬时的影响 随机因素 非标准分布 随机活动的交互作用 第第2章章 物流系统模型物流系统模型n本章首先概述了几类主要的模型及其特点，并对常用的物流系统建模技术进行讨论。 n2.1 模型概述模型概述 n2.2 物流系统模型物流系统模型n2.3 建模方法与步骤

16、建模方法与步骤n2.4 物流系统建模技术物流系统建模技术2.1 模型概述模型概述n2.1.1 模型的分类模型的分类n1.实体模型n2.图形模型流程图 方框图 结构图 流图 n3.数学模型数学模型广义 ：凡是一切数学概念、数学理论体系、各种数学公式、各种方程式以及由公式系列构成的算法系统等都被称为数学模型。 狭义 ：凡是将具体现象、事物的特征和性质给以数学表达的数学结构，如各种等式、不等式、图、表或框图等，也叫数学模型。数学模型，包括原始系统数学模型和仿真系统数学模型。仿真系统数学建模过程称为二次建模过程。 n 模拟模型 模拟模型和原系统的物理元素完全不同，但动作相似。2.1.2 数学模型的意义

17、数学模型的意义2.1.4 系统模型模拟的特殊作用系统模型模拟的特殊作用n过程系统流程复杂、投资巨大、生产连续性强，一般不允许在真实系统上进行试验研究。n计划中或设计中的过程系统尚不存在。 n高质量的模拟模型具有预测性。 n实际过程系统根本不允许作的试验。 n大大节省原材料、能源消耗和人力资源等。n模型的预测性。 n传递复制极为方便。 2.2 物流系统模型物流系统模型 2.2.1 物流系统模拟技术的应用物流系统模拟技术的应用n1.物流系统规划与设计n2.物料控制n3.物料运输调度n4.物流成本估算2.2.2 物流系统模型的特点物流系统模型的特点n1. 三个特征： 是实体的抽象或模仿 是由与分析问

18、题有关的因素所组成 是用来表明这些因素间的关系 n主要参数 ：周期数、库存量 、初始库存 、库存价格 、库存成本 、进(出)货量 2.2.3 物流系统常用的数学模型物流系统常用的数学模型n1.资源分配型n2.存储型n3.输送型n4.等待服务型n5.指配型n6.决策型n7.其他模型2.2.4 物流模型构建的原则物流模型构建的原则n1模型构造的系统化n2物流模型简单化n3物流研究多方位化n4物流模型构建的规范化2.3 建模方法与步骤建模方法与步骤 2.3.1 系统建模方法系统建模方法n U代表目标值，一般希望达到最大值(如利润、效益等)或最小值(如成本、支付、亏损等)，加上约束条件就形成一个系统模

19、型。 n模型思路n1.直接分析法直接分析法 例2.1 流通加工中的下料问题。试求面积为一定值的矩形中，周长和为最小时的各边长度。 n2.数据分析法数据分析法 通过分析系统功能的已有数据或新做的试验所获取的数据可以建立系统的模型。 ),(iiYXfU n3.实验分析法实验分析法n例2.2 销售量 广告费 销售量 广告费 销售量 广告费 n4.主观想象法n5.人工实现法2.3.2 物流系统模型建立步骤物流系统模型建立步骤n弄清问题，掌握真实情况 n搜集资料 n确定因素之间的关系 n构造模型n求解模型 n检验模型的正确性 2.3.3 系统模拟遵循的总体工作流程系统模拟遵循的总体工作流程n系统定义 n

20、数学建模 n模拟建模 n装载 n试验 n 结果分析 图图2.4 系统模拟的工作流程系统模拟的工作流程 2.3.4 物流系统建模应注意的几个问题物流系统建模应注意的几个问题n1.对研究对象的了解对研究对象的了解 经常遇到以下情况 片面性、偏离了实际 无法获得完备的、有关过程系统的数据源 数学方法不正确 建模效率低 n2.对于模型构建者提出的要求对于模型构建者提出的要求面向实际 具备跨学科多专业的知识及扎实的数学功底 意志 、善于合作 注意外部环境 n3物流系统建模应注意的问题物流系统建模应注意的问题明确目的，确定构成要素 模型的简单化和高精度模型 没有固定不变的建模方法2.4 物流系统建模技术物

21、流系统建模技术 2.4.1 形式化建模与非形式化建模技术形式化建模与非形式化建模技术n1. 形式化建模技术形式化建模技术排队网络法、极大代数法 、扰动分析法 n2. 非形式化建模技术非形式化建模技术活动循环图、流程图法、面向对象的建模技术n3. Petri网络物流系统模型网络物流系统模型图图2.5 Petri网网示意图示意图 n4.系统动力学建模技术系统动力学建模技术动力学系统涵义n组成部分的子结构及其相互间的关系 n系统内部的反馈回路结构及其相互作用 n5.Agent与与Multi-Agent模型应用模型应用Agent与多Agent系统 Agent的特征n自治n智能n交互 基于Agent的建

22、模思想 n无论在现在还是在将来的计算机科学及其应用领域中，由Agent组成的RAS有能力扮演重要的角色 。n在建立和分析人类社会中的交互模型和理论方面，MAS也可以扮演重要的角色 。在物流供应链系统建模中的应用 第第3章章 物流系统优化的运筹规划方法物流系统优化的运筹规划方法n本章将就物流系统中常见的规划模型形式及求解方法进行研究，并以一个物流网络布局问题的建模与求解作为实例说明该方法的一般应用过程。 n3.1 概述概述n3.2 求解方法求解方法n3.3 物流网络布局问题的建模与求解物流网络布局问题的建模与求解3.1 概述概述 3.1.1 物流系统数学模型构建和模拟物流系统数学模型构建和模拟过

23、程过程3.1.2 运筹学规划论模型运筹学规划论模型n1.线性规划模型线性规划模型基本结构 n决策变量 n约束条件 n决策目标 n标准型的特点 目标函数是最大化类型 约束条件均由等式组成 决策变量均为非负 n模型隐含的假设 比例性假定 可加性假定 连续性假定 确定性假定 图图3.2 LP问题的解之间的关系图问题的解之间的关系图 nLP问题的解的概念 可行解和最优解基、退化解 、最优基可行解基本解基可行解n建立线性规划模型的基本步骤 明确管理问题，确定决策目标，分析约束因素 建立包含一组线性约束条件等式或不等式和最优线性目标函数表达式的数学模型 数学模型的求解与检验 优化后的分析 n整数规划 纯整

24、数规划 混合整数规划 纯01整数规划 混合01整数规划n2非线性规划模型非线性规划模型 特征n每个问题都可用一组决策变量(x1，x2，xn)表示某一方案 n存在一组线性等式或不等式的约束条件 n目标函数 3.1.3 几个物流系统数学模型的例子几个物流系统数学模型的例子n1.运输问题的数学模型n2. 物流配送计划的制定问题物流配送计划的制定问题n3. 集装箱拼箱及装箱问题集装箱拼箱及装箱问题n4. 物流网络布局问题的数学模型物流网络布局问题的数学模型3.2 求解方法求解方法 3.2.1 单目标优化问题求解算法单目标优化问题求解算法n1无约束优化问题的牛顿法及其修正方法无约束优化问题的牛顿法及其修

25、正方法牛顿法牛顿法 阻尼牛顿法 n2拉格朗日乘子法拉格朗日乘子法n拉格朗日乘子法求约束优化问题的计算步骤如下 n3单纯形法单纯形法基本思想 n单纯形法是描述可行解从可行域的一个极点沿着可行域的边界移到另一个相邻的极点时，目标函数和基变量随之变化的方法。 步骤 图图3.3 单纯形法的求解过程单纯形法的求解过程 n4非线性规划及求解非线性规划及求解n乘子法乘子法3.2.2 多目标函数的优化方法多目标函数的优化方法n1统一目标法统一目标法n极小化“统一目标函数”，为了使各个目标函数能均匀一致地趋向各自的最优值，可采用的方法 n2主要目标法主要目标法3.2.3 整数规划及求解整数规划及求解n1割平面法

26、n2分枝定界法分枝定界法n3求解求解0-1规划的隐枚举法规划的隐枚举法隐枚举法的基本原理与步骤隐枚举法的基本原理与步骤 n4求解指派问题的匈牙利法求解指派问题的匈牙利法3.2.4 动态规划法动态规划法n1动态规划的基本概念动态规划的基本概念n2动态规划模型的构成动态规划模型的构成n3基本原理和基本方程基本原理和基本方程3.2.5 图与网络优化算法图与网络优化算法n1、求最小生成树的、求最小生成树的Kruskal算法算法 n2、求最短路径的、求最短路径的Dijkstra算法算法：n3. 求二部图最大匹配（指派问题）的匈牙求二部图最大匹配（指派问题）的匈牙利算法：利算法： n最大流问题就是找出给定

27、流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。 增广链 截集（割集） 最大流最小截量定理 n4求最大流的方法求最大流的方法(Ford-Fulkerson标号法标号法)n5.贪心法与拟阵贪心法与拟阵 n贪心法的思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 n该算法存在问题： 不能保证求得的最后解是最佳的； 不能用来求最大或最小解问题； 只能求满足某些约束条件的可行解的范围。n实现该算法的基本思路是：从问题的某一初始解出发，重复判断如果能朝给定总目标前进一步，则求出可行解的一个解元素，直到由所有解元

28、素组合成问题的一个可行解为止。 n组合算法：提前判断出某些情况不可能取到最优解。3.3 物流网络布局问题的建模与求解物流网络布局问题的建模与求解 3.3.1 概述概述n1.物流网络布局问题的意义与主要内容物流网络布局问题的意义与主要内容n 2. 物流网络规划的步骤物流网络规划的步骤找出物流网络规划的约束条件 根据约束条件构造物流网络符合的模型 将物流网络符合的模型转化成数学模型求出多组可行解 利用可行的评估方法或准则，对以上求出的多组可行解进行评估，将各可行解进行排序，以选取最适合的规划方案 n3. 选址问题的一个简单实例选址问题的一个简单实例3.3.2 多元网点布局问题多元网点布局问题n1问

29、题描述问题描述n多元网点布局问题通常有如图3-5所示的系统结构。图中有m个资源点Ai(i=1，2，m)，各点的资源量为；有个需求点，各点的需求量为；有个可能设置网点的备选地址；需求点可以从设置的网点中转进货，也可以从资源点直接进货。假定各备选地址设置网点的基建投资、仓储费用和运费率均为已知，以总成本最低为目标确定网点布局的最佳方案。 A1 Am D1 Dq B1 Bj Bn 资源厂 网点 用户 图图3-5网点布局结构示意图网点布局结构示意图n2多元单品种物流网点布局的建模方法多元单品种物流网点布局的建模方法n3多元多品种物流网点布局的建模方法多元多品种物流网点布局的建模方法3.3.3 设施容量

30、问题（设施容量问题（CFLP法）法）nCELP法的基本思想是：法的基本思想是： 首先假定网点布局方案已经确定，即给出一组初始网点设置地址。根据初始方案按运输规划模型求出各初始网点的供货范围，然后在各供货范围内分别移定网点到其他备选地址上，以使各供货范围内的总成本下降，找到各供货范围内总成本最小的新网点设置地址，再将新网点设置地址代替初始方案，重复上述过程直至各供货范围内总成本不能再下降时为止。以图以图3-6所示的物流网络结构为对象来介绍所示的物流网络结构为对象来介绍CFLP方方法的处理过程法的处理过程 nCFLP 法的基本步骤 给出网点地址初始方案 确定各网点的供货范围 寻求网点地址的新方案

31、新旧方案对比 D2 D1 B1 Bj Bn 用 户 备 选 网 点 图图3-6网络结构图网络结构图 数例：在某计划区域内，物流网络结构如图3-6所示，其中有12个需求点，“”中的数字为各点需求量，弧线旁的数字为运价系数。现需要在12个需求点的位置上选取3个点作为网点设置地址。假定网点的最大规模为13，设定每个网点的固定成本为10。 2 12 5 2 4 3 2 11 2 3 3 10 4 2 5 1 9 4 7 3 6 4 8 5 5 5 5 6 6 6 9 4 4 4 4 4 3 3 3 2 1 图图3-7物流网络结构图物流网络结构图 步骤步骤22 以4，6，9为发货点，各点发货量均为13；

32、以需求点为收货点，需求量为已知；收、发货点之间的费用系数用最短路线法求得构成运输规划模型，如表3-1所示。 表表3-1运输运输模型模型步骤步骤3 寻找各子区域内使区域总费用最小的网点位置。表表 3-2初始方案初始方案 上面讨论的是网点数目有限的情况，如果网点数目没有限制，则只需对网点数目为1，2，3，12诸情况分别进行讨论，找出使系统总费用最低的网点数目作为最佳方案即可。第第4章章 物流系统模型的智能优化方法物流系统模型的智能优化方法n本章介绍常见的一些智能优化方法及其在物流系统中的应用。n4.1 智能优化方法概述智能优化方法概述 n4.2 人工神经网络人工神经网络 n4.3 禁忌搜索禁忌搜索

33、 n4.4 遗传算法遗传算法 n4.5 模拟退火算法模拟退火算法 n4.6 群体智能方法群体智能方法 n4.7 车辆路径问题模型及求解车辆路径问题模型及求解 4.1 智能优化方法概述智能优化方法概述 4.1.1 优化算法及其分类优化算法及其分类 n目前工程中常用的优化算法目前工程中常用的优化算法 经典算法 构造型算法 邻域搜索算法 n局部搜索法 n指导性搜索法 基于系统动态演化的方法 混合型算法 4.1.2 智能优化算法的概念智能优化算法的概念n智能优化算法的基本概念智能优化算法的基本概念搜索空间（Search Space） 计算复杂性与NP难题(NP-hard) n按照计算复杂性理沦研究问题

34、求解的难易程度，可把问题分为P类、NP类和NP完全类 。其性质如下：1、这类问题中任何一个问题至今未找到多项式时间算法 。2、如果这类问题中存在一个问题有多项式时间算法，那么这类问题都有多项式时间算法。 4.2 人工神经网络人工神经网络 4.2.1 人工神经网络概述人工神经网络概述 n神经元及其特性神经元及其特性 人工神经网络的基本特性和结构人工神经网络的基本特性和结构 x1x2xnV1V2Vnx1x2xn输入输出图图4.34.3递归（反馈）网络递归（反馈）网络x1x2xnw1m输入层隐层图图4.44.4前馈（多层）网络前馈（多层）网络w11y1yn输出层人工神经网络的简单原理人工神经网络的简

35、单原理 人工神经网络是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。 4.2.2 人工神经网络的数学模型及应人工神经网络的数学模型及应用用n1. BP神经网络的数学模型神经网络的数学模型2.BP算法的实现步骤算法的实现步骤3神经网络模型的运行神经网络模型的运行n神经网络的运

36、行包括两个阶段：训练或学习阶段（training or learning phase）。 预测（应用）阶段（generalization phase）。 4.3 禁忌搜索禁忌搜索 4.3.1 禁忌搜索算法的主要构成禁忌搜索算法的主要构成n1、初始解、初始解 n2、邻域移动、邻域移动 n3、禁忌表和禁忌移动、禁忌表和禁忌移动 n4、选择策略、选择策略 n5、破禁策略、破禁策略 两个准则： 基于适值是准则：若某个禁忌侯选解的适值优于以往搜索最优解，则解禁此候选解为当前解；基于搜索方向的准则：按有效的搜索途径进行。 n6、禁忌频数、禁忌频数 n7、停止规则、停止规则 给定最大迭代步数：给定最大迭代步

37、数：当总迭代次数达到一个给定的最大迭代步数，或在一个给定的连续迭代步数内当前的最好解没有改善时，则算法终止。 禁忌频率数控制原则：禁忌频率数控制原则：达到一定禁忌频数要求时，即当不能使当前最好解改善的循环次数超过了预先设定的阈值时，则算法终止； 目标值变化控制原则：目标值变化控制原则：当目标值偏离最优值的程度超过了预先设定的阈值时，则算法终止。 目标值偏离程度原则：目标值偏离程度原则：当目标值偏离最优值的程度超过了预先设定的阈值时，则算法终止。 4.3.2 禁忌搜索算法流程禁忌搜索算法流程主要步骤如下：主要步骤如下： n给定算法参数，随机产生初始解，置禁忌表为空；n设当前解Xcurrent=X

38、int ，当前最好解Xbest=Xint ； n判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继 续以下步骤。Xint的邻域内产生Ns个测试解Xi， 1iNs； 求出目标函数f(Xi)；判断测试解是否在禁忌表中，若不在禁忌表或在禁忌表中但在其目标函数值比Xbest还好，则把它作为新的当前解Xcurrent，并转到；否则，继续测试下一个测试解。若所有的测试解都在禁忌表中，则转到；Xbest=Xcurrent；若禁忌表已满，则按先进先出的原则更新禁忌表；把当前解Xcurrent 插入禁忌表；n记下最优解Xbest ，结束算法。4.4 遗传算法遗传算法 4.4.1 进化计算与遗传算

39、法概述进化计算与遗传算法概述n进化算法进化算法（Evolutionary Computation）是指一类以达尔文进化论为依据来设计、控制和优化人工系统的技术和方法的总称，包括遗传算法（genetic algorithm）、进化策略（evolutionary strategy）和进化规划（evolutionary programming）。 n遗传算法遗传算法中处理的是染色体，或者叫基因型个体。一定数量的个体组成丁群体(population)。群体中个体的数目称为群体规模(population size)。而各个体对环境的适 应程度叫作适应度(fitness)。 两个必要的数据转换操作，一个是

40、表现型到基因型的转换，另一个是基因型到表现型的转换。 主要特点 直接对结构对象进行操作，不存在求导和函数连续性的限定； 具有内在的隐并行性和较好的全局寻优能力； 采用概率化的寻优方法 4.4.2 基本遗传算法基本遗传算法n1. 染色体编码方法染色体编码方法 n2. 适应度函数适应度函数 n3. 遗传算子遗传算子 选择算子：交叉算子 变异算子 n4.基本遗传算法的运行参数基本遗传算法的运行参数 N：群体大小，即群体中所含个体的数量，一般取20100；T：遗传算法的终止进化代数，一般取为100500 Pc：交叉概率，一般取为0.40.99 Pm：变异概率，一般取为0.000l0.1 4.4.3 基

41、本遗传算法的一般框架基本遗传算法的一般框架n问题求解的过程问题求解的过程 编码 初始群体的生成 适应性值评估检测 选择 交叉 变异 n基本遗传算法可定义为一个八元组： SGA(C，E，P0，M，T)n式中各元素的意义为：C个体的编码方法；E个体适应度评价函数；P0初始群体；M群体大小；选择算子；交叉算子；变异算子；T 遗传运算终止条件。GEN0计算群体中每个个体的适应值随机创建初始群体概率地选择遗传操作是否满足选中标准i0iM完成杂交GENGEN1根据适应值选择两个个体根据适应值选择一个个体根据适应值选择一个个体i=i+1完成变异完成繁殖把新的孩子加入到群体中把变异后个体加入到群体中把变异后个

42、体加入到群体中把新的两个孩子加入到群体中i=i+1指定结果结果YYNN其中：变量GEN是当前进化代数：N是群体规模；M是算法执行的最大次数图图4.4基本遗传算法流程图基本遗传算法流程图4.4.4 遗传算法的应用遗传算法的应用n1. 遗传算法的应用步骤遗传算法的应用步骤 确定决策变量及其各种约束条件，即确定个体的表现型和问题的解空间。建立优化模型，即确定出目标函数的类型及其数学描述形式或量化方法。 确定表示可行解的染色体编码方法，也即确定出个体的基因型及遗传算法的搜索空间。 确定解码方法，即确定出由个体基因型到个体表现型的对应关系或转换方法。确定个体适应度的量化评价方法，即确定由目标函数值f(X

43、)到个体适应度F(X)的转换规则。设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。确定遗传算法的有关运行参数，即确定出遗传算法的群体规模popSize，终止进化代数maxGen，交叉概率pc和变异概率pm。 n2.遗传算法的特点遗传算法的特点优点遗传算法可以直接根据目标函数值进行搜索，而无需其它信息，如导数信息；遗传算法同时使用多个搜索点的搜索信息，隐含并行搜索特性； 遗传算法使用概率搜索特性，其选择、交叉和变异等运算都是以一种概率的方式来进行的，增加了其搜索过程的灵活性； 遗传算法具有全局搜索能力，善于搜索复杂问题和非线性问题； 遗传算法同求解问题的其它启发式算法

44、有较好的兼容性，可以与其它优化算法进行结合，改进算法性能。 如模拟退火遗传算法。 缺点 编码不规范及编码存在表示的不准确性。单一的遗传算法编码不能全面地将优化问题的约束表示出来。 易于陷入局部最优点，导致早熟。 4.5 模拟退火算法 4.5.1 模拟退火算法的模型 n1.基本思想基本思想 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L 。对k=1，L做第(3)至第6步 。产生新解S。计算增量t=C(S)-C(S)，其中C(S)为评价函数 。若t0，然后转第2步。 n2. 模拟退火算法新解的产生和接受可分为如下四模拟退火算法新解的产生和接受可分为如下四个步

45、骤个步骤 由一个产生函数从当前解产生一个位于解空间的新解。计算与新解所对应的目标函数差。 断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是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 因

46、果链因果链 n当这种关系从某一变量出发经过一个闭合回路的传递，最后导致该变量本身的增加，这样的回路就称为正反馈环，反之则称为负反馈环。 n实际的复杂社会系统都是由许多相互联系的非线性反馈回路组成。 n实际的复杂社会系统都是由许多相互联系的非线性反馈回路组成。 n系统动力学了解系统动态特性的主要方法是回路分析法（即因果关系和反馈思想）。n反馈分为正反馈与负反馈，一般原则是：若反馈回路包含偶数个负的因果链，则其极性为正，叫正反馈回路；若反馈回路包含奇数个负的因果链，则其极性为负，叫负反馈回路。 图图6.2 因果反馈回路（环）因果反馈回路（环） 3.流位与流率流位与流率n每一个反馈环中至少包含着两种

47、基本的变量即流位与流率。 流位是系统内流量的积累，它是系统的状态变量。 流率从物理概念上将流位变化定量化，根据对流位的关系分成入流率和出流率(可能有多个)。它是单位时间内流入或流出流位的流量。 4. 流程图流程图图图6.3 常用流程图符号常用流程图符号 6.1.4 系统动力学流程系统动力学流程n为了进一步明确表示系统各元素之间的数量关系，并建立相应的动力学模型，系统动力学方法通过广义的决策反馈机构来描述上述机制，如图6.4所示。n任何决策反馈回路一定要包含两种基本变量 。状态变量（或称为流位变量Lever） 决策变量，也称变化率（或称流率变量Rate） 决策决策系统状态系统状态源或汇（环境）源

48、或汇（环境）有 关 系有 关 系统统 状态状态 的信息的信息图图 6.4 决策反馈决策反馈6.1.5 系统动力学模型方程体系系统动力学模型方程体系n主要方程包括以下五类：主要方程包括以下五类：1.水平方程(L方程)2.速率方程(R方程) 3.辅助方程(A方程) 4.常量方程(C方程) 5.初值方程(N方程) 6.2 物流系统动力学应用物流系统动力学应用 6.2.1 概述概述1.物流系统动力学就是系统动力学与物流系统科学相结合形成的一门新的交叉学科。2.物流系统动力学的基本特点在于它从物流系统复杂的基本构造出发，充分考虑到系统与环境、系统内部各因素间的关系，构造出一种能够比较全面刻画复杂物流系统

49、的模型 。这种模型 也被誉为“战略与策略的实验室” 。3.系统动力学本身亦有其固有的缺陷，需要结合采用多种方法互相补充，互相完善。 6.2.2 物流系统动力学因果分析物流系统动力学因果分析n1. 由于社会系统的复杂性，以至于无法仅凭借语言和文字对它的行为和结构由于社会系统的复杂性，以至于无法仅凭借语言和文字对它的行为和结构做准确地描述。做准确地描述。 n2.在研究模型中，不仅要准确地描述现实领域，也是合理地描述控制领域。在研究模型中，不仅要准确地描述现实领域，也是合理地描述控制领域。 现实领域经济水平。人口水平。消费水平。物流系统需求。物流系统供给等。 控制领域 国民收入分配政策。 人口控制政

50、策。 物流系统政策。 经济发展政策等。 n3.基本因果关系图基本因果关系图 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 物流系统

51、动力学模型建模步骤物流系统动力学模型建模步骤1.确定系统的边界，画出因果图。 2.选择模型的基本变量水准。 3.以水准为中心构造各自的子系统。 4.根据因果图，连接各子系统。 5.根据以上的描述，写出方程式。 6.进行仿真运算，并做出真实性检验与政策分析。 图图6.12 DYNAMO仿真程序框图仿真程序框图6.3 区域物流系统动力学模型设计区域物流系统动力学模型设计n1.物流系统的因果关系图物流系统的因果关系图图图6.12 地区物流系统基本因果关系图地区物流系统基本因果关系图 图图6.13 基本因果关系环基本因果关系环 2. 经济增长子构造经济增长子构造图图6.14 经济增长子构造经济增长子构

52、造 3. 物流需求子构造物流需求子构造图图6.15 物流需求子构造物流需求子构造4、物流供给子构造 图图6.16 物流供给子构造物流供给子构造6. 结果分析结果分析1.不同的物流发展战略对经济的影响差别显著。 2.政府必须保证对物流有足够的投入。3.要逐步完成物流市场，增强物流企业活动， 4.要重视物流价格对物流结构的调整作用。 图图6.17 超前发展战略仿真曲线超前发展战略仿真曲线 图图6.18 同步发展战略仿真曲线同步发展战略仿真曲线 图图6.19 滞后发展战略仿真曲线滞后发展战略仿真曲线 图图6.20 自我自我发展仿真曲发展仿真曲线线 第第7章章 排队模型与存储模型及应用排队模型与存储模

53、型及应用n本章介绍了一些排队系统模型的相关知识，并主要探讨排队模型及仿真在物流系统中的应用问题。 n7.1排队系统模型排队系统模型 n7.2 基于排队系统的建模与仿真基于排队系统的建模与仿真 n7.3 存储论模型及应用存储论模型及应用 n7.4 应用库存模型进行库存规模决策应用库存模型进行库存规模决策7.1排队系统模型排队系统模型 7.1.1 排队系统的特征排队系统的特征1.顾客总体 2.系统容量 3.顾客到达模式 4.排队特性及规则 5.服务机构 7.1.2 排队系统模型符号排队系统模型符号n1. 排队论中常用的记号排队论中常用的记号n：系统中的顾客数；：顾客到达的平均速率，即单位时间内平均

54、到达的顾客数；：平均服务速率，即单位时间内服务完毕离去的顾客数；Pn(t) ：时刻t系统中有n个顾客的概率；c：服务台的个数；M：顾客相继到达的时间间隔服从负指数分布；D：顾客相继到达的时间间隔服从定长分布；Ek ：顾客相继到达的时间间隔服从k阶Erlang分布。n2. 排队系统的符号表示排队系统的符号表示 n一个排队系统的特征可以用六个参数表示，形式为：ABC：defn其中A：顾客到达的概率分布，可取M、D、Ek等；B：服务时间的概率分布，可取M、D、Ek等；C：服务台个数，取正整数；d：排队系统的最大容量，可取正整数或；e：顾客源的最大容量，可取正整数或；f：排队规则，可取FCFS、LCF

55、S等。 7.1.3 顾客到达和服务的时间分布顾客到达和服务的时间分布7.2 基于排队系统的建模与仿真基于排队系统的建模与仿真 7.2.1 排队系统的常用模型排队系统的常用模型2多服务台模型多服务台模型M/M/c服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列图图7.4 M/M/C:/FCFS排队模型的图示排队模型的图示 顾客到达修理速率发生故障等待修理的机器修理速率修理速率正在修理的机器到达速率 (m-n)修理速率c运行的机器数 m-n图图7.5 M/M/c:/m/FCFS排队模型的图示排队模型的图示 7.2.2 物流排队系统仿真应用处理过物流排队系统仿真应用处理过程程图图 7.6 离开

56、事件执行流程离开事件执行流程图图7.7 到达事件执行流程到达事件执行流程7.3 存储论模型及应用存储论模型及应用7.3.1 存储论的基本思想存储论的基本思想n费用n需求 n补充订货或再生产 n存储策略 t0循环策略 (s， S)混合策略 (t， S， S)混合策略 7.3.2 确定型存储控制模型确定型存储控制模型2. 模型二模型二:不允许缺货，生产不允许缺货，生产(补充补充)需一定时间需一定时间设生产(补充)批量为Q，所需生产(补充)时间为T，则生产速度为P=Q/T。己知需求速度为R， RP ，生产(补充)的产品一部分满足需求，剩余部分才作为存储，此时存储变化如下3. 模型三模型三:允许缺货允

57、许缺货(缺货祝补足缺货祝补足)，生产时间很短生产时间很短图图 7.10 允许缺货（缺货需补足），允许缺货（缺货需补足），生产时间很短的确定型存储模型生产时间很短的确定型存储模型 设单位存储费用为C，每次订购费为C3，缺货费为C2(单位缺货损失)，R为需求速度。求最佳存储策略，使平均总费用最小。 假设最初存储量为S，可以满足t1时间的需求，t1时间的平均存储量为S/2，在(t-t1)时间的存储为零，平均缺货量为R(t-t1)/2。由于s仅能满足t1时间的需求S=Rt1，有t1=S/R。4模型四模型四:允许缺货允许缺货(需补足缺货需补足缺货)，生产需一定时间生产需一定时间图图7.11 允许缺货允许

58、缺货(需补足缺需补足缺)、生产需一定时间的确定型存储模型生产需一定时间的确定型存储模型7.3.3随机型存储控制型模型随机型存储控制型模型n1随机性存储策略随机性存储策略定期订货 定点订货 把定期订货和定点订货综合起来 2. 缺货情况与安全库存量缺货情况与安全库存量7.4 应用库存模型进行库存规模决策应用库存模型进行库存规模决策n1需求的不确定性分析需求的不确定性分析n 需求频率情况 n 需求量标准离差的计算 n不同服务水平所要求的库存规模n2供应随机干扰分析供应随机干扰分析n平均补给完成周期 n标准差 n3需求与供给不确定性的综合需求与供给不确定性的综合.83.12)2(5)54. 2(102

59、222tqQt第八章第八章 Petri网模型及仿真网模型及仿真n本章即对Petri网模型与物流供应链系统的仿真应用进行探讨。 n8.1 Petri网模型基础网模型基础n8.2 Petri网模型在物流中的应用网模型在物流中的应用n8.3面向对象信息系统建模语言面向对象信息系统建模语言UML8.1 Petri网模型基础网模型基础 8.1.1 Petri网模型元素介绍网模型元素介绍 n1Petri网的基本结构元素网的基本结构元素资源 位置 变迁 弧 n2Petri网的活动元素：令牌或托肯网的活动元素：令牌或托肯(token)n3. Petri网的图形表示网的图形表示n4. 变迁实施规则变迁实施规则(

60、firing rule)1.如果一个变迁的所有输入位置(这些位置连接到这个变迁，弧的方向从位置到变迁)至少包含一个标记，那么这个变迁可能实施(相联系的事件可能发生)。2.一个可实施变迁的实施导致从它所有输入位置中都清除一个标记，在它的每一个输出位置(这些位置连接到这个变迁，弧的方向从变迁到位置)中产生一个标记。3.当使用大于1的弧权(weight)时，在变迁每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可实施；这个变迁的实施，要根据相连接的弧权，在它每一个输出位置中产生相应标记个数。4.变迁的实施是一个原子操作，在输入位置中清除标记和在输出位置中产生标记是一个不可分割的完整操作。 8