0
$\begingroup$

In 2-phases simplex method what kind of operations must be done to get the canonical form tableau?

In this step(phase 2 of 2-phases method) after the remotion of artificial variables columns of auxiliary problem and copy of coefficents of objective functions, I don't know what are the operations performed to get canonical form tableau (as you see in the picture)

enter image description here

the objective function was

enter image description here

$\endgroup$
  • $\begingroup$ Canonical form, I'm assuming, is $\min c^{T}x$ subject to $Ax \leq b$, $x \geq 0$?. It varies from text-to-text. $\endgroup$ – clocktower Feb 3 '16 at 22:44
  • $\begingroup$ I call this standard form of objective function, before start the simplex method I use the standard form but this isn't a problem. I mean the canonical form of the latest step tableau (in phase 2 of 2-phases simplex method). The step that transform the first table in the second table of my picture. $\endgroup$ – AndreaF Feb 3 '16 at 22:52
  • $\begingroup$ If I'm understanding your confusion. For two-phase simplex, you're solving an auxiliary problem to get the second tableau. There's no straightforward transformation. Unfortunately, I've not encountered two-phase with equality constraints. $\endgroup$ – clocktower Feb 3 '16 at 22:54
  • $\begingroup$ Exactly, I solve an auxiliary problem. my question is about the operation performed after the remotion of the artificial variables used in the auxiliary problem in phase 2 since I have to get a solution of the original problem after the first phase iterations. $\endgroup$ – AndreaF Feb 3 '16 at 22:59
1
$\begingroup$

To get the matrix back in canonical form, you simply need to make sure that any basic variable has a 0 coefficient in the objective function row. So looking at the matrix

$$\begin{bmatrix} 1&0&-1&-1&0&2 \\ 0&0&-4&-4&1&10 \\ 0&1&3&1&0&4 \\ -2&-1&2&0&0&0 \\ \end{bmatrix}$$

You simply need to add 2 times the first row to the last (objective row) and 1 times the third row to the last (objective row). This will make sure there is a coefficient of 0 in the objective row for the first two columns, since they are the columns that contain the basic variables.

Doing this, you should get that after adding $R4 + 2R1$ you get $$\begin{bmatrix} 1&0&-1&-1&0&2 \\ 0&0&-4&-4&1&10 \\ 0&1&3&1&0&4 \\ -2&-1&0&-2&0&4 \\ \end{bmatrix}$$ This makes sure that the basic variable $x_1$ has a 0 coefficient in the objective function row. Doing the same for the basic variable $x_2$, adding $R4+R3$, you should get:

$$\begin{bmatrix} 1&0&-1&-1&0&2 \\ 0&0&-4&-4&1&10 \\ 0&1&3&1&0&4 \\ -2&0&-3&-1&0&8 \\ \end{bmatrix}$$

Which is the matrix in canonical form.

$\endgroup$
  • $\begingroup$ Thanks for the answer. So not in all situation I have to add 2 time the 1st and 1 time the 3rd. I have to choose random rows to sum to latest to get 0 in all basic variables. Right? Is there any other criterion to choose the rows that I have to sum or could I choose what row want to get 0? $\endgroup$ – AndreaF Feb 4 '16 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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