DVD在線租賃方案的優(yōu)化模型

1、DVD在線租賃方案的優(yōu)化模型何榮堅(jiān)、龐淑婷、曹國威摘 要本文對DVD在線租賃的需求預(yù)測、購買與分配等相關(guān)問題，進(jìn)行合理的簡化假設(shè)，得到該問題的數(shù)學(xué)模型.對于DVD張數(shù)問題，根據(jù)需求預(yù)測表（題中表1），計(jì)算租賃周期上、下限的平均值，應(yīng)用圖論知識，利用會(huì)員對DVD的偏好程度建立二部圖和圖論度的計(jì)算得出對應(yīng)不同平均租賃周期的DVD數(shù)量結(jié)果.針對DVD的現(xiàn)有張數(shù)和訂單數(shù)，給出了權(quán)重矩陣和滿意度函數(shù)，建立以最大整體滿意度為單目標(biāo)的0-1整數(shù)規(guī)劃模型，利用Lingo8.0軟件中的ole函數(shù)從Excel中讀取權(quán)重系數(shù)矩陣，求解出最大整體滿意度和其分配方案.利用在線訂單，以最大整體滿意度和最小購買量為多目標(biāo)的

2、0-1整數(shù)規(guī)劃模型，通過線性加權(quán)法化多目標(biāo)為單目標(biāo)規(guī)劃，利用Lingo8.0軟件求解出當(dāng)時(shí)，其最大整體滿意度分別為980.48，1000，978.3，1000，其最小購買量分別為981，1475，1805，2085.從網(wǎng)站角度考慮，分析需求預(yù)測、購買分配中聯(lián)系的參變量，確定了幾個(gè)值得研究的問題，提出并建立了以網(wǎng)站最大收益和最大整體滿意度為多目標(biāo)的規(guī)劃模型.關(guān)鍵詞：0-1整數(shù)規(guī)劃；租賃周期；滿意度1 問題的提出考慮如下的在線DVD租賃問題.顧客繳納一定數(shù)量的月費(fèi)成為會(huì)員，訂購DVD租賃服務(wù).會(huì)員只要在線提交訂單，網(wǎng)站就會(huì)通過快遞的方式盡可能滿足要求.會(huì)員提交的訂單包括多張DVD，這些DVD是基于

3、其偏愛程度排序的.網(wǎng)站會(huì)根據(jù)現(xiàn)有的DVD數(shù)量和會(huì)員的訂單進(jìn)行分發(fā). 請考慮以下問題：1）通過問卷調(diào)查1000個(gè)會(huì)員，得到了愿意觀看這些DVD的人數(shù).假設(shè)網(wǎng)站現(xiàn)有10萬個(gè)會(huì)員，對其中5種DVD來說，應(yīng)該至少準(zhǔn)備多少張，才能保證希望看到該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ì)員的在線訂單，如何對這些DVD進(jìn)行分配，才能使會(huì)員獲得最大的滿意度？請具體列出前30位會(huì)員（即C0001C0030）分別獲得哪些DVD.3） 如果你是網(wǎng)站經(jīng)營管理人員，你如何決定每種D

4、VD的購買量，以及如何對這些DVD進(jìn)行分配，才能使一個(gè)月內(nèi)95%的會(huì)員得到他想看的DVD，并且滿意度最大？4）如果你是網(wǎng)站經(jīng)營管理人員，你覺得在DVD的需求預(yù)測、購買和分配中還有哪些重要問題值得研究？請明確提出你的問題，并嘗試建立相應(yīng)的數(shù)學(xué)模型.2 基本假設(shè)與符號約定2.1 基本假設(shè) 網(wǎng)站在不太長的時(shí)間內(nèi)會(huì)員人數(shù)沒有太大的變化,網(wǎng)站每月的月費(fèi)收入基本保持不變； 不同電影的DVD的價(jià)格相差不大，視作相等； 網(wǎng)站用速遞方式將DVD送交給會(huì)員，以及會(huì)員將DVD郵寄給網(wǎng)站的時(shí)間都很短，視為即日到達(dá).郵寄每次都是三只DVD，而且郵費(fèi)都是一定的； 允許網(wǎng)站不對部分訂單作處理； 每個(gè)會(huì)員每個(gè)月租賃次數(shù)不得超

