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

高引民， 陈建斌

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

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

高引民， 陈建斌

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

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

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

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

1) 对线性规划约束条件的性质进行研究， 分析约束条件与约束条件的关系及约束条件与最优解的关系[2].

2) 对线性规划模型中变量的性质进行研究[3].

3) 以什么方式来识别线性规划模型中的约束条件及变量的性质[3].

4) 什么时间(建模的过程， 求解线性规划模型前还是求解线性规划模型过程中)来删除线性规划模型中的一些约束条件及一些变量, 使得线性规划模型简化.

文献[1]从线性规划对偶问题的角度出发， 对应用对偶性进行数据预处理的方法做了总结， 并研究了利用对偶性理论所产生的方法在预处理的效用， 尤其对大规模线性规划问题[1]. 线性规划的研究直接推动了其他数学规划问题包括整数规划、 随机规划和非线性规划的算法研究. 通过求解线性规划问题的基本解来逼近最优解是求解线性规划问题的方法体系中非常重要的一类方法， 称这一类方法为基点上迭代逼近最优解方法， 它包括线性规划问题单纯形法、 对偶单纯形法、 原始-对偶单纯形法， 松弛法， 以及将摄动算法和亏基原始单纯形算法相结合的方法， 该方法采用最陡边的列主元规则， 以充分发挥这两种算法的优势[4-11]. 同样识别非有效变量的理论及变量与约束条件的关系理论都是有价值的. 本文主要从理论方面深入地研究最优紧约束条件方面的有关问题并提供了一种新的单纯形法(DRSM). 数据试验和理论上表明， DRSM在求解大规模解线性规划问题时， 利用新的求解算法， 使得模型逐步降阶， 能达到求解的高效率.

1 线性规划降阶的基本理论

考虑如下线性规划问题(LP)

s.t.

记A=(aij)m×n,bT=(b1,b2,…,bm),cT=(c1,c2,…,cn),li(X)=∑aij·xj-bi, (i=1,2,…,m),D为LP的可行解域，D≠φ,hi={X|li(X)=0,X∈D},X*为LP最优解,Z*为LP的最优值. 取i0∈{1,2,…,m}, 在LP中删掉第i0约束条件， 构造线性规划问题(LP-i0)

(i=1,2,…,m,i≠i0).

2) 若D≠D-i0(反证法), 设

Z(X0)>Z*.

(4)

Z(X0)

(5)

式 (4)和式(5)矛盾. 证毕.

定理 2 给定i0∈{1,2,…,m}, 对于(LP)构造如下线性规划问题(LPi0)

(i=1,2,…,m,i≠i0).

证明 反证法， 若li0=∑ai0j·xj-bi0≤0为LP的最优紧约束条件， 则li0(X*)=0，

定义 2 称模型(6)中li0≤0为(1)的准最优紧约束条件.

则li0≤0 为LP的最优松约束条件.

同理可证明2)成立.

定理 3 说明在满足何条件下可从原线性规划模型中删掉li0=∑ai0j·xj-bi0≤0约束.

2 降阶的单纯形法(DRSM)

DRSM基本思想是， 以单纯形法原理求(LPi0)， 然后， 根据定理3来判定约束条件li0≤0的性质， 若li0≤0为最优松约束条件， 则在原模型中删掉li0≤0约束条件， 继续选准最优紧约束条件， 再求解.其特点有： 解的过程是降阶的(变量数减少， 约束矩阵的阶数降低)， 简便性， 在计算机上的易实现性， 高效性(解的稳定性增加， 用时节省).

具体步骤如下：

第一阶段(选定某个界面Dl， 先在此界面上求最优解)

1) 列出初始可行单纯形表.

2) 计算变量xj对应的检验数σj， σk=max(σj|j=1,2,…,n).

3) 若σk≤0， 则停止， 得最优解.

4) 若σk>0, 以xk为进基变量， 用SM的θ规则

确定换出基变量为xl.

