矩阵理论在通信的应用

矩阵理论在通信网络中的应用

——利用幺模矩阵分析最小费用流问题

摘要

将通信网络中节点间的业务看作是一个流，假设一对节点间存在v个流量的业务需求，怎样使得最终达到满足要求且费用最小。通过线性规划建模，利用矩阵理论中完全幺模矩阵以及幺模矩阵的知识，保证求得的最优解为整数解，使得最小费用流问题得以解决。

关键字：最小费用流，完全幺模矩阵，幺模矩阵，整数解

ABSTRACT

View the business communication between nodes in the network as a stream, a v of the flow between nodes business needs, how to make the end meet the requirements and minimum cost. The linear programming model, by using matrix theory totally unimodular matrix and knowledge unimodular matrix, guarantee to obtain the optimal solution for the integer solution, so that the minimum cost flow problem can be solved.

Key Words: Minimum Cost Flow ,TotallyUnimodular ,Unimodular , integer solution

第一章矩阵理论简介

根据世界数学发展史的记载，矩阵理论概念剩余19世纪50年代，是为了解决线性方程组的需要而诞生的。1855年，英国数学家Caylag在研究线性变换下的不变量时，为了简介、方便而引入了矩阵的概念。矩阵的理论发展非常的迅速，到19世纪末，矩阵理论体系已经基本形成。到20世纪，矩阵理论得到了进一步的发展。目前，它已近发展成为在物理、控制论、经济学、等学科有大量应用的分支。

用矩阵的理论与方法来处理通信网络技术中的各种问题已越来越普遍。在通信工程技术中引进矩阵理论不仅使理论的表达极为简捷，而且对理论的实质刻画也更为深刻，这一点是不容置疑的，更由于计算机和计算方法的普及发展，不仅为矩阵理论的应用开辟了广阔的前景，也使通信网络技术的研究发生新的变化，开拓了崭新的研究途径，例如网络中的最小费用流问题、最短分离路径对问题、多商品流问题等，无不与矩阵理论发生紧密结合。因此矩阵的理论与方法已成为研究通信工程技术的数学基础。

第二章最小费用流问题

1、最小费用流简介

通信网络的主要作用是将业务从源端发送到宿端。为了充分利用网络的资源，包括线路、转接设备等，总是希望合理地分配流量，以是从源端到宿端的流量尽可能的大，传输的代价尽可能的小。但网络内流量分配并不是任意的，它受限于网络的拓扑结构，边和端的容量及费用，另外可能还有各种别的限制。

在通信网络中，如果将网络中节点间的业务看作是一个流的话，为满足一对节点对之间的业务需求而涉及业务流路径带宽分配被称作为单商品流问题。现假设一对节点间存在v个流量的业务需求，即需要在通信网络拓扑中通过利用其他一些中间节点并且合理的分配路径来搬运v个单位的流，使得最终达到满足要求时的总费用代价最小。

2、最小费用流问题的描述

通信网络中的各个交换机或者路由器通常可以看做是网络拓扑图中的一个个节点，它们之间的链路可以描述为各个节点间相连的线段。通过这样的转换就可以将网络拓扑通过图的形式描绘出来，以便进一步分析。

给定一个通信网络拓扑图G(V,E)，其中V表示的是所有节点的集合，E表示的是所有链路的集合，G(V,E)表示所有的点与边之间的通过一定连接关系所构成的图。除了源、宿端点外的其他节点，比如节点i，用vi表示；lij表示节点i和j之间的链路边；lij边上的流量用xij表示。另外，给定网络拓扑中每条边上的单位流量的代价为cij，边的带宽即容量为uij。

接下来给定一对节点对之间的业务流量需求的理论描述：(1)源点s到宿点t之间需要v个流量的业务，即源点s需要流出v个单位的流量，宿点t需要流入v个单位的流量；并且假设流入为正，流出为负 (2)网络中除了源点s和宿点t之外的其他节点i∈V−{s,t}流入的流量和流出的流量应该守恒，即相加为0 (3)每条链路边上的流量xij应该满足大于等于0且小于等于这条边lij上对应的带宽容量uij(4)优化目标是最小化总的链路流量与单位流量代价的乘积的和。

第三章矩阵理论分析最小费用流

1、最小费用流的矩阵形式

通过上面的分析，我们可以通过线性规划建模得到以下结果：

上面的线性规划建模结果是在确定的源点到宿点存在v个单位流的情况。实际情况下，我们考虑从源节点到宿节点，图中每个节点i的需求等于b(i)

，而不再是

单一值v或者0。这种情况下，上面的表达式需要做一点儿改变：

对比这两个表达式，我们可以看到只有约束条件的等式右端从v或者0变为了b(i)，b(i)表示顶点i的需求量或者供应量。需求量为负整数，供应量为正整数；所有的需求量之和等于供应量之和，即 ni=1b i =0。b(i)>0，则顶点i为供应节点；b(i)

