帮忙解下这道[内部网信息组织规划问题]

banya86

[U][B]

内部网信息组织规划问题

[/B][/U]

一个企业的内部网（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
编号        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

（2）你的模型能否推广到有多种新型号的服务器的问题，例如两种不同服务器，他们的容量和价格不相同。
（3）考虑下面的所谓“在线”信息进行规划问题：对每个信息块（内部，外部）是逐个决策的， 而且仅当对上一个信息块做出是否下载、如何放置的决定后，下一个信息块的参数才告诉决策者。对此问题能否设计一个算法求解，并对提出的算法的效果给以评价。

天地无用

这是浙大数模竞赛的题目嘛，可以参考用装箱问题的算法

banya86

我也知道,我就是看到他们的题目..
不知道怎么解啊?
各们高手们能列出表达式吗?

banya86

我要求大家用0-1规划来解!

subway

分支定界法 是装箱问题 按杨的话说是装箱不是背包 看到背包论文就不看下去

yuanxuemei

有没有人可以给一个具体的参考答案!

jnft007

我们在院赛时的论文，该论文获一等奖！
内部网信息组织规划问题
摘要：
该题总体来说是单目标规划与０－１整型规划相总合的问题，我们的主要解题思路是：首先确定目标函数——整个组织规划的总费用最少，然后根据题目中给出的一些主要条件如：服务器信息总容量，每个内部信息快必须放在某个服务器上等为限制条件建立模型。在具体给的例子中，我们在总费用尽量少的目标下，通过matlab编程，得出至少4台服务器的结论，再在限制条件的约束下得出组织规划方案：
5台服务器的信息块分配方案如下：（单位：MB，注括号为其编号，不带括号的为给的内部信息块，例　114（８）表示第８个外部信息块，容量为１１ ４）
第一台：264（4）、195、53（２）
第二台：361（3）、149
第三台：233（１0）、163（11），114（8）
第四台：257 ( 13 )、104（５）、147 （１5）
第五台：171、175（９）、157（1２）    总费用：6.65万
第二问中，由于问题的本质没变，目标函数，限制条件只要稍微改动既可推广到多种型号的服务器，具体模型见文中。
第三问中，我们提供了两种解决“在线”信息规划问题的方案（有利可图方案，多种因素下的综合评价法），经具体实例验证效果明显，有可行性。

         关键字：单目标规划  0－1整型规划 层次分析法 有利可图方案

一．        问题重述：
一个企业的内部网，对外它主动发布信息，对内它自身也是外部互联网用户。企业在发布信息时，将相应的信息主题分成内部信息块，分布在企业不同的服务器上。企业对外访问是有针对性的，若将那些被访问频繁的外部互联网信息块下载转为内部信息块，即可省下通信费用，但由 于服务器本身内存的限制，企业要有选择的下载外部信息块。
问：1、如何对信息进行组织规划使总费用尽可能的小，并求解实例；
2、所建模型能否推广到有多种型号的服务器的问题；
3、如何对“在线”信息进行规划，给出算法并评价该算法；
二．        基本假设：
1、        所购买的服务器能正常工作，中途不能出现系统崩溃或服务器坏掉的情况；
2、        企业所需要的外部信息块均可下载，且一次性下载，成功转化为内部信息块；
3、        下载外部信息块所发生的费用忽略不记；
4、        下载的外部信息块没有优先级别，即不存在下载的先后次序问题；
5、        外部信息的选择与服务器的购买方案主要由总费用最小决定，其它因素为次；

三．        符号说明：
1． n为内、外部信息块总数（初使内部信息块个数为n1（不包含后来转换的）,外部信息块个数n2（是供选择的外部信息），则n1+n2=n）；
2．        Ni为第i个外部信息的通讯费用；
3．        Ri为第i个外部信息的容量；（i [1,n2]）
4．        rj为第j个内部信息的容量；
5．                 表示下载第i个外部信息的系数， =0时表不下载， =1时表下载；
6．        C为每台服务器的总容量（Ck表示第k台服务器的容量，k=1,2,3…..,m       C总=C*m即所有服务器的总容量）
7．        F为购买一台服务器的费用（Fk表示第k台服务器的购买费用）；
8．        m为购买服务器的个数；
9．        M表示总费用（购买服务器和通讯费用的总和）；
10． 为第i个外部信息下载后将它放在第k个服务器上的系数， = 1时表示放在第k个服务器， = 0（k=1,2…,m）则表示放在其他服务器上；
11．Qjk为第j个内部信息将它放在第k个服务器上的系数，Qjk= 1时表示放在第k个服务器，Qjk=0（k=1,2……m）则表示放在其他服务器上；
  
