资源文件下载模型

1、资源文件的下载优化方案模型摘要 本文我们根据题目的要求，在合理的假设之下，利用MATLAB和LINGO，将各个条件下的问题逐个分析，建立了资源下载的优化模型，并且给出了最优下载计划。对于问题（1），将下载方式分为三个阶段。根据方式1的方式2的下载速度和文件大小，利用MATLAB软件对方式1的八个文件大小排序，利用软件实现合理安排，使时间最短。第一个阶段为方式1和方式2的文件同时下载，速度和达到宽带最大值，利用LINGO建立模型，算出第一个阶段的最优速度，得出此过程耗时为224.611min。进入阶段二，此后只有方式1的文件下载，并且同时下载六个文件，但是其中一个文件速度无法达到最大速度，即为4

2、12-5*70=62kb/s。当其中一个文件下载完毕后，第二个阶段结束，此过程耗时为134.2766min。接下来所剩文件的下载速度全部达到，进入下载的第三个阶段，此过程耗时为24.931min。总计耗时为383.819min=6.397h。其具体下载计划在问题分析里给出。对于问题（2），考虑积分的问题，在问题（1）的基础上，考虑问题（1）的方案能否满足积分的需求，根据多目标规划，16个文件所需积分总数为80分。由于第一次回答问题无需等待，升级后第一次回答问题也无需等待，故获得大于等于80积分的时间为140min。增加此约束条件后最优解不受影响，故最优解及最优方案不受影响。对于问题（3），在考

3、虑积分和上机时间有限的前提下，达到下载文件数量最多的目标，根据多线程下载优化模型，建立了多条线路同时下载的方案，通过对大量数据进行的假设，分析，得出最优解，即能下载15个文件，并且找出8个最优下载计划。对于问题（4），仍然考虑积分和上机时间，以及需求程度的问题，在这些条件下实现下载文件数量的最多，针对此问题，在问题（3）已建立的模型基础上，利用贪心算法，让急需文件优先下载，得出最优下载方案，急需文件全部下载，总文件数为15。之后，我们对己建立的模型利用多线程下载方法优化，得出问题更准确的最优下载时间和下载计划。文章最后，对模型的缺点进行分析，提出模型存在的问题，并且提出了改进方案，通过模型的建

4、立，为下载者节省大量的时间。同时此模型对日程安排，生产流程规划也有很好的推广性。关键词：局部最优分析法 主要目标分析方法 多线程规划 1.问题重述现在互联网发展迅速，网络资源丰富。人们在日常生活及学习中，经常需要在网络上下载需要的文件资料。某学生需要在某论坛下载资料，需要下载的文件共有16个，由于下载方式的不同，下载文件具有不同的下载速度。现在的文件共有两种下载方式（每个文件有且仅有一种下载方式），方式1的下载速度最高是70kb/s，方式2的下载速度最高是390kb/s，16个文件的大小、下载方式及需求程度等资料见附件。另: 由于网络的原因，1.每种下载方式的下载速度都有在10%范围内的波动；

5、2.该生所用电脑网络带宽下载速度最高可达412kb/s.问题：（1）建立数学模型解决如何安排下载计划，使得最短时间内下载完成所需文件；（2）该论坛将注册用户分为新生（回复问题在0-20次），二年级生（回复问题在20-25次），三年级生（回复问题在25次以上）等等级，下载资料需要积分，提供注册用户回复问题每次可获得积分4分，新生每30分钟可回复一次问题，二年级生每20分钟可回复一次问题，三年级生每10分钟可回复一次问题。该生现有积分51分，已回复问题在17次，如何安排下载以及获得积分的计划，使得其可在最短时间内下载完成所需文件。（3）在问题2的条件下，该生现在只有6小时的上机时间，如何安排下载计

6、划，使得其可在规定时间内下载得到所需文件数量最多。（4）在问题2，3的条件下，由于资料的需求程度不一致，要求下载的资料中，急需的文件数量要比一般程度的文件数多，使得其可在规定时间内下载得到所需文件数量最多。2.问题分析实际中文件的下载速度是一直波动的，但波动不大，本文为了便于计算假设下载速度恒定。针对问题(1)，有两种下载方式，方式1和方式2，最大网速分别为70kb/s和390kb/s，并且所用宽带最大网速为412kb/s，考虑网速的最大利用以及时间的同时利用。使用LINGO软件对模型进行初步优化，得出方式1和方式2的最优下载速度，用此最优下载速度又可得出每个文件的最短下载时间（见附表2，表示

