数学建模文件保存问题Word下载.docx
《数学建模文件保存问题Word下载.docx》由会员分享，可在线阅读，更多相关《数学建模文件保存问题Word下载.docx（13页珍藏版）》请在冰点文库上搜索。
\
1474
第二个盘
46
62
87
108
114
164
432
461
第三个盘
137
364
851
1352
表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、各个软盘之间无明显差别；
4、不考虑文件的重要程度；
5、文件间不存在相互制约限制，即文件可以随意分配存储，不存在某几个文件必须存放在同一个软盘中；
6、软盘数目足够多，对于问题不用考虑软盘不够用的情况.
三、模型的符号说明
符号说明：
n:
文件的个数（..由题可知为16）；
m:
分配文件所需的软盘的数目；
q:
软盘的空间大小（..由假设知1.44*1024=1474）；
:
存储标记变量；
：
为剩余软盘的空间大小.
四、问题分析
软盘存储文件是用计算机优化存储文件的一种存储方式.它主要是以提高软盘空间的综合使用率来做到同样多的软盘可以存储更多的文件.换句话说，就是提高软盘利用率尽量减少软盘的剩余空间.而我们将以0-1整数规划模型，同时借助穷举法解决问题，得出最优的分配方案，使文件均存储在确定的软盘中，且软盘数目最少.
在具体建模过程，为研究问题的方便，我们将使用的软盘从1开始按自然数顺序依次编号，同时也对文件按从小到大的顺序编号，然后利用文件存储必须满足的条件，如一张软盘存储文件的总容量必须小于软盘的最大使用空间..文件的个数是确定的，且软盘的数目对于解决问题是足够多的，暂不做复杂的要求，文件存储在某个软盘中，基于都编号的原因，我们可认为是存储是一一配对的原则，如此将简化模型的复杂度.即做出如下约束条件：
1、若第
个文件放在第
个软盘中记为
=1，其余不储存文件
的软盘
=0（..
）可得约束条件：
2、由于软盘空间大小固定，可知加入软盘文件大小总和不能超过软盘空间大小即得约束条件：
3、由假设可知文件不可分割，每个文件有且只能分配在一个软盘中即得约束条件：
4、文件理想情况下所需要的软盘数目的约束条件：
同时
的范围是
五、模型建立与求解
1、模型建立：
对问题进行分析可知，若所用软盘的数量越少，则文件分配后软盘所剩余的总空间一定越小，则由此建立分配方案关于所需软盘数目的函数关系，可得模型为：
目标函数：
min
约束条件：
上述建立了0-1整数规划模型来求解所给文件分配最优化问题，
2、模型求解：
根据题意可以把n（..n的数值比较小时）个文件随即分配到m个软盘中，此时m取最小值即为
，若有解，则软盘数目必定大于或等于
，则取
值时，用lingo软件可以编程求解，若此时取的m值使该题无解.接着取
，继续先前的步骤计算直到
，在这其中必然会有第一个使得lingo软件运行成功的某一个确定的
值，因此那就即使所求之最优解
.若此时所求得结果必然是模型的最优解了.通过lingo软件运行结果显示，就可以求出用到的最少软盘量以及各个文件的具体分配磁盘方案.
当n的数值比较大时，我们采取二分法的分析方法对题目进行模型优化求解..即根据题意可以把n个文件随意分配到m个软盘中，此时m取最小值也为
，将m值带入以上约束条件中，仍然运用lingo软件求解..若有解，则软盘数目必定大于或等于
值时，用lingo软件可以编程求解，若此时取的m值恰好经lingo软件编程求解实现结果，即m即为最小的软盘数目..若此时取的m使该题无解，则选取m=n进行计算，必然成立，我们接着取用m=
进行计算，若结果的正确显示lingo运行可选择的结果时，则说明软盘的最少个数存在于（..
，
）内，否则软盘的最少个数m存在于（..
，n）中取值，依次类推重复以上步骤继续计算..这样不断的二分逼近，最后求得的整数m即为最少软盘量了..
针对本题而言，由于文件个数16为一个小整数值，故采用穷举法通过lingo软件可以求得当
时就可以解决此问题了，即
表2
所求的结果符合题目要求，且所需的软盘数最少，为最优选择.
六、模型的推广及优缺点分析
我们建立的模型可以给出一个文件保存问题的方案，能够给出明确的软盘最少数目及其各张软盘对文件的分配结果.在我们的假设前提下，能给出最优的方案，选用我们的方案不仅可以解决此问题，还可以对其它类似的问题进行推广，可以将要保存的文件数推广到N个.
下面对模型的优缺点进行分析：
1、模型的优点：
（1）我们的模型很简单直观易懂，要实现的想法也很明确，利用此模型能够帮助使用者使用尽量少的软盘装下要保存的文件.
（2）文中的方法对文件数量不是很大时，具有适用性，简洁性，实用性和可操作性.
（3）有很好的推广价值.
2、模型的缺点
（1）由于缺乏这方面的数据，我们有些权重的确定有一定的主观因素.
（2）由于我们的假设是固定的，我们设计最优方案时，是按我们的假设来考虑的，并没有考虑到方便查找或其他方面的因素，
（3）模型的求解对要保存的文件数量非常大时，需要的步骤数要较多，且需要运算的次数较多.
3、模型的推广
对于一般情况即N个文件需要保存时，我们可以按如下步骤求解：
先确定所需软盘的下界
及上界
，再用二分逼近法确定最终的m值，然后列出存储文件的最优组合..
七、参考文献
[1]刁在筠，刘桂真，素洁，马建华《运筹学》第三版高等教育出版社.
[2]朱德通《最优化模型与实验》同济大学出版社.
[3]姜启源，谢金星，叶俊《数学模型》第三版高等教育出版社.
[4]刘琼荪何中市傅鹏任善强《数学实验》高等教育出版社.
[5]谢金星薛毅，优化建模与LINGO/LINDO软件，北京：
清华大学出版社，2004年
[6]韩中庚，数学建模方法及其应用，北京：
高等教育出版社，2005年
八、附件
lingo程序及结果.
sets:
A/1..16/:
u;
B/1..m/;
links（A,B）:
x;
endsets
data:
u=46556287108114137164253364372388406432461851;
v=1474;
enddata
min=@sum（A（i）:
u（i）*x（i,m））;
@for（B（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
当
时程序如下，即：
B/1..3/;
u（i）*x（i,3））;
时，程序正确运行结果，即：
Globaloptimalsolutionfound.
Objectivevalue:
1352.000
Extendedsolversteps:
0
Totalsolveriterations:
2
VariableValueReducedCost
V1474.0000.000000
U
（1）46.000000.000000
U
（2）55.000000.000000
U（3）62.000000.000000
U（4）87.000000.000000
U（5）108.00000.000000
U（6）114.00000.000000
U（7）137.00000.000000
U（8）164.00000.000000
U（9）253.00000.000000
U（10）364.00000.000000
U（11）372.00000.000000
U（12）388.00000.000000
U（13）406.00000.000000
U（14）432.00000.000000
U（15）461.00000.000000
U（16）851.00000.000000
X（1,1）0.0000000.000000
X（1,2）1.0000000.000000
X（1,3）0.00000046.00000
X（2,1）1.0000000.000000
X（2,2）0.0000000.000000
X（2,3）0.00000055.00000
X（3,1）0.0000000.000000
X（3,2）1.0000000.000000
X（3,3）0.00000062.00000
X（4,1）0.0000000.000000
X（4,2）1.0000000.000000
X（4,3）0.00000087.00000
X（5,1）0.0000000.000000
X（5,2）1.0000000.000000
X（5,3）0.000000108.0000
X（6,1）0.0000000.000000
X（6,2）1.0000000.000000
X（6,3）0.000000114.0000
X（7,1）0.0000000.000000
X（7,2）0.0000000.000000
X（7,3）1.000000137.0000
X（8,1）0.0000000.000000
X（8,2）1.0000000.000000
X（8,3）0.000000164.0000
X（9,1）1.0000000.000000
X（9,2）0.0000000.000000
X（9,3）0.000000253.0000
X（10,1）0.0000000.000000
X（10,2）0.0000000.000000
X（10,3）1.000000364.0000
X（11,1）1.0000000.000000
X（11,2）0.0000000.000000
X（11,3）0.000000372.0000
X（12,1）1.0000000.000000
X（12,2）0.0000000.000000
X（12,3）0.000000388.0000
X（13,1）1.0000000.000000
X（13,2）0.0000000.000000
X（13,3）0.000000406.0000
X（14,1）0.0000000.000000
X（14,2）1.0000000.000000
X（14,3）0.000000432.0000
X（15,1）0.0000000.000000
X（15,2）1.0000000.000000
X（15,3）0.000000461.0000
X（16,1）0.0000000.000000
X（16,2）0.0000000.000000
X（16,3）1.000000851.0000
RowSlackorSurplusDualPrice
11352.000-1.000000
20.0000000.000000
30.0000000.000000
4122.00000.000000
50.0000000.000000
60.0000000.000000
70.0000000.000000
80.0000000.000000
90.0000000.000000
100.0000000.000000
110.0000000.000000
120.0000000.000000
130.0000000.000000
140.0000000.000000
150.0000000.000000
160.0000000.000000
170.0000000.000000
180.0000000.000000
190.0000000.000000
200.0000000.000000
升级会员 