0.6 Linear programing: the simplex method  (Page 3/3)

To achieve our goal, we first express our problem as the following matrix.

Observe that this table looks like an initial simplex tableau without the slack variables. Next, we write a matrix whose columns are the rows of this matrix, and the rows are the columns. Such a matrix is called a transpose of the original matrix. We get

The following maximization problem associated with the above matrix is called its dual.

Maximize $Z=\text{40}{y}_1+\text{30}{y}_2$

Subject to:

We have chosen the variables as y's, instead of x's, to distinguish the two problems.

Our minimization problem is as follows.

Minimize $Z=\text{12}{x}_1+\text{16}{x}_2$

Subject to: $x_1+{\mathrm{2x}}_2\ge \text{40}$

We now graph the inequalities.

We have plotted the graph, shaded the feasibility region, and labeled the corner points. The corner point (20, 10) gives the lowest value for the objective function and that value is 400.

Now its dual.

Maximize $Z=\text{40}{y}_1+\text{30}{y}_2$

Subject to:

$y_1\ge 0;y_2\ge 0$

We graph the inequalities.

Again, we have plotted the graph, shaded the feasibility region, and labeled the corner points. The corner point (4, 8) gives the highest value for the objective function, with a value of 400.

The reader may recognize that this problem is the same as [link] , in [link] . This is also the same problem as [link] in [link] , where we solved it by the simplex method.

We observe that the minimum value of the minimization problem is the same as the maximum value of the maximization problem; they are both 400. This is not a coincident. We state the duality principle.

The Duality Principle:

The objective function of the minimization problem reaches its minimum if and only if the objective function of its dual reaches its maximum. And when they do, they are equal.

Our next goal is to extract the solution for our minimization problem from the corresponding dual. To do this, we solve the dual by the simplex method.

The dual is as follows:

Maximize $Z=\text{40}{y}_1+\text{30}{y}_2$

Subject to:

Once again, we remind the reader that we solved the above problem by the simplex method in [link] , in [link] . Therefore, we will only show the initial and final simplex tableau.

The initial simplex tableau is

Observe an important change. Here our main variables are $y_1$ and $y_2$ and the slack variables are $x_1$ and $x_2$ .

The final simplex tableau reads as follows:

A closer look at this table reveals that the $x_1$ and $x_2$ values along with the minimum value for the minimization problem can be obtained from the last row of the final tableau. We have highlighted these values by the arrows.

We restate the solution as follows:

The minimization problem has a minimum value of 400 at the corner point (20, 10).