单纯形法基本原理及实例演示.pptVIP

初始单纯形表 迭代次数 基变量 CB x1 X2 s1 s2 S3 b 比值 50 100 0 0 0 3 x1 50 1 0 1 0 -1 50 S2 0 0 0 -2 1 1 50 x2 100 0 1 0 0 1 250 Zj=CBNj Z= 27500 初始单纯形表 迭代次数 基变量 CB x1 X2 s1 s2 S3 b 比值 50 100 0 0 0 3 x1 50 1 0 1 0 -1 50 S2 0 0 0 -2 1 1 50 x2 100 0 1 0 0 1 250 Zj=CBNj 50 100 50 0 50 Z= 27500 初始单纯形表 迭代次数 基变量 CB x1 X2 s1 s2 S3 b 比值 50 100 0 0 0 3 x1 50 1 0 1 0 -1 50 S2 0 0 0 -2 1 1 50 x2 100 0 1 0 0 1 250 Zj=CBNj 50 100 50 0 50 Z= 27500 0 0 -50 0 -50 表格中，检验系数σj全部小于或等于0，根据判断规则，Z值为最优值（Z=27500），其解： X1=50,S1=50,X2=250,s2=s3=0为模型的最优解。 单纯形法求解—动态演示 在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是 美国数学家G·B·Dantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。 线性规划问题标准型的矩阵形式： Max Z = CX （a） s.t. AX=b （ b） X ? 0 （c） a11 a12 …. a1n b1 A= a21 a22 …. a2n b = b2 …………………………… ………… am1 am2 …. amn bm 一、关于标准型解的若干基本概念 基矩阵  示例: 0 0 0 0 3 2 0 2 0 0 0 1 0 1 0 x1 x2 x4 x3 0 0 1 3 0 0 3 2 1 = 目标函数 约束条件 行列式≠0 基矩阵 X1,x2,x3为基变量,x4为非基变量 因为B为基, 故有 XB +B-1N XN = B-1b， 解得可行解XB=B-1b-B-1NXN，代入目标函数Z， Z = CB B-1b + (CN- CB B-1N ) XN 令非基变量XN = 0 ，则有 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1b AX=b Z = CX 设 A=（B , N）（B为一个基，即线性无关向量组R(A)=R(B)） XT= (XB , XN) T （XB 为基变量，XN为非基变量） C= (CB , CN) （CB 为基变量系数，CN为非基变量系数） 则有： Z= (CB , CN) (XB , XN) T= CB XB+CN XN AX =（ B , N） (XB , XN) T = B XB+ N XN = b 1、单纯形法原理： Z = CB B-1b + (CN- CB B-1N ) XN 如果CN- CB B-1N小于0，无论XN取任何大于0值，只会让Z变小，因此我们可以通过CN- CB B-1N来判断Z取得是不是最大值。 如果存在一个CN- CB B-1N大于0，则说明Z的值会随着XN增大而增大，说明Z有调整的余地。 定理一：若某个基本可行解所对应的检验向量CN- CB B-1N =0,则这个基本可行解就是最优解。 定理二：若某个基本可行解所对应的检验向量CN- CB B-1N存在一个检验数=0,则该问题有无数多个最优解。 定理三：若某个基本可行解所对应的检验向量Cj- CB B-1Nj大于0，且aij,都小于0，