在线性规划中，基本解、基本可行解和可行解是非常重要的概念，特别是在使用单纯形法求解时。下面详细解释这些概念，并说明如何计算它们。
1. 线性规划问题的标准形式
线性规划的标准形式为：
其中：
A 是 m×n 的矩阵（m≤n）。b 是 m 维列向量。c 是 n 维列向量。x 是 n 维决策变量向量。
在标准形式中，所有约束为等式，且变量非负。
2. 基本解
定义
基本解是线性规划约束 Ax=b 的一个特殊解。若 x 是 Ax=b 的解，同时满足：
x 至多有 m 个非零分量（称为基变量）。其余 n−m 个分量固定为 0（称为非基变量）。
计算方法
从 n 个变量中选取 m 个变量作为基变量（假设它们构成矩阵的一个可逆子矩阵）。将剩余的 n−m 个变量设为 0。解方程 Ax=b ，得到对应的解 x。如果解存在，则它是一个基本解。
特点
一个基本解可能是不可行的（即 x 中有负值）。
3. 基本可行解
定义
基本可行解是满足约束 Ax=b 且 x≥0 的基本解。也就是说，基本可行解是一个非负的基本解。
计算方法
按照计算基本解的方法，先求出所有基本解。筛选出满足 x≥0 的解，这些解就是基本可行解。
特点
基本可行解是线性规划的一个重要概念，因为单纯形法的每一步都在基本可行解之间移动。一个线性规划问题可能有多个基本可行解。
4. 可行解
定义
可行解是满足所有约束条件的解：
Ax=b , x≥0
计算方法
与基本解或基本可行解不同，可行解不需要有特定数量的零元素。直接检查解是否满足约束 Ax=b 和 x≥0 即可。
特点
可行解的集合构成一个凸集，即若 和 是可行解，则任意 的凸组合 也是可行解。基本可行解是可行解的一个子集。
5. 关系总结
基本解：满足 Ax=b 且至多有 m 个非零分量。基本可行解：满足 Ax=b 、x≥0 ，且是一个基本解。可行解：满足 Ax=b ，但不要求是基本解。
6. 示例
问题
考虑以下线性规划问题：
基本解
将 ，b=4 。共有两个变量（n=2），但只有一个等式约束（m=1）。至多有 m=1 个非零变量：
令 ，解 ，得到基本解 。令 ，解 ，得到基本解 。
基本可行解
上述两个基本解 和 都满足非负性条件 x≥0 ，因此它们是基本可行解。
可行解
可行解的集合为满足约束 且 的所有 x ，即位于直线 且第一象限内的所有点。
7. 如何计算基本解、基本可行解和可行解？
步骤 1：将问题标准化
确保问题为标准形式 Ax=b , x≥0 。
步骤 2：枚举所有基本解
从 n 个变量中选择 m 个变量作为基变量。将其余 n−m 个变量置为 0。解方程 Ax=b ，得到一个基本解。
步骤 3：筛选基本可行解
检查基本解是否满足 x≥0 。满足的即为基本可行解。
步骤 4：检查可行解
直接验证解是否满足 Ax=b 和 x≥0 。如果问题是连续的，可以用几何方法描述可行解的范围。
8. 总结
基本解：通过选取 m 个基变量并解 Ax=b 得到的解，但可能不满足非负性。基本可行解：基本解中满足 x≥0 的解。可行解：满足 Ax=b 和 x≥0 的所有解。