【正文】 DVD在線租賃決策優(yōu)化模型摘 要：本文建立了關(guān)于DVD在線租賃業(yè)務一系列問題的數(shù)學模型。首先，建立概率模型，并得到DVD的最少需求數(shù)量。接下來給出了目標規(guī)劃模型建立最優(yōu)分配方案，在模型的求解過程中，先后給出了三種近似算法：模擬退火算法、貪婪算法和改進貪婪算法。再建立一調(diào)度模型使得DVD數(shù)量最少，分配方案最優(yōu)。本論文所建模型理論基礎較完善，算法簡潔快速，可操作性強，在計算機上對給定數(shù)據(jù)可以實時得到結(jié)果，因此有較強的實用性；并且只需經(jīng)過簡單的修改便可解決類似問題，易于推廣。關(guān)鍵詞：DVD在線租賃；正態(tài)分布；線性規(guī)劃；貪婪算法；模擬退火算法。 改進貪婪算法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 一、緒論隨著信息時代的到來，網(wǎng)絡成為人們生活中越來越不可或缺的元素之一。許多網(wǎng)站利用其強大的資源和知名度，面向其會員群提供日益專業(yè)化和便捷化的服務。音像制品的在線租賃就是一種可行的服務?？紤]如下的在線DVD租賃問題。顧客繳納一定數(shù)量的月費成為會員，訂購DVD租賃服務。會員對哪些DVD有興趣，只要在線提交訂單，網(wǎng)站就會通過快遞的方式盡可能滿足要求。會員提交的訂單包括多張DVD，這些DVD是基于其偏愛程度排序的。網(wǎng)站會根據(jù)手頭現(xiàn)有的DVD數(shù)量和會員的訂單進行分發(fā)。每個會員每個月租賃次數(shù)不得超過2次，每次獲得3張DVD。會員看完3張DVD之后，只需要將DVD放進網(wǎng)站提供的信封里寄回（郵費由網(wǎng)站承擔），就可以繼續(xù)下次租賃?？紤]以下問題：網(wǎng)站正準備購買一些新的DVD，通過問卷調(diào)查1000個會員，得到了愿意觀看這些DVD的人數(shù)（表1給出了其中5種DVD的數(shù)據(jù)）。此外，歷史數(shù)據(jù)顯示，60%的會員每月租賃DVD兩次，而另外的40%只租一次。假設網(wǎng)站現(xiàn)有10萬個會員，對表1中的每種DVD來說，應該至少準備多少張，才能保證希望看到該DVD的會員中至少50%在一個月內(nèi)能夠看到該DVD？如果要求保證在三個月內(nèi)至少95%的會員能夠看到該DVD呢？表2中列出了網(wǎng)站手上100種DVD的現(xiàn)有張數(shù)和當前需要處理的1000位會員的在線訂單（表2的具體數(shù)據(jù)可從），如何對這些DVD進行分配，才能使會員獲得最大的滿意度？要求具體列出前30位會員（即C0001~C0030）分別獲得哪些DVD。繼續(xù)考慮表2，并假設表2中DVD的現(xiàn)有數(shù)量全部為0。如果你是網(wǎng)站經(jīng)營管理人員，你如何決定每種DVD的購買量，以及如何對這些DVD進行分配，才能使一個月內(nèi)95%的會員得到他想看的DVD，并且滿意度最大？從網(wǎng)站經(jīng)營管理人員的角度考慮在DVD的需求預測、購買和分配中還有哪些重要問題值得研究？提出問題，并嘗試建立相應的數(shù)學模型。表1 對1000個會員調(diào)查的部分結(jié)果DVD名稱DVD1DVD2DVD3DVD4DVD5愿意觀看的人數(shù)200100502510二、模型假設和符號說明（一）模型假設租賃周期為半個月或一個月，凡半個月內(nèi)還回DVD的會員均認定為每個月租賃2次的會員，否則為只租賃1次的會員；每個會員每個月只能提交一次訂單，提交訂單時間為上月月末；一個月為30天，分為上半個月和下半個月，每月的1日和16日網(wǎng)站根據(jù)用戶訂單對DVD進行分配； 會員租賃成功是指該會員必須獲得3張DVD且此3張DVD均為該會員在訂單中所選中的，否則均為租賃不成功；租賃不成功即認為沒有得到想看的DVD；每個人每張碟月內(nèi)只租一次；網(wǎng)站在每次出租DVD碟的時候，將手頭上的碟要盡可能的租出去；會員提交的定單包括多張DVD碟，這些DVD碟是根據(jù)會員的偏愛程度來排序的；
網(wǎng)站每次進行分配時，只考慮網(wǎng)站現(xiàn)有DVD張數(shù)；網(wǎng)站只在每月的1日購買新碟，其余時間均不購碟；1不愿意觀看某種DVD碟的會員不會租看該DVD碟；1不考慮碟片在流通和使用過程中的自然損壞、遺失；1會員對DVD碟的偏愛程度由0，1，…，10來表示，數(shù)字越小表示會員的偏愛程度越高，數(shù)字0表示對應的DVD當前不在會員的在線訂單中。 （二）符號說明 ：第i種DVD碟應準備的數(shù)目； ：將第i種DVD碟第k次給第j類會員的數(shù)目，k=1,…,6。j=1,2； ：第i種DVD碟愿意觀看的人數(shù)； ：第號會員租賃期結(jié)束對網(wǎng)絡公司服務的滿意度，；；：群體滿意度；：第號會員對第種DVD的偏愛程度 ；；：第號會員對第種DVD的偏愛程度指標，且 ，；；：第號會員是否租賃到第種DVD，若是，則取值為1；否，則取值為0，；； ：第種DVD的購買量 ，；：在一月內(nèi)可使至少95%的會員租賃到第種DVD的最小碟數(shù)（由問題1的計算知它可看作的上限）；：第i種DVD碟每月租出的次數(shù)；：網(wǎng)站現(xiàn)有會員的人數(shù)；：第種DVD被選中的概率；：第種DVD沒被選中的概率；：每月租賃DVD一次的會員的比例；：每月租賃DVD二次的會員的比例；：第種DVD應準備的數(shù)量；：一個月內(nèi)對第種DVD；：DVD每月可用次數(shù)的數(shù)學期望值。:某月內(nèi)對第種DVD需求的人數(shù)上限。三、模型的建立與求解（一）問題1考慮到會員租碟的實際情況，表1 中給出的選擇某種DVD 的人數(shù)可以認為是某月選擇該DVD 人數(shù)的數(shù)學期望,每月實際選擇該DVD 的人數(shù)會在其周圍波動,我們認為對第種碟片的總需求可以用正態(tài)分布近似(此處),可以算出第種DVD 的需求人數(shù)上限(在一定置信區(qū)間下,)，只要在租借過程中滿足上限的一定人數(shù)比例 (50%)即可,假設第種DVD 購買張。我們考慮需要DVD 最多的情況：借一次的會員在一個月的最后一天歸還，借兩次的會員在一個月的最后一天第二次歸還，那么對于一張碟來說借一次的會員使得它流通了一次,而借兩次的會員使得它流通了兩次,這相當于該DVD 的每月可用次數(shù)為，對于本題目來說，即，要求一個月至少有需求的會員能得到滿足，即 (1) 求出的最小值。用Matlab 下的上限值分別為：帶入公式(1)解得：對于三個月的情況,想當于一個月情況的三次累積,三個月的DVD 流通次數(shù)是一個月的3倍, 上限 值不變,所得公式為： (2)代入數(shù)據(jù)計算得（二）問題2表2中給出了會員對想看的碟的偏愛程度，因此我們可根據(jù)會員對碟的偏好程度定義其滿意度，定義如下：定義1（個體滿意度） 如果單個會員作為個體租賃了該網(wǎng)站三張DVD且全都是自己選中的DVD，那么其個體滿意度為該個體對這三張DVD的偏愛程度指標之和除以30所得百分比；若未能租到三張或三張中有未被個體選中的DVD，則其滿意度為0。即. 定義2（群體滿意度） 所有個體滿意度之和，即為=。
問題2的目標規(guī)劃模型為： max =. 。模擬退火算法近似求解算法步驟： ① 給定起止“溫度”，、和退化速度；模擬參數(shù)初始化；② 若，轉(zhuǎn)③，否則算法停止，輸出，并計算；③ 計算目標函數(shù)；④ 隨機產(chǎn)生，若則正向調(diào)整，否則反向調(diào)整⑤ 判斷是否滿足約束條件，若滿足，轉(zhuǎn)⑥，否則轉(zhuǎn)④；⑥ 計算目標函數(shù)，若，接受新值，轉(zhuǎn)②；否則若，也接受新值，轉(zhuǎn)②；否則轉(zhuǎn)④ 算法程序見附錄3。由于模擬退火算法不能在短時間給出問題2的最優(yōu)解，我們嘗試用別的算法來代替模擬算法以求得相對較好的解，近似作為問題2的最優(yōu)解。這里我們選擇貪婪算法，主要是因為它能在少量計算的基礎上，可在正確猜想且不用急于考慮以后的情況下，來一步步地構(gòu)筑解，每一步均可建立在局部最優(yōu)解的基礎上，而每一步又可擴大了部分解的規(guī)模，做出的選擇產(chǎn)生最大的直接收益。這對于網(wǎng)站經(jīng)營者來說是其操作性比較強，且實用性也比較強，因此這種算法對于本題應當是非常有效的。貪婪算法求解問題2中只需要考慮在DVD現(xiàn)有數(shù)量給定條件下要求出會員獲得最大滿意度，我們暫不考慮