4
$\begingroup$

(This is NOT a homework question, I am reviewing for my upcoming exam)

Given this linear program:

enter image description here

and this optimal tableau:

enter image description here

I am attempting to determine $B$ inverse using the table above. From the table I know that my basic variables are $x_1$, $x_2$ and $e_2$. I previously believed that $B$ inverse could simply be read from the optimal tableau as the values for your non basic variables. Therefore I originally thought $B$ inverse was the columns (excluding the first row) of $s_3$, $a_1$ and $a_2$ in the table above.

The columns of my BVs from my original equation (and therefore the value for B) is:

\begin{bmatrix}1&2&0\\1&-1&-1\\2&1&0\end{bmatrix}

and if I find the inverse of $B$ myself I get:

\begin{bmatrix}-1/3&0&2/3\\2/3&0&-1/3\\-1&-1&1\end{bmatrix}

However this does not match the entries for my non basic variables in the table. Not only are the last two columns flipped, but the last row also has the wrong signs.

I presume the problem is that $x_1$, $x_2$ and $e_2$ in the final solution do not form the identity matrix, and possibly because $e_2$ is an excess variable and not a slack variable, however I can't be certain as my textbook only has an example where in the optimal solution, the BVs columns form the identity matrix and there are only slack variables.

Is it possible to read $B$ inverse from the optimal table in such a question?

$\endgroup$
1
$\begingroup$

Yes, provided that you read the columns of $B^{-1}$ in a right order.

The working principle behind reading $B^{-1}$ from the optimal tableau

The initial tableau

$$\begin{array}{rr|l} * & * & 0 \\ \hline N & I & b \end{array}$$

Some variables are chosen to be basic so that the solution is optimal. This corresponds to choosing columns in the coefficient matrix $\begin{bmatrix}N & I\end{bmatrix}$ are chosen to form the basis matrix $B$. Then we left multiply $B^{-1}$ to the initial tableau to get the optimal tableau.

The optimal tableau

$$\begin{array}{rr|l} * & * & * \\ \hline B^{-1} N & B^{-1} & B^{-1} b \end{array}$$

Problem in this case

We set the coefficient matrix (in the initial tableau) to be $$A = \begin{bmatrix} 1 & 2 & 0 & 0 & 1 & 0 \\ 1 & -1 & -1 & 0 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 & 0 \end{bmatrix}. $$

Observe that at the right-hand side, it's not the identity matrix $I$, so we need to rewrite our initial tableau.

Rewritten initial tableau

$$\begin{array}{cc|l} * & * & 0 \\ \hline N & I E_1 \cdots E_k & b \end{array}$$

Each $E_i$ denotes a matrix formed by swapping the $i$-th and $j$-th columns of $I$. (i.e. For any matrix $A$, the matrix product $A E_i$ means swapping the $i$-th and $j$-th columns of $A$.) $I E_1 \cdots E_k$ denotes a sequence of column swapping opertions $E_1, \dots, E_k$ on $I$, and it can represent any permutation of the columns of $I$.

Rewritten optimal tableau

$$\begin{array}{cc|l} * & * & * \\ \hline B^{-1} N & B^{-1} E_1 \cdots E_k & B^{-1} b \end{array}$$

Therefore, columns of $B^{-1}$ has been swapped. In exams, one won't try to get rid of $E_1 \cdots E_k$ by matrix multiplication. Instead, use the fact that

\begin{align} I E_1 \cdots E_k &=\begin{bmatrix}\mathbf{e}_{\sigma(1)} \cdots \mathbf{e}_{\sigma(n)}\end{bmatrix} \text{(what you can see from the initial matirx)} \\ B^{-1} E_1 \cdots E_k &= \begin{bmatrix}B^{-1}\mathbf{e}_{\sigma(1)} \cdots B^{-1}\mathbf{e}_{\sigma(n)}\end{bmatrix} \end{align}

