DVD在线租赁的分配及优化研究

1、2005 高教社杯全国大学生数学建模竞赛承诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛

2、规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：河南师范大学参赛队员 (打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期： 2015 年 9 月 日赛区评阅

3、编号（由赛区组委会评阅前进行编号）：2005高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：DVD在线租赁的分配及优化研究摘要许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。本文主要运用01规划模型，线性规划和目标规划模型，研究在线DVD订单问题。问题一中，首先以“至少50%的会员在一个月之内能够看到DVD”和“至少95%的会员在三个月之内能够看到DVD”为约束条件，建立了简易规划模型，

4、计算出五种DVD至少应准备的数量：7599.8张。五种DVD的具体购买情况见表二。但它没有考虑存在同时愿意看5张DVD中两张DVD的会员情况，故进一步考虑同时想看五种DVD中相同两种DVD的人。用动态方程的方法精确描述了租赁过程，并建立了相应的规划模型。在精确模型中，同样以两种百分数为约束条件。精确模型的具体结果见表6和表7。问题二中，针对偏爱程度和满意度的转化问题，用了非增量函数来解决，并在此基础上建立了0-1规划和目标规划模型。会员对DVD的偏爱度随着订单数的增加而减少，而不同会员对同一种DVD的偏爱度相同时，这就要考虑再分配DVD时优先考虑编号在前的会员，使会员对自己所需要DVD的满意度

5、达到最大。对于当前订单的分配方案的确定问题，建立目标规划模型并用LINGO软件实现对此题的0-1规划模型和目标规划模型的求解，因此可以获得最大的满意度和其中前30位会员获得DVD情况也给出最优的分配方案。问题三中，建立以总的DVD购买数最小、会员满意度最大为双目标的规划模型。通过确定在一个月内每张DVD的在每个会员中手中的使用率；然后通过程序编程来确定每种DVD的购买量；建立0-1规划模型；通过LINGO软件使满意度达到最大，来最终确定DVD的分配。将多目标规划转化为单目标，同时将第j种在线DVD的购买量yi的整数约束去掉，求解出最小购买数为178.125张。将最小购买数作为约束条件，优化满意

6、度后，得到最大满意度为95%；然后对此时DVD的购买量yi取整，得到总购买数为186张。当购买数为186张时，会员满意度达到97%。问题四中，对于网站而言，其经营管理的目的是获得最大的经济效益，不同的租赁模式下网站会得到不同的经济效益。在限定每月最多租赁两次的情况下得到使网站的效益最大时，应该限定每个会员每次租赁最多2张DVD。同时讨论了对于限定每次最多租赁3张DVD的情况下，最佳的租赁次数限制。通过上述模型的建立与求解，充分发挥了网络的诸多优势，传播范围广泛、成本相对低廉等，为顾客提供更为周到的在线DVD订购服务，为经营者提供更合理的经营方式。关键字：01规划 目标规划 LINGO 满意度一

7、、问题的提出考虑如下的DVD在线租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。其中网站有如下几个约定：1、每个会员每个月租赁次数不得超过2次，每次获得3张DVD。2、会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。现在需要解决以下几个问题：1） 若网站正准备购买一些新的DVD，通过问卷调查1000个会员，得到了愿意观看这些DVD的人

8、数（表1给出了其中5种DVD的数据）。此外，历史数据显示，60%的会员每月租赁DVD两次，而另外的40%只租一次。假设网站现有10万个会员，对表1中的每种DVD来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD呢？2） 表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单，对这些DVD进行分配，使会员获得最大的满意度。请具体列出前30位会员（即C0001C0030）分别获得哪些DVD。3） 继续考虑表2，并假设表2中DVD的现有数量全部为0。决定每种DVD的购买量

9、，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4） 在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出问题，并建立相应的数学模型加以改进。二、模型假设和符号说明1. 租赁周期为一个月，每月租两次的会员可以在月中再租赁一次；2. 同一种DVD每人只能租赁一次；3. DVD在租赁过程中无损坏；4. 会员每月至少交一次订单；5. 会员只有把前一次所借的DVD寄回，才可以继续下一次租赁；6. 月底DVD全部收回，继续下个周期的租赁；7. 随着时间的推移，该网站的会员们的流动情况不会出现大变动。符号意义 DVD的张数 会员对订单的数量 会

10、员对某种偏爱度 购买量 会员的标号 DVD的种类 第个月实际DVD准备量三、问题分析3.1 问题一的分析1000位会员的调查表即是10万个会员的需求预测。由于具体会员订单的不可预知性，无法考虑各种DVD之间的横向数量约束。但是可以考虑看到DVD的会员中至少50%的会员在一个月之内能够看到该DVD的条件和至少95%的会员在一个月之内能够看到该DVD。这两种情况就是目标函数的一个约束条件。为了结果的精确性，利用目标规划和动态规划建立了简易模型和精确模型。3.2 问题二的分析网站给出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单，要求给出一个是会员总的满意度最大的一个分配

11、方案。即如何对这些DVD进行分配，才能使会员获得最大的满意度，就是说对DVD的分配原则是使得会员的满意度最大。具体说来是当会员一次租到的DVD的数量越多满意度越高，当租到的DVD所具有的会员的偏爱度越高满意度也越高，也就是说会员对网站的满意度与满足会员的偏爱度是有关的，显然这是一个0-1规划和目标规划问题。3.3 问题三的分析题目需要回答怎样购买各种DVD的数量来使95%的会员能看到想看到的DVD，并且要怎么分配才能使满意度达到最大。建立以总的购买数最小、会员满意度最大为双目标的规划模型。并确定在一个月内每张DVD的在每个会员中手中的使用率，然后通过程序编程来确定每种DVD的购买量。应建立0-

12、1规划模型；通过LINGO软件使满意度达到最大，来最终确定DVD的分配；3.4问题四的分析对任何经营方而言，利润是一个关键的考虑因素，显然在前面三个问题中我们没有考虑网站经营者的成本利润问题。网站的利润与会员所缴纳的月费密切相关，但同时会员观看DVD的满意度也是一个关键因素。所以，问题四主要解决经营者的利润最大化、会员满意度最大化的问题，即网站经营管理者的最优模式。四、模型的建立与求解4.1问题一:如何购买新的DVD解决的问题可分为两个部分，一是至少应该准备多少张DVD，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD，我们称这种情况为“50%的情况”；二是至少应该准备多少

13、张DVD，才能保证在三个月内至少95%的会员能够看到该DVD，我们称这种情况为“95%的情况”。这个百分数就是对目标函数的一个约束条件。由题目可知，60%的会员每月租赁两次，40%的会员每月租赁一次。每月租赁两次的会员平均30天归还，考虑到这一特征我们建立了简易模型。同时又考虑到同时存在愿意看5张DVD中的两张DVD的会员情况，会对结果产生影响。我们进一步建立了动态方程下的精确模型。4.1.1简易模型4.1.1.1 50%的情况 通过问卷调查1000个会员，得到了愿意观看这些DVD的人数表1. 愿意观看这些DVD的人数DVD名称愿意观看的人数200100502510令为10万会员中愿意看的人的

14、比例，由表1得到1000人中愿意观看每种DVD的概率分别为 由于这1000人为10万人的子样本，也可表示10万人中愿意观看每种的概率。假设网站对5种DVD准备张才能保证此网看到该的会员中至少50%在一个月内能够看到该DVD，为每月租赁一次的会员的比例。则一个月内租出的总数为。希望看到的总人数为100000*。写出简易模型如下：把代入上面的简易模型易得需要准备的DVD的总数量至少为张，5张DVD的需要数量分别为 4.1.1.2 95%的情况60%的会员每月租赁DVD两次，而另外的40%只租一次，对这一假设见到你的理解为一个人借两次其实他完全可能下一回变成只借一次的人，同样的借一次的人下月也可能变

15、成借两次的人，只不过总量来看是60%的会员每月租赁DVD两次，而另外的40%只租一次。此外月的分界不可能那么清楚，太清楚则并不方便。针对网站三个月进行的六次租赁我们已DVD1为例，坐下面收发图：图1 三个月六次租赁情况时间轴上放的箭头表示网站借出的DVD1的数量，轴下方的箭头表示网站收回的的数量。三个月内，租赁DVD的总次数为6，假设前一次收回的DVD能够立即进入下一次租赁。网站每次租出数如下：第一次：第二次： 可借出的为第一次还回的第三次： 借出的为第一次另一部分还回的与第二次还回的第四次：第五次：第六次：推广到一般的三个月每次租出数目为：由此可得到如下带约束条件的线性规划模型： 用LING

16、O软件求解的DVD准备情况，至少需准备DVD总数：7599.8张。 表2.5种DVD的数量 需准备数量395231969.2989.8490.8197.74.1.2动态方程的精确模型4.1.2.1 模型的建立由于网站现有的DVD数量与DVD已被租赁的次数密切相关，存在不同的状态，因此采用状态方程对以下两种情况进行讨论。4.1.2.2 50%的情况在第一个月内60%的会员租了两次，40%的会员租了一次，我们只需以网站两次租赁DVD的情况为基准来考虑。具体租赁流程如下：第一次租赁在问题一中，愿意观看的人数和实际租出的数量 是随租赁次数而变化的，为状态变量，由此我们对不同的租赁次数形成一系列状态表。

17、在此，与第一周期相对应的为状态表一。表3. 状态表一名称愿意观看人数准备量实际租出在此，实际租出DVD数量即为第一次租赁中准备DVD数量，即使如此也可能不能满足50%的希望看到某DVD的会员在一月内能够看到该DVD,因为DVD数量有限。：第二次租赁同理，列出状态表二表4. 状态表二名称愿意观看人数准备量实际租出数量此时，第二次租赁中愿意观看的人数Ri和实际租出数量未知，求出它们是关键。求在第二次租赁中愿意观看的人数Ri和实际租出数量其中为想租却在第一次租赁中没租到的人数，为每月只租一次的人同时愿意观看与却只租到的人数（它们不参加这个月的第二次租赁），而要计算比较复杂。只要求出和的表达式，我们可

18、以通过求的表达式来推导和。建立模型：目标函数为购买最少的数量： 约束条件为：至少50%的会员在一个月之内能够看到 动态方程下的精确模型为： 4.1.2.3 95%的情况列出三个月中6次租赁的状态表5. 状态表三 愿意观看人数第一月一次 二次第二月一次二次第三月一次二次由此建立精确模型 精确模型的求解：此问题是典型的带约束非线性规划问题，我们采用LINGO编程计算，计算结果如下： 表6.DVD准备情况DVD名称准备数量625031251562.5781.5312.5 至少准备DVD总数：12031.5张表7.DVD准备情况DVD名称准备数量4232.62116.51058.2529.3211.6

19、至少准备DVD总数：8148.2张4.2问题二：的分配方案4.2.1 影响会员满意度的因素会员对某种DVD偏爱度的量化：会员对DVD偏爱度是随着订单数字的增加而减少，其中会员对网站的满意度与满足会员的偏爱度是挂钩的；因此我们可用一非增函数来度量；从心理学的角度来看：随着的增加，相邻的两个订单数字之间的偏爱度的差会越来越小，所以我们定义了: 不同会员在对同一种DVD偏爱指数相同时，我们在分配DVD时优先考虑编号在前的会员。要确定把那张DVD租给哪个会员，才能使满意度达到最大，因此我们引入表示把第种DVD是否租给第个会员；从问题我们可以看出这是一个如何分配的问题，我们不妨把其中现有DVD的张数看成

20、现有判断条件为需要完成的任务，把每一为会员看成完成这些任务的人选，其中他们对各种DVD的偏爱度就代表他们完成相对应的任务的能力；我们就要使他们对各种任务的完成能力达到最大:约束条件：所有的会员分配到种DVD的数量之和不能超过现有的第种DVD的张数 1、2.100；为0-1变量)由于网站每次对每个会员DVD的分配要么0张要么3张所以 （i=1、2、.1000；为0-1变量）4.2.2建立01规划模型目标函数：约束条件：（、均为0-1变量；i=1、2.1000；j=1、2.100）；4.2.3对 01规划模型求解根据上述模型，用LINGO数学软件实现对此题0-1规划模型的求解；执行的代码见附录一；

