# Optimal basis in linear programming

Given the following linear program:

\begin{cases} \max &5x_1 + x_2 + 6x_3 + 2x_4\\ &4x_1 + 4x_2 + 4 x_3 + x_4\le 24\\ &8x_1 + 6x_2 + 4x_3 + 3x_4\le 36\\ &\forall i, x_i\ge 0 \end{cases}

How to know if the basis $B=\{3,4\}$ is an optimal basis?

I only found that it is a feasible basis as far as first

$$B= \begin{pmatrix} 4 & 1\\ 4 & 3 \end{pmatrix}$$

is invertible becasuse $\det B =8 \neq 0$. And second because:

$$B^{-1}b= \frac{1}{8} \begin{pmatrix} 3/8 & 1/8\\ -1/2 & 1/2 \end{pmatrix} \begin{pmatrix} 24\\36 \end{pmatrix}\ge 0$$

The basis is $\{3,4\}$, so the non basic variables are $x_1$ and $x_2$.
$x_1$ has reduced cost $$c_1-z_1=5-6(3/64)-2(-1/16) = 155/32 >0,$$ so if $x_1$ enters the basis, the objective function will increase by $155/32$ for every unit of $x_1$: the basis $\{3,4\}$ is not optimal.
• Okay, and the formula of the reduced cost is $\tilde c_j=c_j -\sum a_{ij}y_i$ Mar 9, 2016 at 6:38
• Thank you for this answer! So isn't it $=5-(4*24 +4*36+24+3*36)$, with the sum of the basic variables multiplied by the "shadow prices" on the right? Mar 9, 2016 at 6:44
• The formulate of reduced costs is $c_j-\sum_{i\in B}c_ia_{ij}$, where $B$ is the basis. Mar 9, 2016 at 13:44