;da i r i* as Bureau of Business Research Graduate School of Business Administration University of Michigan March, 1971 THE UTILIZATION OF LINEAR OPTIMIZATION MODELS IN ADAPTIVE PLANNING AND CONTROL Working Paper No. 33 by William K. Hall Assistant Professor of Statistics and Management Science University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the express permission of the Bureau of Business Research

BACKGROUND OF THIS PAPER This paper is based on material developed for a course in linear optimization models offered at the Graduate School of Business. The intent is to illustrate how the post-optimal feature of linear programming can be used in the firm to guide the adaptive, decentralized response to unplanned exogenous events. Because this paper has been submitted for publication in the Journal of Accounting Research it follows the style prescribed by that journal rather than that prescribed by the Bureau.

Introduction An increasingly large number of industrial concerns are using linear programming models to guide the allocation of resources to productive activities. The utility of these models comes from their ability to characterize complex optimal or near-optimal plans, and to examine quantitatively the effects of exogenous factors and internal policies on these plans. The result is a more explicit understanding of information requirements and planning effectiveness within the firm. The utilization of linear programming models in examining the sensitivity of optimal plans to changes in environmental factors and corporate policies has been discussed by several authors, including Godfrey, Spivey, and Stillwagon (4), Rappaport (7), and Jensen (5). The process of adjustment to such changes has also been examined in order to gain insight into methods for minimizing sub-optimal adjustments. In this regard, Samuels (8) and Bernhard (1) have discussed opportunity costing techniques based on linear programming models to control production volume variances. Furthermore, Demski (3) has developed an accounting control system by conducting a comparison of attained results, planned optimal results derived from a linear programming model, and theoretical optimal results derived from a linear programming model which has been adjusted for exogenous changes incurred during the planning period. The attempt here is to extend these concepts by examining the usefulness of linear programming models in control problems when planning is conducted recursively over multiple time periods. We shall assume that the firm'sshortrun objective is to optimally allocate available productive resources in each time period, and that this allocation can be accomplished by formulating and solving a linear programming model representing the intra-period decision problem.

-2 -Thus, in developing a plan for N time periods, the firm can specify and/or estimate resource availibilities and technological relationships for each period and combine these with estimates of demands and contribution margins to formulate N linear programming problems. The optimal "base plan" is then obtained.by solving these independent programming problems.* As the base plan is implemented, however, the occurrence. of unplanned exogenous and internal events is likely to force deviation from the original plan in certain periods. Moreover, in many situations, these intra-period deviations may affect the implementation of the original plan in subsequent periods. For instance, suppose that the firm receives an unplanned, high-priority order for some product which must be filled by a certain deadline. To achieve this deadline, resources in a given time period may be re-allocated from other activities, or resources which had originally been allocated to a future period may be reallocated to the current period. As a second example, suppose that an engineering problem arises in a given period, thereby placing additional constraints on the maximum attainable levels of certain outputs. In this situation, the underproduction of these outputs yields resources which are potentially available for the production of other outputs within the period. Alternatively, in some cases, these resources can be inventoried to provide extra resource availability in future time periods. It will be shown here that the post-optimality features of linear programming models can be used to determine the optimal response to these types of unplanned deviations from the original base plan. Consequently these models provide valuable control information by facilitating a comparison of the actual response to unplanned deviations with the optimal response. Moreover, it will also be shown that linear programming models provide economic information which can help guide the response to unplanned deviation on a decentralized basis. The extension of these techniques to situations when constraints are present which link the intra-period decisions will be discussed later in this paper.

-3 -Hence these models provide not only a method for evaluating a firm's adjustment to dynamic perturbations, but also an adaptive process by which the optimal adjustments can be guided and controlled. The discussion will be carried out in terms of a slight variant of the simplified linear model for the intra-period resource allocation problem which was utilized by Samuels and Bernhard. This will allow the results presented here to be integrated with the opportunity costing techniques introduced by these authors. To simplify the discussion it will be assumed that the base plans for all time periods are the same; that is, the intra-period linear planning models are assumed to be identical. The extension of the concepts developed here to more complex and non-identical intra-period models will be discussed later in this paper. For this example, assume that the optimal single period production plan for a three-department firm can be found for solving the following linear programming problem: Maximize P = 2x + 3y + 4z (Total contribution margin) Subject to the constraints: 5x + y + z < 8,000 (Floor space restriction) x + 5y + z < 8,000 (Supervisor time restriction) x + + 5z < 8,000 (Raw material restriction) x > 0, y > 0, z > Where x, y, and z are respectively the production levels in the three departments. The optimal solution to this problem is x* = 1,142, y* = z* = 1,143, and p* = 10,284. The first and last tableaus for the problem in standard form are given in Table A: I*