21、可以获得的最大满意度为1634.712其中前30位会员（即C0001C0030）获得情况如下表所示表8.前30名会员获得DVD的情况会员编号DVD编号C000184198C0002 6 44 62C000332 50 80C0004 7 18 41C000566 68 11C0006 19 53 66C0007 26 66 81C000831 3571C0009 53 78100C001041 55 85C001159 6366C001231 2 41C0013 2178 96C0014 5223DVD 89C0015 1385 52C0016 84 97 10C0017674751C0018

22、 41 60 78C0019 84 86 66C0020 45 89 61C0021 53 45 50C0022 57 55 38C0023 95 29 81C0024 76 41 37C00259 69 94C0026 2268 95C0027 5878 80C0028 8 34 37C0029 5530 26C0030 6237 984.3问题三：DVD的最优分配方案1、问三是问题一和问题二的结合，要求我们在确保95%的会员能得到他想看的的前提下使会员对网站的满意度达到最大；在这里我们需要解决的问题是，在满意度最大的情况下，如何使采购的DVD总数量最少；2、如何确定每种DVD的采购量，才能

23、使客户的满意度达到最大；因此我们求出需要准备DVD总数的上下限，假定网站在一个月内分配给会员一次DVD（三张他想要看的DVD）即认为会员得到他想看的DVD。由于在一个月内一张DVD使用率为0.7设购买第j种DVD的数量为bj，相当于能够满足网站在一个月内需求为j种DVD的会员数。每一种DVD都满足95%的会员的观看，这样既能满足题目要求，又能使满足度达到最大；所以需要购买j种DVD的数量bj有如下表达式：上限：每月租二次的人两次会员还回来的DVD全部不能重复利用，则得出可以借出的DVD总数的上限为 下限：每月租二次的人两次会员还回来的DVD全部能重复利用，则得出可以借出的DVD总数的下限为 利

