基于逐步降阶的线性规划的单纯形算法

高引民， 陈建斌

(北京联合大学 商务学院， 北京 100025)

基于逐步降阶的线性规划的单纯形算法

高引民， 陈建斌

(北京联合大学 商务学院， 北京 100025)

为完善线性规划约束条件方面的基本理论， 研究了一种高效的求解线性规划问题的算法. 以区分最优松约束条件和最优紧约束条件为主线， 利用线性规划， 线性代数等数学理论， 进行分析， 并通过大量的数据实验进行验证. 从理论上获得了最优紧约束条件一些性质及识别最优松约束条件的定理， 提供了一种新的单纯形算法. 数据试验和理论上表明， 在求解大规模解线性规划问题时， 利用新的求解算法， 使得模型逐步降阶， 能达到求解的高效率.

线性规划； 单纯形算法； 约束条件； 最优紧约束条件

近年来， 信息科学技术的发展、 互联网的广泛应用， 推动了经济全球化的进程. 企业信息化改变了企业管理的模式. 对企业经营资源进行优化, 需要借助运筹学、 大数据技术等方法来解决企业的生产经营的各类优化问题,有大量具体应用的实际问题需要利用线性规划模型来解决. 实际问题的复杂性导致线性规划问题的规模不断增大， 而计算求解线性规划问题过程中的工作量和复杂度都与线性规划问题的规模大小有关， 尤其对大规模线性规划问题. 缩小原模型的规模,降低原模形的复杂性,有利于线性规划的求解[1，4]. 要达到这样的目的,在线性规划的理论和算法方面应解决以下几个问题.

1) 对……