隨機規(guī)劃模型與理論系列-002：報童問題的機會約束模型與多階段模型

1.1.2 機會約束模型

嚴格的值約束

? 記優(yōu)化問題（1-2）的最優(yōu)解為 $\bar{x}$ 垒棋。若某一場景中需求 $D$ 的取值為 $d$ ，那么顯然 $F(\bar{x},d)$ 可能與 $\mathbb E[F(\bar{x},D)]$ 差別很大掸茅。一個很自然的想法是：能否給優(yōu)化問題（1-2）添加一個約束 $F(x,D)\le \tau$ 椅邓。考慮到 $F(x,D)$ 是一個分片線性函數(shù)昧狮，那么該約束等價為
$(c-b)x+bd\le \tau, \forall d\in \mathbb D \tag{1-5} \\ (c+h)x-hd\le \tau, \forall d\in \mathbb D$
其中 $\mathbb D$ 表示需求 $D$ 的所有可能的取值構(gòu)成的集合景馁。

寬松的概率約束

上述約束過強，若 $\mathbb D$ 足夠大逗鸣，那么很有可能沒有 $x$ 能夠滿足上述約束合住，即優(yōu)化問題不可行。進而我們可以考慮添加這樣一個約束： $F(x,D)> \tau$ 的概率小于閾值 $\alpha$ 撒璧。這就是一個chance constraint透葛，表示如下
$\Pr\{F(x,D)>\tau\}<\alpha \tag{1-6}$
亦即
$\Pr\{F(x,D)\le \tau\}\ge 1-\alpha \tag{1-7}$
我們來看看 $\Pr\{F(x,D) \le \tau\}$ 的形式
$\begin{aligned} \Pr\{F(x,D) \le \tau\} &=\Pr \left \{(c-b)x+bd \le \tau,(c+h)x-hd \le \tau \right \} \\ &=\Pr\left \{(d \le \frac{(b-c)x+\tau}, d \ge \frac{(c+h)x-\tau}{h} \right \} \\ &=\Pr \left \{\frac{(c+h)x-\tau}{h} \le d \le \frac{(b-c)x+\tau}卿樱 \right \} \\ &=H \left( \frac{(b-c)x+\tau}僚害\right)-H\left(\frac{(c+h)x-\tau}{h}\right) \end{aligned}$
于是乎chance constraint (1-7)等價于
$H \left( \frac{(b-c)x+\tau}\right)-H\left(\frac{(c+h)x-\tau}{h}\right) \ge 1-\alpha \tag{1-8}$
相對于約束（1-5）來說殿如，約束（1-8）寬松了很多贡珊。

1.1.3 多階段模型（multistage models）

? 我們對報童問題進行拓展最爬，考慮一個多階段問題涉馁。假定公司需要在一個時間長度為 $T$ 的經(jīng)營活動中做決策。在第 $t$ 個時間段爱致，需求是一個隨機變量烤送，記為 $D_t$ ，其中 $t=1,2,...T$ 糠悯。在開始階段帮坚，即 $t=1$ 時，我們已知當(dāng)前存貨量為 $y_1$ 互艾。在每個階段试和，即 $t=1,2,...T$ 時，公司觀測到當(dāng)前存貨量為 $y_t$ 纫普，然后公司決定購入一些貨物阅悍，使得存貨量更新為 $x_t$ ，顯然 $x_t\ge y_t$ 昨稼；庫存量更新之后节视，公司觀測到需求量 $d_t$ （ $d_t$ 是 $D_t$ 的一個實例），于是在 $t+1$ 時段開始時假栓，庫存量 $y_{t+1}=x_t-d_t$ 寻行。注意 $y_t$ 可能為正也可能為負，為負數(shù)時表示拖欠或者交付延誤匾荆。 $t$ 時段公司的代價如下
$c_t(x_t-y_t)+b_t[d_t-x_t]_{+}+h_t[x_t-d_t]_{+}$
其中 $c_t$ 表示購買成本拌蜘， $b_t$ 表示延誤成本杆烁， $h_t$ 表示庫存成本。一般來說简卧， $b_t > c_t > 0$ 连躏， $h_t \ge 0$ 。

? 目標(biāo)是所有時間段的代價和的期望最小贞滨，可寫為如下優(yōu)化問題
$\begin{alignat}{2} \min_{x_t \ge y_t} \quad & \sum_{t=1}^{T} \mathbb E\{c_t(x_t-y_t)+b_t[d_t-x_t]_{+}+h_t[x_t-d_t]_{+}\} & \tag{1-9}\\ \mbox{s.t.}\quad &y_{t+1} =x_t-d_t, t=1,2,...T-1\\ \end{alignat}$
? 若 $T=1$ 入热，那么優(yōu)化問題（1-9）與優(yōu)化問題（1-2）是等價的。 $T>1$ 時晓铆，情況就復(fù)雜很多了勺良。記 $D_{[t]}:=(D_1,D_2,...D_t)$ 表示截止到時間 $t$ 時的歷史需求構(gòu)成的隨機過程，記 $d_{[t]}:=(d_1,d_2,...d_t)$ 表示 $D_{[t]}$ 的一個實例骄噪。在 $t$ 時間段開始時尚困，我們不知道 $d_t$ ，但是我們很有可能知道 $D_t$ 在 $D_{[t-1]}=d_{[t-1]}$ 情況下的條件概率分布链蕊。假定我們知道該條件分布事甜。

? 最后一個時間段，即 $t=T$ 滔韵，我們觀測到了 $y_T$ ,然后我們求解下述優(yōu)化問題：
$\min_{x_T \ge y_T} \quad \mathbb E\{c_T(x_T-y_T)+b_T[d_T-x_T]_{+}+h_T[x_T-d_T]_{+}|D_{[T-1]}=d_{[T-1]}\} \tag{1-10}$
亦即求解如下問題
$\min_{x_T \ge y_T} \quad \mathbb c_T(x_T-y_T)+E\{b_T[d_T-x_T]_{+}+h_T[x_T-d_T]_{+}|D_{[T-1]}=d_{[T-1]}\} \tag{1-11}$
? 顯然優(yōu)化問題（1-10）或者（1-11）的目標(biāo)函數(shù)最優(yōu)解時一個關(guān)于 $y_T$ 以及 $d[T-1]$ 的函數(shù)逻谦，我們將其記為 $Q_{T}({y_T,d_{[T-1]}})$

? 在 $t=T-1$ 時，我們求解如下優(yōu)化問題
$\min_{x_{T-1} \ge y_{T-1}} \quad \mathbb c_{T-1}(x_{T-1}-y_{T-1})+E\{b_{T-1}[d_{T-1}-x_{T-1}]_{+}+h_{T-1}[x_{T-1}-d_{T-1}]_{+}+Q_{T}({y_T,d_{[T-1]}})|D_{[T-2]}=d_{[T-2]}\} \tag{1-12}$
注意到 $y_{T}=x_{T-1}-d_{T-1}$ 陪蜻，優(yōu)化問題（1-12）可以寫為
$\min_{x_{T-1} \ge y_{T-1}} \quad \mathbb c_{T-1}(x_{T-1}-y_{T-1})+E\{b_{T-1}[d_{T-1}-x_{T-1}]_{+}+h_{T-1}[x_{T-1}-d_{T-1}]_{+}+Q_{T}(x_{T-1}-d_{T-1},d_{[T-1]})|D_{[T-2]}=d_{[T-2]}\} \tag{1-13}$
? 顯然優(yōu)化問題（1-12）或者（1-13）的目標(biāo)函數(shù)最優(yōu)解時一個關(guān)于 $y_{T-1}$ 以及 $d[T-2]$ 的函數(shù)邦马，我們將其記為 $Q_{T-1}({y_{T-1},d_{[T-2]}})$

? 類似地對于 $t=2,3,4...T-1$ ，我們求解如下優(yōu)化問題
$Q_{t}({y_{t},d_{[t-1]}})=\min_{x_{t} \ge y_{t}} \quad \mathbb c_{t}(x_{t}-y_{t})+E\{b_{t}[d_{t}-x_{t}]_{+}+h_{t}[x_{t}-d_{t}]_{+}+Q_{t+1}(x_{t}-d_{t},d_{[t]})|D_{[t-1]}=d_{[t-1]}\} \tag{1-14}$
? 最后在 $t=1$ 時宴卖，求解如下問題
$\min_{x_{1} \ge y_{1}} \quad \mathbb c_{1}(x_{1}-y_{1})+E\{b_{1}[d_{1}-x_{1}]_{+}+h_{1}[x_{1}-d_{1}]_{+}+Q_{2}(x_{1}-D_{1},D_{1})\} \tag{1-14}$
? 我們再來回顧下優(yōu)化問題（1-10）-（1-14）滋将。從 $t=T$ 開始，我們需要回溯求出函數(shù) $Q_{t}({y_t,d_{[t-1]}})$ 症昏。一般來說随闽，很難或者幾乎不可能求出上述函數(shù)。如果假定 $D_t$ 是"階段獨立"（stagewise independent）的肝谭，那么情況會變得簡單很多掘宪。所謂的"階段獨立"是指， $D_t$ 與 $D_{[t-1]}$ 獨立分苇。那么優(yōu)化問題（1-10）-（1-14）中的條件期望就直接轉(zhuǎn)換了期望添诉。目標(biāo)函數(shù)最優(yōu)值也就可以寫為 $Q_{t}(y_t)$ 。此時医寿，我們可以對 $y_t$ 以及 $D_t$ 進行離散化栏赴，對于每一個 $y_t$ 我們求解相應(yīng)的 $Q_{t}(y_t)$ 。但是該方法面臨著維數(shù)災(zāi)難靖秩，如果 $y_t$ 以及 $D_t$ 可取值較多须眷，那么該方法幾乎不可行竖瘾。后面章節(jié)我們會談到，動態(tài)規(guī)劃利用了函數(shù)的凸性來降低維數(shù)帶來的災(zāi)難花颗。

? 假定我們已經(jīng)求解出來了優(yōu)化問題（1-10）-（1-14）捕传。記最優(yōu)解為 $\bar x_t$ 。對于 $t=2,3,...T$ 扩劝， $\bar x_t$ 是 $y_t$ 以及 $d_{[t-1]}$ 的函數(shù)庸论。而 $\bar x_1$ 僅僅與 $y_1$ 有關(guān)。在"階段獨立"的假設(shè)下棒呛， $\bar x_t$ 僅僅是關(guān)于 $y_t$ 的函數(shù)聂示。考慮到 $y_t$ 自身是由 $d_{[t-1]}$ 與 $(x_1,x_2,...x_{t-1})$ 決定簇秒。所以鱼喉，我們考慮將決策視為關(guān)于 $d_{[t-1]}$ 的函數(shù)，即 $x_t=x_t(d_{[t-1]})$ 趋观。這樣的一組決策扛禽，我們稱為實行策略，或者簡稱策略皱坛，policy编曼。策略是指基于當(dāng)前階段可獲得的信息來做出何種決策的規(guī)則。
? 我們可以將優(yōu)化問題（1-9）理解為在所有可能的策略中麸恍，尋找代價期望最少的策略灵巧。動態(tài)規(guī)劃問題求解出來的解即為最優(yōu)策略。在"階段獨立"的情況下抹沪，我們假定 $x_t^{*}$ 是下列無約束優(yōu)化問題的解。
$\min_{x_{t}} \quad \mathbb c_{t}(x_{t}-y_{t})+E\{b_{t}[d_{t}-x_{t}]_{+}+h_{t}[x_{t}-d_{t}]_{+}+Q_{t+1}(x_{t}-d_{t})\} \tag{1-15}$
我們可以證明上述目標(biāo)函數(shù)關(guān)于 $x_t$ 是凸函數(shù)瓤球，并且當(dāng) $x_t$ 逼近于無窮大時融欧，函數(shù)值為正無窮大。因而卦羡，上述優(yōu)化問題一定存在最優(yōu)解噪馏。再考慮函數(shù)的凸性，可知 $\bar x_t=\max\{x_t^*,y_t\}$ 時最優(yōu)策略绿饵。當(dāng)沒有"階段獨立"的假設(shè)時欠肾，結(jié)論依然成立，不過此時 $x_t^*$ 與 $d_{[t-1]}$ 有關(guān)拟赊。

? 我們證明優(yōu)化問題（1-15)的目標(biāo)函數(shù)時一個凸函數(shù)刺桃，無論"階段獨立"是否成立。

