How Do You Solve A Standard Minimization Problem?

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

3y1y2y3 > 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 + 2x2x3 < 14

x1 – 3x2x3 < 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.