NATIONAL BUREAU OF STANDARDS REPORT

10 498

SEQUENCING THE PURCHASE AND RETIREMENT

OF FIRE ENGINES

Prepared for

The Fire Research Program

National Bureau of Standards

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards 1 was established by an act of Congress March 3, 1901. Today,

in addition to serving as the Nation’s central measurement laboratory, the Bureau is a principal

focal point in the Federal Government for assuring maximum application of the physical and

engineering sciences to the advancement of technology in industry and commerce. To this end

the Bureau conducts research and provides central national services in four broad program

areas. These are: (1) basic measurements and standards, (2) materials measurements and

standards, (3) technological measurements and standards, and (4) transfer of technology.

The Bureau comprises the Institute for Basic Standards, the Institute for Materials Research, the

Institute for Applied Technology, the Center for Radiation Research, the Center for Computer

Sciences and Technology, and the Office for Information Programs.

THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the United

States of a complete and consistent system of physical measurement; coordinates that system with measurement systems of other nations; and furnishes essential services leading to accurate and

uniform physical measurements throughout the Nation’s scientific community, industry, and commerce. The Institute consists of an Office of Measurement Services and the following technical

divisions:Applied Mathematics—Electricity—Metrology—Mechanics—Heat—Atomic and Molecular Physics—Radio Physics -

Radio Engineering 2—Time and Frequency -—Astrophysics -

Cryogenics.2 THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research leading to im- proved methods of measurement standards, and data on the properties of well-characterized

materials needed by industry, commerce, educational institutions, and Government; develops,

produces, and distributes standard reference materials; relates the physical and chemical properties of materials to their behavior and their interaction with their environments; and provides

advisory and research services to other Government agencies. The Institute consists of an Office of Standard Reference Materials and the following divisions: Analytical Chemistry—Polymers—Metallurgy—Inorganic Materials—Physical Chemistry.

THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services to promote

the use of available technology and to facilitate technological innovation in industry and Government; cooperates with public and private organizations in the development of technological

standards, and test methodologies; and provides advisory and research services for Federal, state, and local government agencies. The Institute consists of the following technical divisions and

offices: Engineering Standards—Weights and Measures — Invention and Innovation — Vehicle Systems Research—Product Evaluation—Building Research—Instrument Shops—Measurement Engineering—Electronic Technology—Technical Analysis.

THE CENTER FOR RADIATION RESEARCH engages in research, measurement, and application of radiation to the solution of Bureau mission problems and the problems of other agencies and institutions. The Center consists of the following divisions: Reactor Radiation—Linac Radiation—Nuclear Radiation—Applied Radiation. THE CENTER FOR COMPUTER SCIENCES AND TECHNOLOGY conducts research and

provides technical services designed to aid Government agencies in the selection, acquisition, and effective use of automatic data processing equipment; and serves as the principal focus

for the development of Federal standards for automatic data processing equipment, techniques,

and computer languages. The Center consists of the following offices and divisions: Information Processing Standards—Computer Information — Computer Services — Sys- tems Development—Information Processing Technology.

THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination and

accessibility of scientific information generated within NBS and other agencies of the Federal government; promotes the development of the National Standard Reference Data System and a system of information analysis centers dealing with the broader aspects of the National Measure- ment System, and provides appropriate services to ensure that the NBS staff has optimum accessibility to the scientific information of the world. The Office consists of the following

organizational units: _

Office of Standard Reference Data—Clearinghouse for Federal Scientific and Technical Information —Office of Technical Information and Publications—Library—Office of Public Information—Office of International Relations.

' Headquarters and Laboratories at Gaithersburg. Maryland, unless otherwise noted: mailing address Washington. D.C. 20234.

- Located at Boulder. Colorado 80302.

3 Located at 5285 Port Royal Road, Springfield. Virginia 22151.
NATIONAL BUREAU OF STANDARDS REPORT

ms PROJECT NBS REPORT

4314162 December, 1971 10 498

2050153

SEQUENCING THE PURCHASE AND RETIREMENT

OF FIRE ENGINES

R ichard Ku

T echmcal Analysis Division

Patsy B. Saunders

Applied Mathematics Division

Approved:

Approved:

T echnical Analysis Division

Applied thematics Division

IMPORTANT NOTICE NATIONAL BUREAU OF SI

for use within the Government, and review. For this reason, th whole or in part, is not autho Bureau of Standards, Washing!

the Report has been specifically

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015.

ss accounting documents intended

subjected to additional evaluation

listing of this Report, either in

e Office of the Director, National

by the Government agency for which

copies for its own use. <NBS>

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

TABLE OF CONTENTS

Page

1. Introduction 1

2. Initial Considerations 5

3. A Dynamic Programming Model 10

4. Concluding Comments 22

5. References 24

Appendix A: Details of the Dynamic Programming Model A-l

Appendix B: Listing of the Computer Code for the

Dynamic Programming Model B-l

Appendix C: An Integer Programming Model C-l
TABLES AND FIGURES

Page

Figure 2.1: Contours of Optimum Engine Life 8

Table 3.1: Data for the Dynamic Programming Model 17

Table 3.2: Results of Finer Variation in r for Certain

Values of 20

Table A-l: Formulas for the Ranges of the Variables in

the Dynamic Programming Model A- 19
ACKNOWLEDGEMENTS

The cooperation of the Washington, D. C. Fire Department is greatly

appreciated. We would like to thank A. J. Goldman of the Applied

Mathematics Division for his assistance, especially in the preparation

of Appendix A, and D. Coiner and W. Steele of the Technical

Analysis Division for their helpful comments and suggestions.

SEQUENCING THE PURCHASE AND RETIREMENT

OF FIRE ENGINES

1. INTRQIXJCTION

This report describes a method to determine an "optimum"

manner of sequencing the purchase and retirement of fire engines

(hereafter simply called "engines"), with specific application

to the Washington, D. C. Fire Department. The model developed,

however, has more general applicability as regards both the

equipment type and the fire department. Because of the apparent

similarity of the present problem to conventional equipment

replacement problems , we first review in brief some of the ideas

in the equipment replacement literature.

Equipment replacement problems have a long history in

industrial engineering and operations research. The reader

is referred to [8] for a comprehensive bibliography on this

subject. One class of equipment replacement problems balances

the cost of failures against the cost of planned replacements

(see [3]). If units are to operate continuously over some time

period [o , t] and are replaced upon failure, then typically the

expected cost C(t) during [0, t] may be given by

C(t) = c

1

ErN

1 (t)] + c

2E[N2 (t)], (1.1)

where

1
c^ = per unit total cost resulting from a failure and its

replacement

c 7 = per unit total cost of replacing a non-failed item < c^)

N-^(t) = the number of failures in [0, t] , a random variable,

N

? (t) = the number of replacements of non-failed units, a random

variable,

and E denotes expected value. The problem is to minimize (1.1) OA/'er

the possible replacement procedures available within a given policy

of replacement. Examples of replacement policies are: strictly

periodic replacement, random periodic replacement and sequentially

determined replacement. Electronic components typify the equipment

to which this well developed mathematical theory applies.

A second class of equipment replacement problems , called

"preparedness" problems, assumes that a piece of equipment is kept

in a readiness state for use in case of emergency. The objective

is to maintain the equipment in a state of operational readiness

at minimal cost. Thus a sequence of inspection and replacement actions

that minimizes the ratio of expected cost per unit time to proportion

of good time, would constitute an "optimal" decision stream (see

[8], [10]). Large military hardware provides examples of the type

of equipment to which this class of models may be applied.

One of the basic underlying concepts of the two classes of

equipment replacement models discussed so far is that of a reliability

2
function . This is the probability R(t) that the equipment is "good""

at time t (measured from a time at which the equipment is considered

to be "new") and is exemplified by the negative exponential form

R(t) = exp (-At). (1.2)

A closely related concept is the failure rate, defined for any

reliability function R(t) as p (t) = -R"(t)/R(t), where the prime

denotes the derivative. For the negative exponential, the failure

rate is the constant A. A third class of equipment replacement problems deals with

the replacement of items that deteriorate. Mathematical models to

solve this class of problems typically trade off the increasing

operational and maintenance costs (and decreasing resale value ) of an

aging item against the cost of a new purchase, i.e., the "optimal"

replacement time is that time at which these opposing forces are

equalized. Dreyfus [6] used a dynamic programming approach to solve

this problem under the additional complication of technological change.

The main concern of this report is the development of a model to

determine purchase and retirement decisions over a planning period,

subject to certain constraints, which would minimize the cost of

^See [11] for a discussion of the statistical theory of reliability.

2 It is implicitly assumed that the equipment is either in a "good" or a "failed" state.

3
operation of a fleet of engines during that period. The concern of the

Washington, D. C. Fire Department was not with the cost of failure

or the distribution of failures of fire engines per se , primarily

because of the negligible number of engine failures and the inability

to measure the "cost" of a single engine failure. The model developed

may be regarded as an extension of the ideas represented by the

third class of equipment replacement problems discussed above.

Section 2 describes a simple calculation, which serves to

introduce the data at hand and compares the results of this calculation

(as applied to Washington, D. C.) to those of a study [2] from which

the data were obtained. A dynamic programming (DP) model is formulated

and given illustrative application in Section 3, and directions for

further investigation are suggested in Section 4. Appendix A

develops certain details of the DP model and a listing of the DP

computer code appears in Appendix B. Finally, an integer programming

(IP) analog to the DP model is given in Appendix C.

I

4
2 . INITIAL CONSIDERATIONS

Aside from personal communications with members of the staff of

the Washington, D. C. Fire Department, the main source of data was

a report by Balcolm [2], This report also proposes a model, for

determining the life-span of an engine, which will be described later.

A linear relationship between engine age and maintenance cost was

used in [2]

,

and least-squares regressions yielded three sets of

coefficients, corresponding to "high usage," "medium usage," and

"low usage" engines. Balcolm then obtained a "composite" equation-

a weighted average (by the number of engines in the three categories) --

which this report also uses. This equation is of the form:

u

a

= U

0 + U

l a ’ (2 - 1}

where

a = engine age,

u

&

= the maintenance cost of an engine entering its a

1^ year of

service

,

U

Q = 24.17,

U-^ = 122 .46/year.

2

Values of are listed in Table 3.1. This relationship was adopted

as the basis of the data for maintenance cost since it was felt that a

more complex function could not be supported by the observed cost

figures.

3

All monetary quantities are expressed in dollars.

5
A linear relationship was also used in [2] for the purchase

price of a new engine, given by

p

t

= p

0 + p! (t - 1900), (2.2)

where

p

Q = -16258.18,

P

1 = 576.87.

Values of p

t are given in Table 3.1. The choice of the "base" year

1900 is not explained, but it accounts for the surprising (negative)

value of p g. The index t refers to the year for which a value of the

purchase price is desired.

Using these data, a simple calculation can be made to determine

an "optimum" life-span for a single engine. Assuming a zero salvage

4

value (for simplicity) and a constant purchase price, the accumulated

total cost of keeping an engine for n years is

n

TC(n) = l (U + U a) + P

a=l n

= nUn + U, I a + p

0 1 ail

= nU

Q

+ [n(n+l)/2] Uj + P. (2.3)

Thus the average annual cost of keeping an engine for n years is

AC(n) = TC(n)/n

= U

Q + [ (n+l)/2] U

x + p/n. (2.4)

4 Constant salvage values (with respect to age) can be represented

by subtracting them from Uq.

6
Clearly, the longer an engine is kept, the longer the time to amortize

the price P, so that portion of the cost per year will decrease with

n. However, the maintenance costs increase year by year. Thus, with

the "optimum" life-span defined as that value of n which minimizes (2.4)

, the standard calculus technique of setting the derivative of

(2.4) to zero and solving for n yields:

(d/dn) (AC (n) ) = iy2 - P/n2 =0, (2.5)

whence

n = (2P/U

1

) 1/2

. (2.6)

3 Since P > 0 and n > 0, the second derivative 2P/n is positive

so that the value of n given in (2.6) ensures a minimum value of

(2.4)

. Figure 2.1 indicates contours of the optimum value of n in

the (U-^ , P) -plane

.

For Washington, D. C. , using the 1969 purchase price, (2.6)

yields n = 19.6, considerably larger than the present life span of

15 years. Balcolm [2] recommends a life span of 10-11 years, depending

on the number of years over which an engine is linearly depreciated,

using as his criterion the equality of current (resale) value and

accumulated repair cost, i.e., n is chosen so that

P - n(P - S)/N = l U

a

, a=l

where N is the number of years over which an engine is depreciated

and S is the salvage value of an engine after N years. (Note that

Balcolm assumes that the number of years over which an engine is

depreciated (N) and the number of years it is kept (n) need not

7
RATE

OF

INCREASE

IN

MAINTENANCE

COST

(U-, )

,

IN

DOLLARS

FIGURE 2.1 CONTOURS OF THE OPTIMUM ENGINE LIFE

8
be the same.) No rationale for this criterion is offered in [2],

but the large difference between [2

]

T s "optimum" life span and

the one derived from the present calculation indicates a significant

difference between the two models.

9
3. A DYNAMIC PROGRAMMING MODEL

The dynamic programming (DP) model described in this section

takes a somewhat different approach to the problem of equipment

replacement. Instead of determining an "optimum" life-span which

would be applied to all engines, the DP model begins with the

existing scenario and prescribes purchasing and retiring decisions

over a T-year planning horizon. (The index t = 1, . .

. , T is used

in this model and appropriate notation changes' are made in the relevant

formulas presented in Section 2.) In this sense, the model may

be "tailored" to fit the initial state of affairs of any urban

fire department. The reader interested in DP in general, is

referred to the text [9]. For other DP formulations of equipment

replacement problems, see [1] and [4].

In accordance with the concerns and objectives of the Washington,

D. C. Fire Department, the DP model determines the purchases and

retirements to be made during the planning horizon such that the

total cost incurred during this period is minimized. The model

