Linear Programmingin Matrix FormAppendix BWe first introduce matrix concepts in linear programming by developing a variation of the simplex methodcalled the revised simplex method. This algorithm, which has become the basis of all commercial computercodes for linear programming, simply recognizes that much of the information calculated by the simplexmethod at each iteration, as described in Chapter 2, is not needed. Thus, efficiencies can be gained bycomputing only what is absolutely required.Then, having introduced the ideas of matrices, some of the material from Chapters 2,3, and 4 is recastin matrix terminology. Since matrices are basically a notational convenience, this reformulation providesessentially nothing new to the simplex method, the sensitivity analysis, or the duality theory. However, theeconomy of the matrix notation provides added insight by streamlining the previous material and, in theprocess, highlighting the fundamental ideas. Further, the notational convenience is such that extending someof the results of the previous chapters becomes more straightforward.B.1 A PREVIEW OF THE REVISED SIMPLEX METHODThe revised simplex method, or the simplex method with multipliers, as it is often referred to, is a modificationof the simplex method that significantly reduces the total number of calculations that must be performed ateach iterationof the algorithm. Essentially, the revisedsimplexmethod, rather than updating the entire tableauat each iteration, computes only those coefficients that are needed to identify the pivot element. Clearly, thereduced costs must be determined so that the entering variable can be chosen. However, the variable thatleaves the basis is determined by the minimum-ratio rule, so that only the updated coefficients of the enteringvariable and the current righthand-side values are needed for this purpose. The revised simplex method thenkeeps track of only enough information to compute the reduced costs and the minimum-ratio rule at eachiteration.The motivation for the revised simplex method is closely related to our discussion of simple sensitivityanalysis in Section 3.1, 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 activitywas sufficient to justify diverting resources from the current optimal group of activities. The procedure wasessentially to ‘‘price out’’ the new activity by determining the opportunity cost associated with introducingone unit of the new activity, and then comparing this value to the contribution generated by engaging in oneunit of the activity. The opportunity cost was determined by valuing each resource consumed, by introducingone unit of the new activity, at the shadow price associated with that resource. The custom-molder exampleused in Chapter 3 to illustrate this point is reproduced in Tableau B.1. Activity 3, producing one hundredcases of champagne glasses, consumes 8 hours of production capacity and 10 hundred cubic feet of storagespace. The shadow prices, determined in Chapter 3, are $1114per hour of hour of production time and $135perhundred cubic feet of storage capacity, measured in hundreds of dollars. The resulting opportunity cost of505506 Linear Programming in Matrix Form B.1Tableau B.1Basic Currentvariables values x1x2x3x4x5x6−zx460 6 5 8 1 0x5150 10 20 10 1 0x68 1 0 0 1 0(−z) 0 5 4.5 6 1diverting resources to produce champagne glasses is then:11148 +13510 =467= 647.Comparing this opportunity cost with the $6 contribution results in a net loss of $47per case, or a loss of$5717per one hundred cases. It would clearly not be advantageous to divert resources from the current basicsolution to the new activity. If, on the other hand, the activity had priced out positively, then bringing thenew activity into the current basic solution would appear worthwhile. The essential point is that, by using theshadow prices and the original data, it is possible to decide, without elaborate calculations, whether or not anew 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 inadvance whether the activity will be promising or not. The pricing-out mechanism, therefore, could in factbe used at each iteration of the simplex method to compute the reduced costs and choose the variable to enterthe basis. To do this, we need to define shadow prices at each iteration.In transforming the initial system of equations into another system of equations at some iteration, wemaintain the canonical form at all times. As a result, the objective-function coefficients of the variablesthat are currently basic are zero at each iteration. We can therefore define simplex multipliers, which areessentially 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 themultiples of their initial system of equations such that, when all of these equations are multiplied by theirrespective simplex multipliers and subtracted from the initial objective function, the coefficients of thebasic variables are zero.Thus the basic variables must satisfy the following system of equations:y1a1j+ y2a2 j+ · · · + ymamj= cjfor j basic.The implication is that the reduced costs associated with the nonbasic variables are then given by:cj= cj− (y1a1j+ y2a2 j+ · · · + ymamj) for j nonbasic.If we then performed the simplex method in such a way that we knew the simplex multipliers, it would bestraightforward to find the largest reduced cost by pricing out all of the nonbasic variables and comparingthem.In the discussion in Chapter 3 we showed that the shadow prices were readily available from the finalsystem of equations. In essence, since varying the righthand side value of a particular constraint is similar toadjusting the slack variable, it was argued that the shadow prices are the negative of the objective-functioncoefficients of the slack (or artificial) variables in the final system of equations. Similarly, the simplexmultipliers at each intermediate iteration are the negative of the objective-function coefficients of thesevariables. In transforming the initial system of equations into any intermediate system of equations, anumber of iterations of the simplex method are performed,