数学建模案例DVD在线租赁.pdf

1 DVD 在线租赁问题研究 摘要 本文解决的是DVD在线租赁网站在DVD的需求预测 购买和分配中的重要 问题 首先我们通过随机概率模型分析了要满足会员要求的DVD的最少采购量 其中主要利用了10 分布和二项分布的理论 即认为会员是否一个月租赁两次是 一个随机事件 服从10 分布 因此分配到自己想要DVD的会员中租赁两次的 人数就服从二项分布 具体计算时 由于是大样本场合 用标准正态分布逼近二 项分布得到最后的结果 在解决最大满意度原则下的DVD分配时 我们建立的是以最大期望满意度 为目标 含有随机变量的规划模型 出于计算规模和效率方面的考虑 文中采用 类似贪婪算法的处理方法 将DVD的分配分成两个阶段来处理 这两个阶段分 别的最优解之和作为最终要得到的最优目标 最后我们基于现实基础提出了以最大满意度和最小邮费为目标的规划方程 并对上述几个模型进行了评价和推广价值讨论 2 一 问题重述 考虑如下 DVD 租赁问题 顾客缴纳一定数量的月费成为会员 订购 DVD 租赁 服务 会员对哪些 DVD 有兴趣 只要在线提交订单 网站就会通过快递的方式尽 可能满足要求 会员提交的订单包括多张 DVD 这些 DVD 是基于其偏爱程度排序 的 网站会根据手头现有的 DVD 数量和会员的订单进行分发 其中网站有如下几个约定 每个会员每个月租赁次数不得超过 2 次 每 次获得 3 张 DVD 会员看完 3 张 DVD 之后 只需要将 DVD 放进网站提供的信封 里寄回 邮费由网站承担 就可以继续下次租赁 现在需要解决以下几个问题 1 若网站准备购买一些新的 DVD 通过问卷调查 1000 个会员 得到了愿意 观看这些 DVD 的人数 表 1 给出了其中 5 种 DVD 的数据 另外根据经验 有 60 的会员每月租赁 DVD 两次 而另外的 40 只租一次 网站现有 10 万个会员 用表 1 中的数据进行推广 计算出应该至少准备多少张 才 能保证希望看到该DVD的会员中至少50 在一个月内能够看到该DVD 如 果要保证在三个月内至少 95 的会员能够看到该 DVD 该如何准备 2 表 2 中列出了网站手上 100 种 DVD 的现有张数和当前需要处理的 1000 位会员的在线订单 分配这些 DVD 使会员获得最大的满意度 并具体 列出前 30 位会员 即 C0001 C0030 分别获得哪些 DVD 3 继续考虑表 2 并假设表 2 中 DVD 的现有数量全部为 0 决定每种 DVD 的购买量 以及如何对这些 DVD 进行分配 才能使一个月内 95 的会员 得到他想看的 DVD 并且满意度最大 4 深入研究 DVD 的需求预测 购买和分配中的重要问题 提出这些问题并 建立模型加以改进 二 模型假设 1 考虑到邮寄时间的限制 DVD在一个月内分配后返还的次数是有限的 2 会员当月租赁的DVD在当月内归还 3 当会员要归还DVD时 该DVD肯定可以在下一个月前回到网站 4 会员得到该DVD地满意度与会员对该DVD的偏爱程度成正相关的 三 问题分析 1 总体解题思路 在解决第一小题时 会员是否一个月租赁两次是一个随机事件 服从10 分 布 因此要真正保证 50 的会员得到满足 就必须使用概率论与数理统计的方 法 本文在取定一个合理的置信度后 计算出至少要订购的DVD数量 在解决第二小题时 我们认为网站的分配可以分为两个阶段的分配 其中第 一个阶段的分配 网站是可以完全掌控的 而第二个阶段则是一个以最大期望满 3 意度为目标含有随机变量的规划模型 在计算时我们考虑用贪婪算法得出近似最 优解 对于第三个小题 我们认为可以在第一个小题和第二个小题结合得到 考虑 先用第一小题的方法算出网站应该购入的DVD数量 在此基础上再建立和第二 小题类似的规划模型来解决 最后一个问题具有较多的研究方向 由于时间关系 我们仅就邮资最小 网 站的成本最低 盈利最大这个方面进行了一些讨论 2 题目要义的理解 a 一个月内DVD出租次数的限制 根据假设 1 结合实际 由于邮寄货物一般要一到两个星期左右 因此本文 考虑一张DVD在一个月内最多只能分配两次 即只能在初次分配后由会员返还 一次 也就是说一个月可以考虑有两个阶段的分配 第一阶段是网站对其拥有的 DVD进行初次分配 这一阶段的分配网站在某一原则下 文中是满意度最大原 则 是可以完全掌控的 第二个阶段网站可分配的DVD数量是由第一阶段分配后剩下的DVD数量 加上第一阶段分配的会员中返还得DVD数量之和 这一阶段的分配是带有随机 性的 因为会员是否返还DVD 也就是一个月租赁两次 是一个随机事件 这 一阶段 因此必须在承认随机性的前提上考虑其分配 b 会员满意度 ij 的定义 根据假设 4 本文满意度 ij 定义如下 若题中所给表 2 中会员i对第j张DVD的订单是 ij a ij a越小 偏爱程度越 高 则会员i得到第j张DVD的满意度 ijij ji ij aa 1max 1001 10001 如果 0 ij a 则0 ij 与假设相符合 四 符号说明 j x网站对第j张DVD的购入量 ij 满意度矩阵中的元素 表示第i个会员对收到第j张DVD的满意度 ij y0 1 变量 1 ij y表示第一个租赁阶段内将第j张DVD租赁给第i个会员 否则表示没有租赁给第i个会员 ij z0 1 变量 1 ij z表示第二个租赁阶段内将第j张DVD租赁给第i个会员 否则表示没有租赁给第i个会员 4 1 M第一阶段分配的最大满意度 2 M第二阶段分配的最大满意度 M总的最大满意度 五 模型的建立 1 问题一 模型 1 从最直观的思路分析 既然分配到DVD的会员中有 60 的人会归还 碟片并再次租赁 那么最少需要的购入量将是 11 5 06 1dx 即 1 100 1 662 5x 以下计算都以1DVD为例进行分析 模型 2 模型 1 简便易行 直观容易理解 易于推广 但是忽略了 根据历 史数据得到的 60 不是一个绝对比例而是一个估计量的期望值 实际上每个会员 是否归还碟片并再次租赁是一个随机事件 的事实 根据以上的思路深入分析 可以得到更为科学的模型 设 j d为想看第j张DVD的会员数量 i N为第i个会员一个月内是否第二次 租赁的随机事件 服从10 分布 j I为对第j种DVD 它的某一次分配所分给 的会员的指标集 j Ii ij NT 表示对第j种DVD 它的一次分配中可以有多少 DVD被归还供再租赁的随机事件 服从二项分布 既然DVD的分配是一个随机过程 那么必须要对使 想看1DVD的会员中 至少 50在一个月内能够看到1DVD 这一事件设立一个置信度 本题中我们令 置信度为 99 即不能满足需要的情况发生的概率小于 1 是小概率事件 要使会员的需要有 50 被满足 就要使归还的碟片数 1 T和购入的碟片数 1 x满 足 111 5 0dxT 即 111 5 0 xdT 于是有 99 0 5 0 111 xdTP 1 T服从参数 1 6 0 xnp 的二项分布 pnB 故由中心极限定理 1 用标准正 态分布近似得到 99 0 1 6 15 0 1 1 11 1 11 ppx xd ppx pxT P 5 99 0 1 5 06 1 1 11 ppx dx 将题中数据代入计算得到 99 0 1 1006 1 1 1 ppx x 查表 1 得 33 2 24 0 1006 1 1 1 x x 得到的是一个一元二次方程 利用求根公式求出与现实意义相吻合的解 舍去不 合理的解 便得到了购入量的正解 40 68 1 x 由于历史数据是实际数据的样本 根据数理统计中的格列文科定理知 总体的购 入量趋于样本购入量的 100 倍 因此实际的购入量至少是 6840 类似的 可分别解出五种 DVD 的至少购入量 结果如下表 DVD1DVD2DVD3DVD4DVD5 6840355018721008467 对于 三个月内至少 95 的会员能看到1DVD 这一事件 设每个月的分配中 归还再租赁的DVD数的随机变量分别为 1 1 T 2 1 T 3 1 T 由于每个月月初所能分 配的碟片数量均为 1 x 这保证了 1 1 T 2 1 T 3 1 T相互独立 且每个 k T1都满足参数 1 6 0 xnp 的二项分布 因此 3 1 2 1 1 1 TTT 服从参数 1 3 6 0 xnp 的二项分 布 因此要使 95 的会员需求得到满足 同样取置信度为 99 可得 99 0 395 0 11 3 1 2 1 1 1 xdTTTP 99 0 13 1395 0 13 3 1 11 1 1 3 1 2 1 1 1 ppx pxd ppx pxTTT P 类似前一部分的计算 可得到相应答案为 DVD1DVD2DVD3DVD4DVD5 422721721128596265 6 2 问题二 DVD的分配由两个阶段组成 第一阶段是对现有碟片资源按照订单以追求 满意度最大化进行分配 第二阶段是对第一阶段中一部分返回的碟片资源进行再 分配 从网站的角度看 要达到最大的满意度 最理想的情况是可以对第二阶段 归还的会员进行控制 则有如下规划 约束条件 10 61 5 4 31600 23 13 max 1000 1 1000 1 1000 1 100 1 100 1 orwuzy zy ywuxz xy wu wz uy zy iiijij ijij i ijiij i ij j i ij ii i j ij i j ij ji ijijij 其中约束条件 21保证每个会员每次获得0或3张DVD 3 表示有 60的 会员在一个月内租赁 2 次 4 表示第一阶段每种DVD的分配量不超过网站拥有 的该种DVD的数量 5 表示第二阶段每种DVD的分配量不超过第一阶段分配 后的直接剩余量与第一阶段分配量的返还量之和 6 表示不能把会员看过的 DVD再分配给同一会员 但是这个模型存在不合理性 在对第二阶段进行分配时 返还的对象及返还 的碟片数量的多少均是随机的 直接用 60这个期望值进行计算是不合理的 比较可行的做法是把 ij z看成随机变量 通过 ij z的分布列来表示约束 并以第二 阶段的最大期望满意度为目标进行规划 这样就导致整个规划的目标值也是一个 期望值 但是第一阶段的分配方法对于网站来说是完全可支配的 其规划如下 7 约束条件 10 13 max 1000 1 100 1 ory xy uy y ij j i ij i j ij ji ijij 对于这个规划 由于 i u也是10 变量导致问题求解困难 因此我们考虑对可 行域进行缩放 即把条件 1 分别改成 31 100 1 j ij y和 31 100 1 j ij y来求解 经 求解验证缩放的可行域中求得的最优值是一样的 由夹逼原理可知这个最优值原 来的可行域中的规划问题的最优解 具体结果见模型的求解 第二阶段规划 这一阶段是第一阶段的延续 考虑的是在第一阶段分配结束后 网站用剩下 的DVD加上会员返还的DVD来进行再一次分配的过程 但第二阶段的归还人和 数量是不确定的 一般来说不能以规划来进行求解 然而第二阶段求的实际上是 满意度的最大数学期望 则我们考虑以概率意义上来讲 网站能回收到借出DVD 的百分数在 60左右的小范围内浮动 因此我们考虑第二阶段初网站拥有各种 DVD的量是个定值 这是对满意度期望的一个很好近似 而此时的满意度矩阵 和发生了变化 新的满意度矩阵是第一阶段的满意度矩阵把在第一阶段中已经得 到满足的订单的满意度清零 就是说把第一阶段分配结果中1 ij y相对应的原满 意度矩阵中的非零元素 ij 改为零就得到了新的满意度矩阵 具体规划如下 约束条件 10 2 4 0 13 max 1000 1 1000 1 100 1 orz yxz uz z ij i ijj i ij i j ij ji ijij 1 表示第二阶段每个会员获得 0 张或 3 张 DVD 2 表示第二阶段每种DVD的分配量不能超过第一阶段分配后的直接剩余 量与第一阶段分配量的返还量之和 具体结果也参见模型求解部分 总的来说 上述分两阶段的规划实质上是用类似贪婪算法来计算理想的以最 大期望满意度为目标含有随机变量的规划模型 即分别考虑两个阶段的最优解 8 合成后的解即使不是最优解 也是一个较优解 3 问题三 解决这一小题时 可以先在第一题的基础上算出网站应该购买的DVD数量 再在上述DVD数量的限制上用第二题的方法算出满意度最大的分配方案 首先根据第一小题的方法算出DVD的购买量 j x 如下表 DVD 编 号 订购 数量 DVD 编 号 订购 数量 DVD 编 号 订购 数量 DVD 编 号 订购 数量 DVD 编 号 订购 数量 1562163417761628165 2612266426862678251 3572371436163698348 4652461445964718456 5522559456965648559 6582666466266698652 7582758476267598763 8662855485868638849 9612964496069698962 10593064506270669064 11623166517071639170 12643258526072699262 13563360536473569361 14673454546174549459 15563571556475599567 16623664566576579652 17673760577177589763 18603862585178659866 19663958595679549953 207640586067806410057 计算的规划如下 第一阶段 约束条件 10 3 max 1000 1 100 1 ory xy uy y ij j i ij i j ij ji ijij 9 第二阶段 约束条件 10 4 0 3 max 1000 1 1000 1 100 1 orz yxz uz z ij i ijj i ij i j ij ji ijij 这两个约束方程的主体思路与第二题类似 唯一的区别是原来的 j x需要用 j x即 新的购入量来取代 4 第四个问题的解决方案 1 作为网站管理人员 首要要考虑的是网站的收入来源 显然会费是一个重要 组成部分 因此会费如何定价问题也是值得研究的 由于邮费是单方由网站 支付 因此邮费就成为其最主要的支出 则邮费的所有最大可能支出必须小 于所收会费的总和 我们假设在一定时期内会员数量变动不是很大 于是有 max i iii wur 10 1 6 1 3 3 orwuzy zy ywuxz xy Xwu wz uy iiijij ijij i ijiij i ij j i ij ii i j ij i j ij 其中 i r是网站到第i个人的邮费支出 其他的约束条件实际上就是网站的租赁 10 要求 我们在上述规划中将 60实际当成了确定量来计算 因为要考虑的是 极端情形所以小概率事件也可以考虑在内 则在这种情况下算出的就是邮费 的一个上界 则定会费时总和一定要大于这个上界 2 既然有邮费的支出存在 作为盈利为目的的网站 肯定要使邮费的支出降到 极点 然势必会影响整体的满意度 而满意度是网站能否吸引会员 吸引广 告的重要指标 也就是说满意度是网站收入能力的度量 则作为网站管理者 势必应该结合考虑两方面的因素 max i i i ji ijij ury 10 3 ory xy uy ij j i ij i j ij 当然这只是第一阶段的情况 我们也可以像解答问题 2 那样对第二阶段也列 规划方程 其中 x 是满意度与经济效益的函数 肯定正相关 在实际操作 中可以把它看成一个线性函数 这样对求解也是有很大方便的 六 模型的解答 问题 1 的解答 保证 50的会员在一个月内能看到订购的 DVD 所需要的 DVD 购入量 DVD1DVD2DVD3DVD4DVD5 6840355018721008467 保证 95 的会员在三个月内能看到订购的 DVD 所需要的 DVD 购入量 DVD1DVD2DVD3DVD4DVD5 422721721128596265 问题 2 的解答 第二小题第一阶段内DVD的分配方案 会员编号DVD 编号DVD 编号DVD 编号 C00184198 C00264462 C003325080 11 C00471841 C005116668 C006195366 C007266681 C008313571 C0095378100 C010415585 C011596366 C01223141 C013217896 C014235289 C015135285 C016108497 C017475167 C018416078 C019668486 C020456189 C021455053 C022385557 C023298195 C024374176 C02596994 C026226895 C027505878 C02883437 C029263055 C030376298 最大满意度24746 1 M 第二小题第二阶段内DVD的分配方案 若表中数字为 0 说明没有分配到DVD 会员编号DVD 编号DVD 编号DVD 编号 C001118285 C002000 C003000 C00423680 C005213441 C00616410 C0078450 C008000 C0091700 C01014600 12 C01119610 C01275098 C013000 C0144300 C0156600 C0165500 C017500 C01812810 C0192500 C0201800 C021200 C02286950 C0234100 C0247200 C02523810 C02683910 C0272200 C028000 C02944890 C0307000 最大满意度9461 2 M 总的满意度34207 21 MMM 问题 3 的解答 第三小题第一阶段内DVD分配方案 会员编号DVD 编号DVD 编号DVD 编号 C00188298 C00264244 C00345080 C00471841 C005116668 C006161953 C00782681 C008157199 C0095378100 C010556085 C011195963 C0122731 C013217896 C014234352 C015138588 13 C01668497 C017475761 C018416078 C019678486 C020456189 C021455365 C022385557 C023298195 C024417679 C02596994 C026226895 C027224258 C02883482 C029304455 C03013762 最大满意度27000 1 M 第三小题第二阶段内 DVD 分配方案 会员编号DVD 编号DVD 编号DVD 编号 C00111149 C00256271 C003313290 C004234968 C005122134 C006276667 C007456682 C008173135 C009101770 C01054167 C011616682 C01254598 C013498092 C014424689 C015245270 C016104876 C01751131 C018121781 C019256690 C020183340 C02122550 C022258186 14 C023366775 C024374372 C025238190 C02688391 C02763850 C028464757 C029263389 C030708498 最大满意度18000 2 M 总的满意度45000 21 MMM 七 模型的优化 原模型中对于每次租赁的DVD有严格要求只能是3的倍数 这显然有其不 合理性 因为网站租赁还是以盈利为目的 其租赁DVD是要承担一定的风险的 比如会员的丢失或邮寄过程的差错使DVD不能归还 则租赁出的越多风险越大 虽然邮寄单张和三张费用无异 但如果寄出的是会员不想看的DVD 则该额外 的风险承担就没有价值 因此我们考虑网站一次租赁给个人的DVD数量可以不 是3的倍数 而且对模型的求解可以降低很大的规模 九 模型的评价与推广 在确定满意度时 仅考虑了喜好程度对满意度的影响 比较直观和简便 但 是不够全面 在计算最大满意度时使用的规划模型实际上是经过了简化 将 60 作为确定的百分比来处理 同时将一个月划分为两个周期 这个方法可以极大地 简化计算 尤其是该题中的海量数据 可以大大提高效率和普及率 但是这个方 法不够准确 可能会使结果偏离真实值 简单的以偏好程度来决定满意度 显然具有片面性 实际上用户的满意度会 受到很多方面的影响 如递送 DVD 的时间周期越短 用户满意程度会相应的提高 若多次未能满足会员的第一需要 会使会员对网站服务的整体期望下降 若递送 的 DVD 中错漏损坏过多 也会影响满意度 因此在实际的营销中要获得最大满意度还应该考虑以下的一些因素 另外在实际的网站运营中 位于网站所在地的会员往往是通过市内投递的方 式来交付 DVD 而非邮寄 这样可以提高运营周期节省邮递费用 参考文献 1 胡细宝等 概率论 数理统计 随机过程 北京 北京邮电大学出版社 2004 15 2 谢金星等 优化模型与 LINDO LINGO 软件 北京 清华大学出版社 2005 7 附录 1 运算机器配置 GHzMPentiumIntelCPU5 1 内存 MB512 计算软件 0 8Lingo 2 源程序 作用 计算第二小题第一阶段的分配方案及目标值 代码 model sets dvd d1 d100 n user u1 u1000 u link user dvd x a endsets data n file import1 100000 txt a file import2 100000 txt text c out2 1 txt x enddata max sum link x a for link bin x for user j sum dvd i x j i 3 for dvd i sum user j x j i n i end 作用 计算第二小题第二阶段的新的满意度矩阵 代码 model sets dvd d1 d100 d m user u1 u1000 u temp t1 t100000 t link user dvd x y a b endsets 16 data a file import2 100000 txt t file 123 txt text outm txt m text outb txt b enddata for dvd i for user j x j i t 100 j 1 i for dvd i sum user j x j i m i for dvd i for user j y j i not x j i for dvd i for user j b j i a j i y j i End 作用 计算第二小题第二阶段的分配方案及目标值 代码 model sets dvd d1 d100 n m user u1 u1000 u link user dvd b y endsets data n file import1 100000 txt m file outm txt b file outb txt text c out 2 2 txt y enddata max sum link y b for link bin y for user j sum dvd i y j i 3 for dvd i sum user j y j i n i 0 4 m i End 作用 计算第三小题第一阶段的分配方案及目标值 代码 model sets 17 dvd d1 d100 n user u1 u1000 u link user dvd x a endsets data n file import1 3 txt a file import2 100000 txt text c out 3 1 txt x enddata max sum link x a for link bin x for user j sum dvd i x j i 3 for dvd i sum user j x j i n i End 作用 计算第二小题第二阶段的新的满意度矩阵 代码 model sets dvd d1 d100 d m user u1 u1000 u temp t1 t100000 t link user dvd x y a b endsets data a file import2 100000 txt t file 1234 txt text outm1 txt m text outb1 txt b enddata for dvd i for user j x j i t 100 j 1 i for dvd i sum user j x j i m i for dvd i for user j y j i not x j i for dvd i for user j b j i a j i y j i end 18 作用 计算第二小题第二阶段的分配方案及目标值 代码 model sets dvd d1 d100 n m user u1 u1000 u link user dvd b y endsets data n file import1 3 txt m file outm1 txt b file outb1 txt text c out 3 2 txt y enddata max sum link y b for link bin y for user j sum dvd i y j i 3 for dvd i sum user j y j i n i 0 4 m i end 1 DVDDVDDVDDVD 在线租赁在线租赁在线租赁在线租赁 摘要摘要 对问题一 我们分两种情形来考虑并建立与求解模型 一方面 如果网站要在 概率意义上满足题中要求 那么从概率上讲每次寄发出去的 DVD 收回所需要的天 数服从泊松分布 据此建模与编程求解 并对求解时引进的参数进行灵敏度分析 另一方面 如果网站要求在最坏情况下也要满足题中要求 则要考虑最坏情况 建 模求解 对问题二 定义分配布尔变量 利用偏好程度定义顾客的满意度 进而将问题 转化为一个单目标 0 1 线性规划 在 Lingo8 0 上编程求解 对问题三 在保证题目中所要求的条件的前提下 要使得客户的总满意度最大 购买 DVD 的总数量最小 于是问题化为一个多目标 0 1 线性规划问题 我们通过 引进比例因子的方法把它化为一个单目标 0 1 线性规划问题 从而运用 lingo8 0 编程求解 并对引入的比例因子做了灵敏度分析 对问题四 提出对 DVD 需求量预测的更全面分析 考虑诸多影响因素 建立 灰色系统理论分析模型 利用 GM 1 1 预测模型对 DVD 的需求量进行合理预 测 关键字 关键字 泊松分布 单目标线性规划 多目标线性规划 Lingo 8 0 Visual C 灰色系统理论 GM 1 1 模型 合理建议 2 一 问题的重述 1 1 1 1 1 1 1 1提出背景提出背景 随着信息时代的到来 网络成为人们生活中越来越不可或缺的元素之一 许多网站 利用其强大的资源和知名度 面向其会员群提供日益专业化和便捷化的服务 例如 音 像制品的在线租赁就是一种可行的服务 在线 DVD 租赁就是这样一种传播范围广泛 直达核心消费群 强烈的互动性 感官性强 成本相对低廉的服务 1 1 1 1 2 2 2 2问题提出问题提出 客户缴纳一定数量的月费成为会员 通过在线提交订单 订购 DVD 租赁服务 会 员提交的订单包括多张 DVD 这些 DVD 是基于其偏爱程度排序的 网站会根据手头现 有的 DVD 数量和会员的订单进行分发 每个会员每个月租赁次数不得超过 2 次 每次 获得 3 张 DVD 在已知会员订单情况下 如何购买 分配这些 DVD 使会员满意度最 大且成本最低就成了自然而然的问题 另外 在 DVD 的需求预测 购买和分配中还存在很多其他问题值得研究 二 二 二 二 模型的假设模型的假设模型的假设模型的假设 1 会员在三个月内不会租赁同一种 DVD 2 如果客户没有预订某种 DVD 那么这种 DVD 决不会分配给他 3 每种 DVD 的购买单价是相同的 4 DVD 在流通过程中 短期内不会被损坏 三 符号的约定三 符号的约定三 符号的约定三 符号的约定 为了建模的方便 在每一问做答时约定相应的符号 3 四 四 四 四 模型建立及求解模型建立及求解模型建立及求解模型建立及求解 4 4 4 4 1 1 1 1问题一的解答问题一的解答 综述 对这个问题 我们分别从两种不同角度考虑问题 即从概率的角度与从最坏情 况的角度 前一种更贴近于实际生活 第一种角度 考虑从概率上保证满足要求 即对第一子问 从概率上保证希望看 到该 DVD 的会员中至少 50 在一个月内能够看到该 DVD 对第二子问 从概率上保 证希望看到该 DVD 的会员中至少 95 在三个月内能够看到该 DVD 并对此种情况时引进的两个参数 1 与 2 做了灵敏度分析 第二种角度 考虑最坏的情况 在最坏情况下 求出应购买每种 DVD 数量的 上界 即求出无论如何都能满足要求的购买数量 4 4 4 4 1 1 1 1 1 1 1 1 概率意义下讨论问题概率意义下讨论问题 对于每种 DVD 分开考虑 先求总流通量 即一个月内这种 DVD 被租赁的总次数 DVD 租出之后客户对 DVD 的保留天数服从泊松分布 1 即客户收到 DVD 后 第 k 天寄回的概率为 e k kP k 为 k 的数学期望 将会员分为两类 1 每月租一次 DVD 的 记为集合 1 G 2 每月租两次 DVD 的 记为集合 2 G 对 1 G和 2 G 的取值不同 分别设为 1 与 2 则其概率密度分别记为 1 1 1 e k kP k 与 2 2 2 e k kP k 根据历史数据 60 的会员每月租赁 DVD 两次 而另外的 40 只租一次 则 可认为 DVD 每次分配 DVD 时 有 40 分配到 G1 60 分配到 G2 利用如下方法确定一个月内 DVD 的总流通量 即一个月内所有的 DVD 的流 通次数 第二天 将第一天发放 此时收回的 DVD 再寄出去 则客户保留 DVD 的天 数仍然服从泊松分布 第三天 将第一天发放 此时收回与第二天发放 此时收回的 DVD 再寄出去 客户保留 DVD 的天数仍然服从泊松分布 4 第 k 天 将第一天到第 k 1 天发放 此时收回的 DVD 再寄出去 客户保留 DVD 的天数仍然服从泊松分布 这样 把一个月内每天发出去的 DVD 数量求和 就得到了这种 DVD 在一个 月内的总流通量 设需购买某种 DVDS张 预订该 DVD 的人数为T 设第 k 天寄出 DVD k A张 k 1 2 30 则有 SA 1 6 0 1 4 0 1 6 0 2 4 0 2 6 0 1 4 0 1 211 212211 kPkPA kPkPAPPAA kk 要保证预订该 DVD 的会员中至少 50 在一个月内能够看到该 DVD 只要 5 0 30 1 TA k k 下面讨论 1 与 2 的确定方法 可以综合下面的两种途径来确定 1 与 2 1 可参考租赁公司的历史租赁记录 2 可在订单中加入一个调查 即 如果您每个月只租一次 您可能几天归还 DVD 如果您每个月租两次 您可能几天归还 DVD 以 此来统计并寻找规律 通过对互联网上的大量信息的统计 2 我们得出 1 与 2 的大约值如下 1 7 天 2 13 天 随后将做灵敏度分析 即 1 与 2 在此值附近变动时 结果的变化情况 对于每种 DVD 分别用上述方法编程即可计算出精确结果 程序 用 C 语 言 运行环境为Visual C 程序见附录 1 已知每个 T 的值如下 1 T 2 T 3 T 4 T 5 T 2000010000500025001000 5 计算得到各个 S 的值如下表 1 S 2 S 3 S 4 S 5 S 29121456728364146 4 4 4 4 1 1 1 1 2 2 2 2 灵敏度分析灵敏度分析 考虑 1 与 2 的以下几组取值 得出相应的结果如下 a a a a 1 6 2 13 1 S 2 S 3 S 4 S 5 S 28331417709355142 b b b b 1 8 2 13 1 S 2 S 3 S 4 S 5 S 30111506753377147 c c c c 1 7 2 12 1 S 2 S 3 S 4 S 5 S 27791390695348139 d d d d 1 7 2 14 1 S 2 S 3 S 4 S 5 S 30421521766383154 可以看出 1 与 2 在所取值附近变化时 1 S的取值都在 2800 3000 左右浮动 6 对于第二个子问题 可用相同方法求解 此时应满足95 0 90 1 TA k k 运行程序得到各个 S 的值如下表 此问题相应的 C 程序见附录二 1 S 2 S 3 S 4 S 5 S 21221061531266107 此问题相应的灵敏度分析略 与第一子问题类似 4 4 4 4 1 1 1 1 3 3 3 3 考虑最坏情况考虑最坏情况 设购买第 i 种 DVD 的数量为 i S 预订第 i 种 DVD 的人数为 i T 首先求出每种 DVD 在一个月内的最坏的流通总量 即一个月内这种 DVD 被 租赁的最少的总次数 最坏情况下 对于每一张 DVD 它一个月内只流通一或两次 一个月内流通 两次的概率为 60 流通一次的概率为 40 据此求得第 i 种 DVD 一个月内的最 坏的流通总量为 1 4 0 2 6 0 ii SS 要保证希望看到该 DVD 的会员中至少有 50 在一个月内能看到它 也就是说 这种 DVD 在一个月内的最坏流通总量要大于等于希望看到该 DVD 总人数的 50 即 5 0 1 4 0 2 6 0 iii TSS 由 i T计算得到各个 S 的值如下表 1 S 2 S 3 S 4 S 5 S 625031251563782313 我们指出这只是保证在最坏情况下也能满足要求的数据 实际生活中取这样值 7 的可能不大 存在浪费 对第二个子问题 同理 要保证希望看到该 DVD 的会员中至少有 95 在三个 月内能看到它 等价于 95 0 1 4 0 2 6 0 3 iii TSS 由 i T计算得到各个 S 的值如下表 1 S 2 S 3 S 4 S 5 S 39591980990495198 4 4 4 4 2 2 2 2 问题二的解答问题二的解答 设已有的第i种 DVD 的数量为 i S 预订第i种 DVD 的人数为 i T 设分配布尔变量 ij X 即如果第i张 DVD 分配给第j个客户时 ij X取值为 1 否 则为 0 我们用客户对每种 DVD 的偏爱程度来定义客户的不满意度如下 即如果客户偏爱程度为 k 的DVD得到供应 则不满意度为k k 1 2 10 0 k时 不满意度为无穷大 因为如果客户没有预订某种 DVD 那么这种 DVD 决不会分配给他 记给出的订单为矩阵A 令 ij XX 记 AXP为矩阵AX中所有元素之和 那么 AXP即为客户的总不满意度 这次分配只是一次邮寄 所以应有条件 每个客户分配到 DVD 的总数量不多 于 3 张 但解得的结果表明大于 99 以上客户得到了 3 张 DVD 即 3 100 1 i ij X 由于 i S与 i T已知 记 min iii TSR 要取最优值 必要求i j ij RX 1000 1 此时问题二归结为下面的 0 1 线性规划问题 4 8 minAXP ts 1 0 1000 2 1 3 100 1 1000 1 100100 1000 1 22 1000 1 11 ij i ij j j j j j j X jX RX RX RX 经统计得已知 i S与 i T的数值如下表 101 SS 10401520201230333525 101 TT 849287997887871009390 2011 SS 2931286122828263138 2011 TT 959785102849410291100116 3021 SS 3429352229811192541 3021 TT 96101109938910187839797 4031 SS 293514039510630292 4031 TT 1008791821099791948787 5041 SS 1106153634113225264 5041 TT 11910493901069494889194 6051 SS 4026332661211384436 6051 TT 10791989297991087785103 7061 SS 27314244128110353330 7061 TT 94103105108981059096105101 9 8071 SS 240151128242088928 8071 TT 951068582908688998298 9081 SS 31822370213443827 9081 TT 99777284907895739498 10091 SS 3928241550243655240 10091 TT 10794939010278951018086 应用 Lingo8 0 3 求解 程序段见附录 3 解得 minAXP 7706 列出前 30 位客户所获得的 DVD 如下表 C001C002C003C004C005C006C007C008C009C010 8632711198315355 41445018665326357860 986280416866817110085 C011C012C013C014C015C016C017C018C019C020 5922123135547416645 63317852668452608461 66419689859767788689 C021C022C023C024C025C026C027C028C029C030 453829379225082637 50558141696858343062 53579576819578375598 4 4 4 4 3 3 3 3 问题三的解答问题三的解答 设第 i 种 DVD 的购买数量为 i S 预订第 i 种 DVD 的总人数 i T 设分配布尔变量 ij X 即如果第i张 DVD 分配给第j个客户时 ij X取值为 1 否则 为 0 对题目中 一个月内会员得到他想看的 DVD 的理解 把会员分为两类 1 一个月只租一次的会员 1 G 即会员一个月内不还 DVD 那么我们说这 10 类会员 得到了他想看的 DVD 是说他得到一次即可 2 一个月内租两次的会员 2 G 即会员会还一次 DVD 并得到第二次邮寄 那么我们说这类会员 得到了他想看的 DVD 是说他要得到两次 由已知 1 G中的客户占总数的 40 2 G中的客户占总数的 60 要在概率上保证一个月内 95 的会员得到他想看的 DVD 即下两式 95 0 3000 100 1 k k S 对于会员的不满意度定义同问题二 记给出的订单为矩阵 A 令 ij XX 记 AXP为矩阵AX中所有元素之和 那么 AXP即为客户的总不满意度 在满足题目中的前提的条件下购买 DVD 的总数量当然是越少越好 这次分配是重新安排每种 DVD 的数量 所以应有条件 每种 DVD 都被充分利用 即 1000 1j iij SX 那么问题三归结为下面的多目标 0 1 线性规划问题 4 minAXP 100 1 min i i S ts 1 0 95 0 3000 1000 2 1 03 100 2 1 100 1 100 1 1000 1 ij k k i ij j iij X S jorX iSX 11 要解这个多目标0 1线性规划问题 我们把它化为单目标0 1线性规划问题 方法如下 要把两个目标函数化为一个 关键是寻找两个量之间比例因子 我们借助于问 题二中的结果来决定这个系数 在问题二中解得 minAXP 7706 而那时的 DVD 的总数量为 3007 所 以 我 们 可 以 假 定 minAXP 与 100 1 min i i S 的 比 例 因 子 为 7706 3007 2 563 后面我们会考虑此比例因子的变化对结果造成的影响 即灵敏 度分析 于是原问题化为如下的单目标 0 1 规划问题 100 1 563 2 min i i SAXP ts 1 0 95 0 3000 1000 2 1 03 100 2 1 100 1 100 1 1000 1 ij k k i ij j iij X S jorX iSX 已知 i T的值如下表 T1 T10849287997887871009390 T11 T20959785102849410291100116 T21 T3096101109938910187839797 T31 T401008791821099791948787 T41 T5011910493901069494889194 T51 T6010791989297991087785103 12 T61 T7094103105108981059096105101 T71 T80951068582908688998298 T81 T9099777284907895739498 T91 T10010794939010278951018086 应用 lingo8 0 求解 程序段附在后面附录四里 解得 i S的值如下表 S1 S1026363138273130333530 S11 S2030312831273834303238 S21 S3034303527293128252641 S31 S4033353131393526302928 S41 S5053353035382832283234 S51 S6040263326313431283436 S61 S7027333235323732353332 S71 S8036342531282426313130 S81 S9032242223332534242732 S91 S10039292829402436332335 i S的总合为 3139 张 15278 563 2 min 100 1 i i SAXP 总不满意度为 7589 这说明 DVD 的数量的结构得到了很大的优化 灵敏度分析 灵敏度分析 若取 2 4 求得 i S如下表 S1 S102637