毕业论文（设计）dvd在线租赁决策优化模型

DVD在线租赁决策优化模型摘要：本文建立了关于DVD在线租赁业务一系列问题的数学模型。首先，建立概率模型，并得到DVD的最少需求数量。接下来给出了目标规划模型建立最优分配方案，在模型的求解过程中，先后给出了三种近似算法：模拟退火算法、贪婪算法和改进贪婪算法。再建立一调度模型使得DVD数量最少，分配方案最优。本论文所建模型理论基础较完善，算法简洁快速，可操作性强，在计算机上对给定数据可以实时得到结果，因此有较强的实用性；并且只需经过简单的修改便可解决类似问题，易于推广。关键词：DVD在线租赁；正态分布；线性规划；贪婪算法；模拟退火算法;改进贪婪算法Thepolicy-makingoptimizationmodelaboutDVDon-linerentsAbstract:Thisarticleestablishedon-linehasrentedserviceaseriesofquestionsaboutDVDthemathematicalmodel.First,establishestheprobabilisticmodel,andobtainsDVDtheleastdemandsquantity.Metdownhasproducedthetargetprogrammingmodelestablishmentmostsuperiorassignmentplan,inthemodelsolutionprocess,hasproducedthreeapproximatemethodssuccessively:Simulationannealingalgorithm,greedyalgorithmandimprovementgreedyalgorithm.AgainestablishesadispatchmodeltocausetheDVDquantityfew,theassignmentplanismostsuperior.Thepresentpapermodelingrationaleconsummates,thealgorithmsuccinctisfast,feasibility,toassignsthedataonthecomputertobepossiblereal-timetoobtaintheresult,thereforehasthestrongusability;Andonlymustpassthroughthesimplerevisionthentobepossibletosolvethesimilarproblem,iseasytopromote.Keywords:DVDon-linerents;Normaldistribution;Linearprogramming;Greedyalgorithm;Simulationannealingalgorithm;Improvesthegreedyalgorithm一、绪论随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。音像制品的在线租赁就是一种可行的服务。考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，1订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。考虑以下问题：1、网站正准备购买一些新的DVD，通过问卷调查1000个会员，得到了愿意观看这些DVD的人数（表1给出了其中5种DVD的数据）。此外，历史数据显示，60%的会员每月租赁DVD两次，而另外的40%只租一次。假设网站现有10万个会员，对表1中的每种DVD来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD呢？2、表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单（表2的具体数据可从下载），如何对这些DVD进行分配，才能使会员获得最大的满意度？要求具体列出前30位会员（即C0001~C0030）分别获得哪些DVD。3、继续考虑表2，并假设表2中DVD的现有数量全部为0。如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4、从网站经营管理人员的角度考虑在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？提出问题，并尝试建立相应的数学模型。表1对1000个会员调查的部分结果DVD名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数2001005025102二、模型假设和符号说明（一）模型假设1、租赁周期为半个月或一个月，凡半个月内还回DVD的会员均认定为每个月租赁2次的会员，否则为只租赁1次的会员；2、每个会员每个月只能提交一次订单，提交订单时间为上月月末；3、一个月为30天，分为上半个月和下半个月，每月的1日和16日网站根据用户订单对DVD进行分配；4、会员租赁成功是指该会员必须获得3张DVD且此3张DVD均为该会员在订单中所选中的，否则均为租赁不成功；5、租赁不成功即认为没有得到想看的DVD；6、每个人每张碟月内只租一次；7、网站在每次出租DVD碟的时候，将手头上的碟要尽可能的租出去；8、会员提交的定单包括多张DVD碟，这些DVD碟是根据会员的偏爱程度来排序的；9、网站每次进行分配时，只考虑网站现有DVD张数；10、网站只在每月的1日购买新碟，其余时间均不购碟；11、不愿意观看某种DVD碟的会员不会租看该DVD碟；12、不考虑碟片在流通和使用过程中的自然损坏、遗失；13、会员对DVD碟的偏爱程度由0，1，…，10来表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。（二）符号说明)(ix：第i种DVD碟应准备的数目；)(ikjx：将第i种DVD碟第k次给第j类会员的数目，k=1,…,6;j=1,2；)(id：第i种DVD碟愿意观看的人数；jI：第j号会员租赁期结束对网络公司服务的满意度，2,1k；31000,,1j；E：群体满意度；ijC：第j号会员对第i种DVD的偏爱程度100,,1i；1000,,1j；ijR：第j号会员对第i种DVD的偏爱程度指标，且ijijCR110)(00)()(ijijCC，100,,1i；1000,,1j；ijS：第j号会员是否租赁到第i种DVD，若是，则取值为1；否，则取值为0，100,,1i；1000,,1j；iV：第i种DVD的购买量，100,,1i；iM：在一月内可使至少95%的会员租赁到第i种DVD的最小碟数（由问题1的计算知它可看作iV的上限）；in：第i种DVD碟每月租出的次数；m：网站现有会员的人数；jp：第j种DVD被选中的概率；jq：第j种DVD没被选中的概率；：每月租赁DVD一次的会员的比例；：每月租赁DVD二次的会员的比例；jd：第j种DVD应准备的数量；j：一个月内对第j种DVD；n：DVD每月可用次数的数学期望值;jQ:某月内对第j种DVD需求的人数上限。三、模型的建立与求解（一）问题1考虑到会员租碟的实际情况，表1中给出的选择某种DVD的人数可以4认为是某月选择该DVD人数的数学期望,每月实际选择该DVD的人数会在其周围波动,我们认为对第j种碟片的总需求可以用正态分布(,)jjjNmpmpq近似(此处100000m),可以算出第j种DVD的需求人数上限jQ(在一定置信区间下,这里我们选取0.95)，只要在租借过程中满足上限jQ的一定人数比例j(50%)即可,假设第j种DVD购买jd张。我们考虑需要DVD最多的情况：借一次的会员在一个月的最后一天归还，借两次的会员在一个月的最后一天第二次归还，那么对于一张碟来说借一次的会员使得它流通了一次,而借两次的会员使得它流通了两次,这相当于该DVD的每月可用次数n为12jjdd，对于本题目来说，0.4,0.6,即1.6jd，要求一个月至少50%有需求的会员能得到满足，即1.6jjjdQ(1)求出jd的最小值。用Matlab求得置信度为0.95下的上限值分别为：120209Q210157Q35114Q42582Q51052Q带入公式(1)解得：16316d23174d31598d4807d5329d5对于三个月的情况,想当于一个月情况的三次累积,三个月的DVD流通次数是一个月的3倍,上限jQ值不变,所得公式为：4.80.95jjdQ(2)代入数据计算得14000d22011d31013d4512d5209d（二）问题2表2中给出了会员对想看的碟的偏爱程度，因此我们可根据会员对碟的偏好程度定义其满意度，定义如下：定义1（个体满意度）如果单个会员作为个体租赁了该网站三张DVD且全都是自己选中的DVD，那么其个体满意度为该个体对这三张DVD的偏爱程度指标之和除以30所得百分比；若未能租到三张或三张中有未被个体选中的DVD，则其满意度为0。即30/)(1001ijjijjRSI.100,,1i定义2（群体满意度）所有个体满意度之和，即为E=10001iiI。问题2的目标规划模型为：maxE=10001iiIs.t.30/)(1001ijjijjRSI100,,1i610001)(jiijdS100,,1i31001)(iijS1000,,1j10或ijS100,,1i;1000,,1j1、模拟退火算法近似求解算法步骤：①给定起止“温度”，100000T、10T和退化速度9.0；模拟参数初始化ijS；②若0TT，转③，否则算法停止，输出ijS，并计算10001jjI；③计算目标函数old10001jjI；④随机产生ijS，若5.01,0rand则正向调整ijS，否则反向调整ijS⑤判断是否满足约束条件，若满足，转⑥，否则转④；⑥计算目标函数new10001jjI，oldnewE，若0E，接受新值，TT转②；否则若)1,0(exprandTE，也接受新值，TT转②；否则转④算法程序见附录3。由于模拟退火算法不能在短时间给出问题2的最优解，我们尝试用别的算法来代替模拟算法以求得相对较好的解，近似作为问题2的最优解。这里我们选择贪婪算法，主要是因为它能在少量计算的基础上，可在正确猜想且不用急于考虑以后的情况下，来一步步地构筑解，每一步均可建立在局部最优解的基础上，而每一步又可扩大了部分解的规模，做出的选择产生最大的直接收益。这对于网站经营者来说是其操作性比较强，且实用性也比较强，因此这种算法对于本题应当是非常有效的。72、贪婪算法求解问题2中只需要考虑在DVD现有数量给定条件下要求出会员获得最大满意度，我们暂不考虑在半个月后会员所租DVD的归还与否以及后半个月会员的租赁情况。而只考虑会员个体满意度在前半月租赁期的大小。要满足达到最大的个体满意度，经分析，我们可以将其转化为：使得每一种DVD的每一张都能优先满足偏爱程度高的会员。（1）算法基本思想第一次分配（针对各种DVD中偏爱程度为1所对应会员进行分配）先考虑偏爱DVD1程度为1的各个会员，若全能满足，则将DVD1进行分配，若不够，可选取会员号排序靠前的会员，并将DVD1全部进行