| 引用本文: | 张卫民,汪裕武.未知最优值线性规划的修正 Karmarkar算法.[J].国防科技大学学报,1991,13(3):100-107.[点击复制] |
| Zhang Weimin,Wang Yuwu.A Modified Karmarkar Algorithm for Linear Programming with Unknow Optimal Objective Value[J].Journal of National University of Defense Technology,1991,13(3):100-107[点击复制] |
|
| |
|
|
| 本文已被：浏览 6655次 下载 5860次 |
| 未知最优值线性规划的修正 Karmarkar算法 |
| 张卫民, 汪裕武 |
|
(计算机系)
|
| 摘要: |
| 本文对未知最优值的 Karmarkar 型线性规划，得到了一种复杂性为 O(n3.5L)的修正 Karmarkar 算法；通过讨论加边矩阵和秩 1修正矩阵的LDLT分解，得到了一种计算 Q-斜投影的有效方法。最后，从理论上分析了算法的收敛性和复杂性。 |
| 关键词: 线性规划，修正Karmarkar 算法，LDLT分解 |
| DOI： |
| 投稿日期：1990-04-10 |
| 基金项目: |
|
| A Modified Karmarkar Algorithm for Linear Programming with Unknow Optimal Objective Value |
| Zhang Weimin, Wang Yuwu |
|
(Department of Computer Science)
|
| Abstract: |
| A variant of Karmarkar's modified algorithm is given for solving Karmarkar's standard linear programming with unknown optimal objective value. By using LDLT factorization of bordering matrix and modified matrix，an efficient method is given. Finally，convergence and complexity of the algorithm are given theoretically. |
| Keywords: linear programming,Karmarkar algorithm,LDLT factorization |
|
|