四．  模型建立及求解
1．
问题分析和建模
在此问题中要求我们如何对信息进行组织规划，使得总费用最小，而总费用与服务器花费费用和外部信息块通讯费用有关。因此问题的关键在于如何对外部信息块进行选择，确定哪些信息块需要下载到服务器上，使之成为内部信息块以及如何将内部信息块放在不同的服务器上。

总费用可表示为：
M=F*m+
因此模型的目标函数可表示为：
min M=F*m+
    约束条件：
由于题目中规定每个内部信息块必须放在某个服务器上，因此要满足条件：   
上式表示服务器台数至少保障能存放初始内部信息块
     （  第i个外部信息块只放在一台服务器上）
     （第j个内部信息块只放在一台服务器上）
其中i=1,2,3………..,n2   
    j=1,2,3………..,n1   
服务器容量限制：
   +                     
其中k=1,2…………,m
Ri为第i个外部信息块的容量；（i [1,n2]）,  为下载第i个外部信息的系数， 为第i个外部信息将它放在第k个服务器上的系数， ， 取值范围为{0，1}因此 表示下载的外部信息块放在第k台服务器上的信息总量。
表示初始内部信息块放在第k台服务器上的信息总量。由上述分析建立模型：     min  M=  + =F*m+

St:           
其中 i=1,2,3………..,n2, j=1,2,3………..,n1,k=1,2,3…….,m为整数     、 、 为整数 取值范围｛０，１｝
实例求解：
给定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
单位通讯费用（单位：元/MB）        16.05        28.3        23.5        26.5        19.2        12.4        19.56        52.6
编号        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
单位通讯费用（单位：元/MB）        20        17.1        24.5        19.1        35.6        12.98        27.2        13.6
为充分掘取表中信息，我们计算了外部信息的单位通讯费用（见表中），并绘制了服务器单位费用（10000/512 元每兆）和外部信息的单位通讯费用之间的对比关系图（程序见附录程序一 one）


问题求解：
min M==F*m+ =m*10000+

St:         
  其中  ,i=1,2,3………..,n2, j=1,2,3………..,n1为整数 ,    、 、 为整数 取值范围｛０，１｝
根据上式我们运用MATLABLE软件编程（见附录: 程序二two）进行求解
运行结果为：总费用66500元，  服务器台数:  4台
下载第i个信息的信息量（后三个为原内部信息块容量）:
Columns 1 through 14
0    53   361   264     0     0     0   114   175     0     0   157   257     0
Columns 15 through 19

   147     0   171   195   149

由于程序中未体现每个内部信息块不可分割只能放在某台服务器上。
我们人工对上述结果验证，得处需要五台服务器，此时又可下载其它外部信息块。最终结果为：
第一台：264（4）、195、53（２）              
第二台：361（3）、149
第三台：233（１0）、163（11），114（8）
第四台：257 （13）、104（５）、147 （１5）
第五台：171、175（９）、157（１２）    总费用：6.65万


2.   我们的模型可以推广到有多种新型号的服务器的问题，因为他们的决策目标和相应约束条件没有本质区别。要解决型号不同的服务器，只要在原来模型的基础上进行参数修改即可。
参数如下所示：
Fk表示第k台服务器的价格，Ck表示第k台服务器的容量，k=1，2，3…..，m
则目标函数改动为：

min M=  + =  +

St:     

其中  ,i=1,2,3………..,n2, j=1,2,3………..,n1为整数 ,    、 、 为整数 取值范围｛０，１｝
3.   由于现实中企业的具体情况不同，我们制定了两种“在线”信息规划方案供选择。

方案（一）：有利可图方案
有利可图的基本思想，只要这种选择当前会带来利润，就采取它，不考虑这种选择会带来什么样的后果。
情况1、由于内部信息块必须存放于某一台服务器上，只要是内部信息块到来，必须保证有服务器可存放它。当无服务器或服务器剩余空间不足以存 放它时，那么就得购买新的服务器。
情况2、
对外部信息块是否下载的算法
（名词定义：外部信息单位费用=
            服务器单位费用= ）
      当外部信息的参数到来时，先看它的容量大小。
