-
题名线性规划的非可行的内点算法
- 1
-
-
作者
国涓
-
机构
东北财经大学数量经济系
-
出处
《沈阳航空工业学院学报》
2007年第2期85-89,共5页
-
文摘
首先简要介绍非可行的内点算法,然后提出一种新的中心路径的取法,并由此给出一个对Kojima-Megiddo-Mizuno算法的改进的方法,这一新的算法是具有O(n2L)次收敛性的算法,并对这一算法的收敛性加以证明,这一新的算法与其它算法最明显的差异是不必假设LP解的存在性,就可以证明原始—对偶问题的多项式时间收敛性。文章的最后通过数值实验将该算法与Ye的解决线性规划的中心路径算法进行了比较。比较的结果显示新的算法从各个方面都要优于Ye的算法。
-
关键词
原始-对偶规划
非可行内点算法
中心路径
-
Keywords
primal - dual programming
infeasible interior - point algorithm
central - path
-
分类号
O221.1
[理学—运筹学与控制论]
-
-
题名基于设施选址问题的费用分配问题的近似算法
被引量：5
- 2
-
-
作者
王继强
李国君
-
机构
山东大学数学与系统科学学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2006年第13期13-14,32,共3页
-
基金
国家自然科学基金资助项目(编号:60373025
10271065)
-
文摘
许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。
-
关键词
设施选址
费用分配
近似算法
原始与对偶规划
-
Keywords
facility location,cost allocation,approximation algorithm,primal and dual program
-
分类号
O224
[理学—运筹学与控制论]
TP301.6
[理学—数学]
-
