Solving Linear Programs2In this chapter, we present a systematic procedure for solving linear programs. This procedure, called thesimplex method, proceeds by moving from one feasible solution to another, at each step improving the valueof the objective function. Moreover, the method terminates after a finite number of such transitions.Two characteristics of the simplex method have led to its widespread acceptance as a computational tool.First, the method is robust. It solves any linear program; it detects redundant constraints in the problemformulation; it identifies instances when the objective value is unbounded over the feasible region; and itsolves problems with one or more optimal solutions. The method is also self-initiating. It uses itself eitherto generate an appropriate feasible solution, as required, to start the method, or to show that the problem hasno feasible solution. Each of these features will be discussed in this chapter.Second, the simplex method provides much more than just optimal solutions. As byproducts, it indicateshow the optimal solution varies as a function of the problem data (cost coefficients, constraint coefficients,and righthand-side data). This information is intimately related to a linear program called the dual to thegiven problem, and the simplex method automatically solves this dual problem along with the given problem.These characteristics of the method are of primary importance for applications, since data rarely is knownwith certainty and usually is approximated when formulating a problem. These features will be discussed indetail in the chapters to follow.Before presenting a formal description of the algorithm, we consider some examples. Though elementary,these examples illustrate the essential algebraic and geometric features of the method and motivate the generalprocedure.2.1 SIMPLEX METHOD—A PREVIEWOptimal SolutionsConsider the following linear program:Maximize z = 0x1+ 0x2− 3x3− x4+ 20, (Objective 1)subject to:x1− 3x3+ 3x4= 6, (1)x2− 8x3+ 4x4= 4, (2)xj≥ 0 ( j = 1, 2, 3, 4).Note that as stated the problem has a very special form. It satisfies the following:1. All decision variables are constrained to be nonnegative.2. All constraints, except for the nonnegativity of decision variables, are stated as equalities.382.1 Simplex Method—A Preview 393. The righthand-side coefficients are all nonnegative.4. One decision variable is isolated in each constraint with a +1 coefficient (x1in constraint (1) and x2inconstraint (2)). The variable isolated in a given constraint does not appear in any other constraint, andappears with a zero coefficient in the objective function.A problem with this structure is said to be in canonical form. This formulation might appear to be quitelimited and restrictive; as we will see later, however, any linear programming problem can be transformed sothat it is in canonical form. Thus, the following discussion is valid for linear programs in general.Observe that, given any values for x3and x4, the values of x1and x2are determined uniquely by theequalities. In fact, setting x3= x4= 0 immediately gives a feasible solution with x1= 6 and x2= 4.Solutions such as these will play a central role in the simplex method and are referred to as basic feasiblesolutions. In general, given a canonical form for any linear program, a basic feasible solution is given bysetting the variable isolated in constraint j, called the jth basic-variable, equal to the righthand side of thejth constraint and by setting the remaining variables, called nonbasic, all to zero. Collectively the basicvariables are termed a basis.∗In the example above, the basic feasible solution x1= 6, x2= 4, x3= 0, x4= 0, is optimal. For anyother feasible solution, x3and x4must remain nonnegative. Since their coefficients in the objective functionare negative, if either x3or x4is positive, z will be less than 20. Thus the maximum value for z is obtainedwhen x3= x4= 0.To summarize this observation, we state the:Optimality Criterion. Suppose that, in a maximization problem, every nonbasic variable has a non-positive coefficient in the objective function of a canonical form. Then the basic feasible solution givenby the canonical form maximizes the objective function over the feasible region.Unbounded Objective ValueNext consider the example just discussed but with a new objective function:Maximize z = 0x1+ 0x2+ 3x3− x4+ 20, (Objective 2)subject to:x1− 3x3+ 3x4= 6, (1)x2− 8x3+ 4x4= 4, (2)xj≥ 0 ( j = 1, 2, 3, 4).Since x3now has a positive coefficient in the objective function, it appears promising to increase the valueof x3as much as possible. Let us maintain x4= 0, increase x3to a value t to be determined, and update x1and x2to preserve feasibility. From constraints (1) and (2),x1= 6 + 3t,x2= 4 + 8t,z = 20 + 3t.∗We have introduced the new terms canonical, basis, and basic variable at this early point in our discussion becausethese terms have been firmly established as part of linear-programming vernacular. Canonical is a word used in manycontexts in mathematics, as it is here, to mean ‘‘a special or standard representation of a problem or concept,’’ usuallychosen to facilitate study of the problem or concept. Basis and basic are concepts in linear algebra; our use of theseterms agrees with linear-algebra interpretations of the simplex method that are discussed formally in Appendix A.40 Solving Linear Programs 2.1No matter how large t becomes, x1and x2remain nonnegative. In fact, as t approaches +∞, z approaches+∞. In this case, the objective function is unbounded over the feasible region.The same argument applies to any linear program and provides the:Unboundedness Criterion. Suppose that, in a maximization problem, some nonbasic variable has apositive coefficient in the objective function of a canonical form. If that variable has negative or zerocoefficients in all constraints, then the objective function is unbounded from above over the feasibleregion.Improving a Nonoptimal SolutionFinally, let us consider one further version of the previous problem:Maximize z = 0x1+ 0x2− 3x3+ x4+ 20, (Objective 3)subject to:x1− 3x3+ 3x4= 6, (1)x2− 8x3+ 4x4= 4, (2)xj≥ 0 ( j = 1, 2, 3, 4).Now as x4increases, z increases. Maintaining x3= 0, let us increase x4to a value t, and update x1and x2to preserve feasibility. Then, as before, from constraints (1) and (2),x1= 6 − 3t,x2= 4 − 4t,z = 20 + t.If x1and x2are to remain nonnegative, we