How do you apply the Simplex Method to a standard minimization problem?
Example 2 illustrates how to convert a standard minimization problem into a standard maximization problem. These problems are called the dual of each other. The solutions of the dual problems are related and can be exploited to solve both problems simultaneously.
Let’s look at the solution of each linear programming problem graphically. For each problem, let’s look at a graph of the feasible region and a table of corner points with corresponding objective function values. From the table, we see that the solutions share the same objective function value at their respective solutions.
Although the corner points yielding the maximum or minimum are not the same, the value of the objective function at the optimal corner point is the same, 100. In other words,
Another connection between the dual problems is evident if we apply the Simplex Method to the dual maximization problem
If we rearrange the objective function and add slack variables to the constraints, we get the system of equations
This system corresponds to the initial simplex tableau shown below. The pivot column is the second column and the quotients can be formed to yield
The pivot for this tableau is the 3 in the first row, second column. If we multiply the first row by 1/3, the pivot becomes a 1 and results in the tableau
The first simplex iteration is completed by creating zeros in the rest of the pivot column. To change these entries, multiply the first row by -4 and add it to the second row. Then multiply the first row by 24 and add it to the third row.
Now that the pivot is a one and the rest of the pivot column are zeros, look at the indicator row to see if another Simplex Method iteration is needed. Since the entry in the first column of the indicator row, -8, is negative, we make the first column the new pivot column.
The quotients for each row of the tableau are formed below:
The smallest ratio is in the second row. The pivot, 8/3, must be changed to a 1 by multiplying the second row by ,
Once the pivot is a one, row operations are used to change the rest of the pivot column to zeros.
The entry in the first row of the pivot column is
changed to a zero by placing the sum –1/3 of times the second row and the first row in the first row. The entry in the third row of the pivot column is changed to a zero by placing the sum of 8 times the second row and the third row in the third row,
Since the indicator row no longer contains any negative entries, we have reached the final tableau. If we examine the final simplex tableau carefully, we can see the solution to the standard maximization problem and the standard minimization problem:
The final simplex tableau gives the solution to the standard maximization problem and the solution to the corresponding dual standard minimization problem. This means that as long as we can solve the standard maximization problem with the Simplex Method, we get the solution to the dual standard minimization problem for free. This suggests a strategy for solving standard minimization problems.
1. Make sure the minimization problem is in standard form. If it is not in standard form, modify the problem to put it in standard form.2. Find the dual standard maximization problem.3. Apply the Simplex Method to solve the dual maximization problem.4. Once the final simplex tableau has been calculated, the minimum value of the standard minimization problem’s objective function is the same as the maximum value of the standard maximization problem’s objective function.5. The solution to the standard minimization problem is found in the bottom row of the final simplex tableau in the columns corresponding to the slack variables.
Example 3 Find the Optimal Solution
In Section 4.2, we solved the linear programming problem
using a graph. In Example 2, we found the associated dual maximization problem,
Apply the Simplex Method to this dual problem to solve the minimization problem.
Solution In Example 1 and Example 2 we wrote this problem as a standard minimization problem and found the dual maximization problem. In this example, we’ll take the dual problem,
and apply the Simplex Method.
The initial simplex tableau is formed from the system of equations
Notice that the slack variables s1 and s2 are included in the equations corresponding to the constraints, and the objective function has been rearranged appropriately.
The initial tableau is
The most negative entry in the indicator row is -32, so the second column is the pivot column. Now calculate the quotients to find the pivot row,
The smallest quotient corresponds to putting the pivot in the second row, second column. To change the entry in this position to a one, multiply the second row by 1/4:
To put zeros in the rest of the pivot column, we utilize more row operations.
Since the indicator row is non-negative, this tableau corresponds to the optimal solution. The solution is found in the indicator row under the columns for the slack variables. The lowest value for w is 8 and occurs at (y1, y2) = (0, 8).