モンテカルロ法と通常の解の比較(非線形整数計画の解決)

モンテカルロほう
原文:http://blog.csdn.net/qq_34861102/article/details/77859530
ランダムサンプリングまたは統計シミュレーション法は,確率統計理論を指導とする非常に重要な数値計算方法である.
Matlabを用いて非線形整数計画を解く(モンテカルロ法)
モデル:

max z = x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5)

s.t. 

x1 + x2 + x3 + x4 + x5 <= 400
x1 + 2*x2 + 2*x3 + x4 + 6*x5 <= 800
2*x1 + x2 + 6*x3 <= 200
x3 + x4 + 5*x5 <= 200

0=< xi <= 99  , i = 1,2,3,4,5

Matlabコード:

function [f,g] = fun1(x)
f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5);
g(1)=sum(x)-400;
g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;
g(3)=2*x(1)+x(2)+6*x(3)-200;
g(4)=x(3)+x(4)+5*x(5)-200;

主関数:

rand('state',sum(clock));
p0=0;
tic
for i=1:10^7
    x=99*rand(5,1);
    x1=floor(x);
    x2=ceil(x);
    [f,g]=fun1(x1);
    if sum(g<=0)==4
        if p0<=f
            x0=x1;
            p0=f;
        end
    end
    [f,g]=fun1(x2);
    if sum(g<=0)==4
        if p0<=f
            x0=x2;
            p0=f;
        end
    end
end
x0, p0
toc

このような動作時間は11.68秒であり、実行結果は50297であり、その0.01%の数を採用した.
通常のMatlabは非線形計画を解く:

function ff = fun(x)
    ff = -(x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5));
end

tic
x0 = [50 99 0 99 20];
A = [1,1,1,1,1;1,2,2,1,6;2,1,6,0,0;0,0,1,1,5];
b = [400,800,200,200];
Aeq = [];
beq = [];
VLB = [0;0;0;0;0];
VUB = [99;99;99;99;99];
[x,fval] = fmincon(@fun,x0,A,b,Aeq,beq,VLB,VUB)
toc

通常のLingoは非線形整数計画を解く:

model:
sets:
row/1..4/:b;
col/1..5/:c1,c2,x;
link(row,col):a;
endsets
data:
c1=1,1,3,4,2;
c2=-8,-2,-3,-1,-2;
a=1 1 1 1 1
1 2 2 1 6
2 1 6 0 0
0 0 1 1 5;
b=400,800,200,200;
enddata
max=@sum(col:c1*x^2+c2*x);
@for(row(i):@sum(col(j):a(i,j)*x(j))@for(col:@gin(x));
@for(col:@bnd(0,x,99));
end

最適解:51568.00
ここでは簡単な例です.実際の状況は複雑で,実行可能時間内に解が得られない場合,モンテカルロ法を用いることが考えられ,モンテカルロ法の誤差度は低いことがわかる.