物流运筹学与统筹规划教材课件

复习提纲及重点内容复习提纲及重点内容1（一）物流运筹学（一）物流运筹学2第一章物流与运筹学概论1.2物流的概念界定、基本元素及其地位1.3物流运筹学第一章物流与运筹学概论1.2物流的概念界定、基本元素及其3第二章线性规划2.1一般线性规划问题及其数学模型第二章线性规划2.1一般线性规划问题及其数学模型4第三章整数规划3.1整数规划问题的提出3.2整数规划概述3.5匈牙利法与指派问题第三章整数规划3.1整数规划问题的提出5例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少？完成任务所需时间表任务人员ABCD甲215134乙1041415丙9141613丁78119例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、6求解：匈牙利法

第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。

(1)从系数矩阵的每行元素减去该行的最小元素；

(2)再从所得系数矩阵的每列元素中减去该列的最小元素。

若某行(列)已有0元素，那就不必再减了。

例7的计算为

求解：匈牙利法第一步：使指派问题的系数矩阵经变换，在各行7行列都有零元素行列都有零元素8现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到01370606905320100这表明：指定甲完成任务D，乙完成任务B，丙完成任务A，丁完成任务C。所需总时间最少minz=28ABCD甲乙丙丁现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，9第四章物资运输与调运问题4.2物流运输系统规划概述4.3物资调运问题及其模型4.4运输问题的求解方法初始方案的选择（最小元素法和西北角法）解的改进（检验数计算，闭回路法）运量调整第四章物资运输与调运问题4.2物流运输系统规划概述10例4-1调运问题建模（线性规划模型）3个工厂向四个销售地点销售，如表，如何调运成本最小？例4-1调运问题建模（线性规划模型）3个工厂向四个销11供应地约束需求地约束解答供应地约束需求地约束解答12最小元素法123467531113141842722131227155910631919022131213300000000020020最小元素法123467531113141842722131213初始基础可行解—西北角法813131466000000初始基础可行解—西北角法81313146600000014+5非基变量xij的检验数zij-cij—闭回路法(1)σ12=c12-c22+c21-c11=7-4+8-6=5+5非基变量xij的检验数zij-cij—闭回路法(1)σ115+5闭回路法(2)σ13=c13-c23+c21-c11=5-2+8-6=5+5+5闭回路法(2)σ13=c13-c23+c21-c11=516+5闭回路法(3)σ14=c13-c33+c32-c23+c21-c11