①如果现有服务器的剩余容量大于或等于它的容量Ri,则将它下载，变成内部信息块，这样在不增加其它费用的情况下，节省了通讯费用。
②如果现有服务器的剩余容量小于它的容量Ri,，即只有增加新的服务器才能将其下载时，我们的判断标准为关系式α ≤  ，其中α为大于1的某个实数，此式表明，当这个外部信息单位通讯费用等于或大于单位服务器费用的α倍时，则购买新的服务器，将它下载转化为内部信息块，否则不下载。α的的具体权值可由企业的具体情况和相关经验决定。这里推荐α取1.3。
      ③若外部信息块容量过大，即便是购买新的服务器也无法放入服务器，则不予下载。

下面对此算法进行验证和评价
为了具有可比性，这里采用题目中所给数据
假设：内部信息块到来顺序为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
权值（单位：元/MB）        16.05        28.3        23.5        26.5        19.2        12.4        19.56        52.6
γ        0.82        1.45        1.21        1.36        0.98        0.63        1.00        2.69
编号        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
权值（单位：元/MB）        20        17.1        24.5        19.1        35.6        12.98        27.2        13.6
γ        1.02        0.88        1.26        0.98        1.79        0.66        1.39        0.70
注：     γ= *    ，表中加下划线的数字所对应信息块必须下载

具体过程如下：
内部信息块
当大小为171MB的内部信息块到来时，购买服务器F1存放之；
当大小为195MB的内部信息块到来时，195<341,放入服务器F1中。
此时:    F1：171+195=366MB           余146MB
当大小为149MB的内部信息块到来时,149>146,须购买新服务器F2存放之.
外部信息块
当1到来时，虽然γ=0.82〈1.3 但是218〈363    ∴将1放入F2中
此时：   F1：171+195=366MB           余146MB
         F2：149+218=367MB           余145MB
当2到来时，∵γ=1.45〉1.3    53〈146     ∴将2放入F1中
此时：   F1：171+195+53=419 MB       余93MB
         F2：149+218=367MB           余145MB
当3到来时，∵γ=1.21〈1.3，而且316 MB大于任何一台服务器的剩余空间，∴不下载。
当4到来时，虽然γ=1.36〉1.3，但是服务器的剩余空间不够，所以必须购置新的服务器F3
此时：   F1：171+195+53=419 MB       余93MB
         F2：149+218=367MB          余145MB
         F3：264MB                  余248 MB
当5到来时，虽然γ=0.98〈1.3  但是104〈145     ∴将5放入F2中
此时：   F1：171+195+53=419 MB       余93MB
         F2：149+218+104=471MB        余41MB
         F3：264MB                   余248 MB
当6到来时，虽然γ=0.63〈1.3  但是121〈248     ∴将6放入F3中
此时：   F1：171+195+53=419 MB       余93MB
         F2：149+218+104=471MB        余41MB
         F3：264+121=385MB           余127 MB

jnft007

当7到来时，∵γ=1.00〈1.3    而且460 MB大于任何一台服务器的剩余空间，∴不下载
当8到来时，∵γ=2.69〉1.3   114〈127        ∴将8放入F3中
此时：   F1：171+195+53=419 MB       余93MB
         F2：149+218+104=471MB        余41MB
         F3：264+121+114=499MB       余13 MB
当9到来时，∵γ=1.02〈1.3    而且175MB大于任何一台服务器的剩余空间，
∴不下载
当10到来时，∵γ=0.88〈1.3    而且233MB大于任何一台服务器的剩余空间，
∴不下载
当11到来时，∵γ=126〈1.3    而且163MB大于任何一台服务器的剩余空间，
∴不下载
当12到来时，∵γ=0.98〈1.3    而且157MB大于任何一台服务器的剩余空间，
∴不下载
当13到来时，虽然γ=1.79〉1.3  但是服务器的剩余空间不够，所以必须购置新的服务器F4
此时：   F1：171+195+53=419 MB       余93MB
         F2：149+218+104=471MB        余41MB
         F3：264+121+114=499MB       余13 MB
         F4：257MB                   余255MB
当14到来时，虽然γ=0.66〈1.3  但是77〈93  ∴将14放入F1中
此时：   F1：171+195+53+77=496 MB    余16MB
         F2：149+218+104=471MB        余41MB
         F3：264+121+114=499MB       余13 MB
         F4：257MB                   余255MB
