Standard 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.

- 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.

- 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.

- 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.

Minimize C = -2x + y subject to the constraints

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

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 ø |

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 û |

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 ù ê |
R |

é 1 2 1 0 0 | 6 ù ê |
R R |

é 0 4/3 1 -1/3 0 | 2 ù ê |

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 ø |

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

Minimize C = 8x + 12y subject to the constraints

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

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 û |

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 |
R |

é 1/2 |
R R |

é 1/2 |

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 ù ê |
R |

é 1/2 1 1/2 0 0 | 4 ù ê |
R R |

u v x y P RHS é 0 1 3/4 -1/4 0 | 3 ù ê |

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 ø |

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

| Table of Contents | | Previous | | Next |