How can i solve for the maximum? (a little complex)

5 vues (au cours des 30 derniers jours)
mitch flori
mitch flori le 14 Nov 2020
Commenté : John D'Errico le 15 Nov 2020
So I think this is related to the Coin Change problem -
I have these objects with value(V) and cost (E) and they are as follows;
a) Va=9, Ea=7
b) Vb=5, Eb=4
c) Vc=3, Ec=3
d) Vd=1, Ed=1
I need a Quantity (N) of each (0-10), Such that; Na*Ea + Nb*Eb + Nc*Ec + Nd*Ed < 29
For the second part of this I have a variable I have defined as M which is N(V/E) - value per cost of each object multiplied by the quanitity of each object.
I want to maximise how much value i get from the equation Ma + Mb + Mc + Md;
or find all N (integers) for objects a,b,c,d to maximize 1.28Na + 1.2Nb + Nc + Nd
I honestly dont know where to begin. Thank you in advance!

Réponses (2)

John D'Errico
John D'Errico le 14 Nov 2020
Modifié(e) : John D'Errico le 14 Nov 2020
First, learn to use vectors and matrices. This is MATLAB. Naming all of your variables like that will lead to a huge headache as you go on. God forbid what your code would look like one day when you see a really difficult problem!
V = [9 5 3 1];
E = [7 4 3 1];
You want to solve for a vector N, also of length 4, such that the elements of N are integers that lie in the interval [0,10], AND dot(N,E) <= 29. There are infinitely many solutions to that, of course, so you want to solve for the vector that maximizes dot(N,V./E), and therefore minimizes dot(N,-V./E).
This is a basic and ideal problem for an integer linear programming code, thus intlinprog. (Optimization toolbox.) You need to use the minimization form, since intlinprog is a MINIMIZATION tool.
LB = [0 0 0 0]; % lower bounds
UB = [10 10 10 10]; % upper bounds
f = -V./E; % objective to minimize
intcon = [1 2 3 4]; % all elements must be integer
A = E; % dot(N,E) <= 29
b = 29;
[Nsol,fval,exitflag] = intlinprog(f,intcon,A,b,[],[],LB,UB)
LP: Optimal objective value is -16.333333. Heuristics: Found 1 solution using ZI round. Upper bound is -16.000000. Relative gap is 1.47%. Cut Generation: Applied 1 mir cut. Lower bound is -16.250000. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
Nsol = 4×1
0 1.0000 5.0000 10.0000
fval = -16.2500
exitflag = 1
As I said, not difficult. The objective was found, with a maximum of 16.25. You were making it seem complicated. What was dot(N,E)?
dot(Nsol,E)
ans = 29
So the inequality constraint is active, as were two of the bounds, since N(1) was 0 and N(4) was 10.
Admittedly, the problem is a trivial one to solve using brute force too. I'd not use nested loops for this, but just ndgrid. There are only 11^4 possible sets of numbers to check, at least for this problem. The problem is, tomorrow we will learn the real problem has 25 or 100 variables, with limits that go as high as 100. Then loops or any form of brute force will fail miserably. Regardless, intlinprog will still work without even breathing hard.
  4 commentaires
mitch flori
mitch flori le 15 Nov 2020
this is amazing.
Now what happens if we set the maximum number of d to 4? I need to learn how to do this myself
John D'Errico
John D'Errico le 15 Nov 2020
Ok. Then read the help for intlinprog.

Connectez-vous pour commenter.


Alan Stevens
Alan Stevens le 14 Nov 2020
Modifié(e) : Alan Stevens le 14 Nov 2020
Here is a brute force and ignorance method!
% Maximise Value = (9/7)*Na + (5/4)*Nb + Nc + Nd
% Subject to 7*Na + 4*Nb + 3*Nc + Nd < 29
Valuemax = 0;
for Na = 0:4 % 4 = floor(29/7)
Naterm = 7*Na;
for Nb = 0:7 % 7 = floor(29/4)
Nbterm = 4*Nb;
for Nc = 0:9 % 9 = floor(29/3)
Ncterm = 3*Nc;
for Nd = 0:10
if Naterm + Nbterm + Ncterm + Nd < 29
Value = (9/7)*Na + (5/4)*Nb + Nc + Nd;
if Value>Valuemax
Valuemax = Value;
Nav = Na; Nbv = Nb; Ncv = Nc; Ndv = Nd;
end
end
end % Nd loop
end % Nc loop
end % Nb loop
end % Na loop
disp([Nav Nbv Ncv Ndv 7*Nav+4*Nbv+3*Ncv+Ndv])
disp(Valuemax)

Catégories

En savoir plus sur Get Started with Optimization Toolbox dans Help Center et File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by