数学建模案例DVD在线租赁

-1-DVD在线租赁问题研究摘要本文解决的是DVD在线租赁网站在DVD的需求预测、购买和分配中的重要问题。首先我们通过随机概率模型分析了要满足会员要求的DVD的最少采购量，其中主要利用了10−分布和二项分布的理论，即认为会员是否一个月租赁两次是一个随机事件，服从10−分布，因此分配到自己想要DVD的会员中租赁两次的人数就服从二项分布，具体计算时（由于是大样本场合）用标准正态分布逼近二项分布得到最后的结果。在解决最大满意度原则下的DVD分配时，我们建立的是以最大期望满意度为目标，含有随机变量的规划模型。出于计算规模和效率方面的考虑，文中采用类似贪婪算法的处理方法，将DVD的分配分成两个阶段来处理，这两个阶段分别的最优解之和作为最终要得到的最优目标。最后我们基于现实基础提出了以最大满意度和最小邮费为目标的规划方程，并对上述几个模型进行了评价和推广价值讨论。-2-一．问题重述考虑如下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的会员中至少50%在一个月内能够看到该DVD？如果要保证在三个月内至少95%的会员能够看到该DVD该如何准备？2.表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单，分配这些DVD，使会员获得最大的满意度。并具体列出前30位会员（即C0001~C0030）分别获得哪些DVD。3.继续考虑表2，并假设表2中DVD的现有数量全部为0。决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4.深入研究DVD的需求预测、购买和分配中的重要问题，提出这些问题并建立模型加以改进。二．模型假设1.考虑到邮寄时间的限制，DVD在一个月内分配后返还的次数是有限的。2.会员当月租赁的DVD在当月内归还。3.当会员要归还DVD时，该DVD肯定可以在下一个月前回到网站。4.会员得到该DVD地满意度与会员对该DVD的偏爱程度成正相关的。三．问题分析1、总体解题思路：在解决第一小题时：会员是否一个月租赁两次是一个随机事件，服从10−分布，因此要真正保证50％的会员得到满足，就必须使用概率论与数理统计的方法，本文在取定一个合理的置信度后，计算出至少要订购的DVD数量。在解决第二小题时：我们认为网站的分配可以分为两个阶段的分配，其中第一个阶段的分配，网站是可以完全掌控的，而第二个阶段则是一个以最大期望满-3-意度为目标含有随机变量的规划模型，在计算时我们考虑用贪婪算法得出近似最优解。对于第三个小题，我们认为可以在第一个小题和第二个小题结合得到，考虑先用第一小题的方法算出网站应该购入的DVD数量，在此基础上再建立和第二小题类似的规划模型来解决。最后一个问题具有较多的研究方向，由于时间关系，我们仅就邮资最小，网站的成本最低，盈利最大这个方面进行了一些讨论。2、题目要义的理解：a、一个月内DVD出租次数的限制：根据假设1，结合实际，由于邮寄货物一般要一到两个星期左右，因此本文考虑一张DVD在一个月内最多只能分配两次，即只能在初次分配后由会员返还一次，也就是说一个月可以考虑有两个阶段的分配，第一阶段是网站对其拥有的DVD进行初次分配，这一阶段的分配网站在某一原则下（文中是满意度最大原则）是可以完全掌控的；第二个阶段网站可分配的DVD数量是由第一阶段分配后剩下的DVD数量加上第一阶段分配的会员中返还得DVD数量之和。这一阶段的分配是带有随机性的，因为会员是否返还DVD（也就是一个月租赁两次）是一个随机事件，这一阶段，因此必须在承认随机性的前提上考虑其分配。b、会员满意度ijα的定义：根据假设4，本文满意度ijα定义如下：若题中所给表2中会员i对第j张DVD的订单是ija（ija越小，偏爱程度越高），则会员i得到第j张DVD的满意度ijijjiijaa−+=≤≤≤≤1max1001,10001α，如果,0=ija则0ij=α，与假设相符合。四．符号说明jx网站对第j张DVD的购入量ijα满意度矩阵中的元素，表示第i个会员对收到第j张DVD的满意度ijy0-1变量，1=ijy表示第一个租赁阶段内将第j张DVD租赁给第i个会员，否则表示没有租赁给第i个会员ijz0-1变量，1=ijz表示第二个租赁阶段内将第j张DVD租赁给第i个会员，否则表示没有租赁给第i个会员-4-1M第一阶段分配的最大满意度2M第二阶段分配的最大满意度M总的最大满意度五．模型的建立1.问题一：模型1：从最直观的思路分析，既然分配到DVD的会员中有60%的人会归还碟片并再次租赁，那么最少需要的购入量将是115.06.1dx≥，即1100/1.662.5x≥=。（以下计算都以1DVD为例进行分析）模型2：模型1简便易行，直观容易理解，易于推广，但是忽略了“根据历史数据得到的60%不是一个绝对比例而是一个估计量的期望值，实际上每个会员是否归还碟片并再次租赁是一个随机事件”的事实。根据以上的思路深入分析，可以得到更为科学的模型：设jd为想看第j张DVD的会员数量；iN为第i个会员一个月内是否第二次租赁的随机事件，服从10−分布；jI为对第j种DVD，它的某一次分配所分给的会员的指标集；∑∈=jIiijNT，表示对第j种DVD，它的一次分配中可以有多少DVD被归还供再租赁的随机事件，服从二项分布既然DVD的分配是一个随机过程，那么必须要对使“想看1DVD的会员中至少%50在一个月内能够看到1DVD”这一事件设立一个置信度，本题中我们令置信度为99％（即不能满足需要的情况发生的概率小于%1，是小概率事件）。要使会员的需要有50%被满足，就要使归还的碟片数1T和购入的碟片数1x满足：1115.0dxT≥+即1115.0xdT−≥于是有：()99.05.0111≥−≥xdTP1T服从参数1,6.0xnp==的二项分布()pnB,，故由中心极限定理【1】，用标准正态分布近似得到：()()99.016.15.01111111≥⎟⎟⎠⎞⎜⎜⎝⎛−−≥−−ppxxdppxpxTP-5-⇓()99.015.06.1111≥⎟⎟⎠⎞⎜⎜⎝⎛−−Φppxdx将题中数据代入计算得到：()99.011006.111≥⎟⎟⎠⎞⎜⎜⎝⎛−−Φppxx查表【1】得：33.224.01006.111≥−xx得到的是一个一元二次方程，利用求根公式求出与现实意义相吻合的解，舍去不合理的解，便得到了购入量的正解。40.681≥x，由于历史数据是实际数据的样本，根据数理统计中的格列文科定理知，总体的购入量趋于样本购入量的100倍，因此实际的购入量至少是6840。类似的，可分别解出五种DVD的至少购入量，结果如下表DVD1DVD2DVD3DVD4DVD56840355018721008467对于“三个月内至少95%的会员能看到1DVD”这一事件，设每个月的分配中归还再租赁的DVD数的随机变量分别为11T、21T、31T，由于每个月月初所能分配的碟片数量均为1x（这保证了11T、21T、31T相互独立），且每个kT1都满足参数1,6.0xnp==的二项分布，因此312111TTT++服从参数13,6.0xnp==的二项分布，因此要使95%的会员需求得到满足，同样取置信度为99％，可得()99.0395.011312111≥−≥++xdTTTP⇓()()()99.0131395.013311111312111≥⎟⎟⎠⎞⎜⎜⎝⎛−+−≥−−++ppxpxdppxpxTTTP类似前一部分的计算，可得到相应答案为：DVD1DVD2DVD3DVD4DVD5422721721128596265-6-2.问题二：DVD的分配由两个阶段组成，第一阶段是对现有碟片资源按照订单以追求满意度最大化进行分配，第二阶段是对第一阶段中一部分返回的碟片资源进行再分配。从网站的角度看，要达到最大的满意度，最理想的情况是可以对第二阶段归还的会员进行控制，则有如下规划：约束条件()()()()()()()()⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧=≤++−≤≤=+==+∑∑∑∑∑∑=====106154316002313max10001100011000110011001,orwuzyzyywuxzxywuwzuyzyiiijijijijiijiijiijjiijiiijijijijjiijijijα其中约束条件()()21保证每个会员每次获得0或3张DVD；()3表示有%60的会员在一个月内租赁2次；()4表示第一阶段每种DVD的分配量不超过网站拥有的该种DVD的数量；()5表示第二阶段每种DVD的分配量不超过第一阶段分配后的直接剩余量与第一阶段分配量的返还量之和；()6表示不能把会员看过的DVD再分配给同一会员。但是这个模型存在不合理性，在对第二阶段进行分配时，返还的对象及返还的碟片数量的多少均是随机的，直接用%60这个期望值进行计算是不合理的。比较可行的做法是把ijz看成随机变量，通过ijz的分布列来表示约束，并以第二阶段的最大期望满意度为目标进行规划，这样就导致整个规划的目标值也是一个期望值。但是第一阶段的分配方法对于网站来说是完全可支配的，其规划如下：-7-约束条件()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≤=∑∑∑==1013max100011001,oryxyuyyijjiijijijjiijijα对于这个规划，由于iu也是10−变量导致问题求解困难，因此我们考虑对可行域进行缩放，即把条件()1分别改成()311001=′∑=jijy和()311001≤″∑=jijy来求解，经求解验证缩放的可行域中求得的最优值是一样的，由夹逼原理可知这个最优值原来的可行域中的规划问题的最优解，具体结果见模型的求解。第二阶段规划：这一阶段是第一阶段的延续，考虑的是在第一阶段分配结束后，网站用剩下的DVD加上会员返还的DVD来进行再一次分配的过程。但第二阶段的归还人和数量是不确定的，一般来说不能以规划来进行求解。然而第二阶段求的实际上是满意度的最大数学期望，则我们考虑以概率意义上来讲，网站能回收到借出DVD的百分数在%60左右的小范围内浮动。因此我们考虑第二阶段初网站拥有各种DVD的量是个定值。这是对满意度期望的一个很好近似。而此时的满意度矩阵和发生了变化。新的满意度矩阵是第一阶段的满意度矩阵把在第一阶段中已经得到满足的订单的满意度清零，就是说把第一阶段分配结果中1=ijy相对应的原满意度矩阵中的非零元素ijα改为零就得到了新的满意度矩阵。具体规划如下：约束条件()⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=−≤=′∑∑∑∑===10(2)4.013max10001100011001,orzyxzuzzijiijjiijijijjiijijα（1）表示第二阶段每个会员获得0张或3张DVD；（2）表示第二阶段每种DVD的分配量不能超过第一阶段分配后的直接剩余量与第一阶段分配量的返还量之和；具体结果也参见模型求解部分。总的来说，上述分两阶段的规划实质上是用类似贪婪算法来计算理想的以最大期望满意度为目标含有随机变量的规划模型，即分别考虑两个阶段的最优解，-8-合成后的解即使不是最优解，也是一个较优解。3．问题三解决这一小题时，可以先在第一题的基础上算出网站应该购买的DVD数量，再在上述DVD数