运筹学A-第1章线性规划教材教学课件.ppt

(六)判优(检验) 将式(4)代入目标函数，目的：用非基变量表示目标函数，得到新的目标函数值： Z(1) = 2x1 + 5x2 = 2x1 + 5(3 – x4) = 2x1 – 5x4 + 15 非基变量x1的系数为2，大于零，可见，如果x1 能从非基变量变为基变量，即变为正数，则目标函数值会增加，因此X(1) = (0, 3, 4, 0, 2)T 不是最优解。 Z(1) = 2x1 – 5x4 + 15 (七)换基 当x1 = 2时，x5 = 0 即：当x1 入基，x5 出基。 (八)求新的基可行解 此时，基变量为x3、x2和x1，非基变量为x4和x5。 用非基变量表示基变量： x1 = 2 + 2x4 – x5 ，  x3 = 2 – 2x4 + x5 。 令非基变量 x4 = x5 = 0，则  X(2) = (2, 3, 2, 0, 0)T 。 松弛变量x3 = 2 说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。 (九)判优(检验) 非基变量x4和x5的系数均为负值，如果x4 和x5从非基变量变为基变量，即从零变为正数，则目标函数值会减少，因此X(2) = (2, 3, 2, 0, 0)T 是最优解，目标函数最优值Z* = 19。 求解过程(换基迭代过程) 初始基 初始基可行解：X(0)=(0,0,4,3,8)T Z(0) =0 新的基可行解：X(1)=(0,3,4,0,2)T Z(1) =15 新的可行基 最优基 最优解：X* = (2,3,2,0,0)T Z* =19 单纯形法原理-矩阵推导(1) 单纯形法原理-矩阵推导(2) 非基变量检验数 令非基变量等于0，则 Cj CB CN CB XB b XB XN 0 XB b B N σj CB CN CB XB b XB XN CB XB B-1b I B-1N σj 0 CN – CBB-1N 单纯形法原理(单纯形表) 单纯形法求解线性规划问题的步骤： (1)求出初始基本可行解(标准化、单位基)； (2)最优性检验(非基变量检验数非正时停止，否则进入下一步)； (3)换基(迭代)； ①确定入基变量 ②确定出基变量 ③初等变换，求出新的基本可行解 (4)重复步骤(2)、(3)，直到求出最优解。 单纯形法求解步骤举例 maxZ = 2x1 + 5x2 +0x3 +0x4+0x5 x1 + x3 = 4 x2 + x4 = 3 x1 + 2x2 + x5 = 8 xj≥0, j = 1, 2, …, 5 Cj θi CB XB b 检验数?j x1 x2 x3 x4 x5 2 5 0 0 0 4 1 0 1 0 0 3 0 1 0 1 0 8 1 2 0 0 1 x3 x4 x5 0 0 0 0 2 5 0 0 0 – 3/1=3 8/2=4 4 1 0 1 0 0 3 0 1 0 1 0 2 1 0 0 -2 1 x3 x2 x5 0 5 0 2 0 0 -5 0 4 – 2 Cj θi CB XB b 检验数?j x1 x2 x3 x4 x5 2 5 0 0 0 检验数?j 2 0 0 1 2 -1 3 0 1 0 1 0 2 1 0 0 -2 1 x3 x2 x1 0 5 2 0 0 0 -1 -2 最优解: X*=(2,3,2,0,0)T，Z*=19 思考: 在最终单纯形表中，B-1 = ？4.8 单纯形法的管理启示 x1= 4 x2 = 3 x1 + 2x2 = 8 x1 x2 4 3 0 A B C(2, 3) D X(0) =(0, 0, 4, 3, 8)T X(1) =(0, 3, 4, 0, 2)T X(2) =(2, 3, 2, 0, 0)T 在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。 解：引入松驰变量x3, x4 , x5 ，化为标准形式： cj 2