accounts for various constraints within which a fire department must

operate, e.g., constraints on the number of purchases and/or

retirements which may be made in any year, the total fleet size,

and the maximum allowable engine age.

The DP "state variables" (those which describe the system

at each stage, or year in this case) are:

10
x^

t = the number of engines in the initial fleet which

remain in year t-1,

x9 = the number of new engines purchased in years l,...,t-l,

x^

t = the maintenance cost in year t-1 on engines purchased

in years 1, . . . ,t-l.

(Note that x^

t + x9 is the fleet size in year t-1.) The "decision

variables" are

dlt = number °f engines retired from the initial fleet in

year t,

d7 = the number of engines purchased in year t.

It should be emphasized that retirements are made only from engines

in the initial fleet, i.e.

,

none of the engines purchased during the

planning period are considered for retirement. Since the

Washington, D. C. Fire Department indicated interest in a planning

horizon of at most five to ten years, restriction to retiring

engines from the initial fleet only is not considered a limitation.

The data required by the model are :

D = the minimum number of engines required during year t (checked

against the fleet size after year t's decisions have been

made) ,

= the maximum number of engines which may be purchased in year t,

c That adequately measures the demand for fire

...service is a simplification.

11
= the maximum number of engines which may be retired in year t,

R = the age by which engines must be retired,

P

t = the purchase price of a new engine in year t,

Q

= the number of a-year old engines in the initial fleet,

ci

= the initial fleet size,

a u = the maintenance cost of an engine during its a

t^L year of

cl service

v = the resale value in year t of an engine which was initially

r 6 of age a,

a^ = the age of the i^ youngest engine in the initial fleet

(e.g. , a^ is the youngest).

As in the simple model of section 2, the maintenance costs are

calculated as

u

a

= U

0 + Ul a >

I with the values of Up and U^, as indicated earlier. The linear

relationship leads to a recursive definition of u

u

a+l

’ U

0

+ Va+«

= U„ + Uja + Uj (3.1)

= u

a

+ U

lLetting x

f = (x^^, x 9l_, x^) , (3.1) may be used to obtain, as

the stage transformation formula,

^The convention is adopted that an £-year-old engine in the initial fleet

enters its (a+l)st year of service at t=l. It is assumed, for simplicity,

that decisions are made at the beginning of a year, and that a>l.

12

m = I Q
x (3.2) t+1

= (xlt - d

It’

X

2t

+ d

2t ’ 3t

+ u

l d2t

U

l x2t }

-

The transformation for and x

?t

is clear. The value of x^ , the

maintenance cost in year t on engines purchased in years' 1,. .. ,t,

is obtained by adding to both the cost of the first year of

maintenance for engines purchased in year t (u^d

?t ), and the

incremental increase in maintenance cost on engines purchased in the

preceding years (UjX 9 ) , the latter deriving from (3.1).

The "stage return" is the cost of operation in year t. With

the notation d^ = (d^ , d 9 ) , the stage return is calculated as:

x

it"

d

it

I t

(x

t ,dt

) = (P

t

l

i=l

U

It

l v

a.+t • L a-t

1 i=x

i t

- d

it

+1 1

+ x

3t

+ U

lx2f (3.3)

The components of (3.3) have the following interpretations:

(P

t

+u

]_)^2t = t^ie cost Purchasing d2

t engines in

x

it'

d

it

l i=l

+ t

year t and maintaining them during the

first year of service,

= the maintenance cost in year t on engines

which remain from the initial fleet

,

It

l v

j ,, a.+t

1=x

it.-

d

it

+1 1

= the revenue from retiring the d^ oldest

engines not previously retired,

1^

'Whenever the lower limit of a summation exceeds the upper limit, the.

summation is taken to be zero. This is a standard notational convenience.

°This assumption of retiring "oldest" first" is supported by the

Washington, D. C. Fire Department.

13
x^ + U^x-^ = the maintenance cost in year t on engines

purchased in years l,...,t-l.

The linear form of the maintenance cost yields the pleasing

9 result that the values of x^ are all exact multiples of U-^. This,

together with the fact that x^^ and x

?t are integers bounded by the

constraints, makes it computationally feasible to consider all of the

combinations of values that the state variables may assume in any

stage. It follows that the optimal solution is exact , a condition

not often found in DP problems. This characteristic is explicitly

noted here as a favorable feature of the model.

The recursive equations of the DP model are:

f

t

(x

t

) = min [I t (x

t

,d

t

) + f

t+1 (xt+1 )/

(

1+r ) ]

d

t (3.4)

£j,(Xrp) = min I (Xrp,

h

The quantity r is a discount rate, so that division by (l+r) in the

first relation of (3.4) renders f^x^) as the minimum present value

cost of operations from years t through T, given that the state of the

system in year t is x^. Since the initial state is known to be

x^ = (m,0,0), f^(m,0,0) is the optimal value of the objective,

i.e., the minimum total cost of operations in years 1,...,T.

The constraints of the DP model are straightforward from the

definitions of the variables and parameters

9This will be proven in Appendix A.

14
0 i d ( 3 . 5 ) lt

^ N

t

(t =

Old,ti H

t (t-l,...,T), (3.6)

X

lt

+ X

2t - Dt-1 ( l =2 >- •

T+1 ) > (3.7)

t-1

1 (t = 2,...,T+1) (3.8)

j=l 3

where n = £ Q is the number of engines which must be retired

r a>R-t+l a

prior to year t because of the age limitation R. Note that by

definition the initial conditions are: x^ = m, x^ = 0, x^ = 0,

and n^ = 0 . With the definition Dq = m, ( 3 . 7 ) and ( 3 . 8 ) automatically

hold for t = 1.

The constraints ( 3 . 5 ) - ( 3 . 8 ) and the relationships among the

state and decision variables lead to interesting and computationally

useful results which are detailed in Appendix A. Suffice it to say

here that a special computer code,^ developed as a part of this effort,

takes advantage of these results to make it possible to solve larger

problems than could be handled by a general purpose DP code.

Furthermore, experience thus far has indicated that computer running

times are significantly shorter using the special code. For example,

one of the runs to be discussed below took 12 seconds using the

11

special code, while the general purpose code took 227 seconds.

^A listing of this code appears in Appendix B.

^This code is an extension of the code documented in [5].

15
(Both codes are written in FORTRAN V and runs were made on the UNIVAC

1108 at NBS under the EXEC II Operating System.)

In exercising the DP model, the maintenance costs and purchase

prices were the same as those discussed previously (cf . , Section 2)

The purchase price function was modified to

p

t

= p

0 + p! (70 + t), (3.9)

so that t = 1 would correspond to 1971. The values of and P^ are

unaffected by the modification and remain as listed under equation

(2.2). The resale values v were calculated on the basis of (3.9),

assuming an annual depreciation rate p, as

v

at = a - p)

a+t_1

[P

0

+ Pj (70-a+l)], (3.10)

so that resale values of engines in the initial fleet (purchased

1

prior to t = 1) could be calculated from the appropriate purchase prices.

Finally, values of Qa were obtained directly from the Washington, D. C.

Fire Department's inventory of engines. These data are given in

13 Table 3.1 with T = 5 (a five-year planning horizon).

For the remaining data specifications, it was suggested by members

of the Fire Department staff to take R = 15 (the present maximum

engine age in Washington), D = 64 for t = 0,...,5 (i.e. constant

A geometric depreciation is not required by the model. It is

incorporated in the code, but can easily be modified with minor

coding changes.

^Members of Fire Department staff advised that a planning period of

more than five years is unreasonable.

16
TABLE 3.1 - DATA FOR THE DYNAMIC PROGRAMMING MODEL

a Qa u

* a v* at

t=l t=2 t=3 t=4 t*5

1 4 147 14474 8684 5211 3126 1876

2 0 269 8477 5086 3052 1831 1099

3 10 392 4961 2977 1786 1072 643

4 5 514 2902 1741 1045 627 376

5 0 636 1696 1018 611 366 220

6 5 759 991 595 357 214 128

7 10 881 578 347 208 125 75

8 0 1004 337 202 121 73 44

9

5 1126 197 118 71 42 25

10 5 1249 114 69 41 25 15

11 3 1371 67 40 24 14 9

12 4 1494 39 23 14 8 --

13 4 1616 22 13 8 -- --

14 4 1739 13 8 -- -- --

15 5 1861 8 -- r» — -- --

t

1 (1971)

23

4

5 (1975)

p *

t 24700

25276

25853

26430

27007

Values have been rounded to the nearest dollar.

17
minimum required fleet size equal to the present fleet size) , and

M = = 6 for t = 1, . ..,5 (constant and equal purchase and retirement

ceilings)

A base run was made with no discounting, i.e. , r = 0, and the

resultant "optimal" decisions were to purchase and retire 6 engines

in each of the first three years and to purchase and retire 2 engines in

year 4, i.e., ^it

~

^"’t — ^ Cl- 1 > 2 , 3), d-^ ~

*^24 — ^ ’ ^15

— ^25

— ^

Note from the age distribution Q in Table 3.1 that 20 engines reach the

mandatory retirement age by year 5 (i.e. , n^ = 20). Since the

maximum number of retirements permissible is 6 in each year, the

optimal policy is to retire the 20 engines as soon as possible (ASAP

policy) , replacing them with new engines to meet the minimum required

fleet size.

The above results are not surprising in view of the discount

rate r = 0. Increasing maintenance costs, decreasing salvage values,

I and increasing purchase prices all indicate early retirement. The

same policy is optimal in the extreme case where the purchase price

is always zero. It is intuitively obvious that in this situation

the ASAP policy is optimal regardless of the value of r, since the

newly acquired (free) engines are operated at a lower maintenance

cost than are the old ones.

In order to study the effect of the discount rate r on the

optimal decisions, a series of runs was made with U-^ as a parameter,

taken from 62.46 to 162.46 in increments of 10.00. [Recall that

the "nominal" value of is 122.46.] Initially, r was varied from

18
0.0 to 0.5 in increments of 0.1 (a very rough grid), and based upon

these results, smaller ranges with finer increments were studied for

certain values of . The following observations were made consistently

from the outputs of all the runs

(1) The only engines retired were the 20 which reach their

maximum age during the 5 -year planning period.

(2) In every year, the numbers of purchases and retirements

were the same. This may be attributable to the constant

demand and to the constant and equal values of M and N

over all t.

(3) For those values of r considered, there was a value r^

such that for r <_ r^ the ASAP policy was optimal

,

and a value rT such that for r >_ r^ the optimal

policy was to retire as late as possible (ALAP policy)

[The ALAP policy has d^ ., = d^ ? = 5, d^ = d 0 ^_ = 4

(t=2, 3, 4), d-^r- = d 9 ^ = 3 for this particular problem.]

(4)

The values of r

£

, r, and r

? - r£ are monotonically increasing

functions of U^.

The values of U

1

for which the behavior of the optimal policy,

as a function of r, was studied in greater detail are listed in

Table 3.2 together with the relevant results. All other values of

U1 considered gave rise to values of r

£

= 0.0 and r

L

= 0.1 in

the initial runs. It can be seen from Table 3.2 that the finest

19
TABLE 3.2 - RESULTS OF FINER VARIATION OF r FOR CERTAIN VALUES OF THE

PARAMETER ^

U

1 Range of r Increment r

E

r

L

62.46 .01 - .10 .01 .05 .06

122.46 .08 - .09 .001 .080 .089

152.46 .01 - .20 .01 .09 .11

162.46 .01 - .20 .01 .10 .12

20
analysis with the smallest increments for r was made for the "nominal"

value of = 122.46. For .080 < r < .089 the optimal decisions

were "mixed", i.e.

,

neither an ASAP nor an ALAP policy. For example

with r = .085, the optimal decisions were

d = d „ 11 12

r-H fn

r d = d

23

d = d

15 25

d

12

d

22

6 ’

d

14

= d

24

= 3 ’

The "critical" range of r (.080, .089) is quite small, but it should

be noted that the values M = N = 6 do not permit a drastic

difference between the ASAP policy and the ALAP policy.

It is clear that if a value of r is specified, then the DP model

may be run to determine the optimal policy. If r cannot be specified,

then the values of r

p

and rT may be determined for a given value of

U^. Then one need only specify whether r £ r^ or r > r^ to conclude

that the ASAP policy or ALAP policy, respectively, is optimal.

One run was made with = 10 for all t and the other data

remaining the same.

case d^j - d-^-> — d0 -^

With r = 0, the ASAP policy resulted; in this

d 99 = 10, d^ = d^

t =0 (t = 3, 4, 5).

Unfortunately, lack of time prevented further study of this case.

Intuitively, one might expect a greater "critical" range of r since

the larger values of M and N given rise to a greater difference

between the ASAP and ALAP policies.

21
4. CONCLUDING COMMENTS

It should be emphasized that the DP model has considerably

greater generality than was indicated in the limited application

to Washington, D. C. The only model constraint on the data is that

they be self-consistent (e.g. , M^ and N^ must be consistent with D^).

If, for example, an urban fire department sees fit to reduce its

fleet size because of overkill capacity or perhaps because of

declining demand, and the values of M and N fluctuate because

of a fluctuating budget, then a greater portion of the model's

generality could be exploited. The interactions among the variables

and parameters of the model which are evident in Appendix A should

support this contention.

On the other hand, time limitations prevented any attempts to

examine the model with particular relationships among the

parameters. It seems reasonable that certain conditions, e.g.,

M. = N, = constant, or D. = a constant for all t, could lead

t t t

perhaps to closed-form optimal solutions, or at least might

simplify the necessary DP calculations. Further research along

these lines is recommended. In addition to these basic issues,

there is a need for further sensitivity tests, with respect

to the discount rate and the value of , for other values of the

parameters M^, N^ , D

t

, and R. For instance, the optimal values of

the objective f^ (m, 0, 0) could be compared for different values of

R (in some reasonable range of maximum ages) , leading to an "optimal"

22
value of R (i.e. one which minimizes f^ (m, 0, 0)). Finally, runs

