【管理运筹学】第 8 章 | 动态规划（3，资源分配问题）

系列文章

【管理运筹学】第 8 章 | 动态规划（1，多阶段决策过程与动态规划基本概念）
【管理运筹学】第 8 章 | 动态规划（2，动态规划的基本思想与模型求解）
【管理运筹学】第 8 章 | 动态规划（3，资源分配问题）
【管理运筹学】第 8 章 | 动态规划（4，生产与储存问题）
【管理运筹学】第 8 章 | 动态规划（5，设备更新问题）

文章目录

• 系列文章
• 引言
• 三、资源分配问题
• • 3.1 一维离散资源分配问题
  • 3.2 一维连续资源分配问题
  • 3.3 二维资源分配问题
• 写在最后

引言

承接系列前文，有了对动态规划的基本认识，我们接下来就来对资源分配问题进行动态规划具体建模分析。

三、资源分配问题

所谓资源分配问题，就是将数量一定的一种或若干资源（例如原材料、资金、机器设备、劳力、食品等），恰当地分配给若干个使用者，使得目标函数达到最优。

3.1 一维离散资源分配问题

设有某种原料，总数量为 ，用于生产 种产品。若分配数量 用于生产第 种产品，其收益为 。问应如何分配，能使得生产这 种产品的总收入最大？

易得此问题可以写成如下规划问题： 当收益函数 均为线性函数时，该问题是一个线性规划问题，可以利用单纯形法进行求解；当收益函数为非线性函数时，问题变为一个非线性规划问题，我们并没有要求掌握其解法。

由于这类问题的特殊结构，可以将它看作是一个多阶段决策问题，利用我们刚学习的动态规划方法进行求解。对于此类资源分配问题，通常以把资源分配给一个或几个使用者的过程作为一个阶段，将问题中的 作为决策变量，将累计的量或随递推过程变化的量选为状态变量。

此题中，可设状态变量 表示分配用于生产第 种至第 种产品的原料总数量（也即此时剩余的总可用资源数量），决策变量 表示分配给生产第 种产品的原料数，有 。则可得到状态转移方程为： ，允许决策集合： 令最优值函数 表示以数量 的原料分配给第 种产品至第 种产品所得到的最大总收入，可写出动态规划的逆推关系式为： 最后求得的 即为问题所求的最大总收入，具体最优生产计划可以按照 进行推算，第一阶段采用 ，则第二阶段 ，可找出 ，依次类推。

利用动态规划解法还有一个好处就是，当资源数量减少后，不用重新计算，只需修改最后一个阶段的分配情况即可。

这种指将资源合理分配，而不进行回收的问题，又被称为资源平行分配问题。

3.2 一维连续资源分配问题

在资源分配中考虑资源回收利用，决策变量为连续值的问题称为资源连续分配问题，其一般叙述如下：

设有数量为 的某种资源，可投入 两种生产。第 1 年若以数量 投入生产 ，剩下的量 就投入生产 ，则可得收入为 ，其中 为已知收益函数，且 。这种资源在投入 生产后，年终还可回收再投入生产。

设年回收率分别为 ，则在第 1 年生产后，回收的资源量合计为 。第二年可将 中的 和 分别再投入 两种生产，年末又可以得到收入 。如此继续进行 年，问：应该如何决定每年投入 生产的资源量 ，使得总的收入最大？

类比离散资源分配问题的处理手法进行处理，记 为状态变量，表示第 阶段（第 年）可用于投入两种生产的资源总量。 为决策变量，表示第 阶段（第 年）用于 生产的资源量，则 表示用于 生产的资源量。状态转移方程为： 最优值函数 表示第 阶段至第 阶段采取最优分配方案进行生产后所得到的最大总收入。则逆推关系式为： 最后所求 即为所求问题最大总收入。

3.3 二维资源分配问题

看了下书，没有算例，难度应该不小，很可能考试是不涉及的，我就先留着吧。

写在最后

如果能从实际问题中，找到适合建立动态规划模型的状态量、转移方程和指标函数，那么，按照我们前面的动态规划模型求解办法，是可以按部就班顺利解决的。

对于连续和离散两种类型的资源分配问题，它们的建模思想很类似，但是要注意一些细节。下一篇文章，我们来说一说生产与储存问题。