If you’re working through Linear Programming & Optimization tutoring, you’ll keep hearing the same rule: the simplex method searches corner points. That’s not a slogan — it’s built into the algebra of basic feasible solutions (BFS).
In practice, this shows up in Business Analytics tutoring and operations research courses when you’re asked to identify a starting solution, interpret a tableau, or explain why simplex moves “vertex to vertex.” If you want a tutor to check your setup or simplex steps, use the main tutoring services page and send the problem.
What Is a Basic Feasible Solution in Linear Programming?
A basic feasible solution (BFS) is a feasible point obtained by selecting a set of basic variables (as many as the number of constraints), setting all other variables to zero, and solving \(Ax=b\). If the resulting solution satisfies \(x \ge 0\), it is feasible — and it corresponds to a corner point (vertex) of the feasible region.
“Basic” refers to choosing a basis (a square, invertible set of columns in the constraint matrix). “Feasible” means it satisfies all constraints and nonnegativity.
A basic feasible solution occurs where independent constraints intersect — at a corner.
Why Are Basic Feasible Solutions Corner Points?
The feasible set of an LP is an intersection of half-spaces, so it forms a convex polyhedron. A corner point (vertex) is where enough constraints bind simultaneously to “pin down” a unique intersection.
In standard form,
\[ Ax=b,\quad x\ge 0 \]
pick a set of columns \(B\) (a basis) and partition variables into \(x_B\) (basic) and \(x_N\) (nonbasic). Setting \(x_N=0\) forces the solution to lie on the intersection of constraint boundaries. Solving gives:
\[ x_B = B^{-1}b,\quad x_N=0 \]
If \(x_B \ge 0\), then the solution is feasible. Geometrically, you have moved onto the boundary by forcing some variables to zero and binding enough constraints to land at a vertex. That is exactly why simplex can move from BFS to BFS: each BFS is a corner point.
How to Find Basic Feasible Solutions
Method A: From Standard Form \(Ax=b,\, x\ge 0\)
- Put the LP in standard form. Use slack variables for “\(\le\)” constraints (and other conversions if needed).
- Choose a basis \(B\). Pick as many columns as constraints so \(B\) is invertible.
- Set nonbasic variables to zero. \(x_N=0\).
- Solve \(x_B = B^{-1}b\).
- Check feasibility. If \(x_B \ge 0\), you found a BFS. If any basic variable is negative, it’s a basic solution but not feasible.
Method B: In 2D (Quick Corner-Point Check)
- Find intersections of binding constraint lines (including axes).
- Keep only points that satisfy all inequalities.
- Those feasible intersections are the corner points — i.e., BFS candidates.
Numerical Example: BFS and Corner Points Match
Maximize:
\[ z = 3x + 2y \]
Subject to:
\[ x + y \le 4 \]
\[ x \le 3 \]
\[ x \ge 0,\quad y \ge 0 \]
Step 1: Convert to Standard Form
Add slack variables \(s_1, s_2 \ge 0\):
\[ x + y + s_1 = 4 \]
\[ x + s_2 = 3 \]
Step 2: Pick a Basis and Compute a Basic Solution
Use \((s_1, s_2)\) as basic variables and set nonbasic variables \(x=y=0\).
\[ s_1 = 4,\quad s_2 = 3 \]
This is feasible (\(s_1,s_2\ge 0\)), so it is a BFS. In \((x,y)\)-space, it corresponds to the corner point \((0,0)\).
Step 3: Another BFS by Changing Which Variables Are Nonbasic
Set \(y=0\) and \(s_2=0\). Then from \(x + s_2 = 3\) we get \(x=3\). Plug into the first constraint:
\[ 3 + 0 + s_1 = 4 \Rightarrow s_1 = 1 \]
All variables are nonnegative, so this is a BFS. In \((x,y)\)-space, it is the corner point \((3,0)\).
Step 4: Corner Point Where Two Constraints Bind
If \(x=3\) and \(x+y=4\), then \(y=1\). This is another corner point \((3,1)\) and corresponds to a BFS (with \(s_2=0\) and \(s_1=0\)).
Common Mistakes
- Mixing up “feasible” and “basic feasible.” Many feasible points exist on edges, but only vertices correspond to BFS.
- Forgetting nonnegativity. A basic solution with any negative component is not feasible.
- Assuming every intersection is feasible. Intersections must satisfy all inequalities (including \(x\ge 0, y\ge 0\)).
- Confusing degeneracy with “not a BFS.” A degenerate BFS is still a BFS; it just has a basic variable equal to zero.
Why This Matters
The simplex method works because it only needs to evaluate a finite set of candidates: the basic feasible solutions. It moves from one BFS to another by pivoting the basis, which is the algebraic version of moving along edges to a new corner point.
This perspective also matters in applied optimization models used in Inventory & Supply Chain and Decision Analysis, where you must justify why checking vertices (or simplex pivots) is sufficient.
Related Topics
This idea connects directly to:
Speak Directly to a Tutor — Send Your Message Below
No call centers. No delays. Your message goes straight to the tutor.
- Call/Text: 510-398-0006
- Email: tutor@californiagraduatetutor.com
- WhatsApp: Send Files