《全国大学生数学建模竞赛200512、d2404》由会员分享，可在线阅读，更多相关《全国大学生数学建模竞赛200512、d2404（15页珍藏版）》请在金锄头文库上搜索。
1、151D 题之一（全国一等奖）DVD 在线租赁参赛学校：桂林航天工业高等专科学校 参赛学生：李志刚、闫召红、李东风指导老师：刘期怀摘要：随着信息时代的到来，DVD 的在线租赁越来越广泛，此时合理的分配订单中选择的 DVD，使会员的满意度最高，就可以为网站创造更多的经济收益。本文对每月租赁DVD 会员的返还时间进行了讨论，以会员获得最大的满意度为目的，对订单中的 DVD 进行了最优分配，建立了 0-1 整数规划模型：，102maxijijxaZ模型0,120,3,1,.102ijijijijijjijjicaxbts当 当或 L问题 1 中，为了保证在三个月内至少 95%的会员能够看到该 DVD
2、，分别采取对一个月分 阶段的方法建立了一般性的模型:s模型为 取 数 的 最 小 整 数 上 界， 定 义 符 号 TsxquxuNksqntxskks30, ,)1(%95.min21L在问题 3 中每种 DVD 的数量的确定，同样也是采取分阶段的方法。我们采用了 LINGO 软件直接调用 D2005Table2.xls 文件中的数据对 0-1 整数规划模型进行编程求解（程序与结果附后） ，利用了 Mathematica 软件进行数值计算，两者结合，分别得出了分不同阶段返还时的最优分配方案。关键词： 模型；DVD 盘；0-1 整数规划模型；在线租赁；偏爱系数1521. 问题重述随着信息时代的
3、到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。考虑如下的在线 DVD 租赁问题。顾客缴纳一定数量的月费成为会员，订购 DVD 租赁服务。会员对哪些 DVD 有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的。网站会根据手头现有的 DVD 数量和会员的订单进行分
4、发。每个会员每个月租赁次数不得超过 2 次，每次获得 3 张 DVD。会员看完 3 张 DVD 之后，只需要将 DVD 放进网站提供的信封里寄回（邮费由网站承担） ，就可以继续下次租赁。请考虑以下问题：1） 网站正准备购买一些新的 DVD，通过问卷调查 1000 个会员，得到了愿意观看这些DVD 的人数（表 1 给出了其中 5 种 DVD 的数据） 。此外，历史数据显示，60%的会员每月租赁 DVD 两次，而另外的 40%只租一次。假设网站现有 10 万个会员，对表 1 中的每种 DVD 来说，应该至少准备多少张，才能保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD？如
5、果要求保证在三个月内至少 95%的会员能够看到该 DVD呢？2）表 2 中列出了网站手上 20 种 DVD 的现有张数和当前需要处理的 100 位会员的在线订单（表 2 表格格式示例如下表 2，具体数据请从http:/ 下载） ，如何对这些 DVD 进行分配，才能使会员获得最大的满意度？请具体列出前 30 位会员（即 C0001C0030）分别获得哪些 DVD。3）继续考虑表 2，并假设表 2 中 DVD 的现有数量全部为 0。如果你是网站经营管理人员，你如何决定每种 DVD 的购买量，以及如何对这些 DVD 进行分配，才能使一个月内 95%的会员得到他想看的 DVD，并且满意度最大？表 1
6、对 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 会员在线订单 注：D001D020 表示 20 种 DVD, C0001C0100 表示 100 个会员，会员的在线订单用数字1,2,表示，数字越小表示会员的偏爱程度越高，数字 0
7、表示对应的 DVD 当前不在会员的在线订单中。 （表 2 数据从 http:/ 下载）1532模型假设根据题目的要求，并为达到简化问题的目的，我们有以下假设：1、每位会员租赁 DVD 的最长期限为一个月, 租赁 DVD 两次的会员至少在一个月中返还 DVD 一次;2、假设在所有的会员中，60%的会员每月租赁 DVD 两次，另外的 40%只租一次。3、每个会员每个月租赁次数不得超过 2 次，每次获得 DVD 的数量不超过 3 张。4、会员不重复租用同一张 DVD 盘，DVD 盘在租用过程中没有损坏； 3.符号说明1、 表示第 个人对第 张 DVD 盘的会员满意度的数字，ijcij2、 表示第 个
8、人对第 张 DVD 盘的偏爱系数；0,ijijijca当 当 ij3、 ； DVjxij 种位 会 员 不 租 赁 第， 第 种位 会 员 租 赁 第， 第 i14、 表示网站拥有第 张 DVD 盘的数量；jbj5、n 为网站的总会员数；6、 为第 阶段租赁出的 DVD 的数量ku4. 模型的建立与求解4.1 问题 1 模型的建立与求解4.1.1.1 简单模型的建立根据对问题的分析，考虑到 60%的会员每月租赁 DVD 两次，而另外 40%只租一次，为了资源的充分利用，第一批 DVD 应当全部租赁完，且返还的 DVD 数量至少要能满足第二批会员租赁。因此，我们建立以下的模型：模型 %6050x
9、np其中 为希望看到某种 DVD 盘的会员人数比例； 为网站的会员总人数 ；p n万10为网站拥有该种 DVD 盘的数量。x即得: ,因此至少需要 DVD 盘的数量为 。n165 p165利用数学软件 求解列表如下(程序见附录 2.2.1)：0.4cMathermiDVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5p20% 10% 5% 2.5% 1%（ 张 ）x6250 3125 1563 782 3134.1.1.2 模型的进一步思考154进一步分析，我们发现租赁两次的会员分阶段呈周期性的返还 DVD，而模型 实际上考虑了周期为 15 天的情况，而有的会员在很短的时间内就返还了
10、，造成了资源的浪费，故我们对模型进行改进。设租赁两次会员的返还周期为 ,在一个月内分为T（ 个阶段，设 为第 阶段租赁出的 DVD 的数量，建立如下模型：Ts30)Nkuxmin模型为 取 数 的 最 小 整 数 上 界， 定 义 符 号 Ts skxuqunpks30),21(,%5.t11 L即为使会员的满意度最高，网站拥有该种 DVD 盘的最少数量为：sqnpx1)(5重新考虑问题 1，特别地取 ，即分为 4 个阶段。如果取周期为 天，一个月s 10可分为 个阶段，根据模型 利用数学软件 求解列表如下：3s .4cMathermiDVD 名称 DVD1 DVD2 DVD3 DVD4 DV
11、D5p20% 10% 5% 2.5% 1%（ 张 ）x4596 2298 1149 575 2304.1.2 考虑连续三个月的返还连续考虑长时间几个月的返还情况，设 为第 阶段租赁出的 DVD 的数量，则到ku第 阶段时，第 阶段租赁出的 DVD 的数量 此时应该全部返回，且要保证在这几skk月内至少 95%的会员能够看到该 DVD，建立如下数学模型为： 模型为 取 数 的 最 小 整 数 上 界， 定 义 符 号 TsxquxuNksqntxskks30, ,)1(%95.min21L其中每月租赁两次会员的返还周期为 ； 为网站拥有该种 DVD 盘的数量。T在问题 1 中，为了保证在三个月内
12、至少 95%的会员能够看到该 DVD，我们分别取了的情况，即每月分别分为 个阶段，利用数学软件 求解列表4,32s 4,32 0.4cMathermi如下：DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5155p20% 10% 5% 2.5% 1%2s4233 2117 1059 530 21233481 1741 871 436 175张x43190 1595 789 399 1604.2 问题 2 模型的建立与求解4.2.1 模型的建立与分析分析问题 2 及表 2 的数据可知：会员满意度的数字越小表示会员的偏爱度越高，如果要获得最大的满意度，DVD 应该尽量分配给满意度的数字
13、越小的会员。而每位会员同时至多只能获得 3 张 DVD，且获得第 种 DVD 的人数不能超过现有该种 DVD 的数量，j即 10,201Lixji，其中 为第 种 DVD 的数量；2,3,01jbij jb考虑到目标函数的控制条件，我们定义了偏爱系数 ，即偏爱系数0,1ijijijca当 当越大，表示满意度越高，偏爱系数越小，表示满意度越低。为了使会员的满意度最高，即会员总的偏爱度最大，我们考虑目标函数 的最大值。102ijijxa结合以上条件，我们建立数学模型如下：，102maxijijxaZ模型0,120,3,1,.102ijijijijjijjicaxbts当 当或 L4.2.1 问题
14、4.2 的解答根据模型，结合题目所给的数据，利用数学软件 编程进行求解(程序0.8LINGO源代码见附录 1.1 program model)，在会员获得最大的满意度时，对这些 DVD进行最优分配，现具体列出前 30 位会员（即 C0001C0030）分别获得 DVD 的情况，如下表：会员编号 DVD 编号 会员编号 DVD 编号156C0001 D003 D017 D020 C0016 D007 D011 D017C0002 D001 D006 D012 C0017 D004 D007 D017C0003 D013 D017 D020 C0018 D007 D018 D020C0004 D0
15、07 D011 D012 C0019 D006 D017 D020C0005 D006 D007 D019 C0020 D006 D009 D020C0006 D019 D006 D012 C0021 D006 D013 D015C0007 D007 D011 D020 C0022 D003 D007 D011C0008 D013 D014 D020 C0023 D011 D012 D013C0009 D003 D007 D015 C0024 D007 D011 D017C0010 D010 D012 D017 C0025 D007 D017 D020C0011 D003 D008 D010 C0026 D003 D006 D016C0012 D007 D011 D019 C0027 D006 D007 D010C0013 D006 D017 D019 C0028 D005 D007 D009C0014 D006 D016 D017 C0029 D012 D013 D020C0015 D007 D017 D020 C0030 D003 D017 D0204.3 问题 3 模型的建立与求解4.3.1
