Chapter 4

LINEAR PROGRAMMING

• Introduction
• Concepts and Methods
  • Concepts and Geometric Interpretation
  • General Statement of the Linear Programming Problem
  • Slack and Surplus Variables
  • Feasible and Basic Feasible Solutions of the Constraint Equations
  • Optimization with the Simplex Method
  • Simplex Tableau
  • Mathematics of Linear Programming
  • Degeneracy
  • Artificial Variables
• Formulating and Solving Problems
  • Formulating the Linear Programming Problem-A Simple Refinery
  • Solving the Linear Programming Problem for the Simple Refinery
• Sensitivity Analysis
• Changes in the Right Hand Side of the Constraint Equation
• Changes in the Coefficients of the Objective Function
• Changes in the Coefficients of the Constraint Equations
• Addition of New Variables
• Addition of More Constraint Equations
• Closure
• Selected List of Texts on Linear Programming and Extensions
• References
• Problems

   As the name indicates, all of the equations that are used in linear programming must be linear.  Although this appears to be a severe restriction, there are many problems that can be cast in this context.  In a linear programming formulation, the equation that determines the profit or cost of operation is referred to as the objective function.  It must have the form of the sum of linear terms.  The equations which describe the limitations under which the system must operate are called the constraints.  The variables must be non-negative, i.e., positive or zero only.

     The best way to introduce the subject is with an example. This will give some geometric intuition about the mathematical structure of the problem and the way this structure can be used to find an optimal solution.

Example 4-1

A chemical company makes two types of small, solid fuel rocket motors for testing; for motor A the profit is $3.00 per motor, and for motor B the profit is $4.00 per motor.  A total processing time of 80 hours per week is available to produce both motors.  An average of four hours per motor is required for A, but only two hours per motor is required for B.  However, due to hazardous nature of the material in B, a preparation time of five hours is required per motor, and a preparation time of two hours per motor is required for A.  The total preparation time of 120 hours per week is available to produce both motors. Determine the number of each motor that should be produced to maximize the profit.

Solution: The objective function and constraint equations for this case are:

Maximize:   3A + 4B                 Profit

Subject to:  4A + 2B < 80         Processing Time

        2A + 5B < 120       Preparation Time

          A , B > 0

It would be tempting to make all B motors using the preparation time limitation 120/5 = 24 for a profit of $96.  If all A motors were made, there is a processing time limitation 80/4 = 20 for a profit of $60.  However, there is a best solution, and this can be seen from Figure 4-1.  The small arrows show the region enclosed by the constraint equations that is feasible for the variables.   For the processing time and preparation time, any values of the variables lying above the lines violate the constraint equations.  Consequently feasible values must lie on or inside the lines and the A and B axes (because A and B must be non-negative).   This is called the feasible region.  The objective function is shown in Figure 4-1 for P = 96, and this is the one of the family of lines:

3A + 4B  =  P

or

  A =  -(4/3)B + P/3

where P can increase as long as the values of the variables A and B stay in the feasible region.  By increasing P, the profit equation shown above moves up with a constant slope of - 4/3, and P reaches the maximum value in the feasible region at the vertex A = 10, B = 20, where P = $110.

     Another geometric representation of the profit function and constraints is shown in Figure 4-2.  The profit function is a plane, and the highest point is the vertex A = 10, B = 20.  The intersection of the profit function and planes of  P = constant give a line on the profit function plane as shown for P = 96.  The projection of this line on the response surface (the A-B plane) is the same line shown in Figure 4-1 for P = 96.   This diagram emphasizes the fact that the profit function is a plane, and the maximum profit will be at the highest point on the plane and located on the boundary at the intersection of constraint equations, a vertex.

     This example can be used to illustrate infeasibility also, i.e., no feasible solution to linear programming problems.  For example, if there were constraints on A and B such that A > 21 and B > 25, then there would be no solution, for the processing and preparation time constraints could not be satisfied.  Although it is obvious here that A and B could not have these values, it is not unusual in large problems to make a mistake and have the linear programming code return the result INFEASIBLE SOLUTION - the constraints are inconsistent.  Almost always a blunder has been made, and the constraints do not represent the process.  However, in large problems the blunder may not be obvious, and some effort may be required to find the error.

There are several ways to write the general mathematical statement of the linear programming problem.  First, in the usual algebraic notation:

Objective Function:

Optimize:      c₁x₁ = c₂x₂ + ... + c_nx_n                        (4-1a)

Constraint Equations:

Subject to:    a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n  >   b₁        (4-1b)

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n  >   b₂

. . .                   . . .                   . . .

. . .                   . . .                   . . .

