隨機規(guī)劃模型與理論系列-001：報童問題

第一章隨機規(guī)劃模型

1.1 投資問題

1.1.1 報童問題

問題描述

$\quad\quad$ 這是一個關于賣報商人采購報紙的問題. 每天早上, 賣報商以批發(fā)價c(每份)向報社采購x份當天的報紙。如果當天的需求量d比x大，那么商人需要以價格d(每份)向報社再采購d-x份豁鲤。如果當天的需求量d比x小，會觸發(fā)庫存代價，每份報紙的庫存代價是h。一般來說， $d>c>0$ , $h>0$ 陆赋】该牛總代價為：
$F(x,d)=cx+b[d-x]_++h[x-d]_+$
? 其中 $[x]_+=max\{x,0\}$

確定型優(yōu)化問題

? 我們的目標是使得總代價最少鸠信。即可寫為如下優(yōu)化問題
$\min_{x\ge0} \quad F(x,d) \tag{1-1}$
? 顯然，給定 $d$ 论寨，上述問題的最優(yōu)解為 $x^*=d$ 星立。

隨機規(guī)劃問題

$\quad\quad$ 現(xiàn)在我們考慮每天的需求 $D$ 是一個隨機變量的情況。那么我們希望葬凳，采購 $x$ 份報紙時绰垂，代價的期望最小。即可寫為如下優(yōu)化問題
$\min_{x\ge0} \quad \{f(x):=\mathbb{E}[F(x,d)]\} \tag{1-2}$
$\quad\quad$ 該問題是兩階段問題（two-stage problem）的一個好例子火焰。在第一階段劲装，報童不知道當天真實的需求 $d$ ，他需要做出決策購買多少份報紙昌简，即 $x$ 的取值占业；在第二階段，報童知道了當天的需求 $d$ 纯赎，若 $d>x$ 那么報童需要進行追索賠償（recourse action）谦疾，即以高價補購 $d-x$ 份報紙。

解析解

$\quad\quad$ 接下來的問題是如何求解上述優(yōu)化問題犬金。上述問題可以給出其解析解餐蔬。記隨機變量 $D$ 概率密度函數(shù)為 $q(z)$ ，累計概率密度函數(shù)為 $H(z)$ 佑附，即 $H(z):=Pr(D\le z)$ 樊诺。顯然對于任意的 $z\le 0$ ， $H(z)=0$ 音同。期望 $\mathbb{E}[F(x,d)]$ 可寫為如下形式
$\begin{aligned} \mathbb{E}[F(x,d)]\} &=cx+b\int_{x}^{+\infty}(z-x)q(z)dz+h\int_{0}^{x}(x-z)q(z)dz \\ &=cx+ b\int_{0}^{+\infty}(z-x)q(z)dz-b\int_{0}^{x}(z-x)q(z)dz + h\int_{0}^{x}(x-z)q(z)dz\\ \end{aligned}$
其中 $b\int_{0}^{+\infty}(z-x)q(z)dz=b\mathbb{E}[D]-bxH(z)|_0^{+\infty}=b\mathbb{E}[D]-bx$ 词爬，所以
$\mathbb{E}[F(x,d)]\}=cx+b\mathbb{E}[D]-bx-b\int_{0}^{x}(z-x)q(z)dz + h\int_{0}^{x}(x-z)q(z)dz$
記 $G(z)=\int H(z)dz$ ，則有
$\int (z-x)q(z)dz=-xH(z)+zH(z)-G(z)$ $\int (x-z)q(z)dz=xH(z)-zH(z)+G(z)$
那么
$\begin{aligned} -b\int_{0}^{x}(z-x)q(z)dz &=-b\{ -xH(z)+zH(z)-G(z) \}|_0^{x} \\ &=-b(-xH(x)+xH(x)-G(x)+G(0))\\ &=b(G(x)-G(0))\\ \end{aligned}$
$\begin{aligned} h\int_{0}^{x}(x-z)q(z)dz &=h\{ xH(z)-zH(z)+G(z) \}|_0^{x} \\ &=h(xH(x)-xH(x)+G(x)-G(0))\\ &=h(G(x)-G(0))\\ \end{aligned}$

