Say we have been given a simplex tableau and let us assume that this isn't the first tableau (i.e. simplex has been run once or twice on it at this point). Can we convert this tableau back into the form of a linear program that will have the same optimal value as the one we've started with? I've attatched a tableau below so that we can discuss the same tableau.
Can we convert a simplex tableau into a linear program
linear programmingoperations researchoptimization
Related Solutions
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*}
Hint: The dual program is
$$\begin{array}{}\texttt{min} \quad 200y_1+100y_2\\ \\ 3y_1+y_2\geq 3 \\ 4y_1+3y_2\geq 6 \\ 2y_1+2y_2\geq 2 \\ \\ y_1,y_2 \geq 0\end{array}$$
This program can be solved graphically. See here how it works.
Finally you apply the complementary slackness theorem to obtain the solution of the primal problem:
$x_j^*\cdot z_j^*=0 \ \forall \ \ j=1,2, \ldots , n$
$y_i^*\cdot s_i^*=0 \ \forall \ \ i=1,2, \ldots , m$
$s_i^* \text{ are the optimal values of the slack variables of the primal problem.}$
$z_j^* \text{ are the optimal values of the slack variabales of the dual problem.}$
Best Answer
Essentially, all the variables on the left-hand side are basic, and the value they take is the corresponding value on the right.