1、1DVD 在线租赁的优化模型摘要本文主要讨论网络 DVD 在线租赁问题。我们把会员分成二类：I 类会员(每月租赁DVD 一次的会员)和 II 类会员(每月租赁 DVD 二次的会员)。对问题 1，我们建立了优化模型：取 m=1，u%=50%，得到问题 1 第一部分的模型，求得结果为：DVD1-DVD5 的总数量为：12033 取 m=3，u%=95%，得到问题一第二部分的结果为：DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5最小数量 4498 2249 1125 563 225DVD1-DVD5 的总数量为：8660对问题 2，首先将偏好度转化为满意度，数字越大，满意度越大。在此
2、基础上，给出了全体会员对网站的满意度的定义，建立了 DVD 分配的整数规划模型，并利用 lingo进行求解。若我们特别注重满足会员订单中的前几张 DVD，则得到前 30 位会员的分配方案（见表 6） ，总满意度为 24746。若我们侧重提供给会员的 DVD，都是订单中的 DVD，得到前 30 位会员的分配方案（见表 7） 。另外，结合整体优化及个人满意度相结合，给出了多目标规划模型，并利用多层序列法将多目标规划转化为单目标规划进行求解。对问题 3，我们给出了通用模型及算法，对题中所给数据，得到了只购进 3000 张DVD 且这 3000 张 DVD 正好在第一次分配中使每个会员均获得他们偏爱程
3、度最高的 3 张DVD。对问题 4，我们对模型进行了评价及推广，并就如何提高网站方所拥有的 DVD 的利用率等因素进行了考虑，提出了许多合理化建议，并建议从动态方面考虑，建立了相应的动态优化模型。对于问题 1-3 中大量的数据，我们充分利用计算机的数值计算能力，对各种问题进行了求解。DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5最小数量 6250 3125 1563 782 313jmiijAuqtsj .ni2一、问题重述随着信息时代的到来，许多网站面向其会员群提供日益专业化和便捷化的服务。例如，DVD 在线租赁就是一种可行的服务。考虑如下的在线 DVD 租赁问题。顾客缴纳一
4、定数量的月费成为会员，订购 DVD 租赁服务。会员对哪些 DVD 有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的。网站会根据手头现有的 DVD 数量和会员的订单进行分发。每个会员每个月租赁次数不得超过 2 次，每次获得 3 张 DVD。会员看完 3 张 DVD 之后，只需要将 DVD 放进网站提供的信封里寄回（邮费由网站承担） ，就可以继续下次租赁。请考虑以下问题：1）网站正准备购买一些新的 DVD，通过问卷调查 1000 个会员，得到了愿意观看这些DVD 的人数（表 1 给出了其中 5 种 DVD 的数据）
5、 。此外，历史数据显示，60%的会员每月租赁 DVD 两次，而另外的 40%只租一次。假设网站现有 10 万个会员，对表 1 中的每种 DVD 来说，应该至少准备多少张，才能保证希望看到该 DVD 的会员中至少 50%在一个月内能够看到该 DVD？如果要求保证在三个月内至少 95%的会员能够看到该 DVD呢？2）表 2 中列出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会员的在线订单，如何对这些 DVD 进行分配，才能使会员获得最大的满意度？请具体列出前30 位会员（即 C0001C0030）分别获得哪些 DVD。3）继续考虑表 2，并假设表 2 中 DVD 的现有
6、数量全部为 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 D
7、VD 现有数量 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 个会员, 会员的在线订单用数字 1,2,表示，数字越小表示会员的偏爱程度越高，数字 0 表示对应的 DVD 当前不在会员的在线订单中。3二、模型的假设1、对于每张 DVD，每个会员最多租赁一次。2、所有 DVD ，在邮寄和使用过程中没有损坏。3、会员群没有发生改变。4、对于订单中出现的 DVD，网站方会毫不保留地把 DVD 寄给会员；如果网站方
8、拥有的DVD 不能满足会员的需求，网站方按照偏爱程度越高优先的原则，把 DVD 分配给会员；如果会员对同一 DVD 的偏爱程度相同，则网站方将随机分配。5、每月租赁 DVD 一次的会员在月初（每月 1 号）在线提交 DVD 订单 ，每月租赁 DVD两次的会员在月初（每月 1 号）和月中（15 号）在线提交 DVD 订单，会员提交订单后，网站方立即可以收到订单 。6、网站方只在 1 号和 15 号给会员分发 DVD，会员每次获得 3 张 DVD；每月租赁 DVD 一次的会员在当月下旬寄回 DVD；每月租赁 DVD 两次的会员必须在当月 15 号前寄回第一次租的 3 张 DVD，然后再进行第二次租
9、赁 。7、问卷调查中的 1000 个会员是从 10 万个会员中随机抽取的，从而 10 万个会员对各种 DVD 的需求比例与 1000 个会员对 DVD 的需求比例相同。8、每月租赁 DVD 两次的会员在每月第二次租赁时，对 DVD 的偏爱程度与当月第一次无变化。9、会员只要在线提交订单，且满足这次租赁条件，则均可获得 3 张 DVD。三、符号约定及说明I 类会员：每月租赁 DVD 一次的会员。II 类会员：每月租赁 DVD 二次的会员。D001D100 表示 100 种 DVD，C0001C1000 表示 1000 个会员。： 10 万会员中愿意观看第 j 种 DVD 的会员数。jA：第 个月
10、愿意观看第 种 DVD 的会员数。ij： 第 个月愿意观看第 种 DVD 的第 II 类会员数。ijaij： 第 j 种 DVD 的数量。jn： 第 个月租到第 种 DVD 的会员数。ijqij： 第 个会员对第 种 DVD 的满意程度。ijc4四、问题 1 的建模及求解（一） 、问题分析与模型建立根据假设，I 类会员（每月只租一次的会员）在每月 1 号在线提交 DVD 订单 ，II类会员（每月租二次的会员）在每月 1 号和 15 号在线提交 DVD 订单，网站方只在 1 号和 15 号给会员分发 DVD；I 类会员在当月下旬寄回 DVD；II 类会员必须在当月 15 号前寄回第一次租的 3
11、张 DVD，然后再进行第二次租赁 。由于 I 类会员在当月不进行第二次租赁，所以，网站方在每月 15 号只分发 DVD 给 II 类会员。（1）根据假设，10 万会员中愿意观看第 种的总人数 如下表：j jA表 3 10 万个会员按 1000 个会员的比例所得的部分结果1A23A4520000 10000 5000 2500 1000其中 ： 10 万会员中愿意观看第 j 种 DVD 的会员数。j（2） 记 ：第 个月愿意观看第 种 DVD 的会员数。ijA： 第 个月租到第 种 DVD 的会员数。ijqj： 第 j 种 DVD 的数量。jn(i)当 时，则 为ijAjijq,ijA(ii)当
12、 时，则 等于 其中 表示第 i 个月ijjnij ),min(ijjijjj Aanaij愿意观看 DVDj 的会员中，II 类会员所占的比例， 表示月初分给第 i 个月愿ijj意观看 DVDj 的 II 类会员的 DVDj 的数量， 表示第 i 个月愿意观看 DVDjijjijAan的 II 类会员在月初第一次分配 DVDj 后，所剩下的 II 类会员的人数。即 jijij jijijjijjjij nAAananq , ),m(（3） 第一个月愿意观看第 j 种 DVD 的人数 ; jj1第 i 个月愿意观看第 j 种 DVD 的人数 即12.i,iljjijq52,11iqAiljjj
13、ij（4）由于 I 类会员占 40%，II 类会员占 60%， 所以第一个月愿意观看第 j 种 DVD 的II 类会员数；%601aj第 i 个月愿意观看第 j 种 DVD 的 II 类会员数.2),min( 1()1()()1()1( iAanAaAjijjijijjijiij即 a ijiAjiAAjinjii ajij 2 ),1(a jn-1)(ia,(ji-)1()( ,60（5）问题 1 的约束条件为：前 m 个月内， 可以DVjuDVj 的 会 员 可 以 看 到的 会 员 中 ， 至 少 有在 想 看 到 %表示为： jijAuq1%问题 1 的目标函数为： nmij通过以上分
14、析，问题 1 归结为求解如下数学模型：6模型一： jn mi NAaqnji AanaAniiqAnAananqAujiji jijjijijjijijijiljjjij jij jijjijjjij jij, 2i ),m(1 %,602 , ),(%1()1()()1()1(1 ijij15,4321j显然，当 时，希望看到 DVDj 的会员 100都能看到 DVDj。jijnA1、问题 1 的第一部分，即在模型一中，取 m=1,u%=50，此时模型简化为jmits. NA ,a ,qn ,%60),i(50j1jj1jj111 1Anqjj AajjAajjjjj jj5432j解上面的
15、模型得：s.t7表 4DVD1DVD5 的总数量为：120332、问题 1 的第二部分，即在模型一中，取 m=3,u%=95，此时模型转化为：jnmi .ts NAaqnji AanAaniiqAAananqAjiji jijjijijjijijijiljjjij ijjijjjij jij, 2i ),m(1 %,602 , ),i(%95 1()1()()1()1(131用 VC 语言编程得：表 5DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5要满足要求，需要准备的数目 4498 2249 1125 563 225DVD1DVD5 的总数量为：8660五、问题 2 的建模及
16、求解DVD 名称 DVD1 DVD2 DVD3 DVD4 DVD5要满足要求，需要准备的数目 6250 3125 1563 782 3138问题要求针对网站手上 100 种的现有张数和当前需要处理的 1000 位会员的在线订单，对进行分配，使会员获得最大的满意度。会员对的满意度求解：首先，我们将偏好度转化为满意度，数字越大，满意度越大。由于题中数字越小表示会员的偏好程度越高。而会员的偏好程度越高，满意度亦越高。我们对数字进行如下处理：数字 0 不变，因为数字 0 表示对应的 DVD 当前不在会员的在线订单中，因此满意度也为0；其余大于 0 的数字均用数字 11 来减它们，即 1 变成 10，2
17、 变成 9，9 变成2，10 变成 1。模型二：我们将每个会员对所租到的张的满意度和相加作为整体会员对网站的满意度：数值越大，满意度越大。因此得目标函数 ，其中10maxijijcxZ8 DVjixij 种个 会 员 没 有 租 到 第第 种个 会 员 租 到 第第,01且要满足如下约束条件：（1） 、每位会员一次获得张 DVD，即 ；103jix（） 、每种 DVD 租出的数目不得超过的现存数量，即 10ijjnx综上，我们得如下 01 整数规划模型：maxZ= ijijcx1ts.0 ,1310ijjijjixn用 lingo 求解，得出前 30 位会员（即 C0001C0030）获得 D
18、VD 种类如下表所示：表 6所获 DVD 及偏爱程度1 2 3会员编号 DVD 编号 偏爱程 度 DVD 编号 偏爱程 度 DVD 编号 偏爱程 度 满意度C0001 008 1 041 7 098 3 0229C0002 006 1 044 2 062 4 026C0003 032 4 050 2 080 1 026C0004 007 1 018 2 041 3 027C0005 011 3 066 1 068 2 027C0006 019 1 053 2 066 4 026C007 026 3 066 6 081 1 023C008 031 4 035 5 071 1 023C009 05
19、3 1 078 3 100 2 027C010 041 6 055 2 085 3 022C011 059 1 063 2 066 4 026C012 002 2 031 1 041 7 023C013 021 3 078 2 096 1 027C014 023 2 052 1 089 6 024C015 013 1 052 4 085 3 025C016 010 4 084 1 097 2 026C017 047 2 051 3 067 1 027C018 041 1 060 2 078 3 027C019 066 4 084 1 086 2 026C020 045 1 061 3 089
20、2 027C021 045 2 050 5 053 1 025C022 038 3 055 2 057 1 027C023 029 2 081 3 095 1 027C024 037 4 041 2 076 1 026C025 009 1 069 2 094 3 027C026 022 1 068 2 095 3 027C027 050 4 058 1 078 7 021C028 008 1 034 2 037 0 019C029 026 4 030 2 055 1 026C030 037 2 062 1 098 5 025总满意度为：24746从表 6 中数据可发现，虽然 C028 所获三张
21、 DVD 中有一张 DVD 偏爱程度为 0，即对应的 DVD 当前不在会员的在线订单中，但可发现另两张 DVD 均为该会员偏爱程度最高的，因此，我们认为其分配方案是合理的。如要求尽可能使分配方案中，满意程度为 0 的数据少，同样用 lingo 求解，得出前 30个会员获得 DVD 种类如下表所示：表 7所获 DVD 及偏爱程度1 2 3会员编号 DVD 编号 偏爱程 度 DVD 编号 偏爱程 度 DVD 编号 偏爱程 度 满意度10C0001 008 1 041 7 098 3 022C0002 006 1 044 2 062 4 026C0003 032 4 050 2 080 1 026C
22、0004 007 1 018 2 041 3 027C0005 011 3 066 1 068 2 027C0006 019 1 053 2 066 4 026C0007 026 3 066 6 081 1 023C0008 031 4 035 5 071 1 023C0009 053 1 078 3 100 2 027C0010 041 6 055 2 085 3 022C0011 059 1 063 2 066 4 026C0012 002 2 031 1 041 7 023C0013 021 3 078 2 096 1 027C0014 023 2 052 1 089 6 024C001
23、5 013 1 052 4 085 3 025C0016 010 4 084 1 097 2 026C0017 047 2 051 3 067 1 027C0018 041 1 060 2 078 3 027C0019 066 4 084 1 086 2 026C0020 045 1 061 3 089 2 027C0021 045 2 050 5 053 1 025C0022 038 3 055 2 057 1 027C0023 029 2 081 3 095 1 027C0024 037 4 041 2 076 1 026C0025 009 1 069 2 094 3 027C0026 0
24、22 1 068 2 095 3 027C0027 050 4 058 1 078 7 021C0028 008 1 034 2 082 3 027C0029 026 4 030 2 055 1 026C0030 037 2 062 1 098 5 025从表中数据可发现，除 C028 会员所获 DVD 发生变化外，其余会员数据均未发生变化。此时，虽然前 30 个会员中没选择满意程度为 0 的数据，且前 30 个会员满意度比表 6 中情况下满意度要高，但对整体来说（1000 个会员） ，满意度值下降。模型三：模型二是从整体优化考虑使所有会员满意程度之和最大，没有针对每个会员的满意度进行考虑。当出现如下情况时，如某个会员对所租到的 3 张 DVD 满意度取（10，8，6）或（9，8，7）时，应怎样确定哪种方案好呢？括号内数字表示该会员对所租三张 DVD 的满意度。一般地，虽然（10，8，6）和（9，8，7）满意度总和相等，但如果会员偏重于考虑租到 DVD 中满意度最高的那张 DVD，则认为（10，8，6）比（9，8，7）要好。故在此，我们加入第二
