1、第 2 页 共 15 页 DVD 租赁优化方案 摘 要 线租赁是信息时代发展的必然趋势。在租赁过程中，网络经营者主要关注的预测、购买和分配。本文提出了简单随机抽样、分类预测和关联预测等三种方法进行需求预测。针对问题一，利用需求预测得到观看 DVD 的人数服从二项分布，并计算出多种可靠度下购买DVD 的数量 (见文中表 2、表 3). 以会员的最大满意度为目标函数，建立一个整数规划模型，得到问题二的分配方案，并计算出前 30 位会员的分配结果 (见文中表 4). 在问题三中，我们考虑到 60%的会员由于两次租赁而导致可重复利用，因而，采用了两阶段 购买的策略，在每个购买阶段都建立了双目标整数规划
2、，从而得到的购买量比原来网站拥有量小，并且会员的满意度达到 99.38%(见文中表 6、表 7). 文章最后还给出了考虑归还 DVD 周期的情形下购买与分配的模型。 一、问题的重述 第 3 页 共 15 页 这是一个在线 DVD 租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD 租赁服务。会员对哪些 DVD 有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的。网站会根据手头现有的 DVD 数量和会员的订单进行分发。 每个会员每个月租赁次数不得超过 2 次，每次获得 3 张 DVD。会员看完 3张 DVD 之后
3、，只需要将 DVD 放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。考虑以下问题： 1） 网站正准备购买一些新的 DVD，通过问卷调查 1000 个会员，得到了愿意观看这些 DVD 的人数（表 1 给出了其中 5 种 DVD 的数据）。此外，历史数据显示， 60%的会员每月租赁 DVD 两次，而另外的 40%只租一次。假设网站现有 10 万个会员，对表 1 中的每种 DVD 来说，应该至少准备多少张，才能保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD？如果要求保证在三个月内至少 95%的会员能够看到该 DVD 呢？ 2） 题中列出了网站手上 100 种
4、 DVD 的现有张数和当前需要处理的 1000 位会员的在线订单，如何对这些 DVD 进行分配，才能使会员获得最大的满意度？请具体列出前 30 位会员（即 C0001C0030）分别获得哪些 DVD。 3） 假设题中表 2DVD 的现有数量全部为 0。如果你是网站经营管理人员，你如何决定每种 DVD 的购买量，以及如何对这些 DVD 进行分配，才能使一个月内 95%的会员得到他想看的 DVD，并且满意度最大？ 4） 作为网站的经营管理人员，在 DVD 的需求预测、购买 和分配中还有哪些重要问题值得研究？请明确提出问题，并尝试建立相应的数学模型进行解答。 二、模型假设及符号说明 1、模型的假设
5、（） 以一个月为一个周期，考虑在一个周期内 DVD 的租赁情况； （） 一个周期结束，所租赁出的 DVD 全部归还网站，不影响下一个周期的租赁； （） 一个会员在一个周期内租赁到自己想看的 DVD 的时间不影响他的满意度； （） 会员只有在将第一次租赁的三张 DVD 还回网站之后，才能进行第二次租赁； （） 每个会员同一种 DVD 只租赁一次； （） DVD 在租赁过程中无损坏； 2、符号说明 jn 网站第 j 种 DVD 的购买量 jp 会员租赁第 j 种 DVD 的概率 ij 第 i 个会员是否租赁第 j 种 DVD ijx 第 i 个会员是否租赁到第 j 种 DVD ija 第 i 会员
6、对第 j 种 DVD 的偏爱程度 ijb 第 i 个会员租赁到第 j 种 DVD 的 满意度 第 4 页 共 15 页 ijy 网站是否为第 i 个会员购买第 j 种 DVD 三、问题的分析 问题一，要求网站提供的 DVD 能够满足他的会员至少有 50%能够在一个月内看到该 DVD，作为网站的经营者，考虑到利益的问题，因此希望购买到尽可能少的 DVD 。根据历史数据， 60%的会员每月租赁两次，即一部分 DVD 有一定的流通周期，我们在考虑模型的时候先不考虑时间问题，将 DVD 全都看作是一 月被租赁一次，然后根据流通周期以及它被租赁的概率，将所计算的结果按一定的比例减小。 问题二，这是一个优
7、化分配问题。根据各个会员对不同种 DVD 的偏爱程度，以及网站是否满足了他的要求，建立以满意度为目标的目标函数，在 DVD 数量有限的情况下，对其进行合理的分配，使目标函数达到最大值。 我们综合考虑问题一和问题二，在此基础上分析问题三。经营者要尽可能的减小成本，即每种 DVD 购买量尽可能的少的，同时， DVD 的购买量要满足 95%的会员在一个月内能够看到自己想看的 DVD；要求会员的总体满意程度最大，也就是对确定数量的 DVD 进行优化分配。此问题为一个双目标规划，即要求各种 DVD数目最小的情况下，尽可能的使总体满意度最大。 四、模型的建立及求解： 1、问题一模型的建立及求解 设随机变量
8、 1 D V D 1 , 2 , , 100 , 0000 D V Dijij i 表 示 第 个 会 员 租 赁 第 张 其 中表 示 第 个 会 员 不 租 赁 第 张. 显然随机变量 ij 服从两点分布，即 1ij jPp ， 0 1ij jPp （ 1） 其中 jp 的取值见表 1. 网 站通过问卷调查，得到 1,000 位会员愿意观看 5 种 DVD 的人数，根据这些统计数据，我们可以得到网站会员租赁这些 DVD 的概率（频率是概率的近似值）。 表 1 会员租赁 5 种 DVD 的概率 DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5 第 i 张 DVD 被租赁的概率
9、1 0.2p 2 0.1p 3 0.05p 4 0.025p 5 0.01p 设随机变量 100,0001j iji ， 1,2, ,j 5 ，即 j 表示 100,000 个会员中租赁第 j张 DVD 的总数，由于 ij （ 1, 2, ,100, 000i ）之间相对独立，也就是会员 之间第 5 页 共 15 页 是否租赁该张 DVD 是相互独立的，因而 j 服从二项分布，即： 1 0 0 , 0 0 01 0 0 , 0 0 0 C ( ) ( 1 ) , 1 , 2 , , 5k k kj j jP k p p j （ 2） 同时可以得到： ( ) 1 0 0 , 0 0 0 , 1
10、, 2 , , 5jjE p j （ 3） ( ) 1 0 0 , 0 0 0 (1 ) , 1 , 2 , , 5j j jD p p j （ 4） 由于租赁的人数是随机的，因而为了满足至少 50%的租赁会员看到 DVD，网站应该准备的 DVD 的数量也是随机的，为此我们以它的数学期望为应该准备的DVD 的数量，即： 1( 5 0 % ) ( ) 5 0 , 0 0 0 , 1 , 2 , , 52j j jE E p j （ 5） 如果以 (50% )jE 为该种 DVD 的准备量，则我们可以得到满足至少 50%的人看到该 DVD 的概率为： 15 0 % ( )2jjPE 1 ( ) (
11、 5 0 % )5 0 % ( 5 0 % )2( 5 0 % ) ( 5 0 % )jjjjjjEEEP DD 150% ( )2 0( 50% )jjjEp D(0) 12 (6) 其中约等式是由 D e M oivre-Laplace中心极限定理得到。 为了提高满足至少 50%的人看到该片的可靠度，我们需要改变提供的数量。设可以保证至少 50%的人看到该片的可靠度为 99%，即 ( ) 99%t ，由此可以得到 2.33t ，即 : 5 0 % ( 5 0 % ) 2 . 3 3 9 9 %( 5 0 % )jjjEPD（ 7） 50 % ( 50 % ) 2. 33 ( 50 % )j
12、 j jED 15 0 , 0 0 0 2 . 3 3 1 0 0 , 0 0 0 ( 1 )2j j jp p p （ 8） 第 6 页 共 15 页 同时，由于 60%的会员每个月会租赁 DVD 两次， 40%的会员每个月会租赁DVD 一次，所以租赁两次的会员会将第一次租赁的 DVD 归还，这样就可以满足其他会员的租赁要求，但是因为该张 DVD 是被会员在一个月内第一次租赁，还是被会员在第二次租赁的情况是随机的，所以我们假设上述这两种情况是等可能的，所以该张 DVD 可以被再次利用的期望值为： 116 0 % 0 3 0 %22 （ 9） 由此我们可以得出：只需要准备所需量的 70%就可以
13、满足 题目中的要求。 综上所述，我们以 99%的可靠度满足至少 50%的租赁会员能够看到某种DVD 所需要准备的该种 DVD 的数量为： 17 0 % 5 0 , 0 0 0 2 .3 3 1 0 0 , 0 0 0 ( 1 )2j j jp p p （ 10） 代入相关数据，我们可以得到为了保证至少 50%的人一个月内看到该 DVD，网站需要准备该 DVD 的张数（见表 2）。 表 2 网站 为了保证至少 50%的人一个月内看到该 DVD 需要准备的张数 名称 可靠度 张数 DVD1 DVD2 DVD3 DVD4 DVD5 50% 7,000 3,500 1,750 875 350 70%
14、7,024 3,518 1,763 885 356 80% 7,038 3,529 1,771 890 360 99% 7,104 3,578 1,807 916 375 为了保证在三个月内使得 95%的会员看到其所想要租赁的 DVD，只需要提供一个月内使得 95%的会员看到其想要租赁的 DVD 总量的 13 ，这是因为三个月内DVD 的流通量相当于一个月内 DVD 流通了三个周期的量。因而以 99的可靠度使得三个月内 95%的人看到该 DVD，网站应准备的张数为： 1 7 0 % 1 0 0 , 0 0 0 9 5 % 2 . 3 3 0 . 9 5 1 0 0 , 0 0 0 13 j j
15、 jp p p （ 11） 代入相关数据，我们可以得到为了保证至少 95%的人三个月内看到该 DVD，网站需要准备该 DVD 的张数（见表 3）。 表 3 网站 为了保证至少 95%的人三个月内看到该 DVD 需要准备的张数 名称 可靠度 张数 DVD1 DVD2 DVD3 DVD4 DVD5 50% 4,434 2,217 1,109 555 222 70% 4,449 2,228 1,117 560 226 80% 4,458 2,235 1,122 564 228 99% 4,499 2,266 1,144 580 238 2、 问题二模型的建立及求解： 设 1,0,ij ijx 表 示
16、 第 个 会 员 分 到 了 第 张 DVD表 示 第 个 会 员 没 有 分 到 第 张 DVD，则对会员的分配矩阵为： 第 7 页 共 15 页 1 ,1 1 , 2 1 ,1 0 0 11 ,1 1 ,1 2 ,1 0 0 21 0 0 0 ,1 1 0 0 0 , 2 1 0 0 0 ,1 0 0 1000x x x Xx x x XAx x x X （ 12） 其中 iX 为一维行向量，表示对第 i 个会员的 DVD 分配情况。 由题目中的表 2，我们可以得到会员对 DVD 的偏爱程度矩阵为： 1 ,1 1 , 2 1 ,1 0 0 11 ,1 1 ,1 2 ,1 0 0 21 0
17、0 0 ,1 1 0 0 0 , 2 1 0 0 0 ,1 0 0 1000a a a Ba a a BBa a a B （ 13） 其中 ija 表示第 i 个会员对第 j 张 DVD 的偏爱程度。 iB 为一维行向量，表示第 i 个会员对各类 DVD 的偏爱程度。 由于 ija 的数字越大，表示偏爱程度越小，同时会员得到该 DVD 的满意度越小 ，因而我们定义第 i 个会员对分配到第 j 张 DVD 的满意度为 ijb ，即 1 ,00 , 0ijijijijaaba （ 14） 则会员的满意度矩阵为 1 ,1 1 , 2 1 ,1 0 0 11 ,1 1 ,1 2 ,1 0 0 21 0
18、 0 0 ,1 1 0 0 0 , 2 1 0 0 0 ,1 0 0 1000b b b Cb b b CCb b b C (15)其中 iC 为一维行向量，表示第 i 个会员对分配到各类 DVD 的满意度。因而，第 i 个会员对分配方案 A 的满意度为： 1001Ti i ij ijjX C x b (16) 当第 i 个会员得到其偏爱程度为 1、 2 和 3 的 3 张 DVD 时，他是最满意的，其满意度为 1 1 111 2 3 6 ，由此可以得到第 i 个会员的标准化满意度为： 第 8 页 共 15 页 100100116 , 1 , 2 , , 1 0 0 01 1 1 1 1166
19、ij ijTjiiij ijjxbXCx b i (17) 为了使所有的会员获得最大的满意度，只要使他们的满意度和达到最大，由此可以得到目标函数为： 1 0 0 0 1 0 0116m a x 1 1 1 0 0 0 ij ijij xb (18) 在分配的过程中，每种 DVD 分配给会员的总数不超过网站准备的总数，即：10001 , 1, 2 , ,100ij ji x n j (19) 在一次分配中，每个会员获得 3 张 DVD；如果不够 3 张就视为分给该会员 0张 DVD， 即： 10010 3 , 1 , 2 , , 1 0 0 0ijj xi (20) 综合上述分析， 可以得到该问
20、题的模型为 ： 1 0 0 0 1 0 0116m a x 1 1, 0 0 0 ij ijij xb10001. . , 1 , 2 , , 1 0 0ij jis t x n j 10010 3 , 1 , 2 , , 1 0 0 0ijj xi 0 1 1 , 2 , ,1 0 0 0 1 , 2 , ,1 0 0ijx i j取 或 ， ， (21) 根据上述模型，我们使用 Lingo 软件进行求解，结果如下： 目标函数的最大值为 89.13； 没有得到 DVD 人数为 0； 得到 1 张 DVD 人数为 6； 得到 2 张 DVD 人数为 54； 得到 3 张 DVD 人数为 940
21、； 比率分别为 0% , 0.6% , 5.4% , 94% 。 表 4 前 30 位会员获得 DVD 的 情况 名称 客户 分配 用户获得的第 1 张 DVD (该张偏爱度 ) 用户获得的第 2 张 DVD (该张偏爱度 ) 用户获得的第 3 张 DVD (该张偏爱度 ) C0001 D008（ 1） D041（ 7） D098（ 3） 第 9 页 共 15 页 C0002 D006（ 1） D044（ 2） D062（ 4） C0003 D032（ 4） D050（ 2） D080（ 1） C0004 D007（ 1） D018（ 2） D041（ 3） C0005 D011（ 3） D0
22、66（ 1） D068（ 2） C0006 D019（ 1） D053（ 2） D066（ 4） C0007 D008（ 2） D026（ 3） D081（ 1） C0008 D031（ 4） D035（ 5） C0009 D053（ 1） D078（ 3） D100（ 2） C0010 D055（ 2） D060（ 1） D085（ 3） C0011 D059（ 1） D063（ 2） D066（ 4） C0012 D002（ 2） D031（ 1） D041（ 7） C0013 D021（ 3） D078（ 2） D096（ 1） C0014 D023（ 2） D052（ 1） D029（
23、 6） C0015 D013（ 1） D066（ 9） D085（ 3） C0016 D055（ 9） D084（ 1） D097（ 2） C0017 D047（ 2） D051（ 3） D067（ 1） C0018 D044（ 1） D060（ 2） D078（ 3） C0019 D066（ 4） D084（ 1） D086（ 2） C0020 D045（ 1） D061（ 3） D089（ 2） C0021 D045（ 2） D050（ 5） D053（ 1） C0022 D038（ 3） D055（ 2） D057（ 1） C0023 D029（ 2） D081（ 3） D095（ 1）
24、 C0024 D037（ 4） D041（ 2） D076（ 1） C0025 D009（ 1） D069（ 2） D081（ 4） C0026 D022（ 1） D068（ 2） D095（ 3） C0027 D050（ 4） D058（ 1） D078（ 7） C0028 D008（ 1） D034（ 2） C0029 D026（ 4） D030（ 2） D055（ 1） C0030 D037（ 2） D062（ 1） D098（ 5） 经计算，前 30 位会员的标准满意度为 92.0%，获得 3 张 DVD 的比率为 93.3%，也就是 93.3%的会员能够得到他想看的 DVD。 3、
25、问题三模型的建立以及求解： 为了利用题目中表 2 给出的数据，给出一种合理的购买方案，我们分两次完成购买方案。 第一阶段购买方案： 设 ,1 ,1 ,1 0 0( , , )i i i iY y y y 表示针对第 i 个会员的需求所选取的购买方案，则购买方案矩阵为 : 第 10 页 共 15 页 1 ,1 1 , 2 1 ,1 0 0 12 ,1 2 , 2 2 ,1 0 0 21 0 0 0 ,1 1 0 0 0 , 2 1 0 0 0 ,1 0 0 1000y y y Yy y y YDy y y Y (22) 其中 10ij ijy ， 表 示 针 对 第 个 会 员 购 买 第 张
26、DVD， 表 示 不 为 第 个 会 员 购 买 第 张 DVD。 因为有 60%的会员每月会租赁 DVD 两次，而另外 40%的会员每月只租赁一次，因此我们假设一个月会有两次订单，其中题目所给出的表 2 作为第一次订单，首先利用表 2 的数据给出第一阶段购买方案。在购买中，保证 95%的会员得到他想看的 DVD，即 95%的会员得到他订单中的 3 张，同时要使他们的满意度最大，另外网站希望购买的 DVD 张数越少越好，基 于上述要求，我们给出如下模型： 1 0 0 0 1 0 0111 0 0 0 1 0 011m in6m a x1 1, 0 0 0ijijij ijijyyb100110
27、01100110 00 10 0110 3 , 1 , 2 , , 10001 , 1 , 2 , , 1000. 2 , 1 , 2 , , 10001000 95% 30 1 1 , 2 , , 1000 1 , 2 , , 100ijjijjijjijijijyiyis t y iyy i j 取 或 ， ，(23) 由上述目标函数及约束条件可以看到，这个整数规划有多个解，这些解是从1000 个人中任取 950 人，对于 950 人中的每一个人选取其偏爱程度分别为 1， 2，3 的三张 DVD。最后统计一下每张 DVD 被 950 人选为偏爱程度为 1， 2， 3 的总数，则可得到该张
28、DVD 购买的数目。 第二阶段购买方案： 网站为了满足 95%的人的需求，根据 60%的人本月内的第二次租 赁订单，进行第二次购买。题中没有给出 60%的人第二次租赁的订单，我们将利用题目中的表 2，随机选取 600（ 1000 60% ）位会员的在线订单，作为第二次租赁订单。为了便于数学符号上的处理， 不失一般性，我们不妨选择 1000 会员中的前 600个会员的订单作为第二次订单。 因为这 600 个会员在第一阶段购买方案中已经满足了他们偏爱程度编号为 1， 2， 3 的 DVD 的需求，所以在第二次订单中他们偏爱程度编号为 1， 2， 3 的 DVD 的需求应记为 0（否则，因为目标函数
29、是满意度最大，所以最后得出的还是 偏爱程度编号为 1， 2， 3 的 DVD 的需求），则第二次订单中各会员相应的满意度为 ijd ， 第 11 页 共 15 页 ,00 , 1ij ijij ijbyd y (24) 其中 1,2, ,600i ， j 1,2, ,100 ，也就是说，如果第 i 个会员在第一次分配到第 j 张 DVD 时，则在第二次分配中，第 i 个会员对第 j 张 DVD 的满意度为 0。 设 ,1 , 2 ,1 0 0, , ,i i i iZ Z Z Z表示根据第二次租赁订单第 i 个人的需求网站采购DVD 碟片的方案。则第二次购买 DVD 碟片方案矩阵为： 1 ,1
30、 1 , 2 1 ,1 0 011 ,1 1 ,1 2 ,1 0 026 0 0 ,1 6 0 0 , 2 6 0 0 ,1 0 0600z z zZz z zZEz z zZ(25) 在第二次分配中，当第 i 个会员得到其偏爱程度 为 4、 5 和 6 的 3 张 DVD 时，他是最满意的，其满意度为 1 1 1 374 5 6 60 ，由此可以得到第 i 个会员的标准化满意度为： 1001001160 , 1 , 2 , , 6 0 037 3760ij ijjij ijjzdz d i (26) 为了使所有的会员获得比较大的满意度，只要使他们的满意度和达到最大，由此可以得到目标函数为： 6 0 0 1 0 0 6 0 0 1 0 01 1 1 16 0 1m a x m a x3 7 6 0 0 3 7 0ij ij ij iji j i jz d z d (27) 网站在第二次确定购买方案时，一方面需要考虑第一步采购时所有的相关问题，同时 还需要考虑第一次租赁后还回来的 DVD 的再次利用，因而可以得到如下模型： 6 0 0 1 0 0116 0 0 1 0 011m in1m a x370ijijij ijijzzd.st 10010 3 , 1 , 2 , , 6 0 0ijj zi 1001 1, 1, 2 , , 6 0 0ijj zi