5、過2次，每次獲得3張DVD.會(huì)員看完3張DVD之后，只需要將DVD放進(jìn)網(wǎng)站提供的信封里寄回（郵費(fèi)由網(wǎng)站承擔(dān)），就可以繼續(xù)下次租賃；2.1.6 60%的會(huì)員每月租賃DVD兩次，而另外的40%只租一次.2.2 符號約定：會(huì)員總數(shù)，其中在問題一中，萬；在問題二、三中，；：DVD種數(shù)，其中在問題一中，；在問題二、三中，；：會(huì)員租借DVD的平均租賃周期；：DVDj的現(xiàn)有張數(shù)，；：DVDj在會(huì)員的定單中的偏好程度，；：會(huì)員對DVDj的權(quán)重系數(shù)， ，；：對于網(wǎng)站的分配方案,會(huì)員的滿意度，；：所有會(huì)員對網(wǎng)站分配方案的總滿意度.3 DVD數(shù)量的圖論模型3.1 平均周期的上、下限會(huì)員租DVD一次（含看及周轉(zhuǎn)DVD

6、）的時(shí)間稱為租賃周期，而個(gè)會(huì)員的平均租賃周期為.一般情況下，一個(gè)月內(nèi)租DVD一次的會(huì)員當(dāng)中，最小租賃周期為15天，最大租賃周期為30天；一個(gè)月內(nèi)租DVD兩次的會(huì)員當(dāng)中，最小租賃周期為5天，最大租賃周期為15天.根據(jù)上面所述及假設(shè)2.1.6可得平均周期上、下限.計(jì)算其平均值（數(shù)學(xué)期望），有：于是3.2 圖論模型令為會(huì)員集合， 為不同DVD集合.以為頂點(diǎn)集，若會(huì)員愿意觀看，則連一條邊，則得到一個(gè)圖（二部圖）易知：中每個(gè)頂點(diǎn)的度， .的度與的度相等，即是一個(gè)簡單二部圖或偶圖.3.3 模型的轉(zhuǎn)化及求解1）設(shè)DVD應(yīng)準(zhǔn)備的張數(shù)為；2）用表示會(huì)員一個(gè)月租DVD的張數(shù)（不同），或，它是一個(gè)隨機(jī)變量；由假設(shè)3

7、及“每次獲得3張DVD”知，；3）試在中找一個(gè)生成二部子圖，（滿足或6）.3.4 DVD數(shù)量的計(jì)算1）一個(gè)月50%的滿足： 的結(jié)果為：平均租賃期910111213DVD130013334366740014334DVD215001667183420002167DVD375183491710001084DVD4376417459501542DVD5150167184200217由上表可知，當(dāng)平均租賃期為9天時(shí)，所需的五種DVD數(shù)量最少. 2）三個(gè)月95%的滿足： 的結(jié)果為：平均租賃期910111213DVD119012112232325342745DVD29511056116212671373DV

8、D3476528581634687DVD4238264291317344DVD596106117127138由上表可知，當(dāng)平均租賃期為9天時(shí)，所需的五種DVD數(shù)量也最少.4 DVD分配方案模型4.1 矩陣表示由題目的在線訂單數(shù)據(jù)表，可得到DVD的現(xiàn)有數(shù)量矩陣設(shè)表示會(huì)員在100種DVD中選擇了種，從數(shù)據(jù)表得知有三個(gè)取值8，9，10.我們知道，會(huì)員的在線訂單用數(shù)字1,2,表示，數(shù)字越小表示會(huì)員的偏愛程度越高，即數(shù)字1表示會(huì)員對于對應(yīng)DVD的偏愛程度最高，數(shù)字2,3,.,表示其偏愛程度逐漸下降.把會(huì)員的偏愛程度進(jìn)行量化：對于每一個(gè)，當(dāng)會(huì)員在100種DVD中選擇了種時(shí)，定義分段函數(shù)其中表示會(huì)員對的偏愛

9、權(quán)重系數(shù).可以建立選擇權(quán)重矩陣=4.2 滿意度函數(shù)由于每個(gè)會(huì)員每個(gè)月租賃次數(shù)不得超過2次，每次獲得3張DVD.不妨假設(shè)會(huì)員獲得其偏愛權(quán)重前三位的DVD時(shí)，會(huì)員的滿意度就達(dá)到100%.而滿意度為100%時(shí)，我們不妨假設(shè)此時(shí)滿意度為1 .考慮問題二中要處理的租賃，令于是，可以定義會(huì)員的滿意度為所有會(huì)員的整體滿意度為問題二要求對100種DVD進(jìn)行分配，使得會(huì)員獲得最大的滿意度，即要使達(dá)到最大值. 4.3 DVD數(shù)量模型在分配方案中每種DVD租賃出去的總張數(shù)不應(yīng)超過其現(xiàn)有數(shù)量（對應(yīng)模型的式（2）即DVD現(xiàn)有數(shù)量的約束.而在當(dāng)前DVD在線訂單中，每個(gè)會(huì)員只能獲得3張DVD（對應(yīng)模型的式（3）.而是一個(gè)決

