网络流模型优化策略

Zangwill（1969）最先引入网络流规划的方法来解决动态批量问题，大大简化了问题的性质分析过程。于是，本小节采用该方法，对6.1.2小节的混合整数规划模型进行网络流建模，如图6-2所示。

图6-2　网络流模型(www.xing528.com)

图6-2是一个单一起点多终点的网络流模型，顶点0为整个问题的虚拟起始点，它的供应量为问题需要满足的T期总需求，终点集{1″，2″，…，T″}表示相应时期的顾客需求。其他结点对应系统不同位置所在的相应时期，其中，点集{1，2，…，T}对应订单处理中心，{1′，2′，…，T′}对应配送站。弧（t，t′）上的流量表示由订单处理中心到配送站的发送量，它对应两个量，分别为自营物流发送量（左弧）和第三方物流配送量（右弧）。弧（t，t+1）上的流量为订单处理中心的库存流，表示第t期末的库存持有量。弧（t′，t″）上的流量表示快递员从配送站满足该期需求的发送量，它应该恰好等于该期需求量dt。弧（t′，t′+1）为配送站的库存流，表示第t期末的库存持有量。

在该网络流模型中，所有弧上的成本结构都是凹性的。其中，弧（0，1）对应的成本为0，弧（t，t+1）上的单位成本为，弧（t′，t′+1）的单位成本为。弧（t，t′）对应两条流，其中如果流为空，则成本为0，否则成本为+·；流对应成本为·。当为正时，弧（t′，t″）上对应的成本为+·，否则为0。于是，求解6.1.2小节的混合整数规划问题，就等同于在该网络流模型中找到一个最小成本极流的问题。