$\begin{aligned} \mathbb{E}[F(x,d)]\}&=cx+b\mathbb{E}[D]-bx+b(G(x)-G(0))+h(G(x)-G(0) \\ &=b\mathbb{E}[D]+(c-b)x+(b+h)(G(x)-G(0) \\ &=b\mathbb{E}[D]+(c-b)x+(b+h)\int_{0}^{x}H(z)dz \\ \end{aligned}$

? 接著我們分析函數(shù) $f(x):=\mathbb{E}[F(x,d)]$ 的一階導數(shù)與二階導數(shù)权均。

一階導數(shù)

$\begin{aligned} {f}'(x)&=c+\mathbb{E}[\frac{\partial }{\partial x}( b[D-x]_++h[x-D]_+)]\\ &=c-b\Pr(D\ge x)+h\Pr(D\le x)\\ &=c-b(1-H(x))+hH(x) \\ &=c-b+(b+h)H(x) \\ \end{aligned}$

二階導數(shù)

$\begin{aligned} {f}''(x)&=(b+h)H'(x) \\ &\ge 0 \\ \end{aligned}$

$\quad\quad$ 依據(jù)二階導數(shù)顿膨，我們可以判斷函數(shù) $f(x):=\mathbb{E}[F(x,d)]$ 是一個凸函數(shù)锅锨。由 ${f}'(x)=0$ 可求得最優(yōu)解 $x^*=H^{-1}(\kappa)$ ，其中 $\kappa =\frac{b-c}{b+h}$ 恋沃。累積分布函數(shù)的左 $\kappa$ 分位點定義為 $H^{-1}(\kappa)：=\inf \{t:H(t)\ge \kappa\}$ 必搞。同理，累積分布函數(shù)的右 $\kappa$ 分位點定義為 $\sup \{t:H(t)\le \kappa\}$ 囊咏。若左右分位點相等恕洲，則最優(yōu)解為左分位點或者右分位點；反之梅割，最優(yōu)解位于兩個分位點之間霜第。

$\quad\quad$ 假定在 $K$ 個場景（scenarios）中我們采集到 $D$ 的取值為 $d_1$ ， $d_2$ 户辞，... $d_K$ 泌类。那么此時經(jīng)驗累積分布函數(shù)是階躍函數(shù)，最優(yōu)解依然為 $\kappa$ 分位點（左或右）底燎，亦為某個 $d_k,k=1,2,...K$ 刃榨。

隨機規(guī)劃與確定型優(yōu)化的關系

$\quad\quad$ 實際應用中很難得到解析解，對于有限場景（scenarios）的問題双仍，我們通過改寫期望 $\mathbb{E}[F(x,d)]$ 可以將該隨機規(guī)劃建模為一個確定型優(yōu)化問題

$\mathbb{E}[F(x,d)]=\sum_{k=1}^{K}F(x,d_k)$
其中 $F(x,d_k)$ 可以寫為

$F(x,d_k)=\max\{(c-b)x+bd_k,(c+h)x-hd_k\}$
? 我們可以將不確定規(guī)劃寫為線性規(guī)劃形式喇澡，即
$\begin{aligned} \min_{x\ge0, v_1, v_2, ... v_K} \quad &=\sum_{k=1}^{K}p_{k}v_{k} \\ s.t.\quad &v_k \ge(c-b)x+bd_k, k=1,2,...K \\ \quad &v_k \ge(c+h)x-hd_k, k=1,2,...K\\ \end{aligned}$
? 值得注意的是上述分解形式。給定 $x$ 殊校，隨機規(guī)劃的目標函數(shù)是 $K$ 個確定型優(yōu)化問題（ $D=d_k$ ）目標函數(shù)的組合。也就是說读存，它將一個隨機規(guī)劃分解為 $K$ 個確定型規(guī)劃为流。后面我們會看到，這種分解形式是兩階段問題的典型特點让簿。

考慮最壞的情況

? 接下來我們假定每天的需求 $d\in[l,u]$ 敬察，在已知需求上下界的情況下，思考如何決定每天的購買量 $x$ 使得最壞的情況下?lián)p失最少尔当。即求解如下優(yōu)化問題
$\min_{x\ge0} \quad \max_{d\in[l,u]}F(x,d) \tag{1-3}$
? 依據(jù)函數(shù)定義莲祸，可計算 $\max_{d\in[l,u]}F(x,d)$ ，如下
$\max_{d\in[l,u]}F(x,d)=\max\{F(x,l),F(x,u)\}$
? 考慮到 $F(x,l)$ 與 $F(x,l)$ 均為分片線性函數(shù)椭迎，可知 $\max_{d\in[l,u]}F(x,d)$ 依然為分片線性函數(shù)锐帜。當 $h(x-l)=b(u-x)$ 時，取最小值畜号，即 $x^*=\frac {hl+bu} {h+b}$ 缴阎。

? 進一步的，假設我們還知道每天需求的平均值 $\barj1tpb7z=\mathbb E[D]$ 简软。顯然符合條件（指上下界與均值的值）的分布有很多種蛮拔。我們思考如何決定每天的購買量 $x$ 使得在最壞的分布情況下期望損失最少述暂。模型如下
$\min_{x\ge0} \quad \sup_{H\in \mathbb H} \mathbb E_H[F(x,d)] \tag{1-4}$

? 其中， $\mathbb H$ 表示所有符合條件的分布的累積分布函數(shù)的集合建炫； $\mathbb E_H[F(x,d)$ 表示給定 $x$ 的情況下畦韭，需求 $D$ 的累積分布函數(shù)為 $H$ 時的期望損失。我們會在后面討論如何求解該問題肛跌。

最后編輯于：2020.01.16 23:55:24

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

禁止轉(zhuǎn)載艺配，如需轉(zhuǎn)載請通過簡信或評論聯(lián)系作者。

人面猴
序言：七十年代末惋砂，一起剝皮案震驚了整個濱河市妒挎，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌西饵，老刑警劉巖酝掩，帶你破解...
沈念sama閱讀 222,627評論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異眷柔，居然都是意外死亡期虾，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,180評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門驯嘱，熙熙樓的掌柜王于貴愁眉苦臉地迎上來镶苞，“玉大人，你說我怎么就攤上這事鞠评∶荆” “怎么了？”我有些...
開封第一講書人閱讀 169,346評論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵剃幌，是天一觀的道長聋涨。經(jīng)常有香客問我，道長负乡，這世上最難降的妖魔是什么牍白？我笑而不...
開封第一講書人閱讀 60,097評論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮抖棘，結果婚禮上茂腥，老公的妹妹穿的比我還像新娘。我一直安慰自己切省，他們只是感情好最岗，可當我...
茶點故事閱讀 69,100評論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著朝捆，像睡著了一般仑性。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,696評論 1贊 312
城市分裂傳說
那天诊杆，我揣著相機與錄音歼捐，去河邊找鬼。笑死晨汹，一個胖子當著我的面吹牛豹储，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播淘这，決...
沈念sama閱讀 41,165評論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼剥扣，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了铝穷？” 一聲冷哼從身側響起钠怯，我...
開封第一講書人閱讀 40,108評論 0贊 277
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎曙聂，沒想到半個月后晦炊，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,646評論 1贊 319
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡宁脊，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,709評論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年断国，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片榆苞。...
茶點故事閱讀 40,861評論 1贊 353
活死人
序言：一個原本活蹦亂跳的男人離奇死亡稳衬，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出坐漏，到底是詐尸還是另有隱情薄疚，我是刑警寧澤，帶...
沈念sama閱讀 36,527評論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布赊琳，位于F島的核電站街夭，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏慨畸。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 42,196評論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一衣式、第九天我趴在偏房一處隱蔽的房頂上張望寸士。院中可真熱鬧，春花似錦碴卧、人聲如沸弱卡。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,698評論 0贊 25
一樁弒父案住册，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽婶博。三九已至，卻和暖如春荧飞，著一層夾襖步出監(jiān)牢的瞬間凡人，已是汗流浹背名党。一陣腳步聲響...
開封第一講書人閱讀 33,804評論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留挠轴，地道東北人传睹。一個月前我還...
沈念sama閱讀 49,287評論 3贊 379
代替公主和親
正文我出身青樓，卻偏偏與公主長得像岸晦，于是被迫代替她去往敵國和親欧啤。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 45,860評論 2贊 361