A basic solution is a type of solution for a system of linear equations, while a basic feasible solution adds the crucial requirement of non-negativity.
Understanding Basic Solutions
According to reference (1), a solution x of Ax = b is called a basic solution if the vectors {ai : xi ≠ 0} are linearly independent. This means that when you look at the columns of the matrix A that correspond to the variables (xᵢ) which are not zero in the solution vector x, these columns must be linearly independent.
- Consider a system of linear equations represented by Ax = b.
- A solution 'x' is a set of values for the variables that satisfies these equations.
- For a solution to be classified as basic, the subset of variables that are non-zero must correspond to linearly independent columns in the matrix A.
- Variables that are set to zero in a basic solution are often referred to as non-basic variables.
- Variables that are non-zero are often referred to as basic variables.
What is a Basic Feasible Solution (BFS)?
Reference (2) defines a basic solution satisfying x ≥ 0 as a basic feasible solution (BFS). This builds directly upon the definition of a basic solution by adding the constraint that all components of the solution vector x must be non-negative.
- A BFS must first meet the criteria of a basic solution (linear independence of columns corresponding to non-zero variables).
- Additionally, every variable value in the solution (xᵢ) must be greater than or equal to zero (xᵢ ≥ 0 for all i).
BFS are particularly important in linear programming because, for problems with a feasible region defined by linear constraints, optimal solutions often occur at the "corners" or vertices of this region, and these vertices correspond to Basic Feasible Solutions.
Basic Solution vs. Basic Feasible Solution
Here's a simple comparison based on the provided definitions:
| Feature | Basic Solution | Basic Feasible Solution (BFS) |
|---|---|---|
| Core Requirement | Solution to Ax = b | Solution to Ax = b |
| Linear Indep. | Columns of A corresponding to non-zero variables are linearly independent. | Columns of A corresponding to non-zero variables are linearly independent. |
| Non-negativity | No requirement (variables can be positive, negative, or zero). | All variables must be greater than or equal to zero (x ≥ 0). |
| Relevance (LP) | Intermediate step, not necessarily useful for optimization on its own. | Represents vertices of the feasible region; candidates for optimal solutions. |
Understanding these two concepts is fundamental to solving linear programming problems, particularly when using algorithms like the Simplex method, which navigates through basic feasible solutions to find an optimal one.
