DVD在线租赁问题（课堂PPT）

1、主讲教师：董庆来主讲教师：董庆来20122012年年8 8月月9 9日日20122012年数学建模竞赛暑期集训年数学建模竞赛暑期集训系列讲座之一系列讲座之一DVDDVD在线租赁在线租赁CUMCM-2005B: DVDCUMCM-2005B: DVD在线租赁在线租赁命题人：余刚先生（教授）命题人：余刚先生（教授）l时任亚马逊公司全球供应链运营副总裁时任亚马逊公司全球供应链运营副总裁l曾任美国德州大学奥斯汀分校管理学院曾任美国德州大学奥斯汀分校管理学院Jack G. Taylor讲席教授讲席教授l获多项美国专利，获多项美国专利，1995年创建美国科莱科技公司年创建美国科莱科技公司(CALEBTec

2、hnologiesCorp.)并任董事长和总裁并任董事长和总裁l航班管理：航班管理：2001年为美国大陆航空公司所创造的价年为美国大陆航空公司所创造的价值超过值超过6000万美元，获万美元，获2002年运筹学与管理科学应用年运筹学与管理科学应用Franz Edelman奖奖(运筹学与管理科学应用的运筹学与管理科学应用的“世界世界杯杯”)CUMCM-2005B: DVDCUMCM-2005B: DVD在线租赁在线租赁网上网上DVD在线租赁业务（在线租赁业务（2005年时的背景）年时的背景）l亚马逊英国公司亚马逊英国公司(amazon.co.uk) ；美国；美国和和等；欧洲等；欧洲等著名公司等著名

3、公司l租赁的租赁的DVD多达几万种，用户多达几十万多达几万种，用户多达几十万几百万，几百万，有的包括多个配送中心有的包括多个配送中心l题目：会员每月最多可租赁两次，每次张题目：会员每月最多可租赁两次，每次张DVDl第（第（1）、（）、（2）问：分别考虑购买和分发子问题）问：分别考虑购买和分发子问题l第（第（3）问：同时考虑购买和分发）问：同时考虑购买和分发l第（第（4）问：自己提出新问题，尝试建模和求解）问：自己提出新问题，尝试建模和求解 二、问题分析与建模 问题一问题一 网站购买网站购买DVDDVD的最优数量的最优数量在现有会员中随机抽取在现有会员中随机抽取10001000个会员进行调查，以

4、得知愿意观看不同个会员进行调查，以得知愿意观看不同DVDDVD的的人数（表人数（表1.11.1给出了其中给出了其中5 5种种DVDDVD的数据）。从历史数据显示，的数据）。从历史数据显示，60%60%的会员每的会员每月租赁月租赁DVDDVD两次，而另外的两次，而另外的40%40%只租一次。现在我们假设网站现有只租一次。现在我们假设网站现有1010万个会万个会员，并已经知道会员对员，并已经知道会员对DVDDVD的需求，以及会员每月订的需求，以及会员每月订DVDDVD的规律。问题是应的规律。问题是应该至少准备多少张，才能保证希望看到该该至少准备多少张，才能保证希望看到该DVDDVD的会员中至少的会

5、员中至少50%50%在一个月内在一个月内能够看到？如果要求保证在三个月内至少能够看到？如果要求保证在三个月内至少95%95%的会员能够看到呢？的会员能够看到呢？表表1.1 1.1 对对10001000个会员调查的部分结果个会员调查的部分结果DVD名称名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数愿意观看的人数200100502510信息：信息： 数据是随机抽取数据是随机抽取10001000会员的调查数据会员的调查数据 每个会员每月至多租每个会员每月至多租2 2次次 每次租赁可租每次租赁可租3 3张（寄回可再租）；张（寄回可再租）； 4040会员每月租会员每月租1 1次，记作次，记作

6、A A类会员类会员1.1.6060会员每月租会员每月租2 2次，记作次，记作B B类会员类会员问题：问题：至少要准备多少张至少要准备多少张DVDDVD（上述（上述5 5种），才能保证：种），才能保证：希望看到该希望看到该DVDDVD的会员中至少的会员中至少5050能看到想看的能看到想看的DVDDVD？（一个月内）？（一个月内）希望看到该希望看到该DVDDVD的会员中至少的会员中至少9595能看到能看到DVDDVD？（三个月内）（三个月内）假设假设:1、事先无法预测会员在本月订事先无法预测会员在本月订D v D 的次数的次数2、会员每次得到会员每次得到3 张张D V D3、假设假设60 % 的每

