Linear Programming in Matrix Form B

1 Linear Programming in Matrix form Appendix B. We first introduce Matrix concepts in Linear Programming by developing a variation of the simplex method called the revised simplex method. This algorithm, which has become the basis of all commercial computer codes for Linear Programming , simply recognizes that much of the information calculated by the simplex method at each iteration, as described in Chapter 2, is not needed. Thus, efficiencies can be gained by computing only what is absolutely required. Then, having introduced the ideas of matrices, some of the material from Chapters 2,3, and 4 is recast in Matrix terminology.

2 Since matrices are basically a notational convenience, this reformulation provides essentially nothing new to the simplex method, the sensitivity analysis, or the duality theory. However, the economy of the Matrix notation provides added insight by streamlining the previous material and, in the process, highlighting the fundamental ideas. Further, the notational convenience is such that extending some of the results of the previous chapters becomes more straightforward. A PREVIEW OF THE REVISED simplex METHOD. The revised simplex method, or the simplex method with multipliers, as it is often referred to, is a modification of the simplex method that significantly reduces the total number of calculations that must be performed at each iteration of the algorithm.

3 Essentially, the revised simplex method, rather than updating the entire tableau at each iteration, computes only those coefficients that are needed to identify the pivot element. Clearly, the reduced costs must be determined so that the entering variable can be chosen. However, the variable that leaves the basis is determined by the minimum-ratio rule, so that only the updated coefficients of the entering variable and the current righthand-side values are needed for this purpose. The revised simplex method then keeps track of only enough information to compute the reduced costs and the minimum-ratio rule at each iteration.

4 The motivation for the revised simplex method is closely related to our discussion of simple sensitivity analysis in Section , and we will re-emphasize some of that here. In that discussion of sensitivity analysis, we used the shadow prices to help evaluate whether or not the contribution from engaging in a new activity was sufficient to justify diverting resources from the current optimal group of activities. The procedure was essentially to price out'' the new activity by determining the opportunity cost associated with introducing one unit of the new activity, and then comparing this value to the contribution generated by engaging in one unit of the activity.

5 The opportunity cost was determined by valuing each resource consumed, by introducing one unit of the new activity, at the shadow price associated with that resource. The custom-molder example used in Chapter 3 to illustrate this point is reproduced in Tableau Activity 3, producing one hundred cases of champagne glasses, consumes 8 hours of production capacity and 10 hundred cubic feet of storage 11 1. space. The shadow prices, determined in Chapter 3, are $ 14 per hour of hour of production time and $ 35 per hundred cubic feet of storage capacity, measured in hundreds of dollars. The resulting opportunity cost of 505.

6 506 Linear Programming in Matrix form Tableau Basic Current variables values x1 x2 x3 x4 x5 x6 z x4 60 6 5 8 1 0. x5 150 10 20 10 1 0. x6 8 1 0 0 1 0. ( z) 0 5 6 1. diverting resources to produce champagne glasses is then: . 11 1 46. 14 8 + 35 10 = 7 = 6 47 . Comparing this opportunity cost with the $6 contribution results in a net loss of $ 47 per case, or a loss of $57 71 per one hundred cases. It would clearly not be advantageous to divert resources from the current basic solution to the new activity. If, on the other hand, the activity had priced out positively, then bringing the new activity into the current basic solution would appear worthwhile.

7 The essential point is that, by using the shadow prices and the original data, it is possible to decide, without elaborate calculations, whether or not a new activity is a promising candidate to enter the basis. It should be quite clear that this procedure of pricing out a new activity is not restricted to knowing in advance whether the activity will be promising or not. The pricing-out mechanism, therefore, could in fact be used at each iteration of the simplex method to compute the reduced costs and choose the variable to enter the basis. To do this, we need to define shadow prices at each iteration.

8 In transforming the initial system of equations into another system of equations at some iteration, we maintain the canonical form at all times. As a result, the objective-function coefficients of the variables that are currently basic are zero at each iteration. We can therefore define simplex multipliers, which are essentially the shadow prices associated with a particular basic solution, as follows: Definition. The simplex multipliers (y1 , y2 , .. , ym ) associated with a particular basic solution are the multiples of their initial system of equations such that, when all of these equations are multiplied by their respective simplex multipliers and subtracted from the initial objective function, the coefficients of the basic variables are zero.

9 Thus the basic variables must satisfy the following system of equations: y1 a1 j + y2 a2 j + + ym am j = c j for j basic. The implication is that the reduced costs associated with the nonbasic variables are then given by: cj = cj (y1 a1 j + y2 a2 j + + ym am j ) for j nonbasic. If we then performed the simplex method in such a way that we knew the simplex multipliers, it would be straightforward to find the largest reduced cost by pricing out all of the nonbasic variables and comparing them. In the discussion in Chapter 3 we showed that the shadow prices were readily available from the final system of equations.

10 In essence, since varying the righthand side value of a particular constraint is similar to adjusting the slack variable, it was argued that the shadow prices are the negative of the objective-function coefficients of the slack (or artificial) variables in the final system of equations. Similarly, the simplex multipliers at each intermediate iteration are the negative of the objective-function coefficients of these variables. In transforming the initial system of equations into any intermediate system of equations, a number of iterations of the simplex method are performed, involving subtracting multiples of a row from the objective function at each iteration.