2005年全国大学生数学建模国家二等奖获奖论文 DVD在线租赁的研究 尹作龙,姚明,金伟 指导教师汪晓银 摘要 随着信息时代的到来,网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度,面向其会员群提供日益专业化和便捷化的服务。例如,音 像制品的在线租赁就是一种可行的服务。本文主要讨论了在线DVD租赁的问题,对网站 如何购买DⅦD,如何分配DⅦD进行了一些研究。对于问题一,我们首先把会员根据每月 租赁次数分成A、B两类,并对两类会员归还日期作了合理的假设,根据求出DVD归还 的期望值。最后求得会员归还一张DVD的时间期望为12天。然后用DVD的周转次数来 计算网站对某种DVD的购买量,最后根据问题的要求,求得每种DVD至少准备的张数如 DVD名称 DVDI DVD2DVD3 DVD4 DVDs 个月内至少50% 4000 2000 1000 看到的最少张数 三个月内至少95% 2534 267 634 317 127 看到的最少张数 问题二,我们首先对满意度进行了定义,并作出相应的假设。根据假设建立 规划模型,用 LINGO软件编程求得各种DVD的分配方案。我们根据实际情况修改了偏 爱程度,再次用 LINGO编程求解,得出第二中分配方案。第一种分配方案的总偏爱度 U为7924,有30张DVD分配给了没有预订这些DⅤD的会员;第二种分配方案的总偏 爱度U为8191,有8张DVD分配给了没有预订这些DVD的会员。虽然第一种分配方 案的总偏爱度优于第二种,但是经证明无论怎么分配,至少有8张DVD会分配给没有 预定这些DVD的会员,因此我们选择第二种分配方案 问题三,根据满意度最大,我们建立了一个规划模型,由于模型难以用计算机求解, 我们改用计算机仿真来模拟现实购DVD方案,模拟生成的购买的总DVD数为3086。 问题四,在DVD的需求预测、购买和分配中重要问题的研究中,首先研究了DVD 的需求预测,并建立了灰色GM(1,1)模型,灰色GM(1,1)模型能够克服相关数 据不足的缺陷和避免人为因素的影响。这表明基于灰色理论的预测方法,适合于对DD 在线租赁业务趋势进行预测。该方法是切实可行并有效的,并对DWD在线租赁业务发展 规划有重要参考价值。然后从网站的赢利角度出发,建立了一个以赢利函数为目标的线 性规划模型,此模型在租赁方面有着较髙的参考价值。 最后我们对我们所建立的模型及求解方案进行评价,推广。我们考虑到对于更大规 模问题,现有模型的求解就会困难。因此我们想了模型的另外一个算法:贪心算法。贪 心算法速度快,但得到的解难以达到最优 关键词]:DVD在线租赁0-1规划概率模型计算杋仿真灰色GM(l,1模型
2005 年全国大学生数学建模国家二等奖获奖论文 1 DVD 在线租赁的研究 尹作龙，姚明，金伟 指导教师 汪晓银 [摘 要]： 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音 像制品的在线租赁就是一种可行的服务。本文主要讨论了在线 DVD 租赁的问题，对网站 如何购买 DVD，如何分配 DVD 进行了一些研究。对于问题一，我们首先把会员根据每月 租赁次数分成 A、B 两类，并对两类会员归还日期作了合理的假设，根据求出 DVD 归还 的期望值。最后求得会员归还一张 DVD 的时间期望为 12 天。然后用 DVD 的周转次数来 计算网站对某种 DVD 的购买量，最后根据问题的要求，求得每种 DVD 至少准备的张数如 下。 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 一个月内至少 50% 看到的最少张数 4000 2000 1000 500 200 三个月内至少 95% 看到的最少张数 2534 1267 634 317 127 问题二，我们首先对满意度进行了定义，并作出相应的假设。根据假设建立 0—1 规划模型，用 LINGO 软件编程求得各种 DVD 的分配方案。我们根据实际情况修改了偏 爱程度，再次用 LINGO 编程求解，得出第二中分配方案。第一种分配方案的总偏爱度 U 为 7924，有 30 张 DVD 分配给了没有预订这些 DVD 的会员；第二种分配方案的总偏 爱度 U 为 8191，有 8 张 DVD 分配给了没有预订这些 DVD 的会员。虽然第一种分配方 案的总偏爱度优于第二种，但是经证明无论怎么分配，至少有 8 张 DVD 会分配给没有 预定这些 DVD 的会员，因此我们选择第二种分配方案。 问题三，根据满意度最大，我们建立了一个规划模型，由于模型难以用计算机求解， 我们改用计算机仿真来模拟现实购 DVD 方案，模拟生成的购买的总 DVD 数为 3086。 问题四，在 DVD 的需求预测、购买和分配中重要问题的研究中，首先研究了 DVD 的需求预测，并建立了灰色 GM（1，1）模型，灰色 GM（1，1）模型能够克服相关数 据不足的缺陷和避免人为因素的影响。这表明基于灰色理论的预测方法，适合于对 DVD 在线租赁业务趋势进行预测。该方法是切实可行并有效的，并对 DVD 在线租赁业务发展 规划有重要参考价值。然后从网站的赢利角度出发，建立了一个以赢利函数为目标的线 性规划模型，此模型在租赁方面有着较高的参考价值。 最后我们对我们所建立的模型及求解方案进行评价，推广。我们考虑到对于更大规 模问题，现有模型的求解就会困难。因此我们想了模型的另外一个算法：贪心算法。贪 心算法速度快，但得到的解难以达到最优。 [关键词]：DVD 在线租赁 0—1 规划 概率模型 计算机仿真 灰色 GM（1，1）模型
2005年全国大学生数学建模国家二等奖获奖论文 、问题的重述 考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员,订购DVD 租赁服务。会员对哪些DVD有兴趣,只要在线提交订单,网站就会通过快递的方式尽 可能满足要求。会员提交的订单包括多张DVD,这些DⅤD是基于其偏爱程度排序的 网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不 得超过2次,每次获得3张DVD。会员看完3张DVD之后,只需要将DVD放进网站 提供的信封里寄回(邮费由网站承担),就可以继续下次租赁。请考虑以下问题: (1)网站正准备购买一些新的DVD,通过问卷调查1000个会员,得到了愿意观 看这些DⅤD的人数。此外,历史数据显示,60%的会员每月租赁DVD两次,而另外的 40%只租一次。假设网站现有10万个会员,对表1中的每种DVD来说,应该至少准备 多少张,才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD?如 果要求保证在三个月内至少95%的会员能够看到该DVD呢? (2)表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会 员的在线订单,如何对这些DVD进行分配,才能使会员获得最大的满意度?请具体列 出前30位会员(即C0001~C0030)分别获得哪些DVD (3)考虑表2,并假设表2中DVD的现有数量全部为0。如果你是网站经营管理 人员,你如何决定每种DVD的购买量,以及如何对这些DVD进行分配,才能使一个 月内95%的会员得到他想看的DVD,并且满意度最大? (4)如果你是网站经营管理人员,你觉得在DVD的需求预测、购买和分配中还有 哪些重要问题值得研究?请明确提出你的问题,并尝试建立相应的数学模型 二、问题的假设 1、假设所有的DVD都不能拷贝 2、假设调查资料具有一定代表性 3、假设所有会员自觉遵守会员规定 4、假设在租赁和归还过程中DⅴD的遗失或损坏忽略不计 5、假设DVD的种类与购DVD费用无关 、符号的说明 符号 符号说明 该网站拥有的总会员数 第i个会员在线定单中第j种DVD的需求情况 第i个会员对第j种DVD的偏爱程度 第i张DVD的现有量 M愿意观看第i种DVD的总人数 P 愿意观看第i种DVD的人数占总人数的百分比 2
2005 年全国大学生数学建模国家二等奖获奖论文 2 一、问题的重述 考虑如下的在线 DVD 租赁问题。顾客缴纳一定数量的月费成为会员，订购 DVD 租赁服务。会员对哪些 DVD 有兴趣，只要在线提交订单，网站就会通过快递的方式尽 可能满足要求。会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的。 网站会根据手头现有的 DVD 数量和会员的订单进行分发。每个会员每个月租赁次数不 得超过 2 次，每次获得 3 张 DVD。会员看完 3 张 DVD 之后，只需要将 DVD 放进网站 提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题： （1）网站正准备购买一些新的 DVD，通过问卷调查 1000 个会员，得到了愿意观 看这些 DVD 的人数。此外，历史数据显示，60%的会员每月租赁 DVD 两次，而另外的 40%只租一次。假设网站现有 10 万个会员，对表 1 中的每种 DVD 来说，应该至少准备 多少张，才能保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD？如 果要求保证在三个月内至少 95%的会员能够看到该 DVD 呢？ （2）表 2 中列出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会 员的在线订单，如何对这些 DVD 进行分配，才能使会员获得最大的满意度？请具体列 出前 30 位会员（即 C0001~C0030）分别获得哪些 DVD。 （3）考虑表 2，并假设表 2 中 DVD 的现有数量全部为 0。如果你是网站经营管理 人员，你如何决定每种 DVD 的购买量，以及如何对这些 DVD 进行分配，才能使一个 月内 95%的会员得到他想看的 DVD，并且满意度最大？ （4）如果你是网站经营管理人员，你觉得在 DVD 的需求预测、购买和分配中还有 哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。 二、问题的假设 1、假设所有的 DVD 都不能拷贝 2、假设调查资料具有一定代表性 3、假设所有会员自觉遵守会员规定 4、假设在租赁和归还过程中 DVD 的遗失或损坏忽略不计 5、假设 DVD 的种类与购 DVD 费用无关 三、符号的说明 符号 符号说明 V 该网站拥有的总会员数 Dij 第 i 个会员在线定单中第 j 种 DVD 的需求情况 DLij 第 i 个会员对第 j 种 DVD 的偏爱程度 yi 第 i 张 DVD 的现有量 Mi 愿意观看第 i 种 DVD 的总人数 Pi 愿意观看第 i 种 DVD 的人数占总人数的百分比
2005年全国大学生数学建模国家二等奖获奖论文 R为满足会员要求的百分比数 会员获得DVD后所得到的总偏爱度,其值越小满意度越高 四、问题的分析及模型的建立及求解 41问题的背景资料 Netflix目前是美国最大的DVD出租网站,现在公司预计可在2006年达到500万订 户。这家网站的经营方法是,顾客在成为网站的固定会员后,可在网站上选取自己喜欢 的DⅤD影片,该公司现有DVD种类有5万多种,包括一些最新面世的大片,由这家 网站快速寄送到顾客的登记地址,每次最多3张。顾客可以无限期地借用这些影片,但 只有在寄回这些影片后才能借用新影片。顾客只需每月缴纳19.95美元的会员费,而 邮寄费用全部由网站支付。对顾客而言,坐在电脑前拖动几下鼠标就可得到中意的影片, 既省时又省力 据统计,超过60%的美国家庭至少拥有一台DVD影DVD机。去年,美国人在家 看DVD的时间平均为78小时,比2000年上升了53%。DVD的销量和出租量则上升 了6765%5。 42问题一的求解 42.1问题一模型的建立与求解 对问题一的分析,我们根据实际情况作了一些积极的假设,并简化了模型。从网站 经营者的角度出发,出于对自身赢利的考虑,希望DⅤD的周转越快越好。那么我们就 从DVD的周转情况来考虑对DVD数的需求量。 由题目我们把所有会员分成A、B两类:如表1 表1 类型每月租赁DVD次数所占会员总数的百分比会员人数 A类 两次 60% 60000 B类 40% 40000 考虑到DVD的周转,我们对两类会员作以下假设 A类会员归还一张DVD的时间X范围为3-15天 B类会员归还一张DVD的时间K2范围为3-30天 根据现实情况,我们假设X,脸2都服从等概率分布,则: EH,=15+3 EX =16.5 2 则会员归还一张DVD的时间期望为:=0.6×EX+04×EX2=12天。这就是说每张 DVD在会员手中保存的时间大约在12天, 那么: 在一个月内DVD的周转次数为:N=30÷12=25 在三个月内DVD的周转次数为:N=90÷12=7.5。(设30天为一个月) 根据题目中调査1000人愿意观看各种DVD的人数,我们得到会员愿意观看各种 DVD的经验概率分布统计结果如下(见表2): 表2
2005 年全国大学生数学建模国家二等奖获奖论文 3 R 为满足会员要求的百分比数 U 会员获得 DVD 后所得到的总偏爱度，其值越小满意度越高 四、问题的分析及模型的建立及求解 4.1 问题的背景资料 Netflix 目前是美国最大的 DVD 出租网站，现在公司预计可在 2006 年达到 500 万订 户。这家网站的经营方法是，顾客在成为网站的固定会员后，可在网站上选取自己喜欢 的 DVD 影片，该公司现有 DVD 种类有 5 万多种，包括一些最新面世的大片，由这家 网站快速寄送到顾客的登记地址，每次最多 3 张。顾客可以无限期地借用这些影片，但 只有在寄回这些影片后才能借用新影片。顾客只需每月缴纳 19．95 美元的会员费，而 邮寄费用全部由网站支付。对顾客而言，坐在电脑前拖动几下鼠标就可得到中意的影片， 既省时又省力。 据统计，超过 60%的美国家庭至少拥有一台 DVD 影 DVD 机。去年，美国人在家 看 DVD 的时间平均为 78 小时，比 2000 年上升了 53%。DVD 的销量和出租量则上升 了 676.5%[5]。 4.2 问题一的求解 4.2.1 问题一模型的建立与求解 对问题一的分析，我们根据实际情况作了一些积极的假设，并简化了模型。从网站 经营者的角度出发，出于对自身赢利的考虑，希望 DVD 的周转越快越好。那么我们就 从 DVD 的周转情况来考虑对 DVD 数的需求量。 由题目我们把所有会员分成 A、B 两类：如表 1 表 1 类型 每月租赁 DVD 次数 所占会员总数的百分比 会员人数 A 类 两次 60% 60000 B 类 一次 40% 40000 考虑到 DVD 的周转，我们对两类会员作以下假设： A 类会员归还一张 DVD 的时间 X1 范围为 3—15 天； B 类会员归还一张 DVD 的时间 X2 范围为 3—30 天； 根据现实情况，我们假设 X1， X2 都服从等概率分布，则： 9 2 15 3 1 = + EX = 16.5 2 30 3 2 = + EX = 则会员归还一张 DVD 的时间期望为：µ=0.6×EX1+0.4×EX2=12 天。这就是说每张 DVD 在会员手中保存的时间大约在 12 天， 那么： 在一个月内 DVD 的周转次数为：N=30÷12=2.5； 在三个月内 DVD 的周转次数为：N=90÷12=7.5。（设 30 天为一个月） 根据题目中调查 1000 人愿意观看各种 DVD 的人数，我们得到会员愿意观看各种 DVD 的经验概率分布统计结果如下（见表 2）： 表 2
2005年全国大学生数学建模国家二等奖获奖论文 DVD名称 DVDI DVD2 DVD3 DVD4 DVDS 经验概率P 20% 10% 2.5%1% R为满足会员要求的百分比:一个月为50%;三个月为95% 因此愿意观看第i种DVD的人数M为:M=×P×R=1000001×R(V为总会 员数)。 那么所需要DVD的最小数量为:S=M÷N。(向上取整) 我们得到S的函数表达式:S=XP×R÷N 求解得到每种DVD的准备张数(见表3): DVD名称 DVDI DVD2 DVD3 DVD4 DVDS 个月内至少50% 4000 2000 1000 500 200 看到的最少张数 三个月内至少95% 看到的最少张数 2534 1267 634 317 127 作为一个租赁网站的经营者,总是希望赢利更多,就要提高周转次数,减少周转天 数,这样他的先期投入也将减少。就可以考虑尽可能缩短租借的天数,来增加网站的赢 利和减少先期投入。若我们将归还时间定为3-9天,则期望为6。一个月的DD1所需 最少张数为2000张(小于4000张)。 4.3问题二模型的建立与求解 43.1问题二的分析 顾客满意度可以简要地定义为:顾客接受产品和服务的实际感受与其期望值比较的 程度。首先对满意度进行了如下假设:在会员的在线订单D中,数字越小表示会员的 偏爱程度越高,如果会员得到他偏爱程度越髙的DVD,则会员的满意度越大。假设会 员对DVD的偏爱度为:DLn= 11,D=0 该问题的目的就是分配当前的订单,使得这些顾客的满意度最大,可以用0-1规划 模型来求解,定义0-1变量Cn(=1…1000=1…100),C为1时表示第i个顾客租到了 第j种DVD,其值为0时表示没有租到相应的DVD 43.2问题二模型的建立 会员租赁DVD满意度的目标函数为:min∑∑ DL xC 0-1规划模型的约束条件为 1、每个顾客一次能并且只能租到3张DⅤD 2、租赁给会员的每种DⅤD总张数不能超过现有DⅤD数量。 由上述分析得到如下的0-1规划模型:
2005 年全国大学生数学建模国家二等奖获奖论文 4 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 经验概率 Pi 20% 10% 5% 2.5% 1% R 为满足会员要求的百分比：一个月为 50%；三个月为 95%。 因此愿意观看第 i 种 DVD 的人数 Mi 为：Mi=V×Pi×R=100000×Pi×R （V 为总会 员数）。 那么所需要 DVD 的最小数量为：S=M÷N。（向上取整） 我们得到 S 的函数表达式：S=V×Pi×R÷N ； 求解得到每种 DVD 的准备张数（见表 3）： 表 3 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 一个月内至少 50% 看到的最少张数 4000 2000 1000 500 200 三个月内至少 95% 看到的最少张数 2534 1267 634 317 127 作为一个租赁网站的经营者，总是希望赢利更多，就要提高周转次数，减少周转天 数，这样他的先期投入也将减少。就可以考虑尽可能缩短租借的天数，来增加网站的赢 利和减少先期投入。若我们将归还时间定为 3-9 天，则期望为 6。一个月的 DVD1 所需 最少张数为 2000 张（小于 4000 张）。 4.3 问题二模型的建立与求解 4.3.1 问题二的分析 顾客满意度可以简要地定义为：顾客接受产品和服务的实际感受与其期望值比较的 程度。首先对满意度进行了如下假设：在会员的在线订单 Dij 中，数字越小表示会员的 偏爱程度越高，如果会员得到他偏爱程度越高的 DVD，则会员的满意度越大。假设会 员对 DVD 的偏爱度为： ïî ï í ì ¹ = = , 0 11, 0 ij ij ij ij D D D DL 该问题的目的就是分配当前的订单，使得这些顾客的满意度最大，可以用 0-1 规划 模型来求解，定义 0-1 变量 Cij（i=1…1000,j=1…100）, Cij 为 1 时表示第 i 个顾客租到了 第 j 种 DVD，其值为 0 时表示没有租到相应的 DVD。 4.3.2 问题二模型的建立 会员租赁 DVD 满意度的目标函数为： åå= = ´ 1000 1 100 1 min i j DLij Cij 0- 1 规划模型的约束条件为： 1、每个顾客一次能并且只能租到 3 张 DVD； 2、租赁给会员的每种 DVD 总张数不能超过现有 DVD 数量。 由上述分析得到如下的 0-1 规划模型：
2005年全国大学生数学建模国家二等奖获奖论文 DL×C Cn=0,1 0,1变量 >C=3 每位会员租3张DVD C.≤ DVD现有数量的限制 (=1…1000J=1…100 433问题二的求解 对于上述的模型,在用 LINGO编程求解(具体程序请见附件),得到分配方案为 C求得总偏爱度为U=∑∑DxCn为7924由C得到分配了30张DVD给没有要求 预订这些DVD的会员。前30个会员租到DVD的情况如下表4: 会员号c00c0002c000004c0005c00c0007c008c0009c0010 分配 8(1)6(1)32(4)7(1)11(3)19(1)26(3)31(4)53(1)41(6) DvD的[24(7)41[50(2)18(2)6(1)53(266)35(578(3)5(2) 种类号阝398(362(48(1)4(3)68(2)66(4[81(1)71(1)102)85(3) 会员号|c0011c0012c0013c0014c0015c0016C0017c0018c0019c0020 分配159(12(2)21(3)23(2)13(1)10(4)47(2)41(1)66(4)45(1) DVD的|2|63(2)31(1)78(2)52(1)52(4)84(1)51(3)60(2)84(1)61(3) 种类号 66(4)41(7)%6(1)89(6)85(3)97(2)67(1)78(3)86(2)89(2) 会员号C0021C0022c0023C0024c0025c006|c0027c008C0029c0030 分配 45(2)38(3)29(2)37(4)9(1)22(1)50(4)8(1)26(4)37(2) DD的2505)5281(3)41(2)69(2)682)58(134(2)30(2)62(1 种类号|3|53(1)57(1)95(1)76(1)|94(3)95(3)78(7)82(3)551)98(5) 注:括号内的值为会员对该DVD喜好程度。 为使会员得到自己没有预定的DVD总数最少,可以将DL中为11的数增大变为 1000,即将此偏爱程度降低,再如上求解得到一种新的分配方案C,求得总偏爱度U 为8191(>7924),但是经分析,只分配了8张DVD给没有要求预订这些DVD的会员。 事实上这里的8张DVD已经最小,具体原因是,现有DVD总数为3007张,每个人得 到3张DVD,1000个人就得到3000张DVD,则还有7张未出租。根据所给的数据, 第37种DVD现有106张,只有91个会员愿意租此DVD,即第37张DVD按照会员的 需求无论怎么发放,也会有106-91=15张剩余,而总共应该只有7张DVD未出租,这 样就无法满足所有的会员租到自己想看的DVD,而且一定至少有15-7=8张DVD发给 了没有订这8张DVD的会员 比较上面两种分配方案,我们选择第二种分配方案。第二种方案下,前30会员的 租赁情况是只有第25个会员的第3张DVD与第一种分配方案不同,其值为81(4) 44问题三模型的建立与求解
2005 年全国大学生数学建模国家二等奖获奖论文 5 ï ï ï ï î ï ï ï ï í ì = = £ = = ´ å å åå = = = = ( 1 1000, 1 100) 3 0,1 . . min 1000 1 100 1 1000 1 100 1 i L j L C y C C st DL C i ij j j ij ij i j ij ij 4.3.3 问题二的求解 对于上述的模型，在用 LINGO 编程求解（具体程序请见附件），得到分配方案为 Ci,j 求得总偏爱度为 åå= = = ´ 1000 1 100 i j 1 U Dij Cij 为 7924。由 Ci,j 得到分配了 30 张 DVD 给没有要求 预订这些 DVD 的会员。前 30 个会员租到 DVD 的情况如下表 4： 表 4 会员号 C0001 C0002 C0003 C0004 C0005 C0006 C0007 C0008 C0009 C0010 1 8（1） 6（1） 32（4） 7（1） 11（3） 19（1） 26（3） 31（4） 53（1） 41（6） 2 41（7） 44（2） 50（2） 18（2） 66（1） 53（2） 66（6） 35（5） 78（3） 55（2） 分配 DVD 的 种类号 3 98（3） 62（4） 80（1） 41（3） 68（2） 66（4） 81（1） 71（1） 100（2） 85（3） 会员号 C0011 C0012 C0013 C0014 C0015 C0016 C0017 C0018 C0019 C0020 1 59（1） 2（2） 21（3） 23（2） 13（1） 10（4） 47（2） 41（1） 66（4） 45（1） 2 63（2） 31（1） 78（2） 52（1） 52（4） 84（1） 51（3） 60（2） 84（1） 61（3） 分配 DVD 的 种类号 3 66（4） 41（7） 96（1） 89（6） 85（3） 97（2） 67（1） 78（3） 86（2） 89（2） 会员号 C0021 C0022 C0023 C0024 C0025 C0026 C0027 C0028 C0029 C0030 1 45（2） 38（3） 29（2） 37（4） 9（1） 22（1） 50（4） 8（1） 26（4） 37（2） 2 50（5） 55（2） 81（3） 41（2） 69（2） 68（2） 58（1） 34（2） 30（2） 62（1） 分配 DVD 的 种类号 3 53（1） 57（1） 95（1） 76（1） 94（3） 95（3） 78（7） 82（3） 55（1） 98（5） 注：括号内的值为会员对该 DVD 喜好程度。 为使会员得到自己没有预定的 DVD 总数最少，可以将 DLij 中为 11 的数增大变为 1000，即将此偏爱程度降低，再如上求解得到一种新的分配方案 Ci,j，求得总偏爱度 U 为 8191(>7924)，但是经分析，只分配了 8 张 DVD 给没有要求预订这些 DVD 的会员。 事实上这里的 8 张 DVD 已经最小，具体原因是，现有 DVD 总数为 3007 张，每个人得 到 3 张 DVD，1000 个人就得到 3000 张 DVD，则还有 7 张未出租。根据所给的数据， 第 37 种 DVD 现有 106 张，只有 91 个会员愿意租此 DVD，即第 37 张 DVD 按照会员的 需求无论怎么发放，也会有 106-91=15 张剩余，而总共应该只有 7 张 DVD 未出租，这 样就无法满足所有的会员租到自己想看的 DVD，而且一定至少有 15-7=8 张 DVD 发给 了没有订这 8 张 DVD 的会员。 比较上面两种分配方案，我们选择第二种分配方案。第二种方案下，前 30 会员的 租赁情况是只有第 25 个会员的第 3 张 DVD 与第一种分配方案不同，其值为 81（4） 4.4 问题三模型的建立与求解 0，1 变量 每位会员租 3 张 DVD DVD 现有数量的限制
2005年全国大学生数学建模国家二等奖获奖论文 44.1问题三的分析及模型的建立 分析该问题的目标是保证一个月内95%的会员得到他想看的DVD的情况下,使得 会员的满意程度达到最大。 假设分配给第i个会员3张DVD,且这3张DVD都属于该会员预定的DVD那么 记p1为1,否则记p为0。 (注:囗为向下取整) 要使一个月内95%的会员看到他预订的DⅴD,则得到∑P=095×100 根据问题二以及这里分可以建立以下模型: min C C=0 每位会员租3张DVD 1∑C≤y,DVD数量的限制 0.95*1000 44.2问题三的求解 上述模型难以用计算机实现,这里我们用计算机仿真来解决该问题。仿真前先进行 如下假设 交n假设40%的会员一个月只租DVD一次,60%的会员一个月租DVD两次,会员 VD天数在3~30天内并服从等概率分布。 b假设每位顾客都有95%的概率租到自己想看的DVD,若一位顾客按偏爱度 (n<10)种自己想看的DVD,设该顾客租到偏爱度为k(k<n)的DVD的概率为 P(k)=11-k c,假设已经租到DVD的会员只有归还DⅤD后才能再租, 在此假设基础上进行模拟一个月内DVD的供求,得到这一个月中每种DD的需 求的最大量。仿真流程图见图1,程序见附录。 用 MATLAB编程凹,经过多次模拟,得到每种DVD的购买总量在3085左右, 其中一次结果得到各种DⅤD购买量依次为(见表5): 表5 D00l-D010 28332926243031352827 DO11-D020 25243539233437292735 D021-D030 33314228323227233535 D03l-D040 35292228383230333029
2005 年全国大学生数学建模国家二等奖获奖论文 6 4.4.1 问题三的分析及模型的建立 分析该问题的目标是保证一个月内 95%的会员得到他想看的 DVD 的情况下，使得 会员的满意程度达到最大。 假设分配给第 i 个会员 3 张 DVD，且这 3 张 DVD 都属于该会员预定的 DVD 那么 记 pi 为 1，否则记 pi 为 0。 ú ú û ù ê ê ë é ÷ ÷ ø ö ç ç è æ = å= 3 100 j 1 pi Cij （注： []为向下取整） 要使一个月内 95%的会员看到他预订的 DVD，则得到 0.95 1000 1000 1 å = ´ i = pi 根据问题二以及这里分可以建立以下模型： ï ï ï ï ï ï î ï ï ï ï ï ï í ì = = = ú ú û ù ê ê ë é ÷ ÷ ø ö ç ç è æ £ = = ´ å å å å åå = = = = = = ( 1 1000 , 1 100 ) 3 0.95 *1000 3 0,1 . min 1000 1 100 1 1000 1 100 1 1000 1 100 1 i L j L C C y C C s t D C i j ij i ij j j ij ij i j ij ij 4.4.2 问题三的求解 上述模型难以用计算机实现，这里我们用计算机仿真来解决该问题。仿真前先进行 如下假设： a,假设 40%的会员一个月只租 DVD 一次， 60%的会员一个月租 DVD 两次，会员 还 DVD 天数在 3～30 天内并服从等概率分布。 b,假设每位顾客都有 95%的概率租到自己想看的 DVD，若一位顾客按偏爱度订 n （n<10）种自己想看的 DVD，设该顾客租到偏爱度为 k（k<n）的 DVD 的概率为 å= - - = n i i k p k 1 11 11 ( ) ， c,假设已经租到 DVD 的会员只有归还 DVD 后才能再租， 在此假设基础上进行模拟一个月内 DVD 的供求，得到这一个月中每种 DVD 的需 求的最大量。仿真流程图见图 1，程序见附录。 用 MATLAB 编程[1] [2]，经过多次模拟，得到每种 DVD 的购买总量在 3085 左右， 其中一次结果得到各种 DVD 购买量依次为（见表 5）： 表 5 D001—D010 28 33 29 26 24 30 31 35 28 27 D011—D020 25 24 35 39 23 34 37 29 27 35 D021—D030 33 31 42 28 32 32 27 23 35 35 D031—D040 35 29 22 28 38 32 30 33 30 29 0，1 变量 每位会员租 3 张 DVD DVD 数量的限制
2005年全国大学生数学建模国家二等奖获奖论文 D04l-D050 34392325383235352730 D051-D060 31313821303235313638 D06l-D070 25332333344334404236 DO71-D080 35363030332921312333 D08l-D090 34202126332031203832 D09l—D100 43253031292629302634 和 将1000个人分类=0 D(1.100)=1000, 1第i天 计算30天中D i<30? 的减少最大 J=+1 第j个会员 结束 会员j是否还 Y 还回DⅤDdl,d2,d3, D(dl,d2,d3)加1 会员j是否租 租到 DVDdld2d3, D(dl,d2d3)减1 7
2005 年全国大学生数学建模国家二等奖获奖论文 7 D041—D050 34 39 23 25 38 32 35 35 27 30 D051—D060 31 31 38 21 30 32 35 31 36 38 D061—D070 25 33 23 33 34 43 34 40 42 36 D071—D080 35 36 30 30 33 29 21 31 23 33 D081—D090 34 20 21 26 33 20 31 20 38 32 D091—D100 43 25 30 31 29 26 29 30 26 34 总和 3086 Y N Y N N Y Y Y i<30？ i=i+1 第 i 天 j=j+1， 第 j 个会员 j<n？ 会 员 j 是否还 租到 DVDd1,d2,d3， D(d1,d2,d3)减 1 计算 30 天中 Di 的减少最大 结束 N 将 1000 个人分类 i=0, D(1..100)=1000, j=0,n=1000 还回 DVDd1,d2,d3， D(d1,d2,d3)加 1 会 员 j 是否租
2005年全国大学生数学建模国家二等奖获奖论文 图1 45问题四的分析 我们分析了DVD租赁的实际情况,发现以下问题: 45.1已知连续前N个月的DvD需求情况,如何预测出第N+1个月的DD需求 情况? 假设前5个月的DVD总数的需求情况为x1x2x32x4x5 对与上述问题,我们建立灰色GM(1,1)模型求解3 以第一个月为起始点,即在该点t=1,于是有原始数据序列: X0={X()t=1,2 x0(1),x0(2),…X0(5)} {x1,x2,x3,x4,xs} 首先按GM(1,1)建模方法,对已知原始数据序列X进行一阶累加生成 X(m)=∑X(m) (即1-AG0) 。得到生成数列X(1),如下 X ={x1(1),x1(2,…X(5)} (xl, x1+x2, xr+x2+x3, xI+x+x3+x4, x1+x2+x3+xr+xs) 构造数据矩阵B及数据向量Y 1/2(X(1)+X(2) B= l/2(X(2)+X(3) l/2(x°(n-1)+X(n)1 Y=[X0(2),X(3),…X0(n) 求模型参数α a=(a, b)=(B'B)B'Y 建立模型:根据参数α建立模型。模型的时间响应方程为: b x(+1)=(x(1)--)e b 模型的改进 为了提高模型精度,又对参数进行估计,以进一步改进模型。将以上时间响应方程 写成 (+1)=Ae+B 根据第一次估计的α值及原始1-AGO数列X)(k)对A和B进行估计。构造数据 矩阵G及数据向量X() 8
2005 年全国大学生数学建模国家二等奖获奖论文 8 图 1 4.5 问题四的分析 我们分析了 DVD 租赁的实际情况，发现以下问题： 4.5.1 已知连续前 N 个月的 DVD 需求情况，如何预测出第 N+1 个月的 DVD 需求 情况？ 假设前 5 个月的 DVD 总数的需求情况为 x1,x2,x3,x4,x5 对与上述问题，我们建立灰色 GM（1，1）模型求解[3]。 以第一个月为起始点，即在该点 t=1，于是有原始数据序列： X （0） ={ X （0） (t) t=1,2, …5} ={ X（0） (1), X（0） (2), … X（0） (5)} ={x1，x2，x3，x4，x5} 首先按 GM（1，1）建模方法，对已知原始数据序列 X （0）进行一阶累加生成 （即 1—AG0）： å= = t m X t X m 1 (1) (0 ) ( ) ( ) 。得到生成数列 X （1），如下： X （0） ={ X （1） (t) t=1,2, …5} ={ X（1） (1), X（1） (2), … X（0） (5)} ={ x1, x1+ x2，x1+ x2+ x3，x1+ x2+ x3+ x4，x1+ x2+ x3+ x4+x5} 构造数据矩阵 B 及数据向量 YN ú ú ú ú ú û ù ê ê ê ê ê ë é - - + - + - + = 1/ 2( ( 1) ( )) 1 1/ 2( (2) (3)) 1 1/ 2( (1) (2)) 1 (1) (1) (1) (1) (1) (1) X n X n X X X X B M M YN=[ X（0） (2), X（0） (3), … X（0） ( n)]T 求模型参数a ： N T T T a b B B B Y 1 ( , ) ( ) - a = = ) 建立模型：根据参数a 建立模型。模型的时间响应方程为： a b e a b X t X at + = - + - ( 1) ( (1) ) (1) (0) ) 模型的改进： 为了提高模型精度，又对参数进行估计，以进一步改进模型。将以上时间响应方程 写成： X t Ae B at ( +1) = + (1) 根据第一次估计的a 值及原始 1—AGO 数列 X （0）（ k）对 A 和 B 进行估计。构造数据 矩阵 G 及数据向量 X （1）：
2005年全国大学生数学建模国家二等奖获奖论文 G a(n-1 )=[X(1),X(2),…x(n) 求出参数A和B (GG)GX (1) 求出时间相应方程:X(+1)=Aem+B 则需求总量的预测模型为:X(+1)=x(t+1)-x() 452网站月盈利与网站DVD购买,会员会费的关系 网站盈利与网站会员数、会费、会员的满意度和DVD总量存在一定联系,如何购 买DVD,如何确定会费使得网站盈利最大 假设网站会员人数W与网站会费e,会员对网站的满意程度m有关,设: w=f(e, m) 假设会员对网站的满意程度m与网站拥有DVD总数量s,网站拥有DVD种数 有关,设: m=8(S,n) 假设拥有第i种DVD的数量为a,第i中DVD购买价格为b 假设网站的每月的盈利F只于购买DVD的费用与会员的会费有关 根据以上假设建立如下规划模型 maxF=W×e-a,xb w=f(e, m) s.m=g(s,n) 六、模型的评价及推广 在问题一中,我们的根据实际的情况,突破传统以会员为参考切题巧妙地转为以经 营者的身份用周转情况来考虑问题本身,使解题思路突现,运算简单,而且模型非常明 了,十分容易理解。问题二中我们证明了在题设条件下每位会员不可能都租到自己想看 的3张DVD,至少有8张DⅤD租给了不愿意租到该DVD的会员,同时用0-1规划模 型求得了在只有有8张DVD租给了不愿意租到该DVD的会员情况下最优的分配方案
2005 年全国大学生数学建模国家二等奖获奖论文 9 ú ú ú ú ú û ù ê ê ê ê ê ë é = - - - 1 1 1 ( 1) 0 n e e e G a a M M Y （1）=[ X（1） (1), X（1） (2), … X（1） ( n)]T 求出参数 A 和 B 1 (1) (G G) G X B A T - T =÷ ÷ ø ö ç ç è æ 求出时间相应方程： X t Ae B at ( +1) = + (1) 则需求总量的预测模型为： ( 1) ( 1) ( ) (0) (1) (1) X t X t X t ) ) ) + = + - 4.5.2 网站月盈利与网站 DVD 购买，会员会费的关系 网站盈利与网站会员数、会费、会员的满意度和 DVD 总量存在一定联系，如何购 买 DVD，如何确定会费使得网站盈利最大 假设网站会员人数 W 与网站会费 e，会员对网站的满意程度 m 有关，设： W = f (e,m)； 假设会员对网站的满意程度 m 与网站拥有 DVD 总数量 s，网站拥有 DVD 种数 n 有关，设： m = g(s, n) 假设拥有第 i 种 DVD 的数量为 ai，第 i 中 DVD 购买价格为 bi 假设网站的每月的盈利 F 只于购买 DVD 的费用与会员的会费有关 根据以上假设建立如下规划模型： ï ï ï î ï ï ï í ì = = = = ´ - ´ å å = = n i i n i i i s a m g s n W f e m st F W e a b 1 1 ( , ) ( , ) . . max 六、模型的评价及推广 在问题一中，我们的根据实际的情况，突破传统以会员为参考切题巧妙地转为以经 营者的身份用周转情况来考虑问题本身，使解题思路突现，运算简单，而且模型非常明 了，十分容易理解。问题二中,我们证明了在题设条件下每位会员不可能都租到自己想看 的 3 张 DVD，至少有 8 张 DVD 租给了不愿意租到该 DVD 的会员，同时用 0-1 规划模 型求得了在只有有 8 张 DVD 租给了不愿意租到该 DVD 的会员情况下最优的分配方案
2005年全国大学生数学建模国家二等奖获奖论文 此模型中有10万个0-1变量,规模已经相当大,但是运算只有20多秒,在10万个变 量以内规模的问题都可以求解。对于更大规模问题,模型的求解就会困难。因此我们想 了另外的一个算法:贪心算法。贪心算法是在让计算机按照当前的要求逐一进行分配。 在满足一定约束条件下,每次搜索偏爱度最小,然后按此进行分配的原则,得出较优解 对于问题三,我们建立了一个规划模型,满足题目要求并且容易理解,但模型求解较为 困难,然后用计算机仿真的方法模拟一个月内会员租DVD情况,得到网站应该购买DVD 的数量。次方法比较贴近现实,但是每次模拟的结果都会有一定的差别,而且所得到的 结果难以求得最优解。 本文建立的模型,不仅能够解决本文的问题。在超市物品的需求预测,货物的购买 和各个连锁网点的货物分配,都能运用本文的模型进行解决,本文的模型,能很好符合 实际情况,但在精确性上还有待改进。 [参考文献] [张平等, MATLAB基础与应用,北京:北京航空航天大学出版社,2001年 [2]苏金明,张莲花等, MATLAB工具箱应用,北京:电子工业出版社,2004年 [3]蔡家明,灰色系统模型在汽车市场需求预测中的应用,上海工程技术大学学报, 第17卷第1期:72至74页,2003年3月 [4]余祥宣,崔国华等,计算机算法基础,湖北:华中科技大学出版社,2004年 [5]htt/www.netflix.com,2005年9月17日 附录] 1、问题二程序 运行软件: Lingo80 运行环境: windows2,000 运行时间:24秒 sets cd/1.100/:dvd ink(ren, cd): c, b endsets min=@sum(link: c*b); dvd总数的约束; @for(cd(J): @sum(ren (D): b(l,J))<dvd)): 需求约束 @for(ren(I): @sum(cd(): b(ID))=3); @for(link @bin(b); ;输入偏爱度; ;!输入现有的每张DVD张数 nddate
2005 年全国大学生数学建模国家二等奖获奖论文 10 此模型中有 10 万个 0-1 变量，规模已经相当大，但是运算只有 20 多秒，在 10 万个变 量以内规模的问题都可以求解。对于更大规模问题，模型的求解就会困难。因此我们想 了另外的一个算法：贪心算法[4]。贪心算法是在让计算机按照当前的要求逐一进行分配。 在满足一定约束条件下，每次搜索偏爱度最小，然后按此进行分配的原则，得出较优解。 对于问题三，我们建立了一个规划模型，满足题目要求并且容易理解，但模型求解较为 困难，然后用计算机仿真的方法模拟一个月内会员租DVD情况，得到网站应该购买 DVD 的数量。次方法比较贴近现实，但是每次模拟的结果都会有一定的差别，而且所得到的 结果难以求得最优解。 本文建立的模型，不仅能够解决本文的问题。在超市物品的需求预测，货物的购买 和各个连锁网点的货物分配，都能运用本文的模型进行解决，本文的模型，能很好符合 实际情况，但在精确性上还有待改进。 [参考文献]： [1] 张 平 等，MATLAB 基础与应用，北京：北京航空航天大学出版社，2001 年 [2] 苏金明，张莲花 等，MATLAB 工具箱应用，北京：电子工业出版社，2004 年 [3] 蔡家明，灰色系统模型在汽车市场需求预测中的应用，上海工程技术大学学报， 第17卷第1期：72至74页，2003年3月 [4] 余祥宣，崔国华 等，计算机算法基础，湖北：华中科技大学出版社，2004年 [5] http://www.netflix.com，2005 年 9 月 17 日 [附录]： 1、问题二程序： 运行软件：Lingo 8.0 运行环境：windows2000 运行时间：24 秒 model: sets: cd/1..100/:dvd; ren/1..1000/:people; link(ren,cd):c,b; endsets min=@sum(link:c*b); !dvd总数的约束; @for(cd(J):@sum(ren(I):b(I,J))<dvd(J)); !需求约束; @for(ren(I):@sum(cd(J):b(I,J))=3); @for(link:@bin(b)); data: c= ;!输入偏爱度; dvd= ;！输入现有的每张DVD张数; enddate end