数学建模文件保存问题.pdf

数学建模文件保存问题

题目:文件保存问题

摘要

本文就文件如何分配储存使所需软盘数最少问题建立数学模型进行分析.对问

题建立0-1整数规划模型，同时运用穷举法配用软盘的个数的范围进行检验对少量

的文件数目进行依次穷举，运用lingo语言编写程序求出最优解.得出相应的答案.

而针对有大量文件数目的文件保存问题时，我们为了避免麻烦不再采取穷举的

方法，而是运用二分逼近法分析取一个范围进行求解.这样使得问题变得简单.

求出最优解，找出最为合理的一种方案.

最后就模型问题的优缺点进行分析并讨论了问题推广的价值.

本题的最优求解，即:

123456789使用空间第一个盘55253372388406\\\\1474

第二个盘466287108114164432461\1474第三个盘137364851\\\

\\\1352

表1

关键词:0-1整数规划，穷举法，最优解，二分逼近法

-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);

a:第i个文件的大小;i

:存储标记变量;cij

z:为剩余软盘的空间大小.

-2-

四、问题分析

软盘存储文件是用计算机优化存储文件的一种存储方式.它主要是以提高软盘

空间的综合使用率来做到同样多的软盘可以存储更多的文件.换句话说，就是提高

软盘利用率尽量减少软盘的剩余空间.而我们将以0-1整数规划模型，同时借助穷

举法解决问题，得出最优的分配方案，使文件均存储在确定的软盘中，且软盘数目

最少.

在具体建模过程，为研究问题的方便，我们将使用的软盘从1开始按自然数顺

序依次编号，同时也对文件按从小到大的顺序编号，然后利用文件存储必须满足的

条件，如一张软盘存储文件的总容量必须小于软盘的最大使用空间..文件的个数是

确定的，且软盘的数目对于解决问题是足够多的，暂不做复杂的要求，文件存储在

某个软盘中，基于都编号的原因，我们可认为是存储是一一配对的原则，如此将简

化模型的复杂度.即做出如下约束条件:

1、若第个文件放在第个软盘中记为=1，其余不储存文件的软盘jaiiij

=0(..)可得约束条件:ak,jik

a,1或0ij

2、由于软盘空间大小固定，可知加入软盘文件大小总和不能超过软盘空间大

小即得约束条件:

n

a*c,q,j,1...m,iij,1i

3、由假设可知文件不可分割，每个文件有且只能分配在一个软盘中即得约束

条件:

m

c,1,i,1...16,ij,1j

4、文件理想情况下所需要的软盘数目的约束条件:

n，，a,i,,,i1,,,mq,,

,,，，

同时的范围是mm,n

-3-

五、模型建立与求解

1、模型建立:

对问题进行分析可知，若所用软盘的数量越少，则文件分配后软盘所剩余的总

空间一定越小，则由此建立分配方案关于所需软盘数目的函数关系，可得模型为:

nm

in目标函数:mz,q*m,a*c,,iij,,11ij

n,a*c,q,(j,1...n),iij,i,1,m