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

这篇具有很好参考价值的文章主要介绍了【管理运筹学】第 8 章 | 动态规划（3，资源分配问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

系列文章

引言

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

三、资源分配问题

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

3.1 一维离散资源分配问题

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

易得此问题可以写成如下规划问题： $\max z=g_1(x_1)+g_2(x_2)+\cdots+g_n(x_n)$ $s.t.\begin{cases} x_1+x_2+\cdots+x_n=a \\ x_i \geq 0，i=1,2,\cdots,n \end{cases}$ 当收益函数 $g_i(x_i)$ 均为线性函数时，该问题是一个线性规划问题，可以利用单纯形法进行求解；当收益函数为非线性函数时，问题变为一个非线性规划问题，我们并没有要求掌握其解法。

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

此题中，可设状态变量 $s_k$ 表示分配用于生产第 $k$ 种至第 $n$ 种产品的原料总数量（也即此时剩余的总可用资源数量），决策变量 $u_k$ 表示分配给生产第 $k$ 种产品的原料数，有 $u_k=x_k$ 。则可得到状态转移方程为： $s_{k+1}=s_k-u_k=s_k-x_k$ ，允许决策集合： $D_k(s_k)=\{u_k|0\leq u_k=x_k \leq s_k\}$ 令最优值函数 $f_k(s_k)$ 表示以数量 $s_k$ 的原料分配给第 $k$ 种产品至第 $n$ 种产品所得到的最大总收入，可写出动态规划的逆推关系式为： $\begin{cases} f_k(s_k)=\max\{g_k(s_k)+f_{k+1}(s_k-x_k)\}，k=n-1,\cdots,2,1 \\ f_n(s_n)=max\{g_n(s_n)\} \\ f_{n+1}(s_{n+1})=0，边界条件 \end{cases}$ 最后求得的 $f_1(a)$ 即为问题所求的最大总收入，具体最优生产计划可以按照 $x_1^*$ 进行推算，第一阶段采用 $x_1*$ ，则第二阶段 $s_2=s_1-x_1^*$ ，可找出 $s_2^*$ ，依次类推。

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

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

3.2 一维连续资源分配问题

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

设有数量为 $s_1$ 的某种资源，可投入 $A, B$ 两种生产。第 1 年若以数量 $u_1$ 投入生产 $A$ ，剩下的量 $s_1-u_1$ 就投入生产 $B$ ，则可得收入为 $g(u_1)+h(s_1-u_1)$ ，其中 $g, h$ 为已知收益函数，且 $g (0) = h (0) = 0$ 。这种资源在投入 $A, B$ 生产后，年终还可回收再投入生产。

设年回收率分别为 $a,b(a,b\in(0,1))$ ，则在第 1 年生产后，回收的资源量合计为 $s_2=au_1+b(s_1-u_1)$ 。第二年可将 $s_2$ 中的 $u_2$ 和 $s_2-u_2$ 分别再投入 $A, B$ 两种生产，年末又可以得到收入 $g(u_2)+h(s_2-u_2)$ 。如此继续进行 $n$ 年，问：应该如何决定每年投入 $A$ 生产的资源量 $u_1,u_2,\cdots,u_n$ ，使得总的收入最大？

类比离散资源分配问题的处理手法进行处理，记 $s_k$ 为状态变量，表示第 $k$ 阶段（第 $k$ 年）可用于投入两种生产的资源总量。 $u_k$ 为决策变量，表示第 $k$ 阶段（第 $k$ 年）用于 $A$ 生产的资源量，则 $s_k-u_k$ 表示用于 $B$ 生产的资源量。状态转移方程为： $s_{k+1}=au_k+b(s_k-u_k)$ 最优值函数 $f_k(s_k)$ 表示第 $k$ 阶段至第 $n$ 阶段采取最优分配方案进行生产后所得到的最大总收入。则逆推关系式为： $\begin{cases} f_k(s_k)=\max\{g(u_k)+h(s_k-u_k)+f_{k+1}(s_{k+1})\}，k=n,n-1,\cdots,2,1 \\ f_{n+1}(s_{n+1})=0，边界条件 \end{cases}$ 最后所求 $f_1(s_1)$ 即为所求问题最大总收入。