《管理运筹学》02-3线性规划的单纯形表

第二节单纯形法,SimplexMethod,一、单纯形法原理及步骤二、用向量矩阵描述单纯形法原理三、单纯形表四、两阶段法和大M法五、退化和循环,用向量矩阵描述单纯形法原理,并设是A的一个基。,设标准的线性规划问题为,则，相应地，向量X和C可以记为,BXB+NXN=b,XB=B-1b-B-1NXN,CBXB+CNXN,z=CBB-1b-(CBB-1N-CN)XN,用向量矩阵描述单纯形法原理,z=CBB-1b-(CBB-1N-CN)XN,XN=0,基础解,CBB-1N-CN=0：任意非基变量进基，目标函数值减少，当前解已经是最优解。,检验数！,变量xj的检验数：,用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路：,(1)取得初始可行基B、相应的基本可行解及对应的目标函数值,(2)从当前的非基变量中选取一个xk,使xk的值由当前的值0开始增加，其余非基变量的值均保持零值不变。如果任何一个非基变量的值由0增加时，目标函数都不能增加，则当前的基已经是最优基。,用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路：,(3)当xk的值由0开始增加时，当前各基变量的值也会随之变化：,1)当xk的值增加时，某些基变量的值随之减小，则必定有一个基变量xr的值在xk的增加过程中首先降为0。这时，这个基变量xr成为非基变量，而非基变量xk进基成为基变量，相应地，xk在矩阵A中相应（不在基B中）的列向量pk将取代基变量xr在基B中的列向量pr。此时基变换后的目标函数值必定大于原目标函数值。,用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路：,2)当xk的值增加时，所有基变量的值都随之增加，则不会有任何基变量出基，这时xk值的增加没有任何限制。此时可行域无界，即目标函数无界。,(4)重复步骤(2)和(3)，就一定可以获得最优基或确定目标函数无界。,用向量矩阵描述单纯形法原理,单纯形法的几何意义：,从几何意义方面解释，单纯形法就是在可行域的边界上，沿着相邻的极点进行搜索的一种算法。所谓相邻的极点，就是每次只有一个变量进基，一个变量出基转换前后所对应的基本可行解。我们把这两个基本可行解所对应的两个基称为“相邻的”基。,单纯形表,根据单纯形法的向量矩阵描述，可得：,系数矩阵,B-1,B-1,B-1,=E,CB,CB,CB,需要变成0！,单纯形表,与基B对应的单纯形表,目标函数值,基变量的目标函数系数,令,则检验数j可以记为,单纯形表,单纯形表,列出以x3、x4为基变量的单纯形表如下。,z2-c2=-30，最优！,X*=(2,1,0,0),Z*=7,旋转运算,Cj2300,单纯形表,例2,列出以x3、x4为基变量的单纯形表如下。,x2进基,X3离基,(1),Cj1200,单纯形表,(2),x1进基,X4离基,(3),x3进基,目标函数无界！,能确定进基变量，无法确定离基变量,Cj1200,单纯形表,例3,标准化（加入松弛变量x3、x4，z=-z）后，列出以x3、x4为基变量的单纯形表如下。,(1),x2进基,X3离基,Cj-2200,单纯形表,(2),x1进基,X4离基,最优解X1=(0,1,0,1)T，z=2,(3),最优解X2=(1,2,0,1)T，z=2,最优解X=tX1+(1-t)X2=(1-t,2-t,0,t)T，(0t1),Cj-2200,单纯形表,单纯形算法流程图,单纯形表,例4,列出以x3、x4为基变量的单纯形表如下。,x1进基,X4离基,(1),Cj10500,单纯形表,(2),x2进基,X3离基,(3),0，最优！,X*=(1,3/2,0,0),Z*=35/2,旋转运算,Cj10500,单纯形表,例5,引进松弛变量，标准化并初始单纯形表：,x2进基,X5离基,(1),Cj