DVD在線租賃問題（課堂PPT）

1、主講教師：董慶來主講教師：董慶來20122012年年8 8月月9 9日日20122012年數(shù)學(xué)建模競賽暑期集訓(xùn)年數(shù)學(xué)建模競賽暑期集訓(xùn)系列講座之一系列講座之一DVDDVD在線租賃在線租賃CUMCM-2005B: DVDCUMCM-2005B: DVD在線租賃在線租賃命題人：余剛先生（教授）命題人：余剛先生（教授）l時任亞馬遜公司全球供應(yīng)鏈運(yùn)營副總裁時任亞馬遜公司全球供應(yīng)鏈運(yùn)營副總裁l曾任美國德州大學(xué)奧斯汀分校管理學(xué)院曾任美國德州大學(xué)奧斯汀分校管理學(xué)院Jack G. Taylor講席教授講席教授l獲多項(xiàng)美國專利，獲多項(xiàng)美國專利，1995年創(chuàng)建美國科萊科技公司年創(chuàng)建美國科萊科技公司(CALEBTec

2、hnologiesCorp.)并任董事長和總裁并任董事長和總裁l航班管理：航班管理：2001年為美國大陸航空公司所創(chuàng)造的價年為美國大陸航空公司所創(chuàng)造的價值超過值超過6000萬美元，獲萬美元，獲2002年運(yùn)籌學(xué)與管理科學(xué)應(yīng)用年運(yùn)籌學(xué)與管理科學(xué)應(yīng)用Franz Edelman獎獎(運(yùn)籌學(xué)與管理科學(xué)應(yīng)用的運(yùn)籌學(xué)與管理科學(xué)應(yīng)用的“世界世界杯杯”)CUMCM-2005B: DVDCUMCM-2005B: DVD在線租賃在線租賃網(wǎng)上網(wǎng)上DVD在線租賃業(yè)務(wù)（在線租賃業(yè)務(wù)（2005年時的背景）年時的背景）l亞馬遜英國公司亞馬遜英國公司(amazon.co.uk) ；美國；美國和和等；歐洲等；歐洲等著名公司等著名

3、公司l租賃的租賃的DVD多達(dá)幾萬種，用戶多達(dá)幾十萬多達(dá)幾萬種，用戶多達(dá)幾十萬幾百萬，幾百萬，有的包括多個配送中心有的包括多個配送中心l題目：會員每月最多可租賃兩次，每次張題目：會員每月最多可租賃兩次，每次張DVDl第（第（1）、（）、（2）問：分別考慮購買和分發(fā)子問題）問：分別考慮購買和分發(fā)子問題l第（第（3）問：同時考慮購買和分發(fā)）問：同時考慮購買和分發(fā)l第（第（4）問：自己提出新問題，嘗試建模和求解）問：自己提出新問題，嘗試建模和求解 二、問題分析與建模 問題一問題一 網(wǎng)站購買網(wǎng)站購買DVDDVD的最優(yōu)數(shù)量的最優(yōu)數(shù)量在現(xiàn)有會員中隨機(jī)抽取在現(xiàn)有會員中隨機(jī)抽取10001000個會員進(jìn)行調(diào)查，以

4、得知愿意觀看不同個會員進(jìn)行調(diào)查，以得知愿意觀看不同DVDDVD的的人數(shù)（表人數(shù)（表1.11.1給出了其中給出了其中5 5種種DVDDVD的數(shù)據(jù)）。從歷史數(shù)據(jù)顯示，的數(shù)據(jù)）。從歷史數(shù)據(jù)顯示，60%60%的會員每的會員每月租賃月租賃DVDDVD兩次，而另外的兩次，而另外的40%40%只租一次?，F(xiàn)在我們假設(shè)網(wǎng)站現(xiàn)有只租一次?，F(xiàn)在我們假設(shè)網(wǎng)站現(xiàn)有1010萬個會萬個會員，并已經(jīng)知道會員對員，并已經(jīng)知道會員對DVDDVD的需求，以及會員每月訂的需求，以及會員每月訂DVDDVD的規(guī)律。問題是應(yīng)的規(guī)律。問題是應(yīng)該至少準(zhǔn)備多少張，才能保證希望看到該該至少準(zhǔn)備多少張，才能保證希望看到該DVDDVD的會員中至少的會

