k重Π-循环矩阵逆矩阵的简便求法

循环矩阵是一类非常重要的特殊矩阵 ,它在数值计算、信号处理、编码理论、石油勘探等有广泛的应用 .文中引入一类新的特殊循环矩阵———k重Π 循环矩阵的概念 ,利用k重Π

多约束最短链路不相交路径的启发式算法

为求解多约束最短链路不相交路径(MCSDP(k))问题,提出了一种启发式的整数规划方法:FHABIP,并给出了算法搜索方案。根据问题的整数线性约束集合具有的结构特点,利用拉格朗日乘子把整数线性约束集合中的复杂约束引入到目标函数中,导出具有约束系数矩阵是全幺模矩阵特点的整数线性规划问题,从而使这类问题能用单纯形法容易求解。MCSDP(k)在求解线性规划问题的迭代过程中很容易地被求出。算法实验结果表明该算法快速有效。

一类特殊超图的S-匹配最大值的一种算法

超图的S-匹配是图的匹配的推广,文章利用全幺模矩阵的一些性质,给出了一类特殊超图的S-匹配最大值的一种算法.

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优.该问题是一个NP-完全问题.提出了一种新的基于整数线性规划模型选择路由的方法.思路是将复杂约束引入到目标函数作为罚项,得到一个松弛整数线性规划问题.因为约束系数矩阵是全幺模矩阵,松弛问题可以通过线性规划很快地求解.拉格朗日乘子的调整用罚函数的方法很容易计算.数值实验表明提出的方法是有效的.

求不相交QoS路由的一种整数线性规划方法

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.