PauloRP
asked on
Dynamic Programming - Recursive Implementation
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:
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:
How would i go about implementing this in matlab?
This is what i have so far:
Main file
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
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;
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)}
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);
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
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
The "book" appears to be in Portuguese which is more than difficult for me to comprehend....
ASKER
What do you mean? The book is in english. Plus, i already explained my problem in plain english.
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.
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.
ASKER
@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 :(
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
So you just need an if statement something like
if t > T
f = 0
else
f = f(t+1, floor(....
end
ASKER
@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
Function
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
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;
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?
kq=prop(q,y)
So when you got y = 6 - Cost(kant,10); y must be 0?
ASKER
@TommySzalapski Sorry, i didn't understand. I'm way past my melting point with this one :(
Explain what this line is for:
y = 6 - Cost(kant,10);
Any time Cost(kant, 10) is 6 or more, you will see issues.
y = 6 - Cost(kant,10);
Any time Cost(kant, 10) is 6 or more, you will see issues.
ASKER
@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 :(
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 :(
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I have the code running but am still hoping to confirm the objective statement re "is x a single number or 10 numbers?"
ASKER
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.
Thanks.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.