管梅谷与中国邮递员问题

中国邮递员问题The ChinesePostman

problem运筹学

课程思政专题史新峰西安邮电大学

现代邮政学院演示者2020-01-16

04:51:43--------------------------------------------首先，我们学习绪论部分。2023最新整理收集do

something引言运筹学中国余数定理有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？——《孙子算经》中国邮递员问题一个邮递员每次上班，要走遍他负责送信的所有街道最后回到邮局，问应该怎样走才能使所走的路程为最短？

管梅谷.奇偶点图上作业法[J].数学学报,1960,10:263-266

EdmondsJ.TheChinesepostmanproblem[J].OperationsResearch,1965,13(Supplement):1-73．演示者2020-01-16

04:51:45--------------------------------------------1.孙子算经，中国南北朝数术著作，作者生平和编写年不详，共三卷,是《算经十书》之一。2.管梅谷（1934-

）,上海市人，中共党员，教授，博士生导师。1957年华东师范大学数学系毕业来我校任教，1981年担任“运筹学与控制论”专业博士生导师，1984年12月任山东师范大学校长，1990年9月调往复旦大学工作。3.Edmonds

J，工作于NBS美国国家标准局，后更名为，NIST美国国家标准技术研究院。4.这个名称一致在国外使用，而由于一些原因，直到20世纪70年代，才被国人知晓。主要内

容运筹学一、问题的提出背景二、问题的提出过程三、问题的求解四、问题的扩展五、小结一问题的提出背景运筹学，由于在1959年上半年做过一些数学联系实际的试验，又曾在1959年暑假期间参加过中科院数学所在北京举办的运筹学讲习班。1959年下学期，从华东师大大学数学系刚毕业三年的管梅谷被山东师范学院（现为山东师范大学）委派参加山东省

“大搞线性规划”小组。管梅谷的主要工作包括两个方面：一是讲课去普及线性规划里面基本的方法；二是到各个地方去找，什么地方有问题可以用运筹学方法解决。济南市邮政局经二路邮政支局演示者2020-01-16

04:51:47--------------------------------------------济南市最大的一个邮电支局一问题的提出背景运筹学为什么是去邮局呢？当时在国外有一个数学问题——旅行售货员问题（或称为货郎担问题）。即一个售货员从城市1出发，到城市2，3，…，n去推销货物，最后回到城市1.问应沿着什么样的路线走，才能使走过的路线最短?这个问题邮政局肯定有！邮递员送件不就是拿着信，一家一家去送吗？和售货员不是一样的吗？要跑出去几个点然后回来。邮递员投递线路最短问题。演示者2020-01-16

04:51:49--------------------------------------------济南市最大的一个邮电支局二问题的提出过程运筹学1.深入实际，调查研究所去的邮局按照送信范围被划分成61块（称为61个段），每个段由一位邮递员负责送信。管梅谷跟着邮递员一起骑自行车送信，当时几乎跑遍了所有的这些段，并画出了不少邮递员走的路线。演示者2020-01-16

04:51:50--------------------------------------------济南市最大的一个邮电支局二问题的提出过程运筹学2.比对已有模型，提炼投递特点—般地，邮递员每次要送200-300个邮件（包括信和报刊等），从而面临的是一个n为200-300的旅行售货员问题。设若在一条街道路上从东到西依次排列着1，2，…

，10等10个地方要送信，如果把这一问题归结为旅行售货员问题，那么在考虑各种可能的送法时，（

1，2，…，10）的各种排列都应考虑到．但是事实上，如（1,5,4,7，…）这样的排列是用不到考虑的，邮递员一般或者按1，2，…，10