首先我們證明一個保凸運算：一個凸函數(shù)在一個隨機變量上的期望仍然是凸函數(shù)吸祟。若設(shè)函數(shù) $g$ 是實數(shù)范圍內(nèi)的一個凸函數(shù)瑟慈， $D$ 是一個隨機變量桃移，那么函數(shù) $G$ = $\mathbb E\{g(y?D)\}$ 仍然是一個凸函數(shù)。

? 記 $y$ 葛碧， $\bar{y}$ 是任意兩個數(shù)借杰， $\alpha \in (0,1)$ ， $\bar{\alpha}=1-\alpha$ .

$\begin{aligned}\alpha G(y)+\bar{\alpha} G(\bar{y}) &=\alpha \mathbb E\{g(y-D)\}+\bar{\alpha} \mathbb E\{g(\bar y-D)\}\\ &= \mathbb E\{\alpha * g(y-D) + \bar{\alpha} *g(\bar y-D)\}\\ &\ge \mathbb E\{g(\alpha*y + \bar{\alpha}*\bar y -D) \}\\ &= G(\alpha*y + \bar{\alpha}*\bar y) \\ \end{aligned}$
? 證畢。

然后我們證明 $Q_{t}({y_t,d_{[t-1]}})$ 是關(guān)于 $y_t$ 的凸函數(shù)崎弃。首先 $t=T$ 時苗胀，

