1014604842数学建模优秀论文DVD在线租赁方案的优化模型.doc
DVD在线租赁方案的优化模型何荣坚、庞淑婷、曹国威摘 要本文对DVD在线租赁的需求预测、购买与分配等相关问题，进行合理的简化假设，得到该问题的数学模型.对于DVD张数问题，根据需求预测表（题中表1），计算租赁周期上、下限的平均值，应用图论知识，利用会员对DVD的偏好程度建立二部图和图论度的计算得出对应不同平均租赁周期的DVD数量结果.针对DVD的现有张数和订单数，给出了权重矩阵和满意度函数，建立以最大整体满意度为单目标的0-1整数规划模型，利用Lingo8.0软件中的ole函数从Excel中读取权重系数矩阵，求解出最大整体满意度和其分配方案.利用在线订单，以最大整体满意度和最小购买量为多目标的0-1整数规划模型，通过线性加权法化多目标为单目标规划，利用Lingo8.0软件求解出当时，其最大整体满意度分别为980.48，1000，978.3，1000，其最小购买量分别为981，1475，1805，2085.从网站角度考虑，分析需求预测、购买分配中联系的参变量，确定了几个值得研究的问题，提出并建立了以网站最大收益和最大整体满意度为多目标的规划模型.关键词：0-1整数规划；租赁周期；满意度1 问题的提出考虑如下的在线DVD租赁问题.顾客缴纳一定数量的月费成为会员，订购DVD租赁服务.会员只要在线提交订单，网站就会通过快递的方式尽可能满足要求.会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的.网站会根据现有的DVD数量和会员的订单进行分发. 请考虑以下问题：1）通过问卷调查1000个会员，得到了愿意观看这些DVD的人数.假设网站现有10万个会员，对其中5种DVD来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD？2）如今给出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单，如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001C0030）分别获得哪些DVD.3） 如果你是网站经营管理人员，你如何决定每种DVD的购买量，以及如何对这些DVD进行分配，才能使一个月内95%的会员得到他想看的DVD，并且满意度最大？4）如果你是网站经营管理人员，你觉得在DVD的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型.2 基本假设与符号约定2.1 基本假设2.1.1 网站在不太长的时间内会员人数没有太大的变化,网站每月的月费收入基本保持不变；2.1.2 不同电影的DVD的价格相差不大，视作相等；2.1.3 网站用速递方式将DVD送交给会员，以及会员将DVD邮寄给网站的时间都很短，视为即日到达.邮寄每次都是三只DVD，而且邮费都是一定的；2.1.4 允许网站不对部分订单作处理；2.1.5 每个会员每个月租赁次数不得超过2次，每次获得3张DVD.会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁；2.1.6 60%的会员每月租赁DVD两次，而另外的40%只租一次.2.2 符号约定：会员总数，其中在问题一中，万；在问题二、三中，；：DVD种数，其中在问题一中，；在问题二、三中，；：会员租借DVD的平均租赁周期；：DVDj的现有张数，；：DVDj在会员的定单中的偏好程度，；：会员对DVDj的权重系数， ，；：对于网站的分配方案,会员的满意度，；：所有会员对网站分配方案的总满意度.3 DVD数量的图论模型3.1 平均周期的上、下限会员租DVD一次（含看及周转DVD）的时间称为租赁周期，而个会员的平均租赁周期为.一般情况下，一个月内租DVD一次的会员当中，最小租赁周期为15天，最大租赁周期为30天；一个月内租DVD两次的会员当中，最小租赁周期为5天，最大租赁周期为15天.根据上面所述及假设2.1.6可得平均周期上、下限.计算其平均值（数学期望），有：于是3.2 图论模型令为会员集合， 为不同DVD集合.以为顶点集，若会员愿意观看，则连一条边，则得到一个图（二部图）易知：中每个顶点的度， .的度与的度相等，即是一个简单二部图或偶图.3.3 模型的转化及求解1）设DVD应准备的张数为；2）用表示会员一个月租DVD的张数（不同），或，它是一个随机变量；由假设3及“每次获得3张DVD”知，；3）试在中找一个生成二部子图，（满足或6）.3.4 DVD数量的计算1）一个月50%的满足： 的结果为：平均租赁期910111213DVD130013334366740014334DVD215001667183420002167DVD375183491710001084DVD4376417459501542DVD5150167184200217由上表可知，当平均租赁期为9天时，所需的五种DVD数量最少. 2）三个月95%的满足： 的结果为：平均租赁期910111213DVD119012112232325342745DVD29511056116212671373DVD3476528581634687DVD4238264291317344DVD596106117127138由上表可知，当平均租赁期为9天时，所需的五种DVD数量也最少.4 DVD分配方案模型4.1 矩阵表示由题目的在线订单数据表，可得到DVD的现有数量矩阵设表示会员在100种DVD中选择了种，从数据表得知有三个取值8，9，10.我们知道，会员的在线订单用数字1,2,表示，数字越小表示会员的偏爱程度越高，即数字1表示会员对于对应DVD的偏爱程度最高，数字2,3,.,表示其偏爱程度逐渐下降.把会员的偏爱程度进行量化：对于每一个，当会员在100种DVD中选择了种时，定义分段函数其中表示会员对的偏爱权重系数.可以建立选择权重矩阵=4.2 满意度函数由于每个会员每个月租赁次数不得超过2次，每次获得3张DVD.不妨假设会员获得其偏爱权重前三位的DVD时，会员的满意度就达到100%.而满意度为100%时，我们不妨假设此时满意度为1 .考虑问题二中要处理的租赁，令于是，可以定义会员的满意度为所有会员的整体满意度为问题二要求对100种DVD进行分配，使得会员获得最大的满意度，即要使达到最大值. 4.3 DVD数量模型在分配方案中每种DVD租赁出去的总张数不应超过其现有数量（对应模型的式（2）即DVD现有数量的约束.而在当前DVD在线订单中，每个会员只能获得3张DVD（对应模型的式（3）.而是一个决策变量,当=0时说明了编号为j的DVD没有租赁给会员.根据上面模型的分析，我们以整体满意度为目标函数的单目标规划，建立0-1整数规划模型如下：模型：4.4 模型的求解及结果在模型的求解过程中，利用Lingo8.0软件中的ole函数直接将权重系数矩阵（1000100）（此权重系数矩阵是电子表格的格式）输入到内存，通过max函数编程求解10万个决策变量的线性规划模型（程序段见附录1），可得局部最优解如下表所示（列出会员编号为C0001C0030的个人满意度和分配方案）：会员编号个人满意度分配到的DVD的编号会员编号个人满意度分配到的DVD的编号C00010.7916784198C00160.96296108497C00020.9629664462C00171475167C00030.95238325080C00181416078C0004171841C00190.88889666786C00051116668C00201456189C00060.96296195366C00210.92593455053C00070.83333266681C00221385557C00080.48148263135C00231298195C000915378100C00240.96296374176C00100.81481415585C00250.9629696981C00110.95833596366C00261226895C00120.8518523141C00270.77778505878C00131217896C0028183482C00140.88889235289C00290.96296263055C00150.74074136685C00300.92593376298在此种方案中，计算出1000个会员的总满意度为：.5 DVD购买量与分配方案模型5.1 数学模型问题三要求站在网站角度考虑，如何购进最少DVD同时获得要求最大的满意度.与问题二模型相似，在满足最大整体满意度和最小均衡满意度的基础上，继而考虑DVD的购买量要尽量小.于是，建立以整体满意度（即模型中的式（5）和购买量（即模型中的式（6）为三目标函数的0-1整数规划模型.下面讨论问题三的约束条件：1）分配方案中DVD数量的约束：在此分配方案中，要使95%的会员得到他想看的DVD，即对于分配方案中的每一种DVD，其人数百分比都应在95%以上（对应模型的式（7）；2）会员租赁DVD数量的约束：在当前DVD在线订单中，每个会员只能获得3张DVD（对应模型的式（8）.设：购进DVDj的张数.建立模型如下所示:模型：5.2 模型的转化、求解及结果在模型的求解过程中，我们通过线性加权法化双目标为单目标规划,其中，简化后模型如下：这是一个0-1整数规划模型，利用Lingo8.0软件中的ole函数直接将权重系数矩阵（1000100）（此权重系数矩阵是电子表格的格式）输入到内存，通过max函数编程求解，得出局部最优解如下所示：当平均租赁周期为 10天时，所需DVD个数有981个.其中每种DVD个数分别如下表所示：DVD编号D001D002D003D004D005D006D007D008D009D010DVD张数1212913791011118DVD编号D011D012D013D014D015D016D017D018D019D020DVD张数1010910912991012DVD编号D021D022D023D024D025D026D027D028D029D030DVD张数11912791086813DVD编号D031D032D033D034D035D036D037D038D039D040DVD张数101110101311710109DVD编号D041D042D043D044D045D046D047D048D049D050DVD张数17129111181081011DVD编号D051D052D053D054D055D056D057D058D059D060DVD张数13911910111091112DVD编号D061D062D063D064D065D066D067D068D069D070DVD张数9101011101010111110DVD编号D071D072D0730D074D075D076D077D078D079D080DVD张数121181098710109DVD编号D081D082D083D084D085D086D087D088D089D090DVD张数967611711889DVD编号D091D092D093D094D095D096D097D098D099D100DVD张数129871381110611下面列出前三十名会员的满意度和分配方案：会员编号个人满意度分配到的DVD编号会员编号个人满意度分配到的DVD编号c00010.3754816c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c00051116668c00201456189c00061161953c00210.703734553c0007182681c00221385557c00081157199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00140.703722352c00291304455c00150.703721388c0030113762平均租赁周期为：10，总满意度为980.48.当平均租借周期为15天时，所需DVD个数有1475个.其中每种DVD个数分别如下表所示：DVD编号D001D002D003D004D005D006D007D008D009D010DVD张数10181319101415161712DVD编号D011D012D013D014D015D016D017D018D019D020DVD张数14151415131914131519DVD编号D021D022D023D024D025D026D027D028D029D030DVD张数19141315191513101220DVD编号D031D032D033D034D035D036D037D038D039D040DVD张数14171515191710151414DVD编号D041D042D043D044D045D046D047D048D049D050DVD张数26171317171216121617DVD编号D051D052D053D054D055D056D057D058D059D060DVD张数19131613151615141718DVD编号D061D062D063D064D065D066D067D068D069D070DVD张数16151417181515171615DVD编号D071D072D0730D074D075D076D077D078D079D080DVD张数18171215141210151514DVD编号D081D082D083D084D085D086D087D088D089D090DVD张数1491110161017121213DVD编号D091D092D093D094D095D096D097D098D099D100DVD张数1914121119121816917下面列出前三十名会员的满意度和分配方案：会员编号个人满意度分配到的DVD编号会员编号个人满意度分配到的DVD编号c0001188298c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c00051116668c00201456189c00061161953c00211455365c0007182681c00221385557c00081157199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00141234352c00291304455c00151138588c0030113762平均租赁周期为：15，总满意度为1000 .当租借周期为18天时，所需DVD个数有1805个.其中每种DVD个数分别如下表所示：DVD编号D001D002D003D004D005D006D007D008D009D010DVD张数13221722131718202115DVD编号D011D012D013D014D015D016D017D018D019D020DVD张数17191718152317161922DVD编号D021D022D023D024D025D026D027D028D029D030DVD张数21182114181916121525DVD编号D031D032D033D034D035D036D037D038D039D040DVD张数18211818242113181717DVD编号D041D042D043D044D045D046D047D048D049D050DVD张数32211621201519151919DVD编号D051D052D053D054D055D056D057D058D059D060DVD张数24152015181919172122DVD编号D061D062D063D064D065D066D067D068D069D070DVD张数17191921191818211918DVD编号D071D072D0730D074D075D076D077D078D079D080DVD张数22191518171512181817DVD编号D081D082D083D084D085D086D087D088D089D090DVD张数18111212201321141516DVD编号D091D092D093D094D095D096D097D098D099D100DVD张数23171514241522191121下面列出前三十名会员的满意度和分配方案：会员编号个人满意度分配到的DVD的编号会员编号个人满意度分配到的DVD的编号c00010132752c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c00050.96296216668c00200.703724589c00061161953c00211455365c0007182681c00221385557c00080.703767199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00141234352c00291304455c00151138588c0030113762平均租赁周期为：18，总满意度为：978.3 .当租借周期为21天时，所需DVD个数有2085个.其中每种DVD个数分别如下表所示：DVD编号D001D002D003D004D005D006D007D008D009D010DVD张数15251926151718202115DVD编号D011D012D013D014D015D016D017D018D019D020DVD张数20221922192619182226DVD编号D021D022D023D024D025D026D027D028D029D030DVD张数24202415202218131728DVD编号D031D032D033D034D035D036D037D038D039D040DVD张数20242222272415212019DVD编号D041D042D043D044D045D046D047D048D049D050DVD张数36241824241722172224DVD编号D051D052D053D054D055D056D057D058D059D060DVD张数28182318222222192425DVD编号D061D062D063D064D065D066D067D068D069D070DVD张数19222224222221242321DVD编号D071D072D073D074D075D076D077D078D079D080DVD张数25241722191714212219DVD编号D081D082D083D084D085D086D087D088D089D090DVD张数20131513231524171719DVD编号D091D092D093D094D095D096D097D098D099D100DVD张数27191716281725221324下面列出前三十名会员的满意度和分配方案：会员编号个人满意度分配到的DVD的编号会员编号个人满意度分配到的DVD的编号c0001188298c0016168497c0002164244c00171475167c0003145080c00181416078c0004171841c00191678486c00051116668c00201456189c00061161953c00211455365c0007182681c00221385557c00081157199c00231298195c000915378100c00241417679c00101556085c0025196994c00111195963c00261226895c001212731c00271224258c00131217896c0028183482c00141234352c00291304455c00151138588c0030113762平均租赁周期为：21，总满意度为1000 .6 DVD的需求预测、购买和分配中的相关问题作为网站经营管理人员，在DVD的需求预测、购买和分配中还有一些重要问题值得研究.6.1 变量的依赖关系1）对于网站，需求预测与会员的偏爱程度（随时间变化而变化，即是时间的函数）以及每个会员每次租赁DVD张数有关.其中，需求预测即各种DVD的愿看人数（单位：人）.它决定了每种DVD的购买量.而购买量又与租赁周期（平均）、满足会员百分比（题中、等）以及每次租赁张数有关.2）对于网站来说，购买总量（价格相同时）或总价格（为的单价）最小，从而成本最小.3）购买量影响分配方案，而分配方案与（见上）、会员满意度有关总体满意度6.2 函数关系及模型1） 固定，是的增函数.2），考虑 固定时，是的增函数；固定时，是的增函数；固定时，是的增函数.3） 6.3 值得研究的问题1）租赁周期2）租赁张数3）一般的租赁原则4）购买总价格5）会员人数6）一般的网站总收入6.4 明确的问题及数学模型6.4.1 对于会员的月费不变，每张DVD的单价不变.试确定网站经营方案（包括确定，每月租赁次数），使网管总收入最大.6.4.2 数学模型要使总收入增加，就要使会员人数变，就需会员满意度高.于是其中H表示网站日常的开销，如网页管理费，邮寄费用等.约束条件：依赖关系决策变量：7 模型的讨论与推广在DVD分配方案模型中,我们只考虑到所有会员的总体满意度函数为目标的最大化问题,只追求总体的满意度最大,而没有考虑到会员之间的满意度应尽量均衡.故我们可以定义均衡满意度函数 :作为目标函数,这样就使得会员之间满意度的差距比较少,同时也达到了总体满意度尽可能大.同理,我们也可以在DVD购买量与分配方案模型引入该函数,使得解更优化,使模型更符合现实.参考文献：1 魏宗舒等，概率论与数理统计教程，北京：高等教育出版社，1983年.2 王沫然，matlab6.0与科学计算，北京：电子工业出版社，2001年.3 费培之，图和网络及其应用，成都：四川大学出版社，1996年.附录1：问题二的程序model:sets:member/1.1000/:;!会员集合;number/1.100/:demand;!DVD现有数量;link(member,number):weight,decision;!weight是权重系数 decision是为0或者1的决策变量;endsetsdata:weight,demand=OLE('weight.xls'); !weight从weight.xls电子表格中读取;enddata!目标函数;max=sum(link(i,j):weight(i,j)*decision(i,j);!约束每一个会员一次只能租三张DVD;for(member(i): sum(number(j):f(i,j)=3);!约束每一种DVD的选择的人数应少于该种DVD的现有数量;for(number(j): sum(member(i):decision(i,j)<=demand(j);!约束决策变量为0，1变量;for(link(i,j):bin(decision(i,j);End附录2：问题三的程序model:sets:number/1.100/:dvdnumber;!DVD种类的集合;member/1.1000/:;!会员集合;link(member,number):weight,decision;!weight是权重系数 decision是为0或者1的决策变量;endsetsdata:weight=OLE('weight.xls');!weight从weight.xls电子表格中读取;enddata!目标函数;max=sum(link(i,j):weight(i,j)*decision(i,j)-sum(number(i):dvdnumber(i);!约束每一个会员一次只能租三张DVD;for(member(i): sum(dvdnumber(j):decision(i,j)=3);!约束在一个月里每一种DVD的选择的人数应少于该种DVD的现有数量的95%;for(dvdnum(j): sum(member(i):decision(i,j)*0.95<=3*dvdnumber(j);!约束决策变量为0，1变量;for(link(i,j):bin(decision(i,j);!约束决策变量为整数;for(number(i):gin(dvdnumber(i);end
