报童问题的简单解法

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

问题

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

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

求解

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

π(x,D)=pmin(x,D)+smax(xD,0)cx=pmin(x,D)+s[max(x,D)D]cx=pmin(x,D)+s[x+Dmin(x,D)D]cx=(ps)min(x,D)(cs)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)]=(ps)E[min(x,D)](cs)x=(ps)0+min(x,d)f(d)dd(cs)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=(ps)x(0+min(x,d)f(d)dd)(cs)=(ps)x(0xdf(d)dd+x+xf(d)dd)(cs)=(ps)[0x(df(d))xdd+x+(xf(d))xdd](cs)=(ps)x+f(d)dd(cs)=(ps)[1F(x)](cs)\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)=pcpsγF(x) = \frac{p-c}{p-s} \equiv\gamma

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

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