报童模型研究论文

​ 记优化问题（1-2）的最优解为 。若某一场景中需求 的取值为 ，那么显然 可能与 差别很大。一个很自然的想法是：能否给优化问题（1-2）添加一个约束 。考虑到 是一个分片线性函数，那么该约束等价为 其中 表示需求 的所有可能的取值构成的集合。

上述约束过强，若 足够大，那么很有可能没有 能够满足上述约束，即优化问题不可行。进而我们可以考虑添加这样一个约束： 的概率小于阈值 。这就是一个 chance constraint ，表示如下 亦即 我们来看看 的形式 于是乎chance constraint (1-7)等价于 相对于约束（1-5）来说，约束（1-8）宽松了很多。

​ 我们对报童问题进行拓展，考虑一个多阶段问题。假定公司需要在一个时间长度为 的经营活动中做决策。在第 个时间段，需求是一个随机变量，记为 ，其中 。在开始阶段，即 时，我们已知当前存货量为 。在每个阶段，即 时，公司观测到当前存货量为 ，然后公司决定购入一些货物，使得存货量更新为 ，显然 ；库存量更新之后，公司观测到需求量 （ 是 的一个实例），于是在 时段开始时，库存量 。注意 可能为正也可能为负，为负数时表示拖欠或者交付延误。 时段公司的代价如下 其中 表示购买成本， 表示延误成本， 表示库存成本。一般来说， ， 。

​ 目标是所有时间段的代价和的期望最小，可写为如下优化问题 ​ 若 ，那么优化问题（1-9）与优化问题（1-2）是等价的。 时，情况就复杂很多了。记 表示截止到时间 时的历史需求构成的随机过程，记 表示 的一个实例。在 时间段开始时，我们不知道 ，但是我们很有可能知道 在 情况下的条件概率分布。假定我们知道该条件分布。

​ 最后一个时间段，即 ，我们观测到了 ,然后我们求解下述优化问题： 亦即求解如下问题 ​ 显然优化问题（1-10）或者（1-11）的目标函数最优解时一个关于 以及 的函数，我们将其记为

​ 在 时，我们求解如下优化问题 注意到 ，优化问题（1-12）可以写为 ​ 显然优化问题（1-12）或者（1-13）的目标函数最优解时一个关于 以及 的函数，我们将其记为

​ 类似地对于 ，我们求解如下优化问题 ​ 最后在 时，求解如下问题 ​ 我们再来回顾下优化问题（1-10）-（1-14）。从 开始，我们需要回溯求出函数 。一般来说，很难或者几乎不可能求出上述函数。如果假定 是"阶段独立"（stagewise independent）的，那么情况会变得简单很多。所谓的"阶段独立"是指， 与 独立。那么优化问题（1-10）-（1-14）中的条件期望就直接转换了期望。目标函数最优值也就可以写为 。此时，我们可以对 以及 进行离散化，对于每一个 我们求解相应的 。但是该方法面临着维数灾难，如果 以及 可取值较多，那么该方法几乎不可行。后面章节我们会谈到，动态规划利用了函数的凸性来降低维数带来的灾难。

​ 假定我们已经求解出来了优化问题（1-10）-（1-14）。记最优解为 。对于 ， 是 以及 的函数。而 仅仅与 有关。在"阶段独立"的假设下， 仅仅是关于 的函数。考虑到 自身是由 与 决定。所以，我们考虑将决策视为关于 的函数，即 。这样的一组决策，我们称为实行策略，或者简称策略，policy。策略是指基于当前阶段可获得的信息来做出何种决策的规则。 ​ 我们可以将优化问题（1-9）理解为在所有可能的策略中，寻找代价期望最少的策略。动态规划问题求解出来的解即为最优策略。在"阶段独立"的情况下，我们假定 是下列无约束优化问题的解。 我们可以证明上述目标函数关于 是凸函数，并且当 逼近于无穷大时，函数值为正无穷大。因而，上述优化问题一定存在最优解。再考虑函数的凸性，可知 时最优策略。当没有"阶段独立"的假设时，结论依然成立，不过此时 与 有关。

​ 我们证明优化问题（1-15)的目标函数时一个凸函数，无论"阶段独立"是否成立。

​ 记 ， 是任意两个数， ， .

​ 证毕。

记 ，那么依据章节1.1.1中的分析，该函数是一个关于 的凸函数。给定 ，记 关于 最优解为 ，那么

注意函数 是关于 的凸函数。关于它的证明略，可依据二次函数画图理解。那么 是关于 的凸函数。

我们再来观察 ，如式（1-13）所示，目标函数中与 相关的部分可以写为关于 的凸函数（注意包含了一个仿射变换，以及一个求期望运算，都是保凸的)。该凸函数再约束 下求最优值，那么所得目标函数是一个关于 的函数，同上，该函数关于 凸。进而 是关于 的凸函数。

以此类推，可证明 是关于 的凸函数。

那么依据仿射变换跟期望运算的保凸性，可知优化问题（1-15)的目标函数时一个凸函数，无论"阶段独立"是否成立。