Equipment Replacement Problem (example) - Solved

Suppose a company needs to have a machine over the next five year period. Each new machine costs Rs.100,000. The annual cost of operating a machine during its ith year of operation is given as follows: C1 = 6000, C2 = 8000 and C3 = 12,000. A machine may be kept up to three years before being traded in. This means that a machine can be either kept or traded with in the first two years and has to be traded when its age is three. The trade in value after i years is t1= 80,000, t2 = 60,000 and t3 = 50,000. How can the company minimize costs over the five year period (year 0 to year 5) if the company is going to buy a new machine in the year 0?
Devise an optimal solution based on dynamic programming. Illustrate appropriate stages/ states and the optimal-value function.

	class test{
	public static int i=6;
	public static int p=100000;
	public static int[] get= new int[i];
	public static void main(String args[]){
	//get(t)=minimum net cost from time "t" to 5.given that a new vehicle is perchased at time t.
	//getr(t) is also the same.
	//cs[t][x]= net cost of buying a bycicle at "t" time and operating it until time "x".
	//in this programme, we are trying to find get(0).
	//value function -> get(t)=min{c[t][x]+g(x)}, t=0,1,2,3,4
	int[][] cs = { //0 1 2 3 4 5
	/*0*/{0,26000,54000,76000, 0, 0},
	/*1*/{0, 0,26000,54000,76000, 0},
	/*2*/{0, 0, 0,26000,54000,76000},
	/*3*/{0, 0, 0, 0,26000,54000},
	/*4*/{0, 0, 0, 0, 0,26000},
	/*5*/{0, 0, 0, 0, 0, 0}
	};
	//initialising arrays
	for(int j=0;j<5;j++){
	get[j]=-1;
	}
	get[5]=0;
	System.out.println("# Using recursive method without DP ");
	System.out.println("=====================================");
	System.out.println("below shows the number of calles to getr()");
	System.out.println("");
	System.out.println("\n"+"Minimum cost is "+getr(0,cs));
	System.out.println("");
	System.out.println("");
	System.out.println("# Using recursive method with DP ");
	System.out.println("=====================================");
	System.out.println("below shows the number of calles to get()");
	System.out.println("");
	System.out.println("\n"+"Minimum cost is "+get(0,cs));
	System.out.println("");
	System.out.println("--------------------------------------------");
	System.out.println("# We can use DP to get an optimal solution #");
	System.out.println("--------------------------------------------");
	System.out.println("");
	findpath1(0,cs);
	System.out.println("--------------------------------------------");
	}
	//////////////////////////////////////////////////////////////////////////
	// this method calculates the minimum cost without using DP //
	/////////////////////////////////////////////////////////////////////////
	public static int getr(int c,int[][] x){
	System.out.println("call getr["+(c)+"]");
	int min=-1;
	int tp=0;
	//base case
	if(c==5) return 0;
	//check all the possible values and get the minimum
	for(int i=1;i<4;i++){
	if((c+i)<6){
	if(i==1){
	min=x[c][c+i]+getr(c+i,x);
	}
	else{
	tp=(x[c][c+i]+getr(c+i,x));
	if( min> tp ){
	min=tp;
	}
	}
	}
	}
	//return the minimum value
	return min;
	}
	//////////////////////////////////////////////////////////////////////////
	// this method calculates the minimum cost using DP //
	/////////////////////////////////////////////////////////////////////////
	public static int get(int c,int[][] x){
	System.out.println("call get["+(c)+"]");
	int tmp=0;
	int min=-1;
	//base case
	//if(c==5) return get[5];
	//check all the possible values and get the minimum
	for(int i=1;i<4;i++){
	if((c+i)<6){
	if(i==1){
	//if the item is not in the table. then calculate
	if(get[c+i]==-1){
	min=x[c][c+i]+get(c+i,x);
	}
	//if the item is in the table. then get it
	else{
	min=x[c][c+i]+get[c+i];
	}
	}else{
	//if the item is not in the table. then calculate
	if(get[c+i]==-1){
	tmp=x[c][c+i]+get(c+i,x);
	}
	//if the item is in the table. then get it
	else{
	tmp=x[c][c+i]+get[c+i];
	}
	//finding the minumum
	if( min> tmp ){
	min=tmp;
	}
	}
	}
	}
	//put the minimum value in the table
	get[c]=min;
	//return the minimum value
	return min;
	}
	//////////////////////////////////////////////////////////////////////////
	// this method finds the minimum cost paths //
	/////////////////////////////////////////////////////////////////////////
	public static void findpath1(int c,int[][] x){
	System.out.println("Minimum cost paths if we buy at "+c);
	System.out.println("===================================");
	//find the paths from time "t", where are the costs are minimum.
	for(int i=1;i<4;i++){
	if((c+i)<6){
	if(x[c][c+i]+get[c+i]==get[c]){
	//call findpath method()
	findpath(c+i,x);
	}
	}
	}
	}
	//////////////////////////////////////////////////////////////////////////
	// this method finds the minimum cost paths //
	/////////////////////////////////////////////////////////////////////////
	public static void findpath(int c,int[][] x){
	int j=c+1;
	if(c>4){
	System.out.println("");
	}
	else{
	for(int i=1;i<4;i++){
	if((c+i)<6){
	if( (x[c][c+i]+get[c+i])==get[c]){
	System.out.print("buy--> ["+c+"] sell at ["+(c+i)+"] /");
	findpath(c+i,x);
	}
	}
	}
	}
	}
	}

view raw test.java hosted with ❤ by GitHub