动态编程 - 递归实现

Question

首先,我想干净利落地说下面的问题是针对学校的,所以不要对我太苛刻:)

我在使用递归算法(这是一个要求)在matlab中建模优化问题时遇到了一些问题.

问题的定义是:

考虑到10年的时间窗口确定每年要捕获的鱼的数量,知道湖中目前有10000条鱼,第1年,鱼的增长率是每年年初湖中存在的鱼的数量+ 20%.

设x是要捕获的鱼的数量,每条鱼的价格是5美元以及捕鱼的成本:

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

决定每年捕捞鱼类的数量,为期10年,以便最大限度地提高利润.

未来收益的折旧率为0.2 /年,这意味着第1年的收入为1美元,与第2年的0.8美元相同,依此类推.

我目前定义了以下目标函数:

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)}

我将如何在matlab中实现这一点？

这是我到目前为止:

主文件

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);


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 = RecursiveProfit(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 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;

这仅计算年份为10且b = 10(数千的值)的情况.这是同一个poblem在书中描述的"折扣利润问题"

您将给予我任何帮助将不胜感激.

编辑1:我真的被困在这里的人.如果你可以帮我实现这个,比如Java,我会尝试将它移植到Matlab.

编辑2:我将代码编辑为最​​新版本.现在我来了

"达到最大递归限制500."

你能帮助我吗？

编辑3:我设法让它工作,但它只返回0.

编辑4:代码更新.现在我来了

尝试访问prop(2,0); index必须是正整数或逻辑.

主要错误(第66行)kq = prop(q,y)

Answer 1

function gofishing(numoffishes,years)

growFactor=1.2;
%index shift, index 1 : 0 fishes
earn{1}=-inf(numoffishes+1,1);
%index shift, index 1 : 0 fishes
earn{1}(numoffishes+1)=0;
%previous: backpointer to find path of solution.
previous{1}=nan;

%index shift, index 1 : 0 fishes
vcosts = zeros(1,ceil(numoffishes*growFactor^years));

for idx=1:numel(vcosts)
    vcosts(idx)=costs(idx-1);
end

for step = 1:years*2
    fprintf('step %d\n',step);
    if mod(step,2)==1;
        %do fish grow step
        earn{step+1}=-inf(floor(numel(earn{step})*1.2)-1,1);
        previous{step+1}=nan(floor(numel(earn{step})*1.2)-1,1);
        for fishes=0:numel(earn{step})-1
            grownfishes=floor(fishes*1.2);
            earn{step+1}(grownfishes+1)=earn{step}(fishes+1);
            previous{step+1}(grownfishes+1)=fishes;
        end
    else
        %do fishing step
        earn{step+1}=-inf(size(earn{step}));
        previous{step+1}=nan(size(earn{step}));
        for fishes=0:numel(earn{step})-1
            if isinf(earn{step}(fishes+1))
                %earn is -inf, nothing to do
                continue;
            end
            possibleToFish=fishes:-1:0;
            %calculate earn for possible amounts to fish
            options=((vrevenue(possibleToFish)-vcosts(possibleToFish+1))*0.8^(step/2-1)+earn{step}(fishes+1))';
            %append -inf for not existing options
            options=[options;-Inf(numel(earn{step+1})-numel(options),1)];
            %found better option:
            better=earn{step+1}<options;
            earn{step+1}(better)=options(better);
            previous{step+1}(better)=fishes;
        end
    end
end
[~,fc]=max(earn{end});
fc=fc-1;
fprintf('ending with %d fishes and a earn of %d\n',fc,earn{end}(fc+1));
for step=(years*2):-1:2
    fc=previous{step}(fc+1);
    fprintf('fish count %d\n',fc');
end
end

function c=costs(x)
if (x<=5000)
    c=0.4*x + 100;
    return
end
if (x <= 10000)
    c=0.3*x + 5000;
    return
end
c=0.2*x + 10000;
return
end
function c=vrevenue(x)
c=5.*x;
end

再次阅读我的解决方案后，我有一些提高性能的想法：

• 不用向量（possibleToFish）对vcosts进行索引，而是直接使用fishes进行索引。
• 一步预分配选项/板条箱

对于 10000，它在可接受的时间内运行（大约 5 分钟），对于更大的数据，我建议更新。