matlab - 动态规划 - 递归实现

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 年，以实现利润最大化。

future yield 按每年 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(以千为单位的值)的情况进行计算。这与 book 中描述为“贴现利润问题”的问题相同。

如果您能给我任何帮助，我们将不胜感激。

编辑 1: 我真的被困在这里了伙计们。如果你能帮我用 Java 实现这个，我会尝试将它移植到 Matlab。

编辑 2: 我将代码编辑为最​​新版本。现在我得到了

"Maximum recursion limit of 500 reached."

你能帮帮我吗？

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

编辑 4: 代码已更新。现在我得到了

Attempted to access prop(2,0); index must be a positive integer or logical.

Error in Main (line 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) 对 vcost 进行索引，而是直接使用 fishes 进行索引。
• 一步预分配选项/包装箱

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