with depreciation rate p varying, or using a different (perhaps

linear) depreciation policy, would be desirable.

23
REFERENCES

1. Ackoff, R. L. , Progress in Operations Research , John Wiley § Sons,

New York , (1961)

2. Balcolm, R. D. , "A Systems Analysis for the District of Columbia

Fire Department Dealing with the Replacement of Wagon Pumpers,"

report to the Washington, D. C. Fire Department (1970).

3. Barlow, R. E. and Proschan, F. , "Planned Replacement," Studies

in Applied Probability and Management Science , K. J. rmw et_ al_

(eds.), Stanford University Press, Stanford, California, pp. 63-87

(1962).

4. Britten, A. A., "Decision Making in Vehicle Management," Report

No. S.15, Local Government Operational Research Unit, Reading,

England, (1971).

5. Bellmore, M. , Howard, G. and Nemhauser, G. L. , "Dynamic Programming

Computer Model 4," The Johns Hopkins University, Baltimore, Md.

(1966).

6. Dreyfus, S. , "A Generalized Equipment Replacement Study," JSIAM,

Vol. 8, No. 3, pp. 425-435 (1960).

7. Geoffrion, A. M. and Nelson, A. B. , "Users’ Instructions for 0-1

Integer Linear Programming Code RIP30C," Memorandum RM-5627-PR,

The RAND Corporation (1968)

8. McCall, J. J. , "Maintenance Policies for Stochastically Failing

Equipment: A Survey," Management Science , Vol. 11, No. 5,

pp. 493-524 (1965).

24
9.

Nemhauser, G. L. , Introduction to Dynamic Programming, John

Wiley § Sons, New York (1967).

10. Radner, R. and Jorgenson, D. W. , "Optimal Replacement and

Inspection of Stochastically Failing Equipment," Studies in

Applied Probability and Management Science , K. J. Arrow et_ al

(eds.), Stanford University Press, Stanford, California, pp. 184-206

(1962).

11. Zelen, M. (ed.), Statistical Theory of Reliability , The University

of Wisconsin Press, Madison, Wisconsin (1963).

25
}
APPENDIX A

DETAILS OF THE DYNAMIC PROGRAMMING MODEL

This Appendix develops certain details of the DP model described in

Section 3. In particular, relationships among the variables are investigated

which make it possible to examine a limited number of states and

decisions for which the stage returns I^Cx^d^) are calculated.

Although technical in nature, this aspect of the problem is of great

importance to computational feasibility in the sense that computer

storage requirements and running times depend on the number of

states and decisions the algorithm must consider.

The definitions of the relevant variables and parameters are

repeated below for the reader's convenience:

Xf = the number of engines remaining from the initial fleet

in year t-1 (t=l, . .., T+l)

,

x

?t

= the number of new engines purchased in. years 1, ..., t-1

(t=l, T+l)

,

xT ^ = the maintenance cost during year t-1 on engines purchased

in years 1 ,. . . , t-1 (t= 1 , . .

. ,T+1)

,

d.lt = the number of engines retired in year t (t=l,...,T),

d 7 ^ = the number of engines purchased in year t (t=l,...,T),

= the minimum number of engines required in year t (t=l , . .

. ,T) ,

= the maximum number of engines which may be purchased in

year t (t=l,. .

. ,T)

,

= the maximum number of engines which may be retired in

year t (t=l,... ,T)

,

R = the age by which engines must be retired,

Q

= the number of a-year-old engines in the initial fleet

.

cl A-l
From these definitions, we may calculate two other quantities

which are used throughout the sequel:

m = £ Qa

= the number of engines in the initial fleet,

a

n = l Q

= the number of engines which must be retired

Z a>R-t+l a

prior to year t because of the age limitation R(t=2 , . . .T+l)

Note that by definition: = m, x? ^ = 0, x^ = 0> and n^ = 0.

It is notationally convenient to adopt the convention = m.

Using the definitions above, we may immediately establish the

relationships

It

" x

l,t-l

" d

i,t Ct-2,... ,T+1) (A-l)

2t

= X

2,t-1

+ F,t-.! (t= 2 , .

• ,T+1) (A- 2)

°^ d

lt iNt (t=l , . . . ,T)

1 (A-3)

0 - d

2t iMt

r+

II 1—

1 (A-4)

X

lt

+ X

2t -

i

—

II

4J ,T+1) (A- 5)

t-1

l d in (t-1 T+l) (A-6)

j=l J

We maintain our convention regarding sums, viz., a sum is zero if

its lower limit exceeds its upper limit. For example, (A-6) is

valid for t=l since both sides of the inequality are zero. The

variations in the index- ranges are due to the fact that the state
variables refer to the system upon entering year t (or leaving

year t-1), while the decision variables refer to decisions made

in year t (presumed to be made at the beginning of year t)

.

Note that does not appear in (A-l) - (A-6). This is because

x^ depends only upon the distribution of the purchases x^ over

the years l,...,t-l. This observation is discussed at greater

length subsequently.

It is clear that the stream of decisions d.-,^ = (b=l , . . „ ,T)

t-1

resultant stream of states l M. (t=U ? ...,T) do not violate

j=i J

and the

(A-l) - (A-6)

.

Hence the least upper bound (LUB) of d

? is

y(d

2t ) = M

t

(t=l , . .

. ,T)

,

and the LUB of x^ is

t-1

p(x

2

) = I M (t=2 T).

j=l >

[Recall that x^ = 0 by definition.] We use (A- 7) and (A-8) to

develop the LUB and the greatest lower bound (GLB) of x^

(t=2 , . .

. ,T+1) . [Recall that x^ = m by definition.]

For a lower bound on x^, we observe first that for

t < t < T+l, X-. . > X-, — — , so that ’It — lx’

t-1 t-1

"It l M. > x

1t + l d

j=l j=l

U • 2j

= x, + x~ > D , lx 2 t — t-1

(A- 7)

(A-8)

A3

+
implying that

T-l

x, . > D , - y M. (t < T < T + 1) . CA-9)

It — T-l 1 — -

1=1 J

For 1 <_ t < t , we have

t-l

x, = x, ,+ y d, .

It It - L li 5 1=t

so that

T-l t-l T-l x

lt

+

l M,- * l di-i + l d?^

3 = 1

3 - It > ~lj ’ ^ ~2j

3 = T 3=1

> "It

t-l

l

j= T

N.

3 + x

2t

t-l

D

T-l

- I ]=T V

implying that

T-l t-l

x-,. > d , - y m. - y n. a < t < t). ca-io)

It — T-l - L -. ~

3=1 3 =T

With our convention concerning sums, (A-9) and CA- 10) Can be combined

as

T-l t-l

x. > max [D , - [ M. - J N.] (t= 2 T+l)

1<t<T+ 1

T 1 j=l 1 j=T 1

where the case t=1 corresponds to the condition xn >_ m

t-l

- I N-.

3=1 3
We also require >_ 0. Hence

t- 1 t-1

x, >_ max {0, max [D

1 - l M. - £ N.]} (t=2 , . . . ,T+1)

.

1<t<T+1 t_1

j=l 3 j= T

3

For an upper bound to x^, we note that for t <_ x <_ T + 1,

n

T

T-1

1 l

j-1

d

lj 1 X

d

13

T-1

+ 7 N. = m

j=t 3

T-1

x, + l N., so that

j=t 3

x

It

< m max [n

t<T<T+l T

T-1

l N.] (t=2 , . . . ,T+1)

,

j=t 3

where the case T=t corresponds to the condition x^ <_ m-n .

We now let

t- 1 t-1

A (x, ) = max {0, max [D - £ M. - £ N. ]

}

(t=2, . ,

. ,T+1)

,

1<t<T+1 T_i j=l 3 j=T 3

T-1

y(x

1 ) = m - max [n - l N.] (t=2, .

.

. ,T+1)

,

t<r<T+l j=t 3

and we show that the formulas (A- 13) and (A- 14) give the GLB and

LUB of x-j- , respectively. This is accomplished by showing that

the A(x^

t

) (t=l, . .. ,T+1) and y(x

lt ) (t=l, . .

. ,T+1) are feasible

streams of the state variables x-^. From (A-13) we know that

(A-ll)

(A-12)

(A- 13)

(A-14)
t-1

i(x

it} i D

t-i V

or

t-1

Hxlt ) + l M

i > D

j = l (A

Since X(x^) £ y (x^) mast hold for the problem to be feasible, it follows

t-1

p(x

lt ) l

M. >Dh. j=l

(A

Next, (A- 14) implies

y(x

lt )i m - n

t

, (A

from which it follows that

A(x

lt ) < m - nt

. (ARelations (A- 14) and (A-18) imply, respectively, that demand

is met in year t-1 with state A(x^^) and that required retirements

are met with state \(x^ ). Relations (A- 16) and (A-17) imply

that these same two conditions are met by the state y (x., )

-15)

that

,i6)

17)

18 )
We now state an obvious fact.

Lemma 1. If {a^} and {b^} are finite sequences and k-, and k

? are

constants such that k-,±

<_ a.

i

b. <_ k~ for all i, then k, < max a. -max b. < k 1 z, 1 — i i—2

In order to show that A(x-^) and y(x-^) are feasible streams,

it remains only to show the following two propositions.

Proposition 1 . 0 < A(x

lt)

- A(x1>t+1 ) < N

t

(t=l , . .

. ,T+1)

.

Proof. For arbitrary t, let a

Q = b

Q = 0, and let

T-l t-1

a

T = d

t -i - I Mj - I N. (t=1,...,T+1),

j=l J j=T J

T-l t V D

T _1 - I M . - l N (t=1, . .

. ,T+1)

.

j=l J j= T

J

It is clear that 0 £ a^ - b^ £ (t= 0, . . . ,T+1) , so that Lemma 1

implies 0 <_ max a - max b . < N. , or 0 < A(x, J - A(x, . ) < N , 0<x<T+l t 0<t<T+1 t “ 1 u 1 l,t+l J - t*

A7

as stated.
Proposition 2 . 0 <_ y(x^) - y (x^

t+ ^) <_ (t=l , . . . ,T+1)

Proof . For arbitrary t, let a = n ^ , b

t+ ^ = max [n^ , n

t+ , - N^] ,

t-1

a = n - y N. (x=t+2 , . . . ,T+1)

T x . f t j j=t+l

T-1

b = n -l -N 0=t+2 T+l)

T T j=t+l

For x=t+2 , . . ? . ,T+1 J, it is clear that 0 —

< a - b < N.. If b.^, = n, , x x — t t+l t

then a^

+ ^

- b

t+ ^ = n^ +1 - n^ >_ 0 by definition, and in this case

n

t i Vi - V 30 that at+i Vi = Vi nt i V If

b

t+l

= n

t+l

- N

t

> then Vl b

t+I = nt +l

' (n

t + l

' NP

= N

t i °‘

Hence 0 £ a - b .1 N (x=t+l , . .

. ,T+1) , so that Lemma 1 implies

0 —

< max a - max b < N. . Therefore . x x — t

J x x

