教案2标准型及解的几何意义(改).ppt

1,13 线性规划问题的标准形式 为了求解LP问题，必须统一其模型，本课程选用标准型式为,（1) 目标函数为求最大,对于目标函数是求最小怎么办？ min Z=1000 x1+800 x2,令：z= -z, 则minz=maxz,maxZ= -1000 x1-800 x2,2,（2)约束条件均用线性等式方程来表示， 且右边常数项均非负。,实际情形约束条件显然不可能都是等式关系。,当表达式中含“”时,可在约束条件左边加上一个非负的变量松弛变量，使原来的“”变为“”；,3,当表达式中含“”时，,可以在约束条件左边减去一个非负变量剩余变量， 使原来的“”变为“”。,4,（3）所有变量要求非负,现实中，有些变量可能从物理意义或经济意义上讲没有非负要求,min z =x1x24 x3 st 3 x24 x3 9 x1 + x2 6 5 x22 x3 16 x1 0 ，x2 0， x3无符号限制,解：令x1=x1，x10， x3 = x3x3, x3、x3 0 将第一个约束条件两端乘“1”并加入松弛变量x4， 第二个约束减剩余变量x5，第三个约束加入松弛变量x6，代入整理后得：,maxz =x1x24 x34 x3 st 3 x24 x34 x3x4 9 x1 + x2 x5 = 6 5 x22 x32 x3 +x6 = 16 x1， x2， x3、 x3，x4，x5，x60,5,练习：,min z =2x1x22x3 st x1x2x3 4 x1 + x2 x3 6 x1 0 ，x2 3， x3无符号限制,max z =2x1+x23x3 x4 st x1+x2x3 x4 7 2x1-3x2x3 -8 x1-2x22x4 1 x1 , x3 0, x2 0， x4无符号限制,再思考：如果x有区间限制怎么办？,6,经过上述过程，可得到线性规划问题数学模型的标准形式为：,max z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3) 其中bi 0，（i =1，2，m） 一般m 0。,7,标准型的简写形式: max z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3),用求和符号表示,8,用矩阵描述为： max z =CX AX = b X 0,称 A 为约束条件的m n 阶系数矩阵，一般A的秩为m。,0 =,0 0 0,9,用向量表示：,向 量 Pj 对 应 的 决 策 变 量 为 xj 。,10,(p1,p2, ,pn) Pjxj=b,a11 a12 a1n a21 a22 a2n am1 am2 amn,x1 x2 xn,=,xj0 j=1,n,Max z=,x1 x2 xn,(c1 , c2, ,cn ),=cjxj,=CX,=,aijxj =bi,i=1,m,AX = b X 0,b,11,14 线性规划问题的解的概念,12, 基 A中的m m 阶非奇异矩阵B ； （意味着A的秩为m，|B | 0，B 的各列线性无关） 基向量 B中的列向量； 基变量 B中的列向量对应的变量； 非基变量 非B中的列向量对应的变量； 例如，若A的前m列线性无关，则,是个基。 P1，P2，Pm是基向量； x1，x2，xm 是基变量； xm+1，xn 是非基变量； 若Amn，mn，则至多有 个基，每个基有m个基变量，n- m 个非基变量。,13, 基解 对应每一个基B,令所有非基变量为零，由 (1.5) 约束方程组求得的解X ； 约束方程组(1.5)中，有m 个方程n 个变量，mn，有无穷多解，若前m个系数向量线性无关，令xm+1=xn =0，则可求出XB =( x1，x2，xm)T，则X=( x1，x2，xm，0，0)T就是一个基解。 至多有 个基解，基解的非零分量至多m个，非零分量个数小于m 的基解为退化解。 基可行解 满足非负条件(1.6)的基解； 同样至多有 个基可行解，基可行解至多有m个正分量。 可行基 对应于基可行解的基； 基最优解 使目标函数达到最大值的基可行解。 ：,14,上述解的概念中基解和基可行解最为重要，各种解的关系粗略地可用下图表示：,15,本节重点： 凸组合的概念 凸集的概念 线性规划基本定理,16,17,2 线性规划问题的几何意义,本节重点： 凸组合的概念 凸集的概念 线性规划基本定理,18,21 基本概念, 凸组合 设 ，若存在 ，0 1 ，且 ，使 则称X 为 的凸组合。,二维空间,两点连线上的任何一点都是这两点的凸组合,19,凸集,20,图中红粗线和红点是顶点。,21,22,23,24,25,26,27,结论： 线性规划问题的可行域是凸集（凸多面体），有有限多个顶点。顶点对应基可行解。当可行域有界时，必有顶点达到目标函数最优值。,28,因此，下面求解线性规划问题就是求其基最优解，当存在无穷多最优解时，若能找出它的所有基最优解，这些基