9
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Oct 19, 2019 at 19:48

1 Answer 1

5
$\begingroup$

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.

From this page:

We divide the simplex method into two phases:

  1. Finds an initial feasible basic solution.
  2. finds an optimal feasible basic solution.

The steps of phases 1 and 2 are identical. They differ in the objective function and the variables included in the problem. The steps of phase 1 are performed until a basic solution is obtained without any artificial variables. Starting from the solution of phase 1, the artificial variables are removed from the problem and the objective value is restored and phase 2 continues to find an optimal solution.

In the first link, there is an example of writing down the tableau format explained in a very detailed way. Another good example by Vanderbei can be found here. I hope these will be helpful for your problem as well.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2019 at 10:12
  • $\begingroup$ 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? $\endgroup$ Oct 20, 2019 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.