中国邮递员问题_中国邮递员问题的应用

中国邮递员问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“中国邮递员问题的应用”。

运筹学第六组

运筹学个人心得之中国邮递员问题

我们第六组做的第二次案例就是中国邮递员问题，这个问题是运筹学中的经典命题。这个案例讲的是：在中国的六个县城，每个县城都有一个县局，县局下面设立若干个邮政所，每天邮递员的任务就是从县局出发，依次到每一个邮政所送邮件，要求每个邮政所都必须去，而且只能去一次。这就涉及到一个路线的规划问题，怎么走才能使得邮递员走的路最少，而且能够完成任务。

在做题之前考虑了很久，真不知道从何着手，国为以前确实没有接触过这个类型的题，没有一个能够行得通的办法。后来，我们选定了一个代表性的区域，来尝试求解，国为第六个区域的变量最多，所以就选择这个区域作为突破口。只要第六个区域求解成功，其它五个区域便迎刃而解了。

首先，我们画了一个由第六区域的十七个点所组成的17*17矩阵，一一对应设定变量，在去除对角线的17个变量之后，我们得到272个变量。这是一个非常庞大的变量群体，若按传统的线性规划方法求解，求解过程将会变得异常艰辛，而且以前的模板，求解工具都不能求解这么多变量。所以我们一度陷入混乱，求解工作停滞不前。后来老师在对这价目案例作初步的讲解的时候，提出了用运输模型来对这个问题进行求解，此话一出，真是如醍醐灌顶，酣畅极了，眼前简直豁然一亮，真想“拍案而起”。

若用运输模型求解，这个问题将会变得非常简单。一方面由于每行的出发点只能有一个，而每列的终点也只能有一个，这样看来，邮

运筹学第六组

递员总是变成了一个产销平衡的运输问题，产量和销量都有是1。这样我们就完成了求解工作，在第一次求解得出结论后，我们画了一个路线图，发现有几个两点循环，没有形成一条大通路，于是我们重新加入了两点循环约束，进行二次求解；在第二次求解完成后，我们又重新画了路线图，结果发现有四点循环于是我们又加入四点循环约束，进行第三次求解，在得到第三次求解的结果后，我们又画出了路线图，这次刚好形成了一个完整的通路，保证了邮递员每点都走到且行走的路线最合理。

这次案例收获最大的部分，莫过于知识的贯通和灵活运用在求解模型选择上的深刻体现。

企业管理：徐玉飞