Question

A metropolitan area is facing a serious problem with disposing of its waste. Its current landfill is almost full and it is looking for other sites that can fulfill its likely future needs. A landfill must not only be large enough to handle the weekly needs of the region, but has to be as environmentally benign as possible. This means that the types of materials that are placed in the landfill must not exceed certain threshold limits. And of course, officials are mainly concerned with satisfying the needs for disposal in the least costly manner possible. To simplify the problem of analyzing one particular site, the metropolitan planners have divided the region into three major parts and estimated the amount of waste (in tons) that can be transported from each part of the region (due to public opposition to the number of trucks on the local roads) per week. In addition, the amount of nonorganic material per ton deposited in the landfill must be kept at a minimum in order for the landfill to provide the maximum capacity over its useful life. It is expected that the absolute limit of non-organic material allowed per week in the landfill will be a composite 900 pounds per ton. The relevant data is shown in the following table.

	Location 1	Location 2	Location 3
Cost ($/ton)	120	115	105
Supply limit per week	490	635	900
Non-organic (lb/ton)	1250	800	550

a) Write out the set of linear equations needed for the problem assuming that planners expect the landfill to handle 1,850 tons per week. That is, what equation do you want to optimize and what equations would you use as constraints?

b) If planners are expecting the landfill to handle 1,850 tons per week, what is the optimal distribution of waste delivery from the three locations in the region? (Hand in the results from Excel: linear program input sheet, the Answer Report, Sensitivity Report, and Limits Report) How much will the city pay per week for the landfill service?

c) Suppose you want to do a sensitivity analysis on your analysis. In particular, you are interested in answering the following questions. How would the optimal cost change if you were able to obtain 500 tons per week from location 3 instead of the current 850 tons? Show how you would calculate this answer by referencing your sensitivity analysis form.

