租赁碟片规划问题数模比赛题目见解

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

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

3、号（由赛区组委会评阅前进行编号）： 2013高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评阅人 评分 备注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： DVD在线租赁问题 摘要：本文针对DVD租赁问题，利用优化理论等方法建立了目标规划和DVD最优分 配模型，分别确定了合理的DVD购买与分配方案。 问题一中，基于需求预测基础上的 DVD购买方案设计中，我们考虑均值情况。具体结 果见正文。同时，我们也利用目标规划的方法建立了优化购置模型，以所需购买的DVD 总量最小化

4、为目标，以会员租赁情况、租赁具体数量以及观看人数的限制为约束条件。 最后利用Lingo软件编程求解可得到以下结果：至少50%能看到的情况下最少购置 DVD 数量为 25620张。DVD15 分别购置 12687、7029、3264、1809、831 张。至少 95%能 看到的情况下最少购置 8540张。DVD15分别购置4229、2343、1088、603、277张。 问题二中，我们引入0-1变量，并且以会员的满意度最大作为目标函数，会员每次可 租赁3张DVD和每种DVD分配的数量不大于限制数量作为约束条件建立 0-1规划模型， 在模型求解中由于数据庞大不好处理，我们最后利用lingo软件编程

5、求解，前六位会员 DVD分配结果如下，具体结果见正文。 会员编号 C0001 C0002 C0003 C0004 C0005 C0006 分配DVD D008, D041, D098 D006 D044, D062 D032, D05Q D080 D007, D018, D041 D011, D066, D068 D019, D053, D066 问题三中，我们在问题一中的 DVD购置优化模型和问题二中的满意度最大化模型的基 础上，建立了双目标整数规划模型，优先考虑满意度最大，从而解出此目标作为约束条 件，求解第二个目标函数，从而求出 DVD购买的最小量。前六位会员 DVD分配数量 如下具体结

6、果见正文。 会员编号 C0001 C0002 C0003 C0004 C0005 C0006 DVD数量 24 33 30 33 24 25 问题四中，我们考虑商家的利益、每个会员的满意度以及每个年龄段会员的偏爱对于 DVD的购买量以及会员的订单分配进行模型优化。 关键字：目标规划、满意度、0-1规划 一、问题重述 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音 像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传 播范围广泛、直达核心消费群、强烈的互动性、感官性强、

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

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

9、考虑表2,并假设表2中DVD的现有数量全部为0。如果你是网站经营管 理人员，你如何决定每种 DVD的购买量，以及如何对这些 DVD进行分配，才能使一 个月内95%的会员得到他想看的DVD，并且满意度最大？ 4）如果你是网站经营管理人员，你觉得在 DVD的需求预测、购买和分配中还有哪 些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。 表1对1000个会员调查的部分结果 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人数 200 100 50 25 10 表2现有DVD张数和当前需要处理的会员的在线订单（表格格式示例） DVD编号 D001 D002 D

10、003 D004 DVD现有数量 10 40 15 20 会员 在线 订单 C0001 6 0 0 0 C0002 0 0 0 0 C0003 0 0 0 3 C0004 0 0 0 0 注：D001D100表示100种DVD, C0001C1000表示1000个会员,会员的在线订单用 数字1,2,表示，数字越小表示会员的偏爱程度越高，数字 0表示对应的DVD当前不 在会员的在线订单中。 二、问题分析 随着互联网的快速发展，音像制品的在线租赁也逐步走进我们的生活，本题就是 在该背景下对DVD的需求预测、购买和分配进行一定的分析从而确定最优化的分配方 案，具有较强的实际意义。问题的特点是在所给的

11、不同情况下对DVD进行合理分配， 难点是相关约束条件的确定。 对于问题一，由历史数据显示：60%的会员每月可以租赁两次，另外的40%每月只能租 一次。根据大数定理：每个月租两次的会员与租一次会员的人数之比为3:2。假设租两 次的会员分别在月初和月中旬分别借一次DVD，并且再月中旬和月末分别还掉所借的 DVD ;租一次会员在月中旬借，保证部分 DVD能够被重复利用，减少购买量，从而减 少运营成本。 我们也可以通过题目所给的相关数据，在此基础上以会员租赁情况、租赁具体数量 以及愿意观看人数的最小限制等为约束条件，DVD数量最小为目标函数建立了规划模 型。 对于问题二，结合会员的在线订单以及偏好情况

