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

Question

Zdenek 2012-4-9

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/34950-how-to-solve-b-cx-z-with-linear-programming

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 个评论
显示 4更早的评论隐藏 4更早的评论

Zdenek 2012-4-9

Hello, thank you for response. Actually, I am testing it on a 40x13 Matrix which does not fit here, so I reduced it to 40x7. Here it goes:

Matrix C

3.3845 1.5 5.94 9.8239 14.88 1.46 11.59

0.0009 0.0003 0.0009 0.0006 0.0018 0.0002 0

0.0007 0.0021 0.0125 0.0046 0.005 0.0016 0.0061

0.014 0.029 0 0.0527 0 0.039 0.093

0.1804 0.088 0.008 0.5049 0.015 0.082 0.665

0.0257 8.16 2.08 0 2.14 0 1.99

0 0 0.0175 0 0.0024 0 0

0.0011 0.0055 0.018 0.0055 0.0062 0.027 0.04

0.1847 0.132 0.003 0.0388 0 0 0

0.0006 0.0004 0.0007 0.0022 0.0004 0 0

0.0006 0.0003 0.0045 0.0006 0.0033 0.0034 0.0006

0.0206 0.011 0.0305 0.0053 0.0794 0.0025 0.0303

0.0037 0.0028 0.016 0.0043 0.0053 0 0.007

0.002 0.0012 0.0012 0.0015 0.0009 0.002 0.0017

0.0046 0.034 0.25 0 0.015 0 0.01

0.3574 0.63 0.21 0.1514 0.07 0 0.14

0 0 0.02 0 0.016 0 0

0.2699 0.0701 0 0 0 0 0.01

0.0899 0.246 0.4 0.0892 11.8 3.25 0.675

0.0006 0.0004 0.0007 0.0014 0.0003 0 0.0027

0.0068 0.008 0.0047 0.0006 0.003 0 0.8

0.2687 0.03 0.21 0.2259 0.138 0.1 0.034

0.0113 0.0024 0.02 0.006 0.0082 0.04 0.06

0.2469 0.096 0.13 0.2465 0.44 0 0.41

0.0024 0.0036 0.0005 0.0077 0.0006 0 0.0024

0.5532 0.331 2.1 0.857 9.3 0 0.657

4.1092 2.86 1.3 1.4749 0.92 0 10.26

0.0028 0.001 0.233 0.0095 0.11 0 0.022

5.5183 0.66 1.4 4.8095 9.98 0 0.21

0.003 0.0019 0.014 0.0088 0.0275 0 0.002

0.019 0.007 0.126 0.0647 0.336 0.018 0.029

0.7018 0.2 7.5 1.5144 18 0.54 0.79

1.0883 0.26 11 3.6214 31 0.76 1.4

1.0872 0.24 9.9 1.3827 27 0.73 1.2

0.4145 0.07 7 0.7243 10.7 0.22 0.2

1.1282 0.27 12.7 4.1481 35 0.72 1.15

0.643 0.18 6 1.7778 12 0.48 0.65

0.2865 0.06 1.8 0.7243 4.6 0.15 0.14

1.0865 0.3 9.5 2.107 23 0.87 1.2

0.3363 0.08 3.2 0.9218 9.5 0.27 0.44

vector b:

9356.77980000000

1.60000000000000

17

38

130

900

5

15

120

1.20000000000000

1.30000000000000

16

5

1.30000000000000

30

400

2.40000000000000

125

1000

0.900000000000000

35

150

48.9600000000000

420

2.30000000000000

700

4700

55

1500

11

104.800000000000

2489

5502

4978

2489

4323

2620

655

3144

1834

f:

0

Thanks a lot for your help.

z

Sean de Wolski 2012-4-9

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 2012-4-9

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

请先登录，再进行评论。

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

Answer 1

Teja Muppirala 2012-4-10

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/34950-how-to-solve-b-cx-z-with-linear-programming#answer_43884

在 MATLAB Online 中打开

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 =

You can then confirm C*x

ans =

This satisfies b < C*x < z and x > 0

2 个评论
显示无隐藏无

Zdenek 2012-4-10

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 2012-4-10

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 2

Sean de Wolski 2012-4-9

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/34950-how-to-solve-b-cx-z-with-linear-programming#answer_43854

在 MATLAB Online 中打开

%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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Zdenek 2012-4-9

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 :-}}

请先登录，再进行评论。