0 <_ (m - max b^ - (m - max aj = y(xlt ) - y(x_

L t+1 ) £ N

t<

APropositions 1 and 2 imply that A(x^ can be "reached" from

A(x^) with a feasible decision, and that y (x^

t+ j) can be "reached"

from y(x^ ) with a feasible decision, respectively. [See (A-3).]

These propositions together with the conclusions drawn from

(A-15) - (A- 18) imply that the ^(x-^) and the y(x^ ) are feasible

streams, and this together with (A- 11) and (A-12) in turn imply that

A

C

X

1

1

) u

C

x

^ t

) are the GLB and the LUB of x^ , respectively.

Fix a value of x^ , say x-^ t

,.with A(x^

t

) <_ x^ <_ y(x^

t

). We

now develop the GLB of x

7t , given x^ . For t < t £ T+l, we have

x. < y (x, ) and x. < x, . , and so x, < min [x, . , y (x, )

1

.

It — v lx' lx — It’ lx — L It’ v 1 t' j

Hence

,

t-1

min [x, . , y(x, )] + x9 L

. + 7 M. > x, +x0 >D

It v 1 t^ j 2t i — lx 2x — x-1’

3 = t

so

T-1

x

2t i

, (D t-1

- l M

j

" min t x

lt> wCxlPrt<x<T+l j=t J

. t-1 ^ t-1

For 1 < x < t, x

]t £ y(x

i T

) and x

1t = x^ + l

d-j. 1 x

lt

+ l

N. j=T J j=T -

~ ^ "A"

Thus x, <_ min[y (x^

( ) , x^ + £ N ] = x*^. [The notation = means

j=x j T

"defined as."] Essentially x*^^ is the largest value of x-^ such

that x^

t can be "reached" from it by feasible decisions.

A9

CA- 19)
Now, for x £ a <_ t

o-l

la + x

2t

+

l M

i ilo + X2a — D

a-1.

j = T a-1

Hence x

2t >

- x*

a

- j

M.. For 1 < a < t ,

X

la

+ X

2 t —

X

la

+ X

2o — Da-1’

implying x

2t 1

D

(J _ 1

- x

*

a

- Again, using our convention regardsums , we have

a-1 x

2

> max [D

x

- x*

o

- J

M.] - x*

x (VT<t) , l<a<t J=t J (A- 20)

and in particular

t-1 x0

. > max [D , - x?

2t - l«<t 0_1 10 l<T<t

]- max {D

t _2 ' m^Wx^) , ^ (A- ')

Let

t-1

1=T

t-1

X(x

2t ; xu) = ^max

^ ^ {D

t

_ 1

- M

j

- min[u(x

lT ) , x

lt +J

N^}.

1 < x < T+l l=t

(A- 22)

For l<r<t (A-22) reduces to (A-21) , and for t<x<T+l (A-22) reduces to

(A-19) , so that X(x

2t ; x^^_) is a lower bound on x^, given xt

- We show

that X(x

2t ; x^ ) is the GLB of x^, given x^

t

, by first showing the

existence of a feasible stream t£ \(x

2t ; x

] t

) and then showing

that this state can be completed into the future with a stream

feasible in years t for t<T<_T+l„ It is easily shown that the

feasibility condition X(x

2

^.; A(x-^)) <_ aCx^) follows from

the feasibility condition A(x^

t

) <_y(x^

t

).

A- 10
First, note that (x*

t

, x 7 p

= (x^, A (x

^ t

; x^ )). We show

that the sequence {(x*^, X

2 T ^ ( T = is the desired stream.

That x* < y(x, 1 follows from the definition of x* . Since

It — It It

y (x, ) > A (Xt ) and

It — It

X - jN > A(x ) + l [X(x J - x(x )] = A(x ),

J ~T J J=T J

we have x*^ _> A(x^ ). (The inequality in the above expression

follows from x-^ _> A(x-^) Proposition 1.) Therefore,

X (XlP £X*

t < u(xlT ).

Next we observe that 0 <_ y(x

lT ) - y(x^t+ ^) by Proposition 2

t-1 . t-1

and that x-j. + l N. - (x, + £ N.) = N . It

j=T J j=x+l -1 T

follows for all combinations of cases for x* and x* , , , that

It 1,t+1

0 —

< x* - x* , < N . We have already seen that x* > D , - x* , It 1,t+1 — t ' 2t — t-1 It

so that x*^ + x*^ _> D

t y

Thus far we have shown that the sequence

{x*^} (T=l,...,t) is feasible. To complete the proof for

x? , it remains to show that 0 < x* , , - x* < M . This result

2t — 2,t+1 2t — t a-1

follows from Lemma 1 with a =D , - x* - j M.

,

o a-1 la . L

1_, ] ]=t+1 j

a-1

b = D , - x* - y M., since a - b = M for T+l<a<t and

a a-1 la . L

] a a t J=T J

aoo- b =0 for 1<— o<t. —

A-ll
To show that (x,., A(x-*; x-,.)) can be completed into the

-L L Z l X L

future to a stream feasible in years t < x <_T+1, we choose

d0 = M and choose d, so that x, = min[x-,., y(x., )]. Note that

the sequence {x^ } (x = t+l,...,T+l) is non- increasing. That

the condition x^ + x ? ^ £ D holds is a direct consequence of

the way Afx • xn ^) was derived. Next, x, < yfx, ) < m-n , so } 2t It lx — lx — x

that the required number of retirements is met. We need

only show that 0 £ x^ - x^ £ N^ (t<x£T) to complete

the proof. The left-hand inequality is clear from Proposition 2.

For the right-hand inequality, if x^= y(x-^), then

UCX1,T*P i X

lt’

S° ^X

lT

• X

1,T + 1 i', fXlT ) ' ^l.T+P

by Proposition 2. If x^ = x^ = x-^, then the result is clear.

If X

lT

= X

lt

^X

1,T + 1 = P(X1,T+P> tten X

lT

- Xl,m = X

lt

‘ t‘fX

l,T +l

) i

y(x-^) - y (x^ £ Nj., again by Proposition 2.

We now assume given a state x^, A(x^

t

) £ x^ <_ y(x^

t

), and a state

x

2t’ ^^x

2t’

X

lt^ — x

2t — y ^x2t^’ we derive bounds on

x^

t (2£t<T) . [Recall that = 0 by definition.] For the given

states x

lt , x2t

these bounds ACx^; x^

t

, x

2t ) and y (x^ ; x^

t

, x

2t )

correspond to a "purchase late" scenario and a "purchase early"

scenario, respectively, i.e. the smallest value of x^ is realized

when the x

2t engines are purchased as close to t as possible,

A-12
while the largest value of x^ is realized when the x

2 engines

are purchased as distant from t as possible. These intuitive

concepts are formulated mathematically in the following

paragraphs

.

For the "purchase late" scenario, we observe that

t-1 x0i. - y M. is the smallest value of x0 which can "reach"

2t . Li 2x

J=t J

t-1 x

?t . Hence x9 ^_ >_ x,^ - [ M.. We also have x? ^ L X

*

T

’ as

T ei.

j =T 1

derived above. Combining these we have

t-1 x

2t >_max[x*T

, x

1

- l M.] = x

2t

(2<r£t)

.

j=x J

To show that the x^ correspond to the GLB of x^, given x^

t

and

x

/t , it suffices to show that the sequence { (x*

t

, x^) } (x=l,...,t)

is feasible. We have already shown that x*^ is in the appropriate

range and that 0 <_ x*

t

- x* ^ . That demand is met follows

from x* + x0 > x* + x* > D ... Finally, 0 < x 0

- x0

< M

t-1 . t-1

follows from 0 <_ x*

t+1

- x*

T

<_ and x

2t - l M. - (x2t

~ I ) = M

T

»

for all combinations of cases for x0 and x0 , , . The number of

2t 2,t+1

purchases made in year t in the "purchase late" scenario is

x0 , - x~ , so that

2,t+1 2t

A-13
f:\-2 3) ^ '7-4- ? X1 +- » X' t-1

"3t ’ Alt’

A

2lP

= ^ Vt ^X

2 ,t+1 t=1

- x

2t ) (t-2 , . .

. ,T)

The "purchase early" scenario is somewhat simpler. We have

t-1 x

2t 1 I M., so there exits a largest x(2<r<t), say i=

j=l 3

a-1 T-1

for which xn . > j M.. Let x0 = T M. for 1<t<o and xn = 2t — J 2 t i — 2 t

j = l j=l 1

L 2t

for o <r <t . The sequence {x^} (t=1 , . .

. , t-1) is clearly feasible

Hence

t-1

y(x

3t ; Xi t

, x

2t) = I Vt (*2,t+ 1

’ *2t } Ct=2 ,x). (A- 24)

Note that x-^ r does not appear explicitly in this derivation.

It was stated in Section 3 that the linear form of the maintenance

cost function yields a desirable property of the range of x^ , viz.,

II that its values are precisely multiples of the slope of the linear

function. With u^ = Uq + U-^a, y^

= x

? t+^

- x^^ is the number of purchases

in year x corresponding to the "purchase late" scenario.

Let be any feasible number of purchases in year x, given x^

and x

2

. Then

. . t-1 t-1 x

3t - *(x^.; xu>

=

I ui-. z

T 3t ’ It’ 2t' L , “t-x“x - lL -, u

“t-x +.,y7 x X=1 X=1

A-14
t-1 t-1

= l [ un + ui Ot )] ( Z

T

- yT

) = u l l

t ( z

t

- yT )]>

o 1 , , T=1 1 T=1

where the last equality follows from the fact that

t-1 t-1

l r = l

z =

T “ T 2t

T=1 T-1

t-1

Note that the number of values for xx is £

t (z -y)+l, C -i T T T = 1

We turn now to establishing bounds on the decision variables.

Assume fixed values of x and x^ in their appropriate ranges, say

A A A A(x

lt) £ x^t £ y(x^t

) and A(x

2t

;x^

t

) — x

?t — y ^x2t'*’ t*ie state variable

x does not play a role. We know that d^

t £ 0 from (A-3), and that

x

