需求连续的无向网络上最小距离和问题算法  

A algorithm for the weighted minisum problem on an undirected network with continuous link demands

作　　者：马鸣明[1] 王成恩[1] 张士廉[1] 

机构地区：[1]中国科学院沈阳自动化研究所,沈阳110015

出　　处：《机械设计与制造》2001年第6期34-37,共4页Machinery Design & Manufacture

基　　金：国家自然科学基金重点项目(79931000)资助

摘　　要：设施位置优化决策是运筹学中的重要领域和供应链战略规划的一个很重要的部分。企业在建立分散的服务系统时，会面对如何选择服务设施建立位置才能使设施与客户距离的平均值最小的问题。这里将运筹学与图论相结合，提出的有连续需求无向网络上的 ＭＳＰ（ＭｉｎｉＳｕｍ ｐｒｏｂｌｅｍ最小距离和问题）算法，并开发了一个基于此算法的计算机程序。此算法能够解决任意平面图上的最小加权距离总和问题，并且以离散方法代替导数方法来寻找图上距所有需求的加权距离总和最小点的位置。这里对所提出的算法进行了数值例子验证，证明本算法由于避免Ｔ ＮＰ问题，所以能够在较短的时间里求出可行解。Facility location is an active Operation Research area and plays a significant role in strategic planing of Supply Chains. Enterprises will confront with the problem of locating their service facilities to minimize the sum of travel distances from the facilities to the demands during establishing geographically' distributed service systems. On basis of Operation Research and Graph theory, we developed an algorithm for the Minisum problem on an undirected network with continuous link demands. We also develop a program based on this algorithm. This algorithm can solve the Minisum problem on any undirected ichnography with continuous link demands. This algorithm use dispersed method instead of derivative method. In this paper we validate the algorithm with numerical examples. This algorithm can solve the problem in shorter time because of avoidance of NP problem.

关 键 词：位置决策 最小加权距离总和问题 1-median问题 供应链管理 

分 类 号：F270[经济管理—企业管理] O22[经济管理—国民经济]