$Q_{T}({y_T,d_{[T-1]}})= -c_{T}*y_{T}+\min_{x_T \ge y_T} \quad \mathbb c_Tx_T+E\{b_T[d_T-x_T]_{+}+h_T[x_T-d_T]_{+}|D_{[T-1]}=d_{[T-1]}\} \tag{1-16}$

記 $\bar Q(x_T,d_{[T-1]})=c_Tx_T+E\{b_T[d_T-x_T]_{+}+h_T[x_T-d_T]_{+}|D_{[T-1]}=d_{[T-1]}\}$ ，那么依據(jù)章節(jié)1.1.1中的分析粘都，該函數(shù)是一個關(guān)于 $x_T$ 的凸函數(shù)。給定 $d_{[T-1]}$ 刷袍，記 $\bar Q(x_T,d_{[T-1]})$ 關(guān)于 $x_T$ 最優(yōu)解為 $x_T^{*}$ 翩隧，那么 $Q_{T}({y_T,d_{[T-1]}})=-c_{T}*y_{T}+\bar Q(\max\{x_T^{*},y_t\},d_{[T-1]})$

注意函數(shù) $\bar Q(\max\{x_T^{*},y_T\},d_{[T-1]})$ 是關(guān)于 $y_T$ 的凸函數(shù)。關(guān)于它的證明略呻纹，可依據(jù)二次函數(shù)畫圖理解堆生。那么 $Q_{T}({y_T,d_{[T-1]}})$ 是關(guān)于 $y_T$ 的凸函數(shù)。

