Zeitschrift ./fir Operations Research, Band 19, 1975, Seite 15-18. Physica-Verlag, Wfirzbur9.

Planning for Repetitive Cycles Using an Infinite Horizon Linear Program x) By A. J. Michel, Boston 2) Eingegangen am 5. Oktober 1973

Summary: Termination conditions are often difficult to model in a linear program. This paper discusses the use of an infinite horizon linear program which may enable the termination conditions to be modeled more accurately. It can be applied situations where a repetitive cycle (i. e. season) exists and generates steady state values of the decision variables. Examples are then given illustrating the use of the infinite horizon linear program.

Zusammenfassung: Vielfach ist es schwierig, Abschlugbedingungen in ein LP-Modelt einzubauen. In diesem Aufsatz wird die Verwendung eines linearen Modetlansatzes mit unendlichem Horizont diskutiert, der es erm6glicht, Abschlugbedingungen auf sehr sorgf'~iltige Weise zu formulieren. Er kann in solchen F~illen verwendet werden, in denen ein sich wiederholender Zyklus (z. B. Saisonzyklus) gegeben ist, und liefert stabile Werte fiir die Entscheidungsvariablen. Es werden Beispiele zur Anwendung des linearen Modellansatzes mit unendlichem Horizont gegeben.

Current Procedures Any linear programming problem describing a set of decisions over a planning horizon must include initialization and termination conditions. Initialization conditions specify the state of the system at the beginning of the horizon; they incorporate the effect of all previous decisions. In fact, the effect of all previous decisions is incorporated throughout the entire planning horizon. Termination conditions are usually more difficult to specify. Often minimum or maximum limits on decision variables are set in the final period, as in Orgler [1969] where payables are constrained to be less than or equal to some fixed value in the final period of the horizon. Termination conditions for variables such as advertising, which have a carryover effect from period to period, cannot be specified using this method in the final period. If no limiting conditions are used and the response is calculated only over the planning periods i = 1..... Q, where Q is the final period in the horizon, the advertising in period Q is understated. This arises because there are contributions in periods Q + 1, Q + 2 ..... as well. 1) The author thanks John McClain of Cornell University for suggesting this topic and making numerous helpful suggestions. 2) Prof. Dr. Allen J. Michel, Department of Finance, Boston University, 212, Bay State Road, Boston, Massachusetts.

16

A. J. Michel

Only if the advertising effectiveness decays very rapidly will Orgler's method be appropriate. Depending on that decay rate, one or more periods can be added at the end of the horizon to correct the situation. This approach is used by Lodish in his advertising mathematical programming model. When using this method of adding an additional period (or periods) to the formulation, the problem of determining the number of additional periods still remains. One way of looking at the problem is to successively increment the number of periods, checking the decision set over the original horizon after each increment. This process is halted when the decision set remains the same (or deviates less than a fixed amount for two successive iterations). The benefits of this approach, however, must be weighed against cost considerations. Costs include not only the cost of increased computation, but also the cost incurred from forecast inaccuracy, due to the length of the forecast.

Model Description In situations in which there exists a repetitive cycle (i.e. season) over which the problem can be solved, an infinite horizon L.P. model can be developed. This approach requires that all demands, coefficients, etc. remain unchanged from cycle to cycle. For example, inventory in the final period of the cycle is the initial inventory of the following cycle. Thus, in the steady state, since the cycles are unchanged, the final period inventory must also be equal to the initial inventory of the same cycle. Recognizing that I 0, the initial inventory, will equal I a in the steady state, if Q periods represent a cycle and there are no changes in the coefficients of demands, the problem is solved for the optimal starting conditions and the steady state values over the horizon. There are a number of reasons for investigating a steady state solution. The user of this solution, learning the values of the long-run optimal decisions, can then compare the optimal starting conditions and resulting decisions with the initial conditions and decisions he would otherwise follow. He then has the option of making decisions based upon the steady state optimal values. Another important reason for considering the use of the infinite horizon L.P. approach is that the ending conditions may be modeled more accurately. The ending conditions in this formulation optimally prepare the model to enter another cycle. The optimal ending conditions for one cycle are also the optimal initial conditions of the next cycle.

