北京交通大学运筹学教案2标准型及解的几何意义(改).ppt

1,13线性规划问题的标准形式为了求解LP问题，必须统一其模型，本课程选用标准型式为,（1)目标函数为求最大,对于目标函数是求最小怎么办？minZ=1000 x1+800 x2,令：z=-z,则minz=maxz,maxZ=-1000 x1-800 x2,2,（2)约束条件均用线性等式方程来表示，且右边常数项均非负。,实际情形约束条件显然不可能都是等式关系。,当表达式中含“”时,可在约束条件左边加上一个非负的变量松弛变量，使原来的“”变为“”；,3,当表达式中含“”时，,可以在约束条件左边减去一个非负变量剩余变量，使原来的“”变为“”。,4,（3）所有变量要求非负,现实中，有些变量可能从物理意义或经济意义上讲没有非负要求,minz=x1x24x3st3x24x39x1+x265x22x316x10，x20，x3无符号限制,解：令x1=x1，x10，x3=x3x3,x3、x30将第一个约束条件两端乘“1”并加入松弛变量x4，第二个约束减剩余变量x5，第三个约束加入松弛变量x6，代入整理后得：,maxz=x1x24x34x3st3x24x34x3x49x1+x2x5=65x22x32x3+x6=16x1，x2，x3、x3，x4，x5，x60,5,练习：,minz=2x1x22x3stx1x2x34x1+x2x36x10，x23，x3无符号限制,maxz=2x1+x23x3x4stx1+x2x3x472x1-3x2x3-8x1-2x22x41x1,x30,x20，x4无符号限制,再思考：如果x有区间限制怎么办？,6,经过上述过程，可得到线性规划问题数学模型的标准形式为：,maxz=c1x1+c2x2+cnxn(1.1)s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2(1.2)am1x1+am2x2+amnxn=bmx1，x2，xn0(1.3)其中bi0，（i=1，2，m）一般m0。,7,标准型的简写形式:maxz=c1x1+c2x2+cnxn(1.1)s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2(1.2)am1x1+am2x2+amnxn=bmx1，x2，xn0(1.3),用求和符号表示,8,用矩阵描述为：maxz=CXAX=bX0,称A为约束条件的mn阶系数矩阵，一般A的秩为m。,0=,000,9,用向量表示：,向量Pj对应的决策变量为xj。,10,(p1,p2,pn)Pjxj=b,a11a12a1na21a22a2nam1am2amn,x1x2xn,=,xj0j=1,n,Maxz=,x1x2xn,(c1,c2,cn),=cjxj,=CX,=,aijxj=bi,i=1,m,AX=bX0,b,11,14线性规划问题的解的概念,12,基A中的mm阶非奇异矩阵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,2线性规划问题的几何意义,本节重点：凸组合的概念凸集的概念线性规划基本定理,16,17,2线性规划问题的几何意义,本节重点：凸组合的概念凸集的概念线性规划基本定理,18,21基本概念,凸组合设，若存在，01，且，使则称X为的凸组合。,二维空间,两点连线上的任何一点都是这两点的凸组合,19,凸集,20,图中红粗线和红点是顶点。,21,22,23,24,25,26,27,结论：线性规划问题的可行域是凸集（凸多面体），有有限多个顶点。顶点对应基可行解。当可行域有界时，必有顶点达到目标函数最优值。,28,因此，下面求解线性规划问题就