为了书写方便，我们可以将约束条件及约束目标写为矩阵形式。这里定义m维矢量c={cij}、x={xij}、u={uij}，n维矢量b={b(i)}；将第一行的所有约束条件写为n×m维的矩阵N，矩阵N中的元素取值只为1或者-1；当顶点i是边j的起点时，Nij=1；当顶点i是边j的终点时，Nij=1；我们将矩阵N成为点边关联矩阵。这样线性规划表达式可以这样描述：

观察上述表达式，注意到最小费用流问题的矩阵形式具有最优化理论中单纯型法的标准型形式，即{xϵRn|Ax=b,x≥0}，这与最小费用流问题的矩阵形式中的约束条件{xϵRn|Nx=b,x≥0}具有相同的形式。这样我们就可以利用最优化理论中的单纯型法来分析求解这个矩阵问题。

但是，求出来的解是整数解吗？如果不是整数解还满足我们的要求吗？这个问题将在(三-3)部分得到解答，在此之前，我们首先来分析矩阵理论中完全幺模矩阵和幺模矩阵。

2、完全幺模矩阵和幺模矩阵

2.1、完全幺模矩阵

若矩阵A的说有字方阵的行列式都为0或±1，则矩阵A为完全幺模矩阵。接下来，我们利用归纳法证明上文中提到的点边关联矩阵N是“完全幺模矩阵”。

2.2、幺模矩阵

假定p×q矩阵A行满秩，若A的所有基矩阵(A的p×q子方阵，且该矩阵的所有列线性无关)的行列式都为±1，则矩阵A为幺模矩阵。

接下来我们证明完全幺模矩阵是幺模矩阵。

假定A是完全幺模矩阵；则由定义，其所有子方阵的行列式的取值都是0或±1。A的基矩阵必是子方阵；而且基矩阵的行列式不能为0。故而A的基矩阵行列式为±1，因此完全幺模矩阵是幺模矩阵。

紧接着，我们证明幺模矩阵的基本可行解必为整数。

首先，基本解的非基变量取值都为0；基变量部分XB由A的基矩阵B定义：BXB=b。然后，令Bjb表示用矢量b替换B的第j列后得到的矩阵；xj表示XB的第j个元素。最后，由线性代数矩阵理论部分的克拉默(Cramer)法则求解可得xj=|Bjb|/|B|。由于Bjb是整数矩阵，B的行列式为±1，显然基本结构xj都是整数；另外基本可行解必是基本解。由此，我们可得以下结论：假定矩阵A为满秩且为幺模矩阵，同时假定矢量b的元素都是整数；则由{xϵRn|Ax=b,x≥0}

定

义的多面体中，基本可行解必为整数。

3、最小费用流的整数解

3.1、最优解是否为整数解

回到(三-1)中最后的问题，得到的最小费用流问题的矩阵形式，即：

我们已经知道，通过求解上面的线性规划模型便可以得到最小费用流问题的最优解，但是求出来的这个解一定会是整数解吗？如果不是整数解，那便不满足我们的要求，因为我们不能将边上流量存在小数的路径成为一条由源点到宿点的路径。

怎样避免这个问题呢？首先想到的是我们可以再约束条件中加入边上流变量xij必须为整数的约束，即xij∈{0,1}；也就是说边lij上要么存在1的流量，要么没有流从这条边上流过。但是增加了约束条件必然会增加运算量，这显然是我们不希望看到的。

3.2、关联矩阵N是幺模矩阵

实际上，通过(三-2)中的矩阵理论知识，我们注意到关联矩阵N是完全幺模矩阵，根据(三-2.2)中的结论可知关联矩阵N必是幺模矩阵，从而以它为系数矩阵的最小费用流问题中，基本可行解必是整数。若线性规划存在最佳解，必可在某个基本可行解处得到，因此，最小费用流问题问题的最佳解必是整数解。

3.3、结论

至此，我们首先对最小费用流问题进行了线性规划建模，然后我们对线性规划建模求得的解是否为整数解提出了疑问。接下来，

我们引入了矩阵理论中完全幺

模矩阵和幺模矩阵的知识，得到了幺模矩阵的解必为整数解的结论。最后，我们注意到关联矩阵N实际上是完全幺模矩阵，也就是幺模矩阵；这样一来，最小费用流问题中建立的线性规划模型的解便必为整数解！

最终我们可以得出这样的结论：通信网络中遇到的最小费用流问题可以通过上述方法来求解。

第四章感想

通过矩阵理论的学习，深刻体会到了数学知识，特别是矩阵理论知识在实际生活中能够帮助我们分析、解决很多问题。虽然所学专业并不是数学专业，而是通信专业。但是通信工程专业中遇到的许多问题，却需要通过数学专业的矩阵理论知识来帮助我们求解。只有拥有了扎实的数学功底，才能更加娴熟的掌握通信工程专业的知识。