DVD在线租赁问题

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

主讲教师:董庆来2012年8月9日2012年数学建模竞赛暑期集训系列讲座之一DVD在线租赁CUMCM-2005B:DVD在线租赁命题人:余刚先生(教授)时任亚马逊公司全球供应链运营副总裁曾任美国德州大学奥斯汀分校管理学院JackG.Taylor讲席教授获多项美国专利,1995年创建美国科莱科技公司(CALEBTechnologiesCorp.)并任董事长和总裁航班管理:2001年为美国大陆航空公司所创造的价值超过6000万美元,获2002年运筹学与管理科学应用FranzEdelman奖(运筹学与管理科学应用的“世界杯”)CUMCM-2005B:DVD在线租赁网上DVD在线租赁业务(2005年时的背景)亚马逊英国公司(amazon.co.uk);美国netflix.com和blockbuster.com等;欧洲lovefilm.com等著名公司租赁的DVD多达几万种,用户多达几十万~几百万,有的包括多个配送中心题目:会员每月最多可租赁两次,每次3张DVD第(1)、(2)问:分别考虑购买和分发子问题第(3)问:同时考虑购买和分发第(4)问:自己提出新问题,尝试建模和求解二、问题分析与建模问题一网站购买DVD的最优数量在现有会员中随机抽取1000个会员进行调查,以得知愿意观看不同DVD的人数(表1.1给出了其中5种DVD的数据)。从历史数据显示,60%的会员每月租赁DVD两次,而另外的40%只租一次。现在我们假设网站现有10万个会员,并已经知道会员对DVD的需求,以及会员每月订DVD的规律。问题是应该至少准备多少张,才能保证希望看到该DVD的会员中至少50%在一个月内能够看到?如果要求保证在三个月内至少95%的会员能够看到呢?表1.1对1000个会员调查的部分结果DVD名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数200100502510信息:1.数据是随机抽取1000会员的调查数据2.每个会员每月至多租2次3.每次租赁可租3张(寄回可再租);4.40%会员每月租1次,记作A类会员5.60%会员每月租2次,记作B类会员问题:至少要准备多少张DVD(上述5种),才能保证:①希望看到该DVD的会员中至少50%能看到想看的DVD?(一个月内)②希望看到该DVD的会员中至少95%能看到DVD?(三个月内)假设:1、事先无法预测会员在本月订DvD的次数2、会员每次得到3张DVD3、假设60%的每月租赁DVD两次的会员租赁的DVD一个月内可外借两次,而40%的每月租赁DVD一次的会员租赁的DVD在一个月内只能外借一次第j种DVD应准备数量(xj)×每张光盘利用次数的期望(E)=愿观看人数(Pj)×能看到该DVD人数的比例(R)即jjPxRE假设:光盘第一次被每月租两次的会员租的DVD光盘一个月能利用两次,即可被两个会员租到,被只租一次的会员租的DVD光盘一个月只能利用一次每个光盘在一个月内能利用次数的期望E=2x60%+1x40%=1.6一个月的情况能看到该DVD人数的比例:R=50%调查的人数只占全部会员的1%,所以数据按100倍扩大将数值代入jjPxRE三个月的情况每个光盘在三个月内能利用的次数的期望53243222360%6(60%40%5+60%40%4)5+(60%40%3+60%40%3)4+40%34.44890E由于能看到该DVD人数的比例:R=95%将数值代入模型求解并且把解向右取整jjPxRE问题1:网站购买DVD的数量(x)假设:每种DVD独立考虑(联合考虑没有足够信息)•希望看到该DVD的会员数量:确定?随机!!!•保证一个月至少P%有需求的会员能得到满足?会员希望看该DVD的概率为p网站的会员总数为nn比较大,可用正态分布N(np,npq)近似(q=1-p)二项分布N(n,p)可近似认为1个月该DVD实际可用张数是1.6x张一定置信水平下成立!问题1:网站购买DVD的数量(x)•置信水平1-αau1-aξ~N(np,npq)a16.1*%PrxPa1%/6.1PrnpqnpPxnpqnp)1,0(~Nnpqnpa1%/6.1unpqnpPxa1*6.1%unpqnpPx问题1:网站购买DVD的数量(x)a1*6.1%unpqnpPx•1-α=0.95;•n=100000;P%=50%DVD名称DVD1DVD2DVD3DVD4DVD5合计p0.20.10.050.0250.01x62903155158579732312150•推广到3个月的模型类似考虑:1张DVD在三个月内可以用多少次?归还规律/出借规律的探讨将变得复杂一些,一般需要在更多的假设下,才能得到(如还回网站的DVD是否一定能马上分给某个需要的会员?)问题1:网站购买DVD的数量(x)•其他模型:数值模拟(仿真):需交代详细过程(归还规律?出借规律)其他理解:例如认为表中给出的只是初始时段(一个月或半个月)的需求,并进一步假设以后时段的需求持续不变或按某种规律变化(排队论?随机决策?)需求上限:一定置信水平下得到上限M(x=P%*M/1.6)问题二网站分发DVD的数学模型在现有一定数量DVD的前提下,如何分配以使会员总的满意度最大。这与“分配问题”或“指派问题(Assignmentproblem)”有很多相同点。我们可以通过一些变化来使求解“分配问题”的模型能运用于该问题。我们把问题二中“100个会员对DVD的需求”理解为“需要完成的100项任务”,“20种DVD数量”理解为“有20个人可以承担这些任务”,“会员对于不同DVD的偏爱度”理解为“不同人去完成不同工作的效率”,通过类比就能把分配问题的模型运用到问题二中了。0-1规划(最常见)分配问题最常用的方法是0-1型整数规划。在具体使用前,还需要将每个会员对不同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的满意度。可通过如下算法获得:20,,3,2,1;100,,3,2,120100jibBij20,,3,2,1;100,,3,2,100010jibabbaijijijijij3、用0-1变量xij表示DVDj是否分配给第i个会员4、用wj表示DVDj的现有数量jiijwx1001ijijxa5、用0-1变量yi表示第i个用户是否得到DVD2013ijijxy由以上分析可得问题二的模型:10020111001201max31,2,3,,100{0,1},{0,1}1,2,3,,100;1,2,3,,20ijijijijijijjiijijijiZaxxaxwxyixyijLLL用LINGO数学软件实现对此题0-1规划模型的求解答卷中的问题:•目标定义不合理•约束不完整•软件使用不当(LINGO求解容易,Why?)问题二网站分发DVD的数学模型贪婪算法(求近似解)Step1:对于库存的100种光盘,首先满足所有对它偏爱顺序为1的会员的需要,即将每种光盘分配给所有对其偏爱顺序为1会员,如果该光盘的数目偏少无法完成此次分配,则先分配给其中编号较小的那些会员;Step2:对于剩余光盘,再优先满足对它偏爱顺序为2的会员需要,同样地,如果该光盘的数目偏少无法完成此次分配,则先分配给其中编号较小的那些会员;Step3:………依此类推分配下去,在Step3以后分配时,己经拥有3张光盘的会员不参加分配Step11:如果还有剩下的光盘,随机分配给尚未分满的会员,分配结束这种贪婪算法计算量较小,速度很快。由于上述步骤尽量保证了偏爱程度较高的匹配,可以保证结果的近似最优模型二:网络优化模型–最小费用最大流12…n12…m3,0cj,0st',1ija会员DVDaij’=aij(aij0)aij’=M(aij=0)(或没有弧)•存在多项式时间算法•两个模型等价吗?•上海交大问题二网站分发DVD的数学模型构造加权有向图G{V,E}:点集V={source,C1,C2⋯,C1000,D1,D2,⋯,D100,terminal},其中,Ci(1≤i≤1000)代表第i个会员,Dj(1≤j≤100)代表第j张DVD盘,source为网络流的源点,terminal为网络流的汇点。在source与所有的Ci之间添加有向边(source,Ci),(1≤i≤1000),该边具有容量3,单位流量费用为0;在所有Dj与terminal之间添加有向边(Dj,terminal),(1≤j≤100),该边的容量为第j种DVD的现有数量,单位流量费用为0根据题目中订单,若第i个会员预订了第j种DVD,则添加有向边(Ci,Dj),该边的容量为1,单位流量费用为该会员对该种DVD的偏爱值考虑到现实中,DVD的个数为整数,我们规定图1中G所有边的流量为整数。因此,图1中G是一个整数流量的最小费用最大流模型。建立的图论模型,其最小费用最大流恰好表示了满足上述最大满意度定义的分配方案,而最小费用恰恰代表着最大满意度王成,文野,俞寅涛,DVD租赁问题的模型设计及求解,工程数学学报,2005,7(22):92-100•在一定的假设下,把问题近似分解成前面考虑过的购买和分发两个子问题。例如,有的论文先根据会员订单统计DVD的需求情况,确定DVD购买量,然后用前一问中建立的模型进行第一次分发,再对网站是否知道哪些会员租赁两次作出一定假设,进行第二次分发。•有的论文对前一问中建立的模型进行一定修改,建立购买和分发统一的多目标数学规划模型,且同时考虑两次分发和服务水平约束,不过往往在二次分配和服务水平约束方面考虑有些缺陷。•考虑到一个月内可能一个会员要发货两次,这又是一个多阶段的决策问题,建立随机决策模型并寻找最优决策是可能的(例如采用马氏决策方法),但由于后一阶段决策时需要考虑前一阶段哪些会员归还了哪些DVD,因此这样建立模型的难度较大,评委们在评阅中几乎没有见到非常成功的论文。•采用数值模拟(仿真)建模和求解,或检验其他模型。问题三购买和分发同时考虑问题三有两个目标:最少的购买量和最大的满意度,建立双目标规划模型并将其通过加权组合转化为单目标的混合整数规划模型1002011ijijijZax总的满意度总的购买量201jjWw多目标规划模型目标函数为max(1)ZW100120131,2,3,,100{0,1},{0,1}1,2,3,,100;1,2,3,,20ijijijjiijijijixaxwxyixyijLLL约束条件为黄梅,半忠,门海军,DVD租赁问题的模型设计及求解,工程数学学报,2005,7(22):108-112•网站应充分利用会员过去租赁的历史数据从各方面认真进行统计分析(数据挖掘),并对会员进行分类处理;•网站对DVD应分多次购买而不是一次性购买;•网站的短期利益与长期利益应该权衡;•如果不限定会员每月最多只租赁2次,对网站运营会有什么影响?•......问题4–自己提问题小结:CUMCM评阅标准•模型完整明确•模型/算法创新•软件使用恰当假设的合理性,建模的创造性,结果的正确性,表述的清晰性。•深入思考/分析•表达规范严谨•严禁作弊抄袭知识回顾KnowledgeReview

1 / 32
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功