运筹学_7 特殊问题+总流程

1、运筹学 Operational Research Lec. 7 特殊问题 & 总流程 & Excel实现目录l特殊情况l大M方法l单纯形方法解LP问题的总流程l计算机求解单纯形中的特殊问题 l单纯形中的特殊问题l存在四种特殊问题l过程中的退化；结果的无解与无穷多解；找不到初始最优解l如何处理l退化问题l终止计算的判断：无界与无穷，P20l初始基可行解的问题，引出人工初始解退化问题与Bland规则l进基出基时，若进基出基变量不唯一，选择下标小者进、出基。l称为Bland规则l裘宗沪解线性规划的单纯形算法中避免循环的几种方法终止条件l最优解l多重解l无界解终止条件之一：最优解l对最

2、大问题，若检验数均0，则已经得到最优解；否则继续迭代运算终止条件之二：多重最优解l对最大问题，若基变量检验数均0，又存在非基变量的检验数0，则具有多重最优解。终止条件之三：无界解l对最大问题，若至少有一个检验数0，对某个大于零的检验数对应的xk的系数均0，则问题无界解，停止计算单纯形表案例（3）lmax z3x12x2ls.t. -2x1x2 2 x1 -3x2 3 x1，x2 0单纯形表案例（3）lmax z3x12x2ls.t. -2x1x2 x3 = 2 x1 -3x2 x4 3 x1-4 0单纯形表案例（3）基变量原始价值系数基变量Cj3 2 0 0 bCBXB变量系数00 x3x4-

3、2 1 1 0 1 -3 0 1 23检验行3 2 0 00 填表检验单纯形表案例（3）基变量原始价值系数基变量Cj3 2 0 0 bCBXB变量系数00 x3x4-2 1 1 0 1 -3 0 1 23检验行3 2 0 00 进基 离基单纯形表案例（3）基变量原始价值系数基变量Cj3 2 0 0 bCBXB变量系数03x3x1-2 1 1 0 1 -3 0 1 23检验行3 2 0 00 进基 离基单纯形表案例（3）基变量原始价值系数基变量Cj3 2 0 0 bCBXB变量系数03x3x10 -5 1 2 1 -3 0 1 83检验行0 11 0 -39 进基 离基人工初始解l为什么需要人工

4、初始解？l前面例子中的约束条件：左侧右侧l因此，松弛变量系数均为“1”，很容易找到基，其他非基变量均为零（解在原点处），一定是一个可行解。这样，很容易找到初始”基本可行解“。l约束条件为“=”,“”的情况下，却不能保证是“基本可行解”，该如何处理？人工初始解l人工初始解包括两种处理办法l大M法：考察重点l两阶段法大M法思想l基本方法：l在上述情况下，加入人工变量：Rl但是，人工变量是虚拟的，最终不应影响结果，也就是必须要离基l因此，目标函数中增加项：MR（系数M是充分大的正数）。当迭代终了，如果仍有人工变量R为非零基变量，则目标函数不可能实现最大化，无可行解。大M法案例l原题lmin z3x1

5、x2 x3ls.t. x12x2 x3 11 -4x1 +x2 2x3 3 -2x1 + x3 1 x1，x2 ，x3 0大M法案例l加入松弛变量、剩余变量和人工变量lmax z3x1x2 x3 0 x4 0 x5 Mx6 Mx7 ls.t. x12x2 x3 x4 11 -4x1 +x2 x5 x6 3 -2x1 + x3 x7 1 x17 0大M法案例价值系数基变量Cjb31100M MCBXBx1x2x3x4x5x6x70 x4121100011Mx641201103MX720100011（最小）检验行3-6M 1M1+3M（最大）0M00？大M法案例价值系数基变量Cjb31100MMC

6、BXBx1x2x3x4x5x6x70 x4320100110Mx601001121min1X320100011检验行11M（max）00M03M+1？大M法案例价值系数基变量Cjb31100MMCBXBx1x2x3x4x5x6x73x1300122512min1x2010011211X320100011检验行1max0001M+1M1？大M法案例价值系数基变量Cjb31 100MMCBXBx1x2x3x4x5X6x73x11001/32/32/35/341x20100-11211X30012/3-4/34/3-7/39检验行000-1/3 1/3 M+1/3 M+2/3？大M法案例价值系数基变

7、量Cjb31100MMCBXBx1x2x3x4x5X6x73x11001/32/32/35/341x20100-11211X30012/3-4/34/3-7/39检验行000-1/31/3M+1/3M+2/3解为解为(4,1,9) 值为值为2两阶段法思想l大M法的问题：计算机计算中的误差问题l两阶段法的思想：l第一阶段：构造人工变量目标函数，求目标最小。l若目标最小为零，则有可行解l否则无可行解，停止计算l求解原问题两阶段法案例l原题lmin z3x1x2 x3ls.t. x12x2 x3 11 -4x1 +x2 2x3 3 -2x1 + x3 1 x1，x2 ，x3 0两阶段法案例l加入松弛

8、变量、剩余变量和人工变量lmin wx6x7ls.t. x12x2 x3 x4 11 -4x1 +x2 x5 x6 3 -2x1 + x3 x7 1 x17 0max z3x1x2 x3 0 x4 0 x5 Mx6 Mx7两阶段法案例价值系数基变量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x4121100011-1x641201103-1X720100011min检验行-613max0-100两阶段法案例价值系数基变量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x4320100-110-1x6010011-21min0X3-20100011检验行01m

9、ax00-10-3两阶段法案例价值系数基变量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x43001-22-5120 x2010011-210X3-20100011检验行00000-1-1第一阶段结束，解为（0,1,1,12,0,0,0），目标值为0。进入第二阶段两阶段法案例价值系数基变量Cjb00000-1-1CBXBx1x2x3x4x5x6x70 x43001-22-5120 x2010011-210X3-20100011检验行0000011去掉人工变量列，恢复目标函数，继续迭代两阶段法案例价值系数基变量Cjb31100CBXBX1x2x3x4x50X43001-212

10、min1X20100111X3-201001检验行1max0001min z3x1x2 x3两阶段法案例价值系数基变量Cjb31100CBXBx1x2x3x4x53X11001/3-2/341X20100111X30012/3-4/39检验行000-1/3 -1/3min z3x1x2 x3两阶段法案例价值系数基变量Cjb31100CBXBx1x2x3x4x53X11001/3-2/341X20100111X30012/3-4/39检验行000-1/3 -1/3解为（解为（4,1,9,0,0）；值为）；值为3x1x2 x32计算机求解：ExcellExcell见附件计算机求解：Matlabl%

11、 x,fval,exitflag,output,lambda即最优解,最优值, 输出标记,迭代次数,存储情况l% linprog(f,a,b,lb)即（目标函数,系数矩阵,约束常数向量,等式系数矩阵,等式常数向量,决策变量下界,决策变量上界）l% min z=fl% s.t. a*xbl aeq*x=beql lbxub计算机求解：Matlab f=-2,-3;% 目标函数 a=1 1; 1 2;0 1;% 系数矩阵 b=6 8 3;% 约束常数向量 lb=zeros(2,1);% 决策变量下界x,fval,exitflag,output,lambda=linprog(f,a,b,lb)lmax z2x13x2ls.t. x1x2 6 x1 +2x2 8 x2 3 x1，x2 0计算机求解：MatlablOptimization terminated.lx =l 4.0000l 2.0000lfval =l -20.0000lexitflag =l 1loutput = l iterations: 7l algorithm: large-scale: interior pointl cgiterations: 0l message: Optimizat