，10的顺序来送信，或者按10,9,…,1的顺序来送信。二问题的提出过程运筹学2.比对已有模型，提炼投递特点（3）—般地，邮递员应该先看一下这些信的地址，然后把这些地址在地图上标出来，再想想应该怎样送这些信走的路才会最短。但邮递员们实际投递不是这样做的。他们早就记住了一条走遍他负责送信的那个段的投递路线，每次拿到信后，就是按照这些信的地址在他的既定路线上的位置来排序，把在路线上先走到的信排在前面，排好后就可以出去送信了。二问题的提出过程运筹学3.依据投递特点，提出理论问题投递节点数量较多优化计算较难实现。服务对象（研究对象）应从“点”上调整为“线”上。投递节点顺序确定投递路线既定旅行售货员问题模型不适用!二问题的提出过程运筹学3.依据投递特点，提出理论问题问题提出：从邮局出发，走遍他送信的段内所有街道，最后回到邮局的最短的路线。边路线问题点路线问题三问题的求解运筹学如何给这个问题设计一个数学模型？一笔画的游戏：考虑能不能把一个图形用“笔不离纸，不重复的”方式一笔画出来．欧拉在1736年证明的定理：“一个图能从某一个点开始，不重复地一笔画出，并且最后回到起点的充要条件是：图中所有的点都是偶点（即连接该点的边是偶数条）”。三问题的求解运筹学在一个投递段的地图中经常会出现奇点，这时不重复的一笔画出是不可能的。定理2

任何一个图中，奇点个数是偶数演示者2020-01-16

04:51:55--------------------------------------------奇点的个数是偶数个，图论的基本概念中讲过；把图中的奇点两两连接起来，就形成一个无奇点的连通图。三问题的求解运筹学设在一个连通图上有2n个奇点,

而其余点是偶点，现在要在一些边上添上重复边（重复边与原来的边长度相等），以将这些奇点一对一对分别连接起来，使得添边后的连通图没有奇点(

即从奇点出发的添边必须是奇数条,

从偶点出发的添边必须是偶数条),

并且使得添边的总长度为最小。Min

添边总长度最小三问题的求解运筹学如何添边，使添边总长度最小？可行解：n条把所有奇点一对一对分别连起来的链；（有限个添边的集合）。最优解判定定理：一个可行解,为最优解的充要条件是下述两个条件都成立:每条边最多重复一次。每个圈上添边的长度之和不超过圈长的一半。三问题的求解运筹学奇偶点图上作业法步骤：迭代先任意求一个可行解,

然后用最优解判定定理检查它是不是最优解,

如果不是,

就进行调整（添边总长度下降）,直到得到一个最优解为止。三问题的求解运筹学v1v2 5v4v5v6v77154v38142例：337566三问题的求解运筹学例：1v1v2 5v4v5v6v773375661154v381442三问题的求解运筹学例：13v1v2 5v4v5v6v7761154v3814424三问题的求解运筹学例：13v1v2 5v4v5v6v74752618v3414四问题的扩展运筹学Chinese无向图上的中国邮递员问题[1]管梅谷.奇偶点图上作业法[J].数学学报,1960,10:263-266[2]EdmondsJ.TheChinsespostmanproblem[J].OperationsResearch,1965,13(Supplement):1-73．有向图上的中国邮递员问题Edmonds,

J.,

Johnson,

E.,

Matching,

Euler

tours

and

thePostman, MathematicalProgramming,1973,5

:88-124.[2]

Koh,

K.M.,

Teh.

H.H.,

On

directed

postman

problem,

NanyangUniversityJournal.

1974,8:14-26,四问题的扩展运筹学edge

traversing,混合图上的中国邮递员问题Papadirnitriou,C.,OnthecomplexityofJournal

of ACM,1976,23

:544-55Minieka,

E.,TheChinesepostmanproblemformixednetworks.ManagementScience,

1979,25:643-648,Brucker,P.,

Approximation

method for postmanproblem,OperationalResearch’81,Abstracts.p.A90.North-HollandPublishing Company,

Amsterdam, NewYork,Oxford.

1981,四问题的扩展运筹学乡村中国邮递员问题Orloff,C.,Afundamentalprobleminvehiclerouting,Networks.1974,4:35-64.comments, Networks

,[2]Orloff,C.,Ongeneralroutingproblem:1976,6:

281-284.5.带风向的中国邮递员问题Minieka,

E.,TheChinesepostmanproblemformixednetworks.ManagementScience,

1979,25:643-648,五小结运筹学1.如何从点的路线问题转化为线的路线问题？2.奇偶点图上作业法如何产生？不是坐而论道，而是深入实际广泛调研！从基础问题、模型和方法出发，运筹学思维的形成。五小结运筹学对邮递员投递线路的优化实际问题的解决效果？管梅谷用最优性判别定理检查已有的投递路线，发现除了一个段可以做一些