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

DVD在线租赁决策优化模型摘 要：本文建立了关于DVD在线租赁业务一系列问题的数学模型。首先，建立概率模型，并得到DVD的最少需求数量。接下来给出了目标规划模型建立最优分配方案，在模型的求解过程中，先后给出了三种近似算法：模拟退火算法、贪婪算法和改进贪婪算法。再建立一调度模型使得DVD数量最少，分配方案最优。本论文所建模型理论基础较完善，算法简洁快速，可操作性强，在计算机上对给定数据可以实时得到结果，因此有较强的实用性；并且只需经过简单的修改便可解决类似问题，易于推广。关键词：DVD在线租赁；正态分布；线性规划；贪婪算法；模拟退火算法; 改进贪婪算法The policy-making optimization model about DVD on-line rentsAbstract: This article established on-line 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 computer to be possible real-time 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 on-line rents; Normal distribution; Linear programming; Greedy algorithm; Simulation annealing algorithm; Improves the greedy algorithm 一、绪论随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。音像制品的在线租赁就是一种可行的服务。考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，订购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的具体数据可从3、继续考虑表2，并假设表2中DVD的现有数量全部为0。如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4、从网站经营管理人员的角度考虑在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？提出问题，并尝试建立相应的数学模型。表1 对1000个会员调查的部分结果DVD名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数200100502510二、模型假设和符号说明（一）模型假设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当前不在会员的在线订单中。 （二）符号说明 ：第i种DVD碟应准备的数目； ：将第i种DVD碟第k次给第j类会员的数目，k=1,6;j=1,2； ：第i种DVD碟愿意观看的人数； ：第号会员租赁期结束对网络公司服务的满意度，；：群体满意度；：第号会员对第种DVD的偏爱程度 ；：第号会员对第种DVD的偏爱程度指标，且 ，；：第号会员是否租赁到第种DVD，若是，则取值为1；否，则取值为0，； ：第种DVD的购买量 ，；：在一月内可使至少95%的会员租赁到第种DVD的最小碟数（由问题1的计算知它可看作的上限）；：第i种DVD碟每月租出的次数；：网站现有会员的人数；：第种DVD被选中的概率；：第种DVD没被选中的概率；：每月租赁DVD一次的会员的比例；：每月租赁DVD二次的会员的比例；：第种DVD应准备的数量；：一个月内对第种DVD；：DVD每月可用次数的数学期望值;:某月内对第种DVD需求的人数上限。三、模型的建立与求解（一）问题1考虑到会员租碟的实际情况，表1 中给出的选择某种DVD 的人数可以认为是某月选择该DVD 人数的数学期望,每月实际选择该DVD 的人数会在其周围波动,我们认为对第种碟片的总需求可以用正态分布近似(此处),可以算出第种DVD 的需求人数上限(在一定置信区间下,这里我们选取0.95)，只要在租借过程中满足上限的一定人数比例 (50%)即可,假设第种DVD 购买张。我们考虑需要DVD 最多的情况：借一次的会员在一个月的最后一天归还，借两次的会员在一个月的最后一天第二次归还，那么对于一张碟来说借一次的会员使得它流通了一次,而借两次的会员使得它流通了两次,这相当于该DVD 的每月可用次数为，对于本题目来说，即，要求一个月至少有需求的会员能得到满足，即 (1) 求出的最小值。用Matlab 求得置信度为0.95 下的上限值分别为：带入公式(1)解得：对于三个月的情况,想当于一个月情况的三次累积,三个月的DVD 流通次数是一个月的3倍, 上限 值不变,所得公式为： (2)代入数据计算得（二）问题2表2中给出了会员对想看的碟的偏爱程度，因此我们可根据会员对碟的偏好程度定义其满意度，定义如下：定义1（个体满意度） 如果单个会员作为个体租赁了该网站三张DVD且全都是自己选中的DVD，那么其个体满意度为该个体对这三张DVD的偏爱程度指标之和除以30所得百分比；若未能租到三张或三张中有未被个体选中的DVD，则其满意度为0。即. 定义2（群体满意度） 所有个体满意度之和，即为=。问题2的目标规划模型为： max =s.t. ;1、模拟退火算法近似求解算法步骤： 给定起止“温度”，、和退化速度；模拟参数初始化； 若，转，否则算法停止，输出，并计算； 计算目标函数； 随机产生，若则正向调整，否则反向调整 判断是否满足约束条件，若满足，转，否则转； 计算目标函数，若，接受新值，转；否则若，也接受新值，转；否则转 算法程序见附录3。由于模拟退火算法不能在短时间给出问题2的最优解，我们尝试用别的算法来代替模拟算法以求得相对较好的解，近似作为问题2的最优解。这里我们选择贪婪算法，主要是因为它能在少量计算的基础上，可在正确猜想且不用急于考虑以后的情况下，来一步步地构筑解，每一步均可建立在局部最优解的基础上，而每一步又可扩大了部分解的规模，做出的选择产生最大的直接收益。这对于网站经营者来说是其操作性比较强，且实用性也比较强，因此这种算法对于本题应当是非常有效的。2、贪婪算法求解问题2中只需要考虑在DVD现有数量给定条件下要求出会员获得最大满意度，我们暂不考虑在半个月后会员所租DVD的归还与否以及后半个月会员的租赁情况。而只考虑会员个体满意度在前半月租赁期的大小。要满足达到最大的个体满意度，经分析，我们可以将其转化为：使得每一种DVD的每一张都能优先满足偏爱程度高的会员。（1）算法基本思想第一次分配（针对各种DVD中偏爱程度为1所对应会员进行分配）先考虑偏爱DVD1程度为1的各个会员，若全能满足，则将DVD1进行分配，若不够，可选取会员号排序靠前的会员，并将DVD1全部进行分配；再分配DVD2，考虑偏爱DVD2程度为1 的会员，若全能满足，则将DVD2进行分配，若不够，可选取会员号排序靠前的会员，并将DVD2全部进行分配。这样一直类推到DVD100第二次分配（针对各种DVD中偏爱程度为2所对应会员进行分配）先考虑偏爱DVD1程度为2的各个会员，若全能满足，则将第一次分配剩余DVD1进行分配，若不够，可选取会员号排序靠前的会员，并将第一次分配剩余DVD1全部进行分配；再分配DVD2，考虑偏爱DVD2程度为2 的会员，若全能满足，则将前一次分配剩余DVD2进行分配，若不够，可选取会员号排序靠前的会员，并将前一次分配剩余DVD2全部进行分配。这样一直类推到DVD100按照上面所述方法，直至第十次分配。分配结束后便可得到分配DVD的一种预分配方案。（2）算法步骤：对一种DVD而言，按偏爱程度从高到低分配给会员，而不考虑分配的公平性。下面用表示会员的偏爱程度。 ； 若,转；否则算法停止，输出，计算为所得； 按递增遍历，按递增遍历，获得会员目前租赁DVD的数量； 若，且，则，,转。（3）计算结果依此方法，对表2中所给100种DVD的现有数量及1000张订单数据用VC编制程序（见附录4），运行得到计算结果见表5：表5 用贪婪算法求解问题2模型的计算结果（前30位会员）会员编号获得的DVD编号178114182982NNNNNN3431325080904718234168815116668NNN6161920536166782681NNN8NNNNNN910175370781001014415560678511195963NNN12257314598132144788092961423434652899215132452667085166104855849717475167NNN1812174160788119256667848690201718456189912124553NNN22385557NNN2329354175819524374176NNN259236981909426822688391952722385058687828NNNNNN29304455NNN3013237627098注：N表示没有得到碟片。群体满意度为=684.951.对于上表，我们发现，有几位会员没有分配到想看的DVD碟，从全部1000名会员的分配结果来看有208人在此算法下的预分配中只能分配到一张或两张甚至0张自己想看的碟，以致没能在月初成功租赁到DVD碟，导致这个月都不能成功租到碟。则该网站就至少有731张DVD碟未能成功出租。那么问题就产生了，一方面是有大量DVD可租，另一方面却大量会员又租赁不成功。这种现象是矛盾的，因此结果不是很让人满意，需要对算法进行改进。3、改进贪婪算法求解针对上述问题症结所在，只需对在经贪婪算法运算后，未能租赁到DVD的人重新实施分配。不过这种分配不再利用单纯的贪婪算法（否则，会限入死循环）。对这部分人采用如下算法： ； 若,转，否则转； 按递增遍历，按递增遍历，获得会员目前租赁DVD的数量； 若，且，则，, 转； 以递增遍历，获得会员目前的租赁DVD的数量,若则释放预分配会员的DVD资源，并从原订单中分离散出此次未分配到DVD的会员对各种DVD的喜欢程度； 以递增遍历，优先让能达到相对最大满意度且偏爱程度构成的三位最小整数较小的会员分配DVD并登记； 输出。 算法程序见附录4。计算结果见表6：表6 用改进贪婪算法求解问题2模型的计算结果（前30位会员）会员编号获得的DVD编号181141828598254462NNN343132508090471841NNN51112213466686161953NNN782681NNN8NNNNNN95378100NNN10141841556085111959616366701227314150981321447880929614235289NNN15136685NNN1661048558497175113147516718416078NNN1925666784869020456189NNN212254550536522385557NNN2329356775819524374176NNN2596981NNN26226895NNN27225058NNN2883482NNN2926304452558930376298NNN该算法的群体满意度为=773.668.从表6中我们发现，预分配中只能分配到一张或两张甚至0张自己想看的碟的会员只有99人了，比贪婪算法的结果少了107人，群体满意度也比贪婪算法的高出了86.717，且仅有304张碟未能成功出租。由此可见，改进后的贪婪算法的效果是明显的，结果也上令人满意的。（三）问题3对于问题3，我们可以考虑用问题1的模型来决定每种DVD的购买量，然后用问题2的模型来进行DVD的分配。我们根据表2中所有会员的订单统计出对100种DVD的需求量，然后用问题1的模型确定出每种DVD碟的购买量，并用问题2的模型进行分配，发现能在1个月内使全部会员看到他们想看的DVD，自然该满意度就是最大的。然而，从网站的角度考虑，是希望用尽量少的购买量来满足95%的会员的要求，因而可以看出用上述方法确定的购买量虽然满意度很高，但显然购买量过大了。我们考虑任意给出一组初始购买量，在限定95%的覆盖面的条件下，逐步向下或向上调整初始量的数值，并在调整的过程中始终保持与问题2算法中的满意度最大相同的条件，最终得到最优解。具体算法步骤如下： 给与初始每种DVD的购买量（）及一月内可使至少95%的会员租赁到第种DVD的最小碟数（）； 取=min（，）； 用问题二的分配算法对（）进行分配，得到一个月内的看到了想看的DVD的会员占想看此DVD的总会员数的百分比P； 若，转，否则算法结束并输出及； 找出（）中的最大者，并记录此时DVD的编号，然后，转。 算法程序见附录4。为了方便，我们就取表2中的DVD现有数量为初始值进行计算（实际上，可以取任意一组数值为初始值），计算结果如下：1、每钟DVD的购买量，见表7。表7 每钟DVD的购买量DVD名称123456789101112131415购买量124015222014303335252931286112DVD名称161718192021222324252627282930购买量282826313834293522296814192541DVD名称313233343536373839404142434445购买量293517403921613029148026183634DVD名称464748495051525354555657585960购买量193225176340263326612228384436DVD名称616263646566676869707172737475购买量273142442270163533302040151128DVD名称767778798081828384858687888990购买量2420661128318221160213443827DVD名称919293949596979899100购买量39282415502436559402、群体满意度为=832.07.3、一个月能得到他想看的DVD的会员占95.1%.若在程序中的值改为大于95%，会使更多的会员得到他想看的DVD。（四）问题4从网站的利益出发，作为网站经营管理人员应该要考虑网站赢利的最大化，因此，我们认为在网站的经营过程中应始终追求利润的最大化。反映在实际经营过程中就是以最小的碟片数量实现最多的租赁次数。若l为网站规定一个月内进行分配的次数，应为偶数；且网站要求至少r%的会员能看到第i种DVD，则相应的数学模型如下：min max s.t. .由于时间原因，我们未能给出该模型的解。四、结束语1、模型的评价本文对于问题二构造出了线性规划模型，由于变量数目较大，通过计算机编程（用模拟退火算法等）搜索得到该模型的最优解需要花费大量的时间。显然，这不切实际。因此，需要寻求某种快速算法找到该模型的最优解的近似解。为此，我们首先给出了贪婪算法，经实际计算后，结果不让人满意，进而对它作改进得到了改进的贪婪算法。该算法易于理解，易于接受，且可操性强，在计算机上对给定数据可以实时得到结果，应用的范围较广。并且还可以稍作改造就能应用到问题三。其算法的实质在寻求在保持每步满意度最大这一条件下对1000种DVD进行分配。数据表明，将它用于问题二和问题三得到的结果（指满意度），与服务业知名品牌市场调查满意度相差无几。这表明该算法对于此问题的求解有很强的实用性，而且经过简单修改便可解决类似问题，易于推广。但由于时间所限我们对其算法在理论上的合理性、重要性探讨略显不够。2、模型的改进 （1）模型建立还可以进一步更加合理性，租赁DVD的周期由半月十五天转为十天或七天或更短的时间，这样网站DVD的流通速度进一步加快，同时也可为网站带来更好的收益。 （2）我们把满意度分为群体满意度和个体满意度。而群体满意度简单的认为它是所有无区别个体满意度之和。未能考虑对于租赁DVD较为频繁的老会员和新会员而言，为吸引住这两批客人，网站经营管理人员应格外照顾，而他们二者满意度相对于其他会员而言应当更为优先、更为重要，可适当授以权重，以保证网站的长远发展。因此，在模型改进时我们可给这两批人优先考虑使他们达到最大满意度，当然在模型改进时可以对他们的满意度付以较高的权重系数。参考文献：1 姜启源、谢金星、叶俊，数学模型（第三版）M，北京：高等教育出版社，2003。2 赵 静、但 琦，数学建模与数学实验M，北京：高等教育出版社，2000。3 张 磊，全国知名计算机质量和服务满意度调查分析DB/OL，Content/200504/cc4e15cda81d4dfeabd6e0019235bf97.shtm，2005.9.16。附 录附录1：模拟退火算法（VC源代码）/*/Name:模拟退火算法/Mode:高级搜索模型/Date:2005-9-17/*#include "iostream.h"#include "fstream.h"#include "time.h"#include "stdlib.h"#include "math.h"/template <class Type>class SimulationAnnealArithmeticprivate:float T;/止温度float T0;/起温度float a;/退火速度unsigned int X01000100;/-unsigned int X11000100; /模拟参数unsigned int C1000100;/会员对DVD的偏爱矩阵unsigned int S100;float I;float I0;public:InputDate();OutputDate();Resolution();SimulationAnnealArithmetic();SimulationAnnealArithmetic();SimulationAnnealArithmetic:SimulationAnnealArithmetic()T=0;T0=0;for(int i=0; i<1000; i+)for(int j=0; j<100; j+)X0ij=X1ij=0;Cij=0;Sj=0;SimulationAnnealArithmetic:InputDate ()ifstream file1("data1.txt");for(unsigned int i=0; i<1000; i+)for(unsigned int j=0; j<100; j+)file1>>Cij;file1.close();ifstream file2("data2.txt");for(i=0; i<100; i+)file2>>Si;file2.close();T=1000000;T0=1;a=0.9;SimulationAnnealArithmetic:Resolution ()while(T>T0)/产生随机变量X1srand(unsigned)time(NULL);while(1) for(unsigned int i=0;i<1000;i+) while(1)int k=0; for(unsigned int j=1; j<=100; j+) if(unsigned int)rand()%100>96)X1ij=1;k+; if(k<=3) break; /end-while int flg=0; for(unsigned int m=0; m<100; m+) unsigned int sum=0; for(unsigned int n=0; n<1000; n+) sum+=X1mn; if(sum>Sm) flg=1; if(flg=0)break;/whilefor(unsigned int i=0; i<1000; i+)for(unsigned int j=0; j<100; j+)if(Cij=0)I=I+0;elseI=I+X1ij*(float)(1/Cij);if(I>I0)for(unsigned int i=0; i<1000; i+)for(unsigned int j=0; j<100; j+)X0ij=X1ij;cout<<X1ij;cout<<endl;T=T*a;else if(exp(I-I0)/T)>(float)(rand()%100)/100)for(unsigned int i=0; i<1000; i+)for(unsigned int j=0; j<100; j+)X0ij=X1ij;T=T*a;/while;SimulationAnnealArithmetic:OutputDate () /* for(unsigned int i=0; i<2; i+) for(unsigned int j=0; j<100; j+) cout<<Cij; */ofstream file("out.txt");for(unsigned int i=0; i<1000; i+)for(unsigned int j=0; j<100; j+)file<<X1ij;file<<endl;file.close();void main()SimulationAnnealArithmetic *p;p=new SimulationAnnealArithmetic();p->InputDate ();p->Resolution ();p->OutputDate ();附录2：贪心算法及改进,自动调度算法（VC源代码）/*/Name:贪心算法及改进,自动调度算法/Mode:近似求解模型/Date:2005-9-19/*#include "iostream.h"#include "fstream.h"#include "math.h"#include "time.h"#include "stdlib.h"class Nearprivate:unsigned int C1000100;/会员对DVD的偏爱矩阵unsigned int S100;/DVD数量unsigned int MS100;/DVD最大需求量unsigned int DVD100;unsigned int X1000100;/记录会员租的DVD矩阵unsigned int Y1000100;/记录会员第一次租的DVD矩阵unsigned int Ave1000100;float I1000;/第一次每个用户的满意度float II1000;/第一次每个用户的满意度unsigned int usercode1000;/用户编码记录float A;/方差unsigned int flg1000;/60%会员标志unsigned int userExit1000;/第一次得到DVD的会员unsigned int countNum;/得到DVD的会员总数unsigned int ord100;public:InputDate();/数据输入模块OutputDate();/数据输出模块Resolution();/求解模块Near();/数据初始化AutoAdjust();/自动调整模块;Near:Near()for(unsigned int i=0; i<1000; i+)for(unsigned int j=0; j<100; j+)Cij=Xij=Aveij=Yij=0;Sj=DVDj=MSj=ordj=0;Ii=IIi=(float)0;flgi=userExiti=0;usercodei=i+1;A=0;countNum=0;Near:InputDate ()ifstream file1("data1.txt");for