线性规划的Karmarkar方法

线性规划的多项式算法——Karmarkar方法，是近期国际运筹学界的名成果．它在理论与实用上都有重要意义．本希望用比较通俗的方式介绍它，以便让更多的人们了解这一方法并将它应用于实际，产生更多的经济效益．     

线性规划的Karmarkar方法(续)

线性规划的多项式算法——Karmarkar方法，是近期国际运筹学界的著名成果，它在理论与实用上都有重要意义，本文希望用比较通俗的方式介绍它，以便让更多的人们了解这一方法并将它应用于实际，产生更多的经济效益。     

一类线性规划问题的强多项式算法

对一类线性规划问题提出了一个强多项式算法．此算法可进行双向搜索．可行解集、目标函数的两个目标值以及相应的最优解，全部可行基与最优基可以一步求得，无需迭代．算法的复杂性为Ｏ（ｎ３＋ｎ２＋ｎ），其中ｎ为线性规划问题变量的个数     

几何规划的一种多项式时间算法

利用几何规划的特点，借助于对偶理论，把原始对偶道路跟踪内点算法，推广应用于正定式几何规划并证明了此算法对于无约束正定式几何规划是一种多项式间算法，可以预料，这种算法可推广应用于约束几何规划问题。     

求解线性规划问题的一种新方法

本文介绍一种求解线性规划问题的新方法,该方法的特点是初始基不必是可行基。     

线性规划的一个新的多项式算法——Karmarkar方法

本文详细介绍了Karmarkar算法,并论述了算法的适应性。对Karmarkar文章中个别说得不够清楚的地方,本文已进行了补充和修正。     

线性规划的一个新的多项式算法——Karmarkar方法

假设我们已经知道: (Ⅰ)问题有最优解,且最小值为零 (Ⅱ)x=a,y=g是问题的一个可行解,且满足a>0,g>0定义: 作1,2节中的投影变换: 问题就可化为如下的Karmarkar标准型:求满足是问题的一个可行解。现在,让我们考虑形式稍广些的问题     

线性规划的一种算法

本文给出一种用解变量个数较少的线性规划来求解变量太多的线性规划的方法。     

一种新的非线性最小费用网络流算法

为求解非线性可分凸费用网络流问题,提出了一种原始对偶算法,并证明了算法的收敛性。该算法可从任意满足节点流量平衡条件但不一定可行的初始解处开始计算,且能方便地处理目标函数的一阶导数有第一类间断点凸规划问题。用７５０节点和５０１０条弧的网络对本算法作了测试,计算结果说明算法有较高的效率。本算法已被用于实际电网水火联合经济调度问题中,实践证明算法是正确和有效的。     

一类线性规划问题的强多基式算法

对一类线性规划问题提出了一个强多项算法，此算法可进行双向搜索，可行解集，目标函数的两个目标值以有相就的最优解，全部可行基与最优基可以一步求得，无需迭代，算法的复杂性为Ｏ（ｎ＾２＋ｎ＾２＋ｎ），其中ｎ为线性规划问题变量的个数。     

一种新的线性规划不可行内点算法

提出了一个新的求解线性规划问题的不可行内点算法,这个算法每一步只须解一个线性方程组,算法是基于路径跟踪算法思想,适当选取初始点,算法至多可在Ｏ（ｎｌ）迭代步获得ε－可行性和ε－互补性,算法具有每一步的计算量少的特点。     

法向消元和线性规划强多项式算法

为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法.     

递增斜率分段线性规划的对偶算法

针对目标函数具有递增斜率的分段线性规划问题,提出了一种快速的对偶算法。算法基于单纯形的思想,引入指针的概念来建立问题最优性和可行性判据,不需设置分段变量,不会扩大问题的规模,从而减少了内存和计算量。     

关于Karmarkar算法的若干注记

对于线性规划的 Karmarkar-Todd-Burrell-Gay 算法[2],本文重新证明了它的收敛性,此外,我们还提出了一种计算初值的实用途径,并对步长的一维搜索方法进行了初步的分析。最后,我们用几种典型例题检验了该算法的实际效果。     

线性规划的一种线性算法

引入投影坐标表达约束平面的法向量间的特殊线性关系，以此投影坐标表出线性规划解的最优性和可行性条件，导出一种线性迭代算法，其特点是：（１）首先面向最优性；（２）无需处理非负性；（３）解的过程是降维的。     

求解线性规划问题的一种算法

本文给出了求解线性规划问题的一种算法,该算法在用初等行变换求约束条件的基本可行解时,通过控制目标函数的检验数使基本可行解靠近最优解,减少了迭代次数,从而减少计算量,并可以在计算机上实现.     

一种大规模线性规划问题的递阶算法

导出了一种新的求解大规模一规划问题的递阶算法。它的协调级为用迭代法求解低阶线性代数方程组，和一级仅需求一系列低维线性规划，且充分利用了上次迭代的结果，大大提高了运算效率，比较详细地研究了此算法的收敛性，所得结果对问题的分解有明确的指导意义，最后，运用该算法求解某水利工程项目中的大规模线性规划问题。结果表明，本法收敛速度快，求同维问题时明显优于通常的修正单纯形法。     

Kar markar算法与分式线性规划

本文将求解线性规划的Ｋａｒｍａｒｋａｒ算法推广至分式线性规划；给出了两种求解分式线 性规划的算法，其计算步数的界均为Ｏ（），其中Ｌ是问题数据的输入长度，ｎ为问 题的变量数目；改进了 Ｋｈａｃｈｉｙａｎ １９８０年所得的结果。     

线性规划的一个新的多项式算法——Karmarkar方法(续)

四、基本定理的证明为了需要,先证明下面有关对数函数的三个分析性质。性质11 若y_j≥0(j=1,2,…,n),则有证明所有性质证明利用中值定理,可得：性质13证明因此有取,应有性质12,可得：因为故有下面开始证明基本定理。     

一种新的对偶原始算法的有效实现

为了规避求解线性规划问题时存在的一系列不足(如受原始退化影响、迭代次数随规模大幅增长、占用中央处理器时间长等),提出了一种处理一般线性规划问题的新对偶原始算法(NDPA),即采用求解一系列无约束最小二乘问题获得残差,确定搜索方向,而不是通过经典非线性优化算法来处理约束最小二乘问题.通过随机生成的线性规划问题试验,初步证...