5、員中至少50%50%在一個月內(nèi)在一個月內(nèi)能夠看到？如果要求保證在三個月內(nèi)至少能夠看到？如果要求保證在三個月內(nèi)至少95%95%的會員能夠看到呢？的會員能夠看到呢？表表1.1 1.1 對對10001000個會員調(diào)查的部分結(jié)果個會員調(diào)查的部分結(jié)果DVD名稱名稱DVD1DVD2DVD3DVD4DVD5愿意觀看的人數(shù)愿意觀看的人數(shù)200100502510信息：信息： 數(shù)據(jù)是隨機(jī)抽取數(shù)據(jù)是隨機(jī)抽取10001000會員的調(diào)查數(shù)據(jù)會員的調(diào)查數(shù)據(jù) 每個會員每月至多租每個會員每月至多租2 2次次 每次租賃可租每次租賃可租3 3張（寄回可再租）；張（寄回可再租）； 4040會員每月租會員每月租1 1次，記作次，記作

6、A A類會員類會員1.1.6060會員每月租會員每月租2 2次，記作次，記作B B類會員類會員問題：問題：至少要準(zhǔn)備多少張至少要準(zhǔn)備多少張DVDDVD（上述（上述5 5種），才能保證：種），才能保證：希望看到該希望看到該DVDDVD的會員中至少的會員中至少5050能看到想看的能看到想看的DVDDVD？（一個月內(nèi)）？（一個月內(nèi)）希望看到該希望看到該DVDDVD的會員中至少的會員中至少9595能看到能看到DVDDVD？（三個月內(nèi)）（三個月內(nèi)）假設(shè)假設(shè):1、事先無法預(yù)測會員在本月訂事先無法預(yù)測會員在本月訂D v D 的次數(shù)的次數(shù)2、會員每次得到會員每次得到3 張張D V D3、假設(shè)假設(shè)60 % 的每

7、月租賃的每月租賃D V D 兩次的會員租賃的兩次的會員租賃的D V D 一個月內(nèi)可外借兩次一個月內(nèi)可外借兩次,而而40% 的每月租賃的每月租賃D V D 一次的會員租賃的一次的會員租賃的D V D 在一個月內(nèi)只能外借一在一個月內(nèi)只能外借一次次第第j 種種DVD 應(yīng)準(zhǔn)備數(shù)量（應(yīng)準(zhǔn)備數(shù)量（xj）每張光盤利用次數(shù)的期望（每張光盤利用次數(shù)的期望（E）=愿觀看人數(shù)（愿觀看人數(shù)（Pj）能看到該能看到該DVD 人數(shù)的比例（人數(shù)的比例（R）即即jjPxRE假設(shè)假設(shè):光盤第一次被每月租兩次的會員租的光盤第一次被每月租兩次的會員租的D V D 光盤一光盤一個月能利用兩次個月能利用兩次, 即可被兩個會員租到即可被兩

8、個會員租到, 被只租一次被只租一次的會員租的的會員租的D V D 光盤一個月只能利用一次光盤一個月只能利用一次每個光盤在一個月內(nèi)能利用次數(shù)的期望每個光盤在一個月內(nèi)能利用次數(shù)的期望E=2x60% + 1x 40% = 1.6 一個月的情況一個月的情況能看到該能看到該D V D 人數(shù)的比例人數(shù)的比例: R = 50 %調(diào)查的人數(shù)只占全部會員的調(diào)查的人數(shù)只占全部會員的1%, 所以數(shù)據(jù)按所以數(shù)據(jù)按100 倍擴(kuò)大倍擴(kuò)大將數(shù)值代入將數(shù)值代入jjPxRE三個月的情況三個月的情況每個光盤在三個月內(nèi)能利用的次數(shù)的期望每個光盤在三個月內(nèi)能利用的次數(shù)的期望53243222360%6(60%40%5+60%40% 4

9、)5+(60%40%3+60%40%3)4+40%34.44890E 由于能看到該由于能看到該D V D 人數(shù)的比例人數(shù)的比例: R = 95 % 將數(shù)將數(shù)值代入模型值代入模型求解并且把解向右取整求解并且把解向右取整jjPxRE問題問題1:1:網(wǎng)站購買網(wǎng)站購買DVDDVD的數(shù)量的數(shù)量( (x) )假設(shè)：每種假設(shè)：每種DVD獨(dú)立考慮（聯(lián)合考慮沒有足夠信息）獨(dú)立考慮（聯(lián)合考慮沒有足夠信息） 希望看到該希望看到該DVD的會員數(shù)量：確定？隨機(jī)！的會員數(shù)量：確定？隨機(jī)！ 保證保證一個月至少一個月至少P%有需求的會員能得到滿足有需求的會員能得到滿足? 會員希望看該會員希望看該DVD的概率為的概率為p網(wǎng)站的

