Six Sigma and Beyond: Statistics and Probability, Volume III
Although the geometrical method for solving linear programming problems is highly satisfactory for problems that involve only two variables, it is a very difficult one to use on problems involving several variables . For those problems an algebraic method is needed. One of the most popular such algebraic devices is known as the simplex method. Although it was designed to solve more complicated problems, we will apply it to a two-dimensional problem in order to simplify the explanation.
The problem is to find the values of x and y that maximize the linear function
| (1) | |
subject to the restrictions
2x - y ‰ 1
x + 2y ‰ 3
x ‰
y ‰
The solution to this problem can be obtained by inspecting the nature of the feasibility region as shown in Figure B.1 and realizing that f is maximized by a family of lines 3x + 2y = f, which passes through the point (1,1).
It is true in general that a set of linear inequalities in two variables will always give rise to a feasibility region whose boundary consists of line segments. It is this property of the feasibility region that guarantees that a linear function f will take on its maximum (or minimum) value at a corner point of the boundary.
Although we are studying the problem here in two dimensions only, it can be shown by algebraic techniques that a similar property of the feasibility region is true in higher dimensions. Thus a linear function of k variables subject to a set of linear inequalities in those variables will assume its maximum (or minimum) value at one of the corners of the feasibility region that is determined by those inequalities. In practice we assume this fact without proof.
In view of the preceding comments, it should suffice to find all the corner points of the feasibility region and then calculate the value of f at each of those points to determine which of them produces the maximum (or minimum) value of f. Although such a procedure is carried out for a two-dimensional problem, the same is not true for higher dimensional problems because the number of corners may become very large, and much algebra is needed to locate them. The simplex method is a method that allows us to start at any given corner point and then proceed step-by-step to a neighboring corner that yields a larger value of f until the maximum corner is reached. For a minimizing problem, successive corners are chosen that decrease the value of f each time. We restrict ourselves to maximizing problems, because a problem in which f is to be minimized can be converted to one in which g is to be maximized by setting g = -f.
With these preliminaries out of the way, we are ready to solve the problem stated in (1) by the simplex method. This method begins by introducing as many new variables as are needed to convert the inequalities into equalities, except for inequalities of the type x ‰ 0 and y ‰ 0. An inequality such as 2x - y ‰ I can be made into an equality by introducing a new variable, say r, and writing
2x - y + r = 1
If x and y have values such that 2x - y < I, then r will be a positive number which, when added to 2x - y, will make the sum equal 1. If x and y have values such that 2x - y = 1, then r will have the value 0. Thus, r is a nonnegative number that transforms the inequality 2x - y ‰ 1 into the equality 2x - y + r = 1. Similarly, we can introduce a nonnegative variable s that will transform the inequality x + 2y ‰ 3 into the equality x + 2y + s = 3. The variables r and s that have been introduced here are called slack variables because they take up the slack on the left side of an inequality of the form ‰ to make the equality sign hold. In this connection, the variables x and y are called the basic variables.
The linear programming problem of (1) may now be reformulated as the problem of maximizing the function
f = 3x + 2y
subject to the restrictions
| (2) | |
Next , we express the corner points of our feasibility region in terms of the values of the four variables x, y, r, and s. The feasibility region for this problem was obtained earlier and can be found in Figure B.1. It is duplicated in Figure B.2. Each of these corner points is the point of intersection of two lines out of the set:
x = 0, y = 0, 2x - y = 1, and x + 2y = 3
Since the last two lines of this set are special cases of the first two equalities in (2) and are characterized by setting r = 0 and s = 0, respectively, we may represent this set of lines by the symbols:
x = 0, y = 0, r = 0, and s = 0
The origin is a corner point and is labeled (x = 0, y = 0) because it is the intersection of the y axis (x = 0) and the x axis (y = 0). The corner point on the x axis is labeled (y = 0, r = 0) because it is the intersection of the x axis (y = 0) and the line 2x - y = 1 (r = 0). The corner point labeled (r = 0, s = 0) is so labeled because it is the intersection of the two lines 2x - y = 1 (r = 0) and x + 2y = 3 (s = 0). Finally, the corner point on the y axis is labeled (x = 0, s = 0) because it is the intersection of the y axis (x = 0) and the line x + 2y = 3 (s = 0). The labeling of all the corner points of the feasibility region in this manner is shown in Figure B.2.
The next step in the simplex method is to start at a corner point and proceed to a neighboring corner that will increase the value of f, assuming that the maximum value of f has not already been attained. Suppose that we start at the (x = 0, y = 0) corner. Then we wish to proceed to the (y = 0, r = 0) corner or to the (x = 0, s = 0) corner. It should be observed that this procedure leaves one of x = 0 or y = 0 alone and replaces the other by the zero value of a different variable. Since our function f = 3x + 2y will grow faster if x is increased one unit than if y is increased one unit, and we wish to make f as large as possible, we agree to leave y = 0 alone and increase x as much as possible. But from Figure B.2 this means that we choose the (y = 0, r = 0) corner in preference to the (x = 0, s = 0) corner. Setting y = 0 and r = 0 in equations (2), we obtain
2x = 1
x + s = 3
Solving these equations, we find that x = 1/2, s = 5/2, and f = 3/2. Since f had the value 0 and our starting corner (x = 0, y = 0), this shift has increased its value from 0 to 3/2.
We now repeat the performance, beginning with the (y = 0, r = 0) corner and treating y and r as the basic variables and x and s as the slack variables. To do so, we must express f as a function of y and r only. This can be accomplished by expressing x as a function of y and r and substituting it into the expression for f. We therefore solve the first equation in (2) for x in terms of y and r and substitute it into the expression for f. Thus
Now treating y and r as the basic variables, it is clear from this expression that f can be increased by increasing y from its zero value. Increasing r from its zero value, however, would decrease the value of f. This implies that we should hold r fixed at its zero value and should increase y as much as possible. Geometrically, this means that we should move from the (y = 0, r = 0) corner to the neighboring corner where r = 0 and y is positive, which from Figure B.2 is the (r = 0, s = 0) corner. Setting r = 0 and s = 0 in equations (2), we obtain
2x - y = 1
x + 2y = 3
Solving these equations, we get x = 1, y = 1, and f = 5. Since the value of f has increased from 3/2 to 5, this shift has increased the value of f further.
Although we know from our earlier result that we have reached the maximizing corner, we proceed as though we were not aware of this fact. Thus, since our new basic variables are chosen to be r and s, we must express f in terms of r and s. This is accomplished by solving equations (2) for x and y in terms of r and s and substituting those values into f. The solution of equations (2) is given by
x = 1 - 2r/5 - s/5
y = 1 + r/5 - 2s/5
As a result, f assumes the form
Since r and s cannot be increased from their zero values without decreasing the value of f, it follows that r = 0 and s = 0 yield the maximum value of f, namely 5.
This technique of shifting to a neighboring corner that increases the value of f until the maximizing corner has been reached assumes that it is always possible to arrive at the maximizing corner in this manner. A justification for this assumption can be given that is based on the nature of the feasibility region. Since this property of our feasibility region seems obvious from the geometry of the problem for two-dimensional problems, we do not attempt a justification. The chief advantage of our method is that it eliminates the necessity of finding the coordinates of all the corner points and of checking the value of f at each of them. As we stated previously, the latter method can become a lengthy computational problem in higher dimensions.
Another striking advantage of the simplex method is that the technique can be carried out in a systematic routine manner by means of matrix methods , regardless of the number of variables involved. It is not necessary to perform any of the geometry that was used in our present problem. The geometry was introduced to explain how and why the simplex method works.