Here, we use $\sigma$ to represent a permutation on $\{1,\dots,k\}$, and use $\mathbf{e}_i$ to represent the $i$-th column of the identity matrix $I$.

Another ideal situation

From the inital tableau

$$\begin{array}{cc|l} * & * & 0 \\ \hline N & I E_1 \cdots E_k & b \end{array}$$

you get an optimal tableau

$$\begin{array}{cc|l} * & * & * \\ \hline B^{-1} N & B^{-1} E_1 \cdots E_k & B^{-1} b \end{array}$$

with $\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n$ with the right order. i.e. In $\begin{bmatrix}B^{-1} N & B^{-1} E_1 \cdots E_k\end{bmatrix}$, $\forall 1 \le i < j \le n$, $\mathbf{e}_i$ is on the left-hand side of $\mathbf{e}_j$. (The identity matrix $I$ is "properly included" in the optimal tableau.) Then what you've done in the question to get the value of the matrix $B$ is correct.

Another problem in the given optimal tableau

$$\begin{array}{r|r|rrrrrr|l} & z & x_1 & x_2 & s_2 & * & * & * & * \\ \hline & * & * & * & * & * & * & * & * \\ \hline x_2 & * & 0 & 1 & 0 & * & * & * & * \\ x_1 & * & 1 & 0 & 0 & * & * & * & * \\ s_2 & * & 0 & 0 & 1 & * & * & * & * \end{array}$$

In "simple words", "the order is not so proper". We don't see the identity matrix $I$ here. To get $I$ from the given optimal tableau, we may swap the first and the second row. This motivates us to think of the effect on $B$ after swapping two rows.

Swapping two rows in the optimal simplex tableau

We swap two rows in the optimal simplex tableau

$$\begin{array}{cc|l} * & * & * \\ \hline B^{-1} N & B^{-1} E_1 \cdots E_k & B^{-1} b \end{array}$$

In other words, we left multiply the constraints by $E$, which is a square matrix formed by swapping two rows in the identity matrix $I$.

Then the optimal simplex tableau becomes

$$\begin{array}{cc|l} * & * & * \\ \hline E B^{-1} N & E B^{-1} E_1 \cdots E_k & E B^{-1} b \end{array}$$

Note that what you can actually see is $E B^{-1} E_1 \cdots E_k$, and we can sort the columns according to the order of $\mathbf{e}_i$'s in the initial tableau (i.e. we know $E B^{-1}$), so we are interested to find the square matrix $\hat{B}$ such that $\hat{B}^{-1}=E B^{-1}$. $$\hat{B} = B E^{-1} = B E$$. Therefore, $\hat{B}$ is formed by swapping the corresponding columns of $B$. We may re-write the optimal simplex tableau in terms of the transformed matrix $\hat{B}$

$$\begin{array}{cc|l} * & * & * \\ \hline \hat{B}^{-1} N & \hat{B}^{-1} E_1 \cdots E_k & \hat{B}^{-1} b \end{array}$$

We may generalise this to any permutation of rows in the optimal simplex tableau by expressing $E$ as a finite product of square matrices $E'_1, \dots E'_l$. $$E = E'_l \cdots E'_2 E'_1$$ Then we have

\begin{align} E B^{-1} &= E'_l \cdots E'_1 B^{-1} \\ &= E_{l}^{\prime -1} \cdots E_{1}^{\prime -1} B^{-1} \\ &= (B(E'_1 \cdots E'_l))^{-1} \end{align}

Thus, we see that when we have changed the order of rows in the optimal simplex tableau, we also need to perform corresponding column operations on the basis matrix $B$ in order to get the correct result.

Computational steps

It will be much better for you to label the basic varible on the LHS of the simplex tableau.

