全国大学生数学建模竞赛200512、D2404 - 图文

D题之一（全国一等奖）

DVD在线租赁

参赛学校：桂林航天工业高等专科学校 参赛学生：李志刚、闫召红、李东风

指导老师：刘期怀

摘要：随着信息时代的到来，DVD的在线租赁越来越广泛，此时合理的分配订单中选择的DVD，使会员的满意度最高，就可以为网站创造更多的经济收益。本文对每月租赁DVD会员的返还时间进行了讨论，以会员获得最大的满意度为目的，对订单中的DVD进行了最优分配，建立了0-1整数规划模型：

maxZ1???aijxij，

i?1j?110020?20??xij?3,i?1,2,3,?,100?j?1?100??xij?bj,j?1,2,3,?,20?i?1s.t.?x?0或x?1 模型Ⅳ

ij?ij??1??c,当cij?0?aij??ij?0,当c?0?ij??问题1中，为了保证在三个月内至少95%的会员能够看到该DVD，分别采取对一个

月分s阶段的方法建立了一般性的模型:

min　x?s??uk?95%?n?k?1 模型Ⅲ ?u?uk?1?q?uk?s?(1?q),k?s,k?Ns.t.?ks?1u?x,u?xq,?,u?xq2s?1?30s???，定义符号??为取数的最小整数上界?T?在问题3中每种DVD的数量的确定，同样也是采取分阶段的方法。

我们采用了LINGO软件直接调用D2005Table2.xls文件中的数据对0-1整数规划模型进行编程求解（程序与结果附后），利用了Mathematica软件进行数值计算，两者结合，分别得出了分不同阶段返还时的最优分配方案。

关键词： 模型；DVD盘；0-1整数规划模型；在线租赁；偏爱系数

151

1. 问题重述

随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。

考虑如下的在线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中列出了网站手上20种DVD的现有张数和当前需要处理的100位会员的在线订单（表2表格格式示例如下表2，具体数据请从 http://mcm.edu.cn/mcm05/problems2005c.htm下载），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001~C0030）分别获得哪些DVD。

3）继续考虑表2，并假设表2中DVD的现有数量全部为0。如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？ 表1 对1000个会员调查的部分结果 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人200 100 50 25 10 数 表2 现有DVD张数和当前需要处理的会员的在线订单（表格格式示例） DVD编号 D001 D002 D003 D004 … DVD现有数量 8 1 22 10 … C0001 0 0 2 0 … 会员C0002 1 0 9 0 … 在线C0003 0 6 0 0 … 订单 C0004 0 0 0 0 … … … … … … … 注：D001~D020表示20种DVD, C0001~C0100表示100个会员，会员的在线订单用数字1,2,…表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。（表2数据从http://mcm.edu.cn/mcm05/problems2005c.asp下载）

152

2．模型假设

根据题目的要求，并为达到简化问题的目的，我们有以下假设：

1、每位会员租赁DVD的最长期限为一个月, 租赁DVD两次的会员至少在一个月中 返还DVD一次;

2、假设在所有的会员中，60%的会员每月租赁DVD两次，另外的40%只租一次。 3、每个会员每个月租赁次数不得超过2次，每次获得DVD的数量不超过3张。 4、会员不重复租用同一张DVD盘，DVD盘在租用过程中没有损坏；

3.符号说明

1、cij表示第i个人对第j张DVD盘的会员满意度的数字，

?1?c,当cij?02、aij??ij表示第i个人对第j张DVD盘的偏爱系数；

?0,当c?0ij?j种DVD?1，第i位会员租赁第3、xij??；

j种DVD?0，第i位会员不租赁第4、bj表示网站拥有第j张DVD盘的数量； 5、n为网站的总会员数；

6、uk为第k阶段租赁出的DVD的数量

4. 模型的建立与求解

4.1问题1模型的建立与求解

4.1.1.1 简单模型的建立

根据对问题的分析，考虑到60%的会员每月租赁DVD两次，而另外40%只租一次，为了资源的充分利用，第一批DVD应当全部租赁完，且返还的DVD数量至少要能满足第二批会员租赁。因此，我们建立以下的模型Ⅰ：

p?n?50%?x?x?60% 模型Ⅰ

其中p为希望看到某种DVD盘的会员人数比例；n为网站的会员总人数10万；x为网站拥有该种DVD盘的数量。

55即得:x??p?n,因此至少需要DVD盘的数量为?p?n。

1616利用数学软件Mathermatic4.0求解列表如下(程序见附录2.2.1)： DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 p x（张） 20% 6250 10% 3125 5% 1563 2.5% 782 1% 313 4.1.1.2 模型的进一步思考

153

进一步分析，我们发现租赁两次的会员分阶段呈周期性的返还DVD，而模型Ⅰ实际上考虑了周期为15天的情况，而有的会员在很短的时间内就返还了，造成了资源的浪

30费，故我们对模型进行改进。设租赁两次会员的返还周期为T,在一个月内分为s?T（s?N)个阶段，设uk为第k阶段租赁出的DVD的数量，建立如下模型：

min　x

?s??uk?p?n?50%?k?1(k?1,2,?,s)s.t.?uk?uk?1?q,u1?x　 模型Ⅱ

?30?s???，定义符号??为取数的最小整数上界T?即为使会员的满意度最高，网站拥有该种DVD盘的最少数量为： x?50%np(1?q)

1?qs重新考虑问题1，特别地取s?4，即分为4个阶段。如果取周期为10天，一个月可分为s?3个阶段，根据模型Ⅱ利用数学软件Mathermatic4.0求解列表如下： 20% x（张） 4596 4.1.2考虑连续三个月的返还 DVD名称 p DVD1 DVD2 DVD3 DVD4 DVD5 10% 2298 5% 1149 2.5% 575 1% 230 连续考虑长时间几个月的返还情况，设uk为第k阶段租赁出的DVD的数量，则到第

k?s阶段时，第k阶段租赁出的DVD的数量uk此时应该全部返回，且要保证在这几月内

至少95%的会员能够看到该DVD，建立如下数学模型为：

min　x?s??uk?95%?n?k?1 ?uk?uk?1?q?uk?s?(1?q),k?s,k?N 模型Ⅲ

s.t.?s?1u?x,u?xq,?,u?xq12s??30?s???，定义符号??为取数的最小整数上界T?其中每月租赁两次会员的返还周期为T；x为网站拥有该种DVD盘的数量。

在问题1中，为了保证在三个月内至少95%的会员能够看到该DVD，我们分别取了

s?2,3,4的情况，即每月分别分为2,3,4个阶段，利用数学软件Mathermatic4.0求解列表

如下：

154