4.3: Minimization By The Simplex Method
- Page ID
- 38581
In this section, you will learn to solve linear programming minimization problems using the simplex method.
- Identify and set up a linear program in standard minimization form
- Formulate a dual problem in standard maximization form
- Use the simplex method to solve the dual maximization problem
- Identify the optimal solution to the original minimization problem from the optimal simplex tableau.
In this section, we will solve the standard linear programming minimization problems using the simplex method. Once again, we remind the reader that in the standard minimization problems all constraints are of the form \(ax + by ≥ c\).
The procedure to solve these problems was developed by Dr. John Von Neuman. It involves solving an associated problem called the dual problem. To every minimization problem there corresponds a dual problem. The solution of the dual problem is used to find the solution of the original problem. The dual problem is a maximization problem, which we learned to solve in the last section. We first solve the dual problem by the simplex method.
From the final simplex tableau, we then extract the solution to the original minimization problem.
Before we go any further, however, we first learn to convert a minimization problem into its corresponding maximization problem called its dual.
Convert the following minimization problem into its dual.
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{Z}=12 \mathrm{x}_{1}+16 \mathrm{x}_{2} \\
\textbf { Subject to: } & \mathrm{x}_{1}+2 \mathrm{x}_{2} \geq 40 \\
& \mathrm{x}_{1}+\mathrm{x}_2 \geq 30 \\
& \mathrm{x}_{1} \geq 0 ; \mathrm{x}_{2} \geq 0
\end{array} \nonumber \]
Solution
To achieve our goal, we first express our problem as the following matrix.
\[\begin{array}{cc|c}
1 & 2 & 40 \\
1 & 1 & 30 \\
\hline 12 & 16 & 0
\end{array} \nonumber \]
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:
\[\begin{array}{cc|c}
1 & 1 & 12 \\
2 & 1 & 16 \\
\hline 40 & 30 & 0
\end{array} \nonumber \]
The following maximization problem associated with the above matrix is called its dual.
\[\begin{array}{ll}
\textbf { Maximize } & \mathrm{Z}=40 \mathrm{y}_{1}+30 \mathrm{y}_{2} \\
\textbf { Subject to: } & \mathrm{y}_{1}+\mathrm{y}_{2} \leq 12 \\
& 2 \mathrm{y}_1+\mathrm{y}_2 \leq 16 \\
& \mathrm{y}_{1} \geq 0 ; \mathrm{y}_{2} \geq 0
\end{array} \nonumber \]
Note that we have chosen the variables as y's, instead of x's, to distinguish the two problems.
Solve graphically both the minimization problem and its dual maximization problem.
Solution
Our minimization problem is as follows.
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{Z}=12 \mathrm{x}_1+16 \mathrm{x}_2 \\
\textbf { Subject to: } & \mathrm{x}_{1}+2 \mathrm{x}_{2} \geq 40 \\
& \mathrm{x}_{1}+\mathrm{x}_{2} \geq 30 \\
& \mathrm{x}_{1} \geq 0 ; \mathrm{x}_{2} \geq 0
\end{array} \nonumber \]
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 is:
\[\begin{array}{ll}
\textbf { Maximize } & \mathrm{Z}=40 \mathrm{y}_1+30 \mathrm{y}_{2} \\
\textbf { Subject to: } & \mathrm{y}_{1}+\mathrm{y}_{2} \leq 12 \\
& 2 \mathrm{y}_1+\mathrm{y} 2 \leq 16 \\
& \mathrm{y}_{1} \geq 0 ; \mathrm{y}_{2} \geq 0
\end{array}\nonumber \]
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 Example \(\PageIndex{2}\) above is the same as Example 3.1.1, in section 3.1. It is also the same problem as Example 4.1.1 in section 4.1, 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; in Example \(\PageIndex{2}\) the minimum and maximum 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.
Find the solution to the minimization problem in Example \(\PageIndex{1}\) by solving its dual using the simplex method. We rewrite our problem.
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{Z}=12 \mathrm{x}_{1}+16 \mathrm{x}_{2} \\
\textbf { Subject to: } & \mathrm{x}_{1}+2 \mathrm{x}_{2} \geq 40 \\
& \mathrm{x}_{1}+\mathrm{x}_{2} \geq 30 \\
& \mathrm{x}_{1} \geq 0 ; \mathrm{x}_{2} \geq 0
\end{array} \nonumber \]
Solution
\[\begin{array}{ll}
\textbf { Maximize } & \mathrm{Z}=40 \mathrm{y}_{1}+30 \mathrm{y}_{2} \\
\textbf { Subject to: } & \mathrm{y}_{1}+\mathrm{y}_{2} \leq 12 \\
& 2 \mathrm{y}_{1}+\mathrm{y}_{2} \leq 16 \\
& \mathrm{y}_{1} \geq 0 ; \mathrm{y}_{2} \geq 0
\end{array} \nonumber \]
Recall that we solved the above problem by the simplex method in Example 4.1.1, section 4.1. Therefore, we only show the initial and final simplex tableau.
The initial simplex tableau is
\[\begin{array}{ccccc|c}
\mathrm{y}_1 & \mathrm{y}_2 & \mathrm{x}_{1} & \mathrm{x}_{2} & \mathrm{Z} & \mathrm{C} \\
1 & 1 & 1 & 0 & 0 & 12 \\
2 & 1 & 0 & 1 & 0 & 16 \\
\hline-40 & -30 & 0 & 0 & 1 & 0
\end{array}\nonumber \]
Observe an important change. Here our main variables are \(\mathrm{y}_1\) and \(\mathrm{y}_2\) and the slack variables are \(\mathrm{x}_1 and \mathrm{x}_2\).
The final simplex tableau reads as follows:
\[\begin{array}{ccccc|c}
\mathrm{y}_1 & \mathrm{y}_2 & \mathrm{x}_{1} & \mathrm{x}_{2} & \mathrm{Z} & \\
0 & 1 & 2 & -1 & 0 & 8 \\
1 & 0 & -1 & 1 & 0 & 4 \\
\hline 0 & 0 & 20 & 10 & 1 & 400
\end{array} \nonumber \]
A closer look at this table reveals that the \(\mathrm{x}_1\) and \(\mathrm{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.
\[\begin{array}{ccccc|c}
\mathrm{y}_1 & \mathrm{y}_2 & \mathrm{x}_{1} & \mathrm{x}_{2} & \mathrm{Z} & \\
0 & 1 & 2 & -1 & 0 & 8 \\
1 & 0 & -1 & 1 & 0 & 4 \\
\hline 0 & 0 & 20 & 10 & 1 & 400 \\
& & \uparrow & \uparrow & & \uparrow
\end{array} \nonumber \]
We restate the solution as follows:
The minimization problem has a minimum value of 400 at the corner point (20, 10)
We now summarize our discussion.
- Set up the problem.
- Write a matrix whose rows represent each constraint with the objective function as its bottom row.
- Write the transpose of this matrix by interchanging the rows and columns.
- Now write the dual problem associated with the transpose.
- Solve the dual problem by the simplex method learned in section 4.1.
- The optimal solution is found in the bottom row of the final matrix in the columns corresponding to the slack variables, and the minimum value of the objective function is the same as the maximum value of the dual.