linprog not giving all possible solutions

12 次查看（过去 30 天）
Wynand van Losenoord
评论： Alan Weiss 2021-2-16
I have the following issue with linear programming specific to biological data.
The specific method requires the maximization and minimization of all values subject to one specific value.
for example I have 5 variables v,w,x,y,z, I need to maximize v, and when this is performed what are the values of w,x,y,z. This is then repeated where w is maximized and the optimal values of v,x,y and z are required.
I have been using the linprog function to determine the value, the following constraints and equalities are set:
v + w + x + y = 100
v + y <= 60
w + x <= 40
x + z <= 30
v + x <= 70
w + y <= 30
y + z <= 20
v,w,x,y,z >= 0
v,w,x,y,z <=100
I'm assuming my problem is the setup of the objective function, currently what I have been trying with moderate success is to set the objective function specific to the value that needs to be optimized eg. 1v + 0w + 0x + 0y + 0z
my code is as follows:
f = [1;0;0;0;0]
A = [1 0 0 1 0; 0 1 1 0 0; 0 0 1 0 1; 1 0 1 0 0; 0 1 0 1 0; 0 0 0 1 1]
b = [60;40;30;70;30;20]
Aeq = [1 1 1 1 0]
beq = 100
lb =[0;0;0;0;0]
ub = [100;100;100;100;100]
When I perform the linprog I get the following values for when v is minimized:
>> x = linprog(f,A,b,Aeq,beq,lb,ub)
Optimal solution found.
x =
40
10
30
20
0
which according to my notes is correct, however when I maximize v:
>> x = linprog(-f,A,b,Aeq,beq,lb,ub)
Optimal solution found.
x =
60
30
10
0
0
where the expected solution should have been:
x =
60
30
10
0
20
This pattern repeats with every variable where either all the values are correct or the last value is incorect (usually displaying zero when it is not). Is this an issue as to how I approaced the objective function? Is there a better way to solve these types of issues? Any assistance would be greatly appreciated.

请先登录，再回答此问题。

采纳的回答

Alan Weiss
Alan Weiss 2021-2-16
编辑：Alan Weiss 2021-2-16
You might want to try the problem-based approach, which makes formulating and analyzing your problem easier.
v = optimvar('v','LowerBound',0,'UpperBound',100);
w = optimvar('w','LowerBound',0,'UpperBound',100);
x = optimvar('x','LowerBound',0,'UpperBound',100);
y = optimvar('y','LowerBound',0,'UpperBound',100);
z = optimvar('z','LowerBound',0,'UpperBound',100);
prob = optimproblem('Objective',v,'ObjectiveSense','maximize');
prob.Constraints.c1 = v + w + x + y == 100;
prob.Constraints.c2 = v + y <= 60;
prob.Constraints.c3 = w + x <= 40;
prob.Constraints.c4 = x + z <= 30;
prob.Constraints.c5 = v + x <= 70;
prob.Constraints.c6 = w + y <= 30;
prob.Constraints.c7 = y + z <= 20;
[sol,fval] = solve(prob)
Solving problem using linprog.
Optimal solution found.
sol =
struct with fields:
v: 60
w: 30
x: 10
y: 0
z: 0
fval =
60
You can tweak the objective slightly to get the solution you prefer.
prob.Objective = v + 1e-10*(w+x+y+z); % Prefer higher variable values
[sol,fval] = solve(prob)
Solving problem using linprog.
Optimal solution found.
sol =
struct with fields:
v: 60
w: 30
x: 10
y: 0
z: 20
fval =
60.0000
Using the problem-based approach you can easily change the objective sense and other problem attributes.
Alan Weiss
MATLAB mathematical toolbox documentation
  2 个评论
Wynand van Losenoord
Wynand van Losenoord 2021-2-16
This is perfect, thank you so much
Would you mind elaborating why the following:
prob.Objective = v + 1e-10*(w+x+y+z); % Prefer higher variable values
[sol,fval] = solve(prob)
prevents the 0 value from being reported?
Alan Weiss
Alan Weiss 2021-2-16
I changed the objectve function to increase slightly when any variables increase. Therefore, the maximum value, if nonunique, is attained at larger variable values. Your problem has a nonunique solution, so this slight change makes the reported solution nonzero where possible. The change is so slight that it does not affect the resulting objective value to display precision.
Alan Weiss
MATLAB mathematical toolbox documentation

请先登录，再进行评论。

更多回答（1 个）

green_ananas
green_ananas 2021-2-16
Hey,
Maybe you didn't copy the equations correctly. The way you stated it, z doesn't appear in the top equation. Therefore, as long as all constraints are met and x is maximum, the value of z doesn't matter and you just obtain one of all local solutions as expected.
  3 个评论
显示 1更早的评论
green_ananas
green_ananas 2021-2-16
Exactly, and as you can see, every value of is compatible with your constraints. If you wanted to obtain the maximum z of all solutions, you would need to reformulate your objective function which you are minimizing. The way it is formulated now, linprog only looks for the maximum value of v, and doesn't care about the other values as long as they don't violate the constraints.
Wynand van Losenoord
Wynand van Losenoord 2021-2-16
I understand, so the valaues are true, they are however not the maximum values for all. Basically what I want to achieve is to determine the maximum/minimum of the other variables if the variable in question was running at its maximum/minimum. I'm guessing there is no simple way to do this with the linprog function?

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by