itAt - u(xi,t+£ 1,1115

A(d

i t

; x

i t

) = max [°» x

lt a(^xi 5 t+i^ (t=i , . .

. ,t) .

(Note that A.(d^ ;x^ ) is not a function of x

2

.)

Relations (A-3) also state that d^ £ N and we have

x-« , — d*. . > A (X-, , -* ) . In addition to these constraints, d,. must be

It It — l,t+l It

chosen so that the resulting x^

t+2 yields- a lower hound on oc ? that

can be "reached" from x

2t , i.e. x

2t + Mt £

A(x

2 t+1 » xlt ” •

U ,ng tne definition of A(x

2 (:+ 2

’ x

it

" ’ we ^ave

(A- 25)

A-15
T-l * t x? + M > max {D - M - min [y(x ), x - d + l N.]}

2t 1 l<x<t+l j=t+l J lT Lt lt: j=x •

-1 = max { max t D

T -i "I M. - 1<t<T+1 j-t+1

T-l

max

, [D

t- 1 '.J , M

i x

lt

+ d

lt 'l N

j ]>

1<t<T+1 j=t+l

The part of (.A- 2 6) involving becomes

^ t-l t

d

1 < x. + x + M - max [D - l M . - l N.]

It It tx t

1 <t<T+1 j=t+l J j=x J

Therefore, we take

u(dit

;x it> x

2t ) = min {N

t’ x

it

‘ X (xi,t+d’

T-l ^

rn V m - J N-] }

+ x 0j_ + XL - max [D i 1

j 3 1 1 lt 2t t -=t+l 1<t<T+1 3 3='

(A-26)

(A-27)

That A(d^ ;x^

t

, X

2 t

) £ y(d

lt

;xlt , X

2 t

) holds may be shown straightforwardly

by taking x

?t = \(x?t

;x^

t

) in the y term and applying the definitions

in (A- 2 5 ) and (A- 2 7 )

Since we already have y(d9 ) = M from (A-4), it remains only to find

X(d

?t

;x^

t

, X

2 t

, d^) , where the three given variables fall in their

respective ranges. Relations (A- 4) state that d

?t £

0. In addition,

we require X

2 t

+ d

?t £

X(x-, x^ - d^) , so that

Ud

2 t

;xlt,x

2 t

,dlt)

= max [0, X (x

2jt+ i’

x

lt “ ^lt ) " x2t J (t=l,...T). (A-28)

A- 16
That A (^2t’

X

lt’

X

2t

,c^lt^ — y ^2t^

= ^olds a^ s0 ^ s straightforward to

verify.

Observe that the ranges of d, f and developed above, do not

depend on x^. In fact, xve show below that the optimal decisions at any stage

are independent of x^, because given x^ and , the value of the objective

f

t

(x ) at each stage is a linear function of x

3t , with the specific form

T-t - W= g

t (xlt>

X

2t5 + 1= o

where 6 = l/(l+r). For t=T, equations (3.3) and (3.4) imply

f

T

(xT

) = min Lj,(Xp, cfp)

A

grp (X^rji , X^rp) *" X^rp,

with gy

taken as that part of (3.3) not involving x^. Now assuming

T-t . that £

t^

X

t^ = h t

(xlt , x

2t ) +

( I

$

J

) x

5t , we show that

j=0

f

t-l (' x

t-l') h t-l^Xl,t-l’ x2

induction" on t) . We have

t-1

T-t+1 .

) + ( l 6

J

) x

j=0 t-1’

(i.e., "backwards

f

t-i Cxt-f

= y

n [I t-i fxt-i* dt-P

+ {f

t (x

t

)]

h-i

T-t . min [ip-i + 6ht + 6 ( I

6J

) Cx

3 >t _i

+ u

i

d

2,t-l

+ U

lx2,t-1^

d

t-l

J

A- 17
T-t+1 A . T-t+1.

- nun Ig,. + <$h +( l &h ( u

1

tl 2 t-1

+ U

l X 2,t-l ) + ^ x

3 , t - 1 + X

3»td , j=l ’ 3-‘

t-1

where g , is that part of I. , not involving x, . (cf. equation C ))

t - 1 t J- O 5 3, t-1 L jT-t+1

f

t-l

(xt-l } = d

min Ih

i-1

(X

l.t-l> x

2,t-l )+ ( i

Q

4 5 X

3,t-1

t-1

h

t-l

(x l,t-l’ X

2,t-1 } + (J

Q

^ x

3 , t-1

T-t+1-

where hf , = g t

_

] + +

C 1 (

ll i

d

2,t-l

+ U

l X

2,t-l

L i L

1 - 1

).

The fact just proven makes it unnecessary to cycle through all of the values of

d

j and d 0 for each x,^. We need only determine the optimal decisions

for one value of x~ , say A(x~ ; x, , x ? )

these decisions are optimal

Ol J)L JL L ZL

for other values of x,^ , given x^

t and x^, and the corresponding values

of i' t (x ) may be calculated simply by adding the appropriate multiple of

T-t

( l 5-1 to the optimal value of the objective function for A(Xj ; x-^; x 7 t

) i=0

Table A-l gives a summary of all formulas needed to calculate the

ranges of the variables used in the dynamic programming model.

A- 18
Table A-l - FORMULAS FOR RANGES OF THE DYNAMIC PROGRAMMING MODEL VARIABLES

x-1 t-1

A(x, ) = max (0, max [D - l M. - l N . ]

}

lz

1 <j<J+1

T_1 j=l > j=r J

T-1

y(x

lt) = m - max [n - l N.]

t<r<T+l j=t J

A(x

? ; x, ) = max ID , 1Z 1<t<T+1

T-1

l M.

l=t

t-1

- min [y(x

lT ), *

lt

+

l Nj]>

t-1

y(x

2

) = l M

j=l J

t-1

x(x

3t ; xlt , x

2t) = I u

t

_ T (x

2 +1 - x

2t ) T = 1

7t

r* = C2t

t-1

max [x*

x

, x

lt - J

Mj ] J =T

a-l

max [D - x? - j M.]

, . L a-l la . L l<a<t j = t

J

t-1 x

l0

= 11111 t*1 ^IcL x

lt

+ 1

N

j

]

- - t_ -* ^ ^ y(x

3t ; x

lt , x

2

) = l u

t

_ T

(x

2 T +i

' x

2t^

T =1

%

T-1 x0 = V M. for l<T<a

2t i —

J=1

J

x? t = x

2t ^°r a—T —t * k-1

a is the largest value of k such that x

2t

> l M^

A-19
Table A-l continued

*(d

lt ; xid = max [0, x

it

'

p(d

lt ; x

lt , x

2t) = min {N

t

, x

lt

-• *(x1;t+1 )>

T-l T

rn - 7 M. - I N. ]

max [D x-l - 3 3 -t 3 1<t<T+1 3"

+1 3 T

A ( d

2t’ xlt- x2t ’ dld = max [0 ' A(x

2,t+ l

; x

lt
APPENDIX B

LISTING OF THE COMPUTER CODE FOR THE DYNAMIC

PROGRAMMING MODEL

I-2

UJ

a.e

UJ2

<ra

o

un

UJ2

IDX

inuiQ

UJCio

cj

tD

<£

rr

t£> o

or

n_o

X

?

c

X

o

UJ

_Jm

o

or

0.

sr x

2

in id x 2

UJ O CJ

<r <r _J _i n cl 'd id

or rr

tv _i

8 UJ o o

X

t c

COX

. J

Idn

Ul

O'«

LdX

U

c

LlO

2 •or

Ll tO Ll' CO UJ CO X 0 X <1

L/C 2

X Ll 5 O

X

X

2

x

UI Ui

UJ to < <a J— X

U1 U

UJ

>- >- -J X X CO

<r <£ x

x

X X Ui

Ld u

X X Ul <c • X X X X b X _J _) X X

Ul Li 1 s X

Ul Ul > X O O

O • St » X b— x Ll X 2' s x

UJ O Ul a — ui * * ui a

_J x a CY b- O 2 b"

SI Id II X 0 fit l/l > in co CV X 2 ~ 0

a 2 Ld 0 b- x a

x or x

<£ Ui si ? tr ?

s

UJ x UJ XXX

(Y “

UJ c

to X

Id _1 X UJ X o

X e. Ld

J— X

s-f «r 0 x

»-» _! _J

01 <r X Id x rr

• X

UJ 2

e X

l-l X

<c

J- LdX

Ll X

O

or Id O

X X

<r o

j» tsj x

x nr x o

5" x

t—

•

X to

<1 X

X x

X

Ld X

X <t X —

J

a

in

1—1 LdX

Lfl X

rrx x

UJ

x cv X X

or a

o o

Ll Ll UI UI Id UJ X X

o I I a <r <l

<t x

U' X

V

UI

• J X

Ld if

tD <r «I

i— X '-1

1/1 x x

5 • S’ i- Ul UI o

Ll Ld O _1 UI U X

Id J X _J <1 _J c 0> < X

:> x 2

x x

2 2 2

") x x

x X

1-1 Ll) <T X x ^

<C X

X Id X X

Ld x X

X

(—1/11/1

Ld 1—1

1/1 O

x a id X to

1/1 o c

CJ 1/1 X

CL Id <

x rtr x

Ll U_ O O

or or Id Id

CO CO 2 2

X X

X X

X X

X X

X V

#—I 1—1 X X

<r

Ld UJ r x

l/l l/l

i/> in o o

CL CL X 2

orUJ

uj a o 0

Ld si l/l X X Ul c l/lt1—s <£ u a i- O O Lfl Ul u

1/1 Ll < 1—0

i— x or CV uj

x Ll rr. O 2

u X

O 1/1 x

UJ

Ul X X

Id JX

x <r x

_j :> *~i <C X

> _J <

-J x

Ll C

O ld

or x

or 1 dtUJ O

cn o t/i x *-> x a

X Id ld

•5 X

UJ x *r X X x

x in ui

or i— <

x Ld X X

Ll X

C x

in x

Ld X

X X

< Ll > O

in

UJ

or -J uj <r CO 0» X

X Ll X O

O

in

ui 0

o

czo

X

II Ul

in

in

t\J

1

8

Ul

to

siX

<1

rrId

cr • x o

X X

X Ld

Id * X CV X

or ll <r O Id

o

o

T—

l

11 Lfl o

aX

Qk in

cv

11

i/1 orx

+

ui

crx

X

II

l/l orx

cv*

*

Uio

CLX

tl 1/1 o

a.>

— X

x r

X X

CV X

X -

_J —

- ui

-s cr X X

Ul X

cr «- X D

X

X Ul X 0

x a

- x

X t/i

1/1 X

a *- X

X Ld

fOX

X X

_J Ul

ll- *

X X

O X X

X U> X

crUJ

1—

LdX

stor

<x cl

U) CL

or x

Ui ui x u. o or x «- a x — —

x x a x

11 11 - ui

Ul x

O X

a o

X X

C\l X

X

X

2

s tH ^ X

Ul o

cr x

X x

X *

fib. b=b Ul Ld

t£> X

<r <i x x

<r tn 2 —» X X

w x x a

> u x x

®. «b o tv x — x x

Uj x s O l/l X X

x or > a

x X - X

.b 7 —

x —' CV X

a x uj - x *• x x

cr x «r cv - UJ x D

to to ui -

<£ <1 x X

_J X X X

Ir <r OO ^ <b s

u

crx

x

a a

Ld Ld

Id UJ X X

< <£ a a

<r <r q a

x

o

X

X

o

o

in o tn m

o «- o x

a x o . « x in x x — a — <v cm x cv x

x x x s

r» — ro x

x x x x

-> X X X

X

o5-X

o

o

X

0X O'

ro

II

II

u

o

a

Ida

XX

X

UlX

X

o

IVI x

a

o

x

toX

x

X

X

<r_Ja

UJx

ina

«

a

LdX

U_o

a

Ld

COX

ro

UJX

in

or

ui

tocU

c

Ul

Ldo

a

6

ui n u: x or. < —

x

u

X Ld o o

or V X) _J o

_i in

<1 Ld x a

x

x U_ X o

a

<

ui Ld >- Ul to Id <E X O

a Ld x _j n

O CO Ld

in si a

Id ^ x

a o x

_l Ul

iLo

a

ui

CO

X

o

a

Id x XXX

5" H 1/1 XXX

X < x

>

UJ x

X Ld -J -v X X _J n x si Ld in X

to x m x

<C xx

a

* » * *

x

o

O Ul 2 <r

Ll O

Ld Ld X

to <1 X -J

<r x

X o

Ld —

J

x <

X to x

si U

cr *z c

Ld Ld X to x <r

Ll O

X

X LuO

Ll a

O XO

J1 U) X Id x a

uix <t O

x X

« Ll O

2 Ll

12 Ul Ul

<b ox

x u in x o

id o

a

O in Si Ld O X u

CO IOH X

fib -fi x cr in 2

—

X- X I d

si X X

a 2 <1 x

<r a x

Id OO si a Ll X >

X

o

o

a

PQ

ouuu 000 CJ 00 00 1 J CJ 0000 tj u u u u u u u tJ 0

* •* * * Hf\in t

*

o * •* * n d- * *

0 *

O X

* * * * *

m n

X- *

n o * *

O X

* * *

•o jf n

\l CM CM CM CM CM CM CV OJ CM tO fO O 'O -O X

* * * * x fs. O X

rO rO O O

* * * *

O X \J o

d- d- d- dlOOXOOOOO —' ’—' < j j, a _4 r—41 H —4 H r 0^X3^00000000000000000000000

0000000000 0000000000 000 000
7 0: P 0 a Ldn

Ll L -

' LTi

iii <r in C> Li' »-< n

i cru 7

a L. o

r f—

i id -

l/UJ <

«r *—> »— T rr u

U K k)

cr Li 1 CY ~ ^ o a c; L

id n

Lu CL T li o

I— <3 C. 1 /

o

in rr

rrc a m t

t- CJ m 7 o I i/i n ir id c

cj -s? i— id n n

L in o <

id n O 7”

7* < o

7* rr d <1

CJh CJ Id

Ll _l • rr u_ < n -i id cj rr o < m

CJ l/} Id Id

lL

111

<1 I— *

in

CJ

n H l- Id

cl <r > id

hh r m -5 CJ =c 7” d id T

< ~ U U

fL —i rr O !iJ Y -3

g. n q a

c

_j

_j

cn

Li I m

~D

C: 5

<r rr Id O

rr Ll

Ui

UJ

— in o

-H o

CO H

IPn 5

<i rr

Id PD

ft lL

in

Ld

in

Ld

I ld Id h- m K J

<r <r id

rr, rr n

Ld

CD

<1 Id in cd

IdX Ll

II —

< CL+

<\J c

PL O II o cj

o

_J IL

i- <r

f\i ~

~> IL O O *-*

CO

0^ I <* I UJ vO * X —

7 I *-« id

b- b7*

PD 'Y

CJ 7c

ld

_J

Ll

in

Id

CD

* 7”

PD II U ~1

om

LJ

- <3 -H -h h-

•h UJ II LJ Id »-

II • —I II D

—I —* ^ 7? II

>-» VP Ho H H UW ^ J + “) h I 1 O ~) ^ T' 7* a. D II ll D II n "> PD I—

f.D / h n D H L) U K

=t- n ju du u uo CJ CJ CJ CJ O C) CJ CJ

j-o op* o'T' j-» \joj-n on o O' o -h 'M -o x P) ofs--o ,Tio«-i'\ioxr) oi^nT' d h \j o j* r> j- -t -r ± yt s- pjDinm n in n nn in o n n o n n v 0 vO o on 3-c

**********•*•*****

0 p* n :T* 3 -H \J D X D 0 ^ f) T' r> -H O D CO O T' fT> J' 7' T' Ti ,T> .T (T> fT> 3 3

OOOOOOOHOOOOHNNNNOOOOv0 ^iO^^(Mf0 ^ii'J'linOH^inN(MlOJ’l^^d-^OHrO>ONOr\|d-i^^ AjM(\j(\)^\iMroojfonnronnnnnYj--r.-t-j-j--tJ-nvOnvfljoo,OvOvONNNN^ 3 HHHHHHHr\j^(\j'\j(\iroronnnn HHHHHHHHHHHHHHHHHHHH-HHHHHH'HHHHHHHHHHHHHiMfMAJMAJAl \J \J OJ AJ vi C\J AJ \J -M AJ \J \J \J 00300300000300000 0 0 3 0 0 3 OOOOOOOOZJOOOOOOOOO 3 030 0 000000000003 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
OU_ I n

o UJ 3 ->

II X

o

V- ~

I I— 7 o r5

l

1) 7 CJ

O <

Ll »-<

fr- CO »-< I— 7

s-h —

UJ

_l X

-

x

Id 5- Q O

a a D Lx O ID 7 7 < t-t 7

a >~i L <

^ 5T O U.

Lxi in T UJ

I- o

cr - !D ^ o

i- in — ui -< a

x

^ u.o o

^ a

<r uj

rr « t

»- T> — x •

*—< «—

<

x UJ i _l T I- -

id cr I— J) <x x> • I d a x ^ i- o -« 7

cr w

*-* 3 m 5

m a

•-« uj

111 UJ

_i cr x o . o

a in

in

ro m

in

O «H

<D X Id

5" X

II ( D

*H 3 •

ii <i m hh -) 5T ^

<* 3 O I— II O

r- vO — i5“ O 3 a 3 o n n h iy) co

UJ

^ s

- ^

•—<3 3 ? d ^ 3 <— ^

<X - 8 xD — •—< ^ • w || 3 ui 3 3 1/13 3

7 <

II O II Hh

X I- —

5- ^ 7 3 0 3 3 IX

d") ;3 i/l O *-t

^ X

3 7

«=r i •H — ^

I II 3

h 3 l/l

II O II in

«—< ^

*5-3 3

»- (~\ m

— n 7 >-

i i5- — i 3 3

» II «I 4 O H 3 V— —

Id UI II |<J + < w 3^3 • h- l- T 3 * —

*-l ./) t-H

S' 3 3 —

<r 7

h- 7

- I

II

UI l Id

n x z ^

<x

ii uiL

I- _J

<3 _J UJ C

>- *-« —

a »— o 3

U l-H

in 3

<r cr Uiu * 7 -

*-• 3

in -

> Ii

O —

a x

i a ^

3

id 7

T

I- (37

7 7 O lx 3 U HU

o m o

in in o

— w vT

II *—

T

5^ 3

3 <r

l A <— 3 3 O ID

J _J ~ - X

• • O X w

X V <

^ -(T'NO 3 - •. \ m

ui in id w vo w y id 3 1 3 •—» »-' <r 3 3" 7 X 1-3 X

y h j id <r n >— 2” 7 a - o 7 3 li_ O ll_ V O 3 i— o U h u m ? li h 1/lu

Id ~

• m

x ^ 3

— vO X3 Id w KH

lx X

o •• rr ro

i a *—

Id - —

- 3

• ii-in

i— uj cv r a > x u i <r 3

in uj in 7 c >- in OX c o 2

Jl IY h U

>- 3 --

*-* Q h- X

5 <V —« in x m

d UI

V II X - II

l— X 5

- < w. 5- ^ < a a n in o

3 3 —« —

in

o u 3

in a o

uj 3 <r - o i- >

< in h

3 Id 5 li 3 a •-« o O 3

3 a a

cr o a ui

<j ui 3

a n 5- ^ ui Q 3

•-•<13 7

3 ^

Od 3 Id UI X 7 X X

3

O *—• — K- a w w

m - c\j —

3 DJ X X

OJ x a

O -O o inx

a

* * uuu u u CJ u o uu

mdx ot*d-h \j -o x n a ^ nr* d -m vioxno^OTv^-i \joxn or- OT'3-<\j-oj-n.O'^ na d—<\jnrnor>- o i\ o 3o 300 \i in n <o d d n io D d d j xxxxxx xxxnnLnm3innn3 n xmo <mx m nr-r-r-r- O 3 x X X X X X X X X

AJ "\J °U MAJAJMoj-vjcnj \] 0 3 0 03000000 30 3 30030000

r— r- ^-< x r- H(\jn^ mon

x x n in >n D «iw) 4) in s n

AJ nJAJAJAJAJ(\JAJ^\IMAJ >J 000033300 300 30300 303 3 030

rO'On—<OJXvOO—<3 X r-r-r-oooo-H^i-H—i

rsjrMAj -03333333 3000000 33 33

3 000000 0300

KOHtmsHni/KM(\jfO

•X<\J<M<\JC\Jf\J 333 XXX 333333333333

O 3 3003000003 030033003303

XiOoi/uniniD^jjiOiOvO x x JD in n n in n> n n in n 333333333333 0333033 -D 3 3 3 ^ 3003003 3 33 33
^ X

x o

o x

o <

c bi X k- k ti

o x

CL <r ^ o

X or <r u) x *-

c

I bJ i k- X

b b X X

Id b

:> O

C

r b

v— _j

C\ ci X >

Ll

LT,

<V M < 5: n <r J h h

J —I J

X I d

o

bJn

CLo

tlJ X

X X

k- O 3 _l X X

X II II II II o

' J -HM -4 -H

X J X I

I- X . CD OJ

• X ' — II

II Ll OJ

or x

e <3 ^ o

LH b) b T

i n x . m r

in in O lil

o. X X H-l

C' o

r° X

»-» bJ CD * J r

<

II > _J_J

k- b «aX

I hi < m

C 5

- bJ <

I X X O CD X o

*-< x

CL O

X X I *• X I

i/) CC \

r> =t \

CL X

X c \

kO —

II — I

' J <r m, k- *, o —< x

X X o

I X - ll

OJ

I- (X OJ CD

X C

J ^ ^ II\j on _j x

x x

C d

X o

in bJ

bJ X

^ v- X

in x ~ mo* -j • in m

k- a b

; a X

x ^

b-

«> Ll X

- O O

ro x

*-i bJ CD • _j in

m

O i X

CDo

~ 5 X

i- ino

X X

- ^

Hld<J ^

XI

HH o 3

o

• T ,,JX X r-l _J X

ll O J •

• rO II

II XX

in fT' \ > liJ

vf)-« --t 7

. Xo n 1

1

- x x o

- lL

1

1

1

1

1

1

w CD j w to d J o

\l O O li_ _| < ll. X

WH _J ^ *-H u O *”• *>

d x i- X k- I— Cr O O o in m

m or x x X CD co x n

X O bj o in 7 LJ <

bJ X

_J o

Id _l X

CD d X

X ^ Cl d in

_j in Q bJ bl?u

rr c xx

k-—0 — m «—i m l— X 4- b i —

•s- 1- x :>

O X + X k-

• ObJO ^

i— i— rr. i— —

7T X

Cl JXJ _l d x d i X X

O X

bJ

in

k- X

i-H O

Id X

X bl

OJ X X O X

k- X

in *-i

_j <tr

bi k- x

—

*

* m

5- in X Ld

Ld _J

bid n

71 »-<

X o

o

X

k- <r —i x ^ k-

_i in

J) X Ld

CJ U (J U J

X 0 vO o-k.non o x n ^ 1 o o ******** t> d h \j o * x n - ^

* * * * * * ***** * * ******** OX 3 »H\J Oi-OO^ OTNDH\JO-k Ow ~ , ~ . - - - 03)0 0 (n‘0 «lMin' 1WMiH'MMJ' 330300030 DH D ON XJO^fX I D» n ^ D H 0 -f X o

O' ON o 3 3 3 O 3 (3 » v_j •—» «—« *—« —• —• *—

’—• •—• HH(\I.Mf\J(\J'\J'\JMMM\IMv\IOJAJMM(M(\|

o OsOvONOHHHHf\jinf,**OHMrn.'tj-^^inoH'n*inNo^

o n ji n n,o o.oo 0sD0v0r,^r^is^ N^r^-r<cr^r^f^oo3oxo—«—«—<~h-h v ^ O-OOOOX-OOXXX 0 o-o-o OOXXOXO^- rf Xrfrk =k 7) 3 3 3 3 3 3 3 3 30333300 3303330 0 03330303303 3 3 33 3 33333333333 3 33333330 3 33 3 333333033

v j *"“t n _j liii-wj -j JlCiOkkkkDDD

•—4 h i\j m ro oj n n n n »o o -r j- -r ^ .t 3 3 303030033333030330 33 3 0 30 30 33303 3 03 0 00 0 0
CD — ~

— OJ —

CM * n *•

5 .-I 4 4

O

X 'D rn X 3:

cc iO'1 CM II

' 0

it

r— rj> ii h ^ ii o h ii ii

i— *— o lj_

d d- - ON W OJ HD<fI

h Ki r O ^ r-

_l- * o

rO *• CD

•5T O

^ tH «—

»

K! H H

_j - n

* 5^ — II

v£) rO ® 0 _J UJ

i— O

d _i OIL

/• ; u *-t

_J Cl cn —

*H d

l/l Cl d ro Ld ^

cn •> »h PO

lii •

_J

Cl Tl II > o

- O' K

i «H Cl CM —

Q X rO

I Lt I *-• ®in ®

k- i- ^ •> CM d

X I II

Ljj cl y— c

< c

k

LTi O'UJ C I-

<r lvj T C

h- d

cr

L_ <

rr cl O

? idX

L I- Od 7*o •

Ll! • rr uj cn

Li h- Lj X d ?

- u o n o d'

_i

II d J

l- ft » ^

H O lO •- x ir h h

- cr n

i- lj - —

ii ^

vO X

? \ h7 T» x .h d

- X X X

n — i—

ro 4

111 0 d rr i i- O m cr

UJx n

cn !T d d

lit rr X CD O O

cr

' UJ id

Id d *-« X

r- ^ ' CL m rr cr o

X 3 - U h-

: u - y- cn * *

rO 3 J

_J O

II o

I— I rOx if

•

« o y- < rf ‘i O

O tJ U_

•lO'X

i— cr \

,o o x

* \

II v0 w

X ^

c i— r- 4 OJ CM — X —

*

*—I t + ~ o

—« CD H _J X

f > I 1—. -—

«

\ ^ ^ K w f\i — C » H ri n

rO -O -H O X >

_J • rO n I CO

_J o

- rr c LI - x

r- ro Q -

- n

3

- Id

rrD

I _J I y— D -* ii o • .o .

1 1 j

l d Id d - -

y— y- ~ - x o_

rr - o

7) II 0 »—

LL ( i i/l * 4

u ii n ii w

X X (M HI- OH d "0 y i/i -<i ft j j

ii ~

4 X

CD X

- X

v0 —

in

id

m cvi HlLhOXftlltO'

Cl «H I O _J v- 3 d

-v CM — r > x -

rr —i in

•> y— oj

ll d l— *. r* o ro in J v *—

rr Ll - h

l—4 1—d

rr c\i - j i— x m

—1 J •• *-H d iti y— c\ u r h - 4 > in

f-ft o. ‘ ^ 7 in

• »— X -H

I— d CM O _J O ^0 ^

•—I'-

ll IL -

*— Id d

a -r — -i. -i— r ->

ii •> * c r.

^ x

UJ H-* d

tn —) ^ X

>-h 77

i ro *h 1

1

n — y-

»-H «H

ii. o n n

x o

CM O

*-*****--»*'K'*'»4 ****#-»****************#******#****»*4-»**4-* 4 DT>-OHM Otnr).,>^nJ' 3 Hj 14 0 0 ‘^n 7'rOH\J 0 4 nO^-XDXO^«\10 dnDr- JT'O-IMD^-O 0 ^ n

T' 0 HM )r n H T "M OAJ'M'MPU UOO MAlO'OOrOOrO OOOOd 4-4 4 4 T 7 t ^ 7 Jl/l O n D O Oft D D Jft 0 0 0 0 0 0 0 0 n.OSN’v.^NiN.

XI CM CM CM M Al OJ CM OJ CM CM CM CM r\| OJ OJ M C\J M M CM CM CM C\J CM CM CVI CM /M CM CM CM CM CM c\J CM M OJ CM (M CM M M OJ M >M OJ CM 'M M OJ M oj AJ OJ M M

O^H r.nNf\JfOinNOH(\|rOd-^40l4vOOHf\lrO(M’ft l/14 44inJlHC\l4lOHHHft)rft tvflNCMiD4^vOvDvONOr)4nsoiO oo non oo o^onsn^nn ftODOHH4HiM(\i(\PO'Oroioio.tt^4 i n iJinin/ijvnin o no o n n ^ s i d

o r)r>nnnnnr>f)Lnn.nf)nnr)r>Jis)ji nnoto n nnnxi n n ji n n n oo o o o o o 000030300000000300030030000030000000 r Z3000000000000300003 0 00 ~D 7>CDOO ZIZrODOCDODOOOrD TD CD D 3 0 O DOO OOO OOOOOCDOOOOOOO 30 3000 300 0 0 30 3 3
Ld

<£

II II II UJ

“D

k— h— 7

in in >.n

til LiJ Lj i irr m m 7

k- M O

u r . r. ( J

I-- < o

lx, *-

d- > in

UJ ll u

<n o UJ

c' O

d- Id

in i- _J

<r c

? i- ^ o in 1—

<

Or I—

Ll T Q

Ii- O •

I— I din i— u

O ? T UJ o d v- o

o <

5^ CJ Id K ^na: 1/1 7 t —

—* I— <\1 5- 13

T i- h h n i/i nry n t

t-« < i— Id < ! — >- I— t— — >

7 7 —

4

O

“) KH | O

O AJ O id U <-H H 1- H ^ <r >— id

m

ui i

i- o ~

7” O —

4

o 4-4 I O C\J Olio

—* H-4 ~ OJ w

I- o ^

U 4-< n

7” m

o *-< O CM o •. »-* m

n ro -

• on in

4- (7' *—

4

— •* TO

z>

in —

«* <\j

— — ii 2?o

oO W •. 4-* *-< CSJ —

*. X X H

o n n —

7 7 7 7

vD • Ld

7?

C\J —

«

O MC ~ O - w |- 7

I- Id < h-* II c h t h Oh (t 7 5- J re O O ““> Ll « Ll O in

in i on n D O n in

i o — LO O wO o

CT> •-* C^ - m -

LiJ vO *X)

m m in

1-4 0 0

O CT> d'

d- ^ « vD ^

IT7 »

rH O »-H o <— O H-1 •—

)

I- - X o r> O ^ 7

• T> ~> a o o

UJ *—1 4—1 7

i *-4 Id <r Id

V- L- d- 7 H [T H nnco fr O -s. li_ ^

C U Id I- Id UJ

5- d- I— ^ d- d- (Thh HH 1-4 o nr rr il rt. t

' 3

in ~

* CM

l— in

ii i Id ~D

in j < <r d~ >

in

ii 2” O

D

7 7

T> ~> O O

cf cn • UI I- td Icr ^ cr cm

5- X X

“> 3

7 L 7 li O O

Id li

«

r id t uj

I— ~

3

~

)

_l J

in <r in <-t

;w w • w ^ ^ ^ ~) I— X

Id UJ

»- dnr.

i ^

o cm 7 O - f-n n-

— d- o

2) - -4 o r-» M II id

Id UJ 4-4 O Id

”5 !D UJ <S H> 7 Z J 31 7

’ *-4 *-» —i o m i-H

I I- Ll_ C\i X d- .770 07 • o o 7 o sr “>

. o o id n m o

o o o o o o o o o o o o

* * * -# * + +* + + -*•***• •** 

o 7 j>-4 \j n ^ n o n o in d m ?o ^ n o^>oiT' 0 '-»M-o^nor^0 7'o-«MOj-no^oT‘D-HAi-n^-Lno r^ o r» 3-4 mo

r— r— r— o b o® n o n ® b ® ^ fT' .TUT' 'T'^^rr'iiGoo oo ooooo^ht-i— 4 —4— i^cm mcxjm.m m maim Ai’O-n^n-o AcuAAKMAl'MA'NJnjaicxjiMnj'AjiMnjnjtMfMnjojcuArOfnmrorO’nronnrnrnm-onrnrnnmnnnnroponnniOnn-O'nfnn

vno^4 CMmrOmmX)rnrnMjr^o^JfM(MzJ-inncMmrtr^O^-440 o-HO^-«r^Lnr-rfrO-«^-4 —!-4 -H-4 r-CMrOno-H^Lnn)^-»rMCM(Al(Mrt rDnninnrnnionnron-o^ ^ 4 t 4- ® m >o >o >0 o s n n o o h h h nj (M n .-t in '.n n in m imn m ® o vO s s n n n 3 -doooo

O o 0.0 o O 00 o on on 0 0 0 0 DO o o OOOvO ibnnnn^nnsnn^ssnnnnn r— r— r-. r— o 30 3 00 OOOO OOOOOOO 00000000000000000000000000000000000000000-i-4-4-4^-4-H 0000000000000 000000000000000000000 0000 00000000000000000 000
K' C h IjJ fr » <1

II LD II C\J n

* *. * H

'\J II • >'

0 4-

• CO LJ >-• “0 X) rr —• t— II

CO

I — 5

> a c

i "0

<r cc i- —

I

CT* 4-

i » *— o —I II

~> —

«

o < cl

I U fi. J *-

* II

<x nI— 5" O

• X X

IjlJ »—* <r

cn ^

*-« X m m ii ii

a - < ro

Ll* —

crO II Ll

LiJ «~

_J Cl cnH d

L/l O

< CD

LJ >

II n

_i

CO - *-s

LTi •* h K) 5 -

Ui -

- K*

II

i ro r

i :> >— * o

- CO

i u_ o o u. o n n

X 3

oj o

vD

•Jj ^ T> V— •• — J7 '

II Ul

c\) *—

•

i— 3

=X _l

O T) 1

1

> O

* fY h

• —» n cv O X rO _i Lil *- * x n *

I- X *

C\J < XI II

»- cr HO i-O^- x tr h h

• - cr - o

*— Li ) — ~

"0 — - II ^

• vO \

I J \ h 7

I 7N X -H d

- \ X X

D w t_

i ~ X

i— i— -

LJ <1 *-* \ — X * * Q_ m rr cr o X 3 - IjH

: Li • h- c/l * *

111 I I—

<r rr i >— o

in cr - rr i

3. O' \

i- O' \

o o \

c -

Ld m

I— L J c ^

u c> o cr L 1 X>

“1 Ifi

IxJ x n

in x

< <

Li rr rr CD o o

rr c

< cr. L. > V <

cre -

Li -

U‘ -

_J -

an

»- ii if

<. H*

LJ

Ll n ro

h-» a - x -

in «a

ro +

5 l- • - 7 U

rO O J JO •

II o

I- H IrO X

X II “0 O 'J H V— —

•

J 7 H IJ U < - -

X |~ IsJ 4- TO 0J ~ X —

I

• «"H I 4- ~ O

k- h- 1 — CL H h O

X H (0 I )

' ~4 _J X n i h ^

^ i— — oi » H ri n

o -h n x >' rO O I OJ

rO

_J

I i _

h- 3 * II O • \o —

• nr

cr *• uj OrOh

rr h c

rr - U

h - - rr0

• II

. J 1 1 J X \ h— \

X k J (O \ H

o • - \ x in

o OULl -Y o

0 Ll

* \ X

- o

II Dill *~H X

C_> —

—* Ll V K-i

m nil ^

X O 1 ' 4 OH i O

\n o cl x j lUHh II — m —* co 4 o -< on

LO

LJ

— OJ

a. -

it

rvi 7 O “O LO

«- J > —

rr Ll - —

«

CT C\l - J I— X IP

_J J - *-H < III I- (\ cj r h *.

x — •—

cr — rr lo

r\i rr no o.

rO

»*o _J

fY _J

cr o -JO o - - *— o < *—

ii » • nr.u y

* *

*•********* *#-H-*-H-****-i4*-*-lf-*****-||.-#-***.*Ht.^*******^**^*^ if dx-oh\j ot-no^r)T'7)HO ^-roo^r)7'o>H\Jo-roo^o7'o-4\iD^-DOd. )t>o-imdj-iOO v^o ,'oh\j i-rn HHOI\IM'\J ,\lf\lOl(\l'MMO'00'0 /li<10r)D044-+t444444JUl 71 D JO (0 JO Cl (1 j0 O ,0 0 0 O O O 0 n nrs-fs-^'--X.d.

Ol I\j >M OJ (\| \J AJ rj rj ro OJ ^ AJ OO AJ AJ '\J AJ (\J AJ M OJ (\l CM OJ OJ OJ AI (\l AJ OJ AJ OJ DJ (M r\J (\| M OJ (\J (\J OJ \J M AJ ,M >AJ AJ M OJ OJ OJ OJ iM .M OJ \J \J

O »-H t nNAJKlinNOHAlrOJvDHAJrvOOHAinAJDJlt J-J-LDvDHAJJJOHHHAIrA t^NvAJrOJ-^iDvOvDNO’OJ-JlNOJl

io 'On jo jo on nor^-o-o-^A-r- 7>o-do-h-4 '4HAJAJAJ'OOOrOKi-4 4J-.4 no ninjo.nriLD o no or--fs-r-.d-D3 ^>o'D—«"vi Xrf ± *3- + O OiOOO O JO O O JOlO DJO JOX) OOnJOJOiOnoniD OO JO JO JO O OJOJOJO O sO.O .0 vO o o 0 OO 0 0 3 0 0 73 000000030003003000 0. 00000003030300300003003-33003 DO O DO OOOO 3307500000000 OOO OO OOOOOOOOOOOOOOOO O OOOOO 3000 300 0 0 30 3 O
r. <

id

: h- _J

1 L/l h- T 0

7* T

r> i—

CJ 111 ^ an

rr n

i <1 7T

liJ <

II II UJ

“D

in *n -»

i UJ b I K mm 7

-H \l O

LA 3

ui ~

T7 3

<r>

ii m

l/l bl I

7 in

y-* o (M

ojX HH n

7” T

7 kh n

rr 00

ii h- oC vl 1“ n to

lO m -

• O' Ui

O' —. •> m

i lo in o o

O IT'

I vD Id O

II

o

~ 7” O no I(\Ih- I-— ^

i O Id ||

i *—-< *— <i "7 h- w o m cr 5

-

• t u_ Jr ooi i n m b. i b u ui

II 5T h n

in o

,n n o o n in

7* —' ^

t-i O -—«• UI

CD lT) CD

II CJ> *-» fT' -robJ vO ^ vD hh n ~ —

— ^ »- -

H M IJ <1 Id <T Id Id b- XI-l- 7 l-^>-)-^ n 7 H(THffHH

7 oro/r

c> li_ Z

«H O

4

i I- l/l —. *sr o z>

ZT if) ^

C\i o

< <.

if)

IT 7 ^ ^

Jll- II «—I O —I i-H CJ w w •. Ohh(M« |- - < X »-< o o o —

O 7 7 7 7

CO ^ ^ o

I I— Id I—

rH rr tv X 5^ X

) n

u_ 7 u o o

: id t u ihi

• n -> n n

o o o o o

tjJ H H W W ~ T ~ X ~) I— XI

I d Id Id UJ — I— 4- I— il r r rr nt

rO O

O' 4

O' -I

> n

n t* o ^

LJ —

• — b I

II Id

8 — I 7 01 r

i bJ O I d I 7 T —“)—

0 Al hh X h- n 7

o t’ o n n t >

Id UJ

i ^ J?

CJ

n_ 7> *-

r i Ll

7” 7

r O O

O LJ

UJ <r J O Q_ —• O J)

!j_ tv n cj 7 O i

lil :

in u uu o uu uu u o u o

**•**-» #******«**** * * * # 4 **•* * 4 * 444 ***-** 44 ** ON o T' O H \l 1 ^ O 0 N O T J H M ;0 t n ON-0(7\o^|-vj-o-t»^or>.oTNO-IV0 1-nO^OT'DrH'V f0 4-r)O r^ 0 S' D H vl -o r^r^r^r^DD oco o oofi)DcnawT>0'a''T'^.J'ri'a'0'oooj03oo30HHHHHHHHHH(\i'\icM^,MMM\iM.M ,0'0'0'0

t\Ji\iAJf\|(\J AJf\l(\J'\Jf\Jf\!(\J(\|(\J<\|(\|i\|(\jc\j(\ir\j(\i(\jc\|rOK)rOrOrOi,OrOfOrOrOrOfO ,OrOiOrOrOiO!OnrOiOrOrOrOrO.'OiOi'0 0 '0 'OrO '0

\OOH(MK)nfOrOKinrOvONOHf\lf\J 4 Lr)vOrjn 4 NOHK)OHOHNinN 4 lOHHHHHHHN(MKJirJOH'OinvnHf\IOj(\llM--t MO-O^rOrO'OiO'O^rO'O'OT 4 4 4 4 JJ m >0 vO O N N N O O H H H f\l (\i KJ 4 if) if! Li i/J 'JO IT) LO m vO ^0 vO N N N N N O *3000 7) o o o o o o o o o 0.0 0 0 o o oooo o o o o o o .ojjssnnsnnnnnnnsnsnnn fv~r»r'»rs-r^fN^r^o o o o oo i " i rr Li j -ii '_' > u i u i u ) u j a i hj v-u vu r— -» uu uu uu uuu u u u u u u u lj u u u u u uu u u u r^» r*» i',» r— i'*» t^» ^ r^» r

>— n* r>» n- r^- ^ r^» 0 3 o u OOOO 7)0000 OO OOOOOOOOOOOOOOOOOOOOOOOOOOOOO —

•—'OOOOOOOOOOOO — — — — — — — — — — — — — — —

>—

lj _/ u/ v_/ _/ _sw _# j u u u u O OOOO OOOOOOO ooooooooooooooooooooOooooooooooooooooo OOOOOOO
_J ID I- bJ

r> o - 3

- l/l - 1/1 — o

«-

1

a X 7” — X

x o

X 7?

rr - x —

7 LT — O

x a X T

7 — X

in n

a. ~z 3 -* c - L

Ui Ll1

l/l CT

LTCM

CD * d in X o

<1 n_ ^ 3

• ui — a X X

c/1 7!

o' w < <r >- o x x

7 * Cl/1 x l/l X o

> a X CL X X

. <r cv

. T

7 X

> o in

f T' Q

. x x

5> a

CM h X 7

Ln c r O Id ~ U X -

h < \ 7 ^

— X O C

X O \ ~ —

1

« U X IT X x

. « UJ M O'

• O T «- >n H

I) - Ti

T' —* 3 3 rt x \1

O - - o ^ —

O H (\l T

7 X X x

.> n n —

*

, x 7

* T

5 7

* n 3 3 x 3

x — - T

7 —

3

8 —

CM (\j

it- X X

Lit Id n n

i/i

Id

7” UI x w c\J 1 — X n T

7 L . O lO X < X

vO —

n c II •

II II —

CM 3 —

X X Li

d <X Id — » x x > x (Y cj h rr r -) x X "> " II ..J lL

T

7 T

7 n n

' ii n

II 3 3 3 x 3 7

X o o o * o c

x x x cm h cr 3 w. w — X

(M II rv. n o O n _J <r < <r cm <r _J 0 d iJ 1 d -> d <£

1 ) cr cr cr x rr o

T

7 ^

n r. X CM X X

in i x m

a. 3 • x ^ o

rO vD Id 1

3

cc o

O L/l > a u J i/i ^ n - —

rr Id

CD ln d d

CD cf * C/1 CL —IX

Ll <r

•> 7

r CM

- O

i rr

II II 11 II M Id x r\J x M-O r li

n cl 0 l/l 01 x

lj o d o m

Ld Id 7) 3

cr T n co 7 T

7 o o o o i

iD O

CD M M \J

******************** ^

* ***.****o*?io

T O o - o T> 3 .’^7 1 nn^n,n;nd.n,OJi.o 1o.oJi.o

x cr

_J Ld

UJ X

3 Ld

_J d

<c cr :j <r

ID CL

l/l i/1 V lJ- U '7 7 * a x — —

T

7 7” n X

n II - l/l 1/lH-fL

O X L/l X n or/ 7

^ T

7 X —

7 DJ rr cr — x

111 liJ7 ^

x x

id d 7? 5T ^'O

d «7 'T

rr rr ^

d i o

n. n o

c. •-» CM 3

O —

-CD x

5- .n — cr

CM X

T

7 T

7 3 T

7 i

I U x

• Ld

_J +

I II -f UJ r 3 x Ll ^ X Ld O 1 1 —I ID x

X D X w X 1

1

X

>" II Ll O'57 d U. O T 3

d o- -J x n cr o

CL rO w x

4- T

7 T

7 rr 'r

ii ii

^4 X — - 3 0

• ro x 3 • • x Ll *-" xx

J X lii > CO CD

• II _J I UI • • X x + T

7 3 X X

x X -r T M M 7! -JO- x n X -r ^ h-* tn ii x — —

x

"7 lL 3 II “ 7 3 Ll IL Id

k- 3 3 rr C) x x f UI

********

-t n oxo TN o H M O o O ll T» .D H

0000300000 OOOOOOOOOO

oooooooooo

IfO 7 l/l 'Cl N ^ ^ H

J O O .n vO O x X o

“* 0 0000000—4

X X X -o rt- 3 0X00

x x x x \1 M

OOOXCMfOrf-vO

\J O M M

* * * « *

o o^o

\J M -M M O

0-0300'

ooooooooo'o 30 0 0000000000

^ ,o X CM X) D x X CM rvJ'M*D*o*o*o ,Orf CDOOOOOOO O 0000000-0 0
c -