7、月租赁的每月租赁D V D 两次的会员租赁的两次的会员租赁的D V D 一个月内可外借两次一个月内可外借两次,而而40% 的每月租赁的每月租赁D V D 一次的会员租赁的一次的会员租赁的D V D 在一个月内只能外借一在一个月内只能外借一次次第第j 种种DVD 应准备数量（应准备数量（xj）每张光盘利用次数的期望（每张光盘利用次数的期望（E）=愿观看人数（愿观看人数（Pj）能看到该能看到该DVD 人数的比例（人数的比例（R）即即jjPxRE假设假设:光盘第一次被每月租两次的会员租的光盘第一次被每月租两次的会员租的D V D 光盘一光盘一个月能利用两次个月能利用两次, 即可被两个会员租到即可被两

8、个会员租到, 被只租一次被只租一次的会员租的的会员租的D V D 光盘一个月只能利用一次光盘一个月只能利用一次每个光盘在一个月内能利用次数的期望每个光盘在一个月内能利用次数的期望E=2x60% + 1x 40% = 1.6 一个月的情况一个月的情况能看到该能看到该D V D 人数的比例人数的比例: R = 50 %调查的人数只占全部会员的调查的人数只占全部会员的1%, 所以数据按所以数据按100 倍扩大倍扩大将数值代入将数值代入jjPxRE三个月的情况三个月的情况每个光盘在三个月内能利用的次数的期望每个光盘在三个月内能利用的次数的期望53243222360%6(60%40%5+60%40% 4

9、)5+(60%40%3+60%40%3)4+40%34.44890E 由于能看到该由于能看到该D V D 人数的比例人数的比例: R = 95 % 将数将数值代入模型值代入模型求解并且把解向右取整求解并且把解向右取整jjPxRE问题问题1:1:网站购买网站购买DVDDVD的数量的数量( (x) )假设：每种假设：每种DVD独立考虑（联合考虑没有足够信息）独立考虑（联合考虑没有足够信息） 希望看到该希望看到该DVD的会员数量：确定？随机！的会员数量：确定？随机！ 保证保证一个月至少一个月至少P%有需求的会员能得到满足有需求的会员能得到满足? 会员希望看该会员希望看该DVD的概率为的概率为p网站的

