Simplex: Standard Minimization

Simplex method:
Standard Minimization Problems

In the last section we learned how to maximize an objective function such as revenue or profit. In this section we learn how to minimize an objective function such as cost. We study two types of minimization problems.

Minimization with £ constraints.
These problems have nearly the same structure as the standard maximization problems and may be solved by maximizing the negative of the objective function.
Standard minimization.
These problems are different from the standard maximization problems in two ways.
(i) The objective function is to be minimized.
(ii) The constraints are of the ³ form.
The standard minimization problem is solved by setting up and solving a dual problem.

Minimization with £ constraints

This problem is the same as the standard maximization problem except the objective function is to be minimized. This problem is equivalent to maximizing the negative of the given objective function.

The objective function is to be minimized.
All the variables in the problem are nonnegative.
Each linear constraint is written as an expression involving the variables set less than or equal to a nonnegative constant.

Standard minimization problem

The objective function is to be minimized.
All the variables in the problem are nonnegative.
Each linear constraint is written as an expression involving the variables set greater than or equal to a nonnegative constant.

Dual Problem

Each minimization linear programming problem is associated with a maximization linear programming problem. The given problem is called the primal problem and the related problem is called the dual problem. To construct the dual problem write down the a table for the given primal problem :: constraints first :: objective function second :: variables then constants. Interchange the rows and columns of this table. Interpreting the table as a standard maximization problem yields the dual problem.

Solution to standard minimization problem

Solve the standard minimization by solving its dual problem ( a standard maximization problem). The connection between the solution of the primal problem and the dual problem is given in the following theorem.

Fundamental Theorem of Duality

A primal problem has a solution if and only if the corresponding dual problem has a solution. If a solution exists then

The objective function of both the primal and dual functions attain the same optimal value.
The optimal solution of the primal problem appears under the slack variables in the last row of the final simplex table associated with the dual problem.

Example: Minimization with £ constraints.
Minimize C = -2x + y subject to the constraints

æ  x + 2y  £  6  ö
ç 3x + 2y  £  12 ÷
ç       x  ³  0  ÷
è       y  ³  0  ø

(1) CONVERT TO A MAXIMIZATION PROBLEM

The problem of minimizing C is equivalent to the problem of maximizing P = -C.
Maximize P = 2x - y subject to the constraints

æ  x + 2y  £  6  ö
ç 3x + 2y  £  12 ÷
ç       x  ³  0  ÷
è       y  ³  0  ø

(2) SET UP AN INITIAL TABLE

Introduce slack variables u and v to replace the inequalities with equations.
 x + 2y + u = 6
3x + 2y + v = 12
Rewrite the objective function.
-2x + y + P = 0
Form augmented matrix with the constraints first and the objective function last.

   x    y    u    v    P    RHS 
é  1    2    1    0    0 |  6   ù
ê  3    2    0    1    0 |  12  ú
ë -2    1    0    0    1 |  0   û

(3) PERFORM A PIVOT OPERATION

We need to perform a pivot operation since there are negative entries in the last row. Column 1 is the pivot column since -2 is the most negative entry in the last row. Form ratios 6/1 = 6 and 12/3 = 4. Row 2 is the pivot row since it has the smallest ratio. The pivot element is colored red.

é  1    2    1    0    0 |  6   ù
ê  3    2    0    1    0 |  12  ú
ë -2    1    0    0    1 |  0   û

 R₁   > R₁/3

We make the pivot element into a 1 by dividing row 2 through by 3.

é  1    2    1    0    0 |  6  ù
ê  1    2/3  0    1/3  0 |  4  ú
ë -2    1    0    0    1 |  0  û

 R₂   > R₂ - 2 R₁

 R₃   > R₃ + 12 R₁

Eliminate the entries directly below pivot element.

é  0    4/3    1   -1/3    0 |  2  ù
ê  1    2/3    0    1/3    0 |  4  ú
ë  0    7/3    0    2/3    1 |  8  û

There are no negative entries in the last row so we are finished with the pivoting process.

(4) READ THE OPTIMAL SOLUTION

Recall that variables heading columns not in unit form are assigned a value of 0. The optimal solution for the maximization problem is

æ x = 4 ö
ç y = 0 ÷
è P = 8 ø

and hence the optimal solution for the original minimization problem is

æ x = 4  ö
ç y = 0  ÷
è C = -8 ø

Example: Standard minimization.
Minimize C = 8x + 12y subject to the constraints

