毕业答辩ppt模板-中国地质大学.ppt

第一章单纯形法运筹学 2 2 华东交通大学工业工程与物流管理系线性规划单纯形法?单纯形法(Simplex Method) 是美国人丹捷格()1947 年创建的?这种方法简捷、规范,是举世公认的解决线性规划问题行之有效的方法。?单纯形法的表现形式: –代数法–表格法–矩阵法运筹学 3 3 华东交通大学工业工程与物流管理系单纯形法线性规划问题的几何意义: ?凸集:没有凹入部分,内部没有空洞。实****圆、实心球体、实心立方体都是凸集;两个凸集的交集是凸集。?若线性规划问题存在可行域,则可行域是凸集。?线性规划问题的基可行解对应可行域的顶点。?若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。运筹学 4 4 华东交通大学工业工程与物流管理系单纯形法的一般原理?考虑线形规划问题: max Z = CX AX =b X ≥0 如果有可行域 D= {X ∈ Rn|AX=b, X ≥0}非空有界,则 D上的最优目标函数值 Z= CX 一定可以在 D的顶点达到。运筹学 5 5 华东交通大学工业工程与物流管理系单纯形法的基本思路?根据线性规划问题的标准型,从可行域中某个基可行解一个顶点)开始,转换到另一个基可行解(顶点),并且使目标函数达到最大值时,问题就得到最优解。?因此得到 5个步骤: ?初始解?判优?判无界?换基?迭代运筹学 6 6 华东交通大学工业工程与物流管理系确定初始的基本可行解?确定初始的基本可行解=确定初始的可行基?初始的可行基确定——对应初始基本可行解确定运筹学 7 7 华东交通大学工业工程与物流管理系最优解判别最优解判别不妨假设不妨假设 A= A= ( ( B , N B , N ) )( (B B为一个基为一个基) ) 相应地有相应地有 X X t t = (X = (X B B , X , X N N ) ) t t C= (C C= (C B B , C , C N N ) )由式 max Z = CX AX =b X ≥0 Z= Z= (C (C B B , C , C N N ) (X ) (X B B , X , X N N ) ) t t = C = C B B X X B B + +C C N N X X N N AX AX =( =( B , N) (X B , N) (X B B , X , X N N ) ) t t = B = B X X B B + N + N X X N N = b = b 运筹学 8 8 华东交通大学工业工程与物流管理系因为因为 B B为一个基为一个基, det(B)>0 , det(B)>0 有有X X B B = B = B -1 -1 b- B b- B -1 -1 N X N X N N ( ( ) ) Z=C Z=C B B B B -1 -1 b + b + (C (C N N- -C C B B B B -1 -1 N ) N ) X X N N ( ( ) ) 令令X X N N= =0 0,则基变量,则基变量 X X B B= =B B -1 -1b b X X = (X = (X B B , X , X N N ) = ) = ( (B B -1 -1 b , 0 b , 0 ) ) T T为基础解,其目标函数为基础解,其目标函数值为值为 Z = Z = C C B B B B -1 -1b b只要只要 X X B B = B = B -1 -1 b >= 0, X b >= 0, X t t = =( (B B -1 -1 b , 0 b , 0 ) ) >=0 >=0 X X为基础可行解为基础可行解, B , B 就是可行基。就是可行基。运筹学 9 9 华东交通大学工业工程与物流管理系对公式对公式 Z=C Z=C B B B B -1 -1 b + b + (C (C N N - C - C B B B B -1 -1 N ) N ) X X N N ( ( ) ) 若满足若满足 C C N N- -C C B B B B -1 -1 N <= 0 N <= 0 或