10、會員總數(shù)為網(wǎng)站的會員總數(shù)為nn比較大，可用正態(tài)分布比較大，可用正態(tài)分布N(np, npq) 近似（近似（q=1-p） 二項(xiàng)分布二項(xiàng)分布N(n, p) 可近似認(rèn)為可近似認(rèn)為1個月該個月該DVD實(shí)際可用張數(shù)是實(shí)際可用張數(shù)是1.6x張張 一定置信水平下成立！一定置信水平下成立！問題問題1:1:網(wǎng)站購買網(wǎng)站購買DVDDVD的數(shù)量的數(shù)量( (x) ) 置信水平置信水平au1- a N(np, npq)a16 . 1*%PrxPa1%/6 . 1PrnpqnpPxnpqnp) 1 , 0( Nnpqnpa1%/6 . 1unpqnpPxa1*6 . 1%unpqnpPx問題問題1:1:網(wǎng)站購買網(wǎng)站購買DV

11、DDVD的數(shù)量的數(shù)量( (x) )a1*6 . 1%unpqnpPx 0.95; n=100000; P%=50%DVD名稱DVD1DVD2DVD3DVD4DVD5合計(jì)p0.20.10.050.0250.01x62903155158579732312150 推廣到個月的模型推廣到個月的模型類似考慮：張類似考慮：張DVD在三個月內(nèi)可以用多少次？在三個月內(nèi)可以用多少次？歸還規(guī)律出借規(guī)律的探討將變得復(fù)雜一些，歸還規(guī)律出借規(guī)律的探討將變得復(fù)雜一些，一般需要在更多的假設(shè)下，才能得到（如還回網(wǎng)站一般需要在更多的假設(shè)下，才能得到（如還回網(wǎng)站的的DVD是否一定能馬上分給某個需要的會員？）是否一定能馬上分給某個

12、需要的會員？）問題問題1:1:網(wǎng)站購買網(wǎng)站購買DVDDVD的數(shù)量的數(shù)量( (x) ) 其他模型：其他模型：數(shù)值模擬（仿真）：需交代詳細(xì)過程數(shù)值模擬（仿真）：需交代詳細(xì)過程（歸還規(guī)律？出借規(guī)律）（歸還規(guī)律？出借規(guī)律）其他理解：例如認(rèn)為表中給出的只是初始時段其他理解：例如認(rèn)為表中給出的只是初始時段(一一個月或半個月個月或半個月)的需求，并進(jìn)一步假設(shè)以后時段的的需求，并進(jìn)一步假設(shè)以后時段的需求持續(xù)不變或按某種規(guī)律變化需求持續(xù)不變或按某種規(guī)律變化 （排隊(duì)論？隨機(jī)決策？）（排隊(duì)論？隨機(jī)決策？）需求上限：一定置信水平下得到上限需求上限：一定置信水平下得到上限M（x = P% * M / 1.6） 問題二問

13、題二 網(wǎng)站分發(fā)網(wǎng)站分發(fā)DVDDVD的數(shù)學(xué)模型的數(shù)學(xué)模型在現(xiàn)有一定數(shù)量在現(xiàn)有一定數(shù)量DVDDVD的前提下，如何分配以使會員總的的前提下，如何分配以使會員總的滿意度最大。這與滿意度最大。這與“分配問題分配問題”或或“指派問題指派問題（Assignment problem）”有很多相同點(diǎn)。有很多相同點(diǎn)。我們可以通過一些變化來使求解我們可以通過一些變化來使求解“分配問題分配問題”的模型的模型能運(yùn)用于該問題。能運(yùn)用于該問題。 我們把問題二中我們把問題二中“100100個會員對個會員對DVDDVD的需求的需求” 理解理解為為“需要完成的需要完成的100100項(xiàng)任務(wù)項(xiàng)任務(wù)”，“2020種種DVDDVD數(shù)量數(shù)

14、量”理解理解為為“有有2020個人可以承擔(dān)這些任務(wù)個人可以承擔(dān)這些任務(wù)”，“會員對于不同會員對于不同DVDDVD的偏愛度的偏愛度”理解為理解為“不同人去完成不同工作的效不同人去完成不同工作的效率率”，通過類比就能把分配問題的模型運(yùn)用到問題二，通過類比就能把分配問題的模型運(yùn)用到問題二中了。中了。0-1規(guī)劃（最常見）規(guī)劃（最常見）分配問題最常用的方法是分配問題最常用的方法是0-10-1型整數(shù)規(guī)劃。在具體使用型整數(shù)規(guī)劃。在具體使用前，還需要將每個會員對不同前，還需要將每個會員對不同DVDDVD的偏愛度轉(zhuǎn)化為滿意的偏愛度轉(zhuǎn)化為滿意度。因?yàn)槲覀兊哪繕?biāo)是總體滿意度最大。度。因?yàn)槲覀兊哪繕?biāo)是總體滿意度最大。

