How to solve b≤Cx≤z with linear programming?
1 view (last 30 days)
Show older comments
Hello,
I'd like to calculate the following. For example:
There is a Matrix C m*n(5x4), vector b (b1,b2,b3,b4,b5) and vector z (z1,z2,z3,z4,z5), their values are given. I need to find such vector x (x1,x2,x3,x4,x5) that:
*my calculation:
b1<= Cm1n1*x1 + Cm2n1*x2 + Cm3n1*x3 + Cm4n1*x4 + Cm5n1*x5 < z1
.
.
.
b5<= Cm1n5*x1 + Cm2n5*x2 + Cm3n5*x3 + Cm4n5*x4 + Cm5n5*x5 < z5
Also, the vector x must have positive values.
I was adviced to resolve it by linear programmning. So I have had a look at LINPROG. As I was not sure what to put instead of "f" (Linear objective function vector) I set it to a vector of 0's as I also did that for vector of lower bounds.
x = linprog(f,C,b,[],[],lb)
The vector x which was calculated gave me positive values. Then I have used these x-values for *my calculation (see above please), which gave me results which are far bellow the vector b values.
Does anybody know what I am doing wrong? How to get x above d but below z?
Many thanks. LZ
6 Comments
Sean de Wolski
on 9 Apr 2012
Your question isn't clear to me. If you look at the doc for linsolve, you'll see that you're trying to find an optimal x that minimizes f'x. If f is all zeros, you can pick any x you want that meets your above constraints and it will lie on the hyperplane defining the minimum of f'x, i.e. zeros in all n-dimensions.
Answers (2)
Teja Muppirala
on 10 Apr 2012
You can solve this with LINPROG, but I think you need help in understanding how to formulate your constraints properly.
Constraint 1: C*x < z
This is fine as it is.
Constraint 2: C*x > b
Multiply this equation by -1 and rewrite it as
-C*x < -b
Now, we will need to combine both of these constraints into a single matrix.
[C; -C]*x < [z; -b]
This inequality is saying the exact same thing as the two inequalities above. It is just using matrix multiplication. Now LINPROG can accept the [C; -C] and [z; -b] as its inputs to define the constraint.
As a concrete example:
C =[ -1.3617 1.0655 0.0909 -0.5503
-0.6411 -0.2132 -2.1390 0.9111
-0.0097 -0.2970 0.2654 -0.7814
0.5465 0.4400 -0.2322 -0.7191
0.3432 -0.4943 0.4786 -0.3528];
b = [-1; -2; -3; -4; -5];
z = [2; 3; 4; 5; 6];
lowerbound_on_x = zeros(size(C,2),1);
f = zeros(size(C,2),1);
x = linprog(f,[-C;C],[-b;z],[],[],lowerbound_on_x)
This gives me:
x =
1.9958
4.2650
0.3293
2.3048
You can then confirm C*x
ans =
0.5883
-0.7932
-2.9996
1.2334
-2.0788
This satisfies b < C*x < z and x > 0
Sean de Wolski
on 9 Apr 2012
%Cx<z
%Cx>b
C = rand(5);
b = (1:5)';
z = (11:15)';
x = [C;C]\[z; b]
constraintsMet = all(C*x>=b)&&all(C*x<z)
Maybe?
See Also
Categories
Find more on Linear Least Squares in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!