Basic Feasible Solution Problems

Basic feasible solution problems ask you to use a basis matrix to construct or verify a feasible vertex of the standard-form polyhedron.

Standard-Form Setting

Start from:

\[\min c^Tx\]

subject to:

\[Ax=b, \qquad x\ge 0,\]

where $A\in\mathbb{R}^{m\times n}$.

Basis Matrix

Choose $m$ linearly independent columns of $A$:

\[B=[A_{B(1)}\ A_{B(2)}\ \cdots\ A_{B(m)}].\]

The variables corresponding to these columns are basic variables.

Compute the Basic Solution

Set all nonbasic variables to zero:

\[x_N=0.\]

Solve:

\[x_B=B^{-1}b.\]

Then assemble the full vector $x$.

Feasibility Test

The basic solution is feasible if:

\[x_B\ge 0.\]

If any basic variable is negative, it is a basic solution but not a basic feasible solution.

Verifying a Given Vector

To verify a given vector $\bar x$:

  1. check $A\bar x=b$
  2. check $\bar x\ge 0$
  3. identify positive/basic candidate variables
  4. check whether the corresponding columns form a basis
  5. if yes, $\bar x$ is a BFS

Degeneracy

A BFS is degenerate if at least one basic variable is zero.

Equivalently, fewer than $m$ variables may be positive even though $m$ variables are basic.

Checklist

For exam answers, always state the basis, compute $B^{-1}b$, and explicitly conclude feasible or not feasible.

See Also

Added drill source

Use BFS and Reduced Cost Drill Set and Verifying a Given Vector as BFS.

Exam checkpoint

Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.