In an earlier FAQ, we wrote out a standard minimization problem from an application. Now we’ll solve that problem by finding the dual standard maximization problem and applying the Simplex Method.
This process is covered in Section 4.4 of the textbook. For complete details on the process, consult this section and the many examples contained in this section. I will assume that you have looked over this section and are familiar with carrying out row operations on a matrix.
The problem we will solve is
Minimize C = 16y1 + 14y2 + 12y3 subject to
y1 + y2 + y3 > 6000
2y2 – 3y3 > 0
3y1 – y2 – y3 > 0
y1 > 0, y2 > 0, y3 > 0
Solution Write out the dual problem and apply the Simplex Method. Start by entering the objective function and constraints into a matrix. The transpose of this matrix yields the form of the dual standard maximization problem.
The dual problem is
Maximize z = 6000x1 subject to
x1 + 3x3 < 16
x1 + 2x2 – x3 < 14
x1 – 3x2 – x3 < 12
x1 > 0, x2 > 0, x3 > 0
Now add the slack variables to each constraint and form the initial matrix for the Simplex Method.
The pivot column is the first column since that is where the indicator row is most negative. The pivot row is the third row. The entry in the pivot is already a zero so we simply need to put zeros in the rest of the column using row operations.
For this new matrix, the pivot is the 5 in the second row, second column. Change the pivot to a 1 and then use it to put zeros in the rest of the column. This results in
Since there is still a negative number in the indicator row, we continue applying the Simplex Method. In this step, the pivot is the 4 in the first row, third column. As before, this entry is changed to a 1 and used to make the rest of the column into zeros.
The indicator row does not contain any negatives numbers so this is the final matrix. The solution to the standard minimization problem is under the slack variables and indicate that
y1 = 1500, y2 = 2700, and y3 = 1800
with a corresponding minimum of C = 83400 cents or $834.