《线性规划问题的基本解课件.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的基本解课件.ppt（18页珍藏版）》请在三一办公上搜索。
1、3.2 线性规划问题的基本解,基本概念： 可行解、可行域、最优解、基、基变量、基阵、基本可行解,给定一个线性规划问题LP,一、基本概念：,1、可行解 (a feasible solution),满足约束条件的X称为线性规划问题的可行解;,所有可行解的集合称为可行域 (feasible region),使目标函数(1.1)达到最大值的可行解称为最优解(an optimal solution)。,2、基(base),即,是A的m个列向量,设,是线性无关的，,如果,则称,为基向量。,记约束方程系数矩阵A的列向量是,3、基变量(basic variables),构成线性规划问题的一组基向量,设,则对应
2、的变量,称为基变量，,其余的向量称为非基向量，其余的变量称为非基变量(non-basic-variable)，,称为基或基阵(basic matrix)。,矩阵,约束方程A的系数矩阵为：,分别是变量,的系数向量。,例1,向量组 是线性无关组,是此问题的一个基,其中 为基变量，而 是非基变量。,向量组 是线性无关组,是基变量，,是此问题的一个基,而 是非基变量。,（2）设B是A的一个m阶子矩阵，则B是线性规划问题的基阵，当且仅当B是可逆阵,（3）基的个数Cnm,注：（1）基不一定唯一,4、基解,现令所有的非基变量都等于0，即,设 是线性规划问题LP的一基阵，,表示基变量向量，,表示非基变量向量。
3、,则约束方程(1.2)可化为：,它是一个m个变量m个方程组成的线性方程组，B又是可逆阵，从而得出(1.4)的唯一解,得出约束方程(1.2)至少含有n-m个0元的解,称之为相应于基B的一个基本解或基解(a basic solution)。,5、基可行解,设 是对应于基阵B的一个基解，,如果,则称 为一个基本可行解或基可行解.,(a basic feasible solution)；,相应的基B也称为可行基(feasible base)。,在上例1中，对应于 的基解为是一个基可行解，对应于 的基解为而不是基可行解。,思考题：试列出例1中问题的所有基解、基可行解。,注：给定线性规划问题LP，其基可行
4、解的数目是有限个，不会超过 。 图1给出了线性规划问题的解的关系。,图1,非可行解,1.设线性规划,取基,分别指出,对应的基变量和非基变量，,是不是可行基,求出基本解，并说明,1若线性规划无最优解则其可行域无界。（ ）2凡基本解一定是可行解。 （ ）,2判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。）,3线性规划的最优解一定是基本最优解。（ ）4线性规划的最优解是可行解。（ ）5可行解是基本解。（ ）,3.线性规划可行域的顶点一定是（ ）。A.基本可行解B.非基本解C.非可行解D.最优解4. X是线性规划的基本可行解，则有（ ）。A. X中的基变量非零，非基变量为零B. X不一定满足约束条件C. X中的基变量非负，非基变量为零D. X是最优解,
