物流运筹学与统筹规划

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

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

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

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

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

例7的计算为

行列都有零元素现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到01370606905320100这表明：指定甲完成任务D，乙完成任务B，丙完成任务A，丁完成任务C。所需总时间最少minz=28ABCD甲乙丙丁第四章物资运输与调运问题4.2物流运输系统规划概述4.3物资调运问题及其模型4.4运输问题的求解方法初始方案的选择（最小元素法和西北角法）解的改进（检验数计算，闭回路法）运量调整例4-1调运运问题建建模（线线性规划划模型））3个工厂厂向四个个销售地地点销售售，如表表，如何何调运成成本最小小？供应地约约束需求地约约束解答最小元素素法123467531113141842722131227155910631919022131213300000000020020初始基础础可行解解—西北北角法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进基,min{x21,x33}=min{8,6}=6,x33离基-3-5-5-7-9-11调整运量量后的新新运输作作业表第五章运运输路路径规划划5.1图图的基基本概念念最小生成成树的物物理意义义及其求求解方法法（破圈圈法、避避圈法））5.2最最短路路问题（（Dijkstra算算法的步步骤及求求解）5.3网网络最最大流问问题（网络流流、增广广链定义义及其物物理意义义）Dijkstra算法法的步骤骤：1、给起起始点标标记固定定标号P，标号号值记为为0，2、考察察与（0）相邻邻的各点点，修改改其临时时标号值值，数值值为出发发点的固固定标号号值+出出发点到到该点的的权重。。不相邻邻的点，，标号值值记为∞∞3、从所所有的临临时标号号里面找找出最小小的确定定为固定定标号4、从新新得到的的固定标标号出发发，修改改其相邻邻点的临临时标号号。若原原来已有有临时标标号，则则比较原原值与修修改值的的大小，，取最小小值5、重复复3-4，直到到所有顶顶点被标标记。最后，根根据最小小路权，，逆推得得到最短短路径。。思考题：：下图是某某地区交交通运输输示意图图，弧旁旁数字表表示相应应两地间间的公路路里程（（公里））。问，，从1出出发，经经过哪条条路线到到达8，，才能使使总行程程最短。。72415366765335138425192解答：因此，可可知最短短路为13，逆逆推回去去可知经经过的路路径为8←7←←6←3←1或或8←7←6←←2←17241536676533513842519203561071116138存在增广广链μ：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物物流系系统规划划与设计计基本理理论（1.2.1---1.2.3）第三章物物流节节点规划划设计3.4区区域布布置方法法图形构建建法的算算法———节点插插入法练习：某物流中中心作业业区的定定量从至至图如图图所示，，用节点点插入法法完成下下面例题题的布置置物流量到地区域12345起始区域15450247343987042610252402步骤：1.选取具具有最大大权数的的关联作作业区对对；2.选取取与已进进入布置置的作业业区具有有最大权权数的作作业区，，成三角角布置；；3.再选选择，插插入三角角区，直直至布置置完所有有的作业业区第四章物物流节节点选址址4.1物物流节节点选址址概述4.1.3规规划选择择的步骤骤4.1.4物物流节点点选址布布局方法法4.2单单物流流节点选选址（重重心法））例2拟拟建物流流中心，，有四个个原材料料供应地地，试用用重心法法求该物物流中心心的位置置求解：原料供应地P1P2P3P4x1y1x2y2x3y3x4y4坐标位置2070606020205020年运输量200012001000250020×2000+60×1200+20××1000+50×2500x0=———————