Linear programming: basic solution?
If the matrix consists of $$\begin{bmatrix}1&-2&0&0&0\\-3&6&1&3&0\\0&0&2&6&-1\end{bmatrix},$$ how is it that there are 4 basic solutions? It says that the first and second columns, as well as the third and fourth columns are scalar multiples, but what does that have to do with basic solutions?
$\endgroup$ 21 Answer
$\begingroup$Your question only makes sense to me if the matrix given is the coefficient matrix for the constraints. Let's denote that matrix $A$. Each column in $A$ corresponds to a variable. Let's suppose these are $x_1, x_2, x_3, x_4,$ and $x_5$.
There is a one-to-one correspondence between (1) bases of the column space of $A$ that consist of columns of $A$ and (2) basic solutions to the linear program. (That's why they're called basic solutions.) Since columns 1 and 2 are linearly dependent, they can't both be in a basis of the column space of $A$. Similarly for columns 3 and 4. Thus there are four bases for the column space of $A$ that can be formed by choosing columns from $A$:
- Column vectors 1, 3, and 5
- Column vectors 1, 4, and 5
- Column vectors 2, 3, and 5
- Column vectors 2, 4, and 5
This means that there are four basic solutions to the linear program; i.e., those in which the following are the basic variables:
- $\{x_1, x_3, x_5\}$
- $\{x_1, x_4, x_5\}$
- $\{x_2, x_3, x_5\}$
- $\{x_2, x_4, x_5\}$
Depending on the right-hand sides of the constraints, not all of the basic solutions may be feasible, but your question does not ask about feasibility.
$\endgroup$