d) Suppose a trucking firm comes to you and says that they could lower the cost per ton of transporting waste from location 3 from $105 per ton to $95 per ton for a nominal fee (they're anxious to get the business). Using your results and sensitivity analysis from part b, what effect will this change have on (i) the optimal cost? (ii) If the firm will charge the equivalent of a weekly flat fee of $1,000, should metro officials accept this offer?

Answer 1

Finally, 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) x j ≥ 0 (j = 1, 2, 3, 4). Now as x4 increases, z increases. Maintaining x3 = 0, let us increase x4 to a value t, and update x1 and x2 to preserve feasibility. Then, as before, from constraints (1) and (2), x1 = 6 − 3t, x2 = 4 − 4t, z = 20 + t. If x1 and x2 are to remain nonnegative, we require: 6 − 3t ≥ 0, that is, t ≤ 6 3 = 2 and 4 − 4t ≥ 0, that is, t ≤ 4 4 = 1. Therefore, the largest value for t that maintains a feasible solution is t = 1. When t = 1, the new solution becomes x1 = 3, x2 = 0, x3 = 0, x4 = 1, which has an associated value of z = 21 in the objective function. Note that, in the new solution, x4 has a positive value and x2 has become zero. Since nonbasic variables have been given zero values before, it appears that x4 has replaced x2 as a basic variable. In fact, it is fairly simple to manipulate Eqs. (1) and (2) algebraically to produce a new canonical form, where x1 and x4 become the basic variables. If x4 is to become a basic variable, it should appear with coefficient +1 in Eq. (2), and with zero coefficients in Eq. (1) and in the objective function. To obtain a +1 coefficient in Eq. (2), we divide that equation by 4, changing the constraints to read: x1 − 3x3 + 3x4 = 6, (1) 1 4 x2 − 2x3 + x4 = 1. (20 ) Now, to eliminate x4 from the first constraint, we may multiply Eq. (20 ) by 3 and subtract it from constraint (1), giving: x1 − 3 4 x2 + 3x3 = 3, (10 ) 2.1 Simplex Method—A Preview 41 1 4 x2 − 2x3 + x4 = 1. (20 ) Finally, we may rearrange the objective function and write it as: (−z) − 3x3 + x4 = −20 (3) and use the same technique to eliminate x4; that is, multiply (20 ) by −1 and add to Eq. (1) giving: (−z) − 1 4 x2 − x3 = −21. Collecting these equations, the system becomes: Maximize z = 0x1 − 1 4 x2 − x3 + 0x4 + 21, subject to: x1 − 3 4 x2 + 3x3 = 3, (10 ) 1 4 x2 − 2x3 + x4 = 1, (20 ) x j ≥ 0 (j = 1, 2, 3, 4). Now the problem is in canonical form with x1 and x4 as basic variables, and z has increased from 20 to 21. Consequently, we are in a position to reapply the arguments of this section, beginning with this improved solution. In this case, the new canonical form satisfies the optimality criterion since all nonbasic variables have nonpositive coefficients in the objective function, and thus the basic feasible solution x1 = 3, x2 = 0, x3 = 0, x4 = 1, is optimal. The procedure that we have just described for generating a new basic variable is called pivoting. It is the essential computation of the simplex method. In this case, we say that we have just pivoted on x4 in the second constraint. To appreciate the simplicity of the pivoting procedure and gain some additional insight, let us see that it corresponds to nothing more than elementary algebraic manipulations to re-express the problem conveniently. First, let us use constraint (2) to solve for x4 in terms of x2 and x3, giving: x4 = 1 4 (4 − x2 + 8x3) or x4 = 1 − 1 4 x2 + 2x3. (20 ) Now we will use this relationship to substitute for x4 in the objective equation: z = 0x1 + 0x2 − 3x3 + 1 − 1 4 x2 + 2x3 + 20, z = 0x1 − 1 4 x2 − x3 + 0x4 + 21, and also in constraint (1) x1 − 3x3 + 3 1 − 1 4 x2 + 2x3 = 6, or, equivalently, x1 − 3 4 x2 + 3x3 = 3. (10 ) Note that the equations determined by this procedure for eliminating variables are the same as those given by pivoting. We may interpret pivoting the same way, even in more general situations, as merely rearranging the system by solving for one variable and then substituting for it. We pivot because, for the new basic variable, we want a +1 coefficient in the constraint where it replaces a basic variable, and 0 coefficients in all other constraints and in the objective function. Consequently, after pivoting, the form of the problem has been altered, but the modified equations still represent the original problem and have the same feasible solutions and same objective value when evaluated at any given feasible solution. Indeed, the substitution is merely the familiar variable-elimination technique from high-school algebra, known more formally as Gauss–Jordan elimination. 42 Solving Linear Programs 2.1 In summary, the basic step for generating a canonical form with an improved value for the objective function is described as: Improvement Criterion. Suppose that, in a maximization problem, some nonbasic variable has a positive coefficient in the objective function of a canonical form. If that variable has a positive coefficient in some constraint, then a new basic feasible solution may be obtained by pivoting. Recall that we chose the constraint to pivot in (and consequently the variable to drop from the basis) by determining which basic variable first goes to zero as we increase the nonbasic variable x4. The constraint is selected by taking the ratio of the righthand-side coefficients to the coefficients of x4 in the constraints, i.e., by performing the ratio test: min n 6 3 , 4 4 o . Note, however, that if the coefficient of x4 in the second constraint were −4 instead of +4, the values for x1 and x2 would be given by: x1 = 6 − 3t, x2 = 4 + 4t, so that as x4 = t increases from 0, x2 never becomes zero. In this case, we would increase x4 to t = 6 3 = 2. This observation applies in general for any number of constraints, so that we need never compute ratios for nonpositive coefficients of the variable that is coming into the basis, and we establish the following criterion: Ratio and Pivoting Criterion. When improving a given canonical form by introducing variable xs into the basis, pivot in a constraint that gives the minimum ratio of righthand-side coefficient to corresponding xs coefficient. Compute these ratios only for constraints that have a positive coefficient for xs . Observe that the value t of the variable being introduced into the basis is the minimum ratio. This ratio is zero if the righthand side is zero in the pivot row. In this instance, a new basis will be obtained by pivoting, but the values of the decision variables remain unchanged since t = 0. As a final note, we point out that a linear program may have multiple optimal solutions. Suppose that the optimality criterion is satisfied and a nonbasic variable has a zero objective-function coefficient in the final canonical form. Since the value of the objective function remains unchanged for increases in that variable, we obtain an alternative optimal solution whenever we can increase the variable by pivoting.