7、最优速度下不考虑其他因素的下载时间），据此时间估算最优下载方案，进而将整个下载过程分为三个阶段，分别对各个阶段。以下为三个阶段的网速分配和下载计划示意图。图1第一阶段网速分配示意图图2第二三阶段网速分配示意图图1表示第一阶段若要时间最优，则方式1和方式2的文件同时下载，可充分利用宽带网速。图2表示第二三阶段时只剩方式1的文件下载时，选择方式1的下载速度和为宽带最大速度。对于问题(2)为在问题一的基础上考虑积分的问题，有附件数据知道，16个文件所需积分总数为80分。由于第一次回答问题无需等待，升级后第一次回答问题也无需等待，故获得大于等于80积分的时间为140min。由第一问的下载计划知道，该同

8、学的积分不影响第一问的最优计划，故第二个问题里的下载安排不变。针对问题(3)为考虑有限的上机时间，即只有六个小时，由问题1知道，下载完成所有文件的时间为T（hours），则只需验证（T-6）(hours)的时间内，不能下载完的文件数W，即可得最大下载文件数为（16-W）个。问题(4)在考虑积分和上机时间的限制下，根据需求程度下载。此时，将不同的需求程度给以相应的权重，利用规划等方式解决该问题。3.模型假设与符号说明3.1模型假设（1）假设文件下载时，文件下载时速度可控制，且忽略网速波动。（2）假设一个文件下载完毕后立即下载下一个文件，无时间间隔。（3）假设下载过程中人的操作时间可以忽略，不影响

9、整个模型。3.2符号说明 表示第i种下载方式的下载速度； 表示最大带宽速度； 表示方式1最优下载速度； 表示方式2最优下载速度；表示第二阶段中最小速度； 表示最优下载时间（min）； 表示第一阶段所耗时间（min）； 表示第二阶段所耗时间（min）； 表示第三阶段所耗时间（min）； 表示方式1中最大文件； 表示方式1中最大文件在第一阶段下载后所剩文件大小； 文件在第一阶段下载所用时间； 最终下载时间； 表示方式1的第i个文件大小（i=18）； 表示方式2的第j个文件大小 (j=916)； 表示文件下载所需要的积分的大小（i=1.16）；4.数据分析和模型建立4.1 原始数据分析考虑16个文件

10、的下载方式及文件大小，由局部最优方法，先考虑下载速度的最大利用，再考虑速度的合理分配。建立局部最优规划模型，利用LINGO实现，得出下载速度的最优分配为：方式1下载速度70kb/s，方式2下载速度342kb/s，再根据该局部最优模型得出的理想速度，算出每个文件的最短下载时间（见表4.1）。表4.1文 件大小(M)下载方式最优速度分配最优速所需时间（min）时间和file 1392170kb/s95.5731100.801file 26501158.476file 35501134.095file 4380192.648file 55901143.848file 66531159.208file

11、 77001170.667file 86001146.286file 95502342kb/s27.4464224.611file 10563228.0951file 11661232.9856file 12600229.9415file 13350217.4659file 14610230.4405file 15578228.8437file 16589229.39264.2模型建立4.2.1问题（1）的模型建立对问题（1），现将下载过程分为三个阶段，根据方式1的方式2的下载速度和文件大小，由表4.1可知，方式2的下载时间明显少于方式1的下载时间，第一个阶段考虑方式1和方式2的文件同时下载，

12、对方式1的文件大小进行排序，分别选择方式1中两个最小文件先后和方式2一块下载。方式1以最大速度下载，并且方式1、2速度和达到宽带最大值，利用LINGO建立模型，算出第一个阶段的最优速度，得出下载方式1的最优下载速度为，方式2的最优下载速度为。按此最优下载速度，下载至方式2的文件全部下载完成为第一个阶段，记第一阶段耗时为：由表4.1知道此时方式1的文件在此之前已下载完，文件和文件下载时间为（+）*1024/70*60(min)，此时选择方式1中的最大文件继续下载，下载时间为记为=（+）*1024/70*60，剩下部分进入第二阶段继续下载所剩文件大小记为=70*60/1024。进入阶段二，此后只有

13、方式1的文件下载，并且同时下载六个文件，但是其中一个文件速度无法达到最大速度70kb/s，即为412-5*70=62kb/s。由第一阶段下载所剩的文件大小，对现有文件大小排序，将其中最小的文件下载速度设定为62kb/s，故当剩余文件中的最小文件以70kb/s的速度下载完后，62kb/s的速度升为70kb/s，继续下载，此时第二个阶段结束，此过程耗时为接下来所剩文件的下载速度全部达到70kb/s，进入下载的第三个阶段。将此过程所剩文件再次排序，取最大文件进行计算，即为此阶段所耗时间。最后得出问题（1）的最优时间为：最后有三个阶段的划分模型得出了最优下载计划为图4.1 一二三阶段下载计划示意图图4

