内点法_954801291.pdf

单纯形算法的复杂性 n ni max x0 10 xi i 1 i j 2i2 st.. x  2 10 x 10 ,i 2,,n i  j j i x  0, i 1,2,,ni 2 二进制输入大小d(I) 6n  2n3nlog |P|, 2 其中P为所有非零系数的乘积。 n 单纯形算法需要2 -1次迭代。 n max x0 xi i 1 i1 st.. x  2 x  a ,i 2,,n i  j j i x  0, i 1,2,,ni 定理：当a2时，用单纯形算法求解上述问题时需要 n 2 -1次迭代。 最优解为：x 0(i 1,,n1),x an1 i n n1 最优值 a 。 椭球法 第一个可以在多項式时间內解决一般线性规划问 题的解法。  T min cx maxb w   T (P) st.. Ax b (D) st.. A wc  x  0  w 0   根据(P) 与(D) 的对偶关系, 我们可将两者的最优解以 一组最优性条件联结起来: Ax b, x  0  T A w c, w  0 (*) cxwb 0  定理：存在求解LP问题的多项式时间算法的充要条件 是存在求解线性不等式组Ax b的多项式时间算法。 证明：与线性不等式组Ax b相关的LP问题为 min cx  * st.. Ax b     x  0  x 