a_m1x₁ + a_m2x₂ + ... + a_mnx_n  >  b_m

x_j > 0   for j = 1,2,...n                            (4-1c)

We seek the values of the x_j's that optimize (maximize or minimize) the objective function, equation (4-1a).  The coefficients, c_j's, of the x_j's are referred to as cost coefficients. These can be positive and negative depending on the problem.  Also the values of the x_j's must satisfy the constraint equations, equation (4-1b), and be non-negative, equation (4-1c).

     There are more unknowns than constraint equations after the inequalities have been converted to equalities using slack variables.  There will be m positive x_j's that optimize the objective function and the remaining (n - m) x_j's will be zero.  In a chemical or refinery process, the independent variables can be flow rates, for example; and the constraint equations can be material and energy balances, availability of raw materials, limits on process unit capacities, demands for products, etc.

     The general formulation can also be written as:

Matrix notation is another convenient method of writing the above.

Optimize: c^T x                                                         (4-3a)

Subject to: Ax > b                                                   (4-3b)

x > 0                                                   (4-3c)

where

c^T = [ c₁,c₂,...c_n ]

x^T = [ x₁,x₂,...x_n ]

     The constraint equations given above have been written as inequalities. However, linear programming requires the constraints be equalities. In the next section, the use of slack and surplus variables are described to convert the inequalities to equalities.

In example 4-1 the constraint equations were inequalities, and the graphical method of locating the optimum was not affected by the constraints being inequalities. However, the computational method to determine the optimum, the Simplex Method, requires equality constraints. As was done in Chapter 2, the inequalities are converted to equalities by introducing slack and surplus variables. This is illustrated by converting the inequality equation (4-4), to an equality, equation (4-5).

x₁ + x₂ < b                                         (4-4)

Here a positive x₃ is being added to the left hand side of equation (4-4), and x₃ is the slack variable.

x₁ + x₂ + x₃ = b                                 (4-5)

If the inequality had been of greater than or equal to type, then a surplus variable would have been subtracted from the left-hand side of the equation to convert it to an equality.

     In linear programming it is not necessary to use x₃², as in Chapter 2 since the computational method to find the optimum, the Simplex Method, does not allow variables to take on negative values. If the slack variable is zero, as it is in some cases, the largest value of the sum of the other variables (x₁ + x₂) is optimum, and the constraint is tight or active. If the slack variable is positive, then this would represent a difference, or slack, between the optimum values of (x₁ + x₂) and the total value that (x₁ + x₂) could have. In this case the constraint is loose or passive.

Now let us focus on the constraint equation set alone, written as equalities (i.e., slack and surplus variables have been added), and discuss the possible solutions that can be obtained. This set can be written as:

A x = b                                             (4-6)

where there are m equations and n unknowns (for convenience using n again, which now would include the slack and surplus variables also).

     A number of solutions can be generated for this set of linear algebraic equations by selecting (n - m) of the x_j's to be equal to zero. In fact, this number can be computed using the following formula(9):

Thus, a basic solution of the constraint equations is a solution obtained by setting (n - m) variables equal to zero and solving the constraint set for the remaining m variables. From this set of basic solutions, the group of solutions are selected where the values of the variables are all nonnegative. This can be estimated by the following formula (18):

Approximate number of basic feasible solutions   =  2m                                                  (4-8)

Thus, a nondegenerate basic feasible solution is a basic solution where all of the m variables are positive. A solution of m variables that are all positive is called a basis in the linear programming jargon.

     Let us focus on the objective function, equation (4-1a), now that we have a set of basic feasible solutions from the constraint equations. It turns out that one of the basic feasible solutions is the minimum of the objective function, and another one of these basic feasible solutions is the maximum of the objective function. The Simplex Algorithm begins at a basic feasible solution and moves to the maximum (or minimum) of the objective function stepping from one basic feasible solution to another with ever increasing (or decreasing) values of the objective function until the maximum (or minimum) is reached. The optimum is found in a finite number of steps, usually between m and 2m (7).

     We will need to know how to obtain the first basic feasible solution and how to apply the Simplex Algorithm. Also, it will be seen that when the maximum (or minimum) is reached, the algorithm has an automatic stopping procedure. Having briefly described the Simplex Method, let us give the procedure, illustrate its use with an example, and present some of the mathematical basis for the methodology in the next section.

    The Simplex Method is an algorithm that steps from one basic feasible solution (intersection of the constraint equations or vertex) to another basic feasible solution in a manner to have the objective function always increase or decrease. Without attempting to show a model associated with the following linear programming problem (2), let us see how the algorithm operates.

Example 4-2

For the following linear programming problem, convert then constraint equations to equality constraints using slack variables:

Maximize:      x₁ + 2x₂

Subject to:    2x₁ + x₂ < 10

  x₁ + x₂ < 6

-x₁ + x₂ < 2

-2x₁ + x₂ < 1

   x₁,  x₂ > 0

When the slack variables are inserted, the constraint equations are converted to equalities, as shown below:

Maximize:         x₁+ 2x₂                              =   p

Subject to:     2x₁ +  x₂ + x₃                        = 10

   x₁ +  x₂          + x₄               =   6

  -x₁ + x₂                 + x₅         =  2

-2x₁ + x₂                        + x₆  =  1

x_j > 0,       j = 1,2,...,6.

where p represents the value of the objective function.

    There are six variables in the set of four constraint equations in example 4-2. To generate basic solutions, two of the variables are set equal to zero, and the equations are solved for the remaining four variables for the solution. This has been done (2), and all of the basic feasible solutions were selected from the basic solutions and listed in Table 4-1. These correspond to the vertices of the convex polygon A-B-C-D-E-F, as shown in Figure 4-3. Also shown in Table 4-1 are the values of the objective function evaluated for each basic feasible solution. As can be seen, the maximum of the objective function is at the basic feasible solution, x₁ = 2, x₂ = 4 (vertex D); and the minimum is at the basic feasible solution, x₁ = 0, x₂ = 0 (vertex A). .

     The number of basic solutions is given by equation (4-7). For n = 6 and m = 4 the number of basic solutions is 15. The approximate number of basic feasible solutions given by equation (4-8) is eight, which is close to the actual number of six. One of the basic solutions of the constraint equations is obtained by setting x₁ = x₄ = 0, and the result is:

x₁ = 0,        x₂ = 6,        x₃ = 4,        x₄ = 0,        x₅ = - 4,     and      x₆ = -5

Here two of the four values of the variables are negative.

     Referring to Table 4-1 and Figure 4-3 and comparing the variables in a basis with those in an adjacent basis, it is seen that each have all but one nonzero variable in common. For example, to obtain basis B from basis A it is necessary to remove x₆ from the basis (i.e., set x₆ = zero) and bring x₂ into the basis (i.e., solve for x₂ ¹ 0). The Simplex Method does this and moves from one basic feasible solution to another. Each time it moves in a direction of an improved value of the objective function. This is the key to the Simplex Algorithm. To move in this fashion only requires the use of Gaussian elimination applied to the constraints and then to the objective function to determine its new improved value.

The procedure to solve a linear programming problem using the Simplex Algorithm to maximize the objective function is:

1. Place the problem in a linear programming format with linear constraint equations and linear objective function.
2. Introduce slack and surplus variables to convert inequalities to equalities, and adjust the constraint equations to have positive right hand sides.
3. Select an initial basic feasible solution. If all of the constraint equations were inequalities of the less than or equal to form, the slack variables can be used as the initially feasible basis.
4. Perform algebraic manipulations to express the objective function in terms of variables that are not in the basis, i.e., are equal to zero. This determines the value of the objective function for the variables in the basis.
5. Inspect the objective function and select the variable with the largest positive coefficient to bring into the basis, i.e., make nonzero. If there are no positive coefficients, the maximum has been reached (automatic stopping feature of the algorithm).
6. Inspect the constraint equations to select the one to be used for algebraic manipulations to change the variable in the basis. The selection is made to have positive right-hand sides from the Gaussian elimination. This is necessary to guarantee that all of the variables in the new basis will be positive. Use this equation to eliminate the variable selected in step 5 from all of the other constraint equations.
7. Use the constraint equation selected in step 6 to eliminate the variable selected in step 5 from the objective function. This moves one of the variables previously in the basis to the objective function, and it is dropped from the basis, i.e., set equal to zero. Also this determines the new value of the objective function.
8. Repeat the procedure of steps 5 through 7 until all coefficients in the objective function are negative, and stop. If the procedure is continued past this point, then the value of the objective function would decrease. This is the automatic stopping feature of the algorithm.

     The Simplex Algorithm will be applied to example 4-2 to illustrate the computational procedure. The first two steps have been completed, and the slack variables will be used as the initial feasible basis (Step 3).

Example 4-3

Apply the Simplex Method to the linear programming problem of example 4-2 using the slack variables as the first basic feasible solution.

maximize:       x₁ + 2x₂                           = p          p = 0

subject to:    2x₁ +    x₂ + x₃                   = 10       x₃ = 10

  x₁ +   x₂        + x₄            = 6         x₄  = 6

-x₁ +   x₂            + x₅         = 2         x₅ = 2