14、.1表示整个过程（即一二三阶段）的下载计划，红线表示阶段的划分，数字对应下载的文件号。4.2.2问题（2）的模型建立对于问题(2)为在问题（1）的基础上考虑积分的问题，有附件数据知道，16个文件所需积分总数为80分。由于第一次回答问题无需等待，升级后第一次回答问题也无需等待，故获得大于等于80积分的时间为140min。由第一问的下载计划知道，该下载计划的三个阶段，第一个阶段为时间为，第二阶段时间为，第三阶段时间为。4.2.3问题(3)的模型建立问题三：现将解决问题1，2的模型拿来套用，最终发现，最多只能下载13个文件，有三个文件始终无法下载完。这时，考虑重建模型，看是否能在六小时内下载更多文件

15、。模型前的计算：因为时间已经限定为六小时，即为3600分钟，因此，只要在3600分钟内下载的文件最多时，就保证了文件下载最多，由此可以把文件下载的速度问题转化为时间和最小问题。据此展开讨论：当按方式一下载的文件都以70kb/s下载时，都按342kb/s下载，此时各个文件下载完所需的时间如下：表4.2文件大小(M)下载所需时间（min）文件大小（M）下载所需时间（min）file 1392按70kb/s 95.573file 9550按342kb/s 27.446file 2650158.476file 1056328.095file 3550134.095file 1166132.986fil

16、e 438092.648file 1260029.941file 5590143.848file 1335017.466file 6653159.208file 1461030.441file 7700170.667file 1557828.844file 8600146.285file 1658929.39345154501224.611黄色代表急需下载的文件由表4.2分析，假设一：将过程分为两个阶段，第一个阶段分为两个线程，一个线程速度为70kb/s，另一个线程为342kb/s。以完全下载完为第一阶段结束标志。当和中有一个文件同时下载时，这样可以保证在刚第一阶段达到最大。但是第二阶段的下载

17、过程中，通过定性分析可知，最多下载文件只能为13个，依然不能达到最优。假设二：将过程分为两个阶段，第一个阶段分为三个线程，前两个线程速度为70kb/s，都用来下载，最后一个线程速度为372kb/s，用来下载，以完全下载完为第一阶段结束标志。再建立表格：表4.3文件大小(M)下载所需时间（min）文件大小（M）下载所需时间（min）file 1392按70kb/s 95.573file 9550按272kb/s 34.51file 2650158.476file 1056335.325file 3550134.095file 1166141.475file 438092.648file 1260

18、037.647file 5590143.848file 1335021.961file 6653159.208file 1461038.275file 7700170.667file 1557836.267file 8600146.285file 1658937.64745154501283.107表4.4时间和（min），254.049229.668188.221239.421254.781266.24241.858时间和（min），316.952292.571251.124302.324317.684329.143304.761时间和（min），,，329.875316.952226.74

19、3277.943293.303304.762304.762时间和（min），303.056314.515290.133236.496251.856263.315238.933由表4.3、4.4知：在283.107时间内，线程一能把，下载完成，线程二能把，下载完成，此时，全部下载完成。但在第二阶段只剩余76.893分钟，剩余的四个文件不能下载，改变线程一，二的下载资源依然有三个文件无法下载完成。假设三：将过程分为两个阶段，第一阶段分为四个线程，前三个线程下载速度为70kb/s，最后一个线程下载速度为202kb/s。以中任意七个下载完成为第一阶段结束标志。列出图表：表4.5文件大小(M)下载所需时

20、间（min）文件大小（M）下载所需时间（min）file 139295.573file 955046.469file 2650158.476file 1056347.567file 3550134.095file 1166155.847file 438092.648file 1260050.693file 5590143.848file 1335029.571file 6653159.208file 1461051.537file 7700170.667file 1557848.834file 8600146.285file 1658949.76445154501黄色表示急需文件由此模型知：在

