基本可行解(basic feasible solution)亦称 可行点 或 允许解 ，是线性规划的重要概念。在 线性规划问题 中，满足非负约束条件的基本解，称 基本可行解 ，简称 基可行解 。线性规划问题如果有可行解，则必有基可行解，可行解是基可行解的充分必要条件为：它的非零分量所对应的系数矩阵列向量是线性无关的。基本可行解与可行域中的极点相对应，为有限个。若存在有界最优解，则至少有一个基本可行解为最优解。
基本介绍
中文名 ：基本可行解 外文名 ：basic feasible solution 所属领域 ：运筹学（线性规划问题） 相关概念 ：基本解、非负约束、线性无关等 别称 ：可行点或允许解
基本介绍,基本解的产生和转换,基本可行解的产生与转换条件,基本可行解转换的最优性条件,基本可行解转换的非负性条件,
基本介绍
线性规划中的约束条件除变数非负性限制外都采用等式约束，
线性规划问题的一般形式 为 式中
AX =
B 称为约束方程，
A 为系数矩阵，
B 为常数向量， 称为变数非负约束。一般情况下，应有m<n。此时约束方程有无穷多组解。线性规划就是从这无穷多组解中寻找一组使
目标函式 值最小的最优解。 线性规划问题的
约束条件 包括约束方程和变数非负约束两部分，对应的解也分基本解、基本可行解和最优解。其中
基本解 是只满足约束方程的解；
基本可行解 是同时满足约束方程和变数非负约束的解。基本可行解中能使目标函式值最小的称为
最优解 。
基本解的产生和转换
约束方程实际上是一个包含n个变数和m个方程的线性方程组，若令变数中的n—m个等于零，求解方程组得到的解称为线性规划的基本解。 在一个基本解中，称这 个为零的变数为非基本变数，称另外的m个变数为基本变数。 系数矩阵
A 和常数向量
B 合并组成增广矩阵： 对此增广矩阵进行一系列初等行变换，并进行m次消元，可将上述的增广矩阵和约束方程变为 由此不难看出，线性规划问题的一个基本解为 若变换后的常数项均为非负值，即 ，则此基本解也是一个基本可行解。
基本可行解的产生与转换条件
基本可行解是同时满足约束方程和变数非负约束的解。 根据线性规划问题的不同特征，一个初始基本可行解的获得可分为下列两种情况： (1)如果除变数非负约束之外的约束条件全部是“≤”的不等式约束，而且对应的常数向量中的元素均为正数，此时只要引入松弛变数，并以松弛变数为基本变数，得到的解自然就是一个基本可行解。 (2)如果除变数非负约束之外的约束条件中还包含等式约束，此时可以在各个等式约束中分别引入一个与松弛变数类似的变数，称为人工变数，然后建立一个辅助规划问题，求解此辅助规划问题，就可以得到一个基本可行解。 基本可行解之间的相互转换采用消元法，转换时注意以下几个问题： (1)变换后所得解的目标函式值必须下降。若下降量最大，此条件称为
最最佳化条件 。 (2)变换后仍然是一个基本可行解，即常数项的值大于等于零，此条件称为
非负性条件 。 (3)最优解的判断。 满足上述条件的变换，从根本上说就是要在非基本变数所对应的矩阵元素中找到一个合适的变换主元 。
基本可行解转换的最优性条件
选定主元列的方法可概括为 式中， 称为第 列的判别数。 如果 ，对应的基本可行解就是要找的最优解。
基本可行解转换的非负性条件
按下式选取主元，并进行消元变换： 这样，就可以保证变换后的常数项仍为非负，保证由一个基本可行解变换得到的解仍然是一个基本可行解。