-4 -Table A First and Last Tableaus for Intra-Period Production Planning Problem b x y z sL1 sL2 sL3 0 -2 -3 -4 0 0 0 8,000 5 1 1 1 0 0 8,000 1 5 1 0 1 0 8,000 1 1 5 0 0 1 10,284 0 0 0 5/28 12/28 19/28 1,142 1 0 06/28 -1/28 -1/28 1,143 0 1 0 -1/28 6/28 -1/28 1,143 0 0 1 -1/28 -1/28 6/28 Intra-Period Adjustment and Control Procedures To illustrate the intra-period adjustment process to unplanned deviations, suppose that at the beginning of some period, an engineering problem is detected which will cause one department, say Department 3, to fail to meet its target production level of 1,143 units. Assume, for instance, that in the period under consideration Department 3 can produce at most 1,050 units —93 units below the optimal level. With no adjustment this reduction results in a decrease in the firm's profits of $372, and Samuels and Bernhard would argue that for control purposes this opportunity cost should be charged to the responsible department. Notice, however, that the failure of Department 3 to meet its target level results in the under-utilization of some of the firm's resources. If the remaining departments are made aware of these under-utilizations and if they can appropriately adjust their production schedules, it is possible that some of the opportunity cost incurred by Department 3 can be recovered. The question remains as to how Departments 1 and 2 should adjust their production levels to maximize this recovery.

-5 -One potential method for solving this adjustment problem is to resolve the associated linear programming problem after adding the constraint z < 1,050 to reflect the upper bound on production in Department 3. Unfortunately, re-solving the problem may result in considerable computational cost and time (a significant factor in large-scale industrial application). Furthermore, this alternative can be avoided by making certain post-optimality adjustments on the last tableau of the original linear programming problem. A decrease in the level of the basic variable z must be accompanied by an increase in some non-basic variable (in this case one of the slack activities). Then let z' denote the attained productive level in Department 3, let SLK denote the level of the non-basic slack variable k, and let a k denote the marginal rate of substitution between the output of department z and the level of slack activity k. From the last row of the final tableau we can relate these quantities to the optimal production level z* by the equation: z* = z' + a kSLK or equivalently z =- z*- a SLK zk Since in this case z'< z* and the non-basic variable SLK > 0, the level of some slack activity for which a k>. must be increased to a positive level. Inspection of the final tableau reveals that slack activity 3 (unused raw material) is the only activity with a positive marginal rate of substitution with z, and consequently the level of this activity must be increased when the output of z is decreased. Since az3- 6/28 for slack activity 3, when z= 1,050 we can.write 1,050 = 1,143 - 6/28 SL3 and solving for SL3 we obtain SL3 = 434. Consequently, the optimal adjustment to a 93 unit production decrease in Department 3 will leave 434 units of the raw material unutilized. Similar equations can be written from the last tableau relating the new output levels in Departments 1 and 2 to the increase in unutilized raw materials.

-6 -These equations are given by: x' = x - (-1/28) SL3 y' = y* - (-1/28) SL3 and substituting SL3 = 434, one obtains x' = 1157.5 and y' = 1158.5. The corresponding reduction in total contribution margin corresponding to this adjusted plan can be calculated by observing that marginal profit associated with a change in resource availability is equal to the dual price of the resource in the neighborhood of the optimal solution. Since the dual price of the raw material is 19/28, 434 units of unused raw material will decrease total contribution margin by $294 = 19/28 (434). In summary, we see that the failure of Department 3 to reach its target level makes resources available to Departments 1 and 2 which conceivably allow these departments to increase their output. If these departments do not take advantage of the available resources an opportunity cost of $372 is incurred. However, if Departments i & 2 modify their production plans to utilize the available resources in an optimal fashion they each produce an additional 15.5 units and a minimal opportunity cost of $294 is incurred by the firm. Hence, when departments have the ability to adjust to unplanned deviations, the assignment of the opportunity cost to individual departments should be based upon the minimum loss adjustments. That is, for control purposes, departments should be evaluated on the basis of their performance with respect to the best possible plan under the dynamic changes encountered. Such a control procedure encourages adaptive planning and will certainly result in improved performance for the firm. The question remains, however, as to how to implement such dynamic planning. One way is to compute the optimal adjusted plan and announce the re vised target output levels to the individual departments. Unfortunately, in

