# Simplex method - the purpose of $cx$ or $-cx$ in the table

The following example comes from "Introduction to Linear Optimization" book by Dimitris Bertsimas and John N. Tsitsiklis:

Example $$3.5$$ Consider the problem $$\min-10x_1-12x_2-12x_3$$ Subject to: $$x_1+2x_2+2x_3=20$$ $$2x_1+x_2+2x_3=20$$ $$2x_1+2x_2+x_3=20$$ $$x_1,x_2, x_3\ge0$$

After introducing the slack variables the problem looks like this: $$\min-10x_1-12x_2-12x_3$$ Subject to: $$x_1+2x_2+2x_3+x_4\qquad\qquad=20$$ $$2x_1+x_2+2x_3\qquad+x_5\qquad=20$$ $$2x_1+2x_2+x_3\qquad\qquad+x_6=20$$ $$x_1,\ldots, x_6\ge0$$

The first iteration of the simplex table looks like this:

$$\begin{array} {|c|c|} \hline & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \\ \hline & 0 & -10 & -12 & -12 & 0 & 0 & 0 \\ \hline x_4 = & 20 & 1 & 2 & 2 & 1 & 0 & 0 \\ x_5 = & 20 & 2^* & 1 & 2 & 0 & 1 & 0 \\ x_6 = & 20 & 2 & 2 & 1 & 0 & 0 & 1 \\ \hline \end{array}$$

The entry in left upper corner of the table above the $$20$$’s is the value of $$cx$$. Even though I know how to perform the steps of the simplex method I don't know what is the purpose of placing this value here? Also in some other sources I can see that value of $$-cx$$ is placed here. What would be the purpose of that?

• If you mean $c^Tx...$ anyway, maximizing $c^Tx$ is the same as minimizing $-c^Tx.$ Commented Oct 11, 2022 at 22:55
• Please do not post images of text, instead of the text itself. MathJax and table formatting are available. Using images instead of them makes the post less accessible.
– Nij
Commented Oct 12, 2022 at 1:20

That upper left-hand corner of the tableau corresponds the objective function value output for each extreme point Simplex visits. Let’s look at this in a different way as such:

Given the model,

$$\text{min }z=-10x_1-12x_2-12x_3$$ Subject to, $$x_1+2x_2+2x_2\le20$$ $$2x_1+x_2+2x_3\le20$$ $$2x_1+2x_2+x_3\le20$$ $$x_1,x_2,x_3\ge0$$

Let’s put it in standardized form: $$\text{min }z+10x_1+12x_2+12x_3=0$$ Subject to, $$x_1+2x_2+2x_2+s_1=20$$ $$2x_1+x_2+2x_3+s_2=20$$ $$2x_1+2x_2+x_3+s_3=20$$ $$x_1,x_2,x_3,s_1,s_2,s_3\ge0$$

Then the following tableau will look like: $$\begin{array} {|c|c|}\hline BV & z & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & RHS \\ \hline z & 1 & 10 & 12 & 12 & 0 & 0 & 0 & 0 \\ \hline s_1 & 0 & 1 & 2 & 2 & 1 & 0 & 0 & 20 \\ \hline s_2 & 0 & 2 & 1 & 2 & 0 & 1 & 0 & 20 \\ \hline s_3 & 0 & 2 & 2 & 1 & 0 & 0 & 1 & 20 \\ \hline \end{array}$$

Here, the objective function output value (produced by $$C^Tx$$) is in the top right of the tableau on the objective function row. Of course, the only difference between the tableau in the book and this one above is the objective function row in which all the cost coefficients are positive. Here in the above tableau we would pivot the column with most positive value not equal to zero for a minimization function (in the book’s tableau we would pivot the column with the most negative value not equal to zero). To change an objective function from a maximization problem to a minimization problem, and vice versa, is to multiply the objective function row by negative one as pointed out in the comments. Thus, that is why the book shows $$-C^Tx$$ in some places and not in others.

Every time we pivot, the selected row of the minimum ratio test right-hand-side will be added to the objective function’s right-hand-side (in the case of the question’s original tableau, the left-most column.) So every time we visit a new extreme point via Simplex, we’ll know what values the objective function will have with with the basic variable Simplex has found and solved for.

For example, if we pivot the $$x_2$$ column with the $$s_1$$ row of the above tableau, we’ll get the following tableau:

$$\begin{array} {|c|c|}\hline BV & z & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & RHS \\ \hline z & 1 & 4 & 0 & 0 & -6 & 0 & 0 & -120 \\ \hline x_2 & 0 & 1/2 & 1 & 1 & 1/2 & 0 & 0 & 10 \\ \hline s_2 & 0 & 3/2 & 0 & 1 & -1/2 & 1 & 0 & 10 \\ \hline s_3 & 0 & 1 & 0 & -1 & -1 & 0 & 1 & 0 \\ \hline \end{array}$$

Notice that in this new tableau, the output of the objective function is $$-120$$. This is produced when $$x_1 = x_3 = 0$$ and $$x_2 = 10$$. We can even double check this in our original objective function before we put it in standard form as such: $$-10(0)-12(10)-12(0)=-120$$