1、- 1 -DVD 在线租赁方案的优化模型摘 要本文对 DVD 在线租赁的需求预测、购买与分配等相关问题，进行合理的简化假设，得到该问题的数学模型.对于 DVD 张数问题，根据需求预测表（题中表 1） ，计算租赁周期上、下限的平均值，应用图论知识，利用会员对 DVD 的偏好程度建立二部图和图论度的计算得出对应不同平均租赁周期的 DVD 数量结果.针对 DVD 的现有张数和订单数，给出了权重矩阵和满意度函数，建立以最大整体满意度为单目标的 0-1 整数规划模型，利用 Lingo8.0 软件中的ole 函数从 Excel 中读取权重系数矩阵，求解出最大整体满意度 和其分配方案.利用在线订单，以最大整
2、体满意度和最小购买量为多目41标的 0-1 整数规划模型，通过线性加权法化多目标为单目标规划，利用 Lingo8.0 软件求解出当 时，其最大整体满意度分别为 980.48，1000，978.3，1000，0,582其最小购买量分别为 981，1475，1805，2085.从网站角度考虑，分析需求预测、购买分配中联系的参变量，确定了几个值得研究的问题，提出并建立了以网站最大收益和最大整体满意度为多目标的规划模型.关键词：0-1 整数规划；租赁周期；满意度- 2 -1 问题的提出考虑如下的在线 DVD 租赁问题.顾客缴纳一定数量的月费成为会员，订购 DVD租赁服务.会员只要在线提交订单，网站就会
3、通过快递的方式尽可能满足要求.会员提交的订单包括多张 DVD，这些 DVD 是基于其偏爱程度排序的.网站会根据现有的DVD 数量和会员的订单进行分发. 请考虑以下问题：1）通过问卷调查 1000 个会员，得到了愿意观看这些 DVD 的人数.假设网站现有 10 万个会员，对其中 5 种 DVD 来说，应该至少准备多少张，才能保证希望看到该 DVD的会员中至少 50%在一个月内能够看到该 DVD？如果要求保证在三个月内至少 95%的会员能够看到该 DVD？2）如今给出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会员的在线订单，如何对这些 DVD 进行分配，才能使会员获得
4、最大的满意度？请具体列出前30 位会员（即 C0001C0030）分别获得哪些 DVD.3） 如果你是网站经营管理人员，你如何决定每种 DVD 的购买量，以及如何对这些DVD进行分配，才能使一个月内 95%的会员得到他想看的 DVD，并且满意度最大？4）如果你是网站经营管理人员，你觉得在 DVD 的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型.2 基本假设与符号约定2.1 基本假设2.1.1 网站在不太长的时间内会员人数没有太大的变化,网站每月的月费收入基本保持不变；2.1.2 不同电影的 DVD 的价格相差不大，视作相等；2.1.3 网站用速递
5、方式将 DVD 送交给会员，以及会员将 DVD 邮寄给网站的时间都很短，视为即日到达.邮寄每次都是三只 DVD，而且邮费都是一定的；2.1.4 允许网站不对部分订单作处理；2.1.5 每个会员每个月租赁次数不得超过 2 次，每次获得 3 张 DVD.会员看完 3 张DVD 之后，只需要将 DVD 放进网站提供的信封里寄回（邮费由网站承担） ，就可以继续下次租赁；2.1.6 60%的会员每月租赁 DVD 两次，而另外的 40%只租一次.2.2 符号约定：会员总数，其中在问题一中， 万；在问题二、三中， ；m10m10m：DVD 种数，其中在问题一中， ；在问题二、三中， ；n 5nn：会员租借
6、DVD 的平均租赁周期；：DVDj 的现有张数， ；jd,j：DVDj 在会员 的定单中的偏好程度， ， ；ijaiC1,i 1,jn：会员 对 DVDj 的权重系数， ， ；ijbi ,im j：对于网站的分配方案,会员 的满意度， ；ii ,i- 3 -：所有会员对网站分配方案的总满意度.3 DVD 数量的图论模型3.1 平均周期的上、下限会员 租 DVD 一次（含看及周转 DVD）的时间称为租赁周期 ，而 个会员的iC im平均租赁周期为 .一般情况下，一个月内租 DVD 一次的会员当中，最小租赁周期为15 天，最大租赁周期为 30 天；一个月内租 DVD 两次的会员当中，最小租赁周期为
7、 5天，最大租赁周期为 15 天.根据上面所述及假设 2.1.6 可得平均周期上、下限.计算其平均值（数学期望） ，有： inf50.61.49天sup32天于是 9,13.2 图论模型令 为会员集合，12,mC为不同 DVD 集合.YnD以 为顶点集，若会员 愿意观看 ，则连一条边，则得到一个图（二部图）XiCjD,G- 4 -1C234C1D234DnDXY mC,G易知： 中每个顶点的度 ， ， ， ，Y120dD210d350d254d. 的度与 的度相等， ， ，即105DdiCj mi, nj,11mnijijdC是一个简单二部图或偶图.X,YG3.3 模型的转化及求解1）设 DV
8、D 应准备的张数为 ；iDin2）用 表示会员一个月租 DVD 的张数（不同） ， 或 ，它是一个随机变量； 36由假设 3 及“每次获得 3 张 DVD”知 ， ；0.4P0.P3）试在 中找一个生成二部子图 ， （满足 或 6）.X,YGX,YH3idC3.4 DVD 数量 的计算in1）一个月 50%的满足： 30.5iindD的结果为：90123平均租赁期 9 10 11 12 13- 5 -DVD1 3001 3334 3667 4001 4334DVD2 1500 1667 1834 2000 2167DVD3 751 834 917 1000 1084DVD4 376 417 4
9、59 501 542DVD5 150 167 184 200 217由上表可知，当平均租赁期为 9 天时，所需的五种 DVD 数量最少.2）三个月 95%的满足： 0.5iindD的结果为：90123平均租赁期 9 10 11 12 13DVD1 1901 2112 2323 2534 2745DVD2 951 1056 1162 1267 1373DVD3 476 528 581 634 687DVD4 238 264 291 317 344DVD5 96 106 117 127 138由上表可知，当平均租赁期为 9 天时，所需的五种 DVD 数量也最少.4 DVD 分配方案模型4.1 矩阵
10、表示由题目的在线订单数据表，可得到 DVD 的现有数量矩阵40,2,1,021 dD设 表示会员 在 100 种 DVD 中选择了 种，从数据表得知 有三ijjiam10xiCimim个取值 8，9，10.我们知道，会员的在线订单用数字 1,2,表示，数字越小表示会员的偏爱程度越高，即数字 1 表示会员对于对应 DVD 的偏爱程度最高，数字 2,3,., 表示其偏爱程度逐渐i下降.把会员的偏爱程度进行量化：对于每一个 ，当会员 在 100 种 DVD 中选择了iiC种时，定义分段函数im0,0,1ijijiij amb其中 表示会员 对 的偏爱权重系数.ijbiCjDV可以建立选择权重矩阵 1
11、0ijbB- 6 -= 10706004 4.2 满意度函数由于每个会员每个月租赁次数不得超过 2 次，每次获得 3 张 DVD.不妨假设会员获得其偏爱权重前三位的 DVD 时，会员的满意度就达到 100%.而满意度为 100%时，我们不妨假设此时满意度为 1 .考虑问题二中要处理的租赁，令 否 则， 且一 张租 给 会 员若,0 0DVj ijiij aCx于是，可以定义会员 的满意度为iC13211010 ijijiiijiji mxbmxb所有会员的整体满意度为 10i问题二要求对 100 种 DVD 进行分配，使得会员获得最大的满意度，即要使 达到最大值. 4.3 DVD 数量模型在分
12、配方案中每种 DVD 租赁出去的总张数不应超过其现有数量（对应模型的式（2） ）即 DVD 现有数量的约束.而在当前 DVD 在线订单中，每个会员只能获得 3 张DVD（对应模型的式（3） ）.而 是一个决策变量,当 =0 时说明了编号为 j 的 DVDijxijx没有租赁给会员 .iC根据上面模型的分析，我们以整体满意度为目标函数的单目标规划，建立 0-1 整数规划模型如下：模型： 101max 13ijjiibxm - 7 -101.,2,1023, 30 4ijjijijstxdx 或4.4 模型的求解及结果在模型的求解过程中，利用 Lingo8.0 软件中的ole 函数直接将权重系数矩
13、阵（1000 100） （此权重系数矩阵是电子表格的格式）输入到内存，通过max 函数编程求解 10 万个决策变量的线性规划模型（程序段见附录 1） ，可得局部最优解如下表所示（列出会员编号为 C0001C0030 的个人满意度和分配方案）：会员编号 个人满意度 分配到的 DVD的编号 会员编号 个人满意度 分配到的 DVD的编号C0001 0.79167 8 41 98 C0016 0.96296 10 84 97C0002 0.96296 6 44 62 C0017 1 47 51 67C0003 0.95238 32 50 80 C0018 1 41 60 78C0004 1 7 18
14、41 C0019 0.88889 66 67 86C0005 1 11 66 68 C0020 1 45 61 89C0006 0.96296 19 53 66 C0021 0.92593 45 50 53C0007 0.83333 26 66 81 C0022 1 38 55 57C0008 0.48148 26 31 35 C0023 1 29 81 95C0009 1 53 78 100 C0024 0.96296 37 41 76C0010 0.81481 41 55 85 C0025 0.96296 9 69 81C0011 0.95833 59 63 66 C0026 1 22 6
15、8 95C0012 0.85185 2 31 41 C0027 0.77778 50 58 78C0013 1 21 78 96 C0028 1 8 34 82C0014 0.88889 23 52 89 C0029 0.96296 26 30 55C0015 0.74074 13 66 85 C0030 0.92593 37 62 98在此种方案中，计算出 1000 个会员的总满意度为： .9455 DVD 购买量与分配方案模型5.1 数学模型问题三要求站在网站角度考虑，如何购进最少 DVD 同时获得要求最大的满意度.与问题二模型相似，在满足最大整体满意度和最小均衡满意度的基础上，继而考虑D
16、VD 的购买量要尽量小.于是，建立以整体满意度（即模型中的式（5） ）和购买量（即模型中的式（6） ）为三目标函数的 0-1 整数规划模型.下面讨论问题三的约束条件：1）分配方案中 DVD 数量的约束：在此分配方案中，要使 95%的会员得到他想看的DVD，即对于分配方案中的每一种 DVD，其人数百分比都应在 95%以上（对应模型的式（7） ） ；2）会员租赁 DVD 数量的约束：在当前 DVD 在线订单中，每个会员只能获得 3张 DVD（对应模型的式（8） ）.设 ：购进 DVDj 的张数.jy- 8 -建立模型如下所示:模型： 10101max 53in 6ijjiijbxmQy 101.9
17、5%3,2,7,2,080 9ij jijijjjstxxy 或 Z5.2 模型的转化、求解及结果在模型的求解过程中，我们通过线性加权法化双目标为单目标规划,其中 ，简化后模型如下： 1010max()3ijj jiibxZym101.95%,2,2,100ij jijijjjstxy或 Z这是一个 0-1 整数规划模型，利用 Lingo8.0 软件中的ole 函数直接将权重系数矩阵（1000 100） （此权重系数矩阵是电子表格的格式）输入到内存，通过max 函数编程求解，得出局部最优解如下所示：当平均租赁周期为 10 天时，所需 DVD 个数有 981 个.其中每种 DVD 个数分别如下表
18、所示：- 9 -下面列出前三十名会员的满意度和分配方案：会员编号 个人满意度 分配到的 DVD 编号 会员编号 个人满意度 分配到的 DVD 编号c0001 0.375 4 8 16 c0016 1 6 84 97c0002 1 6 42 44 c0017 1 47 51 67c0003 1 4 50 80 c0018 1 41 60 78c0004 1 7 18 41 c0019 1 67 84 86c0005 1 11 66 68 c0020 1 45 61 89c0006 1 16 19 53 c0021 0.7037 3 45 53c0007 1 8 26 81 c0022 1 38
19、55 57c0008 1 15 71 99 c0023 1 29 81 95c0009 1 53 78 100 c0024 1 41 76 79c0010 1 55 60 85 c0025 1 9 69 94c0011 1 19 59 63 c0026 1 22 68 95c0012 1 2 7 31 c0027 1 22 42 58c0013 1 21 78 96 c0028 1 8 34 82c0014 0.7037 2 23 52 c0029 1 30 44 55c0015 0.7037 2 13 88 c0030 1 1 37 62平均租赁周期为：10，总满意度为 980.48.当平均
20、租借周期为 15 天时，所需 DVD 个数有 1475 个.其中每种 DVD 个数分别如下表所示：DVD 编号 D001 D002 D003 D004 D005 D006 D007 D008 D009 D010DVD 张数 12 12 9 13 7 9 10 11 11 8DVD 编号 D011 D012 D013 D014 D015 D016 D017 D018 D019 D020DVD 张数 10 10 9 10 9 12 9 9 10 12DVD 编号 D021 D022 D023 D024 D025 D026 D027 D028 D029 D030DVD 张数 11 9 12 7 9
21、10 8 6 8 13DVD 编号 D031 D032 D033 D034 D035 D036 D037 D038 D039 D040DVD 张数 10 11 10 10 13 11 7 10 10 9DVD 编号 D041 D042 D043 D044 D045 D046 D047 D048 D049 D050DVD 张数 17 12 9 11 11 8 10 8 10 11DVD 编号 D051 D052 D053 D054 D055 D056 D057 D058 D059 D060DVD 张数 13 9 11 9 10 11 10 9 11 12DVD 编号 D061 D062 D063
22、 D064 D065 D066 D067 D068 D069 D070DVD 张数 9 10 10 11 10 10 10 11 11 10DVD 编号 D071 D072 D0730 D074 D075 D076 D077 D078 D079 D080DVD 张数 12 11 8 10 9 8 7 10 10 9DVD 编号 D081 D082 D083 D084 D085 D086 D087 D088 D089 D090DVD 张数 9 6 7 6 11 7 11 8 8 9DVD 编号 D091 D092 D093 D094 D095 D096 D097 D098 D099 D100DV
23、D 张数 12 9 8 7 13 8 11 10 6 11- 10 -下面列出前三十名会员的满意度和分配方案：会员编号 个人满意度 分配到的 DVD 编号 会员编号 个人满意度 分配到的 DVD 编号c0001 1 8 82 98 c0016 1 6 84 97c0002 1 6 42 44 c0017 1 47 51 67c0003 1 4 50 80 c0018 1 41 60 78c0004 1 7 18 41 c0019 1 67 84 86c0005 1 11 66 68 c0020 1 45 61 89c0006 1 16 19 53 c0021 1 45 53 65c0007 1
24、 8 26 81 c0022 1 38 55 57c0008 1 15 71 99 c0023 1 29 81 95c0009 1 53 78 100 c0024 1 41 76 79c0010 1 55 60 85 c0025 1 9 69 94c0011 1 19 59 63 c0026 1 22 68 95c0012 1 2 7 31 c0027 1 22 42 58c0013 1 21 78 96 c0028 1 8 34 82c0014 1 23 43 52 c0029 1 30 44 55c0015 1 13 85 88 c0030 1 1 37 62平均租赁周期为：15，总满意度
25、为 1000 .当租借周期为 18 天时，所需 DVD 个数有 1805 个.其中每种 DVD 个数分别如下表所示：DVD 编号 D001 D002 D003 D004 D005 D006 D007 D008 D009 D010DVD 张数 10 18 13 19 10 14 15 16 17 12DVD 编号 D011 D012 D013 D014 D015 D016 D017 D018 D019 D020DVD 张数 14 15 14 15 13 19 14 13 15 19DVD 编号 D021 D022 D023 D024 D025 D026 D027 D028 D029 D030DV
26、D 张数 19 14 13 15 19 15 13 10 12 20DVD 编号 D031 D032 D033 D034 D035 D036 D037 D038 D039 D040DVD 张数 14 17 15 15 19 17 10 15 14 14DVD 编号 D041 D042 D043 D044 D045 D046 D047 D048 D049 D050DVD 张数 26 17 13 17 17 12 16 12 16 17DVD 编号 D051 D052 D053 D054 D055 D056 D057 D058 D059 D060DVD 张数 19 13 16 13 15 16 1
27、5 14 17 18DVD 编号 D061 D062 D063 D064 D065 D066 D067 D068 D069 D070DVD 张数 16 15 14 17 18 15 15 17 16 15DVD 编号 D071 D072 D0730 D074 D075 D076 D077 D078 D079 D080DVD 张数 18 17 12 15 14 12 10 15 15 14DVD 编号 D081 D082 D083 D084 D085 D086 D087 D088 D089 D090DVD 张数 14 9 11 10 16 10 17 12 12 13DVD 编号 D091 D092 D093 D094 D095 D096 D097 D098 D099 D100DVD 张数 19 14 12 11 19 12 18 16 9 17