-7 -many situations this is infeasible or costly. In these cases, however, the linear programming model provides a surprisingly large amount of information which will aid the adjustment process on a decentralized basis. For instance, in our example suppose that Department 2 is informed that 434 units of raw material are available. If the department knows its marginal rate of substitutions between output level and raw material (-1/28), the revised output level can be computed from the linear equation y' y* - (-1/28) SL3 = 1143 + 1/28 (434) = 1158.5 Thus we see that knowledge of the marginal rates of substitution between activities is sufficient to guide the optimal decentralized adjustment of various departments to changing resource availabilities. These marginal rates are always available as a by-product of the final tableau for a linear programming problem. Hence the only problem in utilizing these in an adaptive control process is to insure effective communication to the individual departments. A similar situation occurs when other unplanned events force deviations from the base plan. For instance, assume that in some period Department 1 is required to produce 1,182 units —40 more than in the original base plan. Here again an increase in the level of the basic variable x must be accompanied by an increase in the level of some non-basic variable SLK. Hence we can write x' = x* -a xSLK xk Since x' >x* and SLK > 0, in this case SLK must be chosen so that the marginal rate of substitution between x and SLK is negative. Inspection of the final tableau in Table A reveals that the appropriate marginal rates of substitution are negative for both SL2 and SL3 (utilized supervisory time and raw material).

-8 - To minimize the reduction in contribution margin obtained when one of these slack activities is increased to a positive level, we wish to choose that activity with the smallest unit cost. The unit cost of these activities can be computed by dividing their dual values by the marginal rates of substitution, and taking absolute values obtaining Marginal rate of Dual Unit Slack activity substitution with x - value cost 2 -1/28 12/28 12 3 -1/28 19/28 19 Hence, we wish to increase slack activity 2 (unused supervisory time) to a positive level. The actual level of unused supervisor time can then be obtained by solving the equation 1182 = 1142 - (-1/28) SL2 yielding SL2 = 1,120, which indicates that the optimal production plan when Department 1 produces 40 units over the base plan will have 1,120 units of unutilized supervisory time. Adjustments in the outputs of Departments 2 and 3 can then be found by developing the following equation from the final tableau: y' = y* - (6/28) SLI = z* - (-1/28) SLl for SL 1 = 1,120, one obtains y' 903 and z' = 1,183. The minimal reduction in the firm' total contribution margin is given by 12/28 (1,120) = $480. This result is both interesting and important, for it illustrates that the best adjustment to overproduction in Department 1 is for Department 2 to reduce output and simultaneously for Department 3 to increase output. Here again, the optimal adjustment can be attained with knowledge only of the marginal rates of substitution between activities, and as before, an opportunity costing plan can be implemented to control deviations from the optimally adjusted base plan. **

-9 -As a final example of intra-period adjustment, suppose that in some period Department 1 improves its technological relationships so that only 5/6 of a unit of supervisory time is required to produce one unit of output, thereby freeing 1/6 (1,142) or-approximately 190 units of supervisory time. The determination of the optimal adjustment to this event is more difficult, since the marginal rates of substitution between activities all may be changed because of this technological improvement. The mathematical effects of such a change in a basic activity coefficient are discussed in detail by Dantzig (2:pp 271-275) and Spivey and Thrall (9:pp 188-189). For our purposes it is sufficient to state the result proved in Appendix A, which indicates that a revised optimal program can be found by adding the perturbation vector given below to the original optimal program, yielding: x' 1,142 -8 1,134 y' = 1,143 + 48 = 1,191 z 1,143 -8 1,135 with an incremental contribution margin of 96. As indicated in Appendix A, the significance of this result is that the optimal adjustment of Department 1 to an internal technological iZrovement is to reduce the level of departmental output. This illustrates again the importance of controlling departmental adjustments on either a centralized or decentralized basis. Unfortunately, it is shown in Appendix A that the optimal adjustment to such a technological change or a decentralized basis requires the knowledge of the marginal rates of substitution between all activities in all departments. Furthermore, significant computation is required to determine the optimal adjustment. Because of these informational and computational requirements, it is unlikley that decentralized, adaptive control is feasible in the situation of changing technological relationships.