-2x₁ +  x₂                  + x₆  = 1         x₆ = 1

      x₁ = 0

      x₂ = 0

     Continuing with the procedure, x₂ is the variable in the objective function with the largest positive coefficient. Thus, increasing x₂ will increase the objective function (Step 5). The fourth constraint equation will be used to eliminate x₂ from the objective function (Step 6). The variable x₂ is said to enter the basis, and x₆ is to leave.

     Proceeding with the Gaussian elimination gives:

Maximize:     5x₁                            -2x₆   = p - 2       p = 2

Subject to:    4x₁        + x₃               - x₆ = 9            x₃ = 9

3x₁              + x₄         - x₆ = 5            x₄ = 5

   x₁                    + x₅  - x₆ = 1            x₅ = 1

-2x₁ + x₂                    + x₆ = 1            x₂ = 1

         x₁ = 0

         x₆ = 0

The nonzero variables in the basis are x₂, x₃, x₄, and x₅; and the objective function has increased from p = 0 to p = 2.

     The procedure is repeated (step 8) selecting x₁ to enter the basis. The third constraint equation is used, and x₅ leaves the basis. Performing the manipulations gives:

Maximize:                          - 5x₅ + 3x₆  =  p - 7            p = 7

Subject to:               x₃      - 4x₅ + 3x₆  =  5                 x₃ = 5

                x₄ - 3x₅ + 2x₆  =  2                  x₄ = 2

x₁                 +    x₅   - x₆ =  1                  x₁ = 1

      x₂           + 2x₅   - x₆ =  3                    x₂ = 3

    x₅ = 0

    x₆ = 0

The procedure is repeated, and x₆ is selected to enter the basis. The second constraint equation is used, and x₄ leaves the basis. The results of the manipulations are:

Maximize:                    - 3/2 x₄ - 1/2 x₅          =  p - 10          p = 10

Subject to:               x₃ - 3/2 x₄ + 1/2 x₅         =   2                x₃ = 2

                 1/2 x₄ - 3/2 x₅ + x₆   =  1                 x₆ = 1

x₁            + 1/2 x₄ - 1/2 x₅        =  2                 x₁ = 2

     x₂       + 1/2 x₄ + 1/2 x₅        =  4                 x₂ = 4

             x₄ = 0

             x₅ = 0

     All of the coefficients in the objective function are negative for the variables that are not in the basis. If x₄ or x₅ were increased from zero to a positive value, the objective function would decrease. Thus, the maximum is reached, and the optimal basic feasible solution has been obtained.

     Referring to Table 4-1 and Figure 4-3 for the set of basic feasible solutions, it is seen that the Simplex Method started at vertex A. The first application of the procedure stepped to the adjacent vertex B, with an increase in the objective function to 2. Proceeding, the Simplex Method then moved to vertex C, where the objective function increased to 7. At the next application of the algorithm, the optimum was reached at vertex D with p = 10. At this point the application of the Simplex Method stopped since the maximum had been reached.

     Let us use this example to demonstrate that the Simplex Method can be used to find the minimum of an objective function by only slightly modifying the logic of the algorithm for maximizing the objective function. If we begin by minimizing the objective function given in the last step of example 4-3, the largest decrease in the objective function is made by selecting x₄ to enter the basis (Step 5), i.e., selecting the variable which is not in the basis and whose coefficient is the largest in absolute value and negative. Then select the second constraint equation for the manipulations to have positive right hand sides of the constraints. This has x₄ entering the basis, and x₆ leaving the basis. The results are the same as in the next to last step of the example. Proceeding, x₅ is selected to enter the basis, the third constraint equation is used for the manipulations, and x₁ leaves the basis. The results are the same as the second step of the example. Continuing, x₆ is selected to enter the basis, the fourth constraint equation is used for the manipulations, and x₂ leaves the basis. The results are the same as the first step in the example, and all of the coefficients of the variables in the objective function are positive for the variables not in the basis. The minimum has been reached, because if either x₁ or x₂ were brought into the basis, i.e., made positive, the objective function would increase.

     Thus, the Simplex Algorithm applies for both maximizing or minimizing the objective function. The logic of the algorithm is essentially the same in both cases, and it only differs in the selection of the variable to enter the basis, i.e., largest positive coefficient for maximizing or the largest in absolute value and negative for minimizing.

     With this example we have illustrated the computational procedure of the Simplex Algorithm. Also, we have seen that a solution of the constraints gives the maximum of the objective function, and another solution gives the minimum of the objective function. These results can be proven mathematically to be true for the linear programming problem stated as equation (4-1), and the details are given in texts devoted to linear programming. In the following section we will give a standard tabular method for the Simplex Method, and then the key theorems of linear programming will be presented along with a list references where more details can be found on mathematical aspects of linear programming.

    In using the Simplex Method, it is not necessary to write the x _j symbols when doing the Gaussian elimination procedure, and a standard method for hand computations has been developed which uses only the coefficients of the objective function and constraints in a series of tables. This is called the Simplex Tableau, and this procedure will be illustrated using the problem given in Example 4-3.

  The Simplex Tableau for the three applications of the Simplex Algorithm of Example 4-3 is shown in Figure 4-4. In this table, dots have been used in places which have to be zero, as opposed to just turning out to be zero. Also, the objective function has been set equal to -y, because the tableau procedure minimizes the objective function; and is called z, i.e.,  z = -y = -x₁ - 2x₂. Then the objective function is included in the last row of the tableau as -z - x₁ - 2x₂ = 0 to have the same form as the constraint equations. Iteration 0 in Table 4-4 is the initial tableau.

     The slack variables are the initially feasible basis in this example, and the Simplex Algorithm first locates the smallest coefficient in the objective function of the variables not in the basis. In this case it is x₂ as shown in Figure 4-4 with a coefficient of -2; x₂ will enter the basis, i.e., becomes positive. A pivotal element is located to insure the next basis is feasible using a minimum ratio test, i.e., selecting the smallest value of (10/1, 6/1, 2/1, 1/1), and the pivotal element is indicated as an asterisk identifying the pivotal row used for the Gaussian elimination to move to iteration 1, with x₆ leaving the basis.

     The above procedure is repeated for two more iterations, as shown in Figure 4-4. The pivotal elements are indicated by an asterisk, having been located by the minimum ratio test. The procedure ends when the values in the objective function row are all positive, for this is a minimizing problem. Also, a comparison of the results in Figure 4-4 with those in Example 4-3 shows the concise nature of the Simplex Tableau. In addition, if a pivotal element can not be located using the minimum ratio test, this means that the problem has an unbounded solution or a blunder has been made.

     The Simplex Tableau procedure can be used effectively for hand calculations when artificial variables are employed to start the solution with an initially feasible basis and to identify problems such as degeneracy. The topics of degeneracy and artificial variables will follow the discussion of the mathematics of linear programming.

