线性规划的一个新算法

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