基本可行解(basic feasible solution)亦称可行点或允许解，是线性规划的重要概念。在线性规划问题中，满足非负约束条件的基本解，称基本可行解，简称基可行解。线性规划问题如果有可行解，则必有基可行解，可行解是基可行解的充分必要条件为：它的非零分量所对应的系数矩阵列向量是线性无关的。基本可行解与可行域中的极点相对应，为有限个。若存在有界最优解，则至少有一个基本可行解为最优解。

线性规划中的约束条件除变量非负性限制外都采用等式约束，线性规划问题的一般形式为

式中

AX=B称为约束方程，A为系数矩阵，B为常数向量，称为变量非负约束。一般情况下，应有m约束方程有无穷多组解。线性规划就是从这无穷多组解中寻找一组使目标函数值最小的最优解。

线性规划问题的约束条件包括约束方程和变量非负约束两部分，对应的解也分基本解、基本可行解和最优解。其中基本解是只满足约束方程的解；基本可行解是同时满足约束方程和变量非负约束的解。基本可行解中能使目标函数值最小的称为最优解。

约束方程实际上是一个包含n个变量和m个方程的线性方程组，若令变量中的（n—m）个变量等于零，求解方程组得到的解称为线性规划的基本解。

在一个基本解中，称这个为零的变量为非基本变量，称另外的m个变量为基本变量。

系数矩阵A和常数向量B合并组成增广矩阵：

对此增广矩阵进行一系列初等行变换，并进行m次消元，可将上述的增广矩阵和约束方程变为

由此不难看出，线性规划问题的一个基本解为

若变换后的常数项均为非负值，即，则此基本解也是一个基本可行解。

基本可行解是同时满足约束方程和变量非负约束的解。

根据线性规划问题的不同特征，一个初始基本可行解的获得可分为下列两种情况：

(1)如果除变量非负约束之外的约束条件全部是“≤”的不等式约束，而且对应的常数向量中的元素均为正数，此时只要引入松弛变量，并以松弛变量为基本变量，得到的解自然就是一个基本可行解。

(2)如果除变量非负约束之外的约束条件中还包含等式约束，此时可以在各个等式约束中分别引入一个与松弛变量类似的变量，称为人工变量，然后建立一个辅助规划问题，求解此辅助规划问题，就可以得到一个基本可行解。

基本可行解之间的相互转换采用消元法，转换时注意以下几个问题：

(1)变换后所得解的目标函数值必须下降。若下降量最大，此条件称为最优化条件。

(2)变换后仍然是一个基本可行解，即常数项的值大于等于零，此条件称为非负性条件。

(3)最优解的判断。

满足上述条件的变换，从根本上说就是要在非基本变量所对应的矩阵元素中找到一个合适的变换主元。

选定主元列的方法可概括为

式中，称为第列的判别数。

如果，对应的基本可行解就是要找的最优解。

按下式选取主元，并进行消元变换：

这样，就可以保证变换后的常数项仍为非负，保证由一个基本可行解变换得到的解仍然是一个基本可行解。