《DVD在线租赁问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《DVD在线租赁问题ppt课件.ppt（32页珍藏版）》请在三一办公上搜索。
1、主讲教师：董庆来2012年8月9日,2012年数学建模竞赛暑期集训系列讲座之一DVD在线租赁,CUMCM-2005B:DVD在线租赁,命题人：余刚先生（教授）时任亚马逊公司全球供应链运营副总裁曾任美国德州大学奥斯汀分校管理学院Jack G.Taylor讲席教授获多项美国专利，1995年创建美国科莱科技公司(CALEBTechnologiesCorp.)并任董事长和总裁航班管理：2001年为美国大陆航空公司所创造的价值超过6000万美元，获2002年运筹学与管理科学应用Franz Edelman奖(运筹学与管理科学应用的“世界杯”),CUMCM-2005B:DVD在线租赁,网上DVD在线租赁业务
2、（2005年时的背景）亚马逊英国公司(amazon.co.uk)；美国和等；欧洲等著名公司租赁的DVD多达几万种，用户多达几十万几百万，有的包括多个配送中心题目：会员每月最多可租赁两次，每次张DVD第（1）、（2）问：分别考虑购买和分发子问题第（3）问：同时考虑购买和分发第（4）问：自己提出新问题，尝试建模和求解,二、问题分析与建模,问题一 网站购买DVD的最优数量,在现有会员中随机抽取1000个会员进行调查，以得知愿意观看不同DVD的人数（表1.1给出了其中5种DVD的数据）。从历史数据显示，60%的会员每月租赁DVD两次，而另外的40%只租一次。现在我们假设网站现有10万个会员，并已经知道
3、会员对DVD的需求，以及会员每月订DVD的规律。问题是应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到？如果要求保证在三个月内至少95%的会员能够看到呢？,表1.1 对1000个会员调查的部分结果,信息：数据是随机抽取1000会员的调查数据每个会员每月至多租2次每次租赁可租3张（寄回可再租）；40会员每月租1次，记作A类会员60会员每月租2次，记作B类会员,问题：至少要准备多少张DVD（上述5种），才能保证：希望看到该DVD的会员中至少50能看到想看的DVD？（一个月内）希望看到该DVD的会员中至少95能看到DVD？（三个月内）,假设:1、事先无法预测会员在本月
4、订D v D 的次数2、会员每次得到3 张D V D3、假设60%的每月租赁D V D 两次的会员租赁的D V D 一个月内可外借两次,而40%的每月租赁D V D 一次的会员租赁的D V D 在一个月内只能外借一次,第j 种DVD 应准备数量（xj）每张光盘利用次数的期望（E）=愿观看人数（Pj）能看到该DVD 人数的比例（R）,即,假设:光盘第一次被每月租两次的会员租的D V D 光盘一个月能利用两次,即可被两个会员租到,被只租一次的会员租的D V D 光盘一个月只能利用一次,每个光盘在一个月内能利用次数的期望,E=2x60%+1x 40%=1.6,一个月的情况,能看到该D V D 人数的
5、比例:R=50%,调查的人数只占全部会员的1%,所以数据按100 倍扩大,将数值代入,三个月的情况,每个光盘在三个月内能利用的次数的期望,由于能看到该D V D 人数的比例:R=95%将数值代入模型求解并且把解向右取整,问题1:网站购买DVD的数量(x),假设：每种DVD独立考虑（联合考虑没有足够信息）,希望看到该DVD的会员数量：确定？随机！,保证一个月至少P%有需求的会员能得到满足?,会员希望看该DVD的概率为p网站的会员总数为n,n比较大，可用正态分布N(np,npq)近似（q=1-p）,二项分布N(n,p),可近似认为1个月该DVD实际可用张数是1.6x张,一定置信水平下成立！,问题1
6、:网站购买DVD的数量(x),置信水平,N(np,npq),问题1:网站购买DVD的数量(x),0.95;n=100000;P%=50%,推广到个月的模型,类似考虑：张DVD在三个月内可以用多少次？归还规律出借规律的探讨将变得复杂一些，一般需要在更多的假设下，才能得到（如还回网站的DVD是否一定能马上分给某个需要的会员？）,问题1:网站购买DVD的数量(x),其他模型：,数值模拟（仿真）：需交代详细过程（归还规律？出借规律）,其他理解：例如认为表中给出的只是初始时段(一个月或半个月)的需求，并进一步假设以后时段的需求持续不变或按某种规律变化（排队论？随机决策？）,需求上限：一定置信水平下得到上
7、限M（x=P%*M/1.6）,问题二 网站分发DVD的数学模型,在现有一定数量DVD的前提下，如何分配以使会员总的满意度最大。这与“分配问题”或“指派问题（Assignment problem）”有很多相同点。我们可以通过一些变化来使求解“分配问题”的模型能运用于该问题。我们把问题二中“100个会员对DVD的需求”理解为“需要完成的100项任务”，“20种DVD数量”理解为“有20个人可以承担这些任务”，“会员对于不同DVD的偏爱度”理解为“不同人去完成不同工作的效率”，通过类比就能把分配问题的模型运用到问题二中了。,0-1规划（最常见）,分配问题最常用的方法是0-1型整数规划。在具体使用前，
8、还需要将每个会员对不同DVD的偏爱度转化为满意度。因为我们的目标是总体满意度最大。,从表1.2中可以看到：会员的在线订单用数字1,2,表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。通过观察我们用一个大于9的固定数值来减偏爱数,把这个差值作为满意度。,1、设矩阵B为偏爱度矩阵，矩阵中的元素bij为表1.2中的偏爱数，表示第i个会员对DVDj的偏爱数。bij越小表示会员的满意程度越高，bij为1时最高，bij为0时表示客户没有下订单。于是就得到了偏爱度矩阵,2、设矩阵A为满意度矩阵，矩阵中的元素aij为满意度，表示第i个会员对第DVDj 的满意度。可通过如下
9、算法获得：,3、用0-1变量xij表示DVDj是否分配给第i个会员,4、用wj表示DVDj的现有数量,5、用0-1变量yi表示第i个用户是否得到DVD,由以上分析可得问题二的模型：,用LINGO 数学软件实现对此题0-1规划模型的求解,答卷中的问题：目标定义不合理 约束不完整 软件使用不当(LINGO求解容易,Why?),问题二 网站分发DVD的数学模型,贪婪算法(求近似解),Step1:对于库存的100 种光盘,首先满足所有对它偏爱顺序为1的会员的需要,即将每种光盘分配给所有对其偏爱顺序为1 会员,如果该光盘的数目偏少无法完成此次分配,则先分配给其中编号较小的那些会员;,Step2:对于剩余
10、光盘,再优先满足对它偏爱顺序为2 的会员需要,同样地,如果该光盘的数目偏少无法完成此次分配,则先分配给其中编号较小的那些会员;,Step 3:依此类推分配下去,在Step 3 以后分配时,己经拥有3 张光盘的会员不参加分配,Step 11:如果还有剩下的光盘,随机分配给尚未分满的会员,分配结束,这种贪婪算法计算量较小,速度很快。由于上述步骤尽量保证了偏爱程度较高的匹配,可以保证结果的近似最优,模型二：网络优化模型 最小费用最大流,会员DVD,aij=aij(aij 0)aij=M(aij=0)(或没有弧),存在多项式时间算法两个模型等价吗?,上海交大,问题二 网站分发DVD的数学模型,构造加权
11、有向图G V,E:点集V=source，C1,C2,C1000,D1,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的现有数量，单位流量费用为0,根据题目中订单，若第i个会员预订了第j种DVD，则添加有向边(Ci，Dj)，该边的容量为1，
12、单位流量费用为该会员对该种DVD 的偏爱值,考虑到现实中，DVD 的个数为整数，我们规定图1中G所有边的流量为整数。因此，图1中G是一个整数流量的最小费用最大流模型。,建立的图论模型，其最小费用最大流恰好表示了满足上述最大满意度定义的分配方案，而最小费用恰恰代表着最大满意度,王成,文野,俞寅涛,DVD租赁问题的模型设计及求解,工程数学学报,2005,7(22):92-100,在一定的假设下，把问题近似分解成前面考虑过的购买和分发两个子问题。例如，有的论文先根据会员订单统计DVD的需求情况，确定DVD购买量，然后用前一问中建立的模型进行第一次分发，再对网站是否知道哪些会员租赁两次作出一定假设，进
13、行第二次分发。有的论文对前一问中建立的模型进行一定修改，建立购买和分发统一的多目标数学规划模型，且同时考虑两次分发和服务水平约束，不过往往在二次分配和服务水平约束方面考虑有些缺陷。考虑到一个月内可能一个会员要发货两次，这又是一个多阶段的决策问题，建立随机决策模型并寻找最优决策是可能的（例如采用马氏决策方法），但由于后一阶段决策时需要考虑前一阶段哪些会员归还了哪些DVD，因此这样建立模型的难度较大，评委们在评阅中几乎没有见到非常成功的论文。采用数值模拟（仿真）建模和求解，或检验其他模型。,问题三 购买和分发同时考虑,问题三有两个目标：最少的购买量和最大的满意度，建立双目标规划模型,并将其通过加权
14、组合转化为单目标的混合整数规划模型,总的满意度,总的购买量,多目标规划模型,目标函数为,约束条件为,黄梅,半忠,门海军,DVD租赁问题的模型设计及求解,工程数学学报,2005,7(22):108-112,网站应充分利用会员过去租赁的历史数据从各方面认真进行统计分析（数据挖掘），并对会员进行分类处理；网站对DVD应分多次购买而不是一次性购买；网站的短期利益与长期利益应该权衡；如果不限定会员每月最多只租赁2次，对网站运营会有什么影响？,问题 自己提问题,小结：CUMCM评阅标准,模型完整明确模型/算法创新软件使用恰当,假设的合理性，建模的创造性，结果的正确性，表述的清晰性。,深入思考/分析表达规范严谨严禁作弊抄袭,感谢大家！,知识回顾Knowledge Review,
