网络资源下载问题数学建模.doc

2015高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2015年6 月 1 日网络资源下载问题摘要本文针对目前互联网的文件下载问题，根据下载方式的不同，建立优化模型，使得用户用最少的时间下载到最多的文件。针对问题1，首先考虑速度波动问题，确定波动范围。为便于分析，用MATLAB计算下载速度的期望，得到速度期望值分别为72.5kb/s、381.3kb/s。根据方式1文件大小，利用MATLAB对方式1的10个文件进行排序，实现文件组合下载的优化。将下载方式分为三个阶段:第一阶段为方式1方式2同时下载，方式2达到速度期望值，当方式2中的文件全部下载完成后第一阶段结束；第二阶段为六个方式1同时下载，其中方式1有一个文件未达到速度期望值；当第二阶段中任一组合文件下载完成后进入第三阶段，此时剩余的文件1同时以期望速度下载。利用MTALAB求解，得到三个阶段分别耗时254.8min，149min,74min,故总耗时为485.8min。针对问题2，考虑积分问题，在问题1的基础上，考虑问题1的方案是否满足积分要求。由附件数据可得，20个文件所需积分为103分。第一次回答无需等待，升级后第一次回答也无需等待，故获得103积分的时间为140min。增加此约束条件后最优解不受影响，故问题1方案可行。针对问题3，在考虑积分和上机时间有限的前提下，达到下载文件数量最多的目标，根据多线程下载优化模型，建立了多条线路没有下载的方案，通过对大量数据进行假设，分析，得出最优解，即能下载19个文件，剩余file7没有下载。针对问题4，仍然考虑积分和上机时间，以及需求程度的问题，在这些条件下实现下载文件数量的最多，针对此问题，在问题3已建立的的模型基础上，利用贪心算法，让急需文件优先下载，得出最优下载方案，急需文件全部下载，总文件数为19。文章最后，对模型的缺点进行分析，提出模型存在的问题，并且提出了改进方案，通过模型的建立，未下载折节省了大量的时间。同时此模型对日程安排，生产流程规划也有很好的推广性。关键词：排队论 数学期望 组合优化 多目标规划 动态规划一 问题重述现在互联网发展迅速，网络资源丰富。人们在日常生活及学习中，经常需要在网络上下载需要的文件资料。现有某学生需要在某论坛下载资料，需要下载的文件共有20个，由于下载方式的不同，下载文件具有不同的下载速度。现在的文件共有两种下载方式（每个文件有且仅有一种下载方式），方式1的下载速度最高是80kb/s，方式2的下载速度最高是400kb/s，20个文件的大小、下载方式及需求程度等资料见附件。另: 由于网络的原因，1.每种下载方式的下载速度都有在10%范围内的波动；2.该生所用电脑网络带宽下载速度最高可达430kb/s.问题：建立数学模型帮助该生解决如何安排下载计划，使得其可在最短时间内下载完成所需文件（该问题不需要考虑积分）；该论坛将注册用户分为A级用户（回复问题在0-20次），B级用户（回复问题在20-25次），C级用户（回复问题在25次以上）等等级，下载资料需要积分，提供注册用户回复问题每次可获得积分4分，为避免有人恶意回复，规定每名用户：A级用户每30分钟可回复一次问题，B级用户每20分钟可回复一次问题，C级用户每10分钟可回复一次问题。该用户现有积分50分，已回复问题在15次，如何安排下载以及获得积分的计划，使得其可在最短时间内下载完成所需文件。在问题2的条件下，由于时间原因，该用户现在只有7小时的上机时间，那么，如何安排下载计划，使得其可在规定时间内下载得到所需文件数量最多？在问题2，3的条件下，由于资料的需求程度不一致，要求下载的资料中，急需的文件数量要比一般程度的文件数多，如何安排下载计划，使得其可在规定时间内下载得到所需文件数量最多？二 问题分析2.1 问题一的分析对于问题一，要求安排下载计划，可以在最短时间内下载完成所需文件。这是一个最优决策问题，无论先前的策略如何，相对于前面的策略所形成的状态而言，余下的决策序列必然构成最优子策略，即一个最优策略的子策略也是最优的。由于下载速度是上下波动的，首先就要确定速度的波动范围，还要考虑用同一种方式下载多个文件时，是否可以对下载速度进行叠加。若下载速度不进行叠加，那么在进行单种方式下载时，会造成带宽的浪费，所以我们假设在带宽足够的情况下，对多个文件的下载速度是可以叠加的，在带宽不够的情况下，就对所下载的文件进行方式的分配。通过这样的分配，可以达到最短的下载时间。当然在对下载方式进行分配的时候，毕竟速度还是存在波动的，为便于分析，用MATLAB计算下载速度的期望，得到期望速度分别为72.5kb/s、381.3kb/s。在对方式二进行下载的时候，方式二的下载速度期望为381.3kb/s若只进行一个方式二的下载任务，则会有带宽浪费，且不可能多个文件下载速度都达到速度上限，所以考虑对方式一和方式二的文件进行组合下载，为尽量保持带宽充分利用，方式二中的文件以期望的速度下载，当方式2中的文件全部下载完成后第一阶段结束，此时耗时254.8min。第二阶段为六个方式1时下载，其中有一个方式1文件未达速度期望值。当第二阶段中任一组合文件下载完成后进入第三阶段，此时剩余的文件1同时下载，均达到速度期望值。在考虑下载方式的速度不同之后，还要考虑到不同质量的资源，下载速度也是不同的，但是题目没有给出资源的质量分析，所以我们做出假设，网络资源没有优劣之分，在资源质量这一条件下，下载速度是相同的。2.2 问题二的分析针对问题2，考虑积分问题，在问题1的基础上，考虑问题1的方案是否满足积分要求。由附件数据可得，20个文件所需积分为103分。第一次回答无需等待，升级后第一次回答也无需等待，故获得103积分的时间为140min。增加此约束条件后最优解不受影响，故问题1方案可行。2.3 问题三的分析针对问题三考虑有限的上机时间为7个小时（420min），由问题1可知下载完所有文件的时间为T(min),只需验证在（T-420）时间内未能下载的文件数W，即下载的文件数是20-W。2.4 问题四的分析要求下载的资料中，急需的文件数量要比一般程度的文件数多，如何安排下载计划，使得其可在规定时间内下载得到所需文件数量最多。问题四在问题三的基础上，添加了文件的重要性这一条件。因此只要尽量多的保证急需文件的下载，就可以达到这一目标。三 模型的基本假设1、假设文件下载时，文件下载速度可控制。2、假设在带宽足够的情况下，对多个文件的下载速度是可以叠加的，在带宽不够的情况下，就对所下载的文件进行速度的分配；3、假设该生进入论坛、点击下载文件的时间为；4、假设在论坛刚回答完问题，积分就可获得，就可以用于下载。四 符号说明主要符号符号意义第i中下载方式的下载速度表示最大带宽速度 表示方式一二的最优下载速度表示第二阶段的最小速度文件下载所需要的积分的大小（表示第一阶段所耗时间表示第二阶段所耗时间表示第三阶段所耗时间表示方式1的最大文件表示方式1最大文件在第一阶段下载后所剩文件的大小文件在第一阶段下载所用时间最终下载时间表示方式1的第i个文件大小（i=1.8.17，18）表示方式2的第j个文件大小（j=9.16，19,20）表示文件下载所需要的积分的大小（i=1.16）五 模型建立与求解5.1.1问题1的模型考虑速度波动，为便于计算，利用MATLAB算出方式1和方式2速度的期望值，分别为、，程序详见附录1。对表格中的数据进行处理，得到按稳定速度下载所需时间，详见表5.1。文件大小（M）积分需求时间（min）file13928一般90file26506急需149file35503急需126file43802一般87file55904急需135.6file66534急需150file77006急需161file86005一般138file1769610急需160file182221一般51file95502急需24file105633一般24.6file116612急需29file126008一般26file1335010一般15.3file146106急需26.6file155785一般25.2file165896一般25.7file198008急需35file205334一般25.3表5.1对问题1，将下载过程分为三个阶段，根据方式1、方式2的下载的速度和文件大小，由表5.1可知，方式2的下载时间明显少于方式1的下载时间，第一阶段考虑方式1和方式2的文件同时下载，对方式1的文件大小进行排序，选择方式1中一个最大文件（即文件7）先后和方式2一起下载。方式2以期望速度下载，剩余带宽用于方式1下载，并且方式1、2速度和达到宽带最大值，按此期望下载速度，下载至方式2的文件全部下载完成为第一阶段，记第一阶段耗时为： += 进入阶段二，此后只有方式1的文件下载，并且同时下载六个文件，但是其中一个文件的速度无法达到72.5kb/s，即为 430 5*72.5=67.5kb/s ，此速度用于下载阶段一尚未完成的文件7，当文件7下载完成后，文件17按此速度继续下载。由第一阶段下载所剩的文件大小，对现有文件大小排序，对其中三组文件进行组合下载。当剩余文件中的最小文件以72.5kb/s的速度下载完成后， 67.5kb/s的速度升为72.5kb/s，继续下载，此时第二个阶段结束，此过程耗时为 = * 1024 / * 60接下来所剩文件的下载速度全部达到72.5kb/s ，进入下载的第三阶段。将此过程所剩文件再次排序，取最大文件进行计算，即为此阶段所耗时间。 =* 1024最后得出问题 （1） 的最优时间为： =+最后有三个阶段的划分模型得出了最优下载计划，详见图5.2. 图5.2表示整个过程（即一二三阶段）的下载计划，数字对应下载的文件号5.1.2问题1的求解根据问题1模型，下载过程分为三个阶段：第一阶段时间为,+= =+/=254.8min该时间表示方式二的文件全部下载完成所需的时间。第二阶段时间为= * 1024 / * 60求得=149min该时间表示方式1文件组合后，以期望速度下载完所需时间。第三阶段时间=* 1024=/*1024=74min故最优时间为=+=485.8min5.2问题2模型的建立针对问题2，考虑积分问题，在问题1的基础上，考虑问题1的方案是否满足积分要求。由附件数据可得，20个文件所需积分为103分。第一次回答无需等待，升级后第一次回答也无需等待，故获得103积分的时间为140min。增加此约束条件后最优解不受影响，故问题1方案可行。5.2.1问题2模型的求解由于第一次回答问题无需等待，升级后第一次回答问题也无需等待。第一阶段下载完成时间为254.8min，此过程所获积分为40分,累计积分为30分。第二三阶段下载完成用时231min，此过程所获积分为92积分，累计积分为56积分。因为累计积分0,故最优下载计划不受影响。5.3问题3模型的建立现将解决问题1,2的模型拿来套用，由图5.2可知，最多只能下载16个文件，有4个文件始终无法下载完成。这时，考虑重建模型，看是否能在7小时内下载更多文件。因为时间已经限定为7小时，即420分钟，因此，只要在420分钟内下载的文件最多时，就保证了文件下载最多。据此展开讨论：当按方式一下载的文件都以72.5kb/s下载时，方式二按357.5kb/s下载，此时各个文件下载完所需的时间详见表5.3。表5.3文件大小（M）积分需求时间（min）速度file13928一般9072.5file26506急需14972.5file35503急需12672.5file43802一般8772.5file55904急需135.672.5file66534急需15072.5file77006急需16172.5file86005一般13872.5file1769610急需16072.5file182221一般5172.5file95502急需26357.5file105633一般27357.5file116612急需32357.5file126008一般29357.5file1335010一般17357.5file146106急需29357.5file155785一般27.6357.5file165896一般28357.5file198008急需38357.5file205334一般25357.5由表5.3分析，假设一： 将过程分为两个阶段，第一个阶段分为两个线程，一个线程速度为72.5kb/s，另一个线程为357.5kb/s。以方式二文件完全下载为第一阶段结束标志。此时进入第二阶段，第二阶段为六个方式一文件下载。通过定性分析，最多下载文件只能为16个，依然不能达到最优。假设二：将过程分为两个阶段，第一阶段分为三个线程，前两个线程速度为72.5kb/s，都用来下载-，最后一个线程速度为285kb/s，用来下载，及完全下载完为第一阶段结束标志。再建立表5.4。表 5.4 经分析，由表5.4可知，在349min内，线程一能把下载完成，线程二能把下载完成，此时，全部下载完成。但在第二阶段只剩余71min，剩余的四个文件下载没有完成，故没有达到最优。 假设三：将过程分为两个阶段，第一阶段分为四个线程，前三个线程下载速度为72.5kb/s，最后一个线程的下载速度为212.5kb/s。以中任意七个下载完成为第一阶段结束的标志。列出表格5.5： 表 5.5由此模型知：在第一个阶段时，可以任意选择三个线程进行下载，此时每个文件都能达到最大。，都以212.5kb/s的速度依次进行下载，当还剩一个文件时，第一阶段结束，由于，的每个文件下载用时都不一样，因此第一阶段的结束时间也不固定，假设第一阶段结束时没有下载完成，此时，第一阶段用时为308.463,。将，放在线程一内依次进行下载用时为304.762分钟。，放在线程二内依次进行下载用时为302.324分钟。将，放在线程三内依次进行下载用时347.429分钟。这样将线程分配完毕，在第二阶段时，将线程三保留，线程一，二，四合并，此时下载速度为342kb/s。用合并线程下载。直到7小时结束，此时，和，全部下载完毕，只剩没有下载。提出模型：由问题1，2模型中提出的动态规划思想引出，该模型依然保留分为两个阶段，但每个阶段文件下载方式与之前的模型不同。该模型的第一阶段分为四个线程，这四个线程把430kb/s的带宽分完，按照前三阶段的带宽为72.5kb/s，最后一个带宽的速度为212.5kb/s。在第一阶段完毕后，保留前三线程中没有下载完的那个线程，其余的与第四线程合并，据此得出的方案最优。5.3问题3模型的求解因为时间已经限定为7小时，即420分钟，因此，只要在420分钟内下载的文件最多时，就保证了文件下载最多。据此展开讨论：假设一：将过程分为两个阶段，第一个阶段分为两个线程，一个线程速度为72.5kb/s，另一个线程为357.5kb/s。以方式二文件完全下载为第一阶段结束标志。此时进入第二阶段，第二阶段为六个方式一文件下载。通过定性分析，最多下载文件只能为16个，依然不能达到最优。假设二：将过程分为两个阶段，第一阶段分为三个线程，前两个线程速度为72.5kb/s，都用来下载-，最后一个线程速度为285kb/s，用来下载，及完全下载完为第一阶段结束标志。经分析，由表5.4可知，在349min内，线程一能把下载完成，线程二能把下载完成，此时，全部下载完成。但在第二阶段只剩余71min，剩余的四个文件下载没有完成，故没有达到最优。假设三：在第一个阶段，文件分四个线程下载，前三个线程达到稳定速度72.5kb/s，剩余212.5带宽用于的下载。第二阶段将线程一二四合并，用合并线程下载文件11，文件16。直到7小时结束，此时只剩文件7没有下载。具体线程详见图5.6。图5.6第一阶段线程一 72.5 373 min线程二 72.5 376 min线程三 72.5 338 min线程四 72.5350 min第二阶段线程一二四，合并 430 54 min剩余 没有下载5.4问题4模型的建立由表5.5知，为急需文件，因此需要优先下载，在问题三模型的基础上增加优先顺序，因此线程内的文件下载顺序可以据图标所示的方式安排，以-，中剩余，为第一阶段结束的标志，线程一内，依次下载，用时373分钟，线程二内，依次下载，用时为376分钟，线程三内，依次下载，用时为338分钟，线程四内依次下载用时为350分钟。第一阶段结束，线程一，二，四合并，下载，最终剩余，这时既保证了急需文件全部下载完成，有办证了下载文件数量最多。故此时为最优。5.4.2问题4的求解 在问题三建立模型的前提下，利用贪心算法继续优化，由于问题3只考虑了文件下载的最多个数与积分问题，而把需求问题忽略了，因此在优化模型时，需要在前提下再加进约束条件，即急需文件优先下载的方法，在7小时结束之前，按文件的需求程度不同，来确定下载的优先顺序。在图5.6的基础上，改进模型的下载计划为，文件，为急需文件，因此需要优先下载，在问题三模型的基础上增加优先顺序，因此线程内的文件下载顺序按如下方式安排，以-，中剩余，为第一阶段结束的标志，线程一内，依次下载，用时373分钟，线程二内，依次下载，用时为376分钟，线程三内，依次下载，用时为338分钟，线程四内依次下载用时为350分钟。第一阶段结束，线程一，二，四合并，下载，最终剩余，这时既保证了急需文件全部下载完成，有办证了下载文件数量最多。故此时为最优。六 模型检验在求解个文件总下载速度超过是小概率事件时，用的是。下面我们取了组随机数（具体见附件），计算发现这组数据的和都是小于的。在不同方式可否同时下载上，我们用实际模拟，在网上同时用不同的下载工具下载，发现很多下载工具是可以的。而在答案的合理性方面，将20种文件下载量之和除以总的稳定速度，得到时间为7时26分30秒。而问题一的答案和问题二的答案都大于7时26分30秒，且相差不大，证明答案是可信的。七 模型优缺点和改进7.1模型的评价7.1.1模型的优点1、该模型充分利用每秒的最大速率，尽可能减少下载所有文件所用的时间；2、运用和对小概率事件计算分析，结果可信；3、在第一问中，把求解的最优策略分解为几个子策略，然后求解子策略的最优解，简化计算，便于分析；4、把问题转化为动态规划的背包问题，易于理解；5、用动态规划解决这个问题，效率高，思路清晰简便，且易于实现。7.1.2模型的缺点1、所建的模型只是一个简化的模型，和现实有差距；2、事实上，进入论坛、点击下载是需要时间和带宽，而本题没有考虑；3、在第一问的求解中，还可以进一步优化。7.2模型的改进对于问题一的下载方案的建立，本文将方式一的文件与方式二的文件分开考虑，即方式一的文件只能以小于的速度，方式二文件只能以在左右的速度进行下载，只在中间一部分将两种方式结合考虑，在方式一下载的最后阶段，部分方式一的文件未下载完成，对下载带宽的分配不合理。而实际情况下，方式二的下载速度可以在低于的任意速度进行下载，即选择方式二的文件加入方式一文件组合下载的过程，将20个文件按文件大小重新排序。前文中的方案是暂停方式一未完成部分的下载，将其留到最后与方式二剩余部分组合下载，这样操作需要对暂停时间精确把握，操作繁琐。所以，在进行方式一文件时，选择与其大小类似的文件，以方式一的网速同时下载，则当方式一文件结束时，剩余方式二文件可继续与其余方式二文件结合下载。方式二文件中部分文件大小与方式一文件近似，可在方式一文件下载过程中，以小于的稳定速度下载，与方式一文件一起下载，在第一阶段选择号文件和方式二中的号文件同时下载，都以速度进行下载，在前个文件下载完成时，逐步启动方式二号文件，再将余下文件组合下载，即号组合，号文件组合，补充了前文方案中只有单个文件下载的部分，充分利用了带宽。八 模型推广动态规划法是求解决策过程中最优化的数学方法，在经济管理、生产调度、工程技术和最优化等方面得到了广泛的应用。如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其他方法求解更为方便。九 参考文献1 韩中庚，数学建模方法及其应用M，北京：高等教育出版社，20052 韩中庚，数学建模竞赛获奖论文精选与点评，北京：科学出版社，20073 盛骤，谢式千，概率论与数理统计，北京：高等教育出版社，20034 姜启源，数学模型（第二版），北京：高等教育出版社，19925 费业泰，误差理论与数据处理（第五版），北京：机械工业出版社，2004.66 韩中庚，数学建模方法及其应用，