山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 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 = = = = × = = = ≤ = = = ∑∑ ∑ ∑
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 用 Lingo求解得偏爱度之和最小为8254。 对于30位会员(C0001C0030)获得的DWD情况如下表所示 会员编号 DVD编号 C000l DVD8 DVD41 DVD9 8 C0002 DVD DVD44 DVD62 C0003 DVD32 DVD50 DVD8O C0004 DVD DVDI8 DVD41 DVD66 DVD68 DVDIl C0006 DVD19 DVD53 DVD66 C0007 DVD26 DVD66 DVD8I C0008 DVD31 DVD35 DVD71 C0009 DVD53 DVD78 DVD100 C0010 DVD41 I DVD55 IDVD85 DVD59 DVD63 DVD66 C0012 DVD31 DVD2 DVD41 C0013 DVD21 DVD78 DVD96 C0014 DVD52 DVD23 DVD89 C0015 DVD13 DVD52 C0016 DVD84 DVD97 DVDIO C0017 DVD67 DVD47 DVD51 C0018 DVD41 DVD60 DVD78 C0019 DVD84 DVD66 C0020 DVD45 D89 DVD61 C0021 DVD53 DVD45 DVD50 C0022 DVD57 DVD55 DVD38 C0023 DVD95 DVD29 DVD8l C0024 DVD76 DVD37 C0025 DVD9 DVD69 D94 C0026 DVD22 DVD68 DVD95 C0027 DVD58 DVD78 DVD50 C0028 D8 DVD34 DVD37 C0029 DVD30 DVD26 C0030 IDVD62 DVD37 D98 对该模型的评价 显然,该模型尽可能的使得所有分配会员偏爱度数值之和最小,根据我们对满 意度的理解,该模型得到的解肯定是满足满意度最大的最优解。 模式二递归算法 由于模式一下的规划模型使得不在会员订单中的DVD也有可能分配给会员,而模式 严格规定公司只能向会员提供其订单中的DⅦD,而这个限制条件用规划模型是无法实 2005年全国大学生数学建模竞赛全国一等奖 6
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 6 用 Lingo 求解得 偏爱度之和最小为 8254。 对于 30 位会员（C0001~C0030）获得的 DVD 情况如下表所示: 会员编号 DVD 编号 C0001 DVD8 DVD41 DVD98 C0002 DVD6 DVD44 DVD62 C0003 DVD32 DVD50 DVD80 C0004 DVD7 DVD18 DVD41 C0005 DVD66 DVD68 DVD11 C0006 DVD19 DVD53 DVD66 C0007 DVD26 DVD66 DVD81 C0008 DVD31 DVD35 DVD71 C0009 DVD53 DVD78 DVD100 C0010 DVD41 DVD55 DVD85 C0011 DVD59 DVD63 DVD66 C0012 DVD31 DVD2 DVD41 C0013 DVD21 DVD78 DVD96 C0014 DVD52 DVD23 DVD89 C0015 DVD13 DVD85 DVD52 C0016 DVD84 DVD97 DVD10 C0017 DVD67 DVD47 DVD51 C0018 DVD41 DVD60 DVD78 C0019 DVD84 DVD86 DVD66 C0020 DVD45 DVD89 DVD61 C0021 DVD53 DVD45 DVD50 C0022 DVD57 DVD55 DVD38 C0023 DVD95 DVD29 DVD81 C0024 DVD76 DVD41 DVD37 C0025 DVD9 DVD69 DVD94 C0026 DVD22 DVD68 DVD95 C0027 DVD58 DVD78 DVD50 C0028 DVD8 DVD34 DVD37 C0029 DVD55 DVD30 DVD26 C0030 DVD62 DVD37 DVD98 对该模型的评价 显然,该模型尽可能的使得所有分配会员偏爱度数值之和最小, 根据我们对满 意度的理解,该模型得到的解肯定是满足满意度最大的最优解。 模式二递归算法 由于模式一下的规划模型使得不在会员订单中的 DVD 也有可能分配给会员,而模式 二严格规定公司只能向会员提供其订单中的 DVD,而这个限制条件用规划模型是无法实
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 现的,所以我们考虑用算法实现 根据我们对满意度的理解及该模式下的网站的经营方案,如果要使得会员的满意度 达到最大,应该尽量满足会员订单之中偏爱度较小的碟片请求.根据我们的假设,会员提 交订单的时间是随机的,当网站在处理会员的订单请求时,必然存在一个处理次序问题, 我们假设处理次序仅与用户发出订单的次序有关 假设当前的订单已经按会员的请求顺序排列出来,会员被编号为1-1000,为了使得 总体的满意度最大,我们所要做的是尽量满足会员订单中偏爱度较小的请求,同时尽量 满足编号靠前的会员的请求.根据以上分析我们引入下面的算法解决分配方案 1),提取表2中的数据,经过一定的加工处理生成需求矩阵Met;,偏爱矩阵 Usermetr.矩阵Metr;反映了会员i对DVDj的偏爱程度,0表示会员对该DVD无需 求,1,2…n分别表示会员对DⅦ的偏爱程度,数值越小偏爱程度越高矩阵 Usermetr反 映了会员m偏爱度为n的对应的DVD编号 2),根据用户的偏爱度从低到高进行排序,偏爱度相同的按照会员编号进行排序, 构成序列A,B,其中A记录了序列第i项对应的会员编号,B记录了序列第i项对应 会员满足一定偏爱的DⅦD编号. 3),构建DD库存序列Sore,(i=1,2100,表示DVD当前的库存数构建会员定购 盘数序列 Check,表示会员j当前还需满足的DV盘数,显然分配前有 Cont1=3,(j=1,2…1000 4),构建与A序列等长的序列 Check,然后对A,B中的数据逐个检索,假设A中第 i项中会员的编号为k,B中第i项中DVD编号为l.如果Coun(k)>0并且Sore(l)>0,则 说明会员k希望得到l号DⅦD,已分配给会员k的光碟数不足三张,而l号DVD有库存,所以 可以把l号DVD分配给会员k, 7 Check(i=l, Count(k)=Count(k)-1, Store(0)=Store(0)-1 否则,如果Coun(k)=0,说明当前的会员k已经分配的三张光碟,如果Sore()=0, 说明会员k希望分配的l号DⅦD已经分完,显然这两种情况都不满足分配条件,故令 Check(i)=0.显然 Check中0,1分布反映了DVD的分配情况 5),统计 Check中的所有的1对应的会员编号及对应的DD编号,由于分配时仅考虑 的时会员对某一张DVD的定购请求是否满足而没有考虑用户请求盘数为三的要求,故上 述分配方案可能导致某些用户请求订单上的一张,或两张盘得到满足,显然对于这些用 户来说分配并未完成,故统计过程中仅可以记录已经分配三张碟片的会员编号,及其对 应的DⅦD编号 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 7 现的,所以我们考虑用算法实现. 根据我们对满意度的理解及该模式下的网站的经营方案,如果要使得会员的满意度 达到最大,应该尽量满足会员订单之中偏爱度较小的碟片请求.根据我们的假设,会员提 交订单的时间是随机的,当网站在处理会员的订单请求时,必然存在一个处理次序问题, 我们假设处理次序仅与用户发出订单的次序有关. 假设当前的订单已经按会员的请求顺序排列出来,会员被编号为 1-1000,为了使得 总体的满意度最大,我们所要做的是尽量满足会员订单中偏爱度较小的请求,同时尽量 满足编号靠前的会员的请求.根据以上分析我们引入下面的算法解决分配方案: 1),提取表 2 中的数据,经过一定的加工处理生成需求矩阵 Metrij ,偏爱矩阵 UserMetrmn .矩阵 Metrij 反映了会员 i 对 DVDj 的偏爱程度,0 表示会员对该 DVD 无需 求,1,2….n 分别表示会员对 DVD 的偏爱程度,数值越小偏爱程度越高。矩阵UserMetrmn 反 映了会员 m 偏爱度为 n 的对应的 DVD 编号. 2),根据用户的偏爱度从低到高进行排序,偏爱度相同的按照会员编号进行排序, 构成序列 Ai , Bi .其中 Ai 记录了序列第 i 项对应的会员编号, Bi 记录了序列第 i 项对应 会员满足一定偏爱的 DVD 编号. 3),构建 DVD 库存序列 ,( 1, 2.....100) i Store i = ,表示 DVDi当前的库存数.构建会员定购 盘 数 序 列 Checki , 表 示 会 员 j 当 前 还 需 满 足 的 DVD 盘 数 , 显 然 分 配 前 有 3,( 1,2......1000) Count j j = = . 4),构建与 Ai 序列等长的序列Checki ,然后对 Ai , Bi 中的数据逐个检索,假设 Ai 中第 i 项中会员的编号为k , Bi 中第i 项中 DVD 编号为l .如果Count k( ) 0 > 并且 Store l( ) 0 > ,则 说明会员k 希望得到l 号DVD,已分配给会员k 的光碟数不足三张,而l 号DVD有库存,所以 可以把l 号 DVD 分配给会员k , 令 Check i( ) 1 = ,Count k Count k ( ) ( ) 1 = − , Store l Store l ( ) ( ) 1 = − . 否则,如果Count k( ) 0 = ,说明当前的会员 k 已经分配的三张光碟,如果 Store l( ) 0 = , 说明会员 k 希望分配的 l 号 DVD 已经分完,显然这两种情况都不满足分配条件,故令 Check i( ) 0 = .显然Checki 中 0,1 分布反映了 DVD 的分配情况. 5),统计Checki 中的所有的 1 对应的会员编号及对应的 DVD 编号,由于分配时仅考虑 的时会员对某一张 DVD 的定购请求是否满足而没有考虑用户请求盘数为三的要求,故上 述分配方案可能导致某些用户请求订单上的一张,或两张盘得到满足,显然对于这些用 户来说分配并未完成,故统计过程中仅可以记录已经分配三张碟片的会员编号,及其对 应的 DVD 编号
性规划遡归算法猢流通最大熵原规理淑祥 6),上述分配完成后剩余部分未分配的碟片,同时有一些会员未分配到DVD,或者仅 分配到部分DVD.显然这些仅用这些剩余碟片无法满足剩余用户的分配需求.但是如果把 分配给会员的部分碟片回收起来,然后对这些会员重新分配仍然可以满足部分会员的分 配需求.故我们把剩余的碟片以及分配给用户的部分碟片统一回收,然后根据已经处理 的会员,DVD情况生成新的需求矩阵M,偏爱矩阵 UserMetr,然后重复上述步骤就可 以对这些剩余的碟片重新分配 7),重复步骤6)可以不断的对剩余碟片进行重新分配.当一次分配过程中得到分配 的会员个数M<1时,说明当前统一回收的DD已经无法满足任何剩余会员的分配请求 这时,上述循环步骤终止 8),对于已完成分配的会员编号i,及其对应的DVD编号j,将其在需求矩阵Metr中 对应的偏爱度Metr(i,j清零. 根据上述算法可以得出每次分配过程中的会员编号以及对应的DVD编号,以及整个 分配过程中得到分配的会员编号及对应的DD编号,未得到满足的会员编号及其对应的 DVD编号 本分配方案从尽量满足会员订单中偏爱度较小的请求,及编号靠前的会员的请求出 发,由于算法开始时创建的A,B序列是按照偏好数值从高到低排列的,对于偏好数值相 同的情况,我们保证会员编号靠前的会员排在编号靠后的会员之前,从而尽可能的保证 了编号靠前的会员的最大的满意度.本算法对剩余碟片及分配给用户的部分碟片统一回 收,然后重新分配,从而保证了尽可能多的会员的订单请求得到满足,如果不采用递归算 法,即仅分配一次得到分配的用户数为792(个),但是采用递归之后得到完全分配的用户 的个数为915(个),显然绝大多数的会员得到了满足.分配结束后会有部分会员的订单请 求没有得到满足,对于本模型来说,有85名会员没有在当天得到需要的碟片,这样显然会 影响这些会员的满意度,但是这些会员的编号一般比较靠后.对整体的满意度影响很小. 同时,对于这部分会员,可以直接将他们放到第二天订单序列的最前部.从而保证他们的 订单请求在第二天先被满足.这样,对于所有会员来说,绝大多数会在订单发出当天得到 满足,而剩余的会员也基本在两天之内得到满足.综上所述,本模型可以使得会员得到较 大满意度 根据上述分配方案可以得到前30位会员(C0001C0030)获得的DVD情况如下表所 示: 「会员编号 DVD编号 C0001 DVD8 DVD82 DVD98 C0002 当天订单请求无法满足 C0003 DVD80 DVD50 DVD DVD18 DVD41 C0005 DVD66 DVD68 DVDII C0006 DVDI9 DVD53 DVDI6 C0007 DVD8l DVDs DVD26 C0008 DVD71 DVD99 DVD31 C0009 DVD53 DVDIO DVD78 C0010 IDVD60 DVD55 VD85 2005年全国线性生数性建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 8 6),上述分配完成后剩余部分未分配的碟片,同时有一些会员未分配到 DVD,或者仅 分配到部分 DVD.显然这些仅用这些剩余碟片无法满足剩余用户的分配需求.但是如果把 分配给会员的部分碟片回收起来,然后对这些会员重新分配仍然可以满足部分会员的分 配需求.故我们把剩余的碟片以及分配给用户的部分碟片统一回收,然后根据已经处理 的会员,DVD 情况生成新的需求矩阵 Metrij ,偏爱矩阵UserMetrmn ,然后重复上述步骤就可 以对这些剩余的碟片重新分配. 7),重复步骤 6)可以不断的对剩余碟片进行重新分配.当一次分配过程中得到分配 的会员个数 M <1 时,说明当前统一回收的 DVD 已经无法满足任何剩余会员的分配请求. 这时,上述循环步骤终止. 8),对于已完成分配的会员编号 i,及其对应的 DVD 编号 j,将其在需求矩阵 Metrij 中 对应的偏爱度 Metr i j ( , )清零. 根据上述算法可以得出每次分配过程中的会员编号以及对应的 DVD 编号,以及整个 分配过程中得到分配的会员编号及对应的 DVD 编号,未得到满足的会员编号及其对应的 DVD 编号. 本分配方案从尽量满足会员订单中偏爱度较小的请求,及编号靠前的会员的请求出 发,由于算法开始时创建的 Ai , Bi 序列是按照偏好数值从高到低排列的,对于偏好数值相 同的情况,我们保证会员编号靠前的会员排在编号靠后的会员之前,从而尽可能的保证 了编号靠前的会员的最大的满意度.本算法对剩余碟片及分配给用户的部分碟片统一回 收,然后重新分配,从而保证了尽可能多的会员的订单请求得到满足,如果不采用递归算 法,即仅分配一次得到分配的用户数为 792(个),但是采用递归之后得到完全分配的用户 的个数为 915(个),显然绝大多数的会员得到了满足.分配结束后会有部分会员的订单请 求没有得到满足,对于本模型来说,有85名会员没有在当天得到需要的碟片,这样显然会 影响这些会员的满意度,但是这些会员的编号一般比较靠后.对整体的满意度影响很小. 同时,对于这部分会员,可以直接将他们放到第二天订单序列的最前部.从而保证他们的 订单请求在第二天先被满足.这样,对于所有会员来说,绝大多数会在订单发出当天得到 满足,而剩余的会员也基本在两天之内得到满足.综上所述,本模型可以使得会员得到较 大满意度. 根据上述分配方案可以得到前 30 位会员（C0001~C0030）获得的 DVD 情况如下表所 示: 会员编号 DVD 编号 C0001 DVD8 DVD82 DVD98 C0002 当天订单请求无法满足 C0003 DVD80 DVD50 DVD4 C0004 DVD7 DVD18 DVD41 C0005 DVD66 DVD68 DVD11 C0006 DVD19 DVD53 DVD16 C0007 DVD81 DVD8 DVD26 C0008 DVD71 DVD99 DVD31 C0009 DVD53 DVD100 DVD78 C0010 DVD60 DVD55 DVD85
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 DVD63 DVDI9 C0012 DVD31 DVD2 DVD C0013 DVD96 DVD78 DVD21 C0014 DVD52 DVD23 D89 C0015 DVD13 D66 C0016 DVD84 DVD55 C0017 DVD67 DVD47 DVD51 C0018 DVD41 DVD60 VD78 C0019 DVD84 DVD86 I DV VD66 C0020 DVD45 DVD89 DVD61 C0021 DVD53 DVD45 DVD2 C0022 DVD57 DVD55 DVD38 C0023 DVD95 DVD29 C0024 DVD76 IDVD37 C0025 DVD9 DVD69 DVD8I C0026 DVD22 DVD68 DVD95 C0027 DVD58 DVD22 DVD50 当天订单请求无法满足 C0029 DVD30 VD44 C0030 DVD62 DVD37 DVD98 对该算法的评价 这种算法的特点是每次递归的过程保证最优,但以我们现有的数学知识无法论证它 最终得到的结果是全局近似最优还是局部最优对于模拟退火算法和遗传算法,模拟退火 中以一定的概率接受恶化解以及遗传算法中的交换和变异使他们避免了陷入局部最优 的境地,但这个算法中似乎没有这样的因子使其避免陷入局部最优但这种算法的计算速 度是相当快的,并且同步给出一个明确的分配方案,这使其优点所在我们考虑可由遗传算 法去验证这种算法的解,但这个体系的规模过于庞大遗传算法运算需要花费相当长的时 间,最终被我们放弃 问题(3) 我们考虑利用问题一与问题二建立的模型来处理问题三 1.我们首先考虑当前分配。先将表二统计成类似表一的表格,我们的原则是,不论偏 爱度,只要该会员选择了这张DD,我们就说他愿意观看这张DVD.下面的表格就是由表 统计出来的这100张DD每张愿意观看的人数(按DD序号排列) 84 99 78 87100 95 85 10284 94 100 116 1011099389101 97 91 91 119104 103 94103105108981059096105101 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 9 C0011 DVD59 DVD63 DVD19 C0012 DVD31 DVD2 DVD7 C0013 DVD96 DVD78 DVD21 C0014 DVD52 DVD23 DVD89 C0015 DVD13 DVD85 DVD66 C0016 DVD84 DVD97 DVD55 C0017 DVD67 DVD47 DVD51 C0018 DVD41 DVD60 DVD78 C0019 DVD84 DVD86 DVD66 C0020 DVD45 DVD89 DVD61 C0021 DVD53 DVD45 DVD2 C0022 DVD57 DVD55 DVD38 C0023 DVD95 DVD29 DVD81 C0024 DVD76 DVD41 DVD37 C0025 DVD9 DVD69 DVD81 C0026 DVD22 DVD68 DVD95 C0027 DVD58 DVD22 DVD50 C0028 当天订单请求无法满足 C0029 DVD55 DVD30 DVD44 C0030 DVD62 DVD37 DVD98 对该算法的评价 这种算法的特点是每次递归的过程保证最优,但以我们现有的数学知识无法论证它 最终得到的结果是全局近似最优还是局部最优.对于模拟退火算法和遗传算法,模拟退火 中以一定的概率接受恶化解以及遗传算法中的交换和变异使他们避免了陷入局部最优 的境地,但这个算法中似乎没有这样的因子使其避免陷入局部最优.但这种算法的计算速 度是相当快的,并且同步给出一个明确的分配方案,这使其优点所在.我们考虑可由遗传算 法去验证这种算法的解,但这个体系的规模过于庞大,遗传算法运算需要花费相当长的时 间,最终被我们放弃. 问题（3）: 我们考虑利用问题一与问题二建立的模型来处理问题三。 1．我们首先考虑当前分配。先将表二统计成类似表一的表格,我们的原则是,不论偏 爱度,只要该会员选择了这张DVD,我们就说他愿意观看这张DVD.下面的表格就是由表二 统计出来的这 100 张 DVD 每张愿意观看的人数(按 DVD 序号排列): 84 92 87 99 78 87 87 100 93 90 95 97 85 102 84 94 102 91 100 116 96 101 109 93 89 101 87 83 97 97 100 87 91 82 109 97 91 94 87 87 119 104 93 90 106 94 94 88 91 94 107 91 98 92 97 99 108 77 85 103 94 103 105 108 98 105 90 96 105 101
山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 95106 78 10794 93 90 10278 我们仍认为需求量满足正态分布,从而由第一问的方法求出各种DVD需求人数的上限 (置信度仍为0.95): 9710710211592102101115108105 10911210011898109118106116133 1l712510810411710297 112 11610210696 106109 102 102 13512010810512 109103105 109 123 11410711211512491 109119 121124114 121105111121 117 110 122100 105101 11596 114 115908598 10492 110 87109 114 1231091081051189211011694101 我们仍假设a=0.4,B=0.6。这样利用公式(1)求出当前各种DVD的需求量(这里 =95%) 58646l685561606864626566597058657063697966 69746462696158666669616357746663656l6l8071 646272656561626573636864666874545971657172 746872626672696572595762606168576868535058 625565526568736564627055656956 利用 Lingo求得模式一的当前分配方案,这里给出前30位会员的分配 会员编号 DVD编号 C000l DVD8 DVD82 DVD98 C0002 DVD DVD42 DVD44 C0003 DVD4 DVD50 DVD8O C0004 DVD7 DVD18 DVD41 C0005 DVDIl DVD66 DVD68 C0006 DVD16 DVDI9 DVD53 C0007 DVD I DVD26 I DVD81 C0008 DVDI5 DVD71 DVD99 C0009 DVD53 DVD78 DVD100 C0010 DVD55 DVD60 DVD85 COOll DVD59 DVD63 DVD19 C0012 DVD31 DVD2 DVD DVD78 DVD96 C0014 DVD52 DVD23 DVD43 C0015 DVD13 DVD85 DVD88 C0016 DVD84 DVD97 DVD C0017 DVD67 DVD47 DVD51 C00l8 DVD41 DVD60 DVD78 2005年全国大学生数学建模竞赛全国一等奖
山东大学：孙凯、姚相振、王棹，指导教师：黄淑祥 2005 年全国大学生数学建模竞赛全国一等奖 10 95 106 85 82 90 86 88 99 82 98 99 77 72 84 90 78 95 73 94 98 107 94 93 90 102 78 95 101 80 86 我们仍认为需求量满足正态分布，从而由第一问的方法求出各种 DVD 需求人数的上限 （置信度仍为 0.95）： 97 107 102 115 92 102 101 115 108 105 109 112 100 118 98 109 118 106 116 133 111 117 125 108 104 117 102 97 112 112 116 102 106 96 125 112 106 109 102 102 135 120 108 105 122 109 109 103 105 109 123 106 114 107 112 115 124 91 100 119 109 119 121 124 114 121 105 111 121 117 110 122 100 96 105 101 103 115 96 114 115 90 85 98 104 92 110 87 109 114 123 109 108 105 118 92 110 116 94 101 我们仍假设α = 0.4 ， β = 0.6。这样利用公式（1）求出当前各种 DVD 的需求量（这里 ω j = 95% ）： 58 64 61 68 55 61 60 68 64 62 65 66 59 70 58 65 70 63 69 79 66 69 74 64 62 69 61 58 66 66 69 61 63 57 74 66 63 65 61 61 80 71 64 62 72 65 65 61 62 65 73 63 68 64 66 68 74 54 59 71 65 71 72 74 68 72 62 66 72 69 65 72 59 57 62 60 61 68 57 68 68 53 50 58 62 55 65 52 65 68 73 65 64 62 70 55 65 69 56 60 利用 Lingo 求得模式一的当前分配方案，这里给出前 30 位会员的分配： 会员编号 DVD 编号 C0001 DVD8 DVD82 DVD98 C0002 DVD6 DVD42 DVD44 C0003 DVD4 DVD50 DVD80 C0004 DVD7 DVD18 DVD41 C0005 DVD11 DVD66 DVD68 C0006 DVD16 DVD19 DVD53 C0007 DVD8 DVD26 DVD81 C0008 DVD15 DVD71 DVD99 C0009 DVD53 DVD78 DVD100 C0010 DVD55 DVD60 DVD85 C0011 DVD59 DVD63 DVD19 C0012 DVD31 DVD2 DVD7 C0013 DVD21 DVD78 DVD96 C0014 DVD52 DVD23 DVD43 C0015 DVD13 DVD85 DVD88 C0016 DVD84 DVD97 DVD6 C0017 DVD67 DVD47 DVD51 C0018 DVD41 DVD60 DVD78
