用解决动态规划问题

子任务4.6　用Excel解决动态规划问题

4.6.1　任务引入

【任务4-6】　某物流公司根据年度设备计划的安排，拟购进某种高效率的仓储设备4台，分配给下属的甲、乙、丙3个物流中心。各物流中心获得设备之后，可以为该公司提供的赢利情况如表4-22所示，请问，物流公司如何分配这4台设备，才能使公司总投资效益最大？

表4-22

首先将问题分为3个阶段，分别对应于甲、乙、丙3个物流中心的设备分配。这就将静态问题转化成了分阶段的动态问题，从而可以利用DP方法进行处理。

4.6.2　任务分析

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是在一些与时间无关的静态规划（如线性规划、非线性规划）问题中，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地进行求解。由于动态规划所面临的问题是复杂多样的，它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理；因此使得动态规划问题没有一个类似于线性规划问题那样具备一般性的Excel处理方法，而是要具体问题具体分析，并灵活地应用Excel工具来解决此类问题。

4.6.3　任务实施

步骤一　将基本工具输入工作表

如图4-7上部所示，并在相应的单元格中输入计算公式，列式如下：

在单元格B18中输入“=SUM（B13：B17）”，并复制到单元格区域“C20：D18”；

在单元格B19中输入“=SUMPRODUCT（B13：B17，＄A＄13：＄A＄17）”，在单元格C19中输入“=SUMPRODUCT（C13：C17，＄A＄13：＄A＄17）”，在单元格D19中输入“=SUMPRODUCT（D13：D17，＄A＄13：＄A＄17）”；

在单元格E19中输入“=SUM（B19：D19）”；

在目标函数单元格B9中输入“=SUMPRODUCT（B3：D7，B13：D17）”；

可变单元格为：B13：D17，共15个单元格。

步骤二　求解参数对话框

单击“工具”→“规划求解”，弹出规划求解参数对话框（见图4-5），在“设置目标单元格”栏中输入“＄B＄9”，在“等于”栏中选中“最大值”单选框，在“可变单元格”栏中输入“＄B＄13：＄D＄17”。

图4-5

添加约束条件“＄B＄13：＄D＄17=二进制”，（只能取值0或者1）

“＄E＄19”≤4（供分配的台数不能少于4）

“＄B＄18：＄D＄18=1”（甲、乙、丙3个物流中心只能取一个状态）

步骤三

在规划求解参数对话框单击“选项”按钮，选中“采用线性模型”和“假定非负”复选框，单击“确定”按钮返回，如图4-6所示。

图4-6

步骤四

单击“求解”按钮。弹出“规划求解结果”对话框，选择“保存规划求解结果（K）”单选框，并单击“确定”按钮得到图4-7所示的求解结果。

图4-7

由图4-7可知，4台设备应该分配给甲物流中心1台，给丙物流中心3台则公司获利最大，最大获利是60万元。