SLI的条件冗余性及LP问题的算法研究

摘要

自从前苏联数学家Konterovitch和美国学者Koopmans先后提出LP问题及其数学模型以来，1947年，美国学者G.B.Dantzig（丹捷格）提出单纯形法被认为是线性规划理论研究的一次重大突破，该算法的出现为线性规划开辟了无限广阔的应用空间与前景。迄今，线性规划研究已取得巨大而辉煌的成就，在LP算法研究方面更是硕果累累。目前，LP算法构成了三大主流派系，它们是，以美国学者G.B.Dantzig所提出的单纯形法为代表的主元算法体系、以前苏联学者Khachiyan L.G.所提出的椭球法为代表的割区域算法体系和以美国学者N.Karmarkar所提出的Karmarkar投影法为代表的内点迭代算法体系，其中，当属内点法派系的研究成果最为丰硕。
　　实际上，线性规划同时具备两个最显著特性——线性及几何平面特性，当前，三大算法体系均未能综合利用好这两大特性。单纯形法类方法均属非多项式时间算法，主要针对线性特性而提出，没能体现及利用好几何平面这一特性，它们的迭代运算极易受基退化现象的干扰与影响;椭球法类方法和内点法类方法尽管理论上是多项式时间算法，但均属非线性类方法，而且都是从非线性规划算法移植而来，更无法体现及利用好几何平面这一特性，它们的非线性化处理方式导致了迭代计算十分繁杂，严重影响了搜索效率，在实际应用中，搜索效果甚至还比不上单纯形方法！
　　本文针对当前LP算法的研究现状，充分考虑到线性规划的两而性特点，运用解析几何、线性空间理论、线性流形理论、线性规划的灵敏度分析理论及凸规划理论等，提出了有别于当前三大算法体系的LP问题新求解方案——基点定向转移搜索方案与消冗降阶方案，并围绕这两大新求解方案，重点探讨了如下几个方面的问题——条件约束冗余性问题，SLI的定解问题，l-正流形锥的可分离性问题，可行域代数、几何刻画问题以及退化基点的非退化转移问题。在此基础上，提出了多种LP问题的新求解方法及SLI的新定解方法。
　　本文研究成果主要表现在如下几个方面:
　　1.构建了单纯形基点的转移模型——基点转移矩阵及其运算法则，为算法研究解决了运算平台这一关键性问题，以此提出了一种LP问题的新求解方案——基点定向转移搜索方案，将LP问题的求解过程变成了矩阵的初等列变换过程，并提出了包括VSEDT迭代法在内的几种LP问题的基点定向转移搜索算法;
　　2.为充分利用非退化基点的优良转移性能、彻底消除退化现象对基点迭代转移的不利影响，提出了单纯形平移扩张原理及局部正则化方法，确保基点迭代转移始终在非退化状况下进行，不仅解决了退化基点的可转移性问题，也较好地解决了单纯形算法中存在的基循环难题;
　　3.基于条件约束冗余的几何特征，对其进行了代数刻画与描述，将条件约束几何冗余性判别问题变为SLI的定解问题，并将之应用到LP问题的解算研究中，提出了消冗降阶原理及LP问题的新求解方案——消冗降阶方案，进而提出了逐次消冗降阶算法及非负约束降阶预估—校正算法等LP新求解方法;
　　4.针对SLI的定解问题，在引进l-正流形锥这一特殊代数结构及提出l-正流形锥可分离性等数学概念的基础上，对l-正流形锥的可分离性机理进行了较深入探讨，以l-正流形锥可分离性公理假设为基础，给出了关于l-正流形锥可分离性的一系列等价及判别定理，并提出了矩阵求逆的SLI新定解方法，为解决SLI定解问题找到了一条有效的新途径。

目录

声明

摘要

第1章 绪论

1．1 研究背景与选题意义

1．1．1 SLI条件多余性研究背景及意义

1．1．2 LP问题算法的研究背景及意义

1．2 当前主要LP问题算法综述

1．2．1 单纯形法概述

1．2．2 椭圆法概述

1．2．3 Karmarkar投影法概述

1．2．4 亏基单纯形法与基线算法概述

1．2．5 本节小结

1．3 本论文的主要研究内容

上篇 平移扩张原理与LP问题的基点定向转移搜索算法

研究背景与任务

1 当前LP问题算法的功能状况

2 摄动原理及摄动单纯形法

3 主要任务

第2章 有关LP问题的基础性研究与探讨

前言

2．1 几个空间概念及相关性质

2．2 单纯形的相关描述

2．3 本章小结

第3章 平移扩张原理与单纯形的局部正则化

前言

3．1 单纯形基点的一种点向式转移模型

3．2 平移扩张原理

3．3 非正则单纯形的局部正则化

3．4 章节小结

第4章 一种求解LP问题的VSEDT迭代算法

前言

4．1 构建LP问题的新算法平台—基点定向转移矩阵及其运算

4．2 小量正参数ε-正则化

4．3 最优性判别定理

4．4 VSEDT迭代算法介绍

4．5 实例分析

4．6 VSEDT迭代法的改进—优势控制群迭代算法

4．7 章节小结

第5章 一种求解LP问题的强迫性VSEDT迭代算法

前言

5．1 构建LP问题新算法平台—强迫性基点定向转移矩阵

5．2 几个最优性判别定理

5．3 强迫性VSEDT迭代算法介绍

5．4 实例分析

5．5 强迫性VSEDT迭代法的改进方法—割区域搜索算法

5．6 强迫性VSEDT迭代算法的改进措施

5．7 章节小结

篇后语

下篇 LP问题的消冗降阶算法与SLI的条件冗余性

研究背景与任务

1 当前LP算法研究的实际状况

2 研究目标与任务

第6章 消冗降阶原理及其应用与展望

前言

6．1 消冗、降阶定理及相关概念

6．2 逐次消冗降阶法

6．3 非负约束降阶预估—校正算法

6．4 影响原理应用的障碍及其展望

6．5 章节小结

第7章 一种SLI的矩阵变换定解方法

前言

7．1 一个新的SLI定解平台及其性质

7．2 线性不等式组的矩阵列变换定解方法

7．3 实例展示

7．4 章节小结

第8章 e-正流形锥及其可分离性研究与应用

前言

8．1 e-正流形锥及可分离性定义及相关性质

8．2 e-正流形锥的可分离性公理及相关判别定理

8．3 e-正流形锥的可分离性在SLI定解问题中的应用

8．4 e-正流形锥分离性判法改进

8．5 本章小结

篇后语

结论

1．主要结论

2．后续工作的展望

寄语

致谢

参考文献

攻读博士学位期间发表的论文及科研情况