12、，如何将 DVD充分的分配给会员是本 问题的重点。根据实际情况，我们将将 b定位满意度，其中bj 1 / aj aj 0。假设每个 会员每次租的DVD数为3张。本问题则所要解决的是如何分配 DVD使所有的满意度 之和达到最大。我们利用0 1规划，0表示会员得不到该DVD ,1表示会员得到该DVD， 建立约束条件，以满意度之和最大为目标函数，从而将问题转化为优化问题。 对于问题三，本问题需要满足两个要求：1、DVD的购买量最小，2、所有会员的满意 度之和最大。考虑到95%的会员会组DVD和60%的会员会租两次DVD，在问题一、二 的基础上，我们建立双目标整数规划，设立两个0 1变量：mi,yi分

13、别表示是否租DVD 和是否租两次 DVD 。首购先在满足满意度之和最大的情况下确定会员的订单，再根据 满意度最大和会员的订单确定 DVD 的最小购买量。 对于问题四，对于 DVD 的购买量以及会员的订单分配还需要考虑商家的利益、每个会 员的满意度以及每个年龄段会员的偏爱； 我们利用 Lingo 软件对本题的各个模型进行编程求解，也解决了部分数据过于庞大 较难处理的问题。 三、模型假设与符号说明 模型假设： 1.60%的会员每月租赁 DVD 两次，而另外的 40%只租一次。 2. 会员每次可租 3张 DVD ，会员在归还 DVD 之后可再次进行租赁。 3. 假设该网站对 1000 名会员的调查结

14、果可较为完整的反映 10 万会员对 DVD 的需求与 喜好。 4. 假设忽略一切 DVD 折损与丢失问题。 5. 假设每个会员都能自觉的严格的遵守网站关于租赁周期的规定，即他们都能在规定的 时间内归还所借的DVD 符号说明： di10 万会员中愿意观看第 i 种的人数 pi10 万会员中愿意观看第 i 种的人的概率 li第i种DVD被租一次的数量 si第 i 种 DVD 被租两次的数量 lij第 i 种 DVD 第 j 个月被租一次的数量 sij第 i 种 DVD 第 j 个月被租两次的数量 Li全部被租赁的 DVD 的数量 c第i名会员获得第j张DVD时的满意度，c,j 0，该值取倒数 bj

15、第 j 种 DVD 的购买量 xij第 i 个会员对第 j 类 DVD 的需求， 0-1变量 mi第 i 个会员是否租 DVD ， 0-1 变量 yi第 i 个会员是否租两次 DVD ， 0-1 变量 tij第 i 个会员对第 j 种 DVD 的租赁次数 aj第 j 种 DVD 现有数量 wij第 i 个会员对于 分给他的第 j 种 DVD 的满意度 四、模型建立与求解 4.1 DVD购置方案的模型 4.1.1 模型一建立 本文提及的样本基数足够大，所以题目中出现的 60%和 40%的频率数据可直接用作 概率Pi。我们在处理问题一时可以不必考虑每个会员的具体租赁、归还 DVD时间，而 只考虑每

16、个月内两次分配方案。 在 DVD 被租赁出去后，对于某种 DVD ，从平均意义 上看，应该是均匀的分布在每月只租赁 1次 DVD 的会员和每月租赁两次 DVD 的会员， 即是说在月中旬，该 DVD 将有 60%被归还。 (1) 50%的情况 在上述所说的网站运营模式下，设第i种DVD有Li张，则假设在1号被分配出去， 在月中旬时，又有0.6Li张被归还。这样，为保证1个月内至少50%的会员时看到该DVD 则应满足： (1 60%) Li 100000* pi *50% (2) 95%的情况 同理可知，为保证3个月内至少95%的会员时看到第i种DVD则应满足： 3*(1 60%)Li 10000

17、0* pi *95% 4.1.2模型二建立 通过题目中对会员喜好的调查，我们得到表 1所示结果，并由此可以求出1000位 会员愿意观看各类DVD的比例Pi,由于这1000人是10万会员中的随机子样本，所以该 比例也可以用于计算10万会员的情况。结果如表2所示 表1对1000个会员调查的部分结果 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人数 200 100 50 25 10 表12对10万位会员调查的部分结果 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人数 di 20000 10000 5000 2500 1000 （1）50%的情况

18、 首先以最小DVD数量为目标函数建立优化模型: 5 min f Li i 1 2* 3 lidi *0.5, i 1,2,3,4,5 5 2*si i 1 5 2* li i 1 li SLi 其中第一个约束条件表示对于每种 DVD来说，准备的DVD张数必须保证希望看 到该DVD的会员中至少50%在一个月内能够看到该 DVD。第二个约束条件是由题目可 知60%的会员每月租赁DVD两次，而剩余的40%会员只租一次，该3:2的比例是一定 的。第三个约束是被租赁的 DVD总数等于被租一次和被租两次的 DVD数量之和。 （2）95%的情况 以最小DVD数量为目标函数建立优化模型，第一个约束条件是由题目

