This file illustrates the Simplex Method for solving Linear Programming problems algebraically. There are many software packages that perform this algorithm, but all are based on the method illustrated here. The example is the Wyndor Glass Co. problem from the book "Introduction to Operations Research" by Hillier and Lieberman. The sample problem is to Maximize 3 x1 + 5 x2 subject to x1 <= 4 2 x2 <= 12 3 x1 + 2 x2 <= 18 x1, x2 >= 0 The first step is to convert the inequalities to equalities by introducing SLACK VARIABLES, here denoted by s1, s2, and s3: x1 + s1 = 4 2 x2 + s2 = 12 3 x1 + 2 x2 + + s3 = 18 x1, x2, s1, s2, s3 >= 0 There are 5 variables, but only three equations. We can arbitrarily specify two of the variables and solve for the others. This is important to remember: once two of the variables are specified, the rest are determined. In the Simplex method we set two of the variables to 0, and solve for the rest. At any stage, the two that are set to 0 are called NON-BASIC variables, and the other three are the BASIC variables. A solution gotten this way is called a BASIC SOLUTION. To begin with, we'll let x1 and x2 be non-basic, and we solve the equations for s1, s2,s3: s1 = 4 - x1 s2 = 12 - 2 x2 s3 = 18 - 3 x1 - 2 x2 Since all the variables occurring on the right of these equations are 0, we can just read off the current solution as s1 = 4, s2 = 12, s3 = 18, plus of course x1 = 0, x2 = 0. Let's put it another way: Given three equations and five variables, we can find simultaneous solutions for three of the variables in terms of the other two; this produces three equations in which the left-hand sides are single variables that do not occur elsewhere in the equations. These variables are referred to as the basic variables. In such a situation, an OBVIOUS solution is obtained by setting all the non-basic variables to 0, after which the solution for the basic variables is read off from the equations. Such a solution is a basic solution. Notice that, because all the right-hand sides in the original constraints were non-negative, this initial basic solution will satisfy the non-negativity constraints. It is therefore called a FEASIBLE solution. Substituting the current equations into the objective function, in this case Z(x1,x2) = 3 x1 + 5 x2 always yields an expression for that function in terms of the non-basic variables; the constant term of that expression is the value of the function at the current basic solution, and the rest of the expression can give some idea of what would happen to the function if we are able to change the values of the non-basic variables. Right now, however, the result of the substitution still leaves 3 x1 + 5 x2 since x1, x2 are non-basic. The value is 0. The largest coefficient is that of x2, so increasing x2 appears to be the way of increasing the objective function the most rapidly. That would mean making x2 basic and some other variable non-basic. We'll do this by solving one of the equations for x2, and using that equation to eliminate x2 from the other equations. In fact, since everything is linear, we see that the derivative of Z with respect to x1 or x2 is simply the coefficient of x1 or x2 in the objective function. But which equation shall we solve for x2? If we solve the third, the new value of x2 would be 9; but plugging this in for x2 in the second equation would leave us with s2 = -6, and that violates the s2 >= 0 constraint. No, it's better if we solve the second equation for x2; that results in x2 = 6, and then s3 = 6. Carrying out the entire process of solving the second equation for x2 and plugging into the other equations, we get s1 = 4 - x1 x2 = 6 - 1/2 s2 s3 = 6 - 3 x1 + s2 The rule is, for each equation in which x2 occurs, divide the constant term by the negative coefficient of x2. The minimum positive quotient determines which equation to solve. The process of solving an equation for a variable and substituting the result into the other equations is called PIVOTING, the variable is the PIVOT VARIABLE, and the equation solved is the PIVOT EQUATION. As you see, the basic variables are the ones appearing on the left sides, and the non-basic variables are those on the right. The current basic solution is s1 = 4, x2 = 6, s3 = 6, x1 = 0, s2 = 0 Now when we substitute these new equations into the expression for the objective function, we obtain 3 x1 - 5/2 s2 + 30 The value is 30 here, a substantial improvement. But we still have a positive coefficient; increasing x1 (i.e., moving it into the BASIS, the set of basic variables) might increase the objective function. Again, we have to select the pivot equation; checking the quotients of the constant terms by the negative coefficients of x1, we find they are 4 and 2. The minimum positive quotient occurs with the third equation, so that will be the pivot equation. Carrying out the pivoting process, s1 = 2 - 1/3 s2 + 1/3 s3 x2 = 6 - 1/2 s2 x1 = 2 + 1/3 s2 - 1/3 s3 Again, we substitute this solution into the objective function: -s3 + 36 - 3/2 s2 The value is 36. There are no positive coefficients, so no change of basis can further improve this result: we've found the optimum solution, which can now be read off from the equations: x1 = 2, x2 = 6, s1 = 2, s2 = 0, s3 = 0 Geometric interpretation: The solutions satisfying the constraints are called FEASIBLE, and the FEASIBLE REGION is the set of all feasible solutions. This region is convex and bounded by some hyperplanes. (In our two-dimensional example, the region is a polygon bounded by straight lines.) Choosing variables = 0 makes corresponding constraints BINDING; it means that the solution is a a corner point of the feasible region. When we chose x1 = 0, x2 = 0 as the initial basic solution, we were actually picking the corner point at the origin, where x1 >= 0 and x2 >= 0 are binding. At a solution where some slack variable is non-basic, the corresponding constraint is binding---for example, after our first pivoting step, x1 and s2 were non-basic, so the binding constraints were x1 >= 0 and 2 x2 <= 12. At the end, both s2 and s3 were non-basic, and the optimum occurred at the corner point corresponding to the second and third constraints. The act of pivoting moves one variable into the basis and one out; it corresponds to sliding along one of the boundary lines from one corner point to another.