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

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

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

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

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

本文介绍一种新的线性规划多项式算法——Karmarkar算法,并演示了它的产生过程。然后,给出了一种Karmarkar的扩充算法,这种算法在不要求已知原问题的最优值的情况下同时产生原问题与其对偶问题的解。     

线性规划的Karmarkar方法

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

线性规划的Karmarkar方法(续)

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

线性规划Karmarkar方法的初始内点的求法

给出了线性规划Ｋａｒｍａｒｋａｒ算法的求初始内点的算法。     

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

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

线性规划的一个新的Mehrotra型预估-矫正算法

在线性规划的内点算法中,理论和实践之间存在着数值效果好的算法具有较差复杂性的矛盾.目前大多数内点算法软件的执行采用Mehrotra型预估-矫正算法.本文提出了求解线性规划问题的一个新的Mehrotra型预估-矫正算法,证明了该算法的迭代复杂性是O(槡n L),这是内点算法所具有的最好的复杂性结果.     

线性规划的一个新算法

§1 引 言 线性规划通常是用单纯形法求解,即沿约束多面体棱边探索以确定那个顶点为最优解。算法简明但迭代次数随维数比例增大,收敛时程为指数型。因而对大系数来说,就产生改进的Dantzig单形分解法。79年Kauиан把椭球体法应用于线性规划并证明其时程为多项式型、时复杂性为O(n~6L~2),其中n为维数、L为精度的位数。     

一个新的线性规划通用神经网络模型

指出了现有模型存在的局限性，为构造了一种新的神经网络模型用于求解一般线性规划问题，避免了现有网络模型的不足，该模型是线性规划的通用模型，具有全局渐近稳定性，能够惟一地收敛到问题的全局最优解，模拟计算表明了新模型的有效性。     

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

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

应用斜投影改进Karmarkar算法

本文改进了解线性规划问题的 Karmarkar 算法。根据一般的最速下降原理及有关广义逆矩阵的斜投影变换,得到一个新的搜索方向。这个方法不需要预先知道目标函数的最优值,且每步迭代的运算量为 O(n~2L),优于 Karmarkar算法每步迭代的运算量 O(n~2·~5L)。     

一个瓶颈问题的多项式算法

在生产安排中会遇到这样问题:确定满足约束条件x_1+…+x_n=m的正整向量X=(x_1,…,x_n),使目标函数y=min{c_jx_i)达到最大。罗宗俊曾给出这个问题的一个拟多项式算法,大约需要n(m-n)次运算。本文给出一个多项式算法,仅需要n·log_2n次运算。     

ABS算法在Karmarkar算法中的应用

应用ABS算法计算Karmarkar算法中的迭代方向 ,讨论了带有较多或较少约束的线性规划投影矩阵及方向失量的求解方法 ,从而在不同情形下降低了运算量及存储量     

关于Karmarkar算法的若干注记

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

求解线性规划的一个非内点算法

利用NCP函数和光滑化方法将线性规划的K-K-T条件化为一个光滑方程组,构造了一个非内点原-对偶路径跟踪算法,并分析了其全局及局部收敛性;同时通过计算标准线性规划考题,验证了它的可行性及有效性。     

最优化计算中解线性规划的一个算法

(一)引言 用可行方向法求解非线性规划问题时,需要求解如下形式的线性规划问题(A): minh0其中H(X)=(h1h2…hN)T. 根据上述问题的特殊性,本文目的在于建立一个具有节省内存单元且有较快收敛速度的算法,并附有FORTRAN标准程序. (二)算法的建立 利用线性规划的对偶性,问题(A)等价于如下问题(B):其中对于问题(B),列出如下单纯形表格 把表格中矩阵的1～n+1行及1～n+m+1列所形成的矩阵记为B,矩阵B的第m+1～m+n+1列是具有特殊形式的列向量。引入整数组L(p),p=1,…,m+n+1,对L(p)进行适当控制,可以把上面单纯形表格中右上角的(n+1)2个单元省…     

一个判定多项式整除的方法

证明了伽罗瓦理论中的一个定理及其推广的定理，给出了一个判定多项式整除的方法。     

一个生产计划问题及其多项式算法

生产计划是企业组织生产的依据，在企业的生产管理中起着至关重要的作用，本文从一家大型企业制定生产计划的实际原则出发，抽象出一个生产计划的排序模型，通过对模型最优解性质的讨论，本文给出求解该模型最优序列及相应的最优生产批量的一个多项式时间算法．     

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

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