_J r ^-

li.l - l- O O -

- "1 ^ J“K Ll h O O -

- ~

0 • 3 x

Q

*: h- o or x

o «* —

o »-

f- o

^ K C

>H H

I- -*- <1 f— ~ LJ o o

Ll <

IT* i/l -> « M

nr 5- l

~ j

Ll T

O LD x cr

UJ 77 L- II

cr ~ in - m cr - ~ c v ^

a ^ a x — o

O ^ H CL ^ rH X ^

— X T* — H

^

g

x - cr T’ _J x -* - l/l ^ - ^ a - ~

h > LJ LJ

1/1 7 0 h

a — < <1 V o x h- 7 * < 1/1

V- _l X IJ

cj o

_J _i a •

x o

a a.7? » II O l/l o o in HCLU

ii a

i/i - ^

cj *

rt \ h

7 i/un

- o cr m ci x

<\J 7 7

II II II r i/i x

rr ox

v (1 O

7 7? 7!

rr rr a

lil hi hi • I- h- *- iJ 1 J !J

5^ 5- *>

I c cr <

rr rr rr

I -X X ^ < cl a. a -

i i/i — O >

n - ~ — Li J x in r,

Ul h 7

nr - x

7> UJ X

— I- Q H < >- x rr _i in -

- w <r ^ X <

i/i a .j

rr i- Ll >• lL ^

7> - ^

— L/l n o

- m n ^ rr T

(/)>-'- r <m X — X '* n.1 n

~ x 7^

I— X CL U X X

- C hi — 7" X

1/ 5- h

rr > cl X - X

w C\J X

7 Li J - — <r rv U X o

lr 1/1 - < — X- X H coo ? ^ —* ***» X- o i/i m -OX

nr — cm x <\j x 7 X

7*

T’ X

X <\J n o

O X X

II II II 7O X -4 X

> Ul Q CL 5" O X- X- 3 ^7 x M O X X X

00 —

X X

* X H J

“1 I + x

x- a m X

X X

II X

LJO

— XIX

X / II 7

O — O X

II II OJ LL PO O

n

•O ^ x ~>

II II CM rO

hi

"D X

~z. X CL-J X c x *X oj >

l J X II II X o 7

O CM

_J X

— «—

I

X “D

- I X «—

<

Q n.

n ~i n x n

x X x LJ 7

- X — f> x

j- u r> 7* —

x n x x *—

(

CVI 1 1 7* IJ _J Cl ^ ^ n II x

+ + II Z + H x Ll 7

ro ro o x rH x ii xii nr H H K) II, X II CD JIjIhD

Mil n^X<_IO£LX'7 7 'D 7 7 O D J t 7 i- |j ^

i—i »-h o -< o x lx lj h rr a h o o

x <M

— m —

co i/i x cr

II x

IJ 77 X II c x

x in

in cr

II CM

Lj I CD *

< in x o

C CL

or m

— in o- - — o x —

h cl 2 m

X z? — o O — X CL ^ x X ^

— X “ — x r - «- x 7 — x

cm —) in n

