全国数学建模大赛获奖论文(DVD租赁问题)

国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖12005高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛的题目是：B题：DVD在线租赁我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：国防科大参赛队员(打印并签名)：1.刘健2.张云安3.李宝娟指导教师或指导教师组负责人(打印并签名)：指导教师组日期：2005年9月19日赛区评阅编号（由赛区组委会评阅前进行编号）：国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖22005高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖3DVD在线租赁摘要本问题是一个DVD在线租赁中，网站方如何对于市场进行需求预测、如何对DVD进行分配才能同时最好的实现其经济效益和社会效益。第一问中，基于需求预测基础上的DVD购买方案设计中，我们分别考虑了悲观情况和均值情况。为了保证希望看到某种DVD的会员中，有50%以上在一个月内能看到该DVD，在悲观情况下，各种DVD的购买量分别为：9000，4500，2250，1125，450。在均值情况下，各种DVD的购买量分别为：6250，3125，1563，720，313。为了保证在三个月内95%以上的会员能够看到，在悲观情况下，各种DVD的购买量分别为：4500，2250，1125，563，225。在均值情况下，各种DVD的购买量分别为：3959，1980，990，495，198。最后，不考虑具体的会员的借还DVD时间，我们使用概率的方法解决了该问题。结果与均值情况相近。对于第二问，对于当前订单的分配方案确定。我们建立了0-1规划模型，求得此时的最大满意度为24746，我们给出了此时的最优分配方案。第三问，是一个多目标规划问题，既要考虑使得会员的满意度尽量大，还要使得网站所购买的总的DVD数目最少，在具体处理时，我们让会员满意度在一定的范围内变动，给出各种情况下使得总DVD数最少的方案。其中当会员相对满意度为0.8时的最少DVD总数为2059张。分析第三问的结果，我们发现了有趣的双峰现象，并对其合理性进行了阐述。同时，我们还可以发现，会员相对满意度与最少DVD之间呈现总数近似线性的关系。如下表所示：相对满意度0.50.60.70.80.91.0所需DVD数120214861760205925673098对于网站而言，其经营管理的目的是获得最大的经济效益，不同的租赁模式设置下网站会得到不同的经济效益，第四问中我们讨论网站经营管理的最优模式。求得了在一种情况下，限定每月最多租赁两次的情况下，得到使得网站的效益达到最大时，应该限定每个会员每次租赁最多2张DVD。同时讨论了对于限定每次最多租赁3张DVD的情况下，最佳的租赁次数限制。本文论证严密，所给出的结果具有启发性和借鉴意义。国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖4一问题重述随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。考虑如下的在线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的数据格式示例如下表2，具体数据请从下载），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001~C0030）分别获得哪些DVD。3）继续考虑表2，并假设表2中DVD的现有数量全部为0。如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4）如果你是网站经营管理人员，你觉得在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖5二背景介绍DVD在线租赁业务是一项近年来在网络技术高度发展的基础上出现的新业务。1998年，成立于美国的Nexfix是目前炙手可热的DVD在线租赁商。该公司有多种DVD出租业务。其中，典型的是一种这样的：顾客每月缴纳19.9美元成为会员。定购DVD租赁服务。顾客对哪些DVD感兴趣，只须在线提交订单，网站收到顾客的订单之后，会根据手头现有的DVD数量和会员的订单尽可能将DVD以快递的方式投递给会员。一般情况下，在一天之内，网站即可将会员所需的DVD送到会员手中，会员每次最多得到3张DVD。每个月订购的次数是有限的，顾客拿到这些DVD之后可以无限期的保留这些DVD，前提是在这段时期内，他仍然是该网站的会员。如果会员想拿进行下一次租赁，则它必须首先将手上的DVD放进网站提供的信封里寄回。之后，即可进行下一次租赁。三问题分析本问题是一个在DVD租赁业务中，网站方如何进行DVD需求预测、如何购置新DVD、如何将手头的DVD分配给会员，从而可以保证会员满意而同时又使自己收到良好的经济效益的问题。第一问中，1000个会员的调查表即是10万个会员的需求预测。由于具体会员订单的不可确知性，，无法考虑“每个会员每次最多获得3张DVD”的约束，同时各种DVD之间的横向数量约束也无法考虑。故计算时，对于每种DVD的购买量可单独考虑。此时，由于每月租赁两次DVD会员的不确定性，我们可以以均值情况估计和最悲观情况估计。第二问中，网站给出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的再现订单。要求我们给出一个使得会员总的满意度最大的分配方案。显然这是一个大规模的0—1规划问题。第三问中综合考虑一个月内DVD的购买分配方案，这其实是一个多目标规划的问题。从网站的经济效益角度考虑看，在保证所有会员中95%以上的会员一个月内看到自己想看的DVD的情况下，希望购买的DVD尽量少，但是从其社会效应来看，则要尽可能地考虑让所有会员的总的满意度最大。这时，可以使用多种方式将多目标规划变为单目标规划，以求得一个经济效益与社会效益的综合最优。具体的1000位会员中到底会有哪些会员是可能会在一个月内租赁两次DVD，这个数据我们无从得知。我们可以随机地从1000名会员中选择600名。认为这些会员将会在一个月内两次租赁DVD，由于所给数据的均匀性，无论是哪600名会员将会两次租赁DVD，对目标影响并不会很大。对于网站而言，其经营管理的目的是获得最大的经济效益，不同的租赁模式设置下网站会得到不同的经济效益，第四问中我们讨论网站经营管理的最优模式。国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖6四符号说明ijC第i名会员获得第j张DVD时的满意度。ijx第i名会员获得第j张DVD时，1ijx=，反之为0id1id=时，第i名会员在该月两次租赁DVD，反之为0jb网站第j种DVD的拥有量C：网站每月收向每位会员取的月费。1ijx：第i名会员第一次分配时获得第j张DVD时，11ijx=，反之为02ijx：第i名会员第一次分配时获得第j张DVD时，21ijx=，反之为0五基本假设1．网站对1000名会员的调查结果足以反映网站的10万名会员对于各种DVD的需求及喜好2．会员中总是有60%的会员每月租赁DVD两次，40%的会员每月租赁DVD一次3．会员只有在需要再次租赁DVD时，才会将将上次租赁的DVD归还。4．因为60%的会员每月租赁2次DVD，40%的会员每月租赁1次DVD，所以假设每位会员每月至少会租赁1次。5．如果会员对某种DVD感兴趣，但是本次提交订单后，并没有得到该DVD则他的下一份订单中仍然会有兴趣观看该DVD6．网站对于会员归还DVD的期限不作限制。7．对于每一类被租赁出去的DVD总是有60%分布在每个月会租赁两次DVD的会员中，40%分布在每月租赁一次DVD的会员中。8．会员在一个月内只要看到一张他想看到的DVD就认为他看到了想看的DVD.国防科技大学：李宝娟、刘健、张云安，指导教师：指导教师组2005年全国大学生数学建模竞赛全国一等奖7六、模型的建立与求解6．1DVD购置方案的确定通过对1000个会员的调查问卷，网站可以获得其10万个会员对于各种DVD的需求状况，在制定订购方案时，可以不用考虑每个会员每次最多租赁3张DVD的限制。同时不考虑各种DVD数量之间的横向联系，而对每种DVD单独考虑其购买量。我们称每个月内只租赁一次DVD的会员为1类会员，每个月内租赁两次DVD的会员为2类会员。此时，由于每个月内会两次租赁DVD会员的不确定性，在制定DVD的购买方案时我们分别考虑悲观情况估计及均值估计两种方式。6．1．1悲观情况估计a）50%情形对于某种DVD，如DVD1，假设其购买量为m，而希望看到DVD1的会员有2万人，假设经过一段时间的租赁后，DVD1都已被租赁出去，这m张DVD可能在占总会员60%的该月将要租赁两次DVD的人的手中，也可能在另外40%该月只租赁一次DVD的会员手中。如果在前者手中，则一个月内该DVD还可被其余会员看到，但是如果在40%的人手中时，则该DVD在这个月内不会再被其余会员看到。考虑一种悲观情况，m的一部分首先被占总会员40%的会员借走了，这部分人借了就不会在该月再还。为了保证至少有50%的会员在一个月内能看到该DVD,那么此时总的碟数应该满足：40%*20000(40%*20000)*250%*20000m+-≥上式的意义是：在悲观情况下，占想看到DVD1的会员40%的会员令其都租赁到DVD1，并且在一个月内不还，另外60%的会员中有部分租到DVD1并且在一个月内该DVD只被第二个会员看到。此时9000m≥同理，对于其他的DVD也有类似的表达式。此时为保证一个月内至少50%的会员看到他想看到的DVD，则每种DVD