一个企业的内部网（Intranet网），在互联网（Internet）上有两种功能．对外，它主动发布信息，介绍其最新产品和技术，为客户提供服务, 在公众面前为企业作宣传等；对内它自身也是外部互联网用户，要访问内部网以外的各种信息以了解市场，在商业竞争中保持有利地位．在企业发布信息时，将相应的信息主题分成块结构，称之为内部信息块，分布在企业内部网的服务器上．另外企业对外访问是有针对性的，对某些外部信息块的频繁访问会造成通信费用的增长．为了有效地降低通信费用，可以将那些被访问频繁的外部互联网信息块下载至内部网的服务器上，使之成为内部信息块．一旦成为内部信息，即可省下通信费用，而且访问速度大大提高．由于服务器本身内存的限制，企业要有选择的下载外部信息块，并放入适当的服务器或在适当的时候购买新的服务器以满足需要．
在此问题中，每个内部信息块必须放在某个服务器上，当然需要占用此服务器的内存．对每个可能有用的外部信息块，企业可以下载也可不下载．如果不将其从外部网上下载下来，则访问该信息将产生一定的通信费用；如果将其放在内部网上，将占用服务器的内存．当然如何决定将信息放在不同服务器上也是重要的．现假设共有n个内、外部信息，每个信息的容量已知，而且每个外部信息的访问费用也已知．每个服务器允许的信息总容量为C, 且购买新服务器的费用为F. 问如何对信息进行组织规划使总费用尽可能的小？
现企业的决策者希望对此问题进行研究，你的解答应至少回答：
（1） 就上述问题建立数学模型。并就下例求解：假设C=512MB, F=1万元，内部信息块的容量分别为171MB，195MB，149MB，可能有用的外部信息块的容量和相应的通讯费用如下表示。
|
编号
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
容量(MB)
|
218
|
53
|
361
|
264
|
104
|
121
|
460
|
114
|
|
通讯费用（万元）
|
0.35
|
0.15
|
0.85
|
0.7
|
0.2
|
0.15
|
0.9
|
0.6
|
|
性价比
|
622.9
|
353.3
|
424.7
|
377.1
|
520
|
806.7
|
511.1
|
190
|
|
编号
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
|
容量（MB）
|
175
|
233
|
163
|
157
|
257
|
77
|
147
|
110
|
|
通讯费用（万元）
|
0.35
|
0.4
|
0.4
|
0.3
|
0.9
|
0.1
|
0.4
|
0.15
|
|
性价比
|
500
|
582.5
|
407.5
|
523.3
|
285.5
|
770
|
367.5
|
733.3
|
（2）你的模型能否推广到有多种新型号的服务器的问题，例如两种不同服务器，他们的容量和价格不相同。
摘要：
首先，我把此问题看作是两个子问题的有机结合，即：
1。企业应该哪些外部信息块下载到内存上；
2。对于要下载的信息如何放置在购得的服务器上。
我将外部信息单位容量的通讯费与单位容量的内存花费做比较，从而初步确定哪些信息值得下载，哪些不值得。然后引入了下载某个信息块的当量节省价格来衡量下载某信息块的合算程度。
然后，我把信息的存放转化为一组0—1背包规划问题，并用动态规划进行了求解。然而背包问题所得的结果是不包含那些通讯费用比较小的信息块的（因为它们的当量节省价格为负），所以服务器的内存就可能有部分空间没有得到充分利用。于是我用贪心算法对背包规划所得的结果进行了修正。并得到了令人满意的结果。
对于有多种不同型号服务器的情况，我在同种型号算法的基础了做了些修改，也能得到较理想的效果。
关键字：数学建模，信息组织规划，0—1背包，动态规划。
一．问题重述：
企业要获取外部信息，可以将那些被访问频繁的外部互联网信息块下载至内部网的服务器上，使之成为内部信息块．一旦成为内部信息，即可省下通信费用，而且访问速度大大提高。由于服务器本身内存的限制，企业要有选择的下载外部信息块，并放入适当的服务器或在适当的时候购买新的服务器以满足需要。
在此问题中，每个内部信息块必须放在某个服务器上，当然需要占用此服务器的内存。对每个可能有用的外部信息块，企业可以下载也可不下载．如果不将其从外部网上下载下来，则访问该信息将产生一定的通信费用；如果将其放在内部网上，将占用服务器的内存。当然如何决定将信息放在不同服务器上也是重要的。现假设共有n个内、外部信息，每个信息的容量已知，而且每个外部信息的访问费用也已知。每个服务器允许的信息总容量为C, 且购买新服务器的费用为F。 问如何对信息进行组织规划使总费用尽可能的小？
二．模型假设：
1．由于信息被访问带有随机性，所以假设题目中给出的每一个可能用到的信息都是同等有用的，即忽略其访问频率上的差别。
2．不考虑信息的更新，通讯及硬件费用的变化等问题。
3．我们先考虑下载信息后在经济上带来的好处，而忽略访问速度等一些难以量化的因素。
三．符号说明：
n 信息块数量。
m 内部信息块数量。
Ai（i=1,2,…,n） 信息块容量。
Fi（i=m+1,m+2,…,n） 外部信息块的访问费用。
C 每个服务器允许的信息容量。
F 购买新服务器的费用。
V0 单位容量的内存花费。
Vi 单位容量的通讯费。
Xi 是否存储的决策变量。
Pi 当量节省价格。
四．问题分析：
设现在共有n个信息块，前m个是内部信息块，即有n-m个外部信息块。每块信息的容量分别是 Ai（i=1,2,…,n）， Fi（i=m+1,m+2,…,n）是每个外部信息相应的访问费用。每个服务器允许的信息总容量为C，且购买新服务器的费用为F。
现在先看单个信息，我们有两种方式来获取它。一是把它下载到内部网服务器上，这样就要负担内存的费用；二是不下载它，那么就要承担通讯费用。很自然地可以想到，要决定用哪一种获取方式，可以把需要的内存花费和其通讯费用折合成单位容量上的花费来进行比较，并取其小者。
单位容量的内存花费为定值:V0=F/C。
单位容量的通讯费Vi=F/C（i=m+1,m+2,…,n）。
内部信息块一定要占具内存空间，可以把其通讯费用看作0。
显然，对于单位通讯费小于单位内存费的信息，下载它是不合算的。这样，我们就把外部信息划分为两类。
现已知V0=F/C=0.001953。所以初步方案是：
Vi>V0时，就下载；反之就不下载。
为衡量一块信息下载的合算程度，我引入了当量节省价格Pi=Fi-V0*Ai，来表示下载此块信息能节省的费用。
对于题中给的例子，算得单位容量通讯费和当量节省价格如下。
|
编号
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
容量(MB)
|
218
|
53
|
361
|
264
|
104
|
121
|
460
|
114
|
|
通讯费用（万元）
|
0.35
|
0.15
|
0.85
|
0.7
|
0.2
|
0.15
|
0.9
|
0.6
|
|
单位通讯费
|
0.001605505
|
0.0028302
|
0.0023546
|
0.0026515
|
0.0019231
|
0.0012397
|
0.0019565
|
0.0052632
|
|
当量节省价格
|
-0.07578125
|
0.0464844
|
0.1449219
|
0.184375
|
-0.003125
|
-0.086328
|
0.0015625
|
0.3773438
|
|
编号
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
|
容量（MB）
|
175
|
233
|
163
|
157
|
257
|
77
|
147
|
110
|
|
通讯费用（万元）
|
0.35
|
0.4
|
0.4
|
0.3
|
0.9
|
0.1
|
0.4
|
0.15
|
|
单位通讯费
|
0.002
|
0.0017167
|
0.002454
|
0.0019108
|
0.0035019
|
0.0012987
|
0.0027211
|
0.0013636
|
|
当量节省价格
|
0.008203125
|
-0.055078
|
0.0816406
|
-0.006641
|
0.3980469
|
-0.050391
|
0.1128906
|
-0.064844
|
蓝色单元格标记的是下载合算的信息块，白色的是不合算的信息块。因为内部信息块是一定要被存储的，所以设其当量节省价格为M（M为一远大于其他值的整数）。
接下来的问题就是，要购买多少服务器来存放这些信息块，并如何安排存放位置才能使内存的使用率最高。
现在对一个服务器，引入变量Xi：
则可转化为0—1背包问题：
用动态规划法可以找出这个服务器上的最优存储方法，然后把已经存储过的那些信息块删去，然后对下一个服务器采用同样的背包规划。直到再增加服务器已经不能节省开销，即新服务器的价格F大于此服务器上存储的信息的总通讯费 
就停止计算。
四．模型求解
1．背包问题的求解：（动态规划法）
按可存储的信息块数划分为n个阶段。
状态变量S表示用于存储第一种物品至第n种物品的总存储量。
则状态转移方程为：
允许决策集合为：
最优值函数fk(S)是当总存储量不超过S时，服务器可以装入第1个到第n个信息块的最大节省费用。
即
因而可写出动态规划的顺序递推关系为：
然后编程逐步计算出fk(S)及相应的决策函数Xk最后得出的fn(C)就是所求的最大值，其相应的最优策略由反推运算即可得出。
根据上述算法用C语言编程，求得第一个服务器对应的决策函数及其总共节省费用值如下：
|
编号i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
Xi
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
|
编号i
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
|
|
Xi
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
总节省费用：2M+0.423828万元。
使用容量：487MB。
然后去掉第1，3，5，11个信息块，同法对第二个服务器做0—1背包规划，得：
|
编号i
|
2
|
4
|
6
|
7
|
8
|
9
|
10
|
12
|
|
Xi
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
编号i
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
|
|
Xi
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
|
总节省费用：M+0.398047万元。
使用容量：452MB。
然后去掉第2，16个信息块，以此类推，结果如下：
第三个服务器：
|
编号i
|
4
|
6
|
7
|
8
|
9
|
10
|
12
|
|
Xi
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
|
编号i
|
13
|
14
|
15
|
17
|
18
|
19
|
|
|
Xi
|
0
|
0
|
0
|
0
|
1
|
0
|
|
总节省费用：0.297266万元。
使用容量411MB。
第四个服务器：
|
编号i
|
4
|
6
|
8
|
9
|
10
|
12
|
|
Xi
|
0
|
1
|
0
|
0
|
0
|
0
|
|
编号i
|
13
|
14
|
15
|
17
|
19
|
|
|
Xi
|
0
|
0
|
0
|
0
|
0
|
|
总节省费用：0.144922万元。
使用容量361MB。
第五个服务器：
|
编号i
|
4
|
8
|
9
|
10
|
12
|
|
Xi
|
0
|
0
|
0
|
0
|
1
|
|
编号i
|
13
|
14
|
15
|
17
|
19
|
|
Xi
|
0
|
1
|
0
|
0
|
0
|
总节省费用：0.089844万元。
使用容量：338MB。
第六个服务器：
|
编号i
|
4
|
8
|
9
|
10
|
|
Xi
|
0
|
0
|
0
|
1
|
|
编号i
|
13
|
15
|
17
|
19
|
|
Xi
|
0
|
0
|
0
|
0
|
总节省费用：0.001563万元。
使用容量：460MB。
剩下的4，8，9，10，13，15，17，19个信息块的当量节省价格都为负，所以再购买服务器一定不合算。算法终止。
2．剩余内存的处理以及购买服务器的必要性分析。
可以注意到，由上述算法得到存储方法，每个服务器的容量是有剩余的。由实际经验可知，利用这些存储空间，即使是下载一些通讯费用比较低，也就是原本不适宜下载的信息，也是合算的。这样，我用贪心法来分配那些多余的空间。
目前算得的六个服务器的存储状况如下：
|
服务器编号
|
1
|
2
|
3
|
4
|
5
|
6
|
|
剩余存储量（MB）
|
25
|
60
|
101
|
151
|
174
|
52
|
|
存储情况（信息块编号）
|
1，3，5，11
|
2，16
|
7，18
|
6
|
12，14
|
10
|
未存储的信息块情况：
|
编号i
|
4
|
8
|
9
|
13
|
15
|
17
|
19
|
|
容量（MB）
|
218
|
104
|
121
|
233
|
157
|
77
|
110
|
|
当量节省价格
|
-0.07578
|
-0.00313
|
-0.08633
|
-0.05508
|
-0.00664
|
-0.05039
|
-0.06484
|
用贪心法对服务器存储状况表进行调整：
|
服务器编号
|
1
|
2
|
3
|
4
|
5
|
6
|
|
剩余存储量（MB）
|
25
|
60
|
24
|
47
|
17
|
52
|
|
存储情况
|
1，3，5，11
|
2，16
|
7，18，17
|
6，8
|
12，14，15
|
10
|
然后，分别对每个服务器进行计算，如果它所存储的所有信息块总共的通讯费用低于购买服务器的费用的话，这台服务器就是不必要的。计算结果如下表（内部信息的通讯费看作一个大值Y）：
|
服务器编号
|
1
|
2
|
3
|
4
|
5
|
6
|
|
信息通讯总费(万元)
|
2Y+0.6
|
Y+0.9
|
1.2
|
1.05
|
1.05
|
0.9
|
已知每个服务器的价格是1万元，所以第六个服务器不应购买。
五．模型推广：
如果有多种型号的服务器，只需将上边的算法做一些改动，仍然能够求解。例如有两种容量和价格不相同的服务器。我仍旧一台一台地挑选来决定其是否使用以及存储的情况。每次挑选的时候，对两种型号的服务器各做一次0—1背包规划，比较两种情况各自的存储信息块的通讯总费用，选择大的录用。然后删去已存储的信息块，反复上述操作。就得到各台服务器的型号以及存储状况。算法的终止条件和同一型号的情况相同。
六．参考文献：
运筹学（第三版），清华大学出版社，北京，2005.6
附录：
//背包问题的C语言程序实现
#include<stdio.h>
#define C 512 //内存容量
#define N 19 //信息块数量
#define M 10 //设内部信息块的当量节省价格为10
double f[20][520];//最优值函数
int main()
{
int A[20],X[20],b;
double P[20],maxn,a;
int i,j,k;
freopen("out.txt","w",stdout);
freopen("in.txt","r",stdin);//数据读入
for(j=1;j<=N;j++)
scanf("%d",&A[j]);
for(j=1;j<=N;j++)
scanf("%lf",&P[j]);
for(j=0;j<A[1];j++)//DP过程
f[1][j]=0;
for(;j<=C;j++)
f[1][j]=P[1];
for(i=2;i<=N;i++)
for(j=0;j<=C;j++)
{
if(j-A[i]>=0)
a=P[i]+f[i-1][j-A[i]];
else a=0;
if(a>f[i-1][j])
f[i][j]=a;
else f[i][j]=f[i-1][j];
}
for(i=N,b=C;i>0;i--)//反推过程
{
if(f[i][b]==f[i-1][b]) X[i]=0;
else
{
X[i]=1;
b-=A[i];
}
}
for(i=1;i<=N;i++)
printf("X%d=%d\n",i,X[i]);
printf("f=%lf\n",f[N][C]);
return 0;
}