3.1. Basic Solutions and Basic Feasible Solutions

A vector \(\hat z\) is called a basic solution of the LP \(P\)

\[\begin{gathered} \text{Maximize } cz + d\\ \begin{aligned} \text{s.t. } b &= Az\\ z &\ge 0 \end{aligned} \end{gathered}\]

with basis \(B = (j_1, \ldots, j_m)\) if \(b = A\hat z\) and \(\hat z_j = 0\) for all \(j \notin B\). In other words, only basic variables can be non-zero in a basic solution.

Since the LP is in standard form, we have \(c_j = 0\) for all \(j \in B\), so the requirement that \(\hat z_j = 0\) for all \(j \notin B\) implies that the objective function value of a basic solution is \(c\hat z + d = d\).

Since \(a_{ij_i} = 1\) and \(a_{ij} = 0\) for all \(j \in B \setminus \{j_i\}\), we also have

\[b_i = \hat z_{j_i} + \sum_{j \notin B} a_{ij}\hat z_{j} = \hat z_{j_i}\]

for all \(1 \le i \le m\). Thus,

Every LP has exactly one basic solution \(\hat z\) defined as

\[\hat z_j = \begin{cases} b_i & \text{if } j = j_i \in B\\ 0 & \text{if } j \notin B, \end{cases}\]

and we call it the basic solution of the LP.

Since \(\hat z_{j_i} = b_i\) for all \(1 \le i \le m\), and \(z_j = 0\) for all \(j \notin B\), we have \(\hat z \ge 0\) if and only if \(b \ge 0\).

If the basic solution \(\hat z\) of an LP \(P\) satisfies \(\hat z \ge 0\), then \(\hat z\) is a feasible solution of \(P\), and we call it the basic feasible solution (BFS) of \(P\).

If \(z_{j_i} = b_i < 0\) for some \(1 \le i \le m\), then \(\hat z\) is not feasible. In this case, \(P\) has no BFS (because it has exactly one basic solution, which is not feasible).

You may wonder how \(\hat z\) can be a "solution" of \(P\) if it isn't feasible, that is, if it doesn't satisfy all constraints of \(P\). Throughout this chapter, we refer to \(\hat z\) as a solution of \(P\) if it satisfies \(A\hat z = b\). It is a feasible solution if additionally, \(\hat z \ge 0\). So, "solution" refers to a solution of the system of linear equations \(Az = b\), while "feasibility" refers to the non-negativity of all variables. This then extends naturally to the distinction between a basic solution and a basic feasible solution.

Observation 3.1: Two equivalent LPs in standard form have the same set of solutions, not only the same set of feasible solutions, and they assign the same objective function value to any solution.