(2.4.1)--02_4线性规划问题各种解的概念及关系.pdf

《(2.4.1)--02_4线性规划问题各种解的概念及关系.pdf》由会员分享，可在线阅读，更多相关《(2.4.1)--02_4线性规划问题各种解的概念及关系.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1.4 线性规划问题的解的概念1.可行解可行解 满足约束条件（包括非负条件）的一组变量值，称可行解。所有可行解的集合称为可行域。最优解 使目标函数达到最大的可行解称为最优解。标准型有n个变量，m 个约束行2.基“基”的概念：设A是约束方程组mn维(mn)的系数矩阵，其秩为m，B是矩阵A中mm阶非奇异子矩阵（B的行列式B0），则称B是线性规划问题的一个基。最多有个基基有：B1，B2，B3B4不是方程的基设B（P1，P2，Pm）称Pj（j1,2,，m）为基向量。它们是一个线性无关的向量组，与基向量对应的变量Xj（j1,2,，m）称为基变量。其他变量就称为非基变量。基向量、基变量：约束方程可改写

2、为：B1中P3=（1，0，0），P4=（0，1，0）P5=（0，0，1）对应基变量为：x3，x4，x5非基变量为：x1，x2=（P3，P4，P5）复习 线性方程组如果有解,那么当系数矩阵A的秩r=n(变量的个数),有唯一解,当rn,有无穷多组解.3、基解、基可行解、可行基：基解 对于有n个变量、m个约束方程的标准型线性规划问题，取其m个变量。若这些变量在约束方程中的系数列向量线性无关，则它们组成一组基变量。确定了一组基变量后，其它n-m个变量称为非基变量。令方程组的基是B，设XB是对应于这个基的基变量，XB=（x1，x2，xm）T,若令上式的非基变量xm1xm2xn0，约束方程变成m元一次方程：=BjBB0可以求出一个解：X=（x1，x2，xm，0，0）T称X为基解。n-m一个基本解的非零分量个数不超过m个。基础可行解的非零分量个数 m时，称为退化解若满足非负约束条件的基解。称为基可行解。对应于基可行解的基，称为可行基。当基可行解为最优解时,对应的基称最优基。注意:基可行解的数目和基解的数目上限示例:对于(LP)问题：基可行解可行基是基解不是可行解线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解退化解