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 $$


You need to check the reduced costs. The basis is optimal if the reduced costs are negative (for a maximization problem).

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.

  • $\begingroup$ Okay, and the formula of the reduced cost is $\tilde c_j=c_j -\sum a_{ij}y_i$ $\endgroup$ – Revolucion for Monica Mar 9 '16 at 6:38
  • $\begingroup$ 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? $\endgroup$ – Revolucion for Monica Mar 9 '16 at 6:44
  • $\begingroup$ The formulate of reduced costs is $c_j-\sum_{i\in B}c_ia_{ij}$, where $B$ is the basis. $\endgroup$ – Kuifje Mar 9 '16 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.