文档介绍：§3 单纯形法(Simplex Method)例子:例子:求解线性规划问题LP规划问题的最优解,可以从基可行解中找到?图解法有局限性;?枚举法计算量大;§ 单纯形法的引入??????????????0,+2x2 =84x1=164x2=12解:首先:将该问题化成标准形?????????????????????5,,2,1,012416482..00032max524132154321?jxxxxxxxxtsxxxxxzj第二:找初始可行解(即一个顶点)。系数矩阵A=(p1 p2 p3 p4 p5) ??0,0,0,3,2,12168,?????????????????????????????CbAXbAXtsCXz矩阵形式因为p3 ,p4,p5 线性独立,故B=( p3 , p4, p5)构成一个基底,对应的基变量x3,x4,x5解出来为(用非基变量表示基变量)x3 =8- x1-2x2 x4 =16-4x1 (a) x5 =12- 4x2将(1)代入目标函数中得z=0+2x1+3x2令非基底变量x1=x2=0,则有z=0。这时得到一个基可行解X(0) =(0,0,8,16,12) T ---原点第三:判别从目标函数中得知,非基底变量的系数为正,因此,将非基变量换入基底后可使目标函数增大,转入第四步第四:换基底(旋转迭代)确定换入变量:由于z=0+2x1+3x2中非基底变量x2系数贡献最大3,故换入基底为x2。换入变量已定,必须从x3,x4,x5换出一个,并且要保证其余均是非负的,即x3,x4,x5?0。x3 =8- 2x2?0 x4 =16 ?0 x5 =12- 4 x2 ?0由此,只要选择x2 =min (8/2,-,12/4)=3,对应基底变量x5 =0,从而确定用x2和x5对调,即将x5换出。有x3=2- x1+1/2x5 x4 =16-4x1 (b) x2 =3- 1/4 x5将(b)代入目标函数中得z=9+2x1-3/4x5令非基变量为零,又得到另一个基可行解X(1) =(0,3,2,16,0) T–顶点Q4返回第三步:非基变量x1的系数是正的,还可增大,X (1)不是最优解。重复上述步骤。由于x1的系数是正的,从而x1为转入变量,再由x3 =2- x1?0 x4 =16- 4 x1?0 x2 =3 ?0只要选x1=min{2,16/4,-}=2上式就成立,因为x1= 2时,基变量x3=0,从而由x1换出x3,得x1 =2- x3 +1/2x5 4x1 +x4 =16 (c) x2 =3- 1/4 x5高斯消去法(行变换)得 x1 =2- x3 +1/2x5 x4 =8-2 x5 +4 x3 x2 =3- 1/4 x5代入目标函数中,得z=13-2 x3 +1/4x5令非基变量x3= x5=0,又得到另一个基可行解X(2) X(2) =(2,3,0,8,0) T–新顶点Q3同理,返回第三步,再迭代,x5作为转入变量x1 =2+1/2x5?0