List the six possible bases of the LP P and find their corresponding solutions

Question

Consider the following LP P:

    max         z = 22x_1 - 12x_2
    subject to: 8x_1 + 4x_2 \le 15
                2x_1 + 6x_2 \le 7
                x_1, x_2 \ge 0 

(a) List the six possible bases of P and find their corresponding solutions. To do this, first add slack variables and then pivot so as to produce each of the bases and its solutions.

I may be missing the point with this question but I am quite confused about finding 6 bases. I have computed 2 tablueax (T^(0) and T^(1)), T^(1) yields an optimal solution x^(1) = (1.875, 0 | 0, 3.25)^T with z^(1) = 41.25. How can six bases be found when the second basis yields an optimal solution?

Any help is appreciated.

Answer 1

I think the author expects elementary solutions without using simplex method. This is possibly an exercise to consolidate the Fundamental Theorem of Linear Programming. As the question suggests, we have to add slack variables so that the LPP becomes $$ \begin{align} \max z = 22x_1 - 12x_2 \\ \text{s.t.} \quad 8x_1 + 4x_2 + s_1 &= 15 \\ 2x_1 + 6x_2 + s_2 &= 7 \\ x_1, x_2, s_1, s_2 &\ge 0 \end{align} $$ The six possible bases are to take two variables from $x_1, x_2, s_1, s_2$. As the number of rows $m$ gets larger, we'll have $\binom{m+n}{2}=O((m+n)^2)$. This is terrible, so I'll use some script to find the solution.

Table generated by the following Octave code. You may see my another another for the explanation of the variables.

octave:1> format rat;
octave:2> c = [22 -12 0 0]'; b = [15 7]'; A = [8 4 1 0; 2 6 0 1];
octave:3> for i=1:3 for j=i+1:4 basis=[i j]; B = A(:,basis); cB = c(basis);
xB=B\b; zval=cB'*xB; disp([basis xB' zval]) endfor endfor
1          2      31/20      13/20     263/10
1          3        7/2        -13         77
1          4       15/8       13/4      165/4
2          3        7/6       31/3        -14
2          4       15/4      -31/2        -45
3          4         15          7          0

\begin{array}{|r|l|r|} \hline \text{basis} & \text{solution} & \text{val} \\\hline x_1 , x_2 & (31/20 , 13/20 )& 263/10 \\ x_1 , s_1 & (7/2 , -13 )& 77 \\\hline x_1 , s_2 & (15/8 , 13/4 )& 165/4 \\\hline x_2 , s_1 & (7/6 , 31/3 )& -14 \\ x_2 , s_2 & (15/4 , -31/2 )& -45 \\ s_1 , s_2 & (15 , 7 )& 0 \\\hline \end{array}