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

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

彭猛[1]2002年在《线性规划逐维选优强多项式解法》文中进行了进一步梳理随着现代科学技术的迅猛发展,最优化理论得到了越来越广泛的应用,同时对其理论发展也提出了新的要求。 最优化学科的基础是线性规划。然而,实际计算和理论分析表明,当决策变量数目猛烈增大时,目前广泛使用的线性规划的各种迭代算法都存在严重缺陷。因此,进一步改进和完善线性规划的算法,努力降低计算的时间复杂度和提高对最优解集的完整描述,具有十分重要的理论意义和实践意义。 通过对低维空间线性规划问题进行分析及研究,我们提取出其中具有普遍性的规律,并将其向高维空间进行推广,研究出了一种新的算法——逐维选优直接算法,以强多项式时间复杂度求出线性规划问题的结构清晰的全部最优解的集合为目的。 此解法以逐次投影为手段,首先将线性代数方程组Ax=b进行法向消元,然后将各个坐标超平面的法向量向其投影,并按其空间几何位置建立序结构,通过逐维选优求出线性规划问题的最优解集,其算法为时间复杂度低于0(mn~3)的强多项式算法。 线性规划逐维选优强多项式解法已经形成一套完整的理论和成熟的算法,我在其中做的工作主要是: 1.从线性规划实际工程应用的角度出发,提出线性规划的理论研究和算法设计需要注重关心最优化问题的最优解集而不只是问题的一个最优解; 2.线性规划逐维选优强多项式解法刚开始形成时,判定原始等式约束平面与若干坐标超平面的交不可行是一直投影到零维平面即一个点,我从二维平面的特例情况出发提出只要在每降一维时考查那些投影向量是零的坐标基向量对应的坐标超平面即可; 3.提出和实现了计算有关参数以用最优解集平面的切向基的线性组合明显表示最优解集各点; 中南大学硕士学位论文 线性规划迈维选优强多项式解法2 4.设计了线性规划逐维选优强多项式算法程序流程图和主要模块的程序代码,编制了线性规划逐维选优强多项式算法程序并以此计算了若干实例。

蒋宏锋[2]2002年在《运输问题的直接算法》文中提出运输问题是一类常见而又极其典型的线性规划问题. 本文基于标准线性规划逐维选优强多项式算法的基本理论,结合运输问题模型的特殊结构,提出了运输问题直接算法的基本定理和直接算法的一般步骤.该算法根据目标函数的梯度向量在可行域的低维界面上的投影,通过确定运输问题在可行域上的低维等值界面,直接得出运输问题的最优解集. 全文共有五章:第一章是绪论,简单介绍了线性规划与运输问题的起源、发展,运输问题的传统理论及算法,算法复杂性分析等;第二章介绍了线性规划强多项式直接算法的基本理论.第叁章主要是给出了运输问题直接算法的基本定理和算法复杂性分析;第四章为运输问题的直接算法的算例,通过几个简单实例说明了该算法的计算过程:第五章结束语. 本人的所做的研究主要在第叁章和第四章,它包括以下几个方面: (1)利用投影矩阵简化了逐维选强多项式算法理论的表达. (2)提出了运输问题直接算法的基本理论. (3)给出了运输问题直接算法的一般步骤,进行了算法时间复杂性分析. (4)对几个规模较小的运输问题,利用运输问题直接算法进行实际计算. 对比求解运输问题最常用的表上作业法,该方法具有几何意义明确、计算过程操作方便、且求解效率高等特点.理论分析和大量的计算实例说明了直接算法是一种有效算法. 从现有文献资料表明,运输问题的直接算法是首次提出:对比运输问题的主要解法——表上作业法,该算法求解效率更高,因而该算法具有十分重要的理论意义和实际意义.

参考文献:

[1]. 线性规划逐维选优强多项式解法[D]. 彭猛. 中南大学. 2002

[2]. 运输问题的直接算法[D]. 蒋宏锋. 中南大学. 2002

标签:;  ;  ;  

线性规划逐维选优强多项式解法
下载Doc文档

猜你喜欢