报童问题的简单解法

发表于 更新于 分类于

我们早先已经在《报童问题》一文中介绍了这个经典的商品采购模型。文中的推导略有些繁复。为了便于理解，本文将给出一个相对简单的解法。

问题

我们还是沿用前文的记号。问题定义如下：

每天早上，报童以批发价 cc 元/份采购当天的报纸，然后以零售价 pp 元/份售卖。如果当天报纸没有卖完，则以 ss 元/份的价格卖给废品回收站。不失一般性，假设 p>c>sp>c>s。用随机变量 DD 表示当天的需求量，并已知其概率分布。求使得期望收益最大的采购量 xx。

求解

收益为总销售额减去总成本：

π(x,D)=p⋅min⁡(x,D)+s⋅max⁡(x−D,0)−c⋅x=p⋅min⁡(x,D)+s⋅[max⁡(x,D)−D]−c⋅x=p⋅min⁡(x,D)+s⋅[x+D−min⁡(x,D)−D]−c⋅x=(p−s)⋅min⁡(x,D)−(c−s)⋅x\begin{aligned} \pi(x, D) &= p\cdot \min(x, D)+s\cdot\max(x-D, 0)-c\cdot x\\ &=p\cdot \min(x, D)+s\cdot[\max(x, D) - D]-c\cdot x\\ &=p\cdot \min(x, D)+s\cdot[x+D - \min(x, D) - D]-c\cdot x\\ &=(p-s)\cdot \min(x, D)-(c-s)\cdot x \end{aligned}

这里利用了 max⁡(x,D)+min⁡(x,D)=x+D\max(x, D) + \min(x, D) = x+D。

收益的期望为

E[π(x,D)]=(p−s)⋅E[min⁡(x,D)]−(c−s)⋅x=(p−s)⋅∫0+∞min⁡(x,d)f(d)dd−(c−s)⋅x\begin{aligned} \mathbb{E}[\pi(x, D)] &= (p-s)\cdot \mathbb{E}[\min(x, D)]-(c-s)\cdot x\\ &= (p-s)\cdot \int_0^{+\infty}\min(x, d) f(d)\mathrm{d}d-(c-s)\cdot x \end{aligned}

其中 f(d)f(d) 为随机变量 DD 的概率密度函数。

为使期望收益最大，我们令

∂E[π(x,D)]∂x=0=(p−s)⋅∂∂x(∫0+∞min⁡(x,d)f(d)dd)−(c−s)=(p−s)⋅∂∂x(∫0xd⋅f(d)dd+∫x+∞x⋅f(d)dd)−(c−s)=(p−s)⋅[∫0x∂(d⋅f(d))∂xdd+∫x+∞∂(x⋅f(d))∂xdd]−(c−s)=(p−s)⋅∫x+∞f(d)dd−(c−s)=(p−s)⋅[1−F(x)]−(c−s)\begin{aligned} \frac{\partial \mathbb{E}[\pi(x, D)]}{\partial x} & = 0\\ &=(p-s)\cdot \frac{\partial}{\partial x}\left( \int_0^{+\infty}\min(x, d)f(d)\mathrm{d}d\right)-(c-s)\\ &=(p-s)\cdot \frac{\partial}{\partial x}\left( \int_0^{x}d\cdot f(d)\mathrm{d}d+\int_x^{+\infty}x\cdot f(d)\mathrm{d}d\right)-(c-s)\\ &=(p-s)\cdot \left[ \int_0^x\frac{\partial (d\cdot f(d))}{\partial x}\mathrm{d}d+\int_x^{+\infty}\frac{\partial (x\cdot f(d))}{\partial x}\mathrm{d}d\right]-(c-s)\\ &=(p-s)\cdot \int_x^{+\infty}f(d)\mathrm{d}d-(c-s)\\ &=(p-s)\cdot [1-F(x)]-(c-s)\\ \end{aligned}

其中 F(d)F(d) 为随机变量 DD 的累积分布函数。解上式得

F(x)=p−cp−s≡γF(x) = \frac{p-c}{p-s} \equiv\gamma

γ\gamma 即为前文解得的临界分位数（Critical Fractile）。使得期望收益最大的采购量为

x∗=F−1(γ)x^*=F^{-1}(\gamma)