山东大学:孙凯、姚相振、王棹,指导教师:黄淑祥 用 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 编号