教案型及解的几何意义改

1、113 线性规划问题的标准形式 为了求解LP问题，必须统一其模型，本课程选用标准型式为（1) 目标函数为求最大 对于目标函数是求最小怎么办？min Z=1000 x1+800 x2 令：z= -z, 则minz=maxzmaxZ= -1000 x1-800 x22（2)约束条件均用线性等式方程来表示，且右边常数项均非负。 实际情形约束条件显然不可能都是等式关系。 当表达式中含“”时 可在约束条件左边加上一个非负的变量松弛变量，使原来的“”变为“”； max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2

2、，x3，x4，x5 0 max z = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 03当表达式中含“”时， 可以在约束条件左边减去一个非负变量剩余变量，使原来的“”变为“”。 目标：min f =1000 x1+800 x2约束条件： x1 1 0.8 x1+ x2 1.6 x1 2 x2 1.4 x1、x2 0maxzminz1000 x1800 x20 x30 x40 x50 x6 st x1 x3 1 0.8 x1+ x2 x4 1.6 x1 x5 2 x2 x61.4 x1、x2、x3、x4、x5、x60 4（3）所有变量要求非负

3、现实中，有些变量可能从物理意义或经济意义上讲没有非负要求 min z =x1x24 x3st 3 x24 x3 9x1 + x2 65 x22 x3 16 x1 0，x2 0， x3无符号限制 解：令x1=x1，x10， x3 = x3x3, x3、x3 0 将第一个约束条件两端乘“1”并加入松弛变量x4，第二个约束减剩余变量x5，第三个约束加入松弛变量x6，代入整理后得： maxz =x1x24 x34 x3st 3 x24 x34 x3x4 9x1 + x2 x5 = 65 x22 x32 x3 +x6 = 16 x1， x2， x3、 x3，x4，x5，x60 5练习： min z =2

4、x1x22x3st x1x2x3 4x1 + x2 x3 6 x1 0，x2 3， x3无符号限制 max z =2x1+x23x3 x4st 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 =

5、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= (P1，P2，Pn)；a11 a12 a1na21 a22 a2n am1 am2 amnA=称 A 为约束条件的m n 阶系数矩阵，一般A的

6、秩为m。0 =0009用向量表示：X=x1x2xnPj =a1ja2jamjb=b1b2bm向 量 Pj 对 应 的 决 策 变 量 为 xj 。10b1b2 bm (p1,p2, ,pn)Pjxj=b a11 a12 a1n a21 a22 a2n am1 am2 amn x1x2 xn=xj0 j=1,nx1x2 xnMax z=x1x2 xn (c1 , c2, ,cn )=cjxj=CX=aijxj =bi i=1,mAX = b X 0 b1114 线性规划问题的解的概念 max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4

7、 x2 +x5 =12 x1，x2，x3，x4，x5 012 基 A中的m m 阶非奇异矩阵B ；（意味着A的秩为m，|B | 0，B 的各列线性无关） 基向量 B中的列向量； 基变量 B中的列向量对应的变量； 非基变量 非B中的列向量对应的变量；例如，若A的前m列线性无关，则a11 a12 a1ma21 a22 a2m am1 am2 amm=( P1，P2，Pm )B =是个基。P1，P2，Pm是基向量；x1，x2，xm 是基变量；xm+1，xn 是非基变量； 若Amn，mn，则至多有 个基，每个基有m个基变量，n- m 个非基变量。13 基解 对应每一个基B,令所有非基变量为零，由 (1

8、.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 上述解的概念中基解和基可行解最为重要，各种解的关系粗略地可用下图表示： 非可行解可行解 基解基可行解最

9、优解152线性规划问题的几何意义本节重点：凸组合的概念凸集的概念线性规划基本定理16如例1，max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 0 x1x2O4 Q2(4,2)Q1Q3Q43A172线性规划问题的几何意义本节重点：凸组合的概念凸集的概念线性规划基本定理1821基本概念 凸组合 设 ，若存在 ，0 1，且 ，使则称X 为 的凸组合。 X1X2X21二维空间两点连线上的任何一点都是这两点的凸组合19(a)(b)(c)(d)(e)凸集20(a)(b)(c)(d)(e)图中

10、红粗线和红点是顶点。21222324252627结论： 线性规划问题的可行域是凸集（凸多面体），有有限多个顶点。顶点对应基可行解。当可行域有界时，必有顶点达到目标函数最优值。28 因此，下面求解线性规划问题就是求其基最优解，当存在无穷多最优解时，若能找出它的所有基最优解，这些基最优解的任一凸组合便表示它的一个最优解。29练习 X1和X2为某一线性规划问题的最优解，证明该线性规划问题有无穷多个最优解。30如例1，max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 0 x1x2O4 Q2(4,2)Q1Q3Q43A31选基变量 基 基解 是否为基可行解 z值（x1,x2,x4) 2 0 0 1 0 4 0（2,3,0,8,0）T是 13（x1,x2,x3) 2 1 0 0 0 4 0（4,3,-2,0,0）T否 （x1,x3,x5) 2 0 0 0 0 4 1（4,2,0,0,4）T是 14（x1,x3,x4) 1 0 0 1 0 0 0 |B|=0 无基和基解 （x1,x4,x5) 0 0 1 0 0 0 1（8,0,0,-16,12）T否 32选基变量 基 基解 是否为基可行解 z值（x2,x3,x4) 2 1 0 0 0 1 4 0 0（0,3,2,16,