当15到来时，∵γ=1.39〉1.3  147〈255 ∴将15放入F4中
此时：   F1：171+195+53+77=496 MB    余16MB
         F2：149+218+104=471MB       余41MB
         F3：264+121+114=499MB       余13 MB
         F4：257+147=404MB           余108MB
当16到来时，∵γ=0.70〈1.3  而110大于任何一台服务器的剩余空间，
∴不下载
根据以上推算得出只要4台服务器便可,4台服务器的信息分布情况为:
F1：171+195+53+77=496 MB     余16MB
         F2：149+218+104=471MB       余41MB
         F3：264+121+114=499MB       余13 MB
         F4：257+147=404MB           余108MB

  这个结果与我们得出的最优情况要5台服务器相差不大，说明此算法具有有效性、可行性。


方案（二）：多种因素下的综合评价法（专家法）
1．        此方案主要针对只有购买新服务器才能将到来的外部信息块下载转化为内部信息块的情况。当信息块类型是内部信息块或是其它情况时，算法与方案（一）相同。
具体算法：
首先当外部信息块的参数到来时，让决策者给出影响决策的相关因素，如：企业资金状况、下载信息对资源的浪费、信息的下载对以后其它信息下载的影响程度、信息下载对企业节省费用程度 （此因素可根据单位通讯费用与服务器单位费用的比值进行评定）等。然后利用层次分析法计算各因素的权重，再由专家来对这些因素指标分别打分（可采用十分制）。
最后用权重与分数相乘得出每个因素的分数，再将它们相加得出总分数。
拿所得总分与基准分（由企业自行抉择）相比较，若大于它则下载，否则不下载。
比如：
①        用层次分析法确定权重
假如影响抉择的因素有：
：企业资金状况                          ：下载信息对资源的浪费
：信息的下载对以后其它信息下载的影响程度  ：信息下载节省费用程度
构造对称矩阵：
由于本题中，早已假设总费用最少为主要决定因素，故设：
                        
则逆对称矩阵为：A=
然后运用迭代法：
e =        e =A* e       e =     
其中 为A* e 的n个分量之和， k=1,2……
我们利用matlab软件对其编程（程序见附录:程序三 three）
该程序运行结果得权重分别为：0.0874，0.1451，0.2882，0.4793
并且R=0.0092<0.1 通过了一致性检验。
因此得出目标决策函数：
Y=0.0874* +0.1451* +0.2882* +0.4793*
由于这里只考虑了四个因素，并每个因素采用十分制进行打分，故满分为40分，基准分这里推荐（25~30）。由于我们无法客观对各因素打分，所以无法进行具体的实例计算也不可进行效果对比分析。

五．模型优缺点分析
    模型优点:本模型不但可以方便简易的解决企业网络中使用同种型号的服务器的信息规划和管理问题,也可适用于当企业所使用服务器的型号不同时的信息规划问题，思路清晰，算法比较容易理解，方便实行。可移植性好，可以推广到其他规划问题。
但模型也存在不足之处，考虑因素不够全面。由于信息有不可估计的潜在价值，因此现实中企业肯定不会太在意钱的问题，但由于题目中只要求在费用上的最优，因此我们也只好把费用当作重要因素建模。

六．模型的推广       
     由于本模型主要是规划问题的解决，在推广上也只能推广到其它累似的规划问题，如货品装箱，多背包问题等。

七．参考文献
1.《大学生数学建模竞赛辅导教材》   叶其孝主编    湖南教育出版社
2．《数学模型（第二版）》        任善强、雷鸣著    重庆大学出版社
3．《运筹学》                   谷源盛主编        重庆大学出
4．《数学模型建模分析》             蔡常丰编著           科学出版社

附录：
程序 一
one:
c=[218,53,361,264,104,121,460,114,175,233,163,157,257,77,147,110] ; %容量
m=[3500,1500,8500,7000,2000,1500,9000,6000,3500,4000,4000,3000,9000,1000,4000,1500];%费用
for i=1:16
     y(i)=10000/512;
o(i)=m(i)/c(i);
d(i)=o(i)/y(i)
end
o
x=linspace(1,16,16);
plot(x,o,x,y);
xlabel('外部信息编号');
ylabel('单位费用');
title('服务器单位费用和外部信息的单位通讯费用之间的对比关系图')


