线性规划问题解的概念和性质课件

1、第五节 线性规划问题解的概念和性质,线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,1,学习交流PPT,第五节 线性规划问题解的概念和性质,可行解：满足约束条件、的解X0 = ( x1，x2，xn )T为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（非奇异子矩阵）（B0），称B是线性规划问题的一个基。设：,称 B中每个列向量Pj ( j = 1 2 m) 为基向量。与基向量Pj 对应的变量xj (

2、j = 1 2 m)为基变量。除基变量以外的变量为非基变量。,2,学习交流PPT,第五节 线性规划问题解的概念和性质,范 例,A =,x1 x2 x3 x4 x5,a1 a2 a3 a4 a5,可取 B0=（a3 ,a4 ,a5）为基（| B0 |0）,这时 称 a3 ,a4 ,a5 为基向量，而 a1 ,a2 为非基向量；称 x3 ,x4 ,x5 为基变量，而 x1 ,x2 为非基变量。,3,学习交流PPT,第五节 线性规划问题解的概念和性质,基解（基本解）：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解（基本解）。可见，有一个基就可以求出一个基本解。在基解中变量

3、取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。 可行基：对应于基可行解的基称为可行基。,4,学习交流PPT,第五节 线性规划问题解的概念和性质,基本解 范例的标准形,max z = 3x1 + 5x2,s.t.,x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 , x2 , x3 , x4 , x5 0,取 B0=（a3 ,a4 ,a5）为基，令一切非基变量 x1= x2 = 0, 可解得基变量 x3 = 8 ， x4 = 12 ， x5 = 36 则得一特解 X0 = ( 0，0，8，12，3

4、6 )T,称为一个(关于 B0 为基的) 基本解。,5,学习交流PPT,第五节 线性规划问题解的概念和性质,也可取 B1= ( a2 ,a3 ,a4 )为基,得 X1 = ( 0，9，8，- 6，0 )T 还可取 B2= ( a1 ,a2 ,a3 )为基,得 X2 = ( 4，6，4，0，0 )T 等等。 基本可行解 满足非负性约束的基本解。 如 X0 ， X2 ；而 X1 不可行。 对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为 0，则称其为一个退化的基本(可行)解，否则为非退化的。 如设： X = ( 0，6，5， 0 ，0 )T 是一个基本可行解，其中 x5 =0 为基变

5、量，则该X为退化的基本可行解。,6,学习交流PPT,第五节 线性规划问题解的概念和性质,非退化的基本(可行)解， 并恰有 n m 个 0 分量。,基本可行解对应的基，称为可行基； 最优基本解对应的基，称为最优基。 如：基 B0= ( a2 ,a3 ,a4 ) 对应 X0 = ( 0，0，8，12，36 )T 可行 基 B1= ( a2 ,a3 ,a4 ) 对应 X1 = ( 0，9，8，- 6，0 )T 不可行 基 B2 = ( a1 ,a2 ,a3 ) 对应 X2 = ( 4，6，4，0，0 )T,恰有 m 个非 0 分量，,为可行基,为非可行基,为最优基,x*,x*,B*,7,学习交流PP

6、T,第五节 线性规划问题解的概念和性质,例： 求线性规划问题的所有基矩阵。,解: 约束方程的系数矩阵为25矩阵,r(A)=2，2阶子矩阵有10个，其中基矩阵（不等于0）只有9个，即,8,学习交流PPT,第五节 线性规划问题解的概念和性质,凸性的几个基本概念 一、凸集 设S En，对任意两点XS ，YS，若对满足0 1的一切 实数 ，都有 X+(1- )Y S 则称S为凸集。,凸集,凸集,非凸集,非,表示S 中两点 X，Y 连线上的任一点,凸集的几何意义：凸集S中任意两点 X，Y 连线上的点，都在凸集S中。,9,学习交流PPT,第五节 线性规划问题解的概念和性质,二、极点 设凸集S En, XS

7、，如果X不能用S中不同的两点Y和Z 表示为 X =Y+(1-)Z (01) 则称X为S的一个极点。 三、 凸组合 设XiEn, 实数i 0,i = 1,2, , s,且i = 1，则称 X = 1X1 + 2X2 + sXs 为点 X1，X2， ，Xs 的一个凸组合。,10,学习交流PPT,第五节 线性规划问题解的概念和性质,线性规划的解的性质 性质1：LP问题标准型的可行域 R = XAX=b, X 0 是凸集。 性质2：LP问题标准型的一个基本可行解与可行域 R 的一个极点 互相对应。 性质3：线性规划的基本定理 对于一个给定的标准型LP问题标准型来说： 若标准型有可行解，则必有基本可行解； 若标准型有最优解，则必有最优基本解。 性质4：若LP问题的可行域 R, 则 R 至少有一极点。 性质5：LP问题可行域 R 的极点数目必为有限个。,11,学习交流PPT,第五节 线性规划问题解的概念和性质,仅就标准形LP问题说明其合理性。 因标准型是一个m阶n维的LP问题，则从其系数阵的n列中取出m列，所构成其基的个数不超过, ,基本可行解的