Solved

Dynamic Programming - Recursive Implementation

Posted on 2013-11-04
14
308 Views
Last Modified: 2016-03-02
I'm having a bit of a problem modelling an optimization problem in matlab using a recursive algorithm (which is a requirement).

The problem is as such:

Decide the quantity of fish to catch each year considering a time window of 10 years knowing there are presently 10000 fishes in the lake, year 1, the growing rate of fish is the number of fishes present in the lake at the beginning of each year + 20%.

Let x be the quantity of fish to catch, $5 the price of each fish and the cost of catching fish:

    0.4x + 100 if x is <= 5000; 
    0.3x + 5000 if  5000 <= x <= 10000; 
    0.2x + 10000 if x > 10000; 

Open in new window


decide the number of fish to catch each year, for 10 years, in order to maximize the profit.

Future gains are depreciated by a factor of 0.2/year, which means that earning $1 in year 1 is the same as $0.8 in year 2 and so on.

I currently have defined the following objective function:

 
   x -> quantity of fish to catch
    b-> quantity of fish availavable in the beginning of year i
    c(x,b) -> cost of catching x fish with b fishes available

    f_i(b) = max {(5x - c(x,b)) + 0.8 * f_i+1((b - x) * 1.2)}

Open in new window


How would i go about implementing this in matlab?

This is what i have so far:

Main file

 
  clear; % make sure previously defined variables are erased.
global FishBeginningYear Years FishSold MaxProfit  MatrixProfit

FishBeginningYear = 10; % In thousands (x1000)
Years = 10;
FishSold = 0;
MatrixProfit = zeros(10,52);

% Border Conditions
if FishBeginningYear <= 5
   MatrixProfit(10, FishBeginningYear) = 5 * FishSold - (0.4 * FishSold + 1);
elseif (FishBeginningYear > 5) && (FishBeginningYear <= 10)
    MatrixProfit(10, FishBeginningYear) = 5 * FishSold - (0.3 * FishSold + 5);
else
   MatrixProfit(10, FishBeginningYear) = 5 * FishSold - (0.2 * FishSold + 10);
end

MaxProfit  = pesca_rec(2, 10);

Open in new window

Function

    function y = pesca_rec(Year, FishBeginningYear)
global FishSold MaxProfit  MatrixProfit Years

y = MatrixProfit(Year, FishBeginningYear);
if y ~= 0 %Memoization
    return
end %if

auxMax=-1000;
kchosen=0;

for k = 1 : Years
     
    % Costs
    if FishSold <= 5
       Cost = 0.4 * FishSold + 100;
    elseif (FishSold > 5) && (FishSold <= 10)
        Cost = 0.3 * FishSold + 5000;
    else
        Cost = 0.2 * FishSold + 10000;
    end

    MaxProfit  = 5 * FishSold - Cost + 0.8 * pesca_rec(k + 1, FishBeginningYear - FishSold); % * 1.2
	
	if auxMax < MaxProfit 
		auxMax=MaxProfit ;
		kchosen=k;
	end %if MaxProfit 

end; %

MatrixProfit(k,FishSold) = kchosen;
y=auxMax;

end %function

Open in new window


This only computes fot the case where the year is 10 and b = 10 (value in thousands).
This is the same poblem describes as "Discounted Profits Problem" in book

EDIT: Can it be done in Java? Then it would be simpler to translate to matlab.

EDIT2: Code edited. Now i'm getting "Maximum recursion limit of 500 reached.". Heeelp
0
Comment
Question by:PauloRP
  • 6
  • 4
  • 4
14 Comments
 
LVL 25

Expert Comment

by:Fred Marshall
Comment Utility
The "book" appears to be in Portuguese which is more than difficult for me to comprehend....
0
 

Author Comment

by:PauloRP
Comment Utility
What do you mean? The book is in english. Plus, i already explained my problem in plain english.
0
 
LVL 37

Expert Comment

by:TommySzalapski
Comment Utility
If you change the .pt in the link to .com, then it displays the book in English (at least for me).

Look at the top of page 59. There is your recursive function, right there. See how the function f(t,b) is based on f(t+1,floor(s(b-xt)))? So the function f calls itself. Recursion.
0
 

Author Comment