Examples This approach can be best illustrated with an example. The standard inventory identity equation can be written as follows: i

go + ~ (Pj j=l

Y j ) = I i.

Planning for RepetitiveCyclesUsing an Infinite Horizon Linear Program

17

Where I o = Initial inventory Pj = Production in period j Yj = Sales in period j I i = Inventory at the end of period i The method suggested here would set the initial inventory level equal to the final period inventory level, i.e.: Io = IQ and solve for I~. Thus, the final period inventory level would be substituted wherever the initial inventory level appeared. All decisions which are not affected by periods prior to the beginning of the horizon can be treated similarly. The model would solve for both the optimal starting conditions and the steady state solution over the horizon. More difficult to formulate is an advertising constraint which includes the effects of prior advertising. An example, is the advertising constraint formulated by Thomas [1971] as follows: i z i = 1 ..... Q

Yik
Where

Y', ejzkAj~krl~ -j

z=l

k = I,...,K.

K = Yik = Sik = Aj~ k =

number of products amount sold of product k during period i base demand (without advertising) of product k during period i dollars spent on the zth segment of advertising in period j of product k q},-J = decay factor, where advertising of product k in periodj has decayed over i - j periods in period i eizk = advertising effectiveness (units of demand added per dollar of advertising) of Ajz k Z = number of segments. This constraint limits sales to an amount less than or equal to the base demand, plus the demand created by advertising. The constraint using the infinite horizon L. P. approach could be reformulated as: Z

Yik <--Sig + ~

~, ei-~,~,k Ai-~,~,k rl~ .

s=0 z=0

Here s is a dummy variable representing the number of periods prior to period i. Thus, it is through the dummy variable that the effects of prior periods are entered into the model. Two cases will be described in the following discussion. The first case arises when i is greater than the period in the horizon corresponding to s periods prior to i. The second case arises when the period in the horizon corresponding to s periods back is greater than or equal to i. In the former case, where i > s mod Q, if s' is defined as s mod Q, then i - s' indicates the period in the horizon corresponding to s periods prior to i. In the latter case, where i < s rood Q, if s" is defined as Q - s mod Q, then i + s" indicates the period in the horizon corresponding to s periods back. When s' = s mod Q,

18

A. J. M i c h e l

there exists an integer L such that s = s ' + (j'Q). When s " = Q - s rood Q, there exists an integer j, such that s = Q - s" + (j" Q). Thus, the steady state formulation, incorporating a horizon of Q periods can be written as:

Y~k -<- ~ik + ~, s'=l

ei_s,,z, kAi_~,,~,krfk'+JQ + ~ j=O

,~ + s",z,k.CXi a + s " , z , k ,~O.-s"+jO. *.,i ~lk .

s"=O j=O

For each period in the horizon, the above expression can be expanded in an infinite geometric series and expressed in closed form, obtaining:

~ -< ~'~ + ~

r 2__ e~_~,,~,kA,_~,,~,k~'+~2 e'+s"'~'kA'+~"'z'k~-~"_l-1 " L~ 1

~,,=o

Conclusion

In situations where seasonality exists, the steady-state values of the decision variables can be generated using the infinite horizon L. P. approach suggested in this paper. This approach may also enable the ending conditions to be modeled more accurately. These values of the long-run optimal decisions can then be used by management as an important input in determining the decisions the firm will actually follow throughout the horizon. References Mathematical Models for Media Planning, Unpublished Ph.D. Dissertation, Massachusetts Institute of Technology. Orgler, Y . : An Unequal-Period Model for Cash Management Decisions, in: Management Science 16, No. 2, B77-B92, 1969. T h o m a s , J . : Linear Programming Models for Production Advertising Decisions, in: Management Science 18, No. 8, B474-B484, 1971. Lodish, L . :