程序二
two:

% b为决定是否对第i个信息下载的系数，b(i)为1在对第i个信息进行下载，b(i)为0在对第i个信息不下载,后三个数据为1表示
%内部信息块必在服务器上
% c为各信息块的容量 ,后三个数据为内部信息块容量
% z 为总费用，由于目标为总费用最小，因此这里根据具体情况分析，我们给了它一个足够大值1000000
% m 外部通讯费用，后三个数据表示，内部信息块通讯费用为0
c=[218,53,361,264,104,121,460,114,175,233,163,157,257,77,147,110,171,195,149]; %容量

b=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1];%对b 的初始化
Z=1000000;                            %对z 的初始化
B=linspace(1,1,19);                    %对B 的初始化
m=[3500,1500,8500,7000,2000,1500,9000,6000,3500,4000,4000,3000,9000,1000,4000,1500,0,0,0];%通讯费用
        for i1=0:1                               %16中循环对b进行组合共2^16中
        for i2=0:1
        for i3=0:1
        for i4=0:1
        for i5=0:1
        for i6=0:1
        for i7=0:1
        for i8=0:1
        for i9=0:1
        for i10=0:1
        for i11=0:1
        for i12=0:1
        for i13=0:1
         for i14=0:1
         for i15=0:1
         for i16=0:1
                        
    b(1)=i1;
    b(2)=i2;
    b(3)=i3;
    b(4)=i4;
    b(5)=i5;
    b(6)=i6;
    b(7)=i7;
   
    b(8)=i8;
    b(9)=i9;
    b(10)=i10;
    b(11)=i1;
    b(12)=i12;
    b(13)=i13;
    b(14)=i14;
    b(15)=i15;
    b(16)=i16;
    d=c.*b;                                                 %需要下载的那些外部信息块的信息量
    z=sum((B-b).*m)+round((sum(d)/512)+0.5)*10000 ;          %通信费用
    if z<Z
        Z=z;                                         %记录通信费用最小值
        C=b;
        M=round((sum(d)/512)+0.5);
    end
   
   
   
  end
end
  end
end
  end
end
  end
end
  end
end
  end
end
  end
end
  end
end
C                                 %C(i)表是否下载第i个信息w为1则下载
Q='总费用为:'
Z                                 %通信费用
Q='服务器太台数:'
M                                 % 初步服务气台数
Q='下载第i个信息的信息量:'

W=C.*c        

程序运行结果：
C =
Columns 1 through 14
0     1     1     1     0     0     0     1     1     0     0     1      1     0
Columns 15 through 19
1     0     1     1   
Q =
总费用为:
Z =
66500
Q =
服务器太台数:
M =
4
Q =
下载第i个信息的信息量:


W =
Columns 1 through 14
0    53   361   264     0     0     0   114   175     0     0   157   257     0
Columns 15 through 19
147     0   171   195   149


程序三
three:
a=[1,1/2,1/3,1/5;2,1,1/2,1/4;3,2,1,2/3;5,4,3/2,1];
% a为所建立的判断距阵（数据只是以本人看法构造，可请有关专业人事，对不同因素打分）
b=[1/4;1/4;1/4;1/4]; %b为n*1距阵
n=4;                 %n为行数（有实际因素决定）
e=a*b;  
E=e/sum(e);
m=8;
for i=2:m            %m为需要跌代的次数（应给足够的大这里为8）
    e=a*E;
    E=e/sum(e);      %当值不在变化即为所求的权值
end                  %一致性检验
f=max(eig(a));     %a距阵秩的最大值
c=(f-n)/(n-1);       %r为随机一致性指标 ——————————可以查资料得到
if n==1
   r=0;end
if n==2
   r=0;end
if n==3
   r=0.38;end
if n==4
   r=0.9;end
if n==5
   r=1.12;end
if n==6
   r=1.24;end
if n==7
   r=1.32;end
if n==8
   r==1.41;end
if n==9
   r=1.45;end
r
R=c/r   

%若R小于0.1时则具有一致性，即此时的权重具有合理性）

E        %最终所求的权重

运行结果：
>>
r =

    0.9000


R =

    0.0092


E =

    0.0874
    0.1451
    0.2882
    0.4793

jnft007

遗憾的是，公式拷不下来。

jnft007

怎么不支持公式那？