【正文】 DVD在線租賃決策優(yōu)化模型摘 要：本文建立了關(guān)于DVD在線租賃業(yè)務(wù)一系列問題的數(shù)學(xué)模型。首先，建立概率模型，并得到DVD的最少需求數(shù)量。接下來(lái)給出了目標(biāo)規(guī)劃模型建立最優(yōu)分配方案，在模型的求解過程中，先后給出了三種近似算法：模擬退火算法、貪婪算法和改進(jìn)貪婪算法。再建立一調(diào)度模型使得DVD數(shù)量最少，分配方案最優(yōu)。本論文所建模型理論基礎(chǔ)較完善，算法簡(jiǎn)潔快速，可操作性強(qiáng)，在計(jì)算機(jī)上對(duì)給定數(shù)據(jù)可以實(shí)時(shí)得到結(jié)果，因此有較強(qiáng)的實(shí)用性；并且只需經(jīng)過簡(jiǎn)單的修改便可解決類似問題，易于推廣。關(guān)鍵詞：DVD在線租賃；正態(tài)分布；線性規(guī)劃；貪婪算法；模擬退火算法。 改進(jìn)貪婪算法The policymaking optimization model about DVD online rentsAbstract: This article established online has rented service a series of questions about DVD the mathematical model. First, establishes the probabilistic model, and obtains DVD the least demands quantity. Met down has produced the target programming model establishment most superior assignment plan, in the model solution process, has produced three approximate methods successively: Simulation annealing algorithm, greedy algorithm and improvement greedy algorithm. Again establishes a dispatch model to cause the DVD quantity few, the assignment plan is most superior. The present paper modeling rationale consummates, the algorithm succinct is fast, feasibility, to assigns the data on the puter to be possible realtime to obtain the result, therefore has the strong usability。 And only must pass through the simple revision then to be possible to solve the similar problem, is easy to promote.Key words: DVD online rents。 Normal distribution。 Linear programming。 Greedy algorithm。 Simulation annealing algorithm。 Improves the greedy algorithm 一、緒論隨著信息時(shí)代的到來(lái)，網(wǎng)絡(luò)成為人們生活中越來(lái)越不可或缺的元素之一。許多網(wǎng)站利用其強(qiáng)大的資源和知名度，面向其會(huì)員群提供日益專業(yè)化和便捷化的服務(wù)。音像制品的在線租賃就是一種可行的服務(wù)?？紤]如下的在線DVD租賃問題。顧客繳納一定數(shù)量的月費(fèi)成為會(huì)員，訂購(gòu)DVD租賃服務(wù)。會(huì)員對(duì)哪些DVD有興趣，只要在線提交訂單，網(wǎng)站就會(huì)通過快遞的方式盡可能滿足要求。會(huì)員提交的訂單包括多張DVD，這些DVD是基于其偏愛程度排序的。網(wǎng)站會(huì)根據(jù)手頭現(xiàn)有的DVD數(shù)量和會(huì)員的訂單進(jìn)行分發(fā)。每個(gè)會(huì)員每個(gè)月租賃次數(shù)不得超過2次，每次獲得3張DVD。會(huì)員看完3張DVD之后，只需要將DVD放進(jìn)網(wǎng)站提供的信封里寄回（郵費(fèi)由網(wǎng)站承擔(dān)），就可以繼續(xù)下次租賃?？紤]以下問題：網(wǎng)站正準(zhǔn)備購(gòu)買一些新的DVD，通過問卷調(diào)查1000個(gè)會(huì)員，得到了愿意觀看這些DVD的人數(shù)（表1給出了其中5種DVD的數(shù)據(jù)）。此外，歷史數(shù)據(jù)顯示，60%的會(huì)員每月租賃DVD兩次，而另外的40%只租一次。假設(shè)網(wǎng)站現(xiàn)有10萬(wàn)個(gè)會(huì)員，對(duì)表1中的每種DVD來(lái)說(shuō)，應(yīng)該至少準(zhǔn)備多少?gòu)垼拍鼙ＷC希望看到該DVD的會(huì)員中至少50%在一個(gè)月內(nèi)能夠看到該DVD？如果要求保證在三個(gè)月內(nèi)至少95%的會(huì)員能夠看到該DVD呢？表2中列出了網(wǎng)站手上100種DVD的現(xiàn)有張數(shù)和當(dāng)前需要處理的1000位會(huì)員的在線訂單（表2的具體數(shù)據(jù)可從），如何對(duì)這些DVD進(jìn)行分配，才能使會(huì)員獲得最大的滿意度？要求具體列出前30位會(huì)員（即C0001~C0030）分別獲得哪些DVD。繼續(xù)考慮表2，并假設(shè)表2中DVD的現(xiàn)有數(shù)量全部為0。如果你是網(wǎng)站經(jīng)營(yíng)管理人員，你如何決定每種DVD的購(gòu)買量，以及如何對(duì)這些DVD進(jìn)行分配，才能使一個(gè)月內(nèi)95%的會(huì)員得到他想看的DVD，并且滿意度最大？從網(wǎng)站經(jīng)營(yíng)管理人員的角度考慮在DVD的需求預(yù)測(cè)、購(gòu)買和分配中還有哪些重要問題值得研究？提出問題，并嘗試建立相應(yīng)的數(shù)學(xué)模型。表1 對(duì)1000個(gè)會(huì)員調(diào)查的部分結(jié)果DVD名稱DVD1DVD2DVD3DVD4DVD5愿意觀看的人數(shù)200100502510二、模型假設(shè)和符號(hào)說(shuō)明（一）模型假設(shè)租賃周期為半個(gè)月或一個(gè)月，凡半個(gè)月內(nèi)還回DVD的會(huì)員均認(rèn)定為每個(gè)月租賃2次的會(huì)員，否則為只租賃1次的會(huì)員；每個(gè)會(huì)員每個(gè)月只能提交一次訂單，提交訂單時(shí)間為上月月末；一個(gè)月為30天，分為上半個(gè)月和下半個(gè)月，每月的1日和16日網(wǎng)站根據(jù)用戶訂單對(duì)DVD進(jìn)行分配； 會(huì)員租賃成功是指該會(huì)員必須獲得3張DVD且此3張DVD均為該會(huì)員在訂單中所選中的，否則均為租賃不成功；租賃不成功即認(rèn)為沒有得到想看的DVD；每個(gè)人每張碟月內(nèi)只租一次；網(wǎng)站在每次出租DVD碟的時(shí)候，將手頭上的碟要盡可能的租出去；會(huì)員提交的定單包括多張DVD碟，這些DVD碟是根據(jù)會(huì)員的偏愛程度來(lái)排序的；
網(wǎng)站每次進(jìn)行分配時(shí)，只考慮網(wǎng)站現(xiàn)有DVD張數(shù)；網(wǎng)站只在每月的1日購(gòu)買新碟，其余時(shí)間均不購(gòu)碟；1不愿意觀看某種DVD碟的會(huì)員不會(huì)租看該DVD碟；1不考慮碟片在流通和使用過程中的自然損壞、遺失；1會(huì)員對(duì)DVD碟的偏愛程度由0，1，…，10來(lái)表示，數(shù)字越小表示會(huì)員的偏愛程度越高，數(shù)字0表示對(duì)應(yīng)的DVD當(dāng)前不在會(huì)員的在線訂單中。 （二）符號(hào)說(shuō)明 ：第i種DVD碟應(yīng)準(zhǔn)備的數(shù)目； ：將第i種DVD碟第k次給第j類會(huì)員的數(shù)目，k=1,…,6。j=1,2； ：第i種DVD碟愿意觀看的人數(shù)； ：第號(hào)會(huì)員租賃期結(jié)束對(duì)網(wǎng)絡(luò)公司服務(wù)的滿意度，；；：群體滿意度；：第號(hào)會(huì)員對(duì)第種DVD的偏愛程度 ；；：第號(hào)會(huì)員對(duì)第種DVD的偏愛程度指標(biāo)，且 ，；；：第號(hào)會(huì)員是否租賃到第種DVD，若是，則取值為1；否，則取值為0，；； ：第種DVD的購(gòu)買量 ，；：在一月內(nèi)可使至少95%的會(huì)員租賃到第種DVD的最小碟數(shù)（由問題1的計(jì)算知它可看作的上限）；：第i種DVD碟每月租出的次數(shù)；：網(wǎng)站現(xiàn)有會(huì)員的人數(shù)；：第種DVD被選中的概率；：第種DVD沒被選中的概率；：每月租賃DVD一次的會(huì)員的比例；：每月租賃DVD二次的會(huì)員的比例；：第種DVD應(yīng)準(zhǔn)備的數(shù)量；：一個(gè)月內(nèi)對(duì)第種DVD；：DVD每月可用次數(shù)的數(shù)學(xué)期望值。:某月內(nèi)對(duì)第種DVD需求的人數(shù)上限。三、模型的建立與求解（一）問題1考慮到會(huì)員租碟的實(shí)際情況，表1 中給出的選擇某種DVD 的人數(shù)可以認(rèn)為是某月選擇該DVD 人數(shù)的數(shù)學(xué)期望,每月實(shí)際選擇該DVD 的人數(shù)會(huì)在其周圍波動(dòng),我們認(rèn)為對(duì)第種碟片的總需求可以用正態(tài)分布近似(此處),可以算出第種DVD 的需求人數(shù)上限(在一定置信區(qū)間下,)，只要在租借過程中滿足上限的一定人數(shù)比例 (50%)即可,假設(shè)第種DVD 購(gòu)買張。我們考慮需要DVD 最多的情況：借一次的會(huì)員在一個(gè)月的最后一天歸還，借兩次的會(huì)員在一個(gè)月的最后一天第二次歸還，那么對(duì)于一張碟來(lái)說(shuō)借一次的會(huì)員使得它流通了一次,而借兩次的會(huì)員使得它流通了兩次,這相當(dāng)于該DVD 的每月可用次數(shù)為，對(duì)于本題目來(lái)說(shuō)，即，要求一個(gè)月至少有需求的會(huì)員能得到滿足，即 (1) 求出的最小值。用Matlab 下的上限值分別為：帶入公式(1)解得：對(duì)于三個(gè)月的情況,想當(dāng)于一個(gè)月情況的三次累積,三個(gè)月的DVD 流通次數(shù)是一個(gè)月的3倍, 上限 值不變,所得公式為： (2)代入數(shù)據(jù)計(jì)算得（二）問題2表2中給出了會(huì)員對(duì)想看的碟的偏愛程度，因此我們可根據(jù)會(huì)員對(duì)碟的偏好程度定義其滿意度，定義如下：定義1（個(gè)體滿意度） 如果單個(gè)會(huì)員作為個(gè)體租賃了該網(wǎng)站三張DVD且全都是自己選中的DVD，那么其個(gè)體滿意度為該個(gè)體對(duì)這三張DVD的偏愛程度指標(biāo)之和除以30所得百分比；若未能租到三張或三張中有未被個(gè)體選中的DVD，則其滿意度為0。即. 定義2（群體滿意度） 所有個(gè)體滿意度之和，即為=。
問題2的目標(biāo)規(guī)劃模型為： max =. 。模擬退火算法近似求解算法步驟： ① 給定起止“溫度”，、和退化速度；模擬參數(shù)初始化；② 若，轉(zhuǎn)③，否則算法停止，輸出，并計(jì)算；③ 計(jì)算目標(biāo)函數(shù)；④ 隨機(jī)產(chǎn)生，若則正向調(diào)整，否則反向調(diào)整⑤ 判斷是否滿足約束條件，若滿足，轉(zhuǎn)⑥，否則轉(zhuǎn)④；⑥ 計(jì)算目標(biāo)函數(shù)，若，接受新值，轉(zhuǎn)②；否則若，也接受新值，轉(zhuǎn)②；否則轉(zhuǎn)④ 算法程序見附錄3。由于模擬退火算法不能在短時(shí)間給出問題2的最優(yōu)解，我們嘗試用別的算法來(lái)代替模擬算法以求得相對(duì)較好的解，近似作為問題2的最優(yōu)解。這里我們選擇貪婪算法，主要是因?yàn)樗茉谏倭坑?jì)算的基礎(chǔ)上，可在正確猜想且不用急于考慮以后的情況下，來(lái)一步步地構(gòu)筑解，每一步均可建立在局部最優(yōu)解的基礎(chǔ)上，而每一步又可擴(kuò)大了部分解的規(guī)模，做出的選擇產(chǎn)生最大的直接收益。這對(duì)于網(wǎng)站經(jīng)營(yíng)者來(lái)說(shuō)是其操作性比較強(qiáng)，且實(shí)用性也比較強(qiáng)，因此這種算法對(duì)于本題應(yīng)當(dāng)是非常有效的。貪婪算法求解問題2中只需要考慮在DVD現(xiàn)有數(shù)量給定條件下要求出會(huì)員獲得最大滿意度，我們暫不考慮