10、策變量,當(dāng)=0時(shí)說明了編號為j的DVD沒有租賃給會(huì)員.根據(jù)上面模型的分析，我們以整體滿意度為目標(biāo)函數(shù)的單目標(biāo)規(guī)劃，建立0-1整數(shù)規(guī)劃模型如下：模型：4.4 模型的求解及結(jié)果在模型的求解過程中，利用Lingo8.0軟件中的ole函數(shù)直接將權(quán)重系數(shù)矩陣（1000100）（此權(quán)重系數(shù)矩陣是電子表格的格式）輸入到內(nèi)存，通過max函數(shù)編程求解10萬個(gè)決策變量的線性規(guī)劃模型（程序段見附錄1），可得局部最優(yōu)解如下表所示（列出會(huì)員編號為C0001C0030的個(gè)人滿意度和分配方案）：會(huì)員編號個(gè)人滿意度分配到的DVD的編號會(huì)員編號個(gè)人滿意度分配到的DVD的編號C00010.7916784198C00160.962

11、96108497C00020.9629664462C00171475167C00030.95238325080C00181416078C0004171841C00190.88889666786C00051116668C00201456189C00060.96296195366C00210.92593455053C00070.83333266681C00221385557C00080.48148263135C00231298195C000915378100C00240.96296374176C00100.81481415585C00250.9629696981C00110.95833596366

12、C00261226895C00120.8518523141C00270.77778505878C00131217896C0028183482C00140.88889235289C00290.96296263055C00150.74074136685C00300.92593376298在此種方案中，計(jì)算出1000個(gè)會(huì)員的總滿意度為：.5 DVD購買量與分配方案模型5.1 數(shù)學(xué)模型問題三要求站在網(wǎng)站角度考慮，如何購進(jìn)最少DVD同時(shí)獲得要求最大的滿意度.與問題二模型相似，在滿足最大整體滿意度和最小均衡滿意度的基礎(chǔ)上，繼而考慮DVD的購買量要盡量小.于是，建立以整體滿意度（即模型中的式（5）和購買量（

13、即模型中的式（6）為三目標(biāo)函數(shù)的0-1整數(shù)規(guī)劃模型.下面討論問題三的約束條件：1）分配方案中DVD數(shù)量的約束：在此分配方案中，要使95%的會(huì)員得到他想看的DVD，即對于分配方案中的每一種DVD，其人數(shù)百分比都應(yīng)在95%以上（對應(yīng)模型的式（7）；2）會(huì)員租賃DVD數(shù)量的約束：在當(dāng)前DVD在線訂單中，每個(gè)會(huì)員只能獲得3張DVD（對應(yīng)模型的式（8）.設(shè)：購進(jìn)DVDj的張數(shù).建立模型如下所示:模型：5.2 模型的轉(zhuǎn)化、求解及結(jié)果在模型的求解過程中，我們通過線性加權(quán)法化雙目標(biāo)為單目標(biāo)規(guī)劃,其中，簡化后模型如下：這是一個(gè)0-1整數(shù)規(guī)劃模型，利用Lingo8.0軟件中的ole函數(shù)直接將權(quán)重系數(shù)矩陣（1000

14、100）（此權(quán)重系數(shù)矩陣是電子表格的格式）輸入到內(nèi)存，通過max函數(shù)編程求解，得出局部最優(yōu)解如下所示：當(dāng)平均租賃周期為 10天時(shí)，所需DVD個(gè)數(shù)有981個(gè).其中每種DVD個(gè)數(shù)分別如下表所示：DVD編號D001D002D003D004D005D006D007D008D009D010DVD張數(shù)1212913791011118DVD編號D011D012D013D014D015D016D017D018D019D020DVD張數(shù)1010910912991012DVD編號D021D022D023D024D025D026D027D028D029D030DVD張數(shù)11912791086813DVD編號D031

