# Doubt on finding simplex's initial canonical tableau (II Phase)

Good day.

Given the following notation for an initial canonical tableau for a linear program in standard form:

$$T_1 = \begin{bmatrix} I & B^{-1}N & \bar{x}_{B} \\ 0^\intercal & \hat{x}_{N}^\intercal & -\bar{z} \end{bmatrix}$$

with:

• $$B$$ representing the matrix of the basic technological coefficients ($$x_{ij})$$,
• $$N$$ representing the matrix of the non-basic tech. coefficients,
• $$\bar{x}_{B}$$ representing the B-partition of the given feasible basic solution,
• $$\hat{x}_{N}^\intercal$$ representing the vector of the non-basic reduced costs,
• $$\bar{z}$$ representing the value of the objective function at the given $$\bar{x}$$ solution.

how would you go about representing the following standard linear program in tableau form?

\begin{alignedat}{4} \min_x{z} = & \; -4x_1 & \; -3x_2 & \; +7x_3 \\ & \; \quad\ 3x_1 & \; -5x_2 & \; +4x_3 & \; + x_4 && = & \; 3 \\ & \; \quad\ 6x_1 & \; +4x_2 & \; -5x_3 & & \; +x_5 \ & = & \; 2 \\ &&&&& \quad\ \ x & \ge & \; 0 \end{alignedat}

Update (adding what I have already tried/already know and tried to apply): looking for help on manuals and here on OR SE alike, the tableau seems to be generally in the form:

$$T_2 = \begin{bmatrix} A & b \\ c^\intercal & -\bar{z} \end{bmatrix}$$

with $$A$$ being the matrix of all technological coefficients, $$b$$ the resources vector and $$c^\intercal$$ the transpose costs vector.

The problem does not give you an initial $$\bar{x}$$ solution and I don't personally know how to represent the program above in tableau form.

Is the following correct? If so, why is $$T_1 = T_2$$?

$$\bar{T} = \begin{bmatrix} 3 & -5 & 4 & 1 & 0 & 3 \\ 6 & 4 & -5 & 0 & 1 & 2 \\ -4 & -3 & 7 & 0 & 0 & 0 \end{bmatrix}$$

The tableau above is built supposing that $$x_4, x_5$$ is the feasible basic solution vector and that, then, the tableau is in canonical form with respect to $$\bar{x} = \begin{bmatrix} 0 & 0 & 0 & 3 & 2 \end{bmatrix}$$.

• As @Oguz Toragay mentioned, you can use the two phases simplex method. If you are interested to see what's happened in the simplex tableau, you could try with this link. – A.Omidi Oct 19 '19 at 19:48

In page 17 of this note by Michel Goemans, the process of converting $$T_2 \iff T_1$$, has been explained. If you define $$Ax=b$$ as $$A_Bx_B+A_Nx_N=b$$ (in your formulation for $$T_1$$, $$A_B=B$$) in which $$x_B$$ are the basic variables and $$x_N$$ are the Non-basic variables, then $$T_1$$ has been obtained from the $$T_2$$ by a sequence of elementary row operations.

• This is great, I really appreciate it; thank you. Given, then, that $T_1 = T_2$, would it be legitimate to construct a tableau with respect to a vector $\bar{x}$ given that $A_B = I$ (the slack variables's coefficients effectively form the identity matrix)? Is it accurate that a feasible basic solution could be the identity matrix if the slack variables were to have $1$ as coefficients? Which would thus mean that $\bar{T}$ with respect to $\bar{x}$ is legitimate in the example above. – Johnny Bueti Oct 20 '19 at 10:12
• Question put more simply after digging deeper and hopefully understanding the matter: given a non-canonical tableau $T_0$ with respect to an initial feasible basic solution $\bar{x} = \begin{bmatrix} \bar{x}_B & \bar{x}_N \end{bmatrix}$, is it possible, through a sequence of elementary row operations, to reduce the $\bar{x}_{\beta(i)}$ (where $\beta$ is the vector of the indices of the $\bar{x}_B$ solutions in $\bar{x}$) columns to identity columns to build a canonical tableau $T_c$ with respect to $\bar{x}$ and proceed with Phase II? – Johnny Bueti Oct 20 '19 at 15:20