线性规划问题解的概念和性质（课堂PPT）

1、1第五节 线性规划问题解的概念和性质线性规划问题的解线性规划问题的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目标函数(1)达到最大值。达到最大值。2第五节 线性规划问题解的概念和性质 可行解可行解：满足约束条件、的解：满足约束条件、的解X X0 0 = ( x = ( x1 1，x x2 2，x xn n ) )T为可行解。所有可行解的集合为可行域。

2、为可行解。所有可行解的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。 基：基：设设A为约束条件的为约束条件的mn阶系数矩阵阶系数矩阵(mn)，其秩为，其秩为m，B是矩阵是矩阵A中中m阶满秩子矩阵（非奇异子矩阵）（阶满秩子矩阵（非奇异子矩阵）（ B 0），），称称B是线性规划问题的一个基。设：是线性规划问题的一个基。设：) (11111mmmmmppaaaaB 称称 B中每个列向量中每个列向量Pj ( j = 1 2 m) 为基向量。与基向量为基向量。与基向量Pj 对应的变量对应的变量xj ( j = 1 2 m)为为基变量基变量。除基变量以外的变。

3、除基变量以外的变量为量为非基变量非基变量。 3第五节 线性规划问题解的概念和性质A =1 0 1 0 0 0 2 0 1 03 4 0 0 1 x1 x2 x3 x4 x5a1 a2 a3 a4 a5 可取可取 B0=（a3 , ,a4 , ,a5）为基（）为基（| B0 |0）, ,这时这时称称 a3 , ,a4 , ,a5 为为基向量基向量，而，而 a1 , ,a2 为为非基向量非基向量；称称x3 , ,x4 , ,x5 为为基变量基变量，而，而 x1 , ,x2 为为非基变量非基变量。4第五节 线性规划问题解的概念和性质 基解（基本解）：基解（基本解）：某一确定的基某一确定的基B，令非基

4、变量等于零，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解（基本由约束条件方程解出基变量，称这组解为基解（基本解）。可见，有一个基就可以求出一个基本解。在基解中解）。可见，有一个基就可以求出一个基本解。在基解中变量取非变量取非0值的个数不大于方程数值的个数不大于方程数m，基解的总数不超过，基解的总数不超过 基可行解：基可行解：满足变量非负约束条件的基本解，简称基可行满足变量非负约束条件的基本解，简称基可行解。解。 可行基：可行基：对应于基可行解的基称为可行基。对应于基可行解的基称为可行基。mnC非可行解非可行解可可行行解解基解基解基可行解基可行解5第五节 线性规划问题解的概念和性质

5、基本解基本解的标准形的标准形max z = 3x1 + 5x2s.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，36 )T 称为一个称为一个(关于关于 B0 为基的为基的) 基本解基本解。6第五节 线性规划问题解的概念和性质也可取也可取 B1=

6、( 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， ， ， 0 ，)T 是一个是一

7、个基本可行解基本可行解，其中其中 5=为为，则该，则该 为为基本可行解基本可行解。7第五节 线性规划问题解的概念和性质基本基本( (可行可行) )解解， 并恰有并恰有个个 分量。分量。 基本可行解基本可行解对应的对应的基基，称为称为可行基可行基； 对应的对应的基基，称为称为最优基最优基。如：如：基基 B0= ( a2 , ,a3 , ,a4 ) 对应对应 X0 = ( 0，0，8，12，36 )T 可行可行 基基 B1= ( a2 , ,a3 , ,a4 ) 对应对应 X1 = ( 0，9，8，0 )T 基基 B2 = ( a1 , ,a2 , ,a3 ) 对应对应 X2 = ( ，4，0，0

8、 )T 恰有恰有 个个分量，分量，为为可行基可行基为为基基为为最优基最优基x*x*B*8第五节 线性规划问题解的概念和性质例：例： 求线性规划问题的所有基矩阵。求线性规划问题的所有基矩阵。 5 , 1, 0226103524max53214321321jxxxxxxxxxxxxZj解解: 约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 10261001115Ar(A)=2，2阶子矩阵有阶子矩阵有10个，其中基矩阵个，其中基矩阵（不等于（不等于0）只有只有9个，即个，即 100116010211120101015061111005261161015987654321BBBBBBBBB9第五

9、节 线性规划问题解的概念和性质凸性的几个基本概念凸性的几个基本概念一一、凸集凸集 设设 En，对任意两点，对任意两点X ， ，若对满足，若对满足0 1的一切的一切实数实数 ，都有，都有 X+ +(1- - ) 则称则称 为为凸集凸集。XX 凸集凸集凸集凸集非非凸集凸集非非表示表示中两点中两点 X，连线上的任一点连线上的任一点凸集凸集的的几何意义几何意义：凸集：凸集 中任意两点中任意两点 X，连线上的点，都在凸集连线上的点，都在凸集 中。中。10第五节 线性规划问题解的概念和性质二、二、极点极点 设凸集设凸集 , , ，如果，如果 不能用不能用 中不同的两点中不同的两点 和和表示为表示为 = +

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