The mathematics of convex sets and linear inequalities has to be developed to prove the theorems that establish the previous procedure for locating the optimal solution of the linear programming problem. This is done in many of the standard texts devoted to the subject and is beyond the scope of this brief discussion. However, the appropriate theorems will be given with an explanation, to convey these concepts. Those who are interested in further details are referred to standard works such as Garvin (3) or Gass (7).

     A feasible solution, is any solution to the constraint equations, equation (4-1-b,c); and also, is a convex set. A convex set is illustrated in Figure 4-5a, for two dimensions and is a collection of points such that if it contains any two points A and B, is also contains the straight line AB between the points. An example of a non-convex set is shown in Figure 4-5b. Also an extreme point or vertex of a convex set is a point that does not lie on any segment joining two other points in the set. The important theorem relating convex sets with feasible and basic feasible solutions is:

The collection of feasible solutions, constitutes a convex set, whose extreme points correspond to basic feasible solutions. (4)

     In the proof of the above theorem it is shown that a linear combination of any two feasible solutions is a feasible solution; and hence, lies on a straight line between the two. Thus, this constitutes a convex set. To prove that a basic feasible solution is an extreme point, it is assumed that a basic feasible solution can be expressed as a linear combination of feasible solutions. Then it is shown by contradiction that this is impossible. Thus, it must be an extreme point.

     The next important theorem is an existence theorem:

If a feasible solution exists, then a basic feasible solution exists. (5)

This is proved by showing that a basic feasible solution can be constructed from a feasible solution.

     The next theorem relates the maximum or minimum of the objective function to the basic feasible solutions of the constraint equations.

If the objective function possesses a finite minimum, then at least one optimal solution is a basic feasible solution. (6)

This theorem can be proven by writing any point P as a convex combination of extreme points. The objective function is a linear function, and it can be written as a sum of linear terms obtained by substituting the convex combination for the point P. Then the value of the objective function evaluated at P is less than that obtained by substituting the minimum value of the objective function, for each value of the objective function in the linear combination. Thus, there is an extreme point at which the objective function assumes its minimum value. Also, one can be located where the objective function obtains its maximum value using the same analysis.

     To formalize the simplex computational procedure consider the set of equations with a basic feasible solution x = (x₄, x₅, x₆).

Maximize:     c₁x₁ + c₂x₂ + c₃x₃                                 = p_o      (4-9a)

Subject to :  a₁₁x₁   +  a₁₂x₂   +  a₁₃x₃   +  x₄             = b₁

