Basic Solution¶

Definition¶

For $m$ independent linear equality constraints in $n$ variables, a basic solution is obtained by choosing $n-m$ variables to be nonbasic and setting them to zero, then uniquely solving for the other $m$ variables.

Interpretation¶

A basic solution is what one obtains by deciding in advance which variables are zero and solving the equations for the rest. In a two-variable LP each such choice picks two boundary lines, and the basic solution is their intersection point, a candidate for a corner of the feasible region.

The same feasible pentagon with five intersection points labelled by the two variables set to zero there; three are corners of the region and two lie outside it and are infeasible.

Each labelled point is named by its two zero variables. A zero slack places the point on that constraint's boundary line, and a zero decision variable places it on an axis. So $s_1=s_2=0$ is the intersection $(20,60)$ of the lines $2x_s+x_t=100$ and $x_s+x_t=80$ $80$ , while $x_t=s_1=0$ gives $(50,0)$ , which lies outside the region.

With $m$ equations in $n$ variables, setting $n-m$ variables to zero leaves $m$ equations in $m$ unknowns. The choice gives a basic solution only if this smaller system has exactly one solution. In the Giapetto system, setting $x_s=s_3=0$ turns the third equation into $0=40$ $40$ ; geometrically, the lines $x_s=0$ and $x_s=40$ are parallel and never meet. Of the ten choices of two zero variables, nine therefore give a basic solution.

Only some basic solutions are feasible, as the table in the Examples shows; those with all values nonnegative are the basic feasible solutions that the simplex method moves between. The equation system itself comes from the augmented form, which adds slack or surplus variables to the inequalities.

Key Results¶

There are at most $\binom{n}{m}$ basis choices.
A basic solution may be feasible or infeasible.
Different bases can represent the same degenerate solution.

Examples¶

The illustrated system has $m=3$ equations and $n=5$ variables:

\begin{aligned} 2x_s+x_t+s_1&=100,\\ x_s+x_t+s_2&=80,\\ x_s+s_3&=40. \end{aligned}

Setting two nonbasic variables to zero gives the following basic solutions. The nonnegative solutions are corners of the shaded feasible region; negative slack values identify the red, infeasible points.

Variables set to zero	$(x_s,x_t)$	$(s_1,s_2,s_3)$	Feasible?
$x_s,x_t$	$(0,0)$	$(100,80,40)$	Yes
$s_1,s_2$	$(20,60)$	$(0,0,20)$	Yes
$x_t,s_3$	$(40,0)$	$(20,40,0)$	Yes
$s_2,s_3$	$(40,40)$	$(-20,0,0)$	No
$x_t,s_1$	$(50,0)$	$(0,30,-10)$	No

There are at most $\binom53=10$ basis choices for this system. The figure shows five of their corresponding basic solutions.

The four-variable example has at most $\binom42=6$ bases.
Week 2 practice 4 has five variables and two equalities, but only eight basic solutions from ten candidate choices.

Prerequisites¶

Augmented Form

Sources¶

OR Modelling · Week 2

Last updated: 20 October 2026 03:02