[Math] Reconstructing an optimal Simplex tableau from an optimal solution

linear algebralinear programmingoperations research

I have here a bounded LP with infinite optimal solutions:

max    60 x1 + 100 x2 +  80 x3
s.t.  144 x1 + 192 x2 + 240 x3 <= 120,000
      100 x1 + 150 x2 + 120 x3 <= 60,000
          x1 +     x2 +     x3 <= 500
                 x >= 0

My Operations Research teacher has hinted that you can reconstruct an entire optimal tableau from the optimal solution and the initial LP. I can easily find the basis and reconstruct the entirety of the tableau, except for the objective row. What I've done now was a really roundabout way of using MATLAB to find an optimal solution (doing this LP by hand is messy, and we've already had plenty of simplex method homework), finding $B^{-1}$ and multiplying through the tableau, which revealed a simpler optimal solution, and then running the simplex method again by hand, but rigging my choices of entering and leaving variables to get the basis I want.

There's a simpler way, yes?

Best Answer

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*}