æ  x + 3y  ³  2 ö
ç 2x + 2y  ³  3 ÷
ç       x  ³  0 ÷
è       y  ³  0 ø

(1) SET UP THE DUAL PROBLEM

Write down the following table for the primal problem

x  |  y  | RHS
--------------
1  |  3  | 2
2  |  2  | 3
8  | 12  |

Interchange the rows and columns to obtain

u  |  v  | RHS
--------------
1  |  2  | 8
3  |  2  | 12
2  |  3  |

Interpret the table as if it were the initial table for a standard maximization problem with the exception that the signs of the coefficients of the objective function are not reversed.

Maximize P = 2u + 3v subject to the constraints

æ  u + 2v  £  8  ö
ç 3u + 2v  £  12 ÷
ç       u  ³  0  ÷
è       v  ³  0  ø

(2) SOLVE STANDARD MAXIMIZATION PROBLEM: SET UP AN INITIAL TABLE

Introduce slack variables x and y to replace the inequalities with equations.
 u + 2v + x = 8
3u + 2v + y = 12
Rewrite the objective function.
-2u - 3v + P = 0
Form augmented matrix with the constraints first and the objective function last.

   u    v    x    y    P   RHS 
é  1    2    1    0    0 |  8   ù
ê  3    2    0    1    0 |  12  ú
ë -2   -3    0    0    1 |  0   û

(3) PERFORM A PIVOT OPERATION

We need to perform a pivot operation since there are negative entries in the last row. Column 2 is the pivot column since -3 is the most negative entry in the last row. Form ratios 8/1 = 8 and 12/3 = 4. Row 1 is the pivot row since it has the smallest ratio. The pivot element is colored red.

é  1    2    1    0    0 |  8   ù
ê  3    2    0    1    0 |  12  ú
ë -2   -3    0    0    1 |  0   û

 R₁   > R₁/2

We make the pivot element into a 1 by dividing row 1 through by 2.

é  1/2  1    1/2  0    0 |  4  ù
ê  3    2    0    1    0 |  12 ú
ë -2   -3    0    0    1 |  0  û

 R₂   > R₂ - 2 R₁

 R₃   > R₃ + 3 R₁

Eliminate the entries directly below pivot element.

é  1/2   1    1/2   0    0 |  4  ù
ê  2     0   -1     1    0 |  4  ú
ë -1/2   0    3/2   0    1 |  12 û

There is a negative entry in the last row. Hence, a second pivot operation is required.

(4) PERFORM A SECOND PIVOT OPERATION

We need to perform a pivot operation since there are negative entries in the last row. Column 1 is the pivot column since -1/2 is the most negative entry in the last row. Form ratios 4/(1/2) = 8 and 4/2 = 2. Row 2 is the pivot row since it has the smallest ratio. The pivot element is colored red.

é  1/2   1    1/2   0    0 |  4  ù
ê  2     0   -1     1    0 |  4  ú
ë -1/2   0    3/2   0    1 |  12 û

 R₂   > R₂/2

We make the pivot element into a 1 by dividing row 2 through by 2.

é  1/2   1    1/2   0    0 |  4  ù
ê  1     0   -1/2   1/2  0 |  2  ú
ë -1/2   0    3/2   0    1 |  12 û

 R₁   > R₁ - 1/2 R₂

 R₃   > R₃ + 1/2 R₂

Eliminate the entries directly above and below the pivot element.

   u   v     x      y     P   RHS 
é  0   1    3/4   -1/4    0 |  3  ù
ê  1   0   -1/2    1/2    0 |  2  ú
ë  0   0    5/4    1/4    1 |  13 û

There are no negative entries in the last row so we are finished with the pivoting process.

(5) READ THE OPTIMAL SOLUTION

The optimal solution to the dual (maximization) problem is read from the final table in the usual manner as

æ u = 2  ö
ç v = 3  ÷
è P = 13 ø

Recall the optimal solution of the primal problem appears under the slack variables in the last row of the final simplex table associated with the dual problem. The optimal solution is colored blue.

æ x = 5/4 ö
ç y = 1/4 ÷
è C = 13  ø

Note that the maximum value of P is equal to the minimum value of C as promised by the fundamental theorem.

Exercises

(1) Minimize C = 2x + 5y subject to the constraints

æ  x + 2y  ³  4 ö
ç 3x + 2y  ³  6 ÷
ç       x  ³  0 ÷
è       y  ³  0 ø

 Dual problem
 Initial table for dual problem.
 First pivot operation.
 Second pivot operation.
 Solution to the dual problem.
 Solution to the primal problem.