x - a r

7 _J ^ > X

• l/)7 » XX Li ! 1x1 1/1 7 0 X

o — c < x r- x x 7 * c 0

X C/1 '— x

X U > L

5* Q - -

•• 7 X «

h i/i r. in

O x

77 in

- a ? x

O l/l o o X CL

II 5

l/l -

CJ Zt- CL X

T

7 m

- o

in cl OJ 77

II II l/l l/l rr o

X CL

m x o J

o - * in x cr

i/i x

nr 7* x —

7 a

n - x —

X L/l O 'Y x nr rr J u i J

LJ X X

7) IJ IJ X X

I _l c <r c rr nr u <r c

i i/ ll (I

cr —

hi x

— - 77 LU x —

X CL X < X - x rr in - u

— CD Cr X < <

CL J X

X U <

a - x

~ ino

x O -

in q ^

rr x ,n x — rr

77 CM X

AJ O — x x r* X “) 7

CM <

IJ X

x J1

X x

o in

- rr —» x

in x o —

a ir x <r — m

OJ CM X X n

< o

a o

uu uu

n n rs. i in n h \i n ^ 7> H '\J n 7 D 0 X X) T> 7) X M-O^-n O'^OT'D-l vJOrt-O o

OJ AJAJ OJ AJ CM OJ CM AJCMfOrOrO-OfOfO On K1 n 7 7 jt J- J J -» ****** ****