a₂₁x₁  +  a₂₂x₂   +  a₂₃x₃          +  x₅       = b₂      (4-9b)

a₃₁x₁  +  a₃₂x₂   +  a₃₃x₃              +  x₆   = b₃

x_j > 0      i = 1,2, ...6

If c₁ is the largest positive coefficient and b₁/a₁₁ is the smallest positive ratio, then x₁ enters the basis and x₄ leaves the basis. Performing the elimination the result is:

Maximize:     (c₂ - c₁a₁₂/a₁₁)x₂ + (c₃ - c₁a₁₃/a₁₁)x₃ - (c₁a₁₄/a₁₁)x₄                = p_o - c₁b₁/a₁₁ =  p₁                  (4-10a)

Subject to:    x₁      +  a₁₂/a₁₁x₂              +  a₁₃/a₁₁x₃     +  a₁₄/a₁₁x₄              = b₁a₁₁

(a₂₂-a₂₁a₁₂/a₁₁)x₂ +(a₂₃-a₂₁a₁₃/a₁₁)x₃ - a₂₁a₁₄/a₁₁x₄   + x₅       = b₂-a₂₁b₁/a₁₁

(a₃₂-a₃₁a₁₂/a₁₁)x₂ +(a₃₃-a₃₁a₁₃/a₁₁)x₃ - a₃₁a₁₄/a₁₁x₄       + x₆   = b₃-a₃₁b₁/a₁₁                                    (4-10b)

If p₁ > p_o then there is an improvement in the objective function, and the solution is continued. If p₁ < p_o then no improvement in the objective function is obtained, and x is the basic feasible solution that maximizes the objective function. The following theorem given by Gass (7) is:

If for any basic feasible solution x_k = (x₁, x₂, ... x_m ) the condition p(x_k ) > p(x_j ) for all j = 1,2,...n (j¹ k) hold, then x_k is a basic feasible solution that maximized the objective function.

     The proof of this theorem is similar to that of the previous theorem. Also a corresponding result can be obtained for the basic feasible solution that minimizes the objective function.

     Further information is given in the textbooks by Garvin(6), and Gass(7), and others listed in the table on selected texts given at the end of the chapter. These books give detailed proofs to the key theorems and other related ones.

     In the Simplex Method there is an improvement in the objective function in each step as the algorithm converges to the optimum. However, a situation can arise where there is no improvement in the objective function from an application of the algorithm, and this is referred to as degeneracy. Also there is a possibility that cycling could occur, and the optimum would not be reached. Degeneracy occurs when the right hand side of one of the constraint equations is equal to zero, and it is selected for the algebraic manipulation to change variables in the basis and evaluate the objective function. Graphically this occurs when two vertices coalesce into one vertex. It is reported (6) that it is not unusual for degeneracy to occur in the various applications of linear programming. However, there has not been a case of cycling reported. An example of cycling has been constructed, and a procedure to prevent cycling has been developed. However, these are not usually employed. The following example from Garvin (6) illustrates degeneracy, and an optimal solution is found even if it does occur.

Example 4-4

Solve the following problem by the Simplex Method.

Maximize:     2x₁ +   x₂

Subject to:      x₁ + 2x₂  < 10

  x₁ +   x₂  <   6

  x₁  -   x₂  <  2

  x₁  - 2x₂  <   1

2x₁  - 3x₂  <   3

     A graphical representation of the constraint equations are shown in Figure 4-6. It shows that the last three constraint equations all intersect at vertex C. Vertex C is said to be overdetermined. If the constraint equation x₁ - 2x₂ < 1 had been 0.9x₁ - 2x₂ < 1, there would have been two separate vertices, as shown in Figure 4-6. Degeneracy occurs when two or more vertices coalesce into a single vertex.

     To illustrate what happens, the Simplex Algorithm will be started at vertex A and move through B and C to D, where the optimal solution is p = 10 for x₁ = 4 and x₂ = 2. Using the slack variables as the initially feasible basis gives:

  Vertex A

2x₁ +   x₂                                = p               p = 0

  x₁ + 2x₂ + x₃                        = 10            x₃ = 10

  x₁ +  x₂         + x₄                  = 6             x₄ = 6

  x₁ -   x₂              + x₅             = 2             x₅ = 2

   ®    x₁ - 2x₂                   + x₆       = 1              x₆ = 1

2x₁ - 3x₂                        + x₇  = 3              x₇ = 3

x₁ is selected to enter the basis, and x₆ leaves the basis.

     Performing the algebraic manipulations, the following results are obtained for vertex B.

    Vertex B

      5x₂                   - 2x₆           = p - 2         p = 2

      4x₂ + x₃              - x₆           = 9             x₃ = 9

      3x₂       + x₄        - x₆           = 5             x₄ = 5