10、会员总数为网站的会员总数为nn比较大，可用正态分布比较大，可用正态分布N(np, npq) 近似（近似（q=1-p） 二项分布二项分布N(n, p) 可近似认为可近似认为1个月该个月该DVD实际可用张数是实际可用张数是1.6x张张 一定置信水平下成立！一定置信水平下成立！问题问题1:1:网站购买网站购买DVDDVD的数量的数量( (x) ) 置信水平置信水平au1- a N(np, npq)a16 . 1*%PrxPa1%/6 . 1PrnpqnpPxnpqnp) 1 , 0( Nnpqnpa1%/6 . 1unpqnpPxa1*6 . 1%unpqnpPx问题问题1:1:网站购买网站购买DV

11、DDVD的数量的数量( (x) )a1*6 . 1%unpqnpPx 0.95; n=100000; P%=50%DVD名称DVD1DVD2DVD3DVD4DVD5合计p0.20.10.050.0250.01x62903155158579732312150 推广到个月的模型推广到个月的模型类似考虑：张类似考虑：张DVD在三个月内可以用多少次？在三个月内可以用多少次？归还规律出借规律的探讨将变得复杂一些，归还规律出借规律的探讨将变得复杂一些，一般需要在更多的假设下，才能得到（如还回网站一般需要在更多的假设下，才能得到（如还回网站的的DVD是否一定能马上分给某个需要的会员？）是否一定能马上分给某个

12、需要的会员？）问题问题1:1:网站购买网站购买DVDDVD的数量的数量( (x) ) 其他模型：其他模型：数值模拟（仿真）：需交代详细过程数值模拟（仿真）：需交代详细过程（归还规律？出借规律）（归还规律？出借规律）其他理解：例如认为表中给出的只是初始时段其他理解：例如认为表中给出的只是初始时段(一一个月或半个月个月或半个月)的需求，并进一步假设以后时段的的需求，并进一步假设以后时段的需求持续不变或按某种规律变化需求持续不变或按某种规律变化 （排队论？随机决策？）（排队论？随机决策？）需求上限：一定置信水平下得到上限需求上限：一定置信水平下得到上限M（x = P% * M / 1.6） 问题二问

13、题二 网站分发网站分发DVDDVD的数学模型的数学模型在现有一定数量在现有一定数量DVDDVD的前提下，如何分配以使会员总的的前提下，如何分配以使会员总的满意度最大。这与满意度最大。这与“分配问题分配问题”或或“指派问题指派问题（Assignment problem）”有很多相同点。有很多相同点。我们可以通过一些变化来使求解我们可以通过一些变化来使求解“分配问题分配问题”的模型的模型能运用于该问题。能运用于该问题。 我们把问题二中我们把问题二中“100100个会员对个会员对DVDDVD的需求的需求” 理解理解为为“需要完成的需要完成的100100项任务项任务”，“2020种种DVDDVD数量数

14、量”理解理解为为“有有2020个人可以承担这些任务个人可以承担这些任务”，“会员对于不同会员对于不同DVDDVD的偏爱度的偏爱度”理解为理解为“不同人去完成不同工作的效不同人去完成不同工作的效率率”，通过类比就能把分配问题的模型运用到问题二，通过类比就能把分配问题的模型运用到问题二中了。中了。0-1规划（最常见）规划（最常见）分配问题最常用的方法是分配问题最常用的方法是0-10-1型整数规划。在具体使用型整数规划。在具体使用前，还需要将每个会员对不同前，还需要将每个会员对不同DVDDVD的偏爱度转化为满意的偏爱度转化为满意度。因为我们的目标是总体满意度最大。度。因为我们的目标是总体满意度最大。

15、 从表从表1.21.2中可以看到：会员的在线订单用数字中可以看到：会员的在线订单用数字1,2,1,2,表示，数字越小表示会员的偏爱程度越高，数表示，数字越小表示会员的偏爱程度越高，数字字0 0表示对应的表示对应的DVDDVD当前不在会员的在线订单中。通过当前不在会员的在线订单中。通过观察我们用一个大于观察我们用一个大于9 9的固定数值来减偏爱数的固定数值来减偏爱数, ,把这个把这个差值作为满意度。差值作为满意度。1、设矩阵、设矩阵B为偏爱度矩阵，矩阵中的元素为偏爱度矩阵，矩阵中的元素bij为表为表1.2中中的偏爱数，表示第的偏爱数，表示第i个会员对个会员对DVDj的偏爱数。的偏爱数。bij越小

16、越小表示会员的满意程度越高，表示会员的满意程度越高，bij为为1时最高，时最高，bij为为0时表时表示客户没有下订单。于是就得到了偏爱度矩阵示客户没有下订单。于是就得到了偏爱度矩阵 2、设矩阵、设矩阵A为满意度矩阵，矩阵中的元素为满意度矩阵，矩阵中的元素aij为满意为满意度，表示第度，表示第i个会员对第个会员对第DVDj 的满意度。的满意度。 可通过如可通过如下算法获得：下算法获得： 20, 3 , 2 , 1;100, 3 , 2 , 120100 jibBij 20, 3 , 2 , 1;100, 3 , 2 , 100010 jibabbaijijijijij3、用、用0-1变量变量xi

17、j表示表示DVDj是否分配给第是否分配给第i个会员个会员4、用、用wj表示表示DVDj的现有数量的现有数量jiijwx 1001ijijxa5、用、用0-1变量变量yi表示第表示第i个用户是否得到个用户是否得到DVD2013ijijxy由以上分析可得问题二的模型：由以上分析可得问题二的模型：10020111001201max31,2,3,1000,1,0,11,2,3,100;1,2,3,20ijijijijijijjiijijijiZa xxaxwxyixyijLLL用用LINGO LINGO 数学软件实现对此题数学软件实现对此题0-10-1规划模型的求解规划模型的求解答卷中的问题：答卷中的

18、问题： 目标定义不合理目标定义不合理 约束不完整约束不完整 软件使用不当软件使用不当(LINGO求解容易求解容易,Why?) 问题二问题二 网站分发网站分发DVDDVD的数学模型的数学模型贪婪算法贪婪算法( 求近似解求近似解)Step1: 对于库存的对于库存的100 种光盘种光盘, 首先满足所有对它偏爱首先满足所有对它偏爱顺序为顺序为1的会员的需要的会员的需要, 即将每种光盘分配给所有对其偏即将每种光盘分配给所有对其偏爱顺序为爱顺序为1 会员会员, 如果该光盘的数目偏少无法完成此次分如果该光盘的数目偏少无法完成此次分配配, 则先分配给其中编号较小的那些会员则先分配给其中编号较小的那些会员;St

19、ep2: 对于剩余光盘对于剩余光盘, 再优先满足对它偏爱顺序为再优先满足对它偏爱顺序为2 的的会员需要会员需要, 同样地同样地, 如果该光盘的数目偏少无法完成此如果该光盘的数目偏少无法完成此次分配次分配, 则先分配给其中编号较小的那些会员则先分配给其中编号较小的那些会员;Step 3 :依此类推分配下去依此类推分配下去, 在在Step 3 以后分配时以后分配时,己经拥有己经拥有3 张光盘的会员不参加分配张光盘的会员不参加分配Step 11 : 如果还有剩下的光盘如果还有剩下的光盘, 随机分配给尚未分随机分配给尚未分满的会员满的会员, 分配结束分配结束这种贪婪算法计算量较小这种贪婪算法计算量较小

20、, 速度很快。由于上述步速度很快。由于上述步骤尽量保证了偏爱程度较高的匹配骤尽量保证了偏爱程度较高的匹配, 可以保证结果可以保证结果的近似最优的近似最优模型二：网络优化模型模型二：网络优化模型 最小费用最大流最小费用最大流12n12m3,0cj,0st, 1ija会员会员DVDaij=aij (aij 0)aij=M (aij =0)(或没有弧或没有弧)存在多项式时间算法存在多项式时间算法两个模型等价吗两个模型等价吗? 上海交大上海交大 问题二问题二 网站分发网站分发DVDDVD的数学模型的数学模型构造加权有向图构造加权有向图G V,E :点集点集V=source，C1,C2 ,C1000,D

21、1,D2, ,D100,terminal，其中，其中， Ci (1i1000)代表第代表第i个会员，个会员，Dj(1j100)代代表第表第j张张DVD盘，盘，source为网络流的源点，为网络流的源点，terminal为网络流的汇点。为网络流的汇点。在在source与所有的与所有的 Ci之间添加有向边之间添加有向边(source，Ci )， (1i1000) ，该边具有容量，该边具有容量3，单位流量费用为，单位流量费用为0；在所有在所有Dj与与terminal之间添加有向边之间添加有向边( Dj，terminal)，(1 j100) ，该边的容量为第，该边的容量为第j种种DVD的现有数量，单的

22、现有数量，单位流量费用为位流量费用为0根据题目中订单，若第根据题目中订单，若第i个会员预订了第个会员预订了第j种种DVD，则添加有向边则添加有向边(Ci ，Dj)，该边的容量为，该边的容量为1，单位流量，单位流量费用为该会员对该种费用为该会员对该种DVD 的偏爱值的偏爱值考虑到现实中，考虑到现实中，DVD 的个数为整数，我们规定图的个数为整数，我们规定图1中中G所有边的流量为整数。因此，图所有边的流量为整数。因此，图1中中G是一个整是一个整数流量的最小费用最大流模型。数流量的最小费用最大流模型。建立的图论模型，其最小费用最大流恰好表示了满建立的图论模型，其最小费用最大流恰好表示了满足上述最大满

23、意度定义的分配方案，而最小费用恰足上述最大满意度定义的分配方案，而最小费用恰恰代表着最大满意度恰代表着最大满意度王成王成, 文野文野, 俞寅涛俞寅涛, DVD租赁问题的模型设计及求租赁问题的模型设计及求解解,工程数学学报工程数学学报, 2005, 7(22): 92-100在一定的假设下，把问题近似分解成前面考虑过的购买和分发两个子在一定的假设下，把问题近似分解成前面考虑过的购买和分发两个子问题。例如，有的论文先根据会员订单统计问题。例如，有的论文先根据会员订单统计DVD的需求情况，确定的需求情况，确定DVD购买量，然后用前一问中建立的模型进行第一次分发，再对网站购买量，然后用前一问中建立的模

24、型进行第一次分发，再对网站是否知道哪些会员租赁两次作出一定假设，进行第二次分发。是否知道哪些会员租赁两次作出一定假设，进行第二次分发。有的论文对前一问中建立的模型进行一定修改，建立购买和分发统一有的论文对前一问中建立的模型进行一定修改，建立购买和分发统一的多目标数学规划模型，且同时考虑两次分发和服务水平约束，不过的多目标数学规划模型，且同时考虑两次分发和服务水平约束，不过往往在二次分配和服务水平约束方面考虑有些缺陷。往往在二次分配和服务水平约束方面考虑有些缺陷。考虑到一个月内可能一个会员要发货两次，这又是一个多阶段的决策考虑到一个月内可能一个会员要发货两次，这又是一个多阶段的决策问题，建立随机决策模型并寻找最优决策是可能的（例如采用马氏决问题，建立随机决策模型并寻找最优决策是可能的（例如采用马氏决策方法），但由于后一阶段决策时需要考虑前一阶段哪些会员归还了策方法），但由于后一阶段决策时需要考虑前一阶段哪些会员归还了哪些哪些DVD，因此这样建立模型的难度较大，评委们在评阅中几乎没有，因此这样建立模型的难度较大，评委们在评阅中几乎没有见到非常成功的论文。见到非常成功的论文。采用