Starting the simplex method from a given basic feasible solution? I have the following LP.
\begin{equation*}
\begin{array}{ll@{}ll}
{\text{maximize}}  & x_1 + x_2 + x_3 + x_4 \\
\text{subject to}
& 
\begin{bmatrix} 1 & -1 & -3 & 1 \\ 2 & 2 & 1 & -2 \end{bmatrix}
\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}
=
\begin{bmatrix} 5 \\ 4 \end{bmatrix} \\
& x_1,x_2,x_3,x_4 \geq 0
\end{array}
\end{equation*}
Usually, when a basic feasible solution is not immediately apparent, I’d go through some procedure to obtain one, and in the process deriving the corresponding tableau. However, by some previous work I know that a bfs for this LP is $(7/2,0,0,3/2)$. How do I set up the simplex tableau corresponding to this bfs?
In general a simplex tableau could be represented in the following form:
$$
\frac{\mathbf{x}_{B}=\mathbf{p}+Q \mathbf{x}_{N}}{z=z_{0}+\mathbf{r}^{T} \mathbf{x}_{N}}
$$
where $\mathbf{x}_{B}$ is the vector of the basic variables, $N=\{1,2, \ldots, n\} \backslash B, \mathbf{x}_{N}$ is the vector of nonbasic variables, $\mathbf{p} \in \mathbb{R}^{m}, \mathbf{r} \in \mathbb{R}^{n-m}, Q$ is an $m \times(n-m)$
matrix, and $z_{0} \in \mathbb{R}$.
I’ve managed to deduce the first lines of the tableau from the information given, and also $z_0$ in the $z$-row. However there are still the reduced costs $\mathbf{r}$ of the nonbasic variables left. There is a formula for it: $\mathbf{r} = \mathbf{c}_N - (\mathbf{c}^T_B A^{-1}_B A_N)^T$, but it’s pretty complicated (for larger problems at least) so I’m not sure if there’s a shortcut here.
The tableau I have so far is as follows:
\begin{equation}
\begin{array}{c|cccc|c}
B & x_1 & x_2 & x_3 & x_4 &  \\ \hline
x_1 & 1 & -1 & -3 & 0 & 7/2  \\
x_4 & 0 & -1 & -1/2 & 1 & 3/2 \\ \hline
& 0 &  &  & 0 & 5 \\ 
\end{array}
\end{equation}
 A: You can put in the equality constraint for the objective function (which is $z-c^Tx=0$ so the row will have the negative coefficients as entries), and then pivot to make the reduced costs of the basic variables zero:
Initial (invalid) simplex table:
\begin{equation}
\begin{array}{c|cccc|c}
B & x_1 & x_2 & x_3 & x_4 &  \\ \hline
x_1 & 1 & -1 & -3 & 0 & 7/2  \\
x_4 & 0 & -1 & -1/2 & 1 & 3/2 \\ \hline
    &\color{red}{-1} & -1 & -1   &\color{red}{-1} & 0
\end{array}
\end{equation}
Entries in red should be zero in a valid table. Let's fix it with a few row operations. First, add the first row to the objective function row to make the reduced cost under $x_1$ equal to zero:
\begin{equation}
\begin{array}{c|cccc|c}
B & x_1 & x_2 & x_3 & x_4 &  \\ \hline
x_1 & 1 & -1 & -3   & 0 & 7/2  \\
x_4 & 0 & -1 & -1/2 & 1 & 3/2 \\ \hline
    & 0 & -2 & -4   &-1 & 7/2
\end{array}
\end{equation}
Now add the second row to the objective function row to make the reduced cost under $x_4$ equal to zero:
\begin{equation}
\begin{array}{c|cccc|c}
B & x_1 & x_2 & x_3 & x_4 &  \\ \hline
x_1 & 1 & -1 & -3   & 0 & 7/2  \\
x_4 & 0 & -1 & -1/2 & 1 & 3/2 \\ \hline
    & 0 & -3 & -9/2 & 0 & 5
\end{array}
\end{equation}
And now you have a valid simplex table from which you can pivot as usual.