®    x₂            + x₅  -   x₆          = 1             x₅ = 1

x₁ - 2x₂                   +   x₆          = 1             x₁ = 1

®    x₂                    - 2x₆ +  x₇  = 1             x₇ = 1

x₂ is selected to enter the basis, and either the equation with x₅ or the equation with x₇ can be used for the algebraic manipulations. The following calculations use the equation with x₇ and then use the one with x₅ to illustrate the effect of these decisions. (In a computer program the decision would be made rather arbitrarily, e.g., by selecting the one with the lowest subscript.)

     Performing the algebraic manipulations to have x₇ leave the basis gives:

    Vertex C

                     + 8x₆ -  5x₇  =  p - 7                          p = 7

        x₃          + 7x₆  - 4x₇  =   5                             x₃ = 5

®          x₄     + 5x₆  - 3x₇  =  2                              x₄ = 2

                  x₅ +  x₆  -   x₇  =  0                              x₅ = 0

x₁                   - 3x₆ + 2x₇  =  3                              x₁ = 3

     x₂              - 2x₆ +   x₇  =  1                              x₂ = 1

The right hand side of the third constraint equation is zero, and this causes x₅ = 0 which contradicts the fact that variables in the basis are to be greater than zero. However, the procedure is to continue with the Simplex Method selecting x₆ to enter the basis, and the third constraint equation is used for the algebraic manipulations to have positive (or zero) right hand sides. x₅ leaves the basis, and the result is

Vertex C

                   - 8x₅      +  3x₇  = p - 7                           p = 7

         x₃       - 7x₅      +  3x₇  = 5                               x₃ = 5

®         x₄   - 5x₅      +  2x₇  = 2                               x₄ = 2

                       x₅ +  x₆  - x₇  = 0                               x₆ = 0

x₁                + 3x₅         - x₇  = 3                               x₁ = 3

     x₂           + 2x₅         - x₇  = 1                               x₂ = 1

There was no improvement in the objective function and the Simplex Method did not move from vertex C. The procedure is continued having x₇ enter the basis and x₄ leave the basis. The results of the algebraic manipulations are:

    Vertex D  

             - 3/2x₄   -    ½x₅               = p - 10           p = 10

         x₃ - 3/2x₄  +    ½x₅               = 2                  x₃ = 2

                  ½x₄   - 5/2x₅       + x₇  = 1                  x₇ = 1

                  ½x₄   - 3/2x₅ + x₆        = 1                  x₆ = 1

x₁             + ½x₄   + ½x₅               = 4                  x₁ = 4

     x₂        + ½x₄  - ½x₅                 = 2                  x₂ = 2

The maximum has been reached, because the coefficients of the variables in the objective function are all negative. The simplex algorithm was unaffected by the right hand side of one of the equations becoming zero during the application of the algorithm.

     Now returning to vertex B and selecting x₅ to enter the basis, the result of the manipulations is:

     Vertex C

                     - 5x₅ + 3x₆          = p - 7                      p = 7

        x₃         - 4x₅ + 3x₆         = 5                           x₃ = 5

®         x₄    - 3x₅ + 2x₆         = 2                           x₄ = 2

     x₂           +   x₅ -   x₆          = 1                           x₂ = 1

x₁                + 2x₅ -   x₆          = 3                           x₁ = 3

                     -   x₅ -   x₆ + x₇  = 0                          x₇ = 0

     Selecting x₆ to enter the basis and x₄ to leave the basis, the result of the manipulation is the optimum given at vertex D previously. Consequently using x₅ there is an improvement in the objective function, and one fewer applications of the Simplex Algorithm were required.

     Unfortunately, the effect of a constraint equation selection with degeneracy can not be predicted in advance for large problems, and an arbitrary selection is made, as previously mentioned. In conclusion, degeneracy is not unusual, but it has yet to affect the solution of linear programming problems in industrial applications.

    To start a linear programming problem it is necessary to have an initially feasible basis as required in Step 3 of the Simplex Method and as shown in equation 4-9b. In the illustrations up to now, we have been able to use the slack variables as the initially feasible basis. However, the constraints generally are not in such a convenient form, so another procedure is used, artificial variables. In this technique a new variable, an artificial variable, is added to each constraint equation to give an initial feasible basis to start the solution. This is permissible, and it can be shown that the optimal solutions to the original problem is the optimal solution to the problem with artificial variables. However, it is necessary to modify the objective function to ensure that all of the artificial variables leave the basis. This is accomplished by adding terms to the objective functions that consist of the product of each artificial variable and a negative coefficient that can be made arbitrarily large in magnitude for the case of maximizing the objective function. Thus, this will insure that the artificial variables are the first ones to leave the basis during the application of the Simplex Method.

     At this point it is reasonable to question if this would not be a significant amount of computations for convenience only. The answer would be yes if only one small linear programming problem was to be solved. However, this is not usually the case, and the margin for error is reduced significantly by avoiding manipulation of the constraint equations in a large problem. In fact, large linear programming codes only require the specification of the values of the coefficients in the objective function and the coefficients, right hand sides and the types of inequalities of the constraint equations to obtain an optimal solution. These programs can solve linear programming problems having thousands of constraints and thousands of variables (12). Consequently, developing a linear model of a plant or a process is the main effort required, and then one of the available general linear programming codes can be used to obtain the optimal solution. Also, most major companies have a group that includes experts in using linear programming, and also, there are firms that specialize in industrial applications of linear programming.

     The following example illustrates the use of artificial variables as they might be employed in a computer program. The technique is sometimes called the "big M method."

