通信网络的设计问题.doc

通信网络的设计问题
摘要
计算机网络技术推动了时代的发展，对于通信网络的研究于人们有着十分重 要的意义。本文就某通信公司拟建一个具有80个结点的通信网络问题，建立了 以下相关模型并给出具体的实施方案。
针对问题一，本文运用图与网络的知费用最低，并且讨论 建立的模型的可靠性；其二就是以网络可靠度为约束条件，使得总的铺设费用最 低；最后需要探讨在一定的约束条件下，使得通信网络的可靠度极大化，总的铺 设成本极小化的方案。
对于问题一就如何设计出一种通信网络的铺设线路，使得总的铺设费用最低 问题的分析研究：由于通信网络是连通的，任意两点之间不多于一条直接相连的 链路，连线问题的数学模型就是图论中在连通的赋权图上求权最小的生成树。结 合运筹学中图与网络的知识，我们将问题转化成求解连通图当中最小生成树的模 型来求解，本文运用prim算法求解最小的生成树，在这里我们给出prim算法的 思想，即：任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把 不在树中的结点加进来。最后通过运用数学软件matlab来编程求解。
对于问题二
对于问题三
对于问题四
模型的基本假设
符号说明
% :第i个结点到第j个结点的距离
C,：第i个结点到第j个结点的单位费用
⑶：第i个结点到第j个结点的铺设费用
模型的建立与求解

运用Excel软件对第i个结点到第j个结点的铺设费用进行求解
由于附件中表一提供的是节点的距离表，表二提供的是节点间单位铺设费用表， 我们利用Excel对节点间的铺设费用编辑计算公式进行求解。
求解的公式如下：
Bjj = D. * C. (z = 1,2,...,80; j = 1,2,...,80)
得出第i个结点到第j个结点的铺设费用(单位的换算已在表格中注明)，铺设 费用的汇总表格见附录一。
运用prim算法求解最小生成树
求解的算法步骤如下：
1)
2)
3)
4)
利用matlab编程输出结果
模型的检验
模型的评价与改进
参考文献
附录
附录一：第i个结点到第j个结点的铺设费用汇总表格
附录二：prim算法基于matlab编程的实现及输出结果
运用mat lab软件编写的程序：
function A = fun(W)
[m, n] = size (W);
e = 0;
for i = 1 : n
for j = i : n
if W(i, j) ~二 0
e = e + 1;
E(e, :) = [i, j, W(i, j)];
end
end
end
% sort W's edge by weight
for i = 1 : e - 1
for j = i + 1 : e
if E(i, 3)
> E(j, 3)
temp
=E(j,:);
E(j,
：)=E(i,:)
E(i,
:) =temp;
end
end
end
A = zeros (1, 3);
S = 1 : n;
for i = 1 : e
% if find-set (u) 〜二 find-set (v)
if S(E(i, 1))〜二 S(E(i, 2))
% A = A + (u, v)
A = cat(1