3.2线性规划问题的基本解.pptVIP

给定一个线性规划问题LP 1、可行解 (a feasible solution) 满足约束条件的X称为线性规划问题的可行解; 3、基变量(basic variables) 构成线性规划问题的一组基向量, 约束方程A的系数矩阵为： 5、基可行解 设 是对应于基阵B的一个基解， * 3.2 线性规划问题的基本解 基本概念： 可行解、可行域、最优解、基、基变量、基阵、基本可行解 一、基本概念： 所有可行解的集合称为可行域 (feasible region), 使目标函数(1.1)达到最大值的可行解称为最优解(an optimal solution)。 2、基(base) 即 是A的m个列向量, 设 是线性无关的， 如果 则称 为基向量。 记约束方程系数矩阵A的列向量是 设 则对应的变量 称为基变量， 其余的向量称为非基向量，其余的变量称为非基变量 (non-basic-variable)， 称为基或基阵(basic matrix)。 矩阵 分别是变量 的系数向量。 例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)。 如果 则称 为一个基本可行解或基可行解. (a basic feasible solution)； 相应的基B也称为可行基(feasible base)。