Optimal basis in linear programming

Question

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

score 4 · Accepted Answer · answered Mar 08 '16 at 23:39

4

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.

answered Mar 08 '16 at 23:39

Kuifje

9,584

Okay, and the formula of the reduced cost is $\tilde c_j=c_j -\sum a_{ij}y_i$ – Revolucion for Monica Mar 09 '16 at 06:38
Thank you for this answer! So isn't it $=5-(424 +436+24+3*36)$, with the sum of the basic variables multiplied by the "shadow prices" on the right? – Revolucion for Monica Mar 09 '16 at 06:44
The formulate of reduced costs is $c_j-\sum_{i\in B}c_ia_{ij}$, where $B$ is the basis. – Kuifje Mar 09 '16 at 13:44

Optimal basis in linear programming

1 Answers1