Why do we identify basic feasible solutions in linear programming before solving?

Answer First

We identify basic feasible solutions because the simplex method must start at a BFS and can only move between BFSs. Without identifying them, the algorithm cannot begin.

BFSs are the only candidates for optimality, so identifying them dramatically reduces the search space from infinitely many points to a finite set of corner points.

• BFS = starting point for simplex
• BFS = corner points where optimal solutions occur
• BFS = feasible solutions defined by active constraints

Step-by-Step: Why BFS Identification Matters

Step 1: Standard Form Creates a Structure

A standard form LP:

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

has m constraints and n variables. A basic solution selects m variables and sets the rest to zero.

Step 2: BFS = Intersection of Active Constraints

A BFS corresponds to a point where exactly m constraints bind. This is the definition of a vertex of a polyhedron.

Step 3: Simplex Requires a BFS to Start

Simplex cannot begin at an interior point — it needs a corner. Identifying BFSs ensures the algorithm has a valid starting point.

Step 4: Only BFSs Can Be Optimal

The Fundamental Theorem of Linear Programming states:

\[ \text{If an optimal solution exists, at least one BFS is optimal.} \]

Thus, identifying BFSs narrows the search to the only points that matter.

Step 5: BFS Identification Helps Detect Issues

By examining BFSs, we can detect:

• infeasibility
• degeneracy
• multiple optimal solutions
• unboundedness

Numerical Example

Maximize:

\[ z = 3x + 2y \]

Subject to:

\[ x + y \le 6 \]

\[ x \le 4 \]

\[ y \le 5 \]

\[ x, y \ge 0 \]

Step 1: Identify Corner Points (BFSs)

• (0,0)
• (4,0)
• (4,2)
• (1,5)
• (0,5)

Step 2: Evaluate Objective

• z(0,0)=0
• z(4,0)=12
• z(4,2)=16
• z(1,5)=13
• z(0,5)=10

Step 3: Choose Maximum

The optimal solution is (4,2) with z = 16 — a BFS.