精品范文模板 可修改删除撰写人：_日 期：_DVD在线租赁决策优化模型摘 要：本文建立了关于DVD在线租赁业务一系列问题的数学模型。首先，建立概率模型，并得到DVD的最少需求数量。接下来给出了目标规划模型建立最优分配方案，在模型的求解过程中，先后给出了三种近似算法：模拟退火算法、贪婪算法和改进贪婪算法。再建立一调度模型使得DVD数量最少，分配方案最优。本论文所建模型理论基础较完善，算法简洁快速，可操作性强，在计算机上对给定数据可以实时得到结果，因此有较强的实用性；并且只需经过简单的修改便可解决类似问题，易于推广。关键词：DVD在线租赁；正态分布；线性规划；贪婪算法；模拟退火算法; 改进贪婪算法The policy-making optimization model about DVD on-line rentsAbstract: This article established on-line has rented service a series of questions about DVD the mathematical model. First, establishes the probabilistic model, and obtains DVD the least demands quantity. Met down has produced the target programming model establishment most superior assignment plan, in the model solution process, has produced three approximate methods successively: Simulation annealing algorithm, greedy algorithm and improvement greedy algorithm. Again establishes a dispatch model to cause the DVD quantity few, the assignment plan is most superior. The present paper modeling rationale consummates, the algorithm succinct is fast, feasibility, to assigns the data on the computer to be possible real-time to obtain the result, therefore has the strong usability; And only must pass through the simple revision then to be possible to solve the similar problem, is easy to promote.Key words: DVD on-line rents; Normal distribution; Linear programming; Greedy algorithm; Simulation annealing algorithm; Improves the greedy algorithm 一、绪论随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。音像制品的在线租赁就是一种可行的服务。考虑如下的在线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来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD呢？2、表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单（表2的具体数据可从http:/mcm.edu.cn/mcm05/problems2005c.asp下载），如何对这些DVD进行分配，才能使会员获得最大的满意度？要求具体列出前30位会员（即C0001C0030）分别获得哪些DVD。3、继续考虑表2，并假设表2中DVD的现有数量全部为0。如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4、从网站经营管理人员的角度考虑在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？提出问题，并尝试建立相应的数学模型。表1 对1000个会员调查的部分结果DVD名称DVD1DVD2DVD3DVD4DVD5愿意观看的人数200100502510二、模型假设和符号说明（一）模型假设1、租赁周期为半个月或一个月，凡半个月内还回DVD的会员均认定为每个月租赁2次的会员，否则为只租赁1次的会员；2、每个会员每个月只能提交一次订单，提交订单时间为上月月末；3、一个月为30天，分为上半个月和下半个月，每月的1日和16日网站根据用户订单对DVD进行分配； 4、会员租赁成功是指该会员必须获得3张DVD且此3张DVD均为该会员在订单中所选中的，否则均为租赁不成功；5、租赁不成功即认为没有得到想看的DVD；6、每个人每张碟月内只租一次；7、网站在每次出租DVD碟的时候，将手头上的碟要尽可能的租出去；8、会员提交的定单包括多张DVD碟，这些DVD碟是根据会员的偏爱程度来排序的； 9、网站每次进行分配时，只考虑网站现有DVD张数；10、网站只在每月的1日购买新碟，其余时间均不购碟；11、不愿意观看某种DVD碟的会员不会租看该DVD碟；12、不考虑碟片在流通和使用过程中的自然损坏、遗失；13、会员对DVD碟的偏爱程度由0，1，10来表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。 （二）符号说明 ：第i种DVD碟应准备的数目； ：将第i种DVD碟第k次给第j类会员的数目，k=1,6;j=1,2； ：第i种DVD碟愿意观看的人数； ：第号会员租赁期结束对网络公司服务的满意度，；：群体满意度；：第号会员对第种DVD的偏爱程度 ；：第号会员对第种DVD的偏爱程度指标，且 ，；：第号会员是否租赁到第种DVD，若是，则取值为1；否，则取值为0，； ：第种DVD的购买量 ，；：在一月内可使至少95%的会员租赁到第种DVD的最小碟数（由问题1的计算知它可看作的上限）；：第i种DVD碟每月租出的次数；：网站现有会员的人数；：第种DVD被选中的概率；：第种DVD没被选中的概率；：每月租赁DVD一次的会员的比例；：每月租赁DVD二次的会员的比例；：第种DVD应准备的数量；：一个月内对第种DVD；：DVD每月可用次数的数学期望值;:某月内对第种DVD需求的人数上限。三、模型的建立与求解（一）问题1考虑到会员租碟的实际情况，表1 中给出的选择某种DVD 的人数可以认为是某月选择该DVD 人数的数学期望,每月实际选择该DVD 的人数会在其周围波动,我们认为对第种碟片的总需求可以用正态分布近似(此处),可以算出第种DVD 的需求人数上限(在一定置信区间下,这里我们选取0.95)，只要在租借过程中满足上限的一定人数比例 (50%)即可,假设第种DVD 购买张。我们考虑需要DVD 最多的情况：借一次的会员在一个月的最后一天归还，借两次的会员在一个月的最后一天第二次归还，那么对于一张碟来说借一次的会员使得它流通了一次,而借两次的会员使得它流通了两次,这相当于该DVD 的每月可用次数为，对于本题目来说，即，要求一个月至少有需求的会员能得到满足，即 (1) 求出的最小值。用Matlab 求得置信度为0.95 下的上限值分别为：带入公式(1)解得：对于三个月的情况,想当于一个月情况的三次累积,三个月的DVD 流通次数是一个月的3倍, 上限 值不变,所得公式为： (2)代入数据计算得（二）问题2表2中给出了会员对想看的碟的偏爱程度，因此我们可根据会员对碟的偏好程度定义其满意度，定义如下：定义1（个体满意度） 如果单个会员作为个体租赁了该网站三张DVD且全都是自己选中的DVD，那么其个体满意度为该个体对这三张DVD的偏爱程度指标之和除以30所得百分比；若未能租到三张或三张中有未被个体选中的DVD，则其满意度为0。即. 定义2（群体满意度） 所有个体满意度之和，即为=。问题2的目标规划模型为： max =s.t. ;1、模拟退火算法近似求解算法步骤： 给定起止“温度”，、和退化速度；模拟参数初始化； 若，转，否则算法停止，输出，并计算； 计算目标函数； 随机产生，若则正向调整，否则反向调整 判断是否满足约束条件，若满足，转，否则转； 计算目标函数，若，接受新值，转；否则若，也接受新值，转；否则转 算法程序见附录3。由于模拟退火算法不能在短时间给出问题2的最优解，我们尝试用别的算法来代替模拟算法以求得相对较好的解，近似作为问题2的最优解。这里我们选择贪婪算法，主要是因为它能在少量计算的基础上，可在正确猜想且不用急于考虑以后的情况下，来一步步地构筑解，每一步均可建立在局部最优解的基础上，而每一步又可扩大了部分解的规模，做出的选择产生最大的直接收益。这对于网站经营者来说是其操作性比较强，且实用性也比较强，因此这种算法对于本题应当是非常有效的。2、贪婪算法求解问题2中只需要考虑在DVD现有数量给定条件下要求出会员获得最大满意度，我们暂不考虑在半个月后会员所租DVD的归还与否以及后半个月会员的租赁情况。而只考虑会员个体满意度在前半月租赁期的大小。要满足达到最大的个体满意度，经分析，我们可以将其转化为：使得每一种DVD的每一张都能优先满足偏爱程度高的会员。（1）算法基本思想第一次分配（针对各种DVD中偏爱程度为1所对应会员进行分配）先考虑偏爱DVD1程度为1的各个会员，若全能满足，则将DVD1进行分配，若不够，可选取会员号排序靠前的会员，并将DVD1全部进行分配；再分配DVD2，考虑偏爱DVD2程度为1 的会员，若全能满足，则将DVD2进行分配，若