首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》运输问题

关灯直达底部

运输问题比转运问题要简单得多,因为没有中继仓库节点。有m个供应站si,每个供应站能够生产sup(si)个单位的商品。有n个需求站tj,每个需求站需要dem(tj)个单位的商品。

对于连接供应站si到需求站tj的边(u,v)来说,其单位开销d(i,j)是固定的。我们的目标是决定了从供应站si到需求站tj的流f(i,j)之后,最小化总开销。可以定义为:

总运输开销(TSC)=∑i∑jd(i,j)*f(i,j)

解必须满足不大于每个需求站tj的需求和每个供应站si的供应能力。

解决方案

我们将运输问题转换成没有中继仓库节点的转运问题。