矩阵理论在通信的应用

.

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

2.1、完全幺模矩阵

若矩阵A的说有字方阵的行列式都为0或1，则矩阵A为完全幺模矩阵。

接下来，我们利用归纳法证明上文中提到的点边关联矩阵N是“完全幺模矩阵”。

2.2、幺模矩阵

假定矩阵A行满秩，若A的所有基矩阵(A的子方阵，且该矩阵

的所有列线性无关)的行列式都为1，则矩阵A为幺模矩阵。

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

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

1，因此完全幺模矩阵是幺模矩阵。

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

首先，基本解的非基变量取值都为0；基变量部分XB由A的基矩阵B定义：BXB=b。然后，令Bjb表示用矢量b替换B的第j列后得到的矩阵；xj表示XB的

Word 资料

.

第j个元素。最后，由线性代数矩阵理论部分的克拉默(Cramer)法则求解可得

。由于Bjb是整数矩阵，B的行列式为1，显然基本结构xj都是整数；

另外基本可行解必是基本解。由此，我们可得以下结论：假定矩阵A为满秩且为幺模矩阵，同时假定矢量b的元素都是整数；则由多面体中，基本可行解必为整数。

定义的

3、最小费用流的整数解

3.1、最优解是否为整数解

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

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

怎样避免这个问题呢？首先想到的是我们可以再约束条件中加入边上流变量

xij必须为整数的约束，即；也就是说边lij上要么存在1的流量，要么没

有流从这条边上流过。但是增加了约束条件必然会增加运算量，这显然是我们不希望看到的。

Word 资料

.

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

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

3.3、结论

至此，我们首先对最小费用流问题进行了线性规划建模，然后我们对线性规划建模求得的解是否为整数解提出了疑问。接下来，我们引入了矩阵理论中完全幺模矩阵和幺模矩阵的知识，得到了幺模矩阵的解必为整数解的结论。最后，我们注意到关联矩阵N实际上是完全幺模矩阵，也就是幺模矩阵；这样一来，最小费用流问题中建立的线性规划模型的解便必为整数解！

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

第四章 感想

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

Word 资料