我們再來觀察 $Q_{T-1}({y_{T-1},d_{[T-2]}})$ 雷酪，如式（1-13）所示淑仆，目標(biāo)函數(shù)中與 $x_{T-1}$ 相關(guān)的部分可以寫為關(guān)于 $x_{T-1}$ 的凸函數(shù)（注意包含了一個仿射變換，以及一個求期望運算哥力，都是保凸的)蔗怠。該凸函數(shù)再約束 $x_{T-1}\ge y_{T-1}$ 下求最優(yōu)值，那么所得目標(biāo)函數(shù)是一個關(guān)于 $y_{T-1}$ 的函數(shù)吩跋，同上寞射，該函數(shù)關(guān)于 $y_{T-1}$ 凸。進而 $Q_{T-1}({y_{T-1},d_{[T-2]}})$ 是關(guān)于 $y_{T-1}$ 的凸函數(shù)锌钮。

以此類推桥温，可證明 $Q_{t}({y_t,d_{[t-1]}})$ 是關(guān)于 $y_t$ 的凸函數(shù)。

那么依據(jù)仿射變換跟期望運算的保凸性梁丘，可知優(yōu)化問題（1-15)的目標(biāo)函數(shù)時一個凸函數(shù)侵浸，無論"階段獨立"是否成立。

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

