報童問題 (The Newsvendor Problem)

引言

本文介紹了一個經(jīng)典的商品采購模型(報童問題)及其解法. 該模型通過考慮需求的不確定性來最大化銷售利潤. 注: 本文的主要內(nèi)容參考Gallego^[1].

1. 報童問題

這是一個關(guān)于賣報商人采購報紙的問題. 每天早上, 賣報商以批發(fā)價0.3元(每份)向報社采購當(dāng)天的報紙, 然后以零售價1元(每份)進(jìn)行售賣. 如果報紙在當(dāng)天沒有賣完, 他會把報紙以0.05元(每份)的價格賣給廢品回收站. 那么賣報商應(yīng)該如何確定報紙的采購數(shù)量?

我們先簡單分析一下這個問題的特點:

采購一個商品.
在一個采購周期內(nèi)僅采購一次.
采購之時不知道準(zhǔn)確的需求.
商品會過期.

2. 數(shù)學(xué)模型

下面我們用數(shù)學(xué)語言把這個問題再描述一下.

參數(shù)

單位采購成本(cost per unit): $c$
零售價(sale price): $p$
殘值(salvage value), 即商品過期之后的售價: $s$
需求(demand): 隨機(jī)變量 $D$ 服從分布 $F$ , 均值和標(biāo)準(zhǔn)差分別記為 $\mu, \sigma$

決策變量

采購量: $x$

目標(biāo)

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

不失一般性, 我們假設(shè) $p>c>s$ , 否則問題的最優(yōu)解是顯而易見的.

3. 求解

記 $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)$ 是凸函數(shù), 它的線性變換 $\alpha(x)$ 也是凸函數(shù), 當(dāng) $F$ 是連續(xù)分布時, 最優(yōu)解的一階導(dǎo)數(shù)為0. 我們可以通過交換積分號導(dǎo), 即

$\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+h}.$

臨界分位數(shù)(Critical Fractile)
$\gamma = \frac只祠{b+h}.$

由于 $F$ 是隨機(jī)變量 $D$ 的cdf(cumulative distribution function) (單調(diào)非遞減), 因而存在逆函數(shù). 設(shè)最優(yōu)解為 $x^*$ , 因此
$x^* = F^{-1}(\gamma).$

4. 例子

本節(jié)考慮兩個具體的例子. 一個是 $D$ 服從正態(tài)分布(連續(xù)分布), 可以按照前文的公式計算最優(yōu)解; 另一個例子是 $D$ 服從Poisson分布, 我們介紹如何把計算方法適配到離散分布的情形.

4.1 正態(tài)分布

$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$ 服從正態(tài)分布, $\mu=100$ , $\sigma=20$ . 設(shè) $c=5$ , $h=1$ , $b=3$ . 我們的計算步驟如下:

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

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

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

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

4.2 Poisson分布

Poisson分布的pmf (probability mass function)為

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

由于Possion分布是離散分布(對任意的 $\gamma$ , $F^{-1}(\gamma)$ 不一定可計算), 我們令
$x^* = \arg\min_x \{x\in \mathbb{N}\mid Pr(D\leq x) \geq \gamma\}.$

例 $D$ 服從Poisson分布, $\lambda=25$ . 設(shè) $c=5$ , $h=1$ , $b=3$ . 我們的計算步驟如下:

$\gamma = \frac萍桌{h+b} = 0.75$

利用二分法找到最小的整數(shù)

x^*

使得

F(x^*)\geq 0.75

(其中

F

是隨機(jī)變量

D

的cdf).

# python
>>> from scipy.stats import poisson
>>> poisson(25).cdf(27)
0.7001861449652768
>>> poisson(25).cdf(28)
0.763400741866402

$x^*=28$

5. 總結(jié)

報童問題是商品采購問題的一個例子. 對該問題的研究和求解可以指導(dǎo)我們在實際中優(yōu)化采購計劃, 從而提高商品的銷售利潤.
但在實際中制定商品的采購計劃時, 我們的目標(biāo)與約束一般會比報童問題復(fù)雜(例如考慮庫存成本), 因此需要根據(jù)實際問題進(jìn)行建模和求解, 不能盲目照搬已有的模型.
制定采購計劃之前可以采用需求預(yù)測(銷量預(yù)測), 但同時也要考慮銷量的隨機(jī)性(詳情見《如何在商品采購中考慮銷量的隨機(jī)性?》).

參考文獻(xiàn)

Guillermo Gallego. "IEOR 4000 Production Management Lecture 7". Columbia University, 2005. ?

最后編輯于：2020.09.14 15:45:05

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末能曾，一起剝皮案震驚了整個濱河市度硝，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌寿冕，老刑警劉巖蕊程，帶你破解...
沈念sama閱讀 218,858評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異驼唱，居然都是意外死亡藻茂，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,372評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門玫恳，熙熙樓的掌柜王于貴愁眉苦臉地迎上來辨赐，“玉大人，你說我怎么就攤上這事京办∠菩颍” “怎么了？”我有些...
開封第一講書人閱讀 165,282評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵惭婿，是天一觀的道長不恭。經(jīng)常有香客問我，道長财饥，這世上最難降的妖魔是什么换吧？我笑而不...
開封第一講書人閱讀 58,842評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮钥星，結(jié)果婚禮上沾瓦，老公的妹妹穿的比我還像新娘。我一直安慰自己谦炒，他們只是感情好贯莺，可當(dāng)我...
茶點故事閱讀 67,857評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著编饺，像睡著了一般乖篷。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上透且，一...
開封第一講書人閱讀 51,679評論 1贊 305
城市分裂傳說
那天撕蔼，我揣著相機(jī)與錄音，去河邊找鬼秽誊。笑死鲸沮，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的锅论。我是一名探鬼主播讼溺，決...
沈念sama閱讀 40,406評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼最易！你這毒婦竟也來了怒坯？” 一聲冷哼從身側(cè)響起炫狱，我...
開封第一講書人閱讀 39,311評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎剔猿，沒想到半個月后视译，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,767評論 1贊 315
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡归敬，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,945評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年酷含，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片汪茧。...
茶點故事閱讀 40,090評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡椅亚，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出舱污，到底是詐尸還是另有隱情呀舔，我是刑警寧澤，帶...
沈念sama閱讀 35,785評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布慌闭，位于F島的核電站别威，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏驴剔。R本人自食惡果不足惜省古，卻給世界環(huán)境...
茶點故事閱讀 41,420評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望丧失。院中可真熱鬧豺妓，春花似錦、人聲如沸布讹。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,988評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽描验。三九已至白嘁，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間膘流，已是汗流浹背絮缅。一陣腳步聲響...
開封第一講書人閱讀 33,101評論 1贊 271
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留呼股，地道東北人耕魄。一個月前我還...
沈念sama閱讀 48,298評論 3贊 372
代替公主和親
正文我出身青樓，卻偏偏與公主長得像彭谁，于是被迫代替她去往敵國和親吸奴。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,033評論 2贊 355