DVD在线租赁问题ppt课件

主讲教师 董庆来2012年8月9日 2012年数学建模竞赛暑期集训系列讲座之一DVD在线租赁 CUMCM 2005B DVD在线租赁 命题人 余刚先生 教授 时任亚马逊公司全球供应链运营副总裁曾任美国德州大学奥斯汀分校管理学院JackG Taylor讲席教授获多项美国专利 1995年创建美国科莱科技公司 CALEBTechnologiesCorp 并任董事长和总裁航班管理 2001年为美国大陆航空公司所创造的价值超过6000万美元 获2002年运筹学与管理科学应用FranzEdelman奖 运筹学与管理科学应用的 世界杯 CUMCM 2005B DVD在线租赁 网上DVD在线租赁业务 2005年时的背景 亚马逊英国公司 amazon co uk 美国和等 欧洲等著名公司租赁的DVD多达几万种 用户多达几十万 几百万 有的包括多个配送中心题目 会员每月最多可租赁两次 每次 张DVD第 1 2 问 分别考虑购买和分发子问题第 3 问 同时考虑购买和分发第 4 问 自己提出新问题 尝试建模和求解 二 问题分析与建模 问题一网站购买DVD的最优数量 在现有会员中随机抽取1000个会员进行调查 以得知愿意观看不同DVD的人数 表1 1给出了其中5种DVD的数据 从历史数据显示 60 的会员每月租赁DVD两次 而另外的40 只租一次 现在我们假设网站现有10万个会员 并已经知道会员对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 事先无法预测会员在本月订DvD的次数2 会员每次得到3张DVD3 假设60 的每月租赁DVD两次的会员租赁的DVD一个月内可外借两次 而40 的每月租赁DVD一次的会员租赁的DVD在一个月内只能外借一次 第j种DVD应准备数量 xj 每张光盘利用次数的期望 E 愿观看人数 Pj 能看到该DVD人数的比例 R 即 假设 光盘第一次被每月租两次的会员租的DVD光盘一个月能利用两次 即可被两个会员租到 被只租一次的会员租的DVD光盘一个月只能利用一次 每个光盘在一个月内能利用次数的期望 E 2x60 1x40 1 6 一个月的情况 能看到该DVD人数的比例 R 50 调查的人数只占全部会员的1 所以数据按100倍扩大 将数值代入 三个月的情况 每个光盘在三个月内能利用的次数的期望 由于能看到该DVD人数的比例 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 网站购买DVD的数量 x 置信水平 N np npq 问题1 网站购买DVD的数量 x 0 95 n 100000 P 50 推广到 个月的模型 类似考虑 张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的满意度 可通过如下算法获得 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 对于剩余光盘 再优先满足对它偏爱顺序为2的会员需要 同样地 如果该光盘的数目偏少无法完成此次分配 则先分配给其中编号较小的那些会员 Step3 依此类推分配下去 在Step3以后分配时 己经拥有3张光盘的会员不参加分配 Step11 如果还有剩下的光盘 随机分配给尚未分满的会员 分配结束 这种贪婪算法计算量较小 速度很快 由于上述步骤尽量保证了偏爱程度较高的匹配 可以保证结果的近似最优 模型二 网络优化模型 最小费用最大流 会员DVD aij aij aij 0 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 因此这样建立模型的难度较大 评委们在评阅中几乎没有见到非常成功的论文 采用数值模拟 仿真 建模和求解 或检验其他模型 问题三购买和分发同时考虑 问题三有两个目标 最少的购买量和最大的满意度 建立双目标规划模型 并将其通过加权组合转化为单目标的混合整数规划模型 总的满意度 总的购买量 多目标规划模型 目标函数为 约束条件为 黄梅 半忠 门海军 DVD租赁问题的模型设计及求解 工程数学学报 2005 7 22 108 112 网站应充