Prev Next Top Tableau2_1

Tableau Method Solution of Equation (2.1) in Chvatal

Equation (2.1)
The problem in equation (2.1) of Chvatal is
maximize    5*x1 + 4*x2 + 3*x3
subject to  2*x1 + 3*x2 +   x3 <= 5
            4*x1 +   x2 + 2*x3 <= 11
            3*x1 + 4*x2 + 2*x3 <= 8
              x1 ,   x2 ,   x3 >= 0

Add Slack And Objective Variables
maximize    5*x1 + 4*x2 + 3*x3                - z  = 0
subject to  2*x1 + 3*x2 +   x3 + s1                = 5
            4*x1 +   x2 + 2*x3      + s2           = 11
            3*x1 + 4*x2 + 2*x3           + s3      = 8
              x1 ,   x2 ,   x3   s1 , s2 , s3     >= 0

Tableau Format
The tableau representation of the equations above is  \[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z  & b  \\
2   & 3   & 1   & 1   & 0   & 0   & 0  & 5  \\
4   & 1   & 2   & 0   & 1   & 0   & 0  & 11 \\
3   & 4   & 2   & 0   & 0   & 1   & 0  & 8  \\
5   & 4   & 3   & 0   & 0   & 0   & -1 & 0
\end{array}
\]  (Note that we have moved the equation for  z to the last row.) The corresponding basic feasible solution is  x_1 = x_2 = x_3 = 0 ,  s_1 = 5 ,  s_2 = 11 ,  s_3 = 8 ,  z = 0 .

Choose First Pivot
We search the row corresponding to the objective  z (last row) for a positive entry and find the value 5 in the  x_1 column. Thus was can increase the objective by increasing the value of  x_1 and holding  x_2 ,  x_3 at zero. We now solve for the value of  x_1 that results in  \[
\begin{array}{llll}
s_1 = 0 & \Leftrightarrow & x_1 = 5/2  & = 2.5 \\
s_2 = 0 & \Leftrightarrow & x_1 = 11/4 & = 2.75 \\
s_3 = 0 & \Leftrightarrow & x_1 = 8/3  & = 2.66 \cdots
\end{array}
\]  Thus we can pivot on the pair  (x_1, s_1) and obtain a new basic feasible solution with an improved value for the objective.

Divide by First Pivot
Divide the row corresponding to pivot element by the value of the pivot element:  \[
\begin{array}{cccccccc}
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z  & b    \\
1   & 1.5 & .5  & .5  & 0   & 0   & 0  & 2.5  \\
4   & 1   & 2   & 0   & 1   & 0   & 0  & 11   \\
3   & 4   & 2   & 0   & 0   & 1   & 0  & 8    \\
5   & 4   & 3   & 0   & 0   & 0   & -1 & 0
\end{array}
\] 

First Row Reduction
For each of the rows, except the one corresponding to the pivot element, subtract the value in the column corresponding to  x_1 times the row corresponding to the pivot element:  \[
\begin{array}{cccccccc}
x_1 & x_2  & x_3 & s_1   & s_2 & s_3 & z  & b    \\
1   & 1.5  & .5  & .5    & 0   & 0   & 0  & 2.5  \\
0   & -5   & 0   & -2    & 1   & 0   & 0  & 1    \\
0   & -.5  & .5  & -1.5  & 0   & 1   & 0  & .5   \\
0   & -3.5 & .5  & -2.5  & 0   & 0   & -1 & -12.5
\end{array}
\]  The corresponding basic feasible solution is  s_1 = x_2 = x_3 = 0 ,  x_1 = 2.5 ,  s_2 = 1 ,  s_3 = .5 ,  z = 12.5 .

Choose Second Pivot
We search the row corresponding to the objective  z (last row) for a positive entry and find .5 in the  x_3 column. Thus we can increase the objective by increasing  x_3 and holding  x_2 ,  s_1 at zero. We now solve for the value of  x_3 that results in  \[
\begin{array}{lll}
x_1 = 0 & \Leftrightarrow & x_3 = 5 \\
s_2 = 1& {\rm for \; all} & x_3     \\
s_3 = 0 & \Leftrightarrow & x_3 = 1 
\end{array}
\]  Thus we can pivot on the pair  (x_3, s_3) and obtain a new basic feasible solution with an improved value for the objective.

Divide by Second Pivot
Divide the row corresponding to pivot element by the value of the pivot element:  \[
\begin{array}{cccccccc}
x_1 & x_2  & x_3 & s_1   & s_2 & s_3 & z  & b    \\
1   & 1.5  & .5  & .5    & 0   & 0   & 0  & 2.5  \\
0   & -5   & 0   & -2    & 1   & 0   & 0  & 1    \\
0   & -1   & 1   & -3    & 0   & 2   & 0  & 1    \\
0   & -3.5 & .5  & -2.5  & 0   & 0   & -1 & -12.5
\end{array}
\] 

Second Row Reduction
 \[
\begin{array}{cccccccc}
x_1 & x_2  & x_3 & s_1   & s_2 & s_3 & z  & b    \\
1   & 2    & 0   & 2     & 0   & -1  & 0  & 2    \\
0   & -5   & 0   & -2    & 1   & 0   & 0  & 1    \\
0   & -1   & 1   & -3    & 0   & 2   & 0  & 1    \\
0   & -3   & 0   & -1    & 0   & -1  & -1 & -13 
\end{array}
\]   s_1 = x_2 = s_3 = 0 ,  x_1 = 2 ,  s_2 = 1 ,  x_3 = 1 ,  z = 13 . This is an optimal solution because all of the coefficients in the row corresponding to the objective  z are less than zero.
Input File: Tableau2_1.omh