线性规划逐维选优强多项式解法

摘要

随着现代科学技术的迅猛发展，最优化理论得到了越来越广泛的应用，同时对其理论发展也提出了新的要求。最优化学科的基础是线性规划。然而，实际计算和理论分析表明，当决策变量数目猛烈增大时，目前广泛使用的线性规划的各种迭代算法都存在严重缺陷。因此，进一步改进和完善线性规划的算法，努力降低计算的时间复杂度和提高对最优解集的完整描述，具有十分重要的理论意义和实践意义。 文中通过对低维空间线性规划问题进行分析及研究，提取出其中具有普遍性的规律，并将其向高维空间进行推广，研究出了一种新的算法——逐维选优直接算法，以强多项式时间复杂度求出线性规划问题的结构清晰的全部最优解的集合为目的。此解法以逐次投影为手段，首先将线性代数方程组Ax=b进行法向消元，然后将各个坐标超平面的法向量向其投影，并按其空间几何位置建立序结构，通过逐维选优求出线性规划问题的最优解集，其算法为时间复杂度低于0(mn~3)的强多项式算法。

目录

第一章 关于最优化传统理论的回顾与总结

第二章 新算法的设想

第三章 新理论的构成

第四章 逐维选优算法的时间复杂度

第五章 逐维选优算法计算程序

第六章 计算样例

致谢

参考文献