Technical Chapter Five
Linear Programming
In chapter twelve in the textbook, we described a linear programming formulation of the aggregate-planning problem. This problem, and many others, can be solved by the methods described in this chapter. This technical chapter begins with a formulation of the product-mix problem and then provides graphical and simplex methods for solution of linear programming problems.
PRODUCT-MIX PROBLEM
For the sake of simplicity, suppose a furniture company can make only two types of products: tables and chairs. The company has limited resources of lumber, labor, and finishing capacity with which to produce these items. The management of the company would like to determine the best mix of products to make: all chairs, all tables, or some mix of chairs and tables. Management defines the best mix of products as the one which maximizes the total contribution to profit and overhead subject to the limited availability of resources already mentioned.
The product-mix problem can be formulated in mathematical terms as follows:
Let: X1 = the number of tables produced
X2 = the number of chairs produced
Both X1 and X2 are unknown variables to be determined by the solution of the linear programming problem. Also assume that the following unit production technology matrix is given. This matrix describes the transformation process used to convert the scarce resources (lumber, labor, and finishing capacity) into tables or chairs. For example, it takes 30 board feet to make one table and 20 board feet to make one chair. We also assume that the amount of scarce resources available is given: 120 board feet of lumber, 9 hours of labor, and 24 hours of finishing capacity.
RESOURCES USED PER UNIT PRODUCED
Tables
/Chairs
Lumber, board feet / 30 / 20Labor, hours / 2 / 2
Finishing capacity, hours / 4 / 6
If we multiply the values in the unit production technology matrix by the number of units produced and add over both products, we will obtain the total resources of each type required. These requirements must be less than the amount of resources available. Thus we have:
30X1 + 20X2≤ 120
2X1 + 2X2≤ 9
4X1 + 6X2≤ 24
Since 30 board feet are required for each table, 30X1 board feet will be required for X1 tables, as shown in the first constraint above. Likewise, 20X2 board feet are required to produce X2 chairs. The total amount of lumber required for both tables and chairs (30X1 + 20X2) must be less than or equal to the amount available (120). A similar logic can be used to derive the second and third constraints.
Management wishes to find the values of X1 and X2, which will maximize the contribution to profit and overhead. To formulate this objective function, we assume that each table contributes $10 and each chair $8 to profit and overhead. Then the total contribution for X1 tables and X2 chairs is
10X1 + 8X2
Finally, we require that X1 and X2 be nonnegative values, since we cannot produce a negative number of tables or chairs. Gathering together the constraints and objective function that we have specified, the product-mix problem can be summarized as follows:
Objective: max 10X1 + 8X2
Subject to: 30X1 + 20X2≤ 120
2X1 + 2X2 ≤ 9
4X1 + 6X2 ≤ 24
X1 ≥ 0, X2 ≥ 0
When this problem is solved by the methods described below, optimal values of X1 and X2 will be found. These optimal values, however, are a solution to the mathematical problem as stated and not necessarily a solution to the manager's original decision problem. The mathematical problem is always an abstraction of the manager's real problem; therefore the optimal solution must be carefully evaluated before a decision can be made.
In practice, a series of product-mix problems may be formulated and solved before the manager is satisfied. For example, suppose the optimal solution to our problem is to produce all tables and no chairs. Also assume that this solution conflicts with the marketing strategy in the company. Therefore, either the marketing strategy must be modified or the production constraints altered or other changes made in the formulation to make the mathematical solution consistent with the real decision problem. Even though the optimal solution to the product-mix problem is not implemented, it may provide important insights into possible coordination problems between marketing and production, possibly leading to further analysis and ultimate solution of the decision problem.
GENERAL LP PROBLEM
The problem that we have just formulated is a member of a class of general problems
called linear programming, or LP, problems - the notation for which follows:
Objective:
max C1X1 + C2X2 + . . . + CnXn
Subject to:
a11X1 + a12X2 + … + a1nXn ≤ b1
a21X1+ a22X2 + … + a2nXn ≤ b2
⋮⋮⋮⋮
am1X1+ am2X2 + … + amnXn ≤ bm
X1≥ 0, X2 ≥ 0, … , Xn ≥ 0
T5-1
In this formulation the Cj,aij, and bi values are given constants and the Xj are called decision variables. The problem is to find the values of the n decision variables (X1, X2 . . . , Xn) which maximize the objective function subject to the m constraints and the nonnegativity conditions on the Xj variables. The resulting set of decision variables which maximizes the objective function is called an optimal solution. In this problem “max” may be replaced by “min” and ≤ may be replaced by ≥ or = signs to obtain the general set of LP problems.
The general LP problem as formulated above is based on the following four assumptions:
1.Linearity. Both the objective function and the constraints must be linear functions of the Xj. This implies that no cross products, powers of Xj, or other nonlinearities are permitted in the problem. It also implies that resource utilization is proportional and additive, e.g., if it takes 2 hours to produce one table, it will take 4 hours to produce two tables.
2.Divisibility. The Xj variables are permitted to take on continuous values. Thus we can obtain a solution to the product-mix problem, for example, of 20.5 chairs and 30.2 tables. Sometimes the continuous solution can be rounded off or interpreted as the average production per day. In other cases, special integer programming problems must be formulated to provide integer solutions.
3.Nonnegativity. The decision variables must have nonnegative values. In many problems this assumption is natural and presents no difficulties. If negative values are needed, however, the LP formulation can be modified to handle these cases.
4.Certainty. All constants Cj, aij, and bi are assumed to have certain values. If these values are probabilistic, other special chance-constrained or stochastic programming problems can be formulated.
Although LP problems have some rather restrictive assumptions, a large class of real decision problems can still be solved by LP methods. In addition, LP methods sometimes form the nucleus for more advanced nonlinear, stochastic, or integer programming methods.
Linear programming can be used to solve a general class of resource- allocation problems including product-mix, blending, and scheduling problems. All these decision problems are concerned with finding the best allocation of scarce resources. In the product-mix problem, the scarce resources are allocated to the products; in the blending problem, the best mix of resource inputs to meet a prescribed product blend is determined; and in scheduling problems, available machine times may be allocated to the required products. Even in the aggregate planning problem, resources are allocated to regular time, overtime, inventory, or subcontracting in order to minimize the costs of meeting required demand. In each of these cases, scarce resource inputs are allocated among several economic activities. This is a general characteristic of most, if not all, LP problems.
Graphical Solution Method
The graphical solution method may be used to solve LP problems with two variables. Although two variables are not enough to describe real problems, the graphical method provides important insights into LP solution procedures. For illustration purposes, we will solve the product-mix problem formulated above.
The first step in the graphical procedure is to plot the constraint equations. The three constraints from the product-mix example are shown in Figure T5-1. Each constraint is plotted on the figure by first considering the ≤ sign as an = sign. The first constraint is thus plotted as the equation 30X1 + 20X2 = 120. By setting X1 = 0 in this equation, we have X2 = 6; and by setting X2 = 0, we have X1 = 4. These two coordinates are placed on the graph and connected with a straight line. The original constraint equation, however, includes all points smaller than or equal to the right-hand side. Thus all points to the left of the lines in Figure T5-1 are permitted by the constraints.
The intersection of points from all three constraint equations plus the nonnegativity conditions forms the feasible region shown in white in Figure T5-1. All points within this feasible region simultaneously satisfy all the LP constraints. The problem then is to find the one or more points (or solutions) in the feasible region which maximize the original objective function. This point(s) will be the optimal solution(s).
The optimal solution is found by graphing the objective function on the same graph as the feasible region. For illustration purposes, we have drawn the feasible region again in Figure T5-2 and plotted a series of objective functions or isoprofit lines on the graph. Each isoprofit line is obtained by setting the objective function equal to an arbitrary value. For example, suppose we arbitrarily set the objective function equal to 60. Then the line 10X1 + 8X2 = 60 is plotted just as we plotted the constraints. Since the value of the objective function is unknown, a series of arbitrary values is selected to generate a series of parallel isoprofit lines, as shown in Figure T5-2.
The problem now is to find the isoprofit line which has the largest profit and is still in the feasible region. This can be done by starting at the origin or any other point inside the feasible region and moving the isoprofit line out away from the origin parallel to itself until the last point in the feasible region is reached. In this example the last feasible point is the corner labeled c (X1 = 3, X2 = 1.5), which maximizes the value of the isoprofit line and is therefore the optimal solution to the LP problem.
The exact coordinates of the optimal solutions may be found by solving for the intersection of equations 1 and 2, which define the optimal corner c. These two equations in two unknowns are solved simultaneously for the values of X1 and X2. As a result, we find X1 = 3 and X2 = 1.5. Although X2 is a fractional number of chairs, this solution might still be perfectly realistic. For example, suppose we produce 3 tables and 1.5 chairs a day over a period of several weeks. The 1.5 chairs can then be interpreted as an average production rate per day.
The optimal solution will always occur on at least one corner point (or extreme point) of the feasible region. In the example, there was only one optimal solution because a single corner point was reached. If the isoprofit line had been parallel to a side of the feasible region, then two corner points and all the points in between would have been optimal solutions. In this case, we would have had alternative optimal solutions, different
values of X1 and X2 which yield the same value of the objective function.
The fact that the optimal solution occurs at one or more extreme points is exploited in LP methods. The simplex method, described next, is an adjacent- extreme-point method. It moves from one corner point to the next until an optimal solution is found. Since there are only a finite number of corner points but an infinite number of feasible solutions inside the feasible region, the general solution to linear programming problems is greatly simplified when only adjacent extreme points are examined.
SIMPLEX METHOD
The simplex method is a general algebraic method which can be used to solve LP problems with a very large number of variables and constraints. When more than a few variables and constraints are involved, the computerized simplex method is required. Nevertheless, for purposes of instruction, we shall illustrate the simplex method by hand computations. An understanding of the simplex method's mechanics facilitates interpretation of LP results.
With the simplex method, the problem must be put in a special format and specific computational rules must be followed. To illustrate, we will use the product-mix problem which has already been solved graphically.
The first step in the simplex method is to convert the LP problem to the proper format by changing all the inequality constraints into equalities. This is done by adding a slack variable to each constraint inequality, as shown below.
Objective:
max 10X1 + 8X2 + 0X3 + 0X4 + 0X5
Subject to: 30X1 + 20X2 + 1X3 + 0X4 + 0X5 = 120
2X1 + 2X2 + 0X3 + 1X4 + 0X5 = 9
4X1 + 6X2 + 0X3 + 0X4 + 1X5 = 24
X1 ≥ 0, X2 ≥ 0, X3 ≥ 0,X4 ≥ 0,X5 ≥ 0
In the first constraint, variable X3 is added to the left- hand side to take up the slack between the value of the original left-hand side and the right-hand side of the inequality. Then X3 must also be restricted to be nonnegative, so that it properly represents the slack on the left-hand side of the first constraint. Similarly, X4 and X5 are added as slack variables to the second and third constraints, respectively. Since we do not want these slack variables to affect the profit, they are entered with zero coefficients in the objective function. The revised problem will have exactly the same optimal solution for X1 and X2 as the original problem.
Now that the problem is in the required form for the simplex method, we can construct the first tableau. The term ``tableau'' refers to the special simplex tables which are constructed to keep track of the computations. The first tableau is shown in Figure T5-3.
The tableau is constructed by detaching the coefficients from the variables and displaying the resulting coefficients by themselves in the appropriate rows and columns of the tableau. For example, the first row in the body of the tableau is the first constraint equation, the second row is the second equation, and so on. In the right-hand column of the tableau, the right-hand side of the constraints is placed under the heading “Solution Quantity.” In every tableau, this column will represent the values of the Xj variables for the current solution. The particular Xj variables in the solution are shown in the box labeled “Solution Variables” on the left-hand side of the tableau. For example, the initial solution is X3 = 120, X4 = 9, X5 = 24. All variables not in the solution are always assumed to have zero values. Thus, X1 = 0 and X2 = 0 in the first tableau.
On the very top row of the tableau, the objective function coefficients are displayed corresponding to the columns represented by each Xj variable. For example, the profit coefficient of X1 is 10, which is written directly above the symbol X1. The values of the Cj which correspond to the solution variables are listed to the left of the solution variables in the tableau. In the first tableau, these Cj values are all zero, since only slack variables are in the initial solution.
FIGURE T5-3 First Tableau – Product Mix Problem Solution
Cj / 10 / 8 / 0 / 0 / 0/ Solution
Variables /
X1
/X2
/X3
/X4
/ X5 / SolutionQuantity
/ 0
0
0 /
X3
X4X5
/ 302
4 / 20
2
6 / 1
0
0 / 0
1
0 / 0
0
1 / 120
9
24
Zj
Cj - Zj / 0
10 / 0
8 / 0
0 / 0
0 / 0
0 / 0
Finally, the tableau has two rows on the bottom labeled Zj and Cj - Zj. The Zj row is computed by multiplying the Cj values on the left by the coefficients in each column and adding. For example, Z1 is computed as follows:
Z1 = 0(30) + 0(2) + 0(4) = 0
In the first tableau, the resulting values of Zj are zero, since all the Cj values are zero.
The last row in the tableau, Cj - Zj is the result of subtracting the Zj value we have just computed from Cj at the top of the tableau.
The Zj values can be interpreted economically as the gross profit due to introducing one unit of the corresponding Xj variable. For example, in column 1, if one unit of X1 is introduced to the solution, the value of X3 must be reduced by 30 to maintain the equality in the first row, X4 must be reduced by 2 to maintain the equality in the second row, and X5 must be reduced by 4 to maintain the equality in the third row. Therefore, the coefficients in the X1 column represent the physical rates of substitution between X1 and each of the variables in the solution. When these substitution rates are multiplied by their respective profit coefficients, the result is Z1, the gross profit lost when one unit of X1 is introduced. The profit gained by introducing one unit of X1, however, is the value C1 = 10. Therefore, the value C1 - Z1 represents the net profit gained by introducing one unit of X1. It stands to reason, then, that introducing either X1 or X2 into the solution of the first tableau will improve the net profit because the C1 - Z1 and C2 - Z2 values are positive.
All the facts required to solve the LP problem are represented in the tableau: the current solution values on the right, the substitution ratios of each variable for the others in the tableau body, and the net profit contribution for increasing the value of each variable on the bottom.
As we mentioned earlier, the simplex method works by moving from one corner of the feasible region to an adjacent corner. The first tableau represents corner a at the origin in Figure T5-2, because we have X1 = 0, X2 = 0, in the tableau. All three constraints have slack in them (X3 = 120, X4 = 9, and X5 = 24) at the origin. There are only two possible ways to move from the origin to an adjacent extreme point without ``cutting across'' the feasible region. One way to move is to increase X1 until we reach corner d, at a value of X1 = 4. At this point, we will also have X3 = 0, since there will no longer be slack in constraint number 1. The other adjacent extreme point can be reached by increasing X2 until X2 = 4 at corner e. In this case X5 = 0, since constraint 3 no longer has slack.
The simplex method selects between these two options on the basis of the largest net profit contribution per unit (Cj - Zj). Since Cj - Zj is largest for X1, the simplex method will move to corner d by increasing X1 and simultaneously decreasing X3 to zero. In the language of the simplex method, X1 is introduced into the solution and X3 is removed from the solution, since its new value is zero.