Example 4-5(8)

Solve the following linear programming problem using artificial variables.

Minimize:       x₁ + 3x₂

Subject to:     x₁ + 4x₂ > 24

5x₁ +  x₂ > 25

Slack variables x₃ and x₄ and artificial variables a₁ and a₂ are introduced as shown below. The artificial variables will be the initially feasible basis, because the slack variable would give negative values and algebraic manipulations would be required to have x₁ and x₂ be the initially feasible basis. In the objective function M is the coefficient of the artificial variables a₁ and a₂, and M can be made arbitrarily large to drive a₁ and a₂ from the basis.

Minimize:       x₁ + 3x₂             + Ma₁ + Ma₂    = c

Subject to:     x₁ + 4x₂ - x₃       +      a₁             = 24

5x₁ +  x₂        - x₄             +    a₂   = 25

The two constraints equations are used to eliminate a₁ and a₂ from the objective function. This is Step 4 in the Simplex Method, and the objective function is a large number, 49M, as shown below.

(1 - 6M)x₁ + (3 - 5M) x₂ + Mx₃ + Mx₄                    = c - 49M               c = 49M

             x₁   +             4x₂ -    x₃             + a₁            = 24                       a₁ = 24

           5x₁ +                 x₂          -      x₄          + a₂    = 25                       a₂ = 25

Applying the Simplex Algorithm, x₁ enters the basis since it has the negative coefficient that is largest in magnitude. The second constraint equation is used to perform the algebraic manipulations, and a₂ leaves the basis. Performing the manipulations gives:

(14/5 - 19/5M)x₂ + Mx₃ + (1/5 - 1/5M)x₄      - (1/5 - 6/5M)a₂   = c - 19M  - 5          c = 19M + 5

                19/5x₂       - x₃               + 1/5x₄ + a₁             - 1/5a₂  = 19                          a₁ = 19 

x₁            + 1/5x₂                            - 1/5x₄                     + 1/5a₂  = 5                           x₁ = 5

Continuing with the Simplex Algorithm, x₂ enters the basis. The first constraint equation is used for the algebraic manipulations, and a₁ leaves the basis. Performing the manipulations gives:

        14/19x₃ + 5/95x₄ + (-14/19 + M)a₁ + (-5/95 + M)a₂     = c - 19            

  c = 19

    x₂ - 5/19x₃ + 1/19x₄                + 5/19a₁           -    1/19a₂   = 5                              

x₂ = 5

x₁     + 1/19x₃ - 20/95x₄              -  1/19a₁            + 20/95a₂  = 4                              

x₁ = 4       

Now the terms containing the artificial variables a₁ and a₂ can be dropped from the objective function and the constraint equations. The reason is that they both have large positive coefficients in the objective function and will not reenter the basis. The problem is continued without them to reduce computational effort. However, for this problem the optimum has been reached, since all of the coefficients in the objective function are positive, and no further reduction can be obtained.

     In addition to the infeasible difficulty discussed at the beginning of this chapter, there is another problem that can be encountered in linear programming, an unbounded problem, which is usually caused by a blunder. In this situation, the constraint equations do not confine the variables to finite values. This is illustrated by changing the linear programming problem in Example 4-5 from one of minimizing x₁ + 3x₂ to maximizing x₁ + 3x₂ subject to the constraints given in the problem. The constraints are of the greater than or equal to type, and they are satisfied with values of x₁ > 4 and x₂ > 5. Then for maximizing the objective function, the values of x₁ and x₂ could be increased without bounds to have the objective function also increase without bounds. Thus, the problem is said to be unbounded.

top