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

第二节 单纯形法 Simplex Method 一、单纯形法原理及步骤 二、用向量矩阵描述单纯形法原理 三、单纯形表 四、两阶段法和大M法 五、退化和循环 用向量矩阵描述单纯形法原理 并设 是A的一个基。 设标准的线性规划问题为 则 ，相应地，向量X 和C 可以记为 max z = CX AX=b X≥0 s.t. 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=-3< z1-c1=-2 ，x2为进基变量 最小比值 法！ 最小检验数规则！ [ ] X4离基 (1) 旋转运算 例1 Cj? 2 3 0 0 单纯形表 (2) x1进基 [ ] X3离基 (3) >0，最优！ X*=(2,1,0,0), Z*=7 旋转运算 Cj? 2 3 0 0 单纯形表 例2 列出以x3、x4为基变量的单纯形表如下。 x2进基 [ ] X3离基 (1) Cj? 1 2 0 0 单纯形表 (2) x1进基 [ ] X4离基 (3) x3进基 目标函数无界！ 能确定进基变量，无法确定离基变量 Cj? 1 2 0 0 单纯形表 例3 标准化（加入松弛变量x3、x4，z’=-z）后，列出以x3、x4为基变量的单纯形表如下。 (1) x2进基 [ ] X3离基 Cj? -2 2 0 0 单纯形表 (2) x1进基 [ ] X4离基 最优解X1=(0,1,0,1)T，z’=2 (3) 最优解X2=(1,2,0,1)T，z’=2 最优解X=t X1+(1-t) X2=(1-t,2-t,0,t)T，(0≤t≤1) Cj?