搜索
DVD在线租赁问题的探讨摘要本文探讨了DVD在线租赁问题，建立了DVD租赁问题的优化模型，依据会员满意度达到最优原则，综合考虑网站制定的若干约束，分层次建立了以下三个模型：模型Ⅰ：利用概率统计中样本分布可估计总体分布的知识，建立了在最糟糕的情况下也能满足会员要求所需要的DVD数量的模型，并且得到了满足要求的结果：一个月：DVD1~DVD5张数分别为：6250，3125，1563，782，313。三个月：3959，1980，990，495，198。模型Ⅱ：我们定义了一个较为合理的满意度函数，建立了0-1整数规划的模型并用lingo8.0求解，得到总体平均满意度为0.9156的全局最优分配情况，并且具体列出了前30位会员分别获得的DVD编号。模型Ⅲ：我们采用了单因素、双因素分层次解决双目标规划的方法，通过计算机C语言编程来实现随机抽样，模拟真实情况，并通过大量的数据观测出DVD总数稳定在2850～2950张之间，根据这一点我们提出了一个快速算法，使得计算效率大大提高。我们还从市场因素，服务因素，时间因素和其他因素综合考虑了DVD需求预测，购买，分配中的一些问题，并就需求问题做了专门的探讨，其中会员人流量为其主要因素。本文章还从会员一次订购DVD的数量对满意度函数进行了灵敏度分析，并根据拟合图像验证了一次订购3张DVD可以使满意度达到最优的假设。在问题的进一步讨论中，我们给出了模型Ⅰ可能的取值范围，考虑到实际情况，对模型Ⅱ进行了改进，提出了一种应用更广泛的模型。关键词：全局最优解0－1规划满意度随机抽样快速算法1一．问题重述1.1问题的背景在线DVD租赁问题。随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。1．2实际现状顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员若对DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。1．3要解决的问题：1）网站正准备购买一些新的DVD，通过问卷调查1000个会员，得到了愿意观看这些DVD的人数。此外，历史数据显示，60%的会员每月租赁DVD两次，而另外的40%只租一次。假设网站现有10万个会员，对表1中的每种DVD来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD呢？2）表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单，如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员分别获得哪些DVD。3）继续考虑表2，并假设表2中DVD的现有数量全部为0。如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4）如果你是网站经营管理人员，你觉得在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。二．基本假设及符号说明基本假设：1)以自然月为单位，会员入会生效时间均从每月月初开始，每个会员每月租赁次数不得超过两次，每次获得三张DVD。定义会员得到DVD并将其归还为一次租赁。2)假设问卷调查中的数据来源准确、可信、稳定、科学。3)假设无论会员该月租赁多少DVD（不得多于6张），交纳会费金额相等。2符号说明：jx（j=1,…5）模型I中DVDj的张数jy（j=1,…5）模型I中愿意看DVDj的会员人数iS（i=1,…1000)第i位会员的满意度（i=1,…1000）ija（j=1,…100）第i位会员对第j种DVD的偏爱程度（偏爱程度越高，数字越小，数字0表示对应的DVD当前不在会员订单中）（i=1,…1000)ijμ（j=1,…100）⎩⎨⎧=10ijμ当网站将DVDj租赁给第i位会员时，该值取1，反之取0jb（j=1,…100）表2中DVDj的张数张次：DVD被借出一次为一张次，即使同一DVD被借出N次为N张次。张数：DVD的数量，单位：张。三．问题分析考察问题的题设与要求，对新购买的DVD，只需考虑一个月内某种DVD借出的总张次要满足该月借该DVD的部分人次的需要，三个月内满足一定比例的计算方法也是一样的。根据抽样调查知识，样本均值可估计总体均值，因此10万会员的计算也是一样的。对于当前需要处理的订单，本问题的难点是怎样定义满意度函数，既要考虑使每位会员每次尽量得到3张DVD，又要考虑其对其得到的DVD的偏爱程度。定义一个科学合理的满意度函数是问题的关键。作为网站经营管理人员，如何购买并分配DVD，在考虑购买成本的同时让会员得到想看的DVD且满意度最大，也是一个规划问题。事实上这相当于原始规划问题的对偶问题。在网络这个大染缸中，网络租赁DVD的经营模式将会遇到很多的挑战。要想在视频销售市场占有一席之地，想让网站赢得更加广阔的消费群，对市场预测，会员购买和DVD分配的分析是必不可少的。3四．模型的建立及求解4.1模型I1.前期工作：补充假设：假设被调查的1000个会员对于整体不存在抽样误差。对于几个问题，做如下说明及处理：①根据假设，问卷调查中的数据来源准确、可信、稳定、科学。那么对于同一种DVD，愿意观看的人中有60%是每月租赁两次的，40%是每月租赁一次的。②由于会员入会生效时间均从每月月初开始，那么所有会员的周期都保持一致，即每位会员在月初都有DVD分配给他。③根据抽样调查知识，样本均值可估计总体均值。这里问卷调查的1000个会员是样本，10万会员是总体，原因如下：(以下与符号说明中的无关)iyiy设总体有N个单元,Y为总体均值，为抽取的n个随机样本，其均值为y；iYY′为Y的估计，则可用样本均值估计总体均值即：Y′=y=1/n（nyyy+++L21）之所以能这样估计是因为Y′是Y的无偏估计，即E(y)=Y证明如下：根据数学期望的定义，E(y)=∑（y/），nNC其中∑是对所有可能的种情况求和,由于每个(i=1,2,...N)出现在样本中的次数均为；nNCiy11−−nNC因此有:∑（）=（nyyy+++L2111−−nNCnyyy+++L21）所以有E(y)=（11−−nNCnyyy+++L21）/n*=（nNCnyyy+++L21）/N=Y证毕④把每月租赁两次DVD的会员抽象出来，即只考虑该会员每月租赁两次，而不用再考虑其该月第一次的具体起租日期和第二次的具体起租日期。同理，对于某张在月初被某个月租赁两次的会员租去的DVD，其在当月必定能被该会员还回并被第二个会员租走。⑤对于“至少”二字的理解，考虑最坏的那种情况，即对于月租赁一次的会员，其占用某DVD的时间为一个月，而月租赁两次的会员，某DVD在月内被某两位会员租赁后最后归还时间在该月最后一天，无法再租赁给第三者。2.模型的建立：4根据分析①，在1000人中每月租赁给两次的会员的DVD数为60%*，由于这种DVD每月被利用两次，其张次为2*60%*，同理，每月租赁给一次的会员的DVD数为40%*，因此总租赁张次为2*60%*+40%*。对某种DVD租赁总张次要满足愿意观看的人数的一定比例，因此列式为：jxjxjxjxjx(2*60%*+40%*)（j=1,…，5）jxjx1000/100000jy≥要保证在三个月内至少95%的会员能够看到该DVD，则DVD流动时间有三个周期，列式为：3*（2*60%*+40%*）（j=1,…，5）jxjx1000/100000jy≥3.模型求解：在一个月内使50%的会员看到该DVD，分别将的具体数值代入，得各DVD至少应该准备的张数iyjx⎡⎤1000*6.1/*5.0*100000jy≥DVD名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数200100502510需要准备的张数625031251563782313同样，三个月内至少95%的会员看到该DVD，应该准备的张数为；jx⎡⎤1000*3*6.1/*95.0*100000jy≥DVD名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数200100502510需要准备的张数395919809904951984.2模型Ⅱ1.前期工作：对于几个问题，做以下说明及处理：①对于所有的会员，由于其缴纳的会费是相同的，因此网站不可能一次只租赁给某会员2张DVD，因为这样就违背了网站一开始的承诺且有失公平，则会员有权利要求其赔偿。②若某会员要求一个月租赁两次，则网站必须满足其要求，对于那些一个月只租赁一次的会员，视其为自动放弃租赁第二次的权利。③当网站只有某个会员想看的DVD中的一张或者两张时，网站可以推迟寄送时间来等待会员要求的DVD，以此达到3张，即网站不可能将会员不要求看的DVD寄给会员，因为这样对网站和会员都5有害无利，一方面若有别的会员想租赁该DVD，网站无法提供，一方面会员不希望看他不想看的DVD。④对于当前需要处理的1000个会员的订单，网站只需要考虑一次的分配，使1000位会员总体满意度最大。2.模型的建立：对网站手上现有的DVD进行合理分配，使得会员的总体满意度最大。因此，我们需要定义一个满意度函数，满足以下几点：I.满意度越大，表示会员越满意。II.控制在0～1之间，即满意度归一。III.在某一区间上，满意度值分布比较均匀。IV.当一次分配给某会员偏好为1、2、3的DVD时，满意度为1。遵循以上原则，我们令个人满意度函数为：271001∑==jijijihSμ（定义变量，27=8+9+10对应以上Ⅳ）⎪⎩⎪⎨⎧=≠−=时当时当00011ijijijijaaah本函数目标是使总体平均满意度最大，约束条件有：I.网站租赁给会员DVDj的总数不得超过现有张数。II.当网站将DVDj租赁给第i位会员时，ijμ值取1，反之取0。III.当0=ija时，ijμ=0。IV.网站一次只租赁给每位会员3张DVD。综上所述，建立0-1整数规划为：max100010001∑=iiSs.t.⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧030010100,,1100110001或者时，且当===⎩⎨⎧==≤∑∑==jijijijijjiijajbμμμμL3.模型的求解：此模型是一个典型的0-1整数规划问题，可用专门的数学软件求解。但是，当我们使用Matlab7.0求解时，求解结果显示，此问题规模太大，超出其运算能力。这是因为Matlab是使用隐枚举法求解此题。于是我们改用Lingo8.0求解，算法流程图如下：6图1：模型Ⅱ算法流程图Lingo使用分枝定界法，大大减少了运算的步骤。得到的结果如下：平均满意度最大值为：max100010001∑=iiS=0.9156在全局最优解的情况下，前30位会员获得的DVD为：会员号得到的DVD号184198264462332508047184151166686195366772666818000953781001041558511596366122314113217896142352891513528516108997174751671841607819668486204561892145505322385557232981952437417625969812622689527505878288348229263055303762984.3模型Ⅲ：1.建模分析：该模型为一个双目标0-1规划模型，目标函数有两个：DVD总量最小、会员总体平均满意度最大。当我们在分析“一个月内95%的会员得到他想看的DVD”时产生了多种理解：一个月内会员租赁DVD的次数是一次还是两次；如何定义会员“得到他想看的DVD”；以及满意度函数是否与借的次数有关而需要重新定