2
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Okay, and the formula of the reduced cost is $\tilde c_j=c_j -\sum a_{ij}y_i$ $\endgroup$ Mar 9, 2016 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$ Mar 9, 2016 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, 2016 at 13:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .