Assumptions
- $A \in M_{m\times n}(\Bbb R)$ ($m\le n$) has rank $n$ and basis matrix $B$.
- $x_B$ denotes the basic solution.
- $c_B$ denotes the reduced objective function so that $c^T x=c_B^T x_B$. (So the order/arrangement of basic variables is very important.)
The initial simplex tableau for your problem(, which is already in canoncial form,) will be
\begin{array}{cc|c}
A & I & b \\ \hline
-c^T & 0 & 0
\end{array}
We multiply the $m$ constraints by $B^{-1}$. Note that $\mathbf{e}_1,\dots,\mathbf{e}_n$ can be found in $[B^{-1}A\;B^{-1}]$ since $B$ is chosen from columns of $[A\;I]$. We add a linear combination of the first $m$ row to the last row.
\begin{array}{cc|c}
B^{-1}A & B^{-1} & B^{-1}b \\ \hline
c_B^T B^{-1}A-c^T & c_B^T B^{-1} & c_B^T B^{-1}b \tag{*} \label{t1}
\end{array}
Why is $c_B^T$ chosen? We write $x_B$ as $(x_{B_1},\dots,x_{B_n})^T$. Choose an index $i$ in $\{1,\dots,n\}$, and suppose that $x_j = x_{B_i}$
Case 1: $1\le j \le n$. In the $j$-th column of the last row,
$$(c_B^T B^{-1}A-c^T)_j = c_B^T B^{-1} \mathbf{a}_j -c_j = c_B^T \mathbf{e}_i - c_j = c_{B_i} - c_j = 0.$$
Case 2: $n+1 \le j \le m+n$. Note that $c_{B_i}= 0$. In the $j$-th column of the last row,
$$(c_B^T B^{-1})_{j - n} = c_B^T \mathbf{e}_i = c_{B_i} = 0.$$
Therefore, the entries corresponding to the basic variables in the last row in tableau $\eqref{t1}$ will be zero. Then, $\eqref{t1}$ is a simplex tableau that you can compute from the given optimal solution.
Computational results for your example
Here's the GNU Octave code for finding the optimal tableau. The syntax should be the same in MATLAB except for the solver glpk
. You may test the code at Octave Online.
c=[60 100 80]'; A=[144 192 240; 100 150 120; 1 1 1];
b=[120000 60000 500]';
[x_max,z_max]=glpk(c,A,b,[0 0 0]',[],"UUU","CCC",-1)
x=[x_max; b-A*x_max] % Include slack variables
A1=[A eye(3)]; % Part of initial tableau
c1=[c' zeros(1,3)]';
B=A1(:,find(x > 0)')
c_B=c1(find(x > 0));
disp('Initial tableau');
[A1 b; -c1' 0]
disp('Final tableau');
[B^-1*A B^-1 B^-1*b; c_B'*B^-1*A-c' c_B'*B^-1 c_B'*B^-1*b]
The computer output
x_max =
0.00000
400.00000
0.00000
z_max = 4.0000e+04
x =
0.0000e+00
4.0000e+02
0.0000e+00
4.3200e+04
-7.2760e-12
1.0000e+02
B =
192 1 0
150 0 0
1 0 1
Initial tableau
ans =
144 192 240 1 0 0 120000
100 150 120 0 1 0 60000
1 1 1 0 0 1 500
-60 -100 -80 -0 -0 -0 0
Final tableau
ans =
Columns 1 through 6:
6.6667e-01 1.0000e+00 8.0000e-01 0.0000e+00 6.6667e-03 -0.0000e+00
1.6000e+01 0.0000e+00 8.6400e+01 1.0000e+00 -1.2800e+00 0.0000e+00
3.3333e-01 1.1102e-16 2.0000e-01 0.0000e+00 -6.6667e-03 1.0000e+00
6.6667e+00 0.0000e+00 0.0000e+00 0.0000e+00 6.6667e-01 0.0000e+00
Column 7:
4.0000e+02
4.3200e+04
1.0000e+02
4.0000e+04
The optimal tableau:
\begin{equation*}
\begin{array}{ccccccc|l}
& x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \\ \hline
x_2 & \frac23 & 1 & \frac45 & 0 & \frac{1}{150} & 0 & 400 \\
s_1 & 16 & 0 & \frac{432}{5} & 1 & -\frac{32}{25} & 0 & 43200 \\
s_3 & \frac13 & 0 & \frac15 & 0 & -\frac{1}{150} & 1 & 100 \\ \hline
& \frac{20}{3} & 0 & 0 & 0 & \frac23 & 0 & 40000 \\
\end{array}
\end{equation*}
From the given optimal solution $z(x_1,x_2,x_3,x_4,x_5)=z(30,0,0,0,10)=150$, you can find:
$$x_1+5x_2+2x_3+x_4=b_1=\color{red}{30},\\ x_1-5x_2-6x_3+x_5=b_2=\color{red}{40},
$$
where $x_4$ and $x_5$ are the slack variables.
Since in the optimal table only the slack variable $x_4$ is replaced with $x_1$, then the intersection of $x_4$ row and $x_1$ column was the pivot element, which corresponds to the original value $1$. Hence the row remained from the initial table:
$$\begin{array}{r|rrrrr|r}
& x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline
z & 0 & & & & 0 & 150 \\ \hline
x_1 & \boxed 1 & \color{red}5 & \color{red}2 & \color{red}1 & 0 & 30 \\
x_5 & 0 & & & & 1 & 10 \\
\end{array}$$
In order to get $0$ as the first element in the row $z=5x_1+2x_2+3x_3$, where the first element was $-5$ initially, pivot row must have been multiplied by $5$ and added to it:
$$\begin{array}{r|rrrrr|r}
& x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline
z & 0 & \color{red}{23} & \color{red}7 & \color{red}5 & 0 & 150 \\ \hline
x_1 & \boxed 1 & \color{red}5 & \color{red}2 & \color{red}1 & 0 & 30 \\
x_5 & 0 & & & & 1 & 10 \\
\end{array}
$$
In order to get $0$ as the first element in the row $x_5$, where the first element was $1$ initially, pivot row must have been multiplied by $-1$ and added to it:
$$\begin{array}{r|rrrrr|r}
& x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline
z & 0 & \color{red}{23} & \color{red}7 & \color{red}5 & 0 & 150 \\ \hline
x_1 & \boxed 1 & \color{red}5 & \color{red}2 & \color{red}1 & 0 & 30 \\
x_5 & 0 & \color{red}{-10} & \color{red}{-8} & \color{red}{-1} & 1 & 10 \\
\end{array}
$$
Note: I am not sure if this is ejecuting (executing). But it is reverse engineering (backwards working).
Best Answer
If the previously optimal basic feasible solution violates the new constraint, then the basis (adjusted to include a basic variable in the new constraint) is "superoptimal" (at least as good as, and possible better, than optimal) but infeasible. In that case, you can use the dual simplex algorithm. Whereas the primal simplex algorithm starts with a feasible basis and works toward optimality while maintaining feasibility, the dual simplex algorithm starts with a superoptimal but infeasible basis and works toward feasibility while maintaining superoptimality. Most (all?) text books that discuss the simplex method also discuss the dual simplex method. Dual simplex is the most common way that solvers handle cuts being added to an LP tableau.