运用图论方法解决不可共存货物仓储的简单模型.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）根据图所示，我们可以很容易的看出，至少要有四个库房，因为、必须存放在不同的库房里。事实上，四个库房就足够了。例如，、，、各存放在一个库房。显然，最少存储仓库数量的存储方式不是唯一的，上例所给的答案只是众多解的一个。另外，由于个量数目较少，使得这个问题比较简单，可以直观的看出答案。但是如果个体数量多达几十种甚至上百种，问题将更加复杂的多。这种情况下，该如何求解？图论是运筹学的一个重要分支,旨在解决离散型的优化问题,近年来发展十分迅速。在人们的社会实践中,图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。图论中的“图”,并不是通常意义下的几何图形或物体的形状图,也不是工程设计图中的“图”,而是以一种抽象的形式来表达一些确定的对象,以及这些对象之间具有或不具有某种特定关系的一个数学系统。也就是说,几何图形是表述物体的形状和结构,图论中的“图”则描述一些特定的事物和这些事物之间的联系。它是数学中经常采用的抽象直观思维方法的典型代表。那么我们是否可以通过图论的方法，解决这个问题呢？二、模型建立我们以运筹学中的图论为工具，找到一个求解的简单方法。我们将上例的图进行反向转化，以图顶点代替货物编号，以边代替能存放在一起的货物。通过该步骤，得到图G并且把原问题转化为一个图论问题。定义：若一个多边形的各个顶点都用对角线连接起来，把这个多边形叫做完备多边形。求解步骤：1、根据题意建立图G 的顶点和边；2、找出图G 中尽可能包含较多顶点的完备多边形；3、若符合条件的多边形有多个，则任取其中一完备多边形，记作S1，然后在图G 中把该多边形包含的顶点和边删去，即做运算：G/S1，在其中找出中包含较多顶点的完备多边形；4、在符合条件的多边形中任取一完备多边形，记作S2，做运算：G（s1s2），再在从中找出包含较多顶点的完备多边形；5、如此继续该过程，直至所有顶点都包含在完备多边形中。由步骤可得该算法的具体流程图如图二所示。k=0,Sk=,Gk=G在Gk中找出包含较多点的完备多边形取其中任意完备多边形，记为：Sk+1K=K+1作运算：Gk=G/SkGk=NY输出：S1.Sk算法结束图二三、例题分析为了说明这种图论方法的实际可操作性，我们对引例中所涉及到的问题建立模型，那么，问题中各种药品的关系可以转化用下图G表示为：图三由于完备多边形的各个定点所代表的货物任意两个之间是可以存储在同一个仓库，所以我们就可以在图中找到一个的包含最多顶点完备多边形，并将这个完备多边形各个定点所代表的药品存放在一个仓库。然后将这些定点和连线去掉，使得问题不断简单化，循环这个步骤，最后将得到最少的仓库数量。对于包含最多顶点完备多边形为；和 令S1=，做运算G/S1 得下图（图四）：图四包含最多顶点完备多边形为令S2=并做运算：G/（S1S2） 得下图（图五）：图五最后只剩下，这两种药品不能放在一起，分别令：S3=,S4=,在分别作运算G/（S1S2S3）和运算G/（S1S2S3S4）,这样所有的点都包含在完备多边形中。所以针对这8种药品应该设立4个仓库即可满足条件，并且最优的满足条件货物存储方案为：仓库一：s1=；仓库二：s2=；仓库三：s3=；仓库四：s4=。四、小结运用图论的方法的关键在于在每次运算时，要找到包含定点最多的完备多边形。通过实例可以看出，运用这种方法可以很容易地解决货物共存这一系列问题，虽然可能因为完备多边形的选取不同，可能导致货物存放方案不完全一致，但最少所需仓