DVD在线租赁问题数学模型

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,数学模型,DVD,在线租赁问题数学模型,(CUMCM2005-B-D,题,),1,问题提出,1,问题分析,2,假设条件,3,模型建立与求解,4,模型评价,5,DVD,在线租赁问题数学模型,DVD,在 线 租 赁 问 题 数 学 模 型,2,DVD,在 线 租 赁 问 题 数 学 模 型,随着信息时代的到来,电子商务已成为一个重要的商业途径。在线,DVD,租赁就是其中一种典型的经营方式，但在实际的经营过程中还是存在很多问题。下面我们从复杂的现实情况中考虑一个典型的情景。,鉴于业务量的考虑，网站有必要采用会员制度，顾客需缴纳一定数量的月费成为会员。,会员对哪些,DVD,有兴趣，只要在线提交订单，网站就能立即了解他们的需求，并通过快递的方式尽可能满足要求。会员提交的订单内容包括他对哪几张,DVD,感兴趣，对不同的,DVD,的偏爱度，用数字表示。这些,DVD,是基于其偏爱程度排序的。网站会根据手头现有的,DVD,数量和会员的订单进行分发。,每个会员每个月租赁次数不得超过,2,次，每次获得,3,张,DVD,。会员看完,3,张,DVD,之后，只需要将,DVD,放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。,问题提出,3,DVD,在 线 租 赁 问 题 数 学 模 型,为深入研究网站的经营策略，我们从以下几个角度由浅入深地进行考察：,1,）至少准备多少张，才能保证希望看到该,DVD,的会员中,至少,50%,在一个月内能够看到？若要求保证在三个月,内至少,95%,的会员能够看到呢？,1,、由于,DVD,的更新速度很快，网站必须时常更新现有产品，因此在现有会员中随机抽取,1000,个会员进行调查，以得知愿意观看不同,DVD,的人数（表,1.1,给出了其中,5,种,DVD,的数据）。虽然网站规定每位会员每月只能借两次,DVD,，但从历史数据显示，,60%,的会员每月租赁,DVD,两次，而另外的,40%,只租一次。现在我们假设网站现有,10,万个会员，并已经知道会员对,DVD,的需求，以及会员每月订,DVD,的规律。问题是应该至少准备多少张，才能保证希望看到该,DVD,的会员中至少,50%,在一个月内能够看到？如果要求保证在三个月内至少,95%,的会员能够看到呢？,DVD,名称,DVD1,DVD2,DVD3,DVD4,DVD5,愿意观看的人数,200,100,50,25,10,表,1.1,对,1000,个会员调查的部分结果,问题提出,4,DVD,在 线 租 赁 问 题 数 学 模 型,为深入研究网站的经营策略，我们从以下几个角度由浅入深得进行考察：,1,）至少准备多少张，才能保证希望看到该,DVD,的会员中,至少,50%,在一个月内能够看到？若要求保证在三个月,内至少,95%,的会员能够看到呢？,2,）如何对手中已有的,DVD,进行分配，以使所有会员的满,意度和达到最大。,2,、,尽可能多的满足会员是经营中的一大目标，但每个会员对不同DVD的偏爱度是大相径庭的，虽然他们都对该DVD下了订单，但最后得到该张DVD收到的效果差别,很大，所以还要考虑会员满意度的问题。表,1.2列出了网站,中,20种DVD的现有张数和当前需要处理的100位会员的在线订单。如何对手中已有的DVD进行分配，以使所有会员的满意度和达到最大,？,D001,D020,表示,20,种,DVD, C0001,C0100,表示,100,个会员，会员的在线订单用数字,1,2,表示，数字越小表示会员的偏爱程度越高，数字,0,表示对应的,DVD,当前不在会员的在线订单中。,表,1.2,现有,DVD,张数和当前需要处理的会员的在线订单（表格格式示例）,DVD,编号,D001,D002,D003,D004,DVD,现有数量,8,1,22,10,会员在线订单,C0001,0,0,2,0,C0002,1,0,9,0,C0003,0,6,0,0,C0004,0,0,0,0,C0005,5,0,0,0,问题提出,5,DVD,在 线 租 赁 问 题 数 学 模 型,为深入研究网站的经营策略，我们从以下几个角度由浅入深得进行考察：,1,）至少准备多少张，才能保证希望看到该,DVD,的会员中,至少,50%,在一个月内能够看到？若要求保证在三个月,内至少,95%,的会员能够看到呢？,2,）如何对手中已有的,DVD,进行分配，以使所有会员的满,意度和达到最大。,3,）作为网站经营管理员，如何决定每种,DVD,的购买量，,以及如何对这些,DVD,进行分配，才能使一个月内,95%,的会员得到他想看的,DVD,，并且满意度最大呢？,问题提出,3,、,在实际的经营过程中，不可能像刚才讨论的两个问题这么简单，我们不可能将顾客的满意率与他们的满意度割裂开来分开研究，可以说这是两个问题是相互牵制的关系。假设表1.2中DVD现有数量全部为0。作为网站经营管理人员，如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大呢？只有弄清楚这个问题，我们才能初步的对DVD在线租赁问题有个认识。,6,DVD,在 线 租 赁 问 题 数 学 模 型,问题一类似于“货物存储问题（,Inventory problem,）”，基本思路是跟踪DVD在一个月（三个月）内的流动情况，目标是计算出DVD的流转次数，然后再结合满意率要求得出所需准备的DVD数量。,问题二类似于“,分配问题”或“指派问题（,Assignment problem,）”，我们可以对偏爱度进行适当的处理以满足我们的要求。0-1规划是处理,该问题的最佳方法，因此如何使用这一方法将是研究问题二的关键。,问题三看似是问题一与问题二的结合,（存贮,+,分配），但实际要复杂得多。他综合考虑一个月内,DVD的购买、分配方案，是一个多目标线性规划。从经济效益看，在保证95%以上会员一个月内看到想看的DVD的情况下，希望购买尽量少的DVD，从社会效应看，则要尽可能多地考虑让总的满意度最大。,这时，可以将多目标变为单目标规划，以求得一个经济与社会效益的综合最优。由于问题三牵涉到两次分配，而对会员满意率的理解又有多种解释，因此目标及约束函数会和问题一、问题二有很大差别。,而问题三的模型又可从当前满意度最大和一段时间内满意度最大两个角度来考虑。,问题分析,7,1.,对,1000,名会员的调查足以反映,10,万名会员对于各种,DVD,的需求及喜好,2.,所有会员提交订单的时间是随机的,3.,一个月的天数为,30,天,4.,会员中有,60%,的会员每月租赁,DVD,两次，,40%,的会员每月租赁,DVD,一次,5.,会员只有在需要再次租赁,DVD,时，才会将上次租赁的,DVD,归还,6.,会员临近两次借的,DVD,种类不会重复,7.,每位会员每月至少租赁,1,次,8.,会员本次提交后没得到该,DVD,，则他下次仍要看该,DVD,，且偏爱度不变,9.,每类租赁出的,DVD,有,60%,在每月租赁,2,次的会员中，,40%,在每月租赁,1,次的会员中,10.,公司收到订单时不知道此会员在一个月内会借一次或两次,DVD,在 线 租 赁 问 题 数 学 模 型,假设条件,在实际建模中还会遇到其他问题，比如问题一中可以淡化会员每次借三张的条件，即会员每次借的,DVD,数量不固定；问题二中不考虑多次分配的问题；问题三中对顾客满意率的不同理解。因此，我们将在以下的讨论具体问题时再给出。,8,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,：所有会员中愿意观看第 种,DVD,的人的概率,：所有会员中每月借,2,次的人的概率,：需要满足的会员比例,：会员总数,：第 个会员对第 种,DVD,的偏爱程度,：第 个会员对第 种,DVD,的满意度,：分配变量， 表示第 个会员得到第 种,DVD,，否则为,0,：网站第 种,DVD,的现有数量,其余特殊的变量将在后面的讨论中具体说明,符号与变量说明,9,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题一的模型与求解,问题一是简化的情形，在制定方案时，暂时不考虑每个会员每次最多借,3,张,DVD,的限制，也不考虑各种,DVD,间产生的影响及数量间的横向联系，单独考虑每种,DVD,的准备量。,如上所述，我们称每个月只租赁一次,DVD,的会员为,1,类会员，每个月租赁两次的会员为,2,类会员。虽然借一次和两次的会员并不固定，但其占总体会员的比例是一定的。由于每个月租赁两次,DVD,的会员的不确定性，无法预知每种,DVD,到底会借给哪类会员。因此，在制定购买方案时我们分别考虑均值估计及其它估计两种方式。,问题一包含两个部分，一是至少准备多少张,DVD,，才能保证希望看到该,DVD,的会员中至少,50%,在一个月内能看到；二是至少准备多少张,DVD,，才能保证在三个月内至少,95%,的会员能够看到该,DVD,。我们分别称上述两种情况为“一月情况”和“三月情况”。“三月情况”是“一月情况”的延续。,10,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题一：,均值情况估计,一月,由于抽样调查的随机性，这种保证可理解为在一定置信水平下的保证，即在一定置信水平下计算希望看到该,DVD,的会员人数的上限。,10,万会员中对,该,DVD,的需求服从二项分布，,简单地取二项分布的均值。,一个月内,DVD,的流通量为月初购买量的,1.6,倍，称这个“,1.6”,为“一月流通系数”。那么,DVD,一个月最小购买量可通过以下公式来计算：,11,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题一：,均值情况估计,一月,由表,1,得到,1000,人中愿意观看每种,DVD,的概率分别为：,由于这,1000,人为,10,万人的子样本， 也可表示,10,万人中愿意观看每种,DVD,的概率。则 表示,10,万人中愿意观看第 种,DVD,的人。经计算，各种,DVD,的最少月初购买量为：,总的最少购买量,S=12033,DVD,名称,DVD1,DVD2,DVD3,DVD4,DVD5,购买量,6250,3125,1563,782,313,12,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题一：一个月,一个月内至少,50%,的会员能看到该,DVD,：,经计算，各种,DVD,的最少月初购买量为,DVD,名称,DVD1,DVD2,DVD3,DVD4,DVD5,0.95,6316,3174,1598,807,329,0.99,6343,3195,1613,818,336,13,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题一：三个月,三个月内至少,95%,的会员能看到该,DVD,：,经计算，各种,DVD,的最少月初购买量为,DVD,名称,DVD1,DVD2,DVD3,DVD4,DVD5,0.95,4000,2011,1013,512,209,0.99,4017,2024,1022,518,213,14,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题二的模型与求解,问题二是在现有一定数量,DVD,的前提下，如何分配以使会员总的满意度最大。这与“分配问题”或“指派问题（,Assignment problem,）”有很多相同点。,我们可以通过一些变化来使求解“分配问题”的模型能运用于该问题。,我们把问题二中“,100,个会员对,DVD,的需求” 理解为“需要完成的,100,项任务”，“,20,种,DVD,数量”理解为“有 个人可以承担这些任务”，“会员对于不同,DVD,的偏爱度”理解为“不同人去完成不同工作的效率”，通过类比就能把分配问题的模型运用到问题二中了。,分配问题最常用的方法是,0-1,型整数规划。在具体使用前，还需要将每个会员对不同,DVD,的偏爱度转化为满意度。因为我们的目标是总体满意度最大。,从表,1.2,中可以看到：会员的在线订单用数字,1,2,表示，数字越小表示会员的偏爱程度越高，数字,0,表示对应的,DVD,当前不在会员的在线订单中。通过观察我们用一个大于,9,的固定数值来减偏爱数,把这个差值作为满意度。,15,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题二,:,参数定义,1,、设矩阵 为偏爱度矩阵，矩阵中的元素 为表,1.2,中的偏爱数，表示第 个会员对 的偏爱数。 越小表示会员的满意程度越高， 为,1,时最高，为,0,时表示客户没有下订单。于是就得到了偏爱度矩阵,2,、设矩阵 为满意度矩阵，矩阵中的元素 为满意度，表示第 个会员对第 的满意度。 可通过如下算法获得：,3,、令 为分配变量， 表示第 个会员得到 ； 表示 未分配给第 个会员。由此得到我们要求的分配矩阵,通过矩阵 就能应用0-1规划进行求解,。,4,、令 表示 的现有数量，则有数量矩阵,5,、令 表示所有会员满意度的总和，我们的目标就是求出其最大值。,16,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题二,:,模型建立,1.因为表1.2中的数字0意义特殊，不直接与满意度产生关系。0代表该DVD没有出现在订单中，即会员不需要看该DVD。从分配费用考虑，避免把该DVD分配给会员。根据 的定义，不妨认为： ，则 时， 也等于0，即避免了上述情况的发生。,2.由于一次最多只能借3张，那么就有：,，又,分配给各会员的数量肯定不超过现有数量 ，所以：,。,由以上分析可得问题二的模型：,用,LINGO,数学软件实现对此题0-1规划模型的求解。,17,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题二,:,模型改进,-约束条件改进,根据上述模型的求解，我们发现又些会员没有分配到3张DVD，即他们的需要没能被满足。从网站的社会效益考虑，这样的情况会导致网站客户的流失。所以希望在满足所有会员都能借到3张DVD的前提下，再通过会员总满意度最大来决定分配方案。这就需要对上面的模型做一些改进。,我们可以将,改为 ，则得到模型,18,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题二,:,模型改进,-约束条件改进,以上修改，约束条件加强了，可能导致模型无可行解。事实通过,LINGO,程序也发现该模型无解。因为约束条件中规定了不能分配给会员不要的,DVD,，而会员每次都被分到,3,张，则网站至少有,300,张,DVD,，而现仅有,303,张，只比最低限度多,3,张，则当某,DVD,需求较大时就会供不应求。所以要放宽条件,1,，才能找到最优解。,最优值在第,165,次迭代后得到,Z=2024,。以上两个模型的结果是相同的，由于约束条件的放宽，后一个模型的迭代次数较少，则在说明每个会员一次能借到,3,张,DVD,不会影响会员整体满意度，而且从模拟结果看，改进后的对原有分配策略影响不大。,19,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题二,:,模型改进,-,满意度定义,改进,以上的讨论都是基于用一个固定数去减会员偏爱数作为满意度来分析的。但存在一定的不合理性。比如，当看到了最想看的,DVD,时，心理上满足是非常大的 ，但当仅仅得到了第二想看的,DVD,，那满足感会大打折扣，而如果仅得到了第三想看得,DVD,，满足感会更低，但与仅获得第二想看的,DVD,相比，也许失落感并不会如没有获得第一想看的,DVD,那么大。所以，如果只是简单得把会员订单中的,DVD,进行了相同差别的处理，无法表示出会员的真实满意度差别。所以我们想到了用偏爱数的倒数来表示会员的满意度，对满意度矩阵 的元素 重新定义：,把新定义的满意度代入上述模型中，并由,LINGO,程序计算，最优值在第,54,次迭代后得到,Z=153.9984,。我们对分配策略的分析发现，该结果与上一个模型相比并没有太大的变动，这是因为两种满意度的定义其实质是一样的。,20,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三的模型与求解,在现实的网站经营中需要综合考虑问题一、二，这就需要我们进一步讨论问题三的模型，它需要考虑两次分配方案，但我们可以简化为仅考虑当前时间点下如何用最小的,DVD,购买来满足,95%,的会员并找出最佳分配方案使会员总满意度最大。那么如何将这两个目标同时放入一个目标函数呢，最简单的方法就是相加。,由问题二知道，目标是使所有会员满意度总和 尽可能地大，而且每种,DVD,数量 是固定的，但问题三中,DVD,的购买量是自己定的，因此设置一个新的变量 表示当前需要购买,的数量， 则表示总的购买数量，而且从盈利角度考虑总的购买数量越小越好。所以我们可以将目标函数定如下：,21,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,等权情况,（,会员总体满意度与DVD购买量权重相等,）,针对“使一个月内,95%,的会员得到想看的,DVD”,的要求，可以参照问题一的处理方法，从表,1.2,中统计出原意观看 的人数占全体会员比例。结果如下：,由问题一的流通量可得,由于网站可自由决定其,DVD,的购买量，则有,DVD,名称,DVD1,DVD2,DVD3,DVD4,DVD5,DVD6,DVD7,DVD8,DVD9,DVD10,愿意观看人数,53,37,46,34,37,42,42,48,41,51,占全体会员比例,0.53,0.37,0.46,0.34,0.37,0.42,0.42,0.48,0.41,0.51,DVD,名称,DVD11,DVD12,DVD13,DVD14,DVD15,DVD16,DVD17,DVD18,DVD19,DVD20,愿意观看人数,48,41,43,45,52,41,43,45,44,31,占全体会员比例,0.48,0.41,0.43,0.45,0.52,0.41,0.43,0.45,0.44,0.31,为了计算上的方便直观，我们选择用,10,减会员偏爱数的来定义会员满意度。并建立模型。,最优值在第,85,次迭代后得到,:Z=1878,22,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,不,等权情况,（,会员总体满意度与DVD购买量权重,不,相等,）,如果不考虑会员总体满意度与,DVD,购买量之间的权重差异，这会导致其中某个目标对整个函数的影响被过分得夸大，所以有必要进行标准化。,1,、先来看 的最大值和最小值,对于当前的分配，最理想的是每位会员都得到了最想看的,3,张,DVD,，此时就达到了最大值。通过表,1.2,的统计我们得到最大值为 。,最差情况就是会员得到了,3,张没有出现在订单中的,DVD,，此时达到最小值,0,。,2,、再来看 的最大值和最小值,由“每位会员每次分配到,3,张,DVD”,和“一个月内,95%,的会员得到想看的,DVD”,的约束，则由 计算出各种,DVD,最小购买量，相加得 的最小值,522,只要某,DVD,出现在订单中，就应将其购入，也就是说保证会员可以拿到他想看的任何一张,DVD,，则会员在一个月中的满意率为,100%,。此时，统计各种,DVD,的购买量并相加得 最大值,864,23,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,不,等权情况,（,会员总体满意度与DVD购买量权重,不,相等,）,我们取 和 的最大值及最小值的平均数,1200,和,693,来确定各自权重。因此，它们的权重分别为 和 。建立带权重的模型：,同样用,LINGO,程序对其进行求解，最优值在第,116,次迭代后得到,Z=688.43,，,DVD,购买总量为,532,张。比较两个模型的计算结果，发现,DVD,的购买量和分配策略没有发生变化，这是由于 和 的数量级相差并不大。,24,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,综合最佳方案,以上的决策是基于当前时刻的考虑。事实上，,60%,的,DVD,会面临二次分配，考虑所有会员在一个月内总的满意度就需要对二次分配进行分开考虑。在此我们假设：不要求会员每次借,DVD,都必须被分配到,3,张，但分配到的必须是在其订单中的。而每次只有拿到,3,张的会员才能算满意。,由于要对二次分别进行讨论，所以需要设置两个新的变量：,1,、 ：第一次分配的分配变量，,表示第一次分配时第 位会员得到了,表示第一次分配时第 位会员未得到,2,、 ：第二次分配的分配变量，,表示第二次分配时第 位会员得到了,表示第二次分配时第 位会员未得到,因此在等权情况下目标函数应为：,25,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,综合最佳方案,约束条件,1,假设中会员在这一个月不会两次借相同的,DVD,，则可以表示为,2,每次分配每位会员最多得到,3,张,DVD,，即 ，,3,第一次分配时最多只能分配出新购入的,DVD,，则,4,考虑前后两分配的关系，平均情况下，可以近似的认为每种,DVD,每次都有,60%,借给,2,类会员，,40%,借给,1,类会员。所以有：,不等式右边表示网站在第二次分配时可用于分配的 数量。,5,因为规定在一个月中必须有,95%,的会员被满足要求，所以,DVD,总的数量需大于,1.60.95,100,3+,1.6,0.05,100,2=472,，相应的约束条件为,:,26,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,综合最佳方案,权重设置,对于 理想情况是两次分配都给会员最想看的,3,张,DVD,，而且会员不想看已经看过的,DVD,，则一个中月获得的最大满意度为,9+8+7+6+5+4=39,，以,60%,的,2,类会员记，一个月所有会员最大满意度为,100*(9+8+7)+60*(6+5+4)=3200,;,而最差的情况是每次会员都只得到了不在其订单中的,DVD,，或没得到,DVD,，则有：,对于 的最大、最小值取值方法和上次讨论的一样，计算得到分别为,864,和,472,。同样取中间值来确定权重，分别得到 的权重为 ，,的权重为 。,27,DVD,在 线 租 赁 问 题 数 学 模 型,模型建立与数值求解,问题三,:,综合最佳方案,模型,综合上述分析，,得到“最佳方案”的模型,：,用LINGO 程序求解,最优值在第2482次迭代后得到,Z=815.6966,DVD购买总量为472,28,DVD,在 线 租 赁 问 题 数 学 模 型,问题一我们分了两种情况进行讨论。问题二我们在原始,0-1,模型的基础上做了多次改进，对会员每次得到的,DVD,数量做了严格限制，得出的结论是会员总的满意度没有变化；对满意度的定义做了改进，并发现对分配策略的影响也不是很大。,在问题三中我们将问题一与问题二的要求结合在一起进行考虑，将两个目标加权后放在一个目标函数中进行讨论。从相对简单的“当前情况最佳方案”进行研究，并将问题分为等权与不等权两种情况进行讨论。然后我们对分配的全过程综合进行考虑，并建立了一个综合模型，经,LINGO,程序求解后得到了“综合最佳方案”。从两种模型的,DVD,购买量来看，“当前情况最佳方案”所需购买的,DVD,数量大于“一月综合最佳方案”所需购买的,DVD,数量，这是由于后一模型考虑了,DVD,的循环使用，降低了,DVD,的所需的储备量。,模型评价,29,