第三章 纯真形法.ppt 104页

2020-04-07 皇冠体育app 阅读

  设B0是(SLP)的一个可行基,或许B0退步,或许在纯真形迭代时,由 θl决定的出基变量标号jl时l不唯一。 引进摄动后果的目标就是为了在纯真形迭代中能肯定唯一的l, 并能使原后果防止轮回。 为便利起见,无妨假定(SLP)的基变量标号交换为1,2,…,m的依次,即交换后的基变量为x1 ,x2,…,xm交换后的计划后果仍记为: (SLP) max f=cx s.t. Ax=b, x≥0 已知A的前m列构成基B0=(P1P2…Pm),在纯真形迭代时肯定不了唯一的l,或许B0是退步的可行基。 结构摄动后果: max f=cx s.t. Ax=b(ε), x≥0 个中b(ε)=b+ε1p1+ε2 p2 +…+ εn pn =b+ 则 设 的第i重量为 是m维列向量,第i重量为 则: 因 下面证实,正数ε足够小时 , ,这标明B0是摄动后果非退步可行基。 或写成 因 ,则 又当ε>0足够小时,总可使 若 则任ε>0都可,若 <0则 (当 时 ) 因而有x i(ε)>0,(i=1~m),即 所以当正数ε足够小时,B。是摄动后果的非退步可行基。下面进一步证实当ε>0足够小时,摄动后果长短退步的。 定理6 对摄动后果 max f=cx s.t. Ax=b(ε),x>0, 存在ε0>0, 使得对任何满足 0<ε<ε0, 此摄动后果长短退步的。 此式摆布两头都是m维列向量共有m个重量,每个重量都表现一个方程,所所以m个方程的方程组。第i方程为: 则 化为: 证实:设B是摄动后果的一个基,设 对这m个方程求根,每个方程最多有n个实根。 对每个基B,有m个如许的多项式方程,而在A中可以取作基矩阵的数量也是有限的,设为P个,因而多项式方程总个数为mp个。 个中J为非基变量下标集合。令xj=0(j∈J)得基变量取值为 下面证实:存在ε0 >0,对任意ε:0<ε<ε0 ,(*)给出的基变量取值不为0。 因(*)式右端是系数不全为0的ε的n次多项式,令其为0 使一切这些多项式中任一个为等于0的ε的个数最多nmp 个,从而这些根ε中取正值的也只要有限个。 取一个ε0 >0,使ε0比一切这些正根ε还要小。则当ε:0<ε< ε0时,形如(*)的方程右端任何一个均不会取零值。即标明: 存在ε0>0,任意ε:0<ε<ε0,摄动后果任何一个基变量不能够为0。因为多项式是ε的延续函数,而区间 (0, ε0 )又没有这些多项式的根, 故每多项式在(0,ε0 )内或许恒大年夜于零,或许恒小于零,二者必居其一。 假设某一多项式在(0, ε0 )内恒大年夜于零,则关于任意的ε,0<ε<ε0 ,由(*)肯定的对应此多项式的基变量也 恒大年夜于零。 假设某基B的m个基变均取正值,那么当ε∈ ( 0 , ε0 )时,B就是摄动后果的非退步可行基。 而摄动后果非退步可行基是存在的。(前面的叙说,对B0基)。 现在要证摄动后果在(0,ε0 )内长短退步的,即只须证摄动后果的任一可行基B长短退步的。 因在(0, ε0 )内,摄动后果的基变量取值非零。 若B是摄动后果的可行基,则基变量取值非负。 故知基变量取值为正值。 即若B是摄动后果的可行基,则B必然是摄动后果的非退步可行基。 定理7:当ε>0足够小, (1)若 是摄动后果的基可行解,令ε=0,则 是原后果的一个基可行解。 (2)若x*(ε)是摄动后果的基本最优解。则x*(0)也是原后果的基本最优解。 证实:(1)设X0(ε)是摄动后果的一个基可行解,对应基B。并设 的重量为 (i=1~m),由(*)式知X0(ε)的基变量取值为: 上式中令ε=0,则X0(0)的基变量取值 ,(i=1~m) 因此,

标签: