多项式时间算法优化技巧

性质6.2为零库存点发货性质，即在最优解中，仅当配送站上一期末的库存为零时，才从订单中心发货到配送站，且根据性质6.1，只会选择一种方式运输。于是，本小节根据这两个性质，设计一个多项式时间的动态规划算法。

假设i-1和j为配送站库存为零的两个相邻时期，即＝＝0。由性质6.2可知，第i期从订单处理中心发货，且发货量用来满足第i期到第j期的需求。定义F（s）为满足需求d1到ds的最小成本，（i，j）问题为寻找一个在第i期发货来满足需求di到dj的最小成本下的发货计划，C（i，j）为（i，j）问题的最小成本。于是，可以得到以下递归方程：

问题总的最小成本可由F（T）得到。

因此，计算（i，j）问题的最小成本C（i，j）就是该动态规划算法的关键。由性质6.1和性质6.2可知，计算C（i，j）即比较图6-3（a）（b）所示两种运送方案的成本。其中，图6-3（a）表示第i期从订单处理中心采用自营物流配送到配送站来满足需求di到dj，而图6-3（b）则表示采用第三方物流配送来满足。

图6-3　（i，j）问题求解(www.xing528.com)

为了表达上的简洁，我们定义

其中，1≤i≤j≤T。于是，C（i，j）可由如下公式计算得到：

其中，计算di，j、h1（i，j）和h2（i，j）的时间复杂度为O（T），计算C（i，j）的时间复杂度为O（T2）。而在递归方程中，计算F（j）的时间复杂度也为O（T2）。因此，整个动态规划算法的时间复杂度为O（T2）。