资源文件的下载方案优化.doc
《资源文件的下载方案优化.doc》由会员分享,可在线阅读,更多相关《资源文件的下载方案优化.doc(16页珍藏版)》请在咨信网上搜索。
1、题目 资源文件的下载方案优化 摘 要本文针对目前互联网的文件下载问题,根据下载方式的不同,建立优化模型,使得用户用最少的时间下载到最多的文件。问题一要求安排下载计划使得在最短的时间内完成下载任务,首先考虑到下载速度的波动问题,为了便于分析,我们利用对速度过大的情况进行概率分析,忽略其影响。得到稳定下载速度,方式一下载速度为,方式二下载速度为,建立下载资源分配模型:利用求解,得到最小下载时间为时分秒,具体下载安排见正文表。问题二要求安排下载和积分获得计划,在最短的时间内完成下载计划,我们将问题转化成订货存储问题,将积分的使用情况结合到问题的分析中,建立在积分限制下的资源分配模型:得出最少的下载时
2、间为时分秒,具体下载安排见正文表。问题三要求再有时间限制的条件下,尽可能多的下载文件,可以转化成动态规划下的背包问题,考虑第个文件能否装入背包,建立在背包问题基础上的资源分配模型:得出舍去号文件的下载,总共用时时分秒。具体安排见正文表。问题四要求在时间和积分的限制下,尽可能多的获得急需文件,只需在问题二、三的基础上加上急需条件的限制,建立动态规划模型:得出共用时时分秒。一共下载了个急需文件,个一般文件,具体下载安排见正文表。 关键词 订货存储 背包 动态规划一、问题背景和重述1.1问题背景现在互联网发展迅速,网络资源丰富。人们在日常生活及学习中,经常需要在网络上下载需要的文件资料。某论坛将注册
3、用户分为新生(回复问题在次),二年级生(回复问题在次),三年级生(回复问题在次以上)等等级,下载资料需要积分,提供注册用户回复问题每次可获得积分分,为避免有人恶意回复,规定每名用户:新生每分钟可回复一次问题,二年级生每分钟可回复一次问题,三年级生每分钟可回复一次问题。1.2问题重述某学生需要在某论坛下载个文件,现有的两种下载方式具有不同的下载速度,对于每一个文件有且仅有一种方式下载。方式的下载速度最高是,方式的下载速度最高是。在附件中,给出了个文件的大小、下载方式及需求程度等资料。题目给出:每种下载方式的下载速度都有在范围内的波动且该生所用电脑网络带宽下载速度最高可达。1、建立数学模型帮助该生
4、解决如何安排下载计划,使得其可在最短时间内下载完成所需文件(该问题不需要考虑积分);2、该生现有积分分,已回复问题在次,如何安排下载以及获得积分的计划,使得其可在最短时间内下载完成所需文件;3、在问题的条件下,由于时间原因,该生现在只有小时的上机时间,那么,如何安排下载计划,使得其可在规定时间内下载得到所需文件数量最多?4、在问题的条件下,要求下载的资料中,急需的文件数量要比一般程度的文件数多,如何安排下载计划,使得其可在规定时间内下载得到所需文件数量最多?二、问题分析2.1问题一的分析对于问题一,要求安排下载计划,可以在最短时间内下载完成所需文件。这是一个最优决策问题,无论先前的策略如何,相
5、对于前面的策略所形成的状态而言,余下的决策序列必然构成最优子策略,即一个最优策略的子策略也是最优的。由于下载速度是上下波动的,首先就要确定速度的波动范围,还要考虑用同一种方式下载多个文件时,是否可以对下载速度进行叠加。若下载速度不进行叠加,那么在进行单种方式下载时,会造成带宽的浪费,所以我们假设在带宽足够的情况下,对多个文件的下载速度是可以叠加的,在带宽不够的情况下,就对所下载的文件进行方式的分配。通过这样的分配,可以达到最短的下载时间。当然在对下载方式进行分配的时候,毕竟速度还是存在波动的,所以就要对超过限制的运用对数据进行分析,得出出现的概率,对概率进行分析,看是否可以忽略影响来简化计算。
6、在对方式二进行下载的时候,方式二的下载速度最高为,而带宽上限为,若只进行一个方式二的下载任务,则会有带宽浪费,且不可能多个文件下载速度都达到速度上限,所以考虑对方式二的文件进行组合下载,为尽量保持带宽充分利用,对方式二文件两两组合下载,且速度平均分配。而文件大小不同,两两组合,以相同速度下载时,最后会剩余部分方式二的文件下载,而方式一转到方式二的阶段,会有部分方式一的文件剩余,所以可以将方式一剩余的部分文件暂停,与方式二剩余部分组合下载,充分利用带宽。在考虑下载方式的速度不同之后,还要考虑到不同质量的资源,下载速度也是不同的,但是题目没有给出资源的质量分析,所以我们做出假设,网络资源没有优劣之
7、分,在资源质量这一条件下,下载速度是相同的。2.2问题二的分析问题二安排下载以及获得积分的计划,使得其可在最短时间内下载完成所需文件,我们可以把问题转化为动态库存问题,将其转化为不允许缺货的订货存储模型。将积分的使用情况结合到问题一里面的安排方式来看,号文件是利用方式二进行下载的,由于号文件所需要的积分很多,如按照问题一的方式进行下载,就会出现积分不够的可能,所以把号文件的下载顺序发生改变,使得用户获得的积分可以满足下载所需积分的支出。2.3问题三的分析问题三要求在上机时间小时的约束下,安排下载计划,使得其可在规定时间内下载得到所需文件数量最多,我们可以把小时看作是一个时间空间,每一个文件只有
8、下载完成才是有效的,我们可以把每个文件的下载时间看作是一个整体,这样,本题就可以看成是一个组合优化完全问题,就可以转化为背包问题2进行分析。背包问题34是一种组合优化的完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。其主要思路是假定某人拥有大量物品,重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中,来加密消息。背包中的物品总重量是公开的,所有可能的物品也是公开的,但背包中的物品是保密的。附加一定的限制条件,给出重量,而要列出可能的物品,在计算上是不可实现的。因此,我们将小时的时间容量看作是一个背包,将每一
9、个文件下载时间整体看成是没意见物品。结合问题一、二对时间和积分的限制,我们要考虑第个文件能否装入背包,就要考虑前个文件所占用的空间大小。结合规划,给出若不能放进,就求前个文件所占用背包的空间与其宗的价值;若可以放进,就考虑个文件的总价值。2.4问题四的分析要求下载的资料中,急需的文件数量要比一般程度的文件数多,如何安排下载计划,使得其可在规定时间内下载得到所需文件数量最多。问题四在问题三的基础上,添加了文件的重要性这一条件。因此只要尽量多的保证急需文件的下载,就可以达到这一目标。三、模型假设1、假设在带宽足够的情况下,对多个文件的下载速度是可以叠加的,在带宽不够的情况下,就对所下载的文件进行速
10、度的分配;2、网络资源没有优劣之分,在资源质量这一条件下,下载速度是相同的;3、假设该生进入论坛、点击下载文件的时间为;4、假设在论坛刚回答完问题,积分就可获得,就可以用于下载。四、符号说明方式一下载文件的速度方式二下载文件的速度各个文件下载最终完成时间每个文件的实际下载速度第个文件的大小剩余带宽时刻第个文件的下载量第个文件的下载速度第个文件所需的积分时刻用户所拥有的积分第个文件开始下载的时刻下载第个文件所需要的时间小于等于的最大整数文件开始下载前回答问题的次数第阶段第个文件的下载速度在不下载文件时,用户所获得的积分数五、模型建立与求解5.1问题一模型的建立与求解设方式一下载文件的速度为,方式
11、二的下载速度为。由于方式一的下载速度最高是,方式二的下载速度最高是,所以在带宽足够的情况下,方式一可以同时下载多个文件,并且每个文件的下载都可以达到速度上限。每种下载方式的下载速度都有在范围内的波动,通过计算可以得到,方式一速度的波动范围是,方式二的速度波动范围是,由于每个时刻的下载速度都是变化,所以每个文件的下载速度是随机变化的,因此,在每种方式的下载速度波动范围之内,各取个随机数(具体数值见附件),取其期望值作为一种下载方式的稳定下载速度,分别为和。对于本题,因为所要求的是时间最短,所以可以建立如下目标函数:其中,为各个文件下载最终完成时间。由于方式一的下载速度最高是,可同时进行多个下载任
12、务,若最后只剩下一个方式一下载的文件,下载速度最高只有,网络下载带宽浪费过多,不是最优分配,所以考虑先尽量将方式一的文件下载完成,再进行方式二的下载。(1)对于方式一带宽限制,为使每个文件都能达到最快下载速度,暂时以稳定下载速度考虑,因为,则最多可以有个文件同时下载。而由于下载速度在的范围内波动,所以当每个文件的下载速度达到时,个文件的总下载速度就会超过这一限制的,根据前文算得的随机下载速度数据,每个文件的实际下载速度为,为随机下载速度中的任意数且每个文件下载速度满足这一波动范围。若个文件总下载速度超过,则分析发现个文件总下载速度超过的概率为:利用求解得概率仅为,远小于,由此证明所以这是一个小
13、概率事件,可忽略不计。因此可以认为方式一一直是以稳定的速度进行下载,下载所需要的时间分别为:,对数据进行分析,若以相同速度下载,号文件的下载时间相似,号文件的下载时间明显小于其余个文件,为使文件尽量同步下载,选取号文件先开始下载。以开始下载的时刻为初始时刻,当一个文件下载完成时,立即进行下一个文件的下载。自初始时刻开始分钟后,文件下载完成,则立即开始下载号文件。分钟时,文件下载完成,立即开始号文件下载。分钟时,号文件下载完成,剩余个方式同时下载,而,有部分带宽被浪费,为维持带宽充分利用,当文件5下载完成时立即启动方式开始下载第二部分文件。(2)对于方式二分钟开始,方式二中号文件大小明显较小,所
14、以先开始下载号文件,接着下载号文件。剩余带宽为,第个文件的大小为,时刻第个文件下载量为,为第个文件的下载速度。当号文件下载完成后,开始方式二文件的两两组合下载,将的下载带宽进行平均分配,即都以进行下载。要充分利用带宽,则要尽量保持两个文件同时下载,将两个下载通道,一个通道内有,号文件,另一个通道内有,号文件,两个通道同时进行,通道一完成的时间为:在完成通道一的文件下载时,通道二内的文件没有全部完成,得到最后剩余文件大小为。在通道一完成时通道二未完成,则当方式二通道一内文件完成的同时,启动方式一的剩余部分,为使总下载速度始终达到上限,就要使文件同时下载完成,对下载速度进行调节,设文件剩余部分下载
15、速度为,文件剩余部分下载速度为使这两个文件下载完成时间尽可能少。两部分文件下载速度总和小于带宽,得到的约束条件为:且满足:,求解得,。则可以得到的稳定速度为,剩余部分完成时间为分秒。利用(具体程序见附录2)得到下载各个文件的下载起始和结束时间如下表:表 下载各个文件的下载起始和结束时间文件号起始下载时间终止下载时间文件号起始下载时间终止下载时间12h27m15s4h12m40s93h17m53s3h54m46s20h0m0s2h54m21s104h12m40s5h3m57s30h0m0s2h27m15s113h54m46s4h51m17s4(1)2h38m15s4h12m40s124h51m1
16、7s5h41m57s4(2)6h34m18s6h41m48s132h40m56s3h17m53s50h0m0s2h38m15s145h41m57s6h34m18s60h0m0s2h55m9s155h3m57s5h55m37s70h0m0s3h7m45s165h55m37s6h41m14s80h0m0s2h40m56s最终得到的最少的下载时间为时分秒。5.2问题二模型的建立与求解5.2.1模型的建立为第个文件所需积分,为时刻用户现有积分,为第个文件开始下载的时刻,为第个文件下载所需时间。在不进行下载的情况下,积分的获得按照题目所给的规则:该论坛将注册用户分为新生(回复问题在次),二年级生(回复问
17、题在次),三年级生(回复问题在次以上),新生每分钟可回复一次问题,二年级生每分钟可回复一次问题,三年级生每分钟可回复一次问题,回答问题每次可以获得个积分。该生现有积分分,已回复问题在次,下表给出了该生在不下载文件的情况下,获得积分的情况如下:表 不进行下载时的积分明细等级123回复次数172025升级需要次数035升级时间090100获得积分516383当回复问题次后,升级进入三年级时,共可以获得积分,此时该用户手中现有的积分为,而完成全部下载任务需个积分,所以只需考虑新生和二年级的积分获取方案。积分是下载的前提,要使下载资源得到充分利用,则要控制用户现有积分始终大于下载需要的积分,在下载的同
18、时,用户可回答问题获取积分补充现有积分。若按问题一的下载方式安排,积分使用情况如下:表 方式一安排下的积分使用情况阶段阶段一阶段二阶段三所需积分282042现有积分512310缺少积分0032对此可以建立在积分限制情况下的下载资源分配模型:则在不下载文件的情况下,用户可拥有积分为:,其中表示小于等于的最大整数。不能出现积分少而不能下载的情况,所以这是一个动态库存问题,将其转化为不允许缺货的订货存储模型。开始下载的同时扣取积分,则时刻用户拥有积分为,由于不能出现缺货情况,所以要保证积分足够,还需对下载顺序进行重新安排。结合问题一的下载时间安排,将下载安排分为三个阶段:只有方式一下载、两种方式同时
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 资源 文件 下载 方案 优化
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。