フィルターのクリア

Solve as Optimization Problem in Matlab

9 ビュー (過去 30 日間)
Paul Safier
Paul Safier 2020 年 11 月 18 日
コメント済み: Paul Safier 2020 年 11 月 19 日
I want to solve this simple equation as an optimization problem in Matlab. I have tried linprog, fmincon and fminunc and all do not seem to get it done. It is trivial to solve with brute-force in a loop (as below) and with Excel's Solver, but I want to be able to use one of Matlab's optimization routines too.
Solve:
15*i + 16*j + 17*k = 121
i, j and k are integers.
With loops, the solution is trivial:
for i = 0:100
for j = 0:100
for k = 0:100
val = 15*i + 16*j + 17*k;
if val == 121
disp('here!')
i,j,k
end
end
end
end
The solution is i=7, j=1, k=0.
I want to solve as:
min 121 - 15*i - 16*j - 17*k
s.t. i,j,k are >=0 integers.
What is the appropriate formulation as a optimization problem in Matlab?
Thanks!

採用された回答

Ameer Hamza
Ameer Hamza 2020 年 11 月 18 日
編集済み: Ameer Hamza 2020 年 11 月 18 日
MATLAB have genetic algorithm ga() from the global optimization toolbox to solve such problems
f = @(x) 121 - 15*x(1) - 16*x(2) - 17*x(3);
sol = ga(@(x) f(x).^2, 3, [], [], [], [], [0 0 0], [], [], 1:3);
Result
>> sol
sol =
7 1 0
Of course, the problem has an infinite number of solutions. This is one of them
  8 件のコメント
Paul Safier
Paul Safier 2020 年 11 月 18 日
Thanks.
Ameer Hamza
Ameer Hamza 2020 年 11 月 18 日
編集済み: Ameer Hamza 2020 年 11 月 18 日
@John, I later realized my mistake of calling it a nonlinear problem. intlinprog() can also be used.

サインインしてコメントする。

その他の回答 (3 件)

Bruno Luong
Bruno Luong 2020 年 11 月 18 日
編集済み: Bruno Luong 2020 年 11 月 18 日
c=[15 16 17];
t = 121;
A = [ c -1;
-c -1];
b = [ t;
-t];
f = [zeros(length(c),1); 1];
LB = 0*f;
x = intlinprog(f, 1:size(f), A, b, [], [], LB, []);
x = round(x);
i = x(1)
j = x(2)
k = x(3)
  1 件のコメント
Paul Safier
Paul Safier 2020 年 11 月 18 日
This works as well! Thanks Bruno Luong!!

サインインしてコメントする。


Jon
Jon 2020 年 11 月 18 日
編集済み: Jon 2020 年 11 月 18 日
I think you can use the MILP mixed integer linear programming functionality if you have the optimization toolbox

John D'Errico
John D'Errico 2020 年 11 月 18 日
編集済み: John D'Errico 2020 年 11 月 18 日
In MATLAB, the solution is intlinprog. Of course, there may be multiple solutions. intlinprog does not give them, if any could exist. But there is no need for loops either, nor even to go out as far as 100.
Since we know
8*15
ans =
120
then we can limit the variables to be no larger than 8.
[x,y,z] = ndgrid(0:8,0:8,0:8);
ind = find(15*x + 16*y + 17*z == 121)
ind =
17
>> x(17)
ans =
7
>> y(17)
ans =
1
>> z(17)
ans =
0
So the only possible solution in positive integers is as found. Fast, efficient, and trivial to write. Sometimes brute force is the easiest thing. Would I have used intlinprog? Of course, as that is the obvious way to solve any problem of this class.
Had the problem been larger, perhaps to find a solution in integers to this?
137*x + 291*y + 313*z + 997*u + 1329*v + 237*w == 1 + 1e15
Now brute force will fail, because the search will push the search space out into numbers on the order of 1e13. And of course, even intlinprog might be at risk, due to the size of the right hand side, compared to the dynamic range of a double. This latter problem can now be solved more easily using number theory. How? Consider this...
(writing)
  5 件のコメント
Bruno Luong
Bruno Luong 2020 年 11 月 19 日
編集済み: Bruno Luong 2020 年 11 月 19 日
I remember I wrote some code based on GCD 12 years ago, and one can find here thank to mother Google.
This code list ALL positive integer solutions of the equation.
The (almost) same code are attached for reference.
Paul Safier
Paul Safier 2020 年 11 月 19 日
Thanks!

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeSolver Outputs and Iterative Display についてさらに検索

製品


リリース

R2020b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by