=3-6+10-2+8-6=7+7+5+5闭回路法(3)σ14=c13-c33+c32-c217选择进基变量,确定离基变量（运量调整）x31进基,min{x21,x33}=min{8,6}=6,x33离基-3-5-5-7-9-11选择进基变量,确定离基变量（运量调整）x31进基,min{18调整运量后的新运输作业表调整运量后的新运输作业表19第五章运输路径规划5.1图的基本概念最小生成树的物理意义及其求解方法（破圈法、避圈法）5.2最短路问题（Dijkstra算法的步骤及求解）5.3网络最大流问题

（网络流、增广链定义及其物理意义）第五章运输路径规划5.1图的基本概念20Dijkstra算法的步骤：1、给起始点标记固定标号P，标号值记为0，2、考察与（0）相邻的各点，修改其临时标号值，数值为出发点的固定标号值+出发点到该点的权重。不相邻的点，标号值记为∞3、从所有的临时标号里面找出最小的确定为固定标号4、从新得到的固定标号出发，修改其相邻点的临时标号。若原来已有临时标号，则比较原值与修改值的大小，取最小值5、重复3-4，直到所有顶点被标记。最后，根据最小路权，逆推得到最短路径。Dijkstra算法的步骤：1、给起始点标记固定标号P，标号21思考题：下图是某地区交通运输示意图，弧旁数字表示相应两地间的公路里程（公里）。问，从1出发，经过哪条路线到达8，才能使总行程最短。72415366765335138425192思考题：下图是某地区交通运输示意图，弧旁数字表示相应两地22解答：因此，可知最短路为13，逆推回去可知经过的路径为8←7←6←3←1或8←7←6←2←17241536676533513842519203561071116138解答：因此，可知最短路为13，逆推回去可知经过的路径为8←723存在增广链μ：1→2→4→71243576（13，5）（5，3）（9，3）（4，1）（5，2）（5，0）（6，3）（6，2）（4，2）（4，1）（10，1）（9，5）存在增广链μ：1→2→4→3→6→7存在增广链μ：1→2→4→71243576（13，5）（5，24（二）物流系统规划（二）物流系统规划25第一章物流系统及其规划概述1.2物流系统规划与设计基本理论（1.2.1---1.2.3）第一章物流系统及其规划概述1.2物流系统规划与设计基本理26第三章物流节点规划设计3.4区域布置方法图形构建法的算法——节点插入法第三章物流节点规划设计3.4区域布置方法27练习：某物流中心作业区的定量从至图如图所示，用节点插入法完成下面例题的布置物流量到地区域12345起始区域15450247343987042610252402步骤：1.选取具有最大权数的关联作业区对； 2.选取与已进入布置的作业区具有最大权数的作业区，成三角布置； 3.再选择，插入三角区，直至布置完所有的作业区练习：某物流中心作业区的定量从至图如图所示，用节点插入法完成28第四章物流节点选址4.1物流节点选址概述4.1.3规划选择的步骤4.1.4物流节点选址布局方法4.2单物流节点选址（重心法）第四章物流节点选址4.1物流节点选址概述29例2拟建物流中心，有四个原材料供应地，试用重心法求该物流中心的位置求解：原料供应地P1P2P3P4x1y1x2y2x3y3x4y4坐标位置2070606020205020年运输量2000120010002500

20×2000+60×1200+20×1000+50×2500x0=——————————————————————=38.42000+1200+1000+2500

70×2000+60×1200+20×1000+20×2500y0=——————————————————————=42.12000+1200+1000+2500例2拟建物流中心，有四个原材料供应地，试用重心法求该物流中30复习提纲及重点内容复习提纲及重点内容31（一）物流运筹学（一）物流运筹学32第一章物流与运筹学概论1.2物流的概念界定、基本元素及其地位1.3物流运筹学第一章物流与运筹学概论1.2物流的概念界定、基本元素及其33第二章线性规划2.1一般线性规划问题及其数学模型第二章线性规划2.1一般线性规划问题及其数学模型34第三章整数规划3.1整数规划问题的提出3.2整数规划概述3.5匈牙利法与指派问题第三章整数规划3.1整数规划问题的提出35例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少？完成任务所需时间表任务人员ABCD甲215134乙1041415丙9141613丁78119例7：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、36求解：匈牙利法

第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。

(1)从系数矩阵的每行元素减去该行的最小元素；

(2)再从所得系数矩阵的每列元素中减去该列的最小元素。

若某行(列)已有0元素，那就不必再减了。

例7的计算为

求解：匈牙利法第一步：使指派问题的系数矩阵经变换，在各行37行列都有零元素行列都有零元素38现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到01370606905320100这表明：指定甲完成任务D，乙完成任务B，丙完成任务A，丁完成任务C。所需总时间最少minz=28ABCD甲乙丙丁现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，39第四章物资运输与调运问题4.2物流运输系统规划概述4.3物资调运问题及其模型4.4运输问题的求解方法初始方案的选择（最小元素法和西北角法）解的改进（检验数计算，闭回路法）运量调整第四章物资运输与调运问题4.2物流运输系统规划概述40例4-1调运问题建模（线性规划模型）3个工厂向四个销售地点销售，如表，如何调运成本最小？例4-1调运问题建模（线性规划模型）3个工厂向四个销41供应地约束需求地约束解答供应地约束需求地约束解答42最小元素法123467531113141842722131227155910631919022131213300000000020020最小元素法123467531113141842722131243初始基础可行解—西北角法813131466000000初始基础可行解—西北角法81313146600000044+5非基变量xij的检验数zij-cij—闭回路法(1)σ12=c12-c22+c21-c11=7-4+8-6=5+5非基变量xij的检验数zij-cij—闭回路法(1)σ145+5闭回路法(2)σ13=c13-c23+c21-c11=5-2+8-6=5+5+5闭回路法(2)σ13=c13-c23+c21-c11=546+5闭回路法(3)σ14=c13-c33+c32-c23+c21-c11

=3-6+10-2+8-6=7+7+5+5闭回路法(3)σ14=c13-c33+c32-c247选择进基变量,确定离基变量（运量调整）x31进基,min{x21,x33}=min{8,6}=6,x33离基-3-5-5-7-9-11选择进基变量,确定离基变量（运量调整）x31进基,min{48调整运量后的新运输作业表调整运量后的新运输作业表49第五章运输路径规划5.1图的基本概念最小生成树的物理意义及其求解方法（破圈法、避圈法）5.2最短路问题（Dijkstra算法的步骤及求解）5.3网络最大流问题

（网络流、增广链定义及其物理意义）第五章运输路径规划5.1图的基本概念50Dijkstra算法的步骤：1、给起始点标记固定标号P，标号值记为0，2、考察与（0）相邻的各点，修改其临时标号值，数值为出发点的固定标号值+出发点到该点的权重。不相邻的点，标号值记为∞3、从所有的临时标号里面找出最小的确定为固定标号4、从新得到的固定标号出发，修改其相邻点的临时标号。若原来已有临时标号，则比较原值与修改值的大小，取最小值5、重复3-4，直到所有顶点被标记。最后，根据最小路权，逆推得到最短路径。Dijkstra算法的步骤：1、给起始点标记固定标号P，标号51思考题：下图是某地区交通运输示意图，弧旁数字表示相应两地间的公路里程（公里）。问，从1出发，经过哪条路线到达8，才能使总行程最短。72415366765335138425192思考题：下图是某地区交通运输示意图，弧旁数字表示相应两地52解答：因此，可知最短路为13，逆推回去可知经过的路径为8←7←6←3←1或8←7←6←2←17241536676533513842519203561071116138解答：因此，可知最短路为13，逆推回去可知经过的路径为8←753存在增广链μ：1→2→4→71243576（13，5）（5，3）（9，3）（4，1）（5，2）（5，0）（6，3）（6，2）（4，2）（4，1）（10，1）（9，5）存在增广链μ：1→2→4→3→6→7存在增广链μ：1→2→4→71243576（13，5）（5，54（二）物流系统规划（二）物流系统规划55第一章物流系统及其规划概述1.2物流系统规划与设计基本理论（1.2.1---1.2.3）第一章物流系统及其规划概述1.2物流系统规划与设计基本理56第三章物流节点规划设计3.4区域布置方法图形构建法的算法——节点插入法第三章物流节点规划设计3.4区域布置方法57练习：某物流中心作业区的定量从至图如图所示，用节