15、 從表從表1.21.2中可以看到：會員的在線訂單用數(shù)字中可以看到：會員的在線訂單用數(shù)字1,2,1,2,表示，數(shù)字越小表示會員的偏愛程度越高，數(shù)表示，數(shù)字越小表示會員的偏愛程度越高，數(shù)字字0 0表示對應(yīng)的表示對應(yīng)的DVDDVD當(dāng)前不在會員的在線訂單中。通過當(dāng)前不在會員的在線訂單中。通過觀察我們用一個大于觀察我們用一個大于9 9的固定數(shù)值來減偏愛數(shù)的固定數(shù)值來減偏愛數(shù), ,把這個把這個差值作為滿意度。差值作為滿意度。1、設(shè)矩陣、設(shè)矩陣B為偏愛度矩陣，矩陣中的元素為偏愛度矩陣，矩陣中的元素bij為表為表1.2中中的偏愛數(shù)，表示第的偏愛數(shù)，表示第i個會員對個會員對DVDj的偏愛數(shù)。的偏愛數(shù)。bij越小

16、越小表示會員的滿意程度越高，表示會員的滿意程度越高，bij為為1時最高，時最高，bij為為0時表時表示客戶沒有下訂單。于是就得到了偏愛度矩陣示客戶沒有下訂單。于是就得到了偏愛度矩陣 2、設(shè)矩陣、設(shè)矩陣A為滿意度矩陣，矩陣中的元素為滿意度矩陣，矩陣中的元素aij為滿意為滿意度，表示第度，表示第i個會員對第個會員對第DVDj 的滿意度。的滿意度。 可通過如可通過如下算法獲得：下算法獲得： 20, 3 , 2 , 1;100, 3 , 2 , 120100 jibBij 20, 3 , 2 , 1;100, 3 , 2 , 100010 jibabbaijijijijij3、用、用0-1變量變量xi

17、j表示表示DVDj是否分配給第是否分配給第i個會員個會員4、用、用wj表示表示DVDj的現(xiàn)有數(shù)量的現(xiàn)有數(shù)量jiijwx 1001ijijxa5、用、用0-1變量變量yi表示第表示第i個用戶是否得到個用戶是否得到DVD2013ijijxy由以上分析可得問題二的模型：由以上分析可得問題二的模型：10020111001201max31,2,3,1000,1,0,11,2,3,100;1,2,3,20ijijijijijijjiijijijiZa xxaxwxyixyijLLL用用LINGO LINGO 數(shù)學(xué)軟件實(shí)現(xiàn)對此題數(shù)學(xué)軟件實(shí)現(xiàn)對此題0-10-1規(guī)劃模型的求解規(guī)劃模型的求解答卷中的問題：答卷中的

