运用图论方法解决不共存货物仓储的简单模型.doc

运用图论方法解决不可共存货物仓储的简单模型 营销070222 顾学松 摘要：仓储是物流行业的重要环节。在实际情况中，常常出现有些货物不能共同存储的现象，这对仓库数量有特殊要求。本文通过对货物不能共存的问题的进行分析，运用图论的知识建立一个图论模型，以完备多边形为纽带，得出能够满足条件的最少仓库数。实例证明，这种方法是可行有效的。 关键词：货物共存；图论；完备多边形 Abstract: The storage is an important link in the logistics industry. In reality, there are often some goods which can not be stored in a same warehouse, which have special requirement on the number of warehouses. This paper analysis this problem, using the knowledge of graph theory to set up a graph theory model ,and the polygon as a link,in the end we can come to the minimum number of warehouses meeting the conditions . Example show that this method is feasible and effective. 仓储是物流活动的重要环节，它的任务是对供应和需求之间在时间上的差异进行调整。仓储成本是整个物流成本的重要组成部分。仓储成本主要是仓库维护费、出入库和库存的操作费、仓库折旧等。仓储成本控制的目标就是要实行货物的合理库存，不断提高保管质量和效率，发挥物流系统的整体功能。所以，优化仓库布局减少库存点，消减不必要的固定费用是仓储保管成本控制应该抓好的主要工作之一。 在社会高度发达的今天，高效的仓储机制不仅可以降低仓储的成本，而且可以提高货物周转率，从而降低整个物流过程的成本，使企业提高经济效益。但是货物在存储过程中，常常会出现这样的情况，某种货物和其他货物不能兼容，即他们不能够共存于同一仓库中，例如:酸性和碱性的货物不能放在一起；易燃易爆物不能和挥发性的物品放在一起，……。那么，在多种货物不能共存的情况下，如何对货物进行仓储，才能在保证货物安全的前提下，使得所需仓库数量最少，最终使仓储成本最少？ 一、引例 某单位存储八种化学药品，其中某些化学药品是不能存放在同一个库房的。为了反映这种情况，用①、②、③、④、⑤、⑥、⑦、⑧分别代表这八种药品。其中药品①不能和②、⑤、⑦、⑧放在同一个库房，药品②不能与①、⑤、⑥、⑧放在同一个库房。药品③不能和④、⑧同放，药品④不能与③、⑤、⑥、⑧一起，药品⑤不能和①、②、④、⑥、⑧，药品⑦不能和①、⑤、⑧，药品⑧不能和①、②、③、④、⑤、⑦放在同一个库房。若某两种药品是不能存放在同一个库房的，则在这两种药品的代号间联一条线（图论中，称这条连线为边，这两个药品代号为这条边的两个端点）。他们的关系如图所示 图一 没有涉及到货物都可以共存在同一仓库。问该站至少要预留几个货物仓库才能够满足货物的安全存储？又如何存放呢？（引例来自《运筹学》176页，北京：清华大学出版社，2005） 根据图所示，我们可以很容易的看出，至少要有四个库房，因为①、②、⑤、⑧必须存放在不同的库房里。事实上，四个库房就足够了。例如，{①}、{②、④、⑦}{③、⑤}，{⑥、⑧}各存放在一个库房。 显然，最少存储仓库数量的存储方式不是唯一的，上例所给的答案只是众多解的一个。另外，由于个量数目较少，使得这个问题比较简单，可以直观的看出答案。但是如果个体数量多达几十种甚至上百种，问题将更加复杂的多。这种情况下，该如何求解？ 图论是运筹学的一个重要分支,旨在解决离散型的优化问题,近年来发展十分迅速。在人们的社会实践中,图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。图论中的“图”,并不是通常意义下的几何图形或物体的形状图,也不是工程设计图中的“图”,而是以一种抽象的形式来表达一些确定的对象,以及这些对象之间具有或不具有某种特定关系的一个数学系统。也就是说,几何图形是表述物体的形状和结构,图论中的“图”则描述一些特定的事物和这些事物之间的联系。它是数学中经常采用的抽象直观思维方法的典型代表。 那么我们是否可以通过图论的方法，解决这个问题呢？ 二、模型建立 我们以运筹学中的图论为工具，找到一个求解的简单方法。我们将上例的图进行反向转化，以图顶点代替货物