《数学建模文件保存问题》由会员分享，可在线阅读，更多相关《数学建模文件保存问题（13页珍藏版）》请在金锄头文库上搜索。
1、题目： 文件保存问题摘 要本文就文件如何分配储存使所需软盘数最少问题建立数学模型进行分析.对问题建立0-1整数规划模型，同时运用穷举法配用软盘的个数的范围进行检验对少量的文件数目进行依次穷举，运用lingo语言编写程序求出最优解.得出相应的答案.而针对有大量文件数目的文件保存问题时，我们为了避免麻烦不再采取穷举的方法，而是运用二分逼近法分析取一个范围进行求解.这样使得问题变得简单.求出最优解，找出最为合理的一种方案. 最后就模型问题的优缺点进行分析并讨论了问题推广的价值.本题的最优求解，即：123456789使用空间第一个盘552533723884061474第二个盘4662871081141
2、644324611474第三个盘1373648511352 表1关键词： 0-1整数规划，穷举法，最优解，二分逼近法一、问题的重述将16个不能压缩的大小分别为：46KB，55KB，62KB，87KB，108KB，114KB，137KB，164KB，253KB，364KB，372KB，388KB，406KB，432KB，461KB，851KB的文件分别存放在若干个软盘上(.软盘的数量足够多)，每个空白软盘的容量是1.44MB，试建立优化模型在用最少的软盘的同时将所有文件分别储存进去. 二、模型假设模型假设： 1、所有文件不能分割，不可以压缩或拆分； 2、在1M =1024KB的情况下考虑问题；
3、3、各个软盘之间无明显差别；4、不考虑文件的重要程度；5、文件间不存在相互制约限制，即文件可以随意分配存储，不存在某几个文件必须存放在同一个软盘中；6、软盘数目足够多，对于问题不用考虑软盘不够用的情况.三、模型的符号说明符号说明：n : 文件的个数(.由题可知为16)；m: 分配文件所需的软盘的数目；q : 软盘的空间大小(.由假设知1.44*1024=1474)；:存储标记变量；：为剩余软盘的空间大小.四、问题分析软盘存储文件是用计算机优化存储文件的一种存储方式.它主要是以提高软盘空间的综合使用率来做到同样多的软盘可以存储更多的文件.换句话说，就是提高软盘利用率尽量减少软盘的剩余空间.而我们
4、将以0-1整数规划模型，同时借助穷举法解决问题，得出最优的分配方案，使文件均存储在确定的软盘中，且软盘数目最少.在具体建模过程，为研究问题的方便，我们将使用的软盘从1开始按自然数顺序依次编号，同时也对文件按从小到大的顺序编号，然后利用文件存储必须满足的条件，如一张软盘存储文件的总容量必须小于软盘的最大使用空间.文件的个数是确定的，且软盘的数目对于解决问题是足够多的，暂不做复杂的要求，文件存储在某个软盘中，基于都编号的原因，我们可认为是存储是一一配对的原则，如此将简化模型的复杂度.即做出如下约束条件：1、 若第个文件放在第个软盘中记为=1，其余不储存文件的软盘=0(.)可得约束条件：2、 由于软
5、盘空间大小固定，可知加入软盘文件大小总和不能超过软盘空间大小即得约束条件： 3、 由假设可知文件不可分割，每个文件有且只能分配在一个软盘中即得约束条件： 4、文件理想情况下所需要的软盘数目的约束条件： 同时的范围是 五、模型建立与求解 1、模型建立：对问题进行分析可知，若所用软盘的数量越少，则文件分配后软盘所剩余的总空间一定越小，则由此建立分配方案关于所需软盘数目的函数关系，可得模型为：目标函数： min 约束条件： 上述建立了0-1整数规划模型来求解所给文件分配最优化问题， 2、模型求解：根据题意可以把n(.n的数值比较小时)个文件随即分配到m个软盘中，此时m取最小值即为，若有解，则软盘数目
6、必定大于或等于，则取值时，用lingo软件可以编程求解，若此时取的m值使该题无解.接着取，继续先前的步骤计算直到，在这其中必然会有第一个使得lingo软件运行成功的某一个确定的值，因此那就即使所求之最优解.若此时所求得结果必然是模型的最优解了.通过lingo软件运行结果显示，就可以求出用到的最少软盘量以及各个文件的具体分配磁盘方案.当n的数值比较大时，我们采取二分法的分析方法对题目进行模型优化求解.即根据题意可以把n个文件随意分配到m个软盘中，此时m取最小值也为，将m值带入以上约束条件中，仍然运用lingo软件求解.若有解，则软盘数目必定大于或等于，则取值时，用lingo软件可以编程求解，若此
7、时取的m值恰好经lingo软件编程求解实现结果，即m即为最小的软盘数目.若此时取的m使该题无解，则选取m=n进行计算，必然成立，我们接着取用m=进行计算，若结果的正确显示lingo运行可选择的结果时，则说明软盘的最少个数存在于(.，)内， 否则软盘的最少个数m存在于(.，n)中取值，依次类推重复以上步骤继续计算.这样不断的二分逼近，最后求得的整数m即为最少软盘量了.针对本题而言，由于文件个数16为一个小整数值，故采用穷举法通过lingo软件可以求得当时就可以解决此问题了，即 123456789使用空间第一个盘552533723884061474第二个盘466287108114164432461
8、1474第三个盘1373648511352 表2所求的结果符合题目要求，且所需的软盘数最少，为最优选择.六、模型的推广及优缺点分析我们建立的模型可以给出一个文件保存问题的方案，能够给出明确的软盘最少数目及其各张软盘对文件的分配结果.在我们的假设前提下，能给出最优的方案，选用我们的方案不仅可以解决此问题，还可以对其它类似的问题进行推广，可以将要保存的文件数推广到N个. 下面对模型的优缺点进行分析：1、模型的优点：(1)我们的模型很简单直观易懂，要实现的想法也很明确，利用此模型能够帮助使用者使用尽量少的软盘装下要保存的文件.(2 ) 文中的方法对文件数量不是很大时，具有适用性，简洁性，实用性和可操
9、作性.(3)有很好的推广价值.2、模型的缺点 (1) 由于缺乏这方面的数据，我们有些权重的确定有一定的主观因素.(2) 由于我们的假设是固定的，我们设计最优方案时，是按我们的假设来考虑的，并没有考虑到方便查找或其他方面的因素，(3) 模型的求解对要保存的文件数量非常大时，需要的步骤数要较多，且需要运算的次数较多.3、模型的推广对于一般情况即N个文件需要保存时，我们可以按如下步骤求解：先确定所需软盘的下界及上界，再用二分逼近法确定最终的m值，然后列出存储文件的最优组合.七、参考文献1 刁在筠，刘桂真，素洁，马建华 运筹学第三版 高等教育出版社.2朱德通 最优化模型与实验 同济大学出版社.3姜启源
10、，谢金星，叶俊 数学模型第三版 高等教育出版社.4刘琼荪 何中市 傅鹏 任善强 数学实验 高等教育出版社.5谢金星 薛毅，优化建模与LINGO/LINDO软件，北京：清华大学出版社，2004年6韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005年八、附件lingo 程序及结果.sets: A/1.16/:u; B/1.m/; links(A,B):x;endsetsdata:u=46 55 62 87 108 114 137 164 253 364 372 388 406 432 461 851;v=1474;enddatamin=sum(A(i):u(i)*x(i,m);for(B
11、(j): sum(A(i):u(i)*x(i,j)=v);for(A(i):sum(B(j):x(i,j)=1);for(links:bin(x);End当时 程序如下，即：sets: A/1.16/:u; B/1.3/; links(A,B):x;endsetsdata:u=46 55 62 87 108 114 137 164 253 364 372 388 406 432 461 851;v=1474;enddatamin=sum(A(i):u(i)*x(i,3);for(B(j): sum(A(i):u(i)*x(i,j)=v);for(A(i):sum(B(j):x(i,j)=1);
12、for(links:bin(x);End当时，程序正确运行结果，即：Global optimal solution found. Objective value: 1352.000 Extended solver steps: 0 Total solver iterations: 2 Variable Value Reduced Cost V 1474.000 0.000000 U( 1) 46.00000 0.000000 U( 2) 55.00000 0.000000 U( 3) 62.00000 0.000000 U( 4) 87.00000 0.000000 U( 5) 108.0000 0.000000 U( 6) 114.0000 0.000000 U( 7) 137.0000 0.000000