21、第一个阶段时，可以任意选择三个线程进行下载，此时没个文件都能达到最大。都以202kb/s的速度依次进行下载，当还剩一个文件时，第一阶段结束，由于的每个文件下载用时都不一样，因此第一阶段的结束时间也不固定，假设第一阶段结束时没有下载完，此时，第一阶段用时为308.463。将，放在线程一内依次下载用时为304.762分钟。，放在线程二内依次下载用时为302.324分钟。将，放在线程三内依次下载用时为347.429分钟。这样将线程分配完毕，在第二阶段时，将线程三保留，线程一，二，四合并，此时下载速度为342kb/s。用合并线程下载。直到六小时结束，此时和全部下载完毕，只剩没有下载。提出模型：由问题1

22、，2模型中提出的动态规划思想引出，该模型依然保留分为两个阶段，但每个阶段文件下载方式与之前的模型不同。该模型的第一个阶段分为四个线程，这四个线程把412kb/s的带宽分完，按照前三个阶段的带宽为70kb/s，最后一个带宽的速度为202kb/s。在第一阶段完毕后，保留前三个线程中没有下载完的那个线程，其余的与202kb/s的线程合并，据此得出的方案最优。4.2.4问题四的模型建立问题四：在问题三建立模型的前提下，利用贪心算法继续优化，由于问题3只考虑了文件下载的最多个数与积分问题，而把需求问题忽略了，因此在优化模型时，需要在前提下在加进约束条件，即：急需文件优先下载的方法，在六小时结束之前，按文

23、件的需求程度不同，来确定下载的优先顺序。表4.5第一阶段：线程一： 70kb/s 303.056剩余56.944min按202kb/s 线程二： 70kb/s， 304.762剩余55.238min 46.469线程三： 70kb/s，346.697剩余13.303min 55.847 min线程四： 202kb/s，329.589剩余30.411min 51.537min 47.567min第二阶段： 29.571 min线程一，二，四，合并：342kb/s 29.393 min剩余0.607 min 48.834 min 49.764 min最后剩没有下载329.58min由表4.5知，为

24、急需文件，因此需要优先下载，在问题三模型的基础上增加优先顺序，因此线程内的文件下载顺序可以据图表所示的方式安排，以中剩余为第一阶段结束标志，线程一内，依次下载，用时为303.056分钟，线程二内，依次下载，用时为304.762分钟，线程三内依次下载，用时为346.697分钟，线程四内，依次下载，用时为329.589分钟。第一阶段结束，线程一，二，四合并，下载12，最终剩余，这时既保证了急需文件全部下载完，又保证下载文件数量最多。故此时为最优。5.模型的求解5.1问题(1)的解答根据问题（1）的模型，下载过程分为三个阶段：第一阶段时间为=该时间表示方式二的文件全部下载完成所耗时间。第二阶段时间该

25、时间表示方式1中最大文件即，以最优速度下载完所耗时间。第三阶段时间改时间表示现有方式1中最大文件即，以最优速度下载完所耗时间。故最有时间为最优下载计划为：5.2问题（2）的求解由于第一次回答问题无需等待，升级后第一次回答问题也无需等待，由于第一阶段和下载完成用时为188.22min，而积分获得所需时间为140min，由于：可获得积分83>所需积分80分故考虑积分限制时，最优下载计划不受影响。5.3问题（3）的求解因为时间已经限定为六小时，即为3600分钟，因此，只要在3600分钟内下载的文件最多时，就保证了文件下载最多，由此可以把文件下载的速度问题转化为时间和最小问题。据此展开讨论：当按

26、方式一下载的文件都以70kb/s下载时，文件二都按342kb/s下载，此时各个文件下载完所需的时间如下：由表4.2分析，假设一：将过程分为两个阶段，第一个阶段分为两个线程，一个线程速度为70kb/s，另一个线程为342kb/s。以文件完全下载完为第一阶段结束标志。当文件和文件中有一个文件同时下载时，这样可以保证在刚第一阶段达到最大。但是第二阶段的下载过程中，通过定性分析可知，最多下载文件只能为个，依然不能达到最优。假设二：将过程分为两个阶段，第一个阶段分为三个线程，前两个线程速度为70kb/s，都用来下载文件，最后一个线程速度为372kb/s，用来下载文件，以文件完全下载完为第一阶段结束标志。

27、由表4.3、4.4知：在283.107时间内，线程一能把文件，下载完成，线程二能把文件，下载完成，此时，文件全部下载完成。但在第二阶段只剩余76.893分钟，剩余的四个文件不能下载，改变线程一，二的下载资源依然有三个文件无法下载完成。由此模型知：在第一个阶段时，文件可以任意选择三个线程进行下载，此时没个文件都能达到最大。文件都以202kb/s的速度依次进行下载，当还剩一个文件时，第一阶段结束，由于文件的每个文件下载用时都不一样，因此第一阶段的结束时间也不固定，假设第一阶段结束时文件14没有下载完，此时，第一阶段用时为308.463。将文件，放在线程一内依次下载用时为304.762分钟。文件，放

