本站原创【关键词】网格计算 供应链管理 优化模型
一、引言
供应链管理需要信息的实时集成和共享、资源的有效配置和利用，以实现供应链利益的最大化，然而Internet资源利用率低、信息标准不统一、难以实现互操作等缺陷无法满足供应链管理的发展。网格计算指基于网格的理由求解，其将分散在不同地理位置的资源虚拟成为一个空前强大的信息系统，具备超强的信息处理和资源整合能力、费用低、协同工作等特性，通过信息共享和集成支持供应链快速反应和相互协调，推动对未来需求的有效预测，解决供应链管理的信息失真和“牛鞭效应”等理由。
二、网格计算对供应链管理的影响
网格计算环境下供应链管理通过网格计算技术实现企业资源、信息的实时掌握和制约利用，跨越企业内部管理和外界“沟通”的范畴，形成以企业自身为链主、链接供应商与用户的全球供应链，从而使企业获取巨大效益。网格计算对供应链管理的影响主要包括：网格具有面向复杂数据的超强处理能力，能够满足供应链管理发展的需求；网格可以实现供应链的资源共享；网格组件化设计使供应链管理具备良好的可扩展性；网格既能实现供应链内部数据之间的无缝连接和高度集成，又能实现与电子商务等系统的集成；网格安全机制提高了供应链管理安全性。三、网格计算环境下供应链管理优化模型设计
根据研究方式的不同，供应链模型分为描述性模型和规范模型（优化模型）。描述性模型是为了更好地理解企业与外部环境之间的联系而建立，多数以图形方式表示供应链的构成及其要素之间的关系。规范模型则是为了帮助管理者更好地做出决策，是数学规划模型，即优化模型。(一)设计思路。
网格计算之于供应链管理最大的优势在于信息流传递的有效性和超强的处理能力，所以，本文从供应链中信息流传递处理的角度建立供应链管理优化模型。首先，介绍在供应链中的信息处理流程，如图1。假设供应网链中有一个通信网络，使得信息从一家企业的计算机向另一家企业的计算机上传递数据组（文件）。顶点V1，V2……Vm表示供应链各主体上处理信息的计算机，边e1，e2……en表示要传输的文件信息，T（ex）表示传输文件ex的时间，C（Vy）表示计算机Vy传输文件的容量，C（Vy）=1表示计算机Vy一次只能传输一个文件。供应链管理涉及的流程和业务非常多，因此，需要进行简化处理，参考简化的供应链网链结构模型，如图2：供应链网链结构模型有13个公司，包括一家核心企业、两家供应商、两家用户、四家供应商的供应商、四家用户的用户。假设每个公司只有一台计算机，每台计算机被表示为一个顶点。各个公司间每天必须传递12个文件，用边表示文件传输。对所有的x，y，都有T（ex）=1和C（Vy）=1。根据供应链管理网链结构模型建立模型设计图，求解即在受传输时间和计算机处理容量等因素的限制下，使得完成文件的传输时间最短。此时间在数学建模上被称为“完工时间”。
图1 供应链信息处理流程 图2 供应链网链结构模型
(二)基本假设。
为了简化计算，突出重点，制定7条假设：①通信网络图是无向的简单图，且任意两个顶点间没有重边，这意味着任意两台计算机之间传递的全部信息可以包括在一个文件里；②所有文件的“准备时间”为零，即所有文件传输可持续进行；③每个文件的传输时间为固定值；④所有文件相互独立，不存在优先传输的文件；⑤任一文件都要连续地传输，无中断；⑥每条边传输文件所需的时间一致，即T（ex）=1；⑦每台计算机一次只能传输处理一个文件信息，即C（Vy）=1。(三)非网格计算环境下供应链管理模型。
由于假设每个文件的传输时间T（ex）=1以及每台计算机的处理容量C（Vy）=1，所以，理由求解相对简单，使所有文件在最短的时间内传输完毕，需要将文件进行必要的分批处理，批数最小值即为完工时间。观察图3中的任意一种传输方案，发现在传输过程中每一单位时间内都有一些不同的文件在传输，它们对应的是图中没有相同端点的边集，即图3中的一个匹配，并且不同的匹配含有不同的边，它们的并集构成图3。这样，理由的最优传输时间表是将图3分解为最少个不相重的匹配，这些匹配的个数即为最优完工时间。图3 模型设计图
基于二分图的最大基数匹配算法设计以下步骤：步骤1，令E（u）是所有边集合，置STAGE=1；步骤2，求E（u）中的一个最大基数匹配，匹配中的边被称为已标号；步骤3，从E（u）中删除已被标号的边；步骤4，如E（u）不为空集，转步骤5；否则终止计算，STAGE即为最优完工时间；步骤5，令STAGE=STAGE+1，返回步骤2。
在具体求解过程中，将图3表示为二分图的形式，得到图4，找出图4的最大基数匹配（图5中虚线表示的边），此匹配中的边对应的文件第一批传输，删除这些边，得到图4的子图，如图6。对图6重复以上步骤，得到图7……
图4 步骤图1 图5 步骤图2
图6 步骤图3 图7 步骤图4
通过上述模型分析求解，第1个单位时间传输4个文件信息，第2个单位时间传输4个文件信息，第3个单位时间传输3个文件信息，第4个单位时间传输1个文件信息，完工时间为4个单位时间。由定理1（对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X中任一子集A和A邻接的点集Г（A），恒有|Г（A）|>|A|）可知，这是此模型的最优完工时间。