19、可知60% 的会员每月租赁DVD两次，而剩余的40%会员只租一次，三个月内这个比例是一定的。 第二个约束条件是指每个月的 DVD总数是不变的。第三个约束条件表示对于每种DVD 来说，准备的DVD张数必须保证希望看到该 DVD的会员中至少95%在三个月内能够 看到该DVD。第四个约束是被租赁的 DVD总数等于三个月内被租一次和被租两次的 DVD数量之和。综上所述可得到以下模型: min L/3 5 j，j 1,2,3 52.1 1,2,3,4,5 53.1 1,2,3,4,5 2*Sj i 1 5 I Uj i 1 li1Sili2 li1S1li3 3 lij2*qdi*0.95, i 1,2

20、,3,4,5 j i 53 Lhsj i 1 j 1 4.1.2模型一求解与分析 模型一结果分别如表3、4所示: 表3保证1个月内至少50%的会员时看到DVD情况下的购买方案 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 购置数量 6250 3125 1563 782 313 表3保证3个月内至少95%的会员时看到DVD情况下的购买方案 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 购置数量 2084 1042 521 261 105 4.1.3模型二求解 （1）50%的情况 用LINGO软件编程求解得到最佳的 DVD购置方案如表5所示（具体程序见附录程 序1）

21、最少购置DVD数量为25620张 表5 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 购置数量 12687 7029 3264 1809 831 (2) 95%的情况 用LINGO软件编程求解得到最佳的DVD购置方案如表6所示(具体程序见附录程 序2)最少购置DVD数量为张。 表6 DVD名称 DVD1 DVD2 DVD3 DVD4 DVD5 购置数量 4229 2343 1088 603 277 4.2 1000位会员在线订单的分配 4.2.1模型建立 0 会员i没有选择第j种DVD 首先引入0-1变量XjXjj1会员i选择第j种DVD 由题目可知，会员的在线订单用数字1,2

22、,表示，数字越小表示会员的偏爱程度越 高，数字0表示对应的DVD当前不在会员的在线订单中。q表示偏爱程度。由此可知, 当所有会员的偏爱程度之和最小时，满意度最高。因为 0为特例，所以考虑非零数的倒 数。目标函数转化为倒数之和的最大值。由此引入满意度的定义。 第i个会员对分给他第j种DVD的满意度表示为 Cij Wj ,Cij 0,Cj 111 其中-作为分母表示会员得到最想要的 3张，满意度最大，即100%满意 123 第i位会员的满意度Wi表示为 100 Wixij wij j 1 我们以会员的满意度最大作为目标函数，会员每次可租赁3张DVD和每种DVD 分配的数量不大于限制数量作为约束条件

23、建立以下模型： 100 max fwi i 1 100 xij 3 j 1 1000 Xij 3j, j 1,2,L ,100 i 1 422模型求解与分析 利用LINGO软件编程求解可得表7所示结果（具体程序见附录） 表7 会员编号 C0001 C0002 C0003 C0004 C0005 C0006 D008, D006 D032 D007, D011 , D019, 分配DVD D041, D098 D044, D062 D05Q D080 D018, D041 D066, D068 D053, D066 会员编号 C0007 C0008 C0009 C0010 C0011 C0012

24、 D008, D031, D053 D055, D059, D002, 分配DVD D026, D081 D035 D071 D078 D100 D060, D085 D063, D066 D031 , D041 会员编号 C0013 C0014 C0015 C0016 C0017 C0018 D021, D023 D013 D055, D047, D041 , 分配DVD D078, D096 D052 D089 D06Q D085 D084, D097 D051 , D067 D060, D078 会员编号 C0019 C0020 C0021 C0022 C0023 C0024 D066,

25、 D045 D045 D038, D029, D037, 分配DVD D084, D086 D061, D089 D05Q D053 D055, D057 D081 , D095 D041 , D076 会员编号 C0025 C0026 C0027 C0028 C0029 C0030 分配DVD D009, D022 D05Q D008, D026, D037, D069, D081 D068, D095 D058 D078 D034, D041 D030, D055 D062 D098 4.3 一个月内的订单分配 4.3.1模型建立 本问题是根据订单确定各种 DVD 的购买数量以及如何进行分

