资源描述
单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,引例,（上一章例）,求解线性规划问题的基本思路,1、构造初始可行基；,2、求出一个基可行解（顶点）,3、最优性检验：判断是否最优解；,4、基变化，转2。要保证目标函数值比,原来更优。,从线性规划解的性质可知求解线性规划问题的基本思路。,第1步 确定初始基可行解,根据,显然 ， 可构成初等可行基,B 。,为基变量,第2步 求出基可行解,基变量用非基变量表示，并令非基变量为 0时对应的解,是否是最优解？,第3步,最优性检验,分析目标函数,检验数,0 时，,无解,换基，继续,只要取 或 的,值可能增大。,换入？基变量,换出？基变量,考虑将 或 换入为基变量,第4步 基变换,换入基变量：,换入变量,（即选最大非负检验数对应的变量）,一般选取,对应的变量,均可,换入。,换出变量,使换入的变量越大越好,同时，新的解要可行。,选非负 的最小者对应的变量换出,为换入变量，应换出,？,变量。,思考：,当,时会怎样？,因此，基由,变为,转第,2,步：基变量用非基变量表示。,第3步：最优性判断,检验数 存在正，按第4步换基继续迭代,均非正，停止,（这时的解即是最优解）,为换入变量，应换出,变量。,转 第,2,步,继续迭代, 可得到:,最优值,最优解,结合图形法分析,（单纯形法的几何意义）,6 ,5 ,4 ,3 ,2 ,1 ,0,x,2,|,123456789,x,1,A(0,3),B(2,3),C(4,2),D(4,0),单纯形法迭代原理,从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法,单纯形法迭代原理,。,观察法:直接观察得到初始可行基,约束条件: 加入松弛变量即形成可行基。（下页）,约束条件: 加入非负人工变量, 以后讨论.,1、初始基可行解的确定,1、初始基可行解的确定,不妨设 为松弛变量，则约束方程组可表示为,1、初始基可行解的确定,2、最优性检验与解的判别,2、最优性检验与解的判别,代入目标函数有：,2、最优性检验与解的判别,(1) 最优解判别定理：若：,为基可行解，且全部,则 为最优解。,（2）唯一最优解判别定理：若所有,则存在唯一最优解。,2、最优性检验与解的判别,（3）,无穷多最优解判定定理：若：,且存在某一个非基变量,则存在无穷多最优解。,（4）无界解判定定理：若有某一个非基,变量,并且对应的非基变量的系数,则具有无界解。,2、最优性检验与解的判别,（4）之证明：,2、最优性检验与解的判别,最优解判断小结,（用非基变量的检验数）,所有,基变量中有,非零人工变量,某非基变量,检验数为零,唯一最优解,无穷多最优解,无可行解,对任一,有,换基继续,Y,Y,Y,Y,N,N,N,无界解,N,以后讨论,3、基变换,换入变量确定,对应的 为换入变量,. (一般),注意,：,只要 对应的变量,均可作为换入变量,此时，目标函数,换出变量确定,3、基变换,Z,大,大,（在可行的范围内）,则对应的 为换出变量.,4、迭代运算,写成增广矩阵的形式,进行迭代.,例：,4、迭代运算,非基变量,基变量,0,0,1,通过初等行变换化主列为,主元,4、迭代运算,每次迭代的信息都在增广矩阵及目标函数中。,检验数,
展开阅读全文