# How to solve b≤Cx≤z with linear programming?

Asked by Zdenek on 9 Apr 2012
Latest activity Commented on by Zdenek on 10 Apr 2012

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

Zdenek on 9 Apr 2012

So, to what number shall I set it? If it was possible, I would like to omit this f.

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.

Zdenek on 9 Apr 2012

Well, when you look at the data I have: Matrix C, vector b, and vector z, what would be the best function for me to find vector x, such that:

b1<= Cm1n1*x1 + Cm2n1*x2 + Cm3n1*x3 + Cm4n1*x4 + Cm5n1*x5 < z1
.
.
.
b5<= Cm1n5*x1 + Cm2n5*x2 + Cm3n5*x3 + Cm4n5*x4 + Cm5n5*x5 < z5

Do you have an idea please?
Many thanks
z

## Products

No products are associated with this question.

## 2 Answers

Answer by 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

## 2 Comments

Zdenek on 10 Apr 2012

Hello, thank you very much for your response. I have ran the code with a larger dataset multiple times with different settings, but I am having some issues.
The smaller "z" is set the higher "Cx" is calculated it implies
the smaller "z" is set the more "b" values is reached, but there are always some "Cx" values which are below "b" values. I thought that if "z" is sufficiently high, every "Cx" would be above "b" but it obviously is not the case. Well I am getting hopeless.Any ideas? Many thanks.z

Zdenek on 10 Apr 2012

Well, I have mixed your code with the one from Sean de Wolski so now I am having:
x = linprog(f,[C;-C],[z;-b],[],[],lowerbound_on_x)
and I am having pretty results. I will play a bit more with it and come back.

Answer by 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?

## 1 Comment

Zdenek on 9 Apr 2012

Alright, now I need to figure out, how to make all x positive. Also, I had a look at your profile and I see you are one of the few magician men in MATLAB ;-). So could you please explain me why in:
x = [C;C]\[z; b] are C;C and z;b separated with semicolon and why are there two of them? In what relation they are to each other? Does it mean the first C gets divided by z and then also by b, the same valid for second C? Or first C is divided by z and second C is divided by b? And then what I do with its results? And how do I get those x positive? :-)
Thank you very much for your time. I am just a begging beginer :-}}

Contact us