18、問題： 目標(biāo)定義不合理目標(biāo)定義不合理 約束不完整約束不完整 軟件使用不當(dāng)軟件使用不當(dāng)(LINGO求解容易求解容易,Why?) 問題二問題二 網(wǎng)站分發(fā)網(wǎng)站分發(fā)DVDDVD的數(shù)學(xué)模型的數(shù)學(xué)模型貪婪算法貪婪算法( 求近似解求近似解)Step1: 對于庫存的對于庫存的100 種光盤種光盤, 首先滿足所有對它偏愛首先滿足所有對它偏愛順序?yàn)轫樞驗(yàn)?的會員的需要的會員的需要, 即將每種光盤分配給所有對其偏即將每種光盤分配給所有對其偏愛順序?yàn)閻垌樞驗(yàn)? 會員會員, 如果該光盤的數(shù)目偏少無法完成此次分如果該光盤的數(shù)目偏少無法完成此次分配配, 則先分配給其中編號較小的那些會員則先分配給其中編號較小的那些會員;St

19、ep2: 對于剩余光盤對于剩余光盤, 再優(yōu)先滿足對它偏愛順序?yàn)樵賰?yōu)先滿足對它偏愛順序?yàn)? 的的會員需要會員需要, 同樣地同樣地, 如果該光盤的數(shù)目偏少無法完成此如果該光盤的數(shù)目偏少無法完成此次分配次分配, 則先分配給其中編號較小的那些會員則先分配給其中編號較小的那些會員;Step 3 :依此類推分配下去依此類推分配下去, 在在Step 3 以后分配時以后分配時,己經(jīng)擁有己經(jīng)擁有3 張光盤的會員不參加分配張光盤的會員不參加分配Step 11 : 如果還有剩下的光盤如果還有剩下的光盤, 隨機(jī)分配給尚未分隨機(jī)分配給尚未分滿的會員滿的會員, 分配結(jié)束分配結(jié)束這種貪婪算法計(jì)算量較小這種貪婪算法計(jì)算量較小

20、, 速度很快。由于上述步速度很快。由于上述步驟盡量保證了偏愛程度較高的匹配驟盡量保證了偏愛程度較高的匹配, 可以保證結(jié)果可以保證結(jié)果的近似最優(yōu)的近似最優(yōu)模型二：網(wǎng)絡(luò)優(yōu)化模型模型二：網(wǎng)絡(luò)優(yōu)化模型 最小費(fèi)用最大流最小費(fèi)用最大流12n12m3,0cj,0st, 1ija會員會員DVDaij=aij (aij 0)aij=M (aij =0)(或沒有弧或沒有弧)存在多項(xiàng)式時間算法存在多項(xiàng)式時間算法兩個模型等價嗎兩個模型等價嗎? 上海交大上海交大 問題二問題二 網(wǎng)站分發(fā)網(wǎng)站分發(fā)DVDDVD的數(shù)學(xué)模型的數(shù)學(xué)模型構(gòu)造加權(quán)有向圖構(gòu)造加權(quán)有向圖G V,E :點(diǎn)集點(diǎn)集V=source，C1,C2 ,C1000,D

21、1,D2, ,D100,terminal，其中，其中， Ci (1i1000)代表第代表第i個會員，個會員，Dj(1j100)代代表第表第j張張DVD盤，盤，source為網(wǎng)絡(luò)流的源點(diǎn)，為網(wǎng)絡(luò)流的源點(diǎn)，terminal為網(wǎng)絡(luò)流的匯點(diǎn)。為網(wǎng)絡(luò)流的匯點(diǎn)。在在source與所有的與所有的 Ci之間添加有向邊之間添加有向邊(source，Ci )， (1i1000) ，該邊具有容量，該邊具有容量3，單位流量費(fèi)用為，單位流量費(fèi)用為0；在所有在所有Dj與與terminal之間添加有向邊之間添加有向邊( Dj，terminal)，(1 j100) ，該邊的容量為第，該邊的容量為第j種種DVD的現(xiàn)有數(shù)量，單的

