Basic Terminologies in Linear Programming: Feasible Solutions, BFS and an Optimal Solution Worked Step by Step

A point can satisfy every constraint without being a basic feasible solution (BFS), while a BFS can still fail to maximise or minimise the objective. That is why memorising “corner point” is not enough. Within broader GATE CS Exam Preparation, the hierarchy becomes concrete: geometry identifies feasible vertices, standard-form algebra tests whether a solution is basic, and objective values decide optimality.

Related reading: assignment optimisation and constrained knapsack optimisation.

Linear programming terminology starts with the model, not the corner points

An LP has decision variables, a linear objective, linear constraints and sign restrictions. Consider the following model:

• Maximise Z = 3x + 2y

• Subject to x + y <= 4, x <= 2, y <= 3

• With x, y >= 0

A solution is simply an assignment of values to x and y. It becomes a feasible solution only when it satisfies every constraint. For (1,1), we get 1 + 1 <= 4, 1 <= 2 and 1 <= 3, so the point is feasible. At (2,3), the individual bounds hold, but 2 + 3 = 5 > 4, so the point is infeasible.

Keep the hierarchy clear: every optimal solution is feasible, a BFS is a feasible basic solution, and a feasible solution need not be basic.

Feasible region and extreme points give the geometric meaning of a BFS

Draw x + y = 4, x = 2, y = 3, x = 0 and y = 0. The feasible region is the intersection of their allowed sets. Set Theory and Relations Explained for GATE is an optional notation refresher.

In order, the polygon vertices are (0,0), (2,0), (2,2), (1,3) and (0,3). The point (1,1) is feasible but interior. The point (1,0) is on an edge. Neither is a vertex. At (2,2), x = 2 and x + y = 4 are active, producing an extreme point. Here the feasible extreme points correspond to BFS points after standard-form conversion.

Basic solution and basic feasible solution in standard form

Introduce one slack variable for each <= constraint:

x + y + s1 = 4, x + s2 = 2, y + s3 = 3, with x, y, s1, s2, s3 >= 0.

With three independent equations, choose three linearly independent columns as a basis, set the other two variables to zero, and solve for the basic variables.

Choose {x, y, s3} as basic and set s1 = s2 = 0. The equations give x = 2, y = 4 - 2 = 2 and s3 = 3 - 2 = 1. Thus (x,y,s1,s2,s3) = (2,2,0,0,1). Every entry is nonnegative, so this is a BFS.

Set x = s1 = 0 with basis {y,s2,s3}. This gives (0,4,0,2,-1), basic but not feasible because s3 = -1. At (1,1), the vector (1,1,2,1,2) has no zero variable, so it cannot have two nonbasic variables set to zero.

Linear programming worked example: enumerate every BFS and find the optimum

The slack values are s1 = 4 - x - y, s2 = 2 - x and s3 = 3 - y. Evaluate them and the objective at every feasible vertex:

The procedure is:

1. Find intersections of the boundary lines.

2. Reject any intersection outside even one constraint.

3. Record the remaining extreme points.

4. Substitute each point into Z = 3x + 2y.

5. Compare the objective values 0, 6, 10, 9, 6.

The maximum is Z = 10 at (2,2). Feasibility comes before optimisation because an infeasible point proves nothing.

To verify uniqueness, slide 3x + 2y = k towards increasing k. At k = 10, it touches the polygon only at (2,2), and no feasible edge lies along it. This model has a unique optimal BFS, but not every LP does.

Degenerate BFS, alternate optima, infeasible LP and unbounded LP

Degeneracy means a basic variable is zero. Consider x + y <= 2, x <= 1, y <= 1, with x,y >= 0. At (1,1), all three inequalities are active and the standard-form vector is (1,1,0,0,0). The valid basis {x,y,s1} has basic variable s1 = 0, so this BFS is degenerate. It remains feasible, and several bases can represent one vertex.

Three short counterexamples separate other edge cases:

• Alternate optima: maximise x + y subject to x + y <= 4 and x,y >= 0. Every point from (4,0) to (0,4) has value 4.

• Infeasible LP: x + y <= -1 and x,y >= 0 cannot hold together.

• Unbounded LP: maximise 2x + y subject to x - 2y = 0 and x,y >= 0. For every t >= 0, (2t,t) is feasible and gives Z = 5t, which has no finite upper limit.

Linear programming terminology traps students should avoid

Here BFS means Basic Feasible Solution, not breadth-first search. A polygon vertex is geometric, not a graph-theory vertex. For that separate usage, see Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.

How exams test feasible solutions, BFS and optimal solutions

Typical questions ask you to check a point, identify active constraints, add slack variables, test a basic solution, count BFS points or recognise degeneracy. Longer problems may ask for the optimum, alternate optima, infeasibility or unboundedness.

The main model yields three quick checks:

• (1,1) is feasible but not a BFS.

• (1,3) is a BFS with Z = 9 but is not optimal.

• (2,3) is infeasible.

Use the order constraints -> nonnegativity -> active constraints or basis -> objective value. It prevents you from optimising a rejected point. The GATE Test Series offers broader timed practice, including Engineering Mathematics tests, if you want to build exam speed on top of this drill.

Basic linear programming terminology: the short version and next step

A solution assigns values. A feasible solution obeys every constraint. A basic solution comes from a basis. A BFS is a nonnegative basic solution and appears as a feasible vertex. An optimal solution gives the best objective value among all feasible solutions.

Use Engineering Mathematics for GATE Exam to shore up the adjacent mathematical foundations this topic leans on. For your next step, set y = s1 = 0, take {x,s2,s3} as the basis, and explain why (4,0,0,-2,3) is basic but infeasible.