线性规划标准型以及定义.ppt
第一节 线性规划的标准型,目标函数：,约束条件：,松弛变量，剩余变量,线性规划问题的标准形式,特点：(1)目标函数求最小值（有时求最大值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。,（2）如何化标准形式,目标函数的转换,如果是求极大值即，则可将目标函数乘以(-1)，可化为求极小值问题。,也就是：令，可得到上式。,即,若存在取值无约束的变量，可令 其中：,变量的变换,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令，显然,例1 将下列线性规划问题化为标准形式,用 替换，且,解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以,(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数不变,标准形式如下：,一、图解法,第二节 解的性质,max Z=2X1+X2 X1+1.9X2 3.8 X1-1.9X2 3.8s.t.X1+1.9X2 10.2 X1-1.9X2-3.8 X1，X2 0,例2 用图解法求解线性规划问题,图解法,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),4=2X1+X2,20=2X1+X2,17.2=2X1+X2,11=2X1+X2,Lo：0=2X1+X2,（7.6，2）,D,max Z,min Z,此点是唯一最优解，且最优目标函数值 max Z=17.2,可行域,max Z=2X1+X2,图解法,max Z=3X1+5.7X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),（7.6，2）,D,L0：0=3X1+5.7X2,max Z,（3.8，4）,34.2=3X1+5.7X2,蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=34.2是唯一的。,可行域,图解法,min Z=5X1+4X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1+1.9X2=10.2(),D,L0：0=5X1+4X2,max Z,min Z,8=5X1+4X2,43=5X1+4X2,（0，2）,可行域,此点是唯一最优解,图解法,2,4,6,x1,x2,2,4,6,无界解(无最优解),max Z=x1+2x2,例3,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),max Z=3x1+4x2,例4,图解法,学习要点：1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动,二线性规划解的定义,可行解：满足约束条件Ax=b、x0的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最小值的可行解。基：设A为约束条件Ax=b的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设：,称 B中每个列向量Pj(j=1 2 m)为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量。,基解：某一确定的基B，令非基变量等于零，由约束条件方程Ax=b解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。,例1.4 求线性规划问题的所有基矩阵。,解:约束方程的系数矩阵为25矩阵,r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即,解的定义,解的定义,解的定义,解的定义,类似可得所有基解。,代入目标函数，通过比较可得最优解。,思考：线性规划的基解最多有多少个？基可行解呢？,引理1：设x00是线性规划的可行解，则x0必定是基可行解。,解的定义,分析：要证x00是基解，由定义，只需要证明存在非奇异子阵B，使得 xB=B-1b=0,xN=0,从而，x0是基解。,解的定义,证明：因为x00是可行解，所有满足Ax0A00b。设r(A)=m,任取一个m阶非奇异方阵,引理2：设x0是线性规划的可行解，并且若相应的P1，P2，Ps线性无关，则x0是基可行解。,证明：设r(A)=m,因为P1，P2，Ps线性无关，所以sm.可以从A中补充(m-s)个列向量，使得新向量组是A的一个极大线性无关组，,解的定义,不妨设为P1，P2，Ps，Ps+1,Pm,则B=(P1，P2，Ps，Ps+1,Pm)为非奇异矩阵，又,解的定义,问:1。若x是线性规划的一基解,那么其中非 零变量最多有多少个?零变量最少多少个？,解的定义,2。已知一可行解，且非零个数小于m，是否一定是基可行解？,解的定义,解的定义,解的定义,注:由可行解中非零变量的个数以及对应列的相关无关性可判断是否是基解.,解的定义,定理2:线性规划可行解的集合R=x|Ax=b,x0是凸集.点x0是R的极点充分必要条件是x0是线性规划的基可行解.,二.解释及相关性质,再证x0是R的极点.假设不是,由定义,解释及相关性质,解释及相关性质,解释及相关性质,解释及相关性质,再证必要性.反证.,（即构造两个可行解x1，x2使得x0是这两个点的组合）,设x0是极点,但不是基可行解.不失一般性,设前s个分量大于0,后面n-s个分量为0.,定理3的第二个结论可知A的前s个列向量线性相关.于是存在一组不全为0的数满足,解释及相关性质,解释及相关性质,解释及相关性质,解释及相关性质,说明:从证明的过程来看,对于任意一个可行解,如果不是基解，可以通过所给的方法，可以得到一可行解，其中0分量的个数至少增加一个。反复进行，一定会得到一基可行解。,解释及相关性质,解释及相关性质,解释及相关性质,线性规划基本定理:1.若线性规划有可行解,则一定有基可行解.,解释及相关性质,2.若线性规划有最优解,则一定可以在基可行解上达到.,（换句话说，若有最优解，必有基础最优解）,证明：设x为最优解。若x是极点，得证。若不是极点，由定理3中所证，可以表示为一些点的线性组合，其中一个为极点，不妨设为,解释及相关性质,注：l是有限的。（思考：为什么？）,因为：变量的个数n是有限的。而定理3的方法操作一次，多出一个0分量，同时多出一个解。这样，最多有p+1步（此时基解等于0）。即lp+1。,解释及相关性质,带入目标函数，得,又x0最优解，所以所有解目标函数值相等。也即，xl为最优解，且为极点。,