22、現(xiàn)有數(shù)量，單位流量費(fèi)用為位流量費(fèi)用為0根據(jù)題目中訂單，若第根據(jù)題目中訂單，若第i個會員預(yù)訂了第個會員預(yù)訂了第j種種DVD，則添加有向邊則添加有向邊(Ci ，Dj)，該邊的容量為，該邊的容量為1，單位流量，單位流量費(fèi)用為該會員對該種費(fèi)用為該會員對該種DVD 的偏愛值的偏愛值考慮到現(xiàn)實(shí)中，考慮到現(xiàn)實(shí)中，DVD 的個數(shù)為整數(shù)，我們規(guī)定圖的個數(shù)為整數(shù)，我們規(guī)定圖1中中G所有邊的流量為整數(shù)。因此，圖所有邊的流量為整數(shù)。因此，圖1中中G是一個整是一個整數(shù)流量的最小費(fèi)用最大流模型。數(shù)流量的最小費(fèi)用最大流模型。建立的圖論模型，其最小費(fèi)用最大流恰好表示了滿建立的圖論模型，其最小費(fèi)用最大流恰好表示了滿足上述最大滿

23、意度定義的分配方案，而最小費(fèi)用恰足上述最大滿意度定義的分配方案，而最小費(fèi)用恰恰代表著最大滿意度恰代表著最大滿意度王成王成, 文野文野, 俞寅濤俞寅濤, DVD租賃問題的模型設(shè)計(jì)及求租賃問題的模型設(shè)計(jì)及求解解,工程數(shù)學(xué)學(xué)報(bào)工程數(shù)學(xué)學(xué)報(bào), 2005, 7(22): 92-100在一定的假設(shè)下，把問題近似分解成前面考慮過的購買和分發(fā)兩個子在一定的假設(shè)下，把問題近似分解成前面考慮過的購買和分發(fā)兩個子問題。例如，有的論文先根據(jù)會員訂單統(tǒng)計(jì)問題。例如，有的論文先根據(jù)會員訂單統(tǒng)計(jì)DVD的需求情況，確定的需求情況，確定DVD購買量，然后用前一問中建立的模型進(jìn)行第一次分發(fā)，再對網(wǎng)站購買量，然后用前一問中建立的模

24、型進(jìn)行第一次分發(fā)，再對網(wǎng)站是否知道哪些會員租賃兩次作出一定假設(shè)，進(jìn)行第二次分發(fā)。是否知道哪些會員租賃兩次作出一定假設(shè)，進(jìn)行第二次分發(fā)。有的論文對前一問中建立的模型進(jìn)行一定修改，建立購買和分發(fā)統(tǒng)一有的論文對前一問中建立的模型進(jìn)行一定修改，建立購買和分發(fā)統(tǒng)一的多目標(biāo)數(shù)學(xué)規(guī)劃模型，且同時考慮兩次分發(fā)和服務(wù)水平約束，不過的多目標(biāo)數(shù)學(xué)規(guī)劃模型，且同時考慮兩次分發(fā)和服務(wù)水平約束，不過往往在二次分配和服務(wù)水平約束方面考慮有些缺陷。往往在二次分配和服務(wù)水平約束方面考慮有些缺陷。考慮到一個月內(nèi)可能一個會員要發(fā)貨兩次，這又是一個多階段的決策考慮到一個月內(nèi)可能一個會員要發(fā)貨兩次，這又是一個多階段的決策問題，建立隨機(jī)決策模型并尋找最優(yōu)決策是可能的（例如采用馬氏決問題，建立隨機(jī)決策模型并尋找最優(yōu)決策是可能的（例如采用馬氏決策方法），但由于后一階段決策時需要考慮前一階段哪些會員歸還了策方法），但由于后一階段決策時需要考慮前一階段哪些會員歸還了哪些哪些DVD，因此這樣建立模型的難度較大，評委們在評閱中幾乎沒有，因此這樣建立模型的難度較大，評委們在評閱中幾乎沒有見到非常成功的論文。見到非常成功的論文。采用