$$\begin{array}{r|r|rrrrrr|l} & z & x_1 & x_2 & s_2 & s_3 & a_1 & a_2 & \text{RHS} \\ \hline & 1 & 0 & 0 & 0 & \frac73 & M-\frac23 & M & \frac{58}{3} \\ \hline \color{red}{\large x_2} & 0 & 0 & 1 & 0 & -\frac{1}{3} & \frac{2}{3} & 0 & \frac{2}{3} \\ \color{red}{\large x_1} & 0 & 1 & 0 & 0 & \frac{2}{3} & -\frac{1}{3} & 0 & \frac{14}{3} \\ \color{red}{\large s_2} & 0 & 0 & 0 & 1 & 1 & -1 & -1 & 1 \end{array}$$

In the leftmost column, the order of basic variable (for top to bottom) is $x_2,x_1,s_2$. Therefore, we should pick the column of coefficients of $x_2$ in the initial tableau first, then the column for $x_1$, and finally the one for $s_2$.

If you set the basis matrix to

$$B=\begin{bmatrix}a_2 & a_1 & a_3\end{bmatrix} = \begin{bmatrix}2&1&0\\-1&1&-1\\1&2&0\end{bmatrix},$$

and observe that $\mathbf{e}_i$ (the $i$-th column of the identity matrix $I$) in the intial tableau will be transformed to $B^{-1} \mathbf{e}_i$ (i.e. the $i$-th column of the optimal tableau), you'll be able to extract $B^{-1}$ from the optimal tableau.

That is, the initial optimal tableau $$\begin{array}{cccccc|c} * & * & * & * & * & * & 0 \\ \hline a_1 & a_2 & a_3 & \mathbf{e}_3 & \mathbf{e}_1 & \mathbf{e}_2 & b \end{array}$$ is changed to $$\begin{array}{cccccc|c} * & * & * & * & * & * & * \\ \hline B^{-1}a_1 & B^{-1} a_2 & B^{-1} a_3 & B^{-1} \mathbf{e}_3 & B^{-1} \mathbf{e}_1 & B^{-1} \mathbf{e}_2 & b \end{array}$$

\begin{align} B&=\begin{bmatrix}a_2 & a_1 & a_3\end{bmatrix} \\ B^{-1} B &= I \\ B^{-1} \begin{bmatrix}a_2 & a_1 & a_3\end{bmatrix} &= \begin{bmatrix} \mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_3 \end{bmatrix} \\ B^{-1} \begin{bmatrix}a_1 & a_2 & a_3\end{bmatrix} &= \begin{bmatrix} \mathbf{e}_2 & \mathbf{e}_1 & \mathbf{e}_3 \end{bmatrix} \end{align}

Computational results

octave:1> A=[
> 1 2 0 0 1 0;
> 1 -1 -1 0 0 1;
> 2 1 0 1 0 0]
A =

   1   2   0   0   1   0
   1  -1  -1   0   0   1
   2   1   0   1   0   0

octave:2> b = [6;3;10]; c=[4 1 0 0 0 0];
octave:3> B=[A(:,2) A(:,1) A(:,3)]
B =

   2   1   0
  -1   1  -1
   1   2   0

octave:4> B^-1
ans =

   0.66667   0.00000  -0.33333
  -0.33333   0.00000   0.66667
  -1.00000  -1.00000   1.00000

octave:5> B^-1*A
ans =

   0.00000   1.00000   0.00000  -0.33333   0.66667   0.00000
   1.00000   0.00000   0.00000   0.66667  -0.33333   0.00000
   0.00000   0.00000   1.00000   1.00000  -1.00000  -1.00000

octave:6> [A(:,4:6)]
ans =

   0   1   0
   0   0   1
   1   0   0
$\endgroup$
  • $\begingroup$ excellent, and very clear answer- thank you! I like the username BTW :) $\endgroup$ – David Zorychta Dec 5 '15 at 20:54
  • $\begingroup$ You're welcome ! I'm also preparing for a linear programming exam. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Dec 6 '15 at 7:23

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.