18.3.2 离散决策模型的例子

18.3.2.1 购买问题

一时间区间可以分成 $n$ 个周期,在其第 $j$ 个周期内,一工场需要某种原材料 $v_{j}$ 个单位. 在第 $j$ 个周期开始时能得到的这种材料的数量记作 $x_{j - 1}$ ,特别地, $x_{0} = x_{a}$ 是给定的. 在每个周期结束时工场将以单位价格 $c_{j}$ 购买待定数量 $u_{j}$ 个单位材料. 同时给定的储存容量 $K$ 是不能超过的,即 $x_{j - 1} + u_{j} \leq K$ . 要求确定购买策略 $(u_{1}, \dots, u_{n})$ ,使得总费用最小. 于是我们要求解如下的动态规划问题:

\begin{matrix} (18.127a) & OF: f (u_{1}, \dots, u_{n}) = \sum_{j = 1}^{n} f_{j} (u_{j}) = \sum_{j = 1}^{n} c_{j} u_{j} \to min! \end{matrix}

\begin{matrix} (18.127b) & \begin{matrix} CT: & x_{j} = x_{j - 1} + u_{j} - v_{j}, & j = 1 (1) n, \\ x_{0} = x_{a}, 0 \leq x_{j} \leq K, & j = 1 (1) n, \\ U_{j} (x_{j - 1}) = {u_{j} : max {0, v_{j} - x_{j - 1}} \\ \leq u_{j} \leq K - x_{j - 1}}, & j = 1 (1) n . \end{matrix}} \end{matrix}

在 (18.127b) 中, 保证满足所需要求, 并且储存容量不会超过. 如果每个周期内还要支付每个单位储存费用 $ℓ$ ,则在第 $j$ 周期内的中间费用是 $(x_{j - 1} + u_{j} - v_{j} / 2) ℓ$ , 而修正的费用函数是

\begin{matrix} (18.128) & f (x_{0}, u_{1}, \dots, x_{n - 1}, u_{n}) = \sum_{j = 1}^{n} (c_{j} u_{j} + (x_{j - 1} + u_{j} - v_{j} / 2) \cdot ℓ) . \end{matrix}

18.3.2.2 背包问题

假设有 $n$ 个项目 $A_{1}, \dots, A_{n}$ ,相应的权重和价值分别为为 $w_{1}, \dots, w_{n}$ 和 $c_{1}, \dots, c_{n}$ ,问题是要从中选取一些项目,使得总的权重数不超过给定上限 $W$ ,而总价值最大. 这个问题与时间无关. 我们按如下方式重新表述这个问题: 在每一阶段要作出一个有关项目 $A_{j}$ 选取的决策 $u_{j}$ ,这里若选取 $A_{j}$ ,则 $u_{j} = 1$ ,否则, $u_{j} = 0$ . 在每一阶段开始时能得到的容量记作 $x_{j - 1}$ . 从而就得到如下动态规划问题:

\begin{matrix} (18.129a) & f (u_{1}, \dots, u_{n}) = \sum_{j = 1}^{n} c_{j} u_{j} \to min! \end{matrix}

\begin{matrix} (18.129b) & \begin{aligned} x_{j} = & x_{j - 1} - w_{j} u_{j}, & j = 1 (1) n, \\ x_{0} = & W, 0 \leq x_{j} \leq W, & j = 1 (1) n, \\ u_{j} \in {0, 1}, & x_{j - 1} \geq w_{j}, & j = 1 (1) n . \\ u_{j} = & 0, & x_{j - 1} < w_{j}, \end{aligned}} \end{matrix}

18.3.2 离散决策模型的例子 ​

18.3.2.1 购买问题 ​

18.3.2.2 背包问题 ​

18.3.2 离散决策模型的例子

18.3.2.1 购买问题

18.3.2.2 背包问题