24、用模型一的方法进行求解：目标函数： （为0-1变量，即当小于6大于时0，就为1；否则就为0；=1、2.100） 约束条件： （为0-1规划；当=0时=0，=1,j=1、2.100）建立0-1规划模型目标函数： 约束条件：（为0、1、2变量，为0-1变量；=1、2.1000；=1、2.100）；根据模型建立，用软件进行编程可求解得各种的购买量，执行的程序见附录二。4.4问题四：网站在经营中，其主要的目标是获得最大的利润。假设会员每个月所缴纳的费用为，而此时网站的经营模式为限定每个月会员租赁次数不得超过次。每次租赁不得超多张，从网站的角度来看，当、增大时，可能网站的经营成本会增加，因为此时，网站需

25、要付出更多的邮费以及出资购买更多的，因此，网站总是尽量减小、，但是考虑到顾客满意度不能太低，此时，、，不能太小，这样，对于网站来说，网站会获得最优的效益。下面我们分别来考虑每月最大租赁次数和每次最多租赁数目对网站经营利润的影响。4.4.1最优每次租赁数限制：4.4 .1.1模型建立我们首先来考察限定每月最多租赁两次的情况下，为了使网站获得最大的利润，应该如何限定会员每次租赁的数目。考虑如下的问题：继续考虑附表2，表中列出了网站手头上100种的现有张数和当前需要处理的1000位会员的在线订单。假定购买一张新的费用为=10美元。每份快递的费用为两美元，会员每月租赁次数不得超过2次。每个月会员每月的