由此， 选定的界面是Dl={X|X∈D,xl=0}， 下面在此界面上求最优解， 并判断变量xl是否为最优变量.

以akl为主元做旋转运算(连同目标函数)， 将xk与xl对换位置， 则得新的单纯形表.

5) 计算变量xj对应的检验数σj， σk=min(σj|j=1,2,…,n,j≠1).

6) 若σk≤0， 则转9).

7) 若σk>0， 以xk为进基变量， 用SM的θ规则

确定换出基变量为xl1, 以akl1为主元做旋转运算(连同目标函数)， 将xk与xl1对换位置， 则得新的单纯形表.

8)返回5)继续迭代运算.

第二阶段(判断Dl界面的特性)

9) 若σ1≤0， 则停止， 得LP的最优解. 否则， 可判定xl为最优基变量, 转下一步.

10) 若xl为基本变量(非松弛变量)， 返回4)， 以xl为进基变量,继续迭代运算.

11)若xl为松弛变量， 用SM的θ规则

确定换出基变量为xl2, 以al2l为主元做旋转运算(连同目标函数)， 则得新的单纯形表.

12) 在新的单纯形表中删除第l列及第l2行， n变为n-1, m变为m-1,使得原线性规划模型降阶， 返回2).

3 实例及数值实验分析

例 1 对线性规划问题

maxZ=2x1+3x2,

计算最优解X*=(2,3), 由定理1可判断原线性规划模型与

maxZ=2x1+3x2,

线性规划问题最优等价.

例 2 数值实验分析

为了验证DRSM算法的效率， 应用MATLAB语言开发了在Windows环境下运行的DRSM程序及单纯形法(SM) 程序， 在具有700MHz,PentiumⅢ处理器，RAM256Mb及WindowsXP的计算机平台上进行数据试验.

为简化起见， 线性规划模型为

maxZ=CX,

aij, ci都在区间[1 000, -1 000]内随机产生， bj=1.

数据试验的结果如表 1 所示.

表 1 DRSM与SM比较

将SM法和DRSM法对问题的计算时间绘成对比曲线图如图 1 所示.

图 1 SM与DRSM对问题的计算时间对比图Fig.1 Computing time contrast figure of SM and DRSM

表 1 及图 1 说明随着线性规划问题的规模增大， DRSM计算效率明显优于SM， 且具有以下优点：

1) 由于减少约束条件导致计算的迭代次数减少， 有利于计算结果精度增加；

2) 同样问题的求解时间减少；

3) 线性规划规模越大效果越好.

4 结束语

线性规划的基本理论表明： 在求解前或求解过程中能判断模型中哪些变量是最优基变量， 哪些约束条件为最优约束， 删掉多余的非最有约束和非最有基变量， 只要计算一个由这些最优约束和基变量构成的线性规划问题， 降阶后规划模型与原问题等价， 不会改变问题的最优性质. 以上述研究内容为基础， 本文提出并研究了一种求解线性规划新方法(逐步降阶的线性规划的算法DRSM). 该方法主要优点是每次迭代计算简单(都是初等运算)， 几何解释很直观便于人们掌握和理解， 迭代次数少， 逼近最优解的速度快， 计算量少等. 进一步需要研究的是， 可综合利用线性规划对偶理论、 单纯形法的逆的乘积、 稀疏矩阵技术和LU分解等改进技术推广到DRSM算法中.

[1]胡艳杰， 黄思明， Adren N， 等. 对偶性在线性规划预处理中的应用分析[J]. 中国管理科学， 2016， 24(12)： 117-126. Hu Yanjie, Huang Siming, Adren N, et al. Analysis of using duality f'or presolving in linear programming[J]. Chinese Journal of Management Science， 2016， 24(12)： 117-126. (in Chinese)

[2]高引民， 甘仞初， 吴立志. 线性规划非最优有效约束方程判别定理研究[J]. 太原理工大学学报， 2004， 35(3)： 371-373. Gao Yinmin， Gan Renchu， Wu Lizhi. The study of characteristics of ineffective constraints in linear programming[J]. Journal of Taiyuan University of Technology， 2004， 35(3)： 371-373. (in Chinese)