26、配，使 95%的会员 能看到想看的 DVD ，并且满意度要最大， 由以上要求可以建立一个双目标整数规划， 在达到满意度最大的前提下尽量使购买的 DVD 数量最少，具体约束条件如下： 一个月内有60%勺会员可租两次DVD且一次为3张DVD因此每个会员一个月内 所租的DVD数量为3或者6,约束条件表示为 100 xij j1 3*(1 yi)* mi,i 1,2,L ,1000 11 95%的会员会看到他们想看的 DVD ，可得约束条件 1000 mi i1 1000*95% 60%的会员会租两次 DVD ，则所租两次的会员人数为为总人数的 60%，可得如 下约束表达式 1000 yi 950*6

27、0% i1 每种 DVD 的购买量与其所被租的次数有关，表达式为 1000 b jtij i1 tij xij, yi 0 xij /2, yij 1 xij / 2, yij 综上，可得到如下模型： 100 1000 100 min f bj ,max ff ij ij * aij j1 i 1 j 1 100 x ij 3*(1yi) * mi ,i 1,2,L ,1000 j1 1000 mi ；d 1000*95% i1 1000 yi 950*60% i1 0 1000 xij , yi bj tij , tij i1 432模型求解 本模型为双目标模型，因此可分两步骤求解： 先求解

28、满意度最大，再根据已知的最大满意度，求解DVD购买最小量。由于变量过 多，因此我们假定前600人租两次DVD，即y(i)已经确定。利用LINGO软件编程求解 可得表8所示结果(具体程序见附录) 表8 DVD编号 DVD数量|DV编号 DVD数 量 DVD编号 DVD数 量 DVD编号 DVD数 量 DVD编号 DVD数 量 D001 24 D021 32 D041 43 D061 21 D081 29 D002 33 D022 26 D042 34 D062 32 D082 16 D003 30 D023 32 D043 25 D063 31 D083 24 D004 33 D024 25 D

29、044 32 D064 37 D084 21 D005 24 D025 26 D045 36 D065 29 D085 31 D006 25 D026 28 D046 29 D066 36 D086 25 D007 29 D027 29 D047 30 D067 27 D087 31 D008 28 D028 19 D048 23 D068 30 D088 23 D009 32 D029 23 D049 27 D069 35 D089 23 D010 27 D030 32 D050 31 D070 35 D090 29 D011 27 D031 28 D051 35 D071 32 D091

30、31 D012 30 D032 30 D052 26 D072 30 D092 28 D013 25 D033 33 D053 31 D073 25 D093 25 D014 28 D034 28 D054 23 D074 32 D094 27 D015 22 D035 38 D055 27 D075 24 D095 30 D016 38 D036 31 D056 34 D076 22 D096 24 D017 31 D037 26 D057 30 D077 23 D097 31 D018 27 D038 26 D058 27 D078 30 D098 26 D019 35 D039 25 D

31、059 32 D079 25 D099 19 D020 32 D040 31 D060 33 D080 31 D100 33 4.4 DVD的需求预测、购买和分配问题 4.4.1模型建立 主要考虑到商家的经济利益，其中包括会员费用 y, DVD单价为d,邮费为b,则得 到商家盈利最大： 1001000 xy d *bjc* 3*(1yi) * mi j 1i 1 约束条件如下： 1、第 j 种的 DVD 购买量不大于所有会员对该种 DVD 的需求量： xij,yi 0 xij / 2,yij 1 1000 b t t j ij ij i1 2、购买的 DVD 总数量为： 3、一个月内有60%勺

32、会员可租两次DVD且一次为3张DVD因此每个会员一个月 内所租的DVD数量为3或者6,约束表达式如下： 100 xij 3*(1yi)* mi,i 1,2,L ,1000 j1 综上，可得到最终单规划模型： 五、 论文评价 评价： 问题一中，我们先利用均值思想建立了简单模型，假设了每月借一次的会员是在 1 号借出月末归还，每月借两次的会员在月询中借还碟片的情况，比较符合现实。之后通 过对限制条件与目标函数的研究， 建立了更为合理完善的规划模型。 整体思路清晰明确。 问题二中，我们利用题目所给定义制定了一个满意度指标，以总体满意度最大为目 标函数，借助 Lingo 软件的强大的求解 01 规划的功能作出了全局最优解。 问题三从宏观上考虑，利用等效的思想将问题大为简化，求出了具有普遍意义的较 优解，避免了繁杂的微观细节以及只是某一特例的情况。 在问题四中，我们通过对商家的利益、每个会员的满意度以及每个年龄段会员的偏 爱等因素的分析优化了 DVD 的购买量以及会员的订单分配的相关模型。 总之，本模型简单明确，具有一定的实用性与现实意义。 六、参考文献 1 姜启源