26、月费为19.9美元，为每次会员最多获得的数目，如何确定以及如何对这些进行分配，才能使网站所获得利润最大，同时使会员的满意度不低于0.8。在此，建立01规划模型： 其中： 第二次分配时每名会员最多获得3张： ，其中随机生成，为1表示第个人在该月内两次租赁，反之为0。一个月内95%以上的会员看到自己想看到的的约束： 上式中，表示第个人在一个月之内至少可以看到一张，反之为0。4.4 .1.2模型求解求解上述模型，可以得到在限定每个会员每月最多租赁2次的情况下，对于上述问题，要使网站所获得的总利润最大网站应该制定时的会员每月最多可获得2张，此时网站可盈利。并且，1000位会员的个人满意度统计如下：图2

27、 个人满意度 上图中，横轴表示个人满意度，纵轴表示相应个人满意度的会员。此时，会员的满意度可以达到0.8。在本问题所给的情况下，对于限制每月最多租赁两次的情况下，允许会员每次借2张网站所获得的经济效益会较好。4.4 .2对于网络经营方式的一些建议为了在购买新时能够准确地对需求进行预测，建议网站的调查表可以设计为让每位会员按其偏爱程度给出自己感兴趣的十张，这时再考虑具体购买新的。此时相当于已经有了一个具体的订单，这样会使购买方案更加精确、合理。五、结果分析与检验5.1 模型评价(1)问题一建立的简易和精确模型，两者相互印证、更好的说明所建模型的正确合理性。从所建两个模型的计算结果来看，可以发现两