[3]高引民， 甘仞初. 线性规划问题非有效约束条件性质研究[J]. 系统工程与电子技术， 2005， 27(6)： 1041-1043. Gao Yinmin, Gan Renchu. Characteristics of ineffective constraints in linear programming[J]. Systems Engineering and Electronics， 2005， 27(6)： 1041-1043. (in Chinese)

[4]Gammth G， Koch T， Martin A， et al. Progress in pre solving for mixed integer programming[J]. Mathcmatical Programming Computation， 2015， 7(4)： 1-32.

[5]戴或虹， 刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报， 2014， 18(1)： 69-92. Dai Yuhong， Liu Xinwei. Advances in iinear and nonlinear programming[J]. Operations Research Tansactions， 2014， 18(1)： 69-92. (in Chinese)

[6]Pan P Q. A dual projective pivot algorithm for linear programming[J]. Computational Optimization and Applications， 2004， 29: 333-344.

[7]孙黎明. 一种求解线性规划的投影动态方法[J]. 南京师大学报(自然科学版)， 2015， 38(4)： 8-13. Sun Liming. A projective dynamic method for solving linear programming[J]. Journal of Nanjing Normal University (Natural Science Edition)， 2015， 38(4)： 8-13. (in Chinese)

[8]孟香惠， 施保昌. 线性规划单纯形法主元规则的几何分析[J]. 数学杂志， 2013， 33(2)： 373-380. Meng Xianghui， Shi Baochang. Geometry analysis of pivot rules in simplex method for linear programming[J]. J. of Math. (PRC)， 2013， 33(2)： 373-380. (in Chinese)

[9]潘平奇. 关于“线性规划界面算法的高效实现” [J]. 运筹学学报， 2015， 19(3)： 78-84. Pan Pingqi. On “An efficient implementation of the face algorithm for linear programming”[J]. Operations Research Tansactions， 2015， 19(3)： 78-84. (in Chinese)

[10]杨欢， 陶凤玲， 李若东， 等. “准最优基”程序实现与应用探讨[J]. 数学实践与认识， 2014， 44(10)： 219-227. Yang Huan， Tao Fengling， Li Ruodong， et al. Program realization of (quasi-optimal basis) and its application discussion[J]. Mathematics in Practice and Theory， 2014， 44(10)： 219-227. (in Chinese)

[11]敖特根. 单纯形法的产生与发展探析[J]. 西北大学学报(自然科学版)， 2012， 42(5)： 861-864. Ao Tegen. Analysis of the formation and development of the simplex method[J]. Journal of Northwest University (Natural Soienc;e Edition)， 2012， 42(5)： 861-864. (in Chinese)

A Simplex Method Base on Reducing the Constraint Conditions of Linear Programming

GAO Yin-min, CHEN Jian-bin

(College of Business， Beijing Union University, Beijing 100025， China)

Aiming to improve the theory of linear programming with respect to the constraint conditions, a new simple method in solving the large-scale problem ineffective variables was presented. Methods to study the property of optimal slack constraint conditions and optimal tight constraint conditions employing some mathematical tools in linear programming and linear algebra and so forth were used to do numerical tests. The characteristics of the optimal tight constraint conditions, the theorems of identifying optimal slack constraint conditions and a new simple method have been obtained from results. Numerical tests and theory illustrated that identifying and eliminating optimal slack constraint conditions can simplify its constraint conditions and improve the efficiency of solving the problem of linear programming in solving the large-scale problem.

linear programming; simplex method; constraint conditions; optimal tight constraint conditions

1673-3193(2017)04-0409-05

2016-12-24

国家自然科学基金资助项目(71572015)

高引民(1960-)， 男， 教授， 博士， 主要从事运筹学， 信息系统与企业信息化的研究.

O221.1

A

10.3969/j.issn.1673-3193.2017.04.003