设备更新的运筹学模型(2)

本文所讨论的设备更新问题正是一个多阶段决策问题．它是要选择在所计算的时间内要进行多少次更新，并且选择在何时更新，才能使在所考虑的计算期内的总利润最大(或总费用最小)的问题．

4　网络优化模型

网络优化模型画出图之后就可以将其转化为最长路径问题。最长路径法是基于最短路径法给出的。最短路径法是计算一个节点到其他节点的最短距离的方法，比较典型的是迪杰斯特拉(Dijkstra)算法，这种方法的主要特点是以起始点为中心向终点层层扩展．最短路径问题是图论研究一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．与之相反的最长路径法依旧可以使用Dijkstra算法，从两节点中选择最长路径．

5　实例应用

康博公司拟为其已有3年役龄的一台设备决定在今后4年内的更新策略．已知一台设备若使用满6年则必须更新．若一台新的设备的价格为 =20万元．下表（表一）给出有关数据：

表一

役龄 /年

每年收益 /万元

年运营成本 /万元

残值 /万元

5。1　动态规划模型求解法

首先建立动态规划的递推关系式（基本方程）．

阶段是指一个问题需要作出决策的步数，也就是问题中互相联系的子问题的阶段。通常用来表示问题包含的阶段数，表示阶段个数，阶段变量可表示为 =1,2,3…, 。

状态转移律从某一状态转移到下一阶段状态值的规律，若给定第k阶段的状态变量的值，当该阶段的决策变量一确定，那么第阶段的状态变量的值也就确定了。

最优指标函数是从某一确定阶段开始到终止阶段取得最优策略后所得到的指标函数，也是对应某一最优子策略的某种效益度量。对于从出发的最优子策略效益值可记为，于是有

Opt即为最优化optimization，根据具体情况可以是求最大max或者最小min[2-4]．

用代表状态变量，意为设备的役龄，为役龄为的设备工作一年的收益（万元），为役龄的设备的年运营成本（万元），为役龄为的设备的残值．

当已有年役龄的设备于年初（或上年末）更新，则当年的收益为

，年末时设备役龄为变为1．

若年初役龄为的设备不更新，则当年的收益为

，年末时设备役龄变为．

用表示年年初役龄为的设备采用最优更新策略时，到规定期限年年末的最大收益，则有

因为考虑4年内更新策略，故 =1，…，4。边界条件为

解决动态规划问题有两种方法，一种是逆序递推法，一种是顺序递推法．

逆序递推法的基本方程：论文网

边界条件为，式中

其求解过程为根据边界条件从开始，从后向前逆推，可以逐步求得各阶段的最优决策和相对应的最优值，当最后求出了时，便得到了整个过程的最优解。

顺序递推法的基本方程

边界条件为，式中，即状态转移是由，去确定。

其求解过程为根据边界条件从开始，由前向后顺推，可逐步得到各阶段的最优决策和相对应的最优值，当最后求得时，便得到了整个问题的最优解．

根据本题建立的模型，我们可以看出是从求，因此很明显是要使用逆序递推法。

采用逆序递推法求解，为进行计算，先分析各年设备状态的演变情况，详见表二．

表二