28、在线程二内依次下载用时为302.324分钟。将文件，放在线程三内依次下载用时为347.429分钟。这样将线程分配完毕，在第二阶段时，将线程三保留，线程一，二，四合并，此时下载速度为342kb/s。用合并线程下载文件。直到六小时结束，此时文件和文件全部下载完毕，只剩文件7没有下载。5.4问题的（4）求解在问题三建立模型的前提下，利用贪心算法继续优化，由于问题3只考虑了文件下载的最多个数与积分问题，而把需求问题忽略了，因此在优化模型时，需要在前提下在加进约束条件，即：急需文件优先下载的方法，在六小时结束之前，按文件的需求程度不同，来确定下载的优先顺序。由表4.5知，改进模型的下载计划为，文件，为急

29、需文件，因此需要优先下载，在问题三模型的基础上增加优先顺序，因此线程内的文件下载顺序可以据图表所示的方式安排，以文件中剩余文件为第一阶段结束标志，线程一内文件，依次下载，用时为303.056分钟，线程二内文件，依次下载，用时为304.762min，线程三内文件.依次下载，用时为346.697分钟，线程四内文件，依次下载，用时为329.589分钟。第一阶段结束，线程一，二，四合并，下载文件12，最终剩余文件，这时既保证了急需文件全部下载完，又保证下载文件数量最多。故此时为最优。6.模型的优化6.1问题（1）模型的优化对于问题一采用多线程下载优化模型我们通过计算机的对数据的模拟，最终确定了最优的下

30、载方案。让计算机以70kb/s的速度一次同时下载三个方式一文件，我们通过统计计算出了各个文件在最优下载时间我们通过对比对文件进行了如下分类:下载速度 文 件一共所进行的时间（min）阶段一70kb/s5 6303.0563 7304.7621 2 4346.697202kb/s9 10 11 13 14 15 16329.589阶段二70kb/s 121.706140kb/s1224.827342kb/s1217.108390kb/s122.036所以从表格中我们可以清楚的看出分类后各组文件下载一共所需要的时间，而且我们可以从表格中算出这15个文件一共下载完成所需的时间为303.056+1.7

31、06+24.827+17.108+2.036=348.733min<360min，故只有没有下载但是360-348.733=11.267min，6个小时内还有一些剩余时间，这些剩余时间可以用来下载文件八，一共可以下载22*2.036*60+11.267*60*390=266.335.32Kb=260.093Mb。文件下载完还需要的时间为可以解出s=14.875min故可以得出优化后模型的求解为360+14.875=374.875min=6.2479h改进模型的下载计划为，文件，为急需文件，因此需要优先下载，在问题三模型的基础上增加优先顺序，因此线程内的文件下载顺序可以据图表所示的方式安排

32、，以文件中剩余文件为第一阶段结束标志，线程一内文件，依次下载，用时为303.056分钟，线程二内文件，依次下载，用时为304.762min，线程三内文件.依次下载，用时为346.697分钟，线程四内文件，依次下载，用时为329.589分钟。第一阶段结束，线程一，二，四合并，下载文件12，最终剩余文件，这时既保证了急需文件全部下载完，又保证下载文件数量最多。故此时为最优。6.2问题(2)的优化问题(2)在问题（1）的基础上考虑积分，因此改进模型也在问题（1）的改进模型上考虑。由于7.模型的评价该模型是建立在不考虑网速波动的情况下求出的网络资源下载最短时间，在这一假设下我们通过对模型的分析，运用多

33、局部最优分析法和目标分析的方法，进行了问题的分析和求解得出了相对比较完善的结果。7.1模型的优点（1）该模型比较完善的解决了网络资源下载时间最优问题，避免下载过程中资源的浪费。（2）从资源需要者的角度出发，较好的解决了最短时间内下载最多文件个数。7.2模型的缺点（1）模型未考虑下载速度波动的影响，但是在实际中存在波动，会影响最优下载时间。（2）忽略了人的操作对整个模型的影响。参考文献：1谢金星，薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005年。2韩中庚，数学建模竞赛获奖论文精选与点评，北京：科学出版社。3张德丰，MATLAB数值分析与应用，北京：国防工业出版社，2007年。4韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005年。附录： 程序排序程序a=(392 650 550 380