Flow Network - Linear Optimization

[snozzla]

Homework Statement

I am doing an assignment in my Linear Algebra class. But I don't know how I will go about solving this problem.

So the problem is a network of water pipes. I start with a matrix and I get the solution to the system from the RREF matrix. All the flow directions are set, so the variables(x1,x2,x3,x4,x5,x6) cannot be negative because I cannot have "negative flow".

The problem text says that since all the x-variables have to be non negative I should get 6 inequalities (x1 bigger than or equal to 0) and (x6 bigger than or equal to 0)
but I don't see how?

I also have to minimize flow between two nodes, how do you go forward doing that?

What method gets me from matrix system of equations to inequalities?
Nothing about this in my book and I have spent countless of hours on the net, and still I can't figure this out.

Homework Equations

The RREF matrix:

1 0 0 0 -1 -1 -20
0 1 0 0 1 1 50
0 0 1 0 0 1 40
0 0 0 1 1 0 10
0 0 0 0 0 0 0

The Attempt at a Solution

I get:

x1= -20 + x5 + x6
x2 = 50 - x5 -x6
x3 = 40 - x6
x4 = 10 - x5
x5 = free variable
x6 = free variable

No inequalities here..

 

[Ray Vickson]

Homework Statement

I am doing an assignment in my Linear Algebra class. But I don't know how I will go about solving this problem.

So the problem is a network of water pipes. I start with a matrix and I get the solution to the system from the RREF matrix. All the flow directions are set, so the variables(x1,x2,x3,x4,x5,x6) cannot be negative because I cannot have "negative flow".

The problem text says that since all the x-variables have to be non negative I should get 6 inequalities (x1 bigger than or equal to 0) and (x6 bigger than or equal to 0)
but I don't see how?

I also have to minimize flow between two nodes, how do you go forward doing that?

What method gets me from matrix system of equations to inequalities?
Nothing about this in my book and I have spent countless of hours on the net, and still I can't figure this out.

Homework Equations

The RREF matrix:

1 0 0 0 -1 -1 -20
0 1 0 0 1 1 50
0 0 1 0 0 1 40
0 0 0 1 1 0 10
0 0 0 0 0 0 0

The Attempt at a Solution

I get:

x1= -20 + x5 + x6
x2 = 50 - x5 -x6
x3 = 40 - x6
x4 = 10 - x5
x5 = free variable
x6 = free variable

No inequalities here..

Imagine submitting this problem to a computer package for solving. The computer does not "know" what x1, x2,... are, and does not "know" they cannot be < 0. You need to ensure that the computer does not give you a solution with some xi < 0. In problems of this type, non-negativity constraints are *crucial*: the set of physically feasible points (x1,x2,...,x6) is a convex polyhedron, but if you drop the non-negativity constraints it is a subspace. Geometrically, these are very different.

RGV

 

[LaissezDairy]

That constraint typically isn't entered into the matrix for LP, the typical LP Min problem goes:

Minimize $\overline{c}^T \overline{x}$

Subject to $\overline{A} \overline{x} \geq \overline{b}$

$x _1 ... x_n \geq 0$

Have you tried constructing the Dual of the problem?

Also which two nodes are you trying to minimize flow between?

 

[snozzla]

Here is the pipe flow network.

[PLAIN]http://img36.imageshack.us/img36/8287/pipes.png

After I have found the 6 inequalities, the assignment asks me to write them as inequalities for x5,x6 or x5 + x6.
Then to minimize flow between D and E.

I have to use Linear Programming to find the inequalities? We have only had 2 lectures and nothing about LP so far, only some matrices and started touching vectors.

Minimize c−Tx−
Subject to A−−x−≥b−
x1...xn≥0
Have you tried constructing the Dual of the problem?

I sadly have no idea what this means. Trying to read up on LP on the net because there is nothing in it in my book.

All constraints can't be that all Xi's ≥ 0? I have understood that they must be equal or greater than 0 because we are not allowed to have 'negative flow', as in in the opposite direction. But there has to be some more? I don't see how the equations I have found will lead me to those 6 inequalities asked for.

 

[LaissezDairy]

Oh, I think you may be overthinking it (and so was I) - you know each inequality, right? (each variable is greater than zero). You know how to express x1 through x4 in terms of x5 and x6, right?

If x1 is greater than zero, and x1 equals -20 + x5 + x6, what does it mean about the quantity -20 + x5 + x6 ?

 

[snozzla]

x1= -20 + x5 + x6
x2 = 50 - x5 -x6
x3 = 40 - x6
x4 = 10 - x5
x5 = free variable
x6 = free variable

-20 + x5 + x6 ≥ 0
50 - x5 - x6 ≥ 0
40 - x6 ≥ 0
10 - x5 ≥ 0
x5 ≥ 0
x6 ≥ 0

Do you mean this?

 

[LaissezDairy]

Yes. Those are your six inequalities. Hint: for the next part, it will be helpful to solve each equality for one variable (because usually the easiest way to do an optimization problem with two variables is by graphing the inequalities)

 

[snozzla]

Thanks, Hopefully I will be able to solve the rest ;)