人面猴
序言：七十年代末氛谜，一起剝皮案震驚了整個濱河市掏觉，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌值漫，老刑警劉巖澳腹，帶你破解...
沈念sama閱讀 218,386評論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異，居然都是意外死亡遵湖，警方通過查閱死者的電腦和手機悔政，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,142評論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來延旧，“玉大人谋国，你說我怎么就攤上這事∏” “怎么了芦瘾？”我有些...
開封第一講書人閱讀 164,704評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長集畅。經(jīng)常有香客問我近弟，道長，這世上最難降的妖魔是什么挺智？我笑而不...
開封第一講書人閱讀 58,702評論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任祷愉，我火速辦了婚禮，結(jié)果婚禮上赦颇，老公的妹妹穿的比我還像新娘二鳄。我一直安慰自己，他們只是感情好媒怯，可當(dāng)我...
茶點故事閱讀 67,716評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布订讼。她就那樣靜靜地躺著，像睡著了一般扇苞。火紅的嫁衣襯著肌膚如雪欺殿。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,573評論 1贊 305
城市分裂傳說
那天鳖敷，我揣著相機與錄音脖苏，去河邊找鬼。笑死哄陶，一個胖子當(dāng)著我的面吹牛帆阳，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播屋吨，決...
沈念sama閱讀 40,314評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼山宾！你這毒婦竟也來了至扰？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,230評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤资锰，失蹤者是張志新（化名）和其女友劉穎敢课，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,680評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡直秆，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,873評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年濒募，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片圾结。...
茶點故事閱讀 39,991評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡瑰剃，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出筝野，到底是詐尸還是另有隱情晌姚，我是刑警寧澤，帶...
沈念sama閱讀 35,706評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布歇竟，位于F島的核電站挥唠，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏焕议。R本人自食惡果不足惜宝磨，卻給世界環(huán)境...
茶點故事閱讀 41,329評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望盅安。院中可真熱鬧唤锉，春花似錦、人聲如沸宽堆。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,910評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽畜隶。三九已至壁肋，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間籽慢，已是汗流浹背浸遗。一陣腳步聲響...
開封第一講書人閱讀 33,038評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留箱亿，地道東北人跛锌。一個月前我還...
沈念sama閱讀 48,158評論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像届惋，于是被迫代替她去往敵國和親髓帽。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,941評論 2贊 355

隨機規(guī)劃模型與理論系列-002：報童問題的機會約束模型與多階段模型

1.1.2 機會約束模型

嚴格的值約束

寬松的概率約束

1.1.3 多階段模型（multistage models）

推薦閱讀更多精彩內(nèi)容