Company must buy furniture at time 0 and must always have a furniture during the

Question

Company must buy furniture at time 0 and must always have a furniture during the next 5 years. For a furniture bought at the beginning of year t, the cost of the furniture is 1000 USD. The maintenance costs per years are as follows: 60 USD for the year t (i.e. between t and t + 1), 80 USD for the year t + 1, and 120 USD for the year t + 2. The salvage value is 800 USD if we sell it at the end of year t, 600 USD at the end of year t + 1, and 500 USD at the end of year t+ 2. Since the technology is developing so fast, Company doesn’t want to use furnitures older than 3 years. Therefore each furniture should be replaced by a new one at every 3 years at most

Find the optimum plan for procurement of new furnitures for the next 5 years.

(NOTE:Derive a recursive formula for buying a furniture at time t and sell it at time x, and optimize this function by using Dynamic Programming)

Introduction to Algoirthms, Dynamic Programming

Explanation / Answer

let's define a few functions and variables:

g(t):minimum net cost from time t until time 5,given that a new furniture is purchased at time t.

ctx:net cost of buying a furniture at time t and operating it until time x,including the initial purchase cost,the maintenance cost,and the salvage value when its sold.

The recursive value relationship is then:g(t)=minx{ctx+g(x)}for t=0,1,2,3,4

The optimum from time t to time 5 depends on two things:the value of the current decision ctx,and the value of a previously found optimum g(x).

Each calculation takes into account the initial purchase price,the maintenance cost,and the salvage value:

Keep furniture 1 year:c01=c12=c23=c34=c45=1000+60-800=$260

keep furniture 2 year:c02=c13=c24=c35=1000+(60+80)-600=$540

keep furniture 3year:c03=c14=c25=1000+(60+80+120)=$760

The average annual cost of ownershipis:

1year$260/1=260

2yr$540/2=$270

3yr$760/3=$253.33.

We also define g(5)=0.No costs are incurred after the timeframe ends.

using backward recursion,start at time 5 and works backwards.

g(5)=0(this is trivial first stage)

g(4)=c454+g(5)=260+0=260(also a trivial stage since there is onlu one possible decision)

g(3)=minimum over:(finally a real decision)

c34+g(4)=260+260=520

c35+g(5)=540=0=540

g92)=minimum over

c23+g(3)=260+520=780

c24+g(4)=540+260=800

c25+g(5)=760+0=760

g(1}=minimu over:

c12+g(2)=260+760=1020(tie)

c13+g(3)= 540+520=1060

c14+g(4)=760+260=1020(tie)

g(0)=minimum over:

c01+g(1)=260+1020=1280(tie)

c02+g(2)=540+760=1300

c03+g(3)=760+520=1280(tie)

At this point we know that the cheapest policy has a total cost of $1280.

We know that we have to buy a furniture at time 0,but there is tie for the best length of time to keep it either 1 or 3 yrs.Let's follow the 1 yr ownership first:that leads us to yr 1,where we buy another furniture and again to a tie for the best length of time to keep it,again either 1 yr or 3 yrs.Following the one year ownershio again takes us to yr 2,where we buy another furniture and thus time keep it for 3 yrs until time 5.so at least one soliyion that gives a minimum total cost ofownershio of $1280 is to buy furnitures at times 0,1,2.

Following up the various ties in the solution we find that there are 3 different solutions that give the same minimum total cost of ownership:buy @ 0,1,2;buy @ 0,1,4;buy @ 0,3,4.This is not surprising given that our initial cursory analysis showed that keeping a furniture for 3 yrs is most economical,followed by keeping furniture for 1 yr.The 3 equivalent solutins are made of all possible combinations of 3 yr and 1 yr ownwnership patterns within a 5 yr timeframe.

This problem doesn't seem at all like a shortest route problem does it?However it is easy to transform an equipment relacement problem into a shortest route problem.Just construct a network in which the nodes represent points in time(time 0,time1,etc)and the connecting arcs are labelled with the cost of keeping a bicycle for the appropriate amount of time.The equivalent network is shown here:just find the shortest route from time 0 to time 5!. Linear programming could actually be applied to this network formulation.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.