Q:

Finding $B$ and $B^{-1}$ matrix for each simplex iteration

Suppose I have the linear programming problem:
Maximize $3x_1+2x_2$ 
subject to the contraints
$2x_1-3x_2+x_3 = 3$
$-x_1+x_2 = 5$
Now, graphing this we see this particular problem cannot be optimized but there are only 2 iterations possible using the simplex method and that's what I'm focusing on.
Iteration 0: 
($x_3,x_4$ are the slack variables)
\begin{array}{|c|c|c|c|c|c|}
\hline
BASES&x_1&x_2&x_3&x_4&p&RHS \\ \hline
&-3&-2&0&0&1&0\\ \hline
x_3&2&-3&1&0&0&3\\ \hline
x_4&-1&1&0&1&0&5\\ \hline
\end{array}
Iteration 1:
\begin{array}{|c|c|c|c|c|c|}
\hline
BASES&x_1&x_2&x_3&x_4&p&RHS \\ \hline
&0&-\frac{13}{2}&\frac{3}{2}&0&1&\frac{9}{2}\\ \hline
x_1&1&-\frac{3}{2}&\frac{1}{2}&0&0&\frac{3}{2}\\ \hline
x_4&0&-\frac{1}{2}&\frac{1}{2}&1&0&8\\ \hline
\end{array}
I'm interested in knowing what the significance of the $B$ matrix and its inverse is, and how it can be calculated for each iteration.
I'm not good with the theorems and heavy maths, I'd like an understanding  as intuitive as possible, which might help me understand the heavy stuff at a later stage,
Thanks.

A:

When you solve the problem
$$
\max\; c^{T}x
$$
subject to 
$$
Ax=b
$$
You have to partition your variables in two sets: basic variables $x_b$ and non basic variables $x_n$. With this partition, you can rewrite the problem as follows
$$
\max\; c^T\pmatrix{x_b\\x_n}= c^{T}_b x_b + c^{T}_n x_n
$$
subject to
$$
A \pmatrix{x_b\\x_n} =b\quad \Leftrightarrow \quad \pmatrix{B &N}\pmatrix{x_b\\x_n} =b\quad \Leftrightarrow \quad Bx_b +Nx_n = b
$$
So to answer your question: $B$ is the set of columns of the initial matrix $(A)$ that correspond to your basic variables of the optimal solution. This is the key. So in your example, in the optimal tableau, basic variables are $x_1$ and $x_4$. It follows that 
$$
B= \pmatrix{2 &0 \\ -1 &1}
$$
When you reach optimality, you have 
$$
Bx_b +Nx_n = b \quad \Leftrightarrow \quad x_b = B^{-1}b - B^{-1}Nx_n
$$
So $B^{-1}$ represents the $B$ matrix after all the pivots necessary for reaching optimality have been performed. To compute $B^{-1}$, you use the simplex algorithm, which does it iteratively. Typically you don't get $B^{-1}$ in one shot. But as explained in your document there is a clever way to read $B^{-1}$ in the optimal tableau: Look for the identity matrix in the initial tableau, and look at what it became in the last tableau: it is precisely $B^{-1}$. In your example, columns $x_3$ and $x_4$ give the identity matrix, so
$$
B^{-1} = \pmatrix{1/2&0\\1/2& 1}
$$

