438 ACTIVITY 6: Putting Linear Programming Problems into Standard Form

WHY:

This activity is designed to help you understand the process of putting linear programming problems into standard form. This form makes the problems easier to solve, especially when they are too large to solve by hand. We will learn to use the computer to solve LP problems later in the semester and the software requires that the problem be in standard form.

INFORMATION:

Slack Variable

Let g(X) <= b be a constraint inequality. A variable x with the property that g(X) + x = b is called a slack variable.

Surplus Variable

Let h(X) >= b be a constraint inequality. A variable y with the property that h(X) - y = b is called a surplus variable.

Unrestricted Variable

A variable is unrestricted if it is allowed to take on positive, negative or zero values.

Standard Form

A Linear Programming problem is in standard form if the objective function is minimized, the constraints are all equalities with right sides >= 0, and all the variables are nonnegative.

METHODOLOGY:

A Simple Example

Scenario: Set up exercise 1.6 in standard form.

This problem can be written as follows:

             maximize        10y1 + 300y2
             subject to:    0.2y1 +  30y2 <= 0.05
                            1.5y1 +  35y2 <= 0.07
                               y1= 0, y2 >= 0

1. Change to Minimize

Change the objective function to - minimize -10y₁ - 300y₂

2. Make Right Side >= 0

The right hand sides of the constraints are already nonnegative.

3. Add Slack/Surplus Variables

Since the constraints are <= we need to add slack variables y₃ and y₄ to make the constraints equalities, as follows:

                    0.2y1 +  30y2 + y3       = 0.05
                    1.5y1 +  35y2       + y4 = 0.07

4. Replace Unrestricted Variables

There are no unrestricted variables. They are all nonnegative.

5. Check answer

Let us rewrite the problem and check its format.

          - minimize     -10y1 - 300y2
          subject to     0.2y1 +  30y2 + y3       = 0.05
                         1.5y1 +  35y2       + y4 = 0.07
                    y1 >= 0, y2 >= 0, y3 >= 0, y4 >= 0

DISCUSSION:

1. Change to Minimize

Theorem 1.3.2 verifies that the solution to maximizing a function is the same as the negative of the solution to minimizing the function. Since most software programs for solving linear programming problems assume that all problems are either all to be minimized or all to be maximized, we choose to put them all in the minimize form. When we have to change a problem to put the objective function in minimize form, we must remember to negate the value of the objective function after plugging in the solution.

2. Make Right Side >= 0

3. Add Slack/Surplus Variables

Since it is easier to solve a system of equations than a system of inequalities, we change the contraints to equalities by adding nonnegative slack variables to <= constraints, or subtracting nonnegative surplus variables from >= constraints. These variables often have nonzero values in the final solution, and represent the unused capacity in the process we are modeling. The mathematical effect of introducing additional variables into a problem is to increase the dimension of the solution space.

4. Replace Unrestricted Variables

Since we require all variables to be nonnegative, we must replace any variables which could take on negative values with the difference of nonnegative variables. Theorem 1.3.4 justifies this process. Replacing a single variable with the difference of two variables also increases the dimension of the solution space. It ensures that the solution and the sequence of points leading up to it will always be in the nonnegative orthant (region of Rn where all coordinates are >= 0).

5. Check Answer

After making the above changes, you should always rewrite the problem in its final standard form and check that the objective function is minimized, the constraints are all equalities with nonnegative right hand sides, and that all the variables are restricted to nonnegative values. If these conditions are satisfied, the problem is in standard form.

Example of the Standard Form Methodology

See example 1.10 on page 75.

LEARNING OBJECTIVES:

1. Understand the methodology for putting a linear programming problem into standard form.
2. Discover the meaning of slack and surplus variables in real problems.
3. Discover that learning is fun.

PERFORMANCE CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.
   • Completeness
   • Clarity
   • Depth
2. The depth of understanding of the standard form methodogy
3. Success in applying the methodology to homework and quiz problems.

RESOURCES:

1. Section 1.3: Strategic Mathematics, especially example 1.10.
2. 30 minutes

PLAN:

1. Choose roles if you have not already done so.

MODEL:

CRITICAL THINKING QUESTIONS:

These will be provided in class.

SKILL EXERCISES:

1. Put the following problem in standard form:

   
        maximize     x1 + x2 + x3 + x4
        subject to   x1 + x2             >=  4
                          x2 + x3        >=  8
                               x3 + x4   >= -1
                  x2 >= 0, 0 <= x3 <= 6, x4 <= 0