《物流运筹学与统筹规划77194.pptx》由会员分享，可在线阅读，更多相关《物流运筹学与统筹规划77194.pptx（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、复习提纲及重点内容（一）物流运筹学第一章第一章 物流与运筹学概论物流与运筹学概论n n1.2 物流的概念界定、基本元素及其地物流的概念界定、基本元素及其地位位n n1.3 物流运筹学物流运筹学第二章第二章 线性规划线性规划n n2.12.1一般线性规划问题及其数学模型一般线性规划问题及其数学模型第三章第三章 整数规划整数规划n n3.1 整数规划问题的提出整数规划问题的提出n n3.2 整数规划概述整数规划概述n n3.5 匈牙利法与指派问题匈牙利法与指派问题n n例例例例7 7：某物流公司现有四项运输任务：某物流公司现有四项运输任务：某物流公司现有四项运输任务：某物流公司现有四项运输任务A
2、A、B B、C C、D D，现有甲、乙、丙、丁四辆车，他们完成任务所需时现有甲、乙、丙、丁四辆车，他们完成任务所需时现有甲、乙、丙、丁四辆车，他们完成任务所需时现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需间如表所示。问应指派何人去完成何工作，使所需间如表所示。问应指派何人去完成何工作，使所需间如表所示。问应指派何人去完成何工作，使所需总时间最少？总时间最少？总时间最少？总时间最少？完成任务所需时间表 任务任务人员人员A AB BC CD D甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78
3、 811119 9求解：匈牙利法求解：匈牙利法 第一步：使指派问题的系数矩阵经变换，在第一步：使指派问题的系数矩阵经变换，在第一步：使指派问题的系数矩阵经变换，在第一步：使指派问题的系数矩阵经变换，在各行各列中都出现各行各列中都出现各行各列中都出现各行各列中都出现0 0 0 0元素。元素。元素。元素。(1)(1)(1)(1)从系数矩阵的每行元素减去该行的最小从系数矩阵的每行元素减去该行的最小从系数矩阵的每行元素减去该行的最小从系数矩阵的每行元素减去该行的最小元素；元素；元素；元素；(2)(2)(2)(2)再从所得系数矩阵的每列元素中减去该再从所得系数矩阵的每列元素中减去该再从所得系数矩阵的每列
4、元素中减去该再从所得系数矩阵的每列元素中减去该列的最小元素。列的最小元素。列的最小元素。列的最小元素。若某行若某行若某行若某行(列列列列)已有已有已有已有0 0 0 0元素，那就不必再减了。元素，那就不必再减了。元素，那就不必再减了。元素，那就不必再减了。例例例例7 7 7 7的计算为的计算为的计算为的计算为行列都有行列都有零元素零元素n n现用例现用例现用例现用例7 7 7 7的的的的(b(b(b(bijijijij)矩阵，按上述步骤进行运算。矩阵，按上述步骤进行运算。矩阵，按上述步骤进行运算。矩阵，按上述步骤进行运算。按步骤按步骤按步骤按步骤(1)(1)(1)(1)，先给，先给，先给，先给
5、b b b b22222222加圈，然后给加圈，然后给加圈，然后给加圈，然后给b b b b31313131加圈，加圈，加圈，加圈，划掉划掉划掉划掉b b b b11111111，b b b b41414141；按步骤；按步骤；按步骤；按步骤(2)(2)(2)(2)，给，给，给，给b b b b43434343加圈，划掉加圈，划掉加圈，划掉加圈，划掉b b b b44444444，最后给，最后给，最后给，最后给b b b b14141414加圈，得到加圈，得到加圈，得到加圈，得到 0 13 7 0 0 13 7 0 6 0 6 9 6 0 6 9 0 5 3 2 0 5 3 2 0 1 0 0
6、 0 1 0 0这表明：指定甲完成任务这表明：指定甲完成任务D，乙完成任务，乙完成任务B，丙完成任务，丙完成任务A，丁完成任务，丁完成任务C。所需总时间最少。所需总时间最少 min z=28A B C D甲 乙 丙 丁第四章第四章 物资运输与调运问题n n4.2 物流运输系统规划概述物流运输系统规划概述n n4.3 物资调运问题及其模型物资调运问题及其模型n n4.4 运输问题的求解方法运输问题的求解方法初始方案的选择（最小元素法和西北角法）初始方案的选择（最小元素法和西北角法）初始方案的选择（最小元素法和西北角法）初始方案的选择（最小元素法和西北角法）解的改进（检验数计算，闭回路法）解的改进
7、（检验数计算，闭回路法）解的改进（检验数计算，闭回路法）解的改进（检验数计算，闭回路法）运量调整运量调整运量调整运量调整例例4-1 调运问题建模（线性规划调运问题建模（线性规划模型）模型）3 3个工厂向四个销售地点销售，如表，如何调运成本个工厂向四个销售地点销售，如表，如何调运成本个工厂向四个销售地点销售，如表，如何调运成本个工厂向四个销售地点销售，如表，如何调运成本最小？最小？最小？最小？供应地约束需求地约束解答解答最小元素法12346753111314184272213122715591063191902213121330000000002 0020初始基础可行解初始基础可行解西北角法西北
8、角法813131466000000+5非基变量xij的检验数zij-cij闭回路法(1)12=c12-c22+c21-c11=7-4+8-6=5+5闭回路法(2)13=c13-c23+c21-c11=5-2+8-6=5+5+5闭回路法(3)14=c13-c33+c32-c23+c21-c11 =3-6+10-2+8-6=7+7+5选择进基变量选择进基变量,确定离基变量（运量调整）确定离基变量（运量调整）x31进基进基,minx21,x33=min8,6=6,x33离基离基-3-5-5-7-9-11调整运量后的新运输作业表调整运量后的新运输作业表第五章第五章 运输路径规划运输路径规划n n5.1
9、 图的基本概念图的基本概念最小生成树的物理意义及其求解方法（破最小生成树的物理意义及其求解方法（破最小生成树的物理意义及其求解方法（破最小生成树的物理意义及其求解方法（破圈法、避圈法）圈法、避圈法）圈法、避圈法）圈法、避圈法）n n5.2 最短路问题（最短路问题（Dijkstra算法的步骤算法的步骤及求解）及求解）n n5.3 网络最大流问题网络最大流问题（网络流、增广链（网络流、增广链定义及其物理意义）定义及其物理意义）Dijkstra算法的步骤：算法的步骤：1、给起始点标记固定标号、给起始点标记固定标号P，标号值记，标号值记为为0，2 2、考察与（、考察与（、考察与（、考察与（0 0）相邻
10、的各点，修改其临时标号）相邻的各点，修改其临时标号）相邻的各点，修改其临时标号）相邻的各点，修改其临时标号值，数值为出发点的固定标号值值，数值为出发点的固定标号值值，数值为出发点的固定标号值值，数值为出发点的固定标号值+出发点到出发点到出发点到出发点到该点的权重。不相邻的点，标号值记为该点的权重。不相邻的点，标号值记为该点的权重。不相邻的点，标号值记为该点的权重。不相邻的点，标号值记为3 3、从所有的临时标号里面找出最小的确定为固、从所有的临时标号里面找出最小的确定为固、从所有的临时标号里面找出最小的确定为固、从所有的临时标号里面找出最小的确定为固定标号定标号定标号定标号4 4、从新得到的固定
11、标号出发，修改其相邻点的、从新得到的固定标号出发，修改其相邻点的、从新得到的固定标号出发，修改其相邻点的、从新得到的固定标号出发，修改其相邻点的临时标号。若原来已有临时标号，则比较原临时标号。若原来已有临时标号，则比较原临时标号。若原来已有临时标号，则比较原临时标号。若原来已有临时标号，则比较原值与修改值的大小，取最小值值与修改值的大小，取最小值值与修改值的大小，取最小值值与修改值的大小，取最小值5 5、重复、重复、重复、重复3-43-4，直到所有顶点被标记。，直到所有顶点被标记。，直到所有顶点被标记。，直到所有顶点被标记。最后，根据最小路权，逆推得到最短路径。最后，根据最小路权，逆推得到最短
12、路径。最后，根据最小路权，逆推得到最短路径。最后，根据最小路权，逆推得到最短路径。思考题：思考题：下图是某地区交通运输示意图，弧旁数下图是某地区交通运输示意图，弧旁数字表示相应两地间的公路里程（公里）。字表示相应两地间的公路里程（公里）。问，从问，从1出发，经过哪条路线到达出发，经过哪条路线到达8，才，才能使总行程最短。能使总行程最短。72415366765335138425192解答：解答：因此，可知最短路为因此，可知最短路为因此，可知最短路为因此，可知最短路为1313，逆推回去可知经过的，逆推回去可知经过的，逆推回去可知经过的，逆推回去可知经过的路径为路径为路径为路径为8 87 76 63
13、 31 1或或或或8 87 76 62 21 17241536676533513842519203561071116138存在增广链存在增广链：12471243576（13，5）（5，3）（9，3）（4，1）（5，2）（5，0）（6，3）（6，2）（4，2）（4，1）（10，1）（9，5）存在增广链存在增广链：124367（二）物流系统规划第一章第一章 物流系统及其规划概物流系统及其规划概述述n n1.2 1.2 物流系统规划与设计基本理论物流系统规划与设计基本理论物流系统规划与设计基本理论物流系统规划与设计基本理论（1.2.1-1.2.3 1.2.1-1.2.3）第三章第三章 物流节点规划设
14、计物流节点规划设计n n3.4 区域布置方法区域布置方法图形构建法的算法图形构建法的算法图形构建法的算法图形构建法的算法节点插入法节点插入法节点插入法节点插入法练习：练习：某物流中心作业区的定量从至某物流中心作业区的定量从至图如图所示，用节点插入法完成下面图如图所示，用节点插入法完成下面例题的布置例题的布置物流量物流量物流量物流量到地区域到地区域到地区域到地区域1 12 23 34 45 5起起起起始始始始区区区区域域域域1 15 54 45 50 02 24 47 73 34 43 39 98 87 70 04 42 26 610102 25 52 24 40 02 2步骤：步骤：1.选取具
15、有最大权数的关联作业区对；选取具有最大权数的关联作业区对；2.选取与已进入布置的作业区具有最大权数的作业区，成三角布置；选取与已进入布置的作业区具有最大权数的作业区，成三角布置；3.再选择，插入三角区，直至布置完所有的作业区再选择，插入三角区，直至布置完所有的作业区第四章第四章 物流节点选址物流节点选址n n4.1 物流节点选址概述物流节点选址概述4.1.3 4.1.3 规划选择的步骤规划选择的步骤规划选择的步骤规划选择的步骤4.1.4 4.1.4 物流节点选址布局方法物流节点选址布局方法物流节点选址布局方法物流节点选址布局方法n n4.2 单物流节点选址（重心法）单物流节点选址（重心法）例例
16、2 拟建物流中心，有四个原材拟建物流中心，有四个原材料供应地，试用重心法求该物流料供应地，试用重心法求该物流中心的位置中心的位置求解：求解：原料原料原料原料供应地供应地供应地供应地P1P1P2P2P3P3P4P4x1x1y1y1x2x2y2y2x3x3y3y3x4x4y4y4坐标位置坐标位置坐标位置坐标位置 20207070606060602020202050502020年运输量年运输量年运输量年运输量 20002000120012001000100025002500 202000+601200+201000+502500202000+601200+201000+502500 x0=38.4x0=38.4 2000+1200+1000+2500 2000+1200+1000+2500 702000+601200+201000+202500702000+601200+201000+202500y0=42.1y0=42.1 2000+1200+1000+2500 2000+1200+1000+2500