x m n j- n n 1 o t* d x m o j- n

x x x x x n rt- in -n x o o o oox<MfO=r OODJOOOOOOOXXXXXXXXX

OOOOOOOOOOOOO ZJOOOOO o 7)0 0 00 0 00 0 07)0000 0 00

in^NoiMiojiNoiod-NoxcM^in^xixj^i/ivOsoxoj x x x x m ^-invoxooooox x x x M OJ (M (M (M (O N1 (O ^ ^ d- ^ ^ ^ Ll in l/l :n m ifl v(l .0 ^1 ooooo ooooxxxxxx x X x xxx X X X X X X X X X X X X X X X X X X X X X X X X X X X X X —I X X XXX 00000000000000000000 0 000030 OO 300 0000000 000 0 0 000000000000000000000 75 00 0 3 0

- — — — — ~ ~ ^

CJ LJ '—J ~-J >—i —» X v—t —> —j — OO 000000300 0
if .

i- -

' rr f\:

K ^

.5f b.* y'

1

1

0 C

V- I—

1 I O

Lfl <

III — o

(.0 to

• • I —

«

I— liJ C l /> 10 JJ «>

~0 v <

<r .o i Oil 1/1 1

1

"0 "O “ c ii ii ~

i— liJ <r i- i

cr r ?

i— c —• o — i— (—cr

c/i ^

ll_ -H o o

— ir ^

'YCOM

h- -D

i/I CO M O -«

C C L/1 I— > II CO to II “0

o

to

h- c

to T

r . i

i “0

II if) Id

“0 ~D

II T o —« i r- >' »— 5- 7 O 1 O I m/i u i

75C liJ I

— Y_ h- ,*0

ii in

0 H

- CP

II

5- I- ^

* “0 C 5*

L/1 1 > CM LP ,

u

II 111 to *

I CO

Ml to id ~

CM O

X o

O CO "> l|_ li_

• <X —

I— c •

. ro x -tt w I— 1

1

O C "5 M

or c • k— j ix C r> 3 «—lt' n—. w

m.-rr ;> • >—

^vl O -) O.IL Ol !L

r—< ii 1^/1 ’l "i —• "X >—

«

‘Id •m ->

3- T’

. .> fV k QJ

Cl (V -r- C X

Till-.' -

, CM X O * X h~

~~ Z? C II >T b- I 7 c -

h- t or - >~

Itl -» O O 0

rr x rr *-«^x

cr

>— li ’ «*- -

TO - >"

:» ~ o. 11 in x ^

•O X r-

.'Ll -.TV\ -*H-T

_l - X X II • K.0 W

T.* O I— It— X

_l -U1 c *

I— 3- • -• -• o- •-•rr iij o ~) 1 > o 1

O -i \l O t- 0 .0 0 H 5 -I J O * .0 0

v'* 0 T» O -H \l O it- O 0 ,N D T'.p H-iMO + ,,5 O vO -T» O -4 \J 0 J- 0 0*X 0 Tn M CM CM 0 CM CM CM J vJC\IOfOOK1

'1 Kl'0 ,OOrO-tJ'd'--f 1‘J'J-.tJ-J-JW1 0 /1-0 O iTI D JO O >D -O -O 0 Q v0 0 0 0 0
IU

it n

Uj * I n o

u7

O

3

LO

in

r>

CL

<r iu

_l CD 3 <=r o X

_J L/1 <rCJ _J

_j cr oj o

ti cvUJ

lr. o - o in x or

II v

UJ 7

I— II

L/J nr

cT, *-H T- x in 7

lO or

II c\i Lil *

CD * X i/j X O

< 0 ^ 7

- II O lO O CD

•—4 CL in v o _J

7 in

• tu i

nr Mil til

x rr in >-

rr 7

>7 n

1 1 - x m

o nr 7 >-

cr —

ui 7

— in

in o •

. o v r*

i CL 7 O'.

: 7 ~ o

i x CL X X 7

X 7 ~

< r * H

7 — x nm n

- cr 7

J-^ >* H

l/l 7 •* CL - ^

X U, LU Z O •" w < «I o > *- - <i m

^ ^

i/I ~ x

CJ > lA Q. - •

. 7 X ^

. w UJ r-4

4 in o m

7 O

LU x ' X Cl 7

<t X -

i— rr in - iu w 03 co X <t <

CL -I X

X Ll Ll - ^ — mo x o - m q *-» nr ^ m

>- w rr 7 oo x ^ X 7

CM O ^

X 7 7

^ 7

... U 'U

i ? y

i _i <t <

< nr nr u <r <r

i (C Q CL

>U 7

5- O

<r 7

nr rr

<r o

a o

x m

or «- o »

u_

ii H CL X X o cv 7 X

CM X

III - X X

<r cv x o

in •> x X

7 X

n n

in ro o x

a -

•5- X — M

r\j x

5 a —

x x

x

O O «*• • X X

II 11 II CD

X 7 IU

ro cl Ll

\ J 7

in

V—* oo

CD

x m

X CM — o

7 X

^ o

8 CD

X ~> x

8 <C X

cm x cr »

cr>

•

7 II O 7 x o x

D^lfl^ O (M

J X O tL x > O p-t

X X

—I *5-

II II X X

_J :>

~> o <r

il o o

3- X K>

X •

II 7>

o cr o

n _j n

5* Ll

in x

o ll x n

II o

X

!5" O

LU II lil ? Ill x vD ^

II 7) II ZD II ~> II 7> <X 7) 7 —

7 <r 7 j z < x

I x X X X 3 X x X X |

1 U <1 _IX^-'5"C\J5 X~X~X^ <r 7 <r 7> <T7 7 w rr s-o j ul <r o j o Ll o il nr o

in CJ r- x x O X CJ X (.J X u

. o in o in o o XX M .MO 3

x crco

• O

in cl LU CL 7D

X Lu O X

7 X

7 7

< x

X

x ino

lu or

cr <l C CJ

in ui

ui x

5 II, 7) 7

in <a in or

<T <rCL Xx LU X X

3 \

X \

Tv \

Z> o o

nr 7 »\iurn

n n .n- n n

o — _i m

x o x <r 7 h iu <r > _i

— “D x O

7 CJ

7> x

O

CJ UJ II Ul x ~2) X ^7-^7

x :T> n

CL «>* (M XvOa x * o o

i x x x uj cr

r o

M ll

J CL X X — X

IU cl O CM 7 x 7

T x ^ 3 X 7 x v n .j i j cj * «- X o

' u

IJ <_> CJ CJ

vi o 7 n

* » * #

O ^ 0 iT» **##*#**#********-»-***#*****-»l-**********#*****-»* •D n ^ n 7* o -i aj-o t nor-oT*3xM'n7nnxn t»jx m o j- n ox ot'dx \jo 7 n nr- ot» j X X X X X DJ \KMfM(M(\jCJOJC\J(MnrOnr)rOrOrDDrOn.tJJJ rf t ± t J J- in /) O n.n OH JO D O O

^,^^(^(^(rO^' ir)J3fs-oooo

O OOOOOOOOO'H-H— '"4 oooooooooooooo "DOOOOOOOOOOO oo

oHaiiojinoMioisoioJvDsnjKiiniDOHjinNHKunioioj-invootMfti HHHH-(HlMMrM(M(MI<1lOIO'Orti-ir)--+i/)l/l!nLninfW)£NSNNS003

•X H X X X *H X X X H H H X H «X *X X H X *X X H X <X X X X *X X X X X X \J M OJ 3030330300303000000000333330333033 0 3 030300 3000000000300000030000 0 3 O O O O 3 M

r\jiOJ-inNo(\imxr\i 3 3 OOOXXXfMOJ

iM 'M <M M \J VJ M M M M 0 0 0033 3033

3 330033 3
APPENDIX C

AN INTEGER PROGRAMMING MODEL

The model described in this Appendix is a somewhat simplified

integer programming (IP) analog to the DP model presented in Section

3. Since the IP version is subsumed under the DP version, the former

is documented here for its own sake, as an application of integer

programming, and is not necessarily intended to serve as an

"alternative" model.

As in the DP model , the IP model prescribes actions to be

taken each year for a T-year period to minimize the total cost over

those T years. From a given initial fleet, the decisions specify the

number of purchases each year and the number of retirements , from

the initial fleet, of engines of each age a. (Note that T may

not be taken so large as to make liable to retirement engines which

were purchased during the T-year period.) These decisions are to

be made so as to minimize the total cost for the T years, subject

to the constraint that a specified minimum fleet size be met each

year.

• -/.•Vs*- - T >

- " ‘ ' • The variables are:

x = the number of engines, initially of age a, retired in

cl

L

year t,

y

= the number of new engines purchased in year t.

The conventions regarding age definition and decision times are the

same as for the DP model (cf . , footnote 6)

.

Ol
The data required by the model include:

= the minimum number of engines required during year t

(checked against the fleet size after year t's decisions

have been made)

,

M = the maximum number of engines which may be purchased in

year t,

P

t = the purchase price of an engine in year t,

Q

= the number of a - year - old engines in the initial fleet

,

u^ = the maintenance cost of an engine during its a^1 year of

service

,

v = the resale value in year t of an engine which was initially

cl U

of age a.

Note that this model does not have a ceiling on the number of engines

that may be retired, nor does it have a mandatory retirement age, as

does the DP model. If a set A of ages of engines in the initial fleet

is given, then the model requires data for u and v for a as large as

a + T, where u is the maximum age in A.

Using the above definitions , the IP is formulated as

minimize

T

l

t=i

f p

t + uPyt

+

l [u

14

aeA a+t ^a ^ X

at^

V

at

x

at^

T < t T < t

Vt+1 >\ (C-l)

14 T

The term l l u Q in the objective function (C-l) does not

t=l aeA

a 1 a affect the minimising values of x and y , but it must be included

3.L L to calculate the minimum value of (C-l). Also, discounting has

been omitted for simplicity and could clearly be implemented in the model.

C-2
subject to

T

l x < Q (aeA)

,

t=l

at a

(C-2)

: .. . yt S;Mt (t=l,. .

. ,T)

,

(C-3)

l Qa

+

l (yT

- l x ) > d

acA

a x<t

T aeA

ax ' (C-4)

yt nonnegative integers (aeA, t= l , . .

. ,1

)

(C-5)

The expressions { } summed in (C-l) are the costs for the individual

years t. Each of these is calculated from the following components:

( p

t

+ up) = the cost of purchasing an engine and

maintaining it during its first year

of service,

„ rn

~ I x . = the maintenance cost in year t of engines,

a+t^a x<t

o: . ’initially of age a, which remain in the fleet,

* v

atxat

= the revenue from retiring x engines, initially

of age a, in year t,

l u

t

^ T+p7T = the maintenance cost in ; year t of engines

T < t

purchased during years t = 1, . t-1.

Constraint (C^2j specifies that the total number of engines

retired, initially of age a, not exceed the initial number of age

a engines, and constraint (C-3) restricts to at most the number

of engines purchased in year t. Constraint (C-4) requires that the

number of engines in the fleet in year t (after purchases and retirements

C-3
in year t) to be at least D^. If d is the number of distinct ages in

the set A of ages, then the IP in (C-l) through (C-5) has d + 2T

constraints and (d + 1)T variables.

The reader may have observed that the IP described above does not

specify any retirement order. The condition that engines be retired

in order of decreasing age may be imposed by the following suggestion

of A. J. Goldman. This uses (d - 1)T additional variables and

2(d - 1) T additional constraints :

l

a<a x

at

< (I Q ) 6 L a a<a

at 5 (06)

Q, - l

T <t x < Q ax — xa

(1 6 at>’ (07)

with aeA, a f min {a|aeA} and t = 1,...,T. The 0-1 variable 6

3. l

acts as a "switch": if 5 = 0, then the retiring of engines of

l initial age less than a in year t is prohibited by (C-6), and (C-7)

is non- constraining , whereas if 6 = 1 such engines may be retired

since (C-7) together with (C-2) would imply that all Q engines,

initially of age a, have been retired, and the right side of (C-6)

is non -cons training in view of (C-2). Of course, the constraints

(C-6) and (C-7) may be introduced only as they are needed. Thus if

the IP (C-l) - (C-5) yields a solution in which retirements are

partially "out of order," (C-6) and (C-7) would be imposed only for

the exceptional pairs (a, t). The nature the solution will depend

on the data, and if these are "reasonable" one might expect the "order"

C-4



II1