文档介绍：单纯形算法的复杂性 0 1 2 2 max 10 . . 2 10 10 , 2, , 0, 1, 2, , n n i i i i j i i j j i i x x s t x x i n x i n ??? ???? ??? ?????单纯形算法需要2 n-1次迭代。 2 2 ( ) 6 2 3 log | |, d I n n n P P ? ???二进制输入大小其中为所有非零系数的乘积。 0 1 1 max . . 2 , 2, , 0, 1, 2, , n i i i i j j i i x x s t x x a i n x i n ????? ??? ?????定理:当a>2时,用单纯形算法求解上述问题时需要 2 n-1次迭代。 1 1 0( 1, , 1), n i n n x i n x a a ??? ? ????最优解为: 最优值。椭球法第一个可以在多項式时间內解决一般线性规划问题的解法。min ( ) . . 0 cx P s t Ax b x ??????? max ( ) . . 0 T T b w D s t A w c w ???????根据(P)与(D)的对偶关系, 我们可将两者的最优解以一组最优性条件联结起来: , 0 , 0 (*) 0 T Ax b x A w c w cx wb ? ???? ???? ?? LP Ax b ?定理:存在求解问题的多项式时间算法的充要条件是存在求解线性不等式组的多项式时间算法。?????? min * . . 0 , , , , 0, 0 Ax b LP cx s t Ax b x x x A A A b b x x c c x ?? ??????????? ?? ??????? ?? ?? ?证明:与线性不等式组相关的问题为其中任取如??* LP Ax b Ax b Ax b ???若有多项式时间的算法,能够判断问题不可行,则不等式组无解;或者得到其最优解或判定问题无界,则得到不等式组的一个解,显然就以多项式时间解决了问题。 LP Ax b ?定理:存在求解问题的多项式时间算法的充要条件是存在求解线性不等式组的多项式时间算法。???? max * . . 0 , , , 0, , 0 wb s t wA c w LP x w Ax b wA c cx wb x w ???????? ????的对偶问题为所以求解问题可归结为求解关于变量的线性不等式组: ??*, * * * , 0 x w x LP w Ax b x LP LP ? ?设有多项式时间方法求解线性不等式组。若该联立不等式组有解,则是问题的最优解, 是其对偶问题的最优解;若该联立不等式组无解,考虑不等式组若它有解,则问题无界;否则问题不可行。只要能有效的解决最优性条件的线性不等式, 就能夠同时的解决一个线性规划问题(P)以及它的对偶问题(D)。椭球法正是一种专门解决线性不等式的方法。介绍如何以椭球法來解一组线性不等式Mu≤v Mu≤v的解集合是一个凸集: { | } S u Mu v ? ?假设S≠?, 以原点u 1为圆心, 足夠大的半径做一圆E 1, 使得S∩E 1≠?。 1 1 Mu v u ?若,则为所求的解。否则, 因为S∩E 1是一个凸集, 所以经过圆心, 可以切掉不含S∩E 1的半个圆, 而只剩下包含 S∩E 1的半个圆(以1/2E 1表示)。对1/2E 1而言,可以做出一个最小的椭圆E 2, 使得1/2E 1?E 2,椭圆的圆心记u 2。 S∩E 1?E 2, 若Mu 2≤v成立, 则u 2∈S∩E 1必为其解。否则经过u 2又可切去半个E 2, 而使S∩E 1包含在另一半椭圆1/2E 2之中。在p维空间中, 每次做出的椭球体积都会逐渐缩小。以V(E k)及V(E k+1)来表示前后两个椭球的体积, 那么可以证明V(