2005年中国大学生数学建模竞赛论文VIP

重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 1 DVD 在线租赁在线租赁 重庆通信学院重庆通信学院 郑丽莉郑丽莉 叶淑香叶淑香 李立埔李立埔 指导教师指导教师 刘忠敏刘忠敏 摘要摘要本问题是一个以 DVD 租赁为背景包含 01 规划，带约束非线性规划、线 性规划等内容的建模问题。 问题一中，首先建立了一个简易规划模型，它没有考虑对两种 DVD 都有需 求的人的“交集”问题，易计算出五种 DVD 至少应准备的数量。进一步考虑同 时想看五种 DVD 中相同两种 DVD 的人，即所谓“交集”现象对结果的可能影 响，我们用动态方程的方法精确描述了租赁过程，并建立了相应的规划模型。 显然“交集”问题是彻底解决 DVD 租赁问题的“核心”难点。 问题二中，我们对偏爱程度进行求倒处理使之转化为满意度，并对这样处理 的合理性进行详细论述。在此基础上建立了 0- 1 规划模型，求出了整体最大满意 度，相应的得出网站手上现有 100 种 DVD 的分配方案。在模型的求解过程中， 由于数据庞大不好处理，我们运用了 Lingo 批命令，很好的解决了这个难点。 问题三中，结合了问题一与问题二，看似是一个双目标规划问题，但实际上 无法把两个目标综合成一个整体同时来求解， 因为第一个租赁周期还 DVDi 的人 是随机的，所以第二阶段的分析很难进行，显然这也是彻底解决 DVD 租赁问题 的另一“核心”难点。注意到本题问题一、问题二的求解我们可以看到问题一的 本质是求 DVD 数量，问题二的本质是求满意度，所以我们按这个次序分别来解 决问题三，即这是一个“序列决策”问题。 问题四中，我们考虑到对任何经营方而言，利润是一个关键的考虑因素，而 利润与会员月费、网站每月租出 DVD 数目密切相关，因此我们建立模型来阐述 利润与两者的关系。 此外还定性的分析了会员的总人数 M 的稳定性和 DVD 的租 赁周转周期对网站管理的影响。 简要计算结果如下： （1） 对表1所给5种 DVD， 为保证至少50%的会员在一个月内能够看到该DVD， 那 5 种 DVD 各应准备至少 6250、3150、1562.5、781.3、312.5 张，共 12031 张。 保证在三个月内至少 95%的会员能够看到该 DVD 时，5 种 DVD 各应准备至少 4232.6 2116.3 1058.2 529.1 211.6 张，共 8147.8 张。 （2）问题的最大满意度为 1634.712，归一化后的满意度为 0.892 ，前 5 位会员 分别获得 DVD 的情况： （具体结果见正文） 会员编号 会员 1 会员 2 会员 3 会员 4 会员 5 DVD 编号 8 44 98 6 44 62 32 50 80 7 18 41 11 66 68 （3）对表 2 中 DVD 的现有数量全部为 0 的情况，要使一个月内 95%的会员得 到其在线租赁的 DVD，需购进 DVD 的总量为 4560 张（100 种 DVD 的具体购进 量见正文） 。 一个月的总体归一化最大满意度为 0.84。 前 5 位会员分别获得 DVD 的情况（具体分配情况见问题三） ： 会员编号 会员 1 会员 2 会员 3 会员 4 会员 5 DVD 编号 8 82 98 6 42 44 4 50 80 7 18 41 11 66 68 关键字关键字 动态规划动态规划 0- 1 规划规划 交集问题交集问题 满意度满意度 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 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位会员 的在线订单（表 2 的数据格式示例如下表 2） ，如何对这些 DVD 进行分配，才 能使会员获得最大的满意度？请具体列出前 30 位会员（即 C0001C0030）分 别获得哪些 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 会员 在线 订单 注： D001D100 表示 100 种 DVD, C0001C1000 表示 1000 个会员, 会员的 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 3 在线订单用数字 1,2,表示，数字越小表示会员的偏爱程度越高，数字 0 表示对 应的 DVD 当前不在会员的在线订单中。 二、基本假设二、基本假设 1、60%的会员每月租赁 DVD 两次，而另外的 40%只租一次 2、每个会员每次租得 3 张 DVD。 3、每个会员只有将已租 DVD 归还后才能继续参加下一次租赁. 4、归还时会员需要将 DVD 放进网站提供的信封里寄回（邮费由网站承担） ，就 可以继续下次租赁。 5、归还的 DVD 可以马上参加下一次租赁. 6、同一种 DVD 每个会员只能借一张。 7、假设网站现有 10 万会员. 8、其他假设在具体问题分析中提出. 三、符号说明 三、符号说明 1 0, 10 10iDVD 10iDVD ij ijijij ij j i i i i biDVDjDVD aiDjDVDba b xj M M P q RDVDi Q = ? ? ? ? ? ? ? ? ? 第 个会员对编号为的的偏爱程度; 第 个会员对编号为的的满意度, 当时 ; 购买DVD 的数量 G 整体满意度; 会员的总人数万 万会员中愿意看第 种的人数 万会员中愿意看第 种的人的概率 每月只租一次的会员所占百分比 愿意看的会员 1,2,3,1000100 j ij DVDi SDVD pDjDVD hDVDiDVDj ij= ? ? ? ? ? 实际租出的数量 购买总数 所有会员中愿意观看编号为的的人的比例; 同时想看和的人数 , =1,2,3, 四、问题分析四、问题分析 结合本题的背景知识， 宏观上我们应该站在数学期望的角度从以下几个方面 分析 DVD 的在线租赁问题： 1、 在保障足够多会员在一定时间内能看到其希望看到的 DVD 的条件下，网方 最少需要准备各种 DVD 的数量。 2、网方现有 DVD 数一定，如何将其合理分配，才能使会员满意度最大，并详 细说明满意度最大的含义 。 3、在保障足够多会员在一定时间内能看到其希望看到的 DVD， 并且满意度最大 的条件下，网方最少需要准备各种 DVD 的数量，如何将其合理分配。 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 4 4、在考虑保障足够多会员在一定时间内能看到其希望看到的 DVD 以及会员最 大满意度的同时，考虑网站的实际经营问题，包括经营成本，邮递时间等等。 5、问题的约束条件，包括：(1) 每个会员每个月租赁次数不得超过 2 次，每次 获得 3 张 DVD（2）60%的会员每月租赁 DVD 两次，而另外的 40%只租 1 次。 （3）满足人数占总人数的比例的下限值。 下面我们将逐个问题进行讨论. 五、模型的建立与求解五、模型的建立与求解 （一） 问题一（一） 问题一 如何购买新的如何购买新的 DVD 问题一要求我们解决的问题可分为两个部分，一是至少应该准备多少张 DVD，才能保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD，我们称这种情况为“50%的情况” ；二是至少应该准备多少张 DVD，才能 保证在三个月内至少 95%的会员能够看到该 DVD，我们称这种情况为“95%的 情况” 。这个百分数就是对目标函数的一个约束条件。 由题目可知，60%的会员每月租赁两次，40%的会员每月租赁一次。每月租 赁两次的会员平均 15 天归还，当次租的 DVD 归还后可以立即进入网站的下一 次租赁，每月租赁一次的会员平均 30 天归还，考虑到这一特征我们建立了简易 模型。 又考虑到存在同时愿意看 5 张 DVD 中的两张 DVD 的会员情况， 即产生 “交 集”的情况，会对结果产生影响。我们进一步建立了动态方程下的精确模型。 1 简易模型简易模型 1.1 50%的情况的情况 题单通过问卷调查 1000 个会员，得到了愿意观看这些 DVD 的人数(表 1) 表 1 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人数 200 100 50 25 10 令 i P 为10万会员中愿意看DVDi的人的比例,由表1得到1000人中愿意观看 每种DVD的概率分别为() 12345 ,PPPPP ()0.2, 01, 005, 0025001=., . 由于 这 1000 人为 10 万人的子样本, 12345 ( ,)PPPPP 也可表示 10 万人中愿意观看 每种 DVD 的概率. 假设网站对 5 种 DVD 准备() 12345 xxxxx， ， ， ，张才能保证希望看到该 DVD 的会员中至少50%在一个月内能够看到该DVD， q为每月租赁一次的会员的比例。 则一个月内租出 DVDi 的总数为()1 ii xq x+.希望看到 DVDi 的总人数为 100000*Pi 。 写出简易模型简易模型如下： 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 5 5 i=1 i Min Sx= () () () () () 5 111 5 222 5 333 5 444 5 555 110/2 110/2 110/2 110/2 110/2 xq xP xq xP xq xP xq xP xq xP + + + + + 把()() 12345 ,0.2010050 025001PPPPP= , ., . , ., . 代入上面的模型易 得需要准备的 DVD 的总数量至少为 S=12031.25 张，5 种 DVD 的需要数量分别 为() 12345 xxxxx， ， ， ，=()625031251562.5781.25312.5 ， ， ， ， 1.2 95%的情况的情况 60%的会员每月租赁 DVD 两次，而另外的 40%只租一次，对这一假设不能简 单的理解为一个人借两次就一直是借两次， 其实他完全可能下一回变成只借一次 的人，同样的借一次的人下月也可能变为借两次的人，只不过总量来看是 60%的 会员每月租赁 DVD 两次， 而另外的 40%只租一次。 此外月的分界不可能那么清楚， 太清楚则并不方便。 针对网站三个月进行的六次租赁我们以 DVD1 为例，做下面收发图： 时间轴上方的箭头表示网站借出的 DVD1 的数量，轴下方的箭头表示网站 收回的 DVD1 的数量. 三个月内， 租赁 DVD 的总次数为 6， 假设前一次收回的 DVD 能够立即进入 下一次租赁。网站每次租出 DVD 数如下： 第一次： 111 cx= 第二次： 1211 c= （1-q）c 可借出的为第一次还回的 第三次： 131112 cqcc=+(1-q) 借出的为第一次另一部分还回的与第二次还回的 第四次： 141213 cqcc=+(1-q) 第五次： 151314 cqcc=+(1-q) 第二次 第六次 第一次租赁 第五次 第四次 第三次 14 c 12 c 13 c 15 c 11 c 16 c 12 c 13 c 14 c 15 c 16 c 时间 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 6 第六次： 161415 cqcc=+(1-q) 推广到一般的 i DVD （i=1,2,3,4.5）三个月每次租出数目(1,2,.,6) ij cj =为： 11 21 312 423 534 645 (1,2,3,4,5) ii ii iii iii iii iii cx c cqcc cqcc cqcc cqcci = = = = = = （1-q）c +(1-q) +(1-q) +(1-q) +(1-q) 由此我们可得到如下带约束条件的线性规划模型：线性规划模型： 5 1 6 020000 i i ij i ij Min fx c i M c = = i=1 95% =1.5 用 MATLAB 优化工具箱求解(见附录 I)得 DVD 准备情况,至少需准备 DVD 总数：7599.8 张。5 种 DVD 的数量分别 2、动态方程下的精确模型动态方程下的精确模型 在现实中, 必然存在想看这 5 张 DVD 中多张 DVD 的会员的情况,我们把 它称为“交集”问题，显然“交集”问题是彻底解决 DVD 租赁问题的“核心” 难点问题。上面的简易模型没有考虑到交集问题，下面我们先考虑不同的交集对 结果的影响，然后利用动态方程列出精确模型。 2.1 讨论交集问题对模型结果的影响讨论交集问题对模型结果的影响. 因为 i M为M的子集，所以其分布与(1,2,.,5) i P i =的分布相同。 a、针对同时想看相同两种 DVD 的会员情况，我们定义了一个交集矩阵 H 为： 112131415 212232425 3 13233425 414243445 5 15253545 () ij MM PM PM PM P M PMM PM PM P HhM PM PMM PM P M PM PM PMM P M PM PM PM PM = DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 需准备数量 3952.3 19692 989.8 490.8 197.7 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 7 2000020001000500200 200010000 500250100 1000500500012550 50025012562525 200100502510 = i=(1,2,3,4,5),j=(1,2,3,4,5) 10 10iDVD 10iDVD i i M M P ? ? ? 会员的总人数万 万会员中愿意看第 种的人数 万会员中愿意看第 种的人的比例 其中， ij h 表示同时想看 DVDi 与 DVDj 的人数，矩阵对角线上的元素表示 5 张 DVD 中只愿意看一张 DVD 的人数。很显然这个矩阵为对称矩阵， ji h 也为同 时想看 DVDi 与 DVDj 的人数，因为 i P 与 j P 是相互独立的，即 ijijijjijiji hM PMPPMP PM Ph= b、同理，对于同时想看三张 DVD 的情况，我们也可形成交集矩阵H ,下列表中 列举了在 5 种 DVD 中想看 DVD1 同时还想看其它两种 DVD 的人数： 12345 12 13 14 2000 2000 100 50 20 1000 100 1000 25 10 500 50 25 PPPPP MPP MPP MPP 15 500 5 200 20 10 5 200 MPP 比如，表中第一行第三列表示 123 MPPP，即 123 MPP P ，表示同时想看 DVD1、 DVD2、DVD3 的人数为 100。从上表可以看出：与同时想看一张或两张 DVD 的 情况相比，想看三张 DVD 的概率很小 ，可以忽略不计(从理论上讲这是因为 123 PP P 数量级已为 0.0010,很小),因此我们只需考虑想看两张 DVD 的情况时的交 集。 2.2 2.2 模型的建立模型的建立 由于网站现有的 DVD 的数量与 DVD 已被租赁的次数密切相关，存在不同 的状态，因此我们采用了状态方程，下面，我们对问题的两个部分分别讨论。 2.2.1 2.2.1 50%的情况的情况 在第一个月内 60%的会员租了两次，40%的会员租了一次，我们只需以网站 两次租赁 DVD 的情况为基准来考虑。具体租赁流程如下： Step1Step1 第一次租赁 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 8 在问题一中,愿意观看DVDi的人数 i M 和实际租出DVDi的数量 i Q 是随租赁次 数而变化的,为状态变量,由此我们对不同的租赁次数形成一系列状态表.在此, 与第一周期相对应的为状态表一: 状态表一 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看人数 1 M 2 M 3 M 4 M 5 M DVD准备数量 1 x 2 x 3 x 4 x 5 x DVD实际租出数量 1 x 2 x 3 x 4 x 5 x 在此, 实际租出 DVD 数量 12345 ( ,)x x x x x即为第一次租赁中准备 DVD 数量, 即使如此也可能不能满足 50的希望看到某 DVD 的会员在一月内能够看到该 DVD,因为 DVD 数量有限。 Step2 Step2 第二次租赁 同理，列出状态表二 状态表二 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人数 1 R 2 R 3 R 4 R 5 R DVD现有数量 0.6 1 x 0.6 2 x 0.6 3 x 0.6 4 x 0.6 5 x DVD实际租出数量 1 Q 2 Q 3 Q 4 Q 5 Q 此时，第二次租赁中愿意观看的人数 i R 和实际租出 DVD 数量 i Q 未知,求出它 们是关键. Step3 Step3 求在第二次租赁中愿意观看的人数 i R 和实际租出 DVD 数量 i Q () iii RMx= - ij m 其中 ii Mx 为想租 DVDi 却在第一次租赁中没租到的人数 , ij m 为每月只 租一次的人群中 同时愿意看DVDi与DVDj 却只租到DVDj 的人数(他们不参加这 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 9 个月的第二次租赁),而要计算 ij m 比较复杂,是整个问题二的难点。 只要求出 i R 的表达式， i Q 的表达式就好得到了。下面我们通过求 1 R 的表达 式来推导 i R 和 i Q 。 11求求 1 R 的表达式 的表达式 为便于表述，首先引入以下符号： 事件 A：会员在线租赁 DVD1 事件 B：会员既在线租赁 DVD1 又在线租赁 DVD2 事件 C：在第一次租赁中,会员租到 DVD1 同时还想租赁 DVD2，但他们每月只 租一次。 事件 D：在第一次租赁中,会员租到 DVD2 同时还想租赁 DVD1，但他们每月只 租一次。 事件 E： 会员在第一次租赁中既租到 DVD1 又租到 DVD2，但他们每月只租一 次。 显然，这 5 个事件存在如下关系： ,BA CB DB CDE EB= 用文氏图表示（B 为全集）表示这些事件之间的关系 A、B、C、D、E 事件的人数分别为： n(A)= 1 M n(B) = 1221 M PM P= n(C)= 12 x Pq n(D)= 21 x Pq 其中，n(A)、n(B)、 n(C)、 n(D)、 n(E)分别代表满足 A、B、C、D、E 事 件的人数。q=40%表示每月只租一次 DVD1 的会员的比例。 求每月只租一次的人群中 同时愿意租 DVD1 与 DVD2 却只借到 DVD2 人数 12 m 由于事件 C、D 相互独立，则： 2 12 12 (E)()( )() x x q PP C DP CP D M M = 在第一次租赁中既租到 DVD1 也租到 DVD2 的人数： 2 122 12 2 n(E)= () x x Pq MP P C D M = 想 看DVD1又 想 看DVD2却 只 租 到DVD2的 人 数 ： 12 m = 2 122 21 2 n D E x x q P x Pq M =() A B C D E 文氏图 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 10 这部分人很特殊，他们既想看这部分人很特殊，他们既想看 DVD1 又想看又想看 DVD2，但在第一次租赁中他，但在第一次租赁中他 们只租到们只租到 DVD2， 又由于他们一个月只租一次，所以在第二次租赁中他们不再为， 又由于他们一个月只租一次，所以在第二次租赁中他们不再为 被租赁的对象。被租赁的对象。 由得第二次租赁中愿意观看的人数 1 R 的表达式为： 5 1111 2 () j j RMxm = = 22由 1 R 推广得到 i R 的表达式： 5 1 () iiii j j j i RMxm = = 33实际租出 DVD 数量 i Q ： () ()() i 1 11 iii iii RRq x Q q xRq x = , , Step4 Step4 建立模型 目标函数为购买最少的 DVD 数量: 5 1 i i Minx = S= 约束条件为：想看 DVDi 的会员中至少 50%在一个月内能够看到 DVDi,即： 50 ii i xQ M + % 动态方程下的精确模型精确模型为： 5 1 i i Minx = S= 50 1,2,.,5 0 ii i i xQ Mi x + % = () 2.2.2 95的情况的情况 列出三个月中 6 次租赁的状态 状态表三: DVD 编号 DVD1 DVD2 DVD3 DVD4 DVD5 愿意观看的人数 1 R 2 R 3 R 4 R 5 R DVD准备数量 11 x 12 x 13 x 14 x 15 x 第 一 次 DVD实际借出数量 11 x 12 x 13 x 14 x 15 x 第 一 月 第 二 DVD准备数量 60% 11 x 60% 12 x 60% 13 x 60% 14 x 60% 15 x 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 11 次 DVD实际租出数量 11 Q 12 Q 13 Q 14 Q 15 Q DVD准备数量 21 x 22 x 23 x 24 x 25 x 第 三 次 DVD实际借出数量 21 x 22 x 23 x 24 x 25 x DVD准备数量 60% 21 x 60% 22 x 60% 23 x 60% 24 x 60% 25 x 第 二 月 第 四 次 DVD实际租出数量 21 Q 22 Q 23 Q 24 Q 25 Q DVD准备数量 31 x 32 x 33 x 34 x 35 x 第 五 次 DVD实际借出数量 31 x 32 x 33 x 34 x 35 x DVD准备数量 60% 31 x 60% 32 x 60% 33 x 60% 34 x 60% 35 x 第 三 月 第 六 次 DVD实际租出数量 31 Q 32 Q 33 Q 34 Q 35 Q 其中， ij x .为第 i 月实际 DVD 准备量 由此建立精确模型精确模型： 5 1 1 112233 ()()() 951,2,.,5 0 i i iiiiii i ij Min Sx xQxQxQ i M x = = + % ( =) 2.3 精确模型的求精确模型的求解解： 此问题是典型的带约束非线性规划问题， 编程中涉及到很多阶跃函数，很难 用 LINGO 编程计算， 在这里我们用 MATLAB 优化工具箱解决此问题 （见附录 I） ， 求得具体结果如下： 2.3.1 至少至少 50%在一在一个月内能够个月内能够看看到该到该 DVD 的的条件条件下，下，DVD 准备准备情况：情况： DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 需准备数量 6250 3125 1562.5 781.3 312.5 至少需准备 DVD 总数：12031.3 张 2.3.2 至少至少 95%在在三个月内能够三个月内能够看看到该到该 DVD 的的条件条件下，下，DVD 准备准备情况：情况： DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 需准备数量 4232.6 2116.5 1058.2 529.3 211.6 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 12 至少需准备 DVD 总数：8148.2 张。 3 两种模型的比较两种模型的比较 从上表数据可以看出各 DVD 需准备数量的比例和对各种 DVD 有需求的人 的比例近似，这里我们在精确模型下作出 50%的情况下 5 种 DVD 对应的被租概 率，和实际需最少准备的数目对应关系图: (其中 X 轴表示 5 种 DVD 对应的需求概率，Y 轴表示 5 种 DVD 实际需最少准备的数目） 由图可看出 5 种 DVD 各自实际需最少准备的数目，与 5 种 DVD 各自对应 的需求概率近似成线形关系，说明了交集问题对结果的影响很小。从两个模型 的结果来看，结果也几乎一样.因此我们得出结论：交集问题对简易方法的影响交集问题对简易方法的影响 不大，可以忽略不大，可以忽略。到此我们可以放心的使用简易模型求解。 (二) 问题二 DVD 的分配方案 (二) 问题二 DVD 的分配方案 根据表 2 可知网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会 员的在线订单，此时网站需要对这些现有的 DVD 进行分配，使会员获得最大的满 意度。我们以最大满意度为目标函数，在相应的约束条件下,利用 0-1 规划模型 求出最大满意度，同时得到相应的分配方案。 1、 最大满意度的计算公式 1、 最大满意度的计算公式 1.1 几个矩阵的说明 1.1 几个矩阵的说明 a、订单矩阵 B 根 据 表 2 得 到 第 i 个 会 员 对 编 号 为 Dj 的 DVD 的 偏 爱 程 度 为 ij b ,(1,2,.,1000,1,2,.100)ij=,()0,1,2,10 ij b ?。则订单矩阵计作 1000 100 () ij Bb =。 ij b 越小表示会员的偏爱程度越高， ij b 为 1 时偏爱程度最高， ij b 为 0 表示对 应的 DVD 当前不在会员的在线订单中。 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 13 b、满意度矩阵 A 第 i 个会员对编号为 Dj 的 DVD 的满意度为 ij a ，它与偏爱程度 ij b 满足如下关 系 1 ,0 00 ijij ij ijijij ab b abb = = 时 = ， 时 ， 1 11 10 2 310 ij a ?， ，由此可得满意度矩阵 (),(1,2,.1000,1,2,.100) ij Aaij=。 现在我们来阐述一下用 ij a 来表示满意度的合理性。将 1 11 1 2 310 ?，化 为 （1 0.5 0.33 0.25 0.2 0.1667 0.1429 0.1251 0.1111 0.1） ，在 这组数据中我们可以明显地看出越在前面满意度差距越大， 如 1 与 0.5 的差距为 0.5，而越在后面的满意度相差非常小，如 0.111 与 0.1 只相差 0.001，这看似 不太合理， 但这是符合现实情况的， 比如在运动会中， 获第一名与获第二名的 “名 望”差距显然比获第九名与获第十名的差距大得多。进一步，为了得到更合理的 满意度的表达方式，我们可设一个满意度参数 K 来调节，即满意度取值为 111 2+k 3+k10+k ? 1 ， 1+k ，在这里我们先取 k=0。对参数 k 的其他情况也易 进行进一步讨论，这里就不再详述。 c、分配矩阵 X 如果第 i 位会员借到编号为 Dj 的 DVD，记为1 ij x = ，否则记为0 ij x =， ij x 为 0-1 变量。则 1000 个会员对 100 种 DVD 的借到情况可形成 0-1 矩阵 (), (1,2,.,1000,1,2,.100) ij Xxij= 我们称作分配矩阵。 1.2 1.2 约束条件约束条件 a、对分配矩阵 X 进行行求和则得到第i个会员借到的 DVD 的数量，记为： 100 1 iij j yx = = (1,2,1000,1,2,100)ij= 由基本假设知第i个会员每次借到的 DVD 的数量 i y 只能为 0 或 3，应该说这 个规定是合理的，否则邮寄效率差，也不合一般人想多要的心理愿望。 即有 31,2,.1000 iii ytti=， (其中 为0-1变量, ) b、 表2中第二行数据表示DVD现有数量10 40 15 2036 55 2 40 =, 每种 DVD 所借出的总数不能大于网站所拥有的该种 DVD 的总数，即 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 14 1000 1 ,(1,2,.100) ijj i xj = = c、没订单的 DVD 不借约束 ijij bx 1.3 目标函数 1.3 目标函数 目标函数为： ijij i j Gxa x , （ ）= 综上写出 0-1 规划模型0-1 规划模型： ijij i j Max Gxa x , （ ）= )10.(. 100.2 . 1.1000.2 . 1 3 1000 1 变量为 = = = i i jij ijij ii t ji x bx ty 2、模型的求解 、模型的求解 此问题显然是 0-1 规划模型，MATLAB 没有解决 0-1 规划的相应工具箱， 而 LINGO 中有；特别是针对此 10 万以上数据量的大型问题，用 LINGO 编程解 决更适合。但由于此问题涉及数据量非常大，而 LINGO 又在数据矩阵处理方面 比较薄弱，所以本问题的主要难点就落到人为的数据处理方面了。 a、由于 LINGO 对数据矩阵的识别要求非常严格，而本问题数据量非常大，满意 度矩阵 A（ ij a ）向 LINGO 程序的输入便成了本问题的难点。在这里我们试了 很多方法如 MATLAB 编程的 DIARY 命令转换文件格式等都不可行，最终我 们运用 C 语言编程，把 1000100 的数据转化成文本文件，巧妙的解决了此 问题。 b、在用 LINGO 编程求解过程中，由于计算数据量达几十万以上，电脑屏幕根 本无法完整显示，导致无法知晓计算结果，这里我们运用批命令，解决了此问 题: 批命令： bat dive result go solu rvrt bat bat,批命令开始，先用 dive result 命令，指定输出到 result 文本文件，接着 go 命 令运行当前 lingo 程序， 然后用 solu 命令将计算的结果显示在 result 中， 最后 rvrt 将模型结果返回到荧光屏, bat,批命令结束。 批命令工作流程如下： 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 15 c、LINGO程序 由于此程序涉及数据量较大，这里只对主体程序部分作如下说明： （完整程序见附录II） MODEL: SETS： i100/1.100/:B; ！网站现有DVDj的数目； i1000/1.1000/:t; ！自定义01向量； cc(i1000,i100):A,x; ！A满意度矩阵，X分配矩阵； ENDSETS ！ 目标函数（总体满意度最大）； max=sum(i1000(i):sum(i100(j):A(i,j)*x(i,j); ！约束条件每人可租DVD数Yi=3或0； for(i1000(i):sum(i100(j):x(i,j)=3*t(i); ！所租DVDj总数小于网站现有DVDj的数量； for(i100(j):sum(i1000(i):x(i,j)B(j); ！x(i,j)，t（i）为01变量； for(i1000(i):BIN(t(i); for(i1000(i):for(i100(j):BIN(x(i,j); DATA: ！网站现有DVDj的数目； B=10 40 15 20 20 12 30 33 35 25 29 31 36 55 2 40 ; ！A满意度矩阵； A = 0.1667 0 0 0 0 0 0.1250. 0 0.2500; ENDDATA END 1）、定义向量、矩阵：网站现有DVDj的数目向量，满意度矩阵，分配矩阵t（0 1）向量。 2）、主程序：目标函数（总体满意度最大）； 约束条件：每人可租DVD数Yi=3或0，所租DVDj总数小于等于网站现有 为使无法显示到显示屏幕中的大量数据结果显示于文本文件 result 中,建立批命令 打开 LINGO 主程序,点机击文件,并执行 Take command 命令导入批文件 执行 LINGO 主体程序,观察运行情况,等待运行结束 结果显示于文本文件 Result 中,观察并分析结果,得出 DVD 具体方案. 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 16 DVDj的数量;x(i,j)，t（i）为01变量。 3）、初始化：网站现有DVDj的数目向量，满意度矩阵。 d、 具体求解过程如下： 1 由表 2 数据通过 C+编程，得到会员满意度矩阵 A（ ij a ） ，同时设定分配 矩阵 100 1 ,(1,2,1000,1,2,100) ij j xij = = ， ij x 为 01 变量。 2 限定函数约束条件：每种 DVD 被借走的数目不超过现有数目，同时每个 会员借 DVD 数30- 1(1,2,.1000) iii ytti=， 为变量 。 3 建立目标函数： ijij i j Max Gxa x , （ ）=。 4 用 LINGO 程序具体求解， 得到会员满意度的最优解值 （最大值） ， 得到 DVD 的具体分配方案。 求解过程图 e、最终求解结果： 最大满意度为G = 1634.712， 显然， 最理想满意度为人人租到最想要的DVD， 即 1+1/2+1/3 为个人最大满意度，所以 1634.712 归一化为 1634.712 G0.892 11 1000 (1+) 23 = 前 30 位会员所获的 DVD 情况： 倒数运算 每种 DVD 被 借 走 的 数 目 不 超 过 现 有数目 目 标 函 数 设 定 （ 0- 1 ） 分 配 矩 阵 得 到 订 单 矩 阵 由 表 二 的 数 据 满 意 度 矩 阵 每 个 会 员 借 碟 数 为 0 或 3 约 束 条 件 两 矩 阵 所 有 对 应 元 素 乘 积 之 和 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 17 会员编号 分配 DVD 编号 1 8 44 98 2 6 44 62 3 32 50 80 4 7 18 41 5 11 66 68 6 19 53 66 7 8 26 81 8 31 35 71 9 53 78 100 10 55 60 85 11 59 63 66 12 2 31 41 13 21 78 96 14 23 52 89 15 13 66 85 （三）问题三（三）问题三 针对表针对表 2 的的 DVD 的购买和分配的购买和分配 本问题显然是问题一与问题二的结合性问题， 在这里我们根据题目要求解决 两个问题：1、用较小的 DVD 时 95%的会员得到他想看的 DVD；2、要求满意 度最大。 问题看似是一个双目标规划问题， 但实际上无法把两个目标综合成一个整体 同时来求解，因为第一个租赁周期还 DVDi 的人是随机的，所以第二阶段的分析 很难进行，注意到本题问题一、问题二的求解我们可以看到问题一的本质是求 DVD 数量，问题二的本质是求满意度，所以我们将按这个次序分别来解决问题 三，即这是一个“序列决策”问题。首先解决 DVD 数量问题。 根据题目 95%的会员得到他想看的 DVD， 我们先解决 DVD 的利用率指标 r， 问题一中的 r=50%，然后按照问题一的简易模型求出 DVD 数。 Step1 Step1 求需准备的 DVD 的数量，以满足 95%的人能看到该 DVD 借出 DVD 总数的上下限 上限：上限：假设租两次的人还回的 DVD 全部不能重复利用，则可得到借出 DVD 总数 的最大值： 0.4 1000 95% 30.6 1000 95% 64560 += 下限：下限：假设租两次的人还回的 DVD 全部能重复利用，则可得到借出 DVD 总数的 最小值： 0.4 1000 95% 30.6 1000 95% 32850 += 会员编号 分配 DVD 编号 16 10 55 97 17 47 51 67 18 41 60 78 19 66 84 86 20 45 61 89 21 45 50 53 22 38 55 57 23 29 81 95 24 37 41 76 25 9 69 81 26 22 68 95 27 50 58 78 28 8 26 34 29 26 30 55 30 37 62 98 重庆通信学院：郑丽莉、叶淑香、李立埔，指导教师：刘忠敏 2005 年全国大学生数学建模竞赛全国二等奖 18 利用问题一的模型求解 () 100 i=1 1 i iii Min Sx xq xMr = + （i=1，2，3，100） 此时假设网站保证希望看到该 DVD 的会员中