15、D032D033D034D035D036D037D038D039D040DVD張數(shù)101110101311710109DVD編號D041D042D043D044D045D046D047D048D049D050DVD張數(shù)17129111181081011DVD編號D051D052D053D054D055D056D057D058D059D060DVD張數(shù)13911910111091112DVD編號D061D062D063D064D065D066D067D068D069D070DVD張數(shù)9101011101010111110DVD編號D071D072D0730D074D075D076D077D078

16、D079D080DVD張數(shù)121181098710109DVD編號D081D082D083D084D085D086D087D088D089D090DVD張數(shù)967611711889DVD編號D091D092D093D094D095D096D097D098D099D100DVD張數(shù)129871381110611下面列出前三十名會(huì)員的滿意度和分配方案：會(huì)員編號個(gè)人滿意度分配到的DVD編號會(huì)員編號個(gè)人滿意度分配到的DVD編號c00010.3754816c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c001916

17、78486c00051116668c00201456189c00061161953c00210.703734553c0007182681c00221385557c00081157199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00140.703722352c00291304455c00150.703721388c0030113762平均租賃周期為：10，總滿意度為980.48.當(dāng)

18、平均租借周期為15天時(shí)，所需DVD個(gè)數(shù)有1475個(gè).其中每種DVD個(gè)數(shù)分別如下表所示：DVD編號D001D002D003D004D005D006D007D008D009D010DVD張數(shù)10181319101415161712DVD編號D011D012D013D014D015D016D017D018D019D020DVD張數(shù)14151415131914131519DVD編號D021D022D023D024D025D026D027D028D029D030DVD張數(shù)19141315191513101220DVD編號D031D032D033D034D035D036D037D038D039D040DV

19、D張數(shù)14171515191710151414DVD編號D041D042D043D044D045D046D047D048D049D050DVD張數(shù)26171317171216121617DVD編號D051D052D053D054D055D056D057D058D059D060DVD張數(shù)19131613151615141718DVD編號D061D062D063D064D065D066D067D068D069D070DVD張數(shù)16151417181515171615DVD編號D071D072D0730D074D075D076D077D078D079D080DVD張數(shù)1817121514121015

20、1514DVD編號D081D082D083D084D085D086D087D088D089D090DVD張數(shù)1491110161017121213DVD編號D091D092D093D094D095D096D097D098D099D100DVD張數(shù)1914121119121816917下面列出前三十名會(huì)員的滿意度和分配方案：會(huì)員編號個(gè)人滿意度分配到的DVD編號會(huì)員編號個(gè)人滿意度分配到的DVD編號c0001188298c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c0005111666

21、8c00201456189c00061161953c00211455365c0007182681c00221385557c00081157199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00141234352c00291304455c00151138588c0030113762平均租賃周期為：15，總滿意度為1000 .當(dāng)租借周期為18天時(shí)，所需DVD個(gè)數(shù)有1805個(gè).其中每種D

22、VD個(gè)數(shù)分別如下表所示：DVD編號D001D002D003D004D005D006D007D008D009D010DVD張數(shù)13221722131718202115DVD編號D011D012D013D014D015D016D017D018D019D020DVD張數(shù)17191718152317161922DVD編號D021D022D023D024D025D026D027D028D029D030DVD張數(shù)21182114181916121525DVD編號D031D032D033D034D035D036D037D038D039D040DVD張數(shù)18211818242113181717DVD編號D04

23、1D042D043D044D045D046D047D048D049D050DVD張數(shù)32211621201519151919DVD編號D051D052D053D054D055D056D057D058D059D060DVD張數(shù)24152015181919172122DVD編號D061D062D063D064D065D066D067D068D069D070DVD張數(shù)17191921191818211918DVD編號D071D072D0730D074D075D076D077D078D079D080DVD張數(shù)22191518171512181817DVD編號D081D082D083D084D085D0

24、86D087D088D089D090DVD張數(shù)18111212201321141516DVD編號D091D092D093D094D095D096D097D098D099D100DVD張數(shù)23171514241522191121下面列出前三十名會(huì)員的滿意度和分配方案：會(huì)員編號個(gè)人滿意度分配到的DVD的編號會(huì)員編號個(gè)人滿意度分配到的DVD的編號c00010132752c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c00050.96296216668c00200.703724589c00

25、061161953c00211455365c0007182681c00221385557c00080.703767199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00141234352c00291304455c00151138588c0030113762平均租賃周期為：18，總滿意度為：978.3 .當(dāng)租借周期為21天時(shí)，所需DVD個(gè)數(shù)有2085個(gè).其中每種DVD個(gè)數(shù)分別如下表所