28、个模型是存在差别的。简易模型的误差之所以存在是因为考虑的情况不全面，因此精确模型的可靠性还是比较高的。(2)问题三对每一种均满足95%的会员的观看，这样既能满足题目要求使总数达到满足95%的会员观看，又能使满足度达到最大。(3)问题四考虑了每月最大租赁次数和每次最多租赁数目对网站经营利润的影响，建立01规划模型将限定在一个较小的范围内，对最优租赁次数进行多次验证，发现会员满意度在允许会员每次借2张时网站才能获得最大经济效益，并且因为所用的求解数据均为人为设定的，结果难免会有一定误差。5.2 模型改进上文中所涉及到的0-1整数规划模型，是一个NP难问题，在小规模情况下可以直接用LINGO软件求得

29、最优解，但当规模很大时就无法使用。所以对于一般的大规模问题，就必须对此模型进行改进，我们将其转化为一个有多项式时间算法可解的模型并对决策变量的0-1整数约束进行松弛处理，将约束条件：改为： 得到数学模型：这是一个线性规划模型，有多项时间算法可解。因此可以用来求解大规模问题。设用此松弛模型得到的最优解为:对其中的某一个，若，则松弛条件模型的最优解即为原整数规划模型对应变量的最优解，否则，我们可以定义为一个随机解，即以的概率为1，以的概率为0。然后为了将随机解确定下来，分别以它们各自的概率计算得到一组确定的解。若解不可行，则对导致解不可行的那些随机解依从小到大依次变换调整，直至解可行，由此得到一组

30、解即为满意解。六、模型评价6.1 模型优缺点优点： (1)问题一建立模型一通过简单计算得出的购买数量，并建立模型二验证模型一的准确性。(2)根据实际情况设置上下限确定需要购买种的数量，将上下限作为约束条件是问题更准确(3)应用0-1整数规划模型完整地描述了本问题，对于如本题中的实例这种小规模问题可快速求解缺点：(1)在已知满足1000个会员的满意度下的的数量的情况下按照比例推出10万个会员的满意度的的数量，这样虽然避免大的计算量，但是使结果的误差变大，而且调查具有随机性。由于数据量不够充足使得我们所求得种的数量存在误差。(2)在实际中，租赁分配又是一个复杂的数学问题存在着大量的不确定。例如：网

31、站会员数量，会员对不同的偏爱度，会员的租赁时间，租赁的的数目以及归还的时间等等，所以我们的模型就会有一定程度的偏差。七、参考文献1郭科、胥泽银最优化方法及其程序设计四川科学技术出版社.1998.82甘应爱等运筹学北京:清华大学出版社.20043姚恩瑜、何勇等 数学规划于组合优化杭州：浙江大学出版社.2003.4汪裕钊、辛培清等 数学模型与计算机模拟成都：电子科技大学出版社.1989.5司守奎、孙玺菁、张德存、周刚、韩庆龙等 数学建模算法与应用习题解答国防工业出版社.2013年.6吴黎军、田存福 名额分配问题的0-1整数规划模型工程数学学报，第21卷第1期，P135-138，2004.附录一问题

32、二附录model:sets:DVD/1.100/:total;!total为网站现有的数量;huiyuan/1.1000/; !自定义0-1向量;pianai(huiyuan,DVD):ONE;bianliang(huiyuan,DVD):data1;Endsets!目标函数（总体满意度最大）;max=sum(pianai(i,j):data1(i,j)*ONE(i,j);! x (i,j) ,t (i)为0-1变量;for(bianliang:bin(data1); ! 约束条件每人可租数Yi=3或0;for(huiyuan(j):sum(bianliang(j,i):data1(j,i)=3); ! 所租总数小于网站现有的数量; for(DVD(i):sum(bianliang(i,j):data1(i,j)=total(i);data:total=10 40 15 20 20 12 30