How do you apply the Simplex Method to a minimization application?
The dual problem strategy works for standard minimization problems involving more variables or more constraints. Example 4 has two decision variables, but three constraints. This changes the sizes of the matrices involved, but not the process of applying the Simplex Method to the dual standard maximization problem.
Example 4 Find the Minimum Cost
In Section 4.2, we found the cost C of contracting barrels of American ale from contract brewery 1 and barrels of America ale from contract brewery 2. The linear programming problem for this application is
Follow the parts a through c to solve this linear programming problem.
a. Rewrite this problem so that it is a standard minimization problem.
Solution The objective function must have the form w = d1 y1 + d2 y2 + … + dn yn where y1, y2, … , yn are the decision variables, and d1, d2, … , dn are constants. In this case the decision variables are Q1 and Q2, and C is used instead of w. A different name for the variable is acceptable as long as the terms on the right side each contain a constant times a variable.
The constraints must have the form e1 y1 + e2 y2 + … + en yn ≥ f, where e1, e2, … , en and f are constants. The first constraint, Q1 + Q2 ≥ 100, has the proper format, but with the decision variables Q1 and Q2 instead of y1 and y2.
The second and third constraints must be modified to match the form e1 y1 + e2 y2 + … + en yn ≥ f. Subtract 0.25Q1 from both sides of the constraint Q2 ≥ 0.25Q1 to yield
-0.25Q1 + Q2 ≥ 0
The third constraint is converted to the proper form by rearranging the inequality Q1 ≥ Q2. Subtract Q2 from both sides to yield
Q1 – Q2 ≥ 0
These changes lead to a standard minimization problem,
b. Find the dual problem for the standard minimization problem.
Solution The dual maximization problem is found by forming a matrix from the constraints and objective function. The coefficients and constants in the constraints compose the first three rows. The coefficients from the objective function are placed the fourth row of the matrix.
The dual maximization problem’s coefficients and constant are found by switching the rows and columns of the matrix
We’ll use the decision variables x1, x2, and x3 and write the corresponding dual maximization problem,
c. Apply the Simplex Method to the dual problem to find the solution to the standard minimization problem.
Solution The standard minimization problem is solved by applying the Simplex Method to the dual maximization problem. The first step is to write out the system of equations we’ll work with including the slack variables:
This system of equations corresponds to the initial simplex tableau
The only negative number in the indicator row is -10,000, so the pivot column is the first column. We choose the pivot row by forming quotients from the last column and the pivot column:
The smallest quotient is 100 so the first row is the pivot row.
Conveniently, the pivot is already a 1 and we can use row operations to change the rest of the column to zeros.
The new matrix still has a negative number in the indicator row, so we must choose a new pivot. The second column is the pivot column. The second row is the pivot row since it contains the only admissible quotient, 25/1.25.
The pivot, 1.25, is changed to a 1 by multiplying the second row by 1/1.25:
With a 1 in the pivot, we can use row operations to put zeros in the rest of the pivot column. Multiply the pivot row by 0.25 and add it to the first row to put a zero at the top of the pivot column. Multiply the pivot row by 2500 and add it to the third row to put a zero at the bottom of the pivot row:
No entry in the indicator row is negative, so we know that this tableau corresponds to the solution. The solution to the minimization problem lies in the indicator row in the columns corresponding to the slack variables,
The lowest cost is $1,050,000 and occurs when (Q1, Q2) = (8000, 2000). This means the lowest cost occurs when 8000 barrels are contracted from brewery 1 and 2000 barrels are contracted from brewery 2.