26、示：DVD編號D001D002D003D004D005D006D007D008D009D010DVD張數(shù)15251926151718202115DVD編號D011D012D013D014D015D016D017D018D019D020DVD張數(shù)20221922192619182226DVD編號D021D022D023D024D025D026D027D028D029D030DVD張數(shù)24202415202218131728DVD編號D031D032D033D034D035D036D037D038D039D040DVD張數(shù)20242222272415212019DVD編號D041D042D043D

27、044D045D046D047D048D049D050DVD張數(shù)36241824241722172224DVD編號D051D052D053D054D055D056D057D058D059D060DVD張數(shù)28182318222222192425DVD編號D061D062D063D064D065D066D067D068D069D070DVD張數(shù)19222224222221242321DVD編號D071D072D073D074D075D076D077D078D079D080DVD張數(shù)25241722191714212219DVD編號D081D082D083D084D085D086D087D088D

28、089D090DVD張數(shù)20131513231524171719DVD編號D091D092D093D094D095D096D097D098D099D100DVD張數(shù)27191716281725221324下面列出前三十名會(huì)員的滿意度和分配方案：會(huì)員編號個(gè)人滿意度分配到的DVD的編號會(huì)員編號個(gè)人滿意度分配到的DVD的編號c0001188298c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c00051116668c00201456189c00061161953c00211455365c

29、0007182681c00221385557c00081157199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00141234352c00291304455c00151138588c0030113762平均租賃周期為：21，總滿意度為1000 .6 DVD的需求預(yù)測、購買和分配中的相關(guān)問題作為網(wǎng)站經(jīng)營管理人員，在DVD的需求預(yù)測、購買和分配中還有一些重要問題值得研究.6.1 變量

30、的依賴關(guān)系1）對于網(wǎng)站，需求預(yù)測與會(huì)員的偏愛程度（隨時(shí)間變化而變化，即是時(shí)間的函數(shù)）以及每個(gè)會(huì)員每次租賃DVD張數(shù)有關(guān).其中，需求預(yù)測即各種DVD的愿看人數(shù)（單位：人）.它決定了每種DVD的購買量.而購買量又與租賃周期（平均）、滿足會(huì)員百分比（題中、等）以及每次租賃張數(shù)有關(guān).2）對于網(wǎng)站來說，購買總量（價(jià)格相同時(shí)）或總價(jià)格（為的單價(jià)）最小，從而成本最小.3）購買量影響分配方案，而分配方案與（見上）、會(huì)員滿意度有關(guān)總體滿意度6.2 函數(shù)關(guān)系及模型1） 固定，是的增函數(shù).2），考慮 固定時(shí)，是的增函數(shù)；固定時(shí)，是的增函數(shù)；固定時(shí)，是的增函數(shù).3） 6.3 值得研究的問題1）租賃周期2）租賃張數(shù)3）

31、一般的租賃原則4）購買總價(jià)格5）會(huì)員人數(shù)6）一般的網(wǎng)站總收入6.4 明確的問題及數(shù)學(xué)模型6.4.1 對于會(huì)員的月費(fèi)不變，每張DVD的單價(jià)不變.試確定網(wǎng)站經(jīng)營方案（包括確定，每月租賃次數(shù)），使網(wǎng)管總收入最大.6.4.2 數(shù)學(xué)模型要使總收入增加，就要使會(huì)員人數(shù)變，就需會(huì)員滿意度高.于是其中H表示網(wǎng)站日常的開銷，如網(wǎng)頁管理費(fèi)，郵寄費(fèi)用等.約束條件：依賴關(guān)系決策變量：7 模型的討論與推廣在DVD分配方案模型中,我們只考慮到所有會(huì)員的總體滿意度函數(shù)為目標(biāo)的最大化問題,只追求總體的滿意度最大,而沒有考慮到會(huì)員之間的滿意度應(yīng)盡量均衡.故我們可以定義均衡滿意度函數(shù) :作為目標(biāo)函數(shù),這樣就使得會(huì)員之間滿意度的差距比較少,同時(shí)也達(dá)到了總體滿意度盡可能大.同理,我們也可以在DVD購買量與分配方案模型引入該函數(shù),使得解更優(yōu)化,使模型更符合現(xiàn)實(shí).參考文獻(xiàn)：1 魏宗舒等，概率論與數(shù)理統(tǒng)計(jì)教程，北京：高等教育出版社，1983年.2 王沫然，matlab6.0與科學(xué)計(jì)算，北京：電子工業(yè)出版