by:PauloRP
Comment Utility
@TommySzalapski  Can you show me a code example? I can't seem to grasp the concept. Evem more i don't know what the stop cndition would be. I keep getting errors with 0 indexing in matlab :(
0
 
LVL 37

Expert Comment

by:TommySzalapski
Comment Utility
The stop condition is if t > T. Notice how f(t,b) only depends on f if t <= T. When t = T+1, f(t,b) = 0;

So you just need an if statement something like
if t > T
  f = 0
else
  f = f(t+1, floor(....
end
0
 

Author Comment

by:PauloRP
Comment Utility
@TommySzalapski Great. Can you take a look at my implementation?

I'm getting an "Attempted to access prop(2,0); index must be a positive integer or logical." error on line 66 of my Main file.

My implementation is:

Main file

 
   clear;
    
    global M Kdep Cost RecursiveProfit ValorF prop
    
    Kdep=[10; 20; 30; 40; 50; 60; 70; 80; 90; 100]; %max nr of fish in the lake at the beginning of each year, 10 years, in thousands. Growth factor = 20%
    
    M=1000; 
    
    %Cost and Profit of selling i fishes given that there are j at the beginning of the year
    for i = 1:50
    	for j = 1:11
    		Cost(i,j) = 0.2 * i + 10;
            RecursiveProfit(i,j) = 5 * i - Cost(i, j);
    	end
    end
    
    
    for i = 1:10
    	for j = 1:10
    		Cost(i,j) = 0.3 * i + 5;
            RecursiveProfit(i,j) = 5 * i - Cost(i, j);
    	end
    end
    
    for i = 1:5
    	for j = 1:5
    		Cost(i,j) = 0.4 * i + 0.1;
            RecursiveProfit(i,j) = 5 * i - Cost(i, j);
    	end
    end
    
    %prop = 1 : 10;
    
    ValorF = -M * ones(10, 50);
    
    %Border conditions  
    for a = 1:5
        ValorF(10, a) = 5 * a - (0.4 * a + 1); %On Year 10, if there are <= a thousand fishes in the lake ...
    	prop(10, a) = a;
    end
    
    for b = 6:10
        ValorF(10, b) = 5 * b - (0.3 * b + 5); %On Year 10, if there are 6 <= a <= 10  thousand fishes in the lake ...
    	prop(10, b) = b;
    end
    
    for c = 10:41
        ValorF(10, c) = 5 * c - (0.2 * c + 10); 
    	prop(10, c) = c;
    end
    
    MaxProfit = RecursiveProfitRecursivo(1, 10)
    
    k1 = prop(1,10)
    
    kant=k1;
    
    y = 6 - Cost(kant,10);
    
    for q=2:10
        if(kant == 0)
        kant = kant + 1;
    end
    	kq=prop(q,y)
    	kant=kq;
    	y = y - Cost(kant,q);
    end %for i

Open in new window


Function

    function y=RecursiveProfit(j,x)
    global M Kdep Cost Prof ValorF prop
    
    y=ValorF(j,x);
    
    if y~= -M
        return
    end %if
    
    auxMax=-M;
    decision=0;
    
    for k=1:Kdep(j)
    	if Prof(k,j) <= x-k
    		aux=Prof(k,j)+RecursiveProfit(j+1, (x - k));
    			if auxMax < aux 
    				auxMax=aux;
    				decision=k;
    			end %if aux
    		else break
    	end %if Cost   
    	
    end %for k
    
    ValorF(j,x)=auxMax;
    prop(j,x)=decision;
    y=auxMax;

Open in new window

0
 
LVL 37

Expert Comment

by:TommySzalapski
Comment Utility
I'm guessing this is the offending line?
kq=prop(q,y)

So when you got y = 6 - Cost(kant,10); y must be 0?
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:PauloRP
Comment Utility
@TommySzalapski Sorry, i didn't understand. I'm way past my melting point with this one :(
0
 
LVL 37

Expert Comment

by:TommySzalapski
Comment Utility
Explain what this line is for:
y = 6 - Cost(kant,10);

Any time Cost(kant, 10) is 6 or more, you will see issues.
0
 

Author Comment

by:PauloRP
Comment Utility
@TommySzalapski y is supposed to be the money available minus the cost associated with a "decision" for the problem. I based my code on some code for a similar problem (resource alocation). I forgot to edit that line.
In the original problem that expression is:

Money to invest (6) minus where to invest, and compute that 3 times (3 decisions to be made). In my version there are 10 decisions. k is supposed to be "decision", k1 "decision 1" and kant "previous decision".

Thank you very much for your help. I don't have words to express my gratitude. I'm really stuck and i'm on a very tight deadline :(
0
 
LVL 25

Assisted Solution

by:Fred Marshall
Fred Marshall earned 500 total points
Comment Utility
Yes, the English here is fine. I was only referring to the link you provided, as a reference no doubt, and the result.  The change from google.pt to google.com seems to work.

It seems you've made good progress on this.  I'm still trying to wrap my head around your code.  If the objective function is this:

 f_i(b) = max {(5x - c(x,b)) + 0.8 * f_i+1((b - x) * 1.2)}

Then I would read it this way:  "Maximum profit over 10 years given b fishes at the beginning of the ith year ....."  I'm unclear on this.
It seems to me that you want:
Maximum profit over 10 years given a catch size of x_i for the ith year in each of the 10 years.
I'm assuming that the catch each year is different because you said:
decide the number of fish to catch each year
instead of "decide the equal number of fish to catch per year each and every year".  But, perhaps I made a bad interpretation of the objective.  Which is it?
0
 
LVL 25

Expert Comment

by:Fred Marshall
Comment Utility
I have the code running but am still hoping to confirm the objective statement re "is x a single number or 10 numbers?"
0
 

Author Comment

by:PauloRP
Comment Utility
Hey fmarshal. Sorry for not responding. The solution itself is 1 number, MaxProfit. But part os the solution is deciding how many fishes to catch each year, prop.

Thanks.
0
 
LVL 25

Accepted Solution

by:
Fred Marshall earned 500 total points
Comment Utility
Yes.  I understand the overall objective.  What I still don't understand are the specifications.  If x represents the number of fish caught in one year, is the specification to maximize total profit based on:

x_i+0,  x_i+1, x_i+2, ....... x_i+9 based on the x_i being *all equal* or 10 separate values?
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Suggested Solutions

We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
The viewer will learn how to implement Singleton Design Pattern in Java.
This video teaches viewers about errors in exception handling.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now