-10 -Inter-period Adjustment and Control Procedures In the first example of the previous section it was shown that the optimal adjustment to a specified engineering problem in Department 3 results in the under-utilization of raw materials within the period. In many situations this excess material can be inventoried for use in subsequent periods. Alternatively, it is possible that unplanned intra-period events may result in an infeasible production schedule unless resources are "borrowed" from future periods in the form of overtime, specially ordered raw materials, etc. In this case, adjustments must be made on the base plan in future periods unless the original future resource availabilities can be stored. The process of adjustment in both of these cases leads to a consideration of recursive programming procedures. Recursive programming problems arise when the resource availabilities in any period are functionally dependent upon the decisions made in the previous period. This results in interdependencies which alter the sequence of optimal decisions through time. In the situation being considered here, these dependencies arise because the process of adjustment to deviations from the base intra-period plans may result in the shifting of resources between periods. It is important to note, however, that in these cases the resulting interdependencies do not result in a significantly increased computations burden, for they can be conveniently handled by the post-optimality features of linear programming which were utilized in the intra-period adjustment process. To illustrate these ideas, suppose that the 434 units of unused raw material resulting from an optimal adjustment to the engineering problem in Department 3 discussed earlier can be inventoried for use in the next period. If we assume that the base intra-period planning problems are identical, the revised planning problem for the next period is given by the initial tableau of Table A with 8,434 units of raw material rather than 8,000 units. The reader might be interested in recursive programming applications to the problem of capital acquisition over time which are developed by Spivey and Godfrey (10). 16

-11 -Instead of resolving the entire problem with this revised right hand side, the new optimal program can immediately be developed by observing that it is obtained by adding the slack activity to the original optimal basic program at a level SL3 =-434. Hence, from the final tableau of the original problem one can write the following equations for the new optimal program. x = x* - ax3SL3 = 1,142 - (-1/28) (-434) = 1,126.5 y'= y* - a SL3 = 1,143 - (-1/28) (-434) = 1,127.5 z' = z* - a SL3 = 1,143 - (6/28) (-434) = 1,233 The incremental contribution margin is obtained from the dual price of slack activity 3 as (19/28) (434) = 294.5' Here again, the optimal adjustment can be guided on a decentralized basis by providing each department with information on the marginal rates of. substitution which prevail within the department and with data as to the extent of resource adjustments which prevail between planning periods. Summary and Extensions The objective of this paper has been to show how the post-optimality features of linear programming provide a method for guiding the optimal adjustment to unplanned deviations affecting the firm's planning process. These features allow a firm to dynamically update an intra-period base plan as new information becomes available. They also allow the firm to optimally allocate those resources which can be shifted between periods to minimize the effects of intra-period adjustments. Moreover, in both of these cases, the post-optimality features utilize economic information which can be conveyed in individual departments so that optimal adjustments can be made adaptively on a decentralized basis. Unfortunately, the extent of the information required to perform adjustments to certain technological changes may limit the applicability of decentralized con trol in this class of situations. In the majority of situations, however, the only informational requirement is knowledge of the marginal rates of substitution between the activities conducted by the department.

I^ i~~~~~~~~~~r,.~~~~~~~~~;. r -12 - I The examples studied here assume that the intra-period planning models are identical with no inter-period linking constraints. Non-identical models create no problem; the post-optimal adjustments are merely made on the final tableaus for the appropriate periods, Inter-period linking of constraints can be handled by treating the N period planning problem as a single, large linear programming problem. Alternatively, prices can be set on the linking constraints thereby modifying the intra-period unit contribution margins to account for the effects of such constraints. This latter approach gives rise to the discomposition of the large problem into a sequence of intra-period problems /See, for instance Spivey & Thrall (9:pp 351-36427.

Appendix A Sensitivity of Optimal Tableau to Changes in Basic Activity Coefficients Suppose we are given the following initial tableau for a linear programming problem b x y z SLI SL2 SL3 0 -2 -3 -4 0 0 0 8000 5 1 11 0 0 8000 1 5 1 0 1 0 8000 1 1 5 0 0 1 Then it is well known /Spivey & Thrall (9), pp. 139-1451 that the optimal basic program for the problem can be attained by premultiplying the first column of the initial tableau by the inverse of a matrix whose columns are the coefficients of the optimal basic activities. In this case the matrix is: 5 1 1 A a 1 5. 1 1 1 5 with the following inverse which can be directly computed or found from the final tableau*: 6/28 -1/28 -1/28 -1 -1/28 6/28 -1/28 -1/28 -1/28 6/28 *~. ' 800 0 *Note that the elements of A-1 are the marginal rates of substitution between activities for all departments. -13 -

O i r 1 I w r I r ~e, -14 -Suppose that the original problem is modifed by changing the coefficient in row three, column two of the initial tableau from 1 by a general value of o. Then if we assume that 6 is constrained so that the optimal basic activities are unchanged, the A matrix becomes: 5 I 1 A' = 1+ 5 1 I 1 5 and we can write A' A + UV where 0 I U = V [0 0 0 Furthermore, the inverse of A' can be computed from the inverse of A by using the following result /Rao (6), p. 29/:,-1 -= 1 -ll_0 )(V A (A') = A 1- 1 1+ V AU The revised optimal program for the linear programming problem can be found by pre-multiplying the first column of the original tableau by (A') 1 Equivalently, we can pre-multiply this column by -(A-l vt-l) 1 + VtAU and add this "perturbation vector" to the original optimal program (given in Table A of this paper). For the data of this problem Q is given by: -6 1 1 -6 1

I B -15 -and the perturbation vector is given by -.6 1 i1 8000 32,000 o36 -6 -6 8000 3 192,000 784(1+0) 784(1- ) -6 1 1 8000 32,000 For the change outlined in the text of the main paper e=-1/6. Hence the perturbation vector becomes: 32,000 -8 -i -192,000:48 5(784) 32,000-8 Therefore, the revised optimal program is obtained by reducing the outputs of departments 1 and 3 by 8 units and increasing the output of department 2 by 48 units with an incremental contribution margin of 2(-8) + 3(48) + 4(-8) = 96. This result is interesting and important, for it illustrates that the optimal corporate adjustment for a technological advance achieved in Department 1 is for Departments 1 and 3 to reduce output. A sub-optimal adjustment is made if department 1 utilizes its improved technological relationship to increase output! a

S$ -16 -Unfortunately, guiding the optimal departmental adjustments to technological improvements such as the one outlined here is a difficult problem. This is true because the computation of the perturbation vector requires knowledge of the marginal rates of substitution between activities in all departments as well as knowledge of the technological change to which the firm is adapting. Thus, adjustment must be made on a centralized basis or all marginal rates of substitution must be communicated to all departments. This latter alternative is likely to be infeasible in view of the massive information flow problem and computational burden created in large-scale applications.

-17 -References (1) Bernhard, R.H., "Some Problems in Applying Mathematical Programming to Opportunity Costing," Journal of Accounting Research (Spring, 1968), pp. 143-148. (2) Dantzig, G. B., Linear Programming & Extensions, Princeton University Press, 1963. (3) Dempski, J. S., "An Accounting System Structured on a Linear Programming Model," The Accounting Review (October, 1967), pp. 701-712. (4) Godfrey, J. T., Spivey, W. A., and Stillwagon, G. B., "Production and Market Planning with Parametric Programming," Industrial Manaemnt Review (Fall, 1968), pp. 61-76. (5) Jenson, R. E., "Sensitivity Analysis and Integer Linear Programming," The Accounting Review (July, 1968), pp. 425-446. (6) Rao, C. R., Linear Statistical Inference and Its Applications, Wiley, 1965. (7) Rappaport, A., "Sensitivity Analysis in Decision Making," The Accounting Review (July, 1967), pp. 441-456. (8) Samuels, J. M., "Opportunity Costing: An Application of Mathematical Programming," Journal of Accounting Research (Autumn, 1965), pp. 182-191. (9) Spivey, W. A., and Thrall, R. M., Linear Optimization, Holt, Rinehart, & Winston, 1970. (10) Spivey, W. A., and Godfrey, J. T., Models for Cash Flow Estimation in Capital Budgeting, Bureau of Business Research Working Paper No. 17, The University of Michigan, December, 1970. r a

-18 -WORKING PAPERS;~ ~Working Paper Number; 1 "Reflections on Evolving Competitive Aspects in Major Industries," by Sidney C. Sufrin 2 "A Scoring System to Aid in Evaluating a Large Number of Proposed Public Works Projects by a Federal Agency," by M. Lynn Spruill 3 "The Delphi Method: A Systems Approach to the Utilization of Experts in Technological and Environmental Forecasting," by John D. Ludlow 4 "What Consumers of Fashion Want to Know," by Claude R. Martin — out of print. To be published in a forthcoming issue of the Journal of Retailing. 5 "Performance Issues of the Automobile Industry," by Sidney C. Sufrin, et. al. —out of print. To be published as a future Michigan Business Paper. 6 "Management Experience with Applications of Multidimensional Scaling Methods," by James R. Taylor 7 "Profitability and Industry Concentration," by Daryl Winn 8 "Why Differences in Buying Time? A Multivariate Approach," by Joseph W. Newman and Richard Staelin —out of print. To be published in a forthcoming issue of the Journal of Marketina Research. 9 "The Contribution of the Professional Buyer to the Success or Failure of a Store," by Claude R. Martin, Jr. 10 "An Empirical Comparison of Similarity and Preference Judgments in a Unidimensional Context," by James R. Taylor 11 "A Marketing Rationale for the Distribution of Automobiles," by H.O. Helmers —out of print. To be published as a future Michigan Business Paper. 12 "Global Capital Markets," by Merwin H. Waterman 13 "The Theory of Double Jeopardy and Its Contribution to Understanding Consumer Behavior' by Claude R. Martin, Jr. 14 "A Study of the Sources and Uses of Information in the Development of Minority Enterprise —A Proposal for Research on Entrepreneurship," by Patricia Braden and H. Paul Root 15 "Program Auditing," by Andrew M. McCosh

r g r 1 I Work:: -19 -ing Paper Number 16 "Time Series Forecasting Procedures for an Economic Simulation Model," by Kenneth 0. Cogger 17 "Models for Cash Flow Estimation in Capital Budgeting," by James -T. Godfrey and W. Allen Spivey 18 "Optimization in Complex Management Systems," by W. Allen Spivey 19 "Support for Women's Lib: Management Performance," by Claude R. Martin, Jr. 20 "!'nnovations in the Economics of Project Investment," by Donald G. Simonson 21 "Corporate Financial Modeling: Systems Analysis in Action," by Donn C. Achtenberg and William J. Wrobleski 22 "Sea Grant Delphi Exercises: Techniques for Utilizing Informed Judgments of a Multidisciplinary Team of Researchers," by John D. Ludlow 23 "The Spanish in Nova Scotia in the XVI Century —A Hint in the Oak Island Treasure Mystery," by Ross Wilhelm 24 Not yet ready for release 25 "Market Power, Product Planning, and Motivation," by H. Paul Root 26 "Competition and Consumer Alternatives," by H. Paul Root and Horst Sylvester 27 "Stepwise Regression Analysis Applied to Regional Economic Research," by Dick A. Leabo 28 "Some New Statistical Methods for Analyzing Incomplete Brand Preference Data," by M.J. Karson and W. J. Wrobleski 29 "Multivariate Methods in Marketing Research: A Further Attempt at Classification," by Thomas C. Kinnear and James R. Taylor 30 "A Deductive Approach to Linear Optimization," by W. Allen Spivey 31 "A Stochastic Model of the National Political System in the United States," by Neal Campbell and Cyrus K. Motlagh 32 "Implementation of Risk Analysis Models for the Management of Product Innovations," by H. Paul Root A 9