| 线性规划的改进行旋转算法 |
| |
| 引用本文： | 刘燕武,涂燕,周晓阳,汪寿阳,张忠桢.线性规划的改进行旋转算法[J].中国科学:数学,2023(11):1509-1532. |
| |
| 作者姓名： | 刘燕武 涂燕 周晓阳 汪寿阳 张忠桢 |
| |
| 作者单位： | 1. 武汉理工大学安全科学与应急管理学院;2. 西安交通大学管理学院;3. 中国科学院数学与系统科学研究院;4. 武汉理工大学管理学院 |
| |
| 基金项目： | 国家自然科学基金(批准号:72271194)资助项目； |
| |
| 摘 要： | 行旋转算法是求解线性不等式组的一种直接、有效的算法,为大数据时代众多与线性不等式组紧密相关的问题提供了统一、高效的解决思路.求解线性规划问题本质上是求解线性不等式组,因而行旋转算法可以作为基础算法直接应用于求解线性规划.不同于以单纯形法为代表的列旋转算法,线性规划的行旋转算法以行几何(或行向量)为基础,其核心思想是在保证最优性条件始终成立的前提下求解约束条件对应的线性不等式组.改进的行旋转算法保持了原算法的所有特色.该算法的改进之处在于利用约束条件变量的部分系数构成的非奇异矩阵的逆矩阵(称为特征逆矩阵)和原始数据计算出枢轴行和枢轴列,从而完成一次旋转运算.特征逆矩阵的阶数一般要比约束的数目和变量的数目小很多,在每次迭代过程中只需要计算原算法算表中的小部分必要元素,因而能够显著提高计算效率.
|
| 关 键 词： | 线性规划 改进行旋转算法 逆矩阵 分块行旋转运算 线性不等式组 |
|
|
