报童问题

目录

本文介绍了一个经典的商品采购模型，称之为报童问题，以及它的解法。该模型通过考虑需求的不确定性来最大化销售利润。本文的主要内容参考 Gallego1。

问题描述

这是一个关于卖报商人采购报纸的问题。 每天早上，卖报商以批发价0.3元(每份)向报社采购当天的报纸，然后以零售价1元(每份)进行售卖。如果报纸在当天没有卖完，他会把报纸以0.05元(每份)的价格卖给废品回收站。那么卖报商应该如何确定报纸的采购数量？

我们先简单分析一下这个问题的特点:

  1. 采购一个商品。
  2. 在一个采购周期内仅采购一次。
  3. 采购之时不知道准确的需求。
  4. 商品会过期。

数学模型

下面我们用数学语言把这个问题再描述一下.

参数

  • 单位采购成本(cost per unit): $c$
  • 零售价(sale price): $p$
  • 残值(salvage value), 即商品过期之后的售价: $s$
  • 需求(demand): 随机变量$D$服从分布$F$, 均值和标准差分别记为$\mu, \sigma$

决策变量

  • 采购量: $x$

目标

  • 最大化期望收益 $\pi(x) := p \cdot \mathbb{E}[\min(x, D)] + s\cdot \mathbb{E}[\max(x-D, 0)] - cx$

不失一般性，我们假设 $p>c>s$，否则问题的最优解是显而易见的。

求解

记 $x^+ := \max(x, 0), x^-:=\min(x, 0)$。因此$x=x^+ + x^-$，$x^- = -(-x)^+$。利用 $\min(x, D) = D - (D-x)^+$，我们可以把 $\pi(x)$ 表示成如下形式:

$$\pi(x) = (p-c)\mu - \alpha(x),$$

其中

$$\alpha(x) = (c-s)\mathbb{E}[(x-D)^+] + (p-c)\mathbb{E}[(D-x)^+].$$

因此 $\max \pi(x) \Leftrightarrow \min \alpha(x)$。记$h = c-s$, $b=p-c$。则 $h, b$ 分别代表采购过量(overage) 和少量 (underage) 的单位成本.

令 $f(z) = hz^+ - bz^-$。$\alpha(x)$可以被写成

$$\alpha(x)=\mathbb{E}[f(x-D)].$$

由于 $f(z)$ 是凸函数，它的线性变换 $\alpha(x)$ 也是凸函数， 当 $F$ 是连续分布时，最优解的一阶导数为 0。 我们可以通过交换积分号导，即

$$\alpha’(x) = h\cdot \mathbb{E}[\delta(x-D)] - b\cdot \mathbb{E}[\delta(D-x)]$$

其中 $\delta(z)=1$。如果$z>0$，否则$\delta(z)$为0。

注意到 $\mathbb{E}[\delta(x-D)] = Pr(x-D>0)$且$\mathbb{E}[\delta(D-x)] = Pr(D-x>0)$。我们有

$$ \alpha’(x)= h \cdot Pr(D < x) - b \cdot Pr(D>x).$$

令 $\alpha’(x)=0$，我们得到

$$F(x) := Pr(D\leq x) = \frac{b}{b+h}.$$

临界分位数(Critical Fractile)

$$\gamma = \frac{b}{b+h}.$$

由于 $F$ 是随机变量 $D$ 的 cdf(cumulative distribution function) (单调非递减)，因而存在逆函数。设最优解为$x^*$，因此

$$x^* = F^{-1}(\gamma).$$

例子

本节考虑两个具体的例子。一个是 $D$ 服从正态分布(连续分布)，可以按照前文的公式计算最优解；另一个例子是 $D$ 服从Poisson 分布，我们介绍如何把计算方法适配到离散分布的情形。

正态分布

$D\sim N(\mu,\sigma^2)$。令 $Z\sim N(0, 1)$，$\Phi(z) = Pr(Z\leq z) $且$ z_{\gamma} = \Phi^{-1}(\gamma)$。

由于 $$Pr\left(\frac{D-\mu}{\sigma}\leq z_{\gamma}\right) = \Phi(z_{\gamma}) = \gamma.$$

因此 $$x^* = \mu + z_{\gamma}\sigma.$$

例 $D$ 服从正态分布，$\mu=100$，$\sigma=20$。设 $c=5$，$h=1$, $b=3$。我们的计算步骤如下：

  1. $\gamma = \frac{b}{h+b} = 0.75$

  2. $z_{\gamma} = \Phi^{-1}(0.75) = 0.6745$

    >>> from scipy.stats import norm
>>> norm.ppf(0.75)
0.6744897501960817

  3. $x^*=\mu + z_{\gamma} \cdot \sigma = 100 + 0.6745 * 20 = 113.49$

Poisson分布

Poisson分布的pmf (probability mass function) 为

$$Pr(D=k) = e^{-\lambda}\frac{\lambda^k}{k!}.$$

由于Possion分布是离散分布(对任意的 $\gamma$，$F^{-1}(\gamma)$ 不一定可计算)， 我们令 $$x^* = \arg\min_x \set{x\in \mathbb{N}\mid Pr(D\leq x) \geq \gamma}.$$

例 $D$ 服从Poisson分布，$\lambda=25$。设$c=5$, $h=1$, $b=3$。

我们的计算步骤如下:

  1. $\gamma = \frac{b}{h+b} = 0.75$
  2. 利用二分法找到最小的整数 $x^*$ 使得 $F(x^*)\geq 0.75$ (其中 $F$ 是随机变量 $D$ 的 cdf)。
    # python
>>> from scipy.stats import poisson
>>> poisson(25).cdf(27)
0.7001861449652768
>>> poisson(25).cdf(28)
0.763400741866402
  3. $x^*=28$

总结

  1. 报童问题是商品采购问题的一个例子。对该问题的研究和求解可以指导我们在实际中优化采购计划，从而提高商品的销售利润。
  2. 但在实际中制定商品的采购计划时，我们的目标与约束一般会比报童问题复杂(例如考虑库存成本)，因此需要根据实际问题进行建模和求解，不能盲目照搬已有的模型。
  3. 制定采购计划之前可以采用需求预测(销量预测)，但同时也要考虑销量的随机性。

参考文献

  1. Guillermo Gallego. “IEOR 4000 Production Management Lecture 7”. Columbia University, 2005. ↩︎

标签 :