线性规划问题的基本解课件.ppt

3.2 线性规划问题的基本解基本概念：可行解、可行域、最优解、基、基变量、基阵、基本可行解给定一个线性规划问题LP一、基本概念：1、可行解(a feasible solution)满足约束条件的X称为线性规划问题的可行解;所有可行解的集合称为可行域(feasible region),使目标函数(1.1)达到最大值的可行解称为最优解(an optimal solution)。2、基、基(base)即是A的m个列向量,设是线性无关的，如果则称为基向量。记约束方程系数矩阵A的列向量是3、基变量(basic variables)构成线性规划问题的一组基向量,设则对应的变量 称为基变量，其余的向量称为非基向量，其余的变量称为非基变量(non-basic-variable)，称为基或基阵(basic matrix)。矩阵约束方程A的系数矩阵为：分别是变量的系数向量。例例1向量组 是线性无关组是此问题的一个基其中 为基变量，而 是非基变量。向量组 是线性无关组 是基变量，是此问题的一个基而 是非基变量。（2）设B是A的一个m阶子矩阵，则B是线性规划问题的基阵，当且仅当B是可逆阵 （3）基的个数Cnm注：（1）基不一定唯一4、基解 现令所有的非基变量都等于0，即设 是线性规划问题LP的一基阵，表示基变量向量，表示非基变量向量。则约束方程(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，其基可行解的数目是有限个，不会超过 。图1给出了线性规划问题的解的关系。可行解基解基可行解图1非可行解1.设线性规划取基分别指出对应的基变量和非基变量，是不是可行基求出基本解，并说明1若线性规划无最优解则其可行域无界。（）2凡基本解一定是可行解。（）2判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。）3线性规划的最优解一定是基本最优解。（）4线性规划的最优解是可行解。（）5可行解是基本解。（）3.线性规划可行域的顶点一定是（）。A.基本可行解B.非基本解C.非可行解D.最优解4.X是线性规划的基本可行解，则有（）。A.X中的基变量非零，非基变量为零B.X不一定满足约束条件C.X中的基变量非负，非基变量为零D.X是最优解