山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 DVD在线租赁方案 摘要 本论文通过对DⅦD租赁问题的抽象简化,建立了一个明确的、完整的数学模型,分 别用线性规划模型与递归算法对υD分配进行优化,设计出一个使得会员满意度较高的 分配方案。 针对问题一,我们利用正态分布等概率论知识建立了一个较为完整而又简单的数学 模型 1.6d1≥Q, 在问题四中,关于问题一我们利用货币流通模型和信息源的最大熵原理,建立起关 于需求量的另一种模型: 针对问题二,考虑到当天会员的偏爱度加和可以用来衡量满意度,我们提出了在两 种不同网站运行模式下的分配方案,方案一运用线性规划很好的解决了分配问题,使得 满意度最大。方案二运用递归算法较好的解决了此问题,并且跟方案一结果相当吻合 针对问题三,我们利用问题一和问题二建立的数学模型组合起来解决了当前DVD的 购买和分发问题,并阐述了动态规划的方法。 针对问题四,我们从DVD需求预测角度出发,利用本模型特点合理的引入了传染病 模型,有效的解决了该预测问题。 最后,我们对模型的科学性和现实性进行了阐述,并得到了对模型的整体评价,及急 需改进之处 关键字:正态分布线性规划递归算法货币流通最大熵原理SIS模型 SIR模型 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 1 DVD 在线租赁方案 摘要 本论文通过对 DVD 租赁问题的抽象简化，建立了一个明确的、完整的数学模型，分 别用线性规划模型与递归算法对 DVD 分配进行优化，设计出一个使得会员满意度较高的 分配方案。 针对问题一,我们利用正态分布等概率论知识建立了一个较为完整而又简单的数学 模型 1.6 j j j d Q≥ ×ω 在问题四中，关于问题一我们利用货币流通模型和信息源的最大熵原理，建立起关 于需求量的另一种模型： j j j m d n ω = 针对问题二, 考虑到当天会员的偏爱度加和可以用来衡量满意度，我们提出了在两 种不同网站运行模式下的分配方案，方案一运用线性规划很好的解决了分配问题，使得 满意度最大。方案二运用递归算法较好的解决了此问题，并且跟方案一结果相当吻合。 针对问题三,我们利用问题一和问题二建立的数学模型组合起来解决了当前 DVD 的 购买和分发问题，并阐述了动态规划的方法。 针对问题四,我们从 DVD 需求预测角度出发，利用本模型特点合理的引入了传染病 模型，有效的解决了该预测问题。 最后,我们对模型的科学性和现实性进行了阐述,并得到了对模型的整体评价,及急 需改进之处. 关键字: 正态分布 线性规划 递归算法 货币流通 最大熵原理 SIS 模型 SIR 模型
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 问题重述 随着信息时代的到来,网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度,面向其会员群提供日益专业化和便捷化的服务。DVD的在 线租赁就是一种可行的服务。顾客缴纳一定数量的月费成为会员,订购DVD租赁服务。 会员对哪些DVD有兴趣,只要在线提交订单,网站就会通过快递的方式尽可能满足要求 会员提交的订单包括多张DⅦD,这些DⅦD是基于其偏爱程度排序的。网站会根据手头现 有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次,每次获 得3张DD。会员看完3张DVD之后,只需要将DⅦD放进网站提供的信封里寄回(邮费 由网站承担),就可以继续下次租赁 1)网站正准备购买一些新的DVD,通过问卷调查1000个会员,得到了愿意观看这些DWD 的人数(表1给出了其中5种DVD的数据)。此外,历史数据显示,60%的会员每月 租赁DWD两次,而另外的40%只租一次。假设网站现有10万个会员,对表1中的每 种DVD来说,应该至少准备多少张,才能保证希望看到该DVD的会员中至少50%在 个月内能够看到该DVD?如果要求保证在三个月内至少95%的会员能够看到该DVD 呢? 2)表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线 订单,如何对这些DD进行分配,才能使会员获得最大的满意度?请具体列出前30 位会员(即C0001C0030)分别获得哪些DVD 3)继续考虑表2,并假设表2中DVD的现有数量全部为0。如何决定每种DVD的购买量 以及如何对这些DVD进行分配,才能使一个月内95%的会员得到他想看的DⅦD,并且 满意度最大? 4)在DⅦD的需求预测、购买和分配中还有哪些重要问题值得硏究?明确提出问题, 尝试建立相应的数学模型。 表1对1000个会员调查的部分结果 DVD名称 DVDIDVD2DVD3DVD4 DVD5 愿意观看的人200 10 数 表2现有DVD张数和当前需要处理的会员的在线订单(表格格式示例) DVD编号0001 D002 D003 D004 DVD现有数量10 40 0 会员c002 在线c003 0 订单C004 6000 0000 0030 0 注:D001D100表示100种DVD,C0001C1000表示1000个会员,会员的在线订单用数 字1,2,…表示,数字越小表示会员的偏爱程度越高,数字0表示对应的DVD当前不在会 员的在线订单中。 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 2 问题重述 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站 利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。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 中列出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会员的在线 订单,如何对这些 DVD 进行分配，才能使会员获得最大的满意度？请具体列出前 30 位会员（即 C0001~C0030）分别获得哪些 DVD。 3）继续考虑表 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 D003 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 … 会员 在线 订单 … … … … … … 注：D001~D100 表示 100 种 DVD, C0001~C1000 表示 1000 个会员, 会员的在线订单用数 字 1,2,…表示，数字越小表示会员的偏爱程度越高，数字 0 表示对应的 DVD 当前不在会 员的在线订单中
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 问题分析 1)对网站运行模式的理解 模式一:网站的会员可随时提交订单,每天网站将订单信息及现有DⅦD信息汇总, 然后进行DWD分配,不在会员订单中的DVD也有可能分配给会员.不会将任何客户订单推 迟到第二天处理,即不存在会员等待时间 模式二:网站的会员可随时提交订单,每天网站按当天顾客提交订单的时间先后对 其排序,并将其订单信息及现有DVD信息汇总,然后进行DⅦD分配,使排在前面的会员 尽量被满足。公司只能向会员提供其订单中的DVD,即会员不喜欢的DVD公司不能给会员 (这是模式二与模式一的根本区别).当天没有被满足的会员及没有被分派的DVD汇入第 天,并在第二天排序时将这些会员排在最前面。 2)对DVD需求问题的分析 由于各种因素的随机性,DⅦD的流通问题是很复杂的,我们考虑需求最大情况,即 DVD需求上限,以及DVD月流通次数最少 3)对满意度的理解 我们认为满意度受会员等待时间和偏爱度影响,等待时间为从提交订单到订单中 DⅦD被邮寄的时间间隔。对于方案一无等待时间,会员的满意度被会员的偏爱度唯一确定. 对于方案二,等待时间的影响很小,所以我们也以当天被满足的会员的偏爱度加和来衡 量满意度。 问题假设 1)对于调査问卷中1000人和所有会员对DwD的选择情况是同分布的,也就是说这1000 人对DⅦD的选择情况代表了所有会员的选择倾向。 2)对于所有的会员提交订单的时间是随机的 3)无论租赁一次或两次,会员必须在30天之内归还所借的DVD. 4)一个月内借两次的会员这两次借的DVD种类不会重复 5)公司收到订单时不知道此会员在一个月内会借一次或两次 模型分析与求解 问题(1): 变量假设: m:网站现有会员人数 P:第j种DⅦD被选中的概率 7:第j种DD没被选中的概率 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 3 问题分析 1） 对网站运行模式的理解 模式一: 网站的会员可随时提交订单，每天网站将订单信息及现有 DVD 信息汇总， 然后进行 DVD 分配,不在会员订单中的 DVD 也有可能分配给会员.不会将任何客户订单推 迟到第二天处理,即不存在会员等待时间. 模式二: 网站的会员可随时提交订单，每天网站按当天顾客提交订单的时间先后对 其排序，并将其订单信息及现有 DVD 信息汇总，然后进行 DVD 分配，使排在前面的会员 尽量被满足。公司只能向会员提供其订单中的 DVD,即会员不喜欢的 DVD 公司不能给会员 (这是模式二与模式一的根本区别).当天没有被满足的会员及没有被分派的 DVD 汇入第 二天，并在第二天排序时将这些会员排在最前面。 2） 对 DVD 需求问题的分析 由于各种因素的随机性，DVD 的流通问题是很复杂的，我们考虑需求最大情况,即 DVD 需求上限,以及 DVD 月流通次数最少. 3） 对满意度的理解 我们认为满意度受会员等待时间和偏爱度影响，等待时间为从提交订单到订单中 DVD 被邮寄的时间间隔。对于方案一无等待时间,会员的满意度被会员的偏爱度唯一确定. 对于方案二，等待时间的影响很小，所以我们也以当天被满足的会员的偏爱度加和来衡 量满意度。 问题假设 1) 对于调查问卷中1000人和所有会员对DVD的选择情况是同分布的,也就是说这1000 人对 DVD 的选择情况代表了所有会员的选择倾向。 2) 对于所有的会员提交订单的时间是随机的. 3) 无论租赁一次或两次,会员必须在 30 天之内归还所借的 DVD. 4) 一个月内借两次的会员这两次借的 DVD 种类不会重复. 5) 公司收到订单时不知道此会员在一个月内会借一次或两次. 模型分析与求解 问题 (1): 变量假设: m : 网站现有会员人数. j p ：第 j 种 DVD 被选中的概率 : j q 第 j 种 DVD 没被选中的概率
东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 a:每月租赁DVD一次的会员的比例 B:每月租赁DVD两次的会员的比例 d:第j种DWD应准备的数量 :一个月内对第j种DD有需求的会员得到满足的比例 n:DVD每月可用次数的数学期望 Q1:某月内对第j种DVD需求的人数上限 考虑到会员租碟的实际情况,表1中给出的选择某种DD的人数可以认为是某月选 择该DⅦD人数的数学期望,每月实际选择该DVD的人数会在其周围波动,我们认为对第 种碟片的总需求可以用正态分布N(mp,mq)近似(此处m=100000以算出第j种 DVD的需求人数上限Q(在一定置信区间下,这里我们选取0.95),只要在租借过程中满 足上限Q,的一定人数比例a(50%)即可,假设第j种DD购买d张 我们考虑需要DVD最多的情况:借一次的会员在一个月的最后一天归还,借两次的 会员在一个月的最后一天第二次归还,那么对于一张碟来说借一次的会员使得它流通了 一次,而借两次的会员使得它流通了两次,这相当于该DVD的每月可用次数n为 a×1×d1+B×2×d1,对于本题目来说,a=0.4,B=0.6,即1.6d1,要求一个月至少 50%有需求的会员能得到满足,即 1.6d;≥Q2×O 求出d1的最小值 用 Matlab求得置信度为0.95下的上限值分别为 Q1=20209 Q2=10157 Q3=5114 Q4=2582 Q5=1052 带入公式(1)解得: d,=6316 d2=3174 d3=1598 d,=807 d5=329 对于三个月的情况,想当于一个月情况的三次累积,三个月的DVD流通次数是一个月的3 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 4 α ：每月租赁 DVD 一次的会员的比例 β ：每月租赁 DVD 两次的会员的比例 j d ：第 j 种 DVD 应准备的数量 ω j ：一个月内对第 j 种 DVD 有需求的会员得到满足的比例. n : DVD 每月可用次数的数学期望 Qj :某月内对第 j 种 DVD 需求的人数上限. 考虑到会员租碟的实际情况，表 1 中给出的选择某种 DVD 的人数可以认为是某月选 择该 DVD 人数的数学期望,每月实际选择该 DVD 的人数会在其周围波动,我们认为对第 j 种碟片的总需求可以用正态分布 ( , ) N mp mp q j j j 近似(此处m =100000),可以算出第 j 种 DVD 的需求人数上限Qj (在一定置信区间下,这里我们选取 0.95)，只要在租借过程中满 足上限Qj 的一定人数比例ω j (50%)即可,假设第 j 种 DVD 购买 j d 张。 我们考虑需要 DVD 最多的情况：借一次的会员在一个月的最后一天归还，借两次的 会员在一个月的最后一天第二次归还，那么对于一张碟来说借一次的会员使得它流通了 一次,而借两次的会员使得它流通了两次,这相当于该 DVD 的每月可用次数 n 为 α × 1× j d + β × 2 × j d ,对于本题目来说, α =0.4, β =0.6,即 1.6 j d ,要求一个月至少 50%有需求的会员能得到满足,即 1.6 j j j d Q≥ ×ω (1) 求出 j d 的最小值. 用 Matlab 求得置信度为 0.95 下的上限值分别为: 1 2 3 4 5 20209 10157 5114 2582 1052 Q Q Q Q Q = = = = = 带入公式(1)解得: 1 2 3 4 5 6316 3174 1598 807 329 d d d d d = = = = = 对于三个月的情况,想当于一个月情况的三次累积,三个月的 DVD 流通次数是一个月的 3
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 倍,上限Q,值不便,所得公式为 4.8d1≥Q;×0.95 带入数据计算得 d1=4000 d3=1013 d4=512 d4=209 问题 模式一规划模型 对于问题中的分配问题,我们可以建立一个0-1分配矩阵q,q=1表示将j号DD 分配给i号会员,91=0表示不分配而根据模型分析中对满意度的理解满意度由会员 的偏爱度加和来衡量.显然该分配问题可以转化成为使得已分配的会员的偏爱度之和最 小的规划问题.由于附件表格中的0项表示用户对该DVD无任何偏爱度,而题目里有表格 中数据越小,偏爱程度越大,显然所有的0项将把我们规划模型导向错误的方向,为了方 便模型的建立,我们对附录表进行了一定的技术处理一将所有的0项改成11. 变量假设: x:编号为的会员对第号DWD偏爱度 y;:编号为jDV的当天库存 根据上述分析,考虑到会员一次有且仅得到3张DVD,DVD有数量限制的约束条件, 我们可以建立如下的线性规划模型. min qixi qn=0,1(=1,2….1000,j=1,2…100) ∑9≤y(j=12.10 ∑q1=3(=12.1000 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 5 倍, 上限Qj 值不便,所得公式为: 4.8 0.95 j j d Q≥ × (2) 带入数据计算得: 1 2 3 4 5 4000 2011 1013 512 209 d d d d d = = = = = 问题 (2): 模式一规划模型 对于问题中的分配问题,我们可以建立一个 0-1 分配矩阵 ij q ， ij q =1 表示将 j 号 DVD 分配给 i 号会员, ij q =0 表示不分配.而根据模型分析中对满意度的理解,满意度由会员 的偏爱度加和来衡量.显然该分配问题可以转化成为使得已分配的会员的偏爱度之和最 小的规划问题.由于附件表格中的 0 项表示用户对该 DVD 无任何偏爱度,而题目里有表格 中数据越小,偏爱程度越大,显然所有的 0 项将把我们规划模型导向错误的方向,为了方 便模型的建立,我们对附录表进行了一定的技术处理—将所有的 0 项改成 11. 变量假设： : : ij j x i j DVD DVD 编号为 的会员对第 号 的偏爱度 y 编号为j的 的当天库存 根据上述分析,考虑到会员一次有且仅得到 3 张 DVD,DVD 有数量限制的约束条件, 我们可以建立如下的线性规划模型. 1000 100 1 1 1000 1 100 1 min 0,1 ( 1, 2...1000, 1,2...100) . . ( 1, 2...100) 3 ( 1,2...1000) ij ij i j ij ij j i ij j q x q i j s t q y j q i = = = = × = = = ≤ = = = ∑∑ ∑ ∑