Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Flow Network - Linear Optimization

  1. Aug 25, 2011 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant 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

    3. 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..
  2. jcsd
  3. Aug 25, 2011 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.

  4. Aug 25, 2011 #3
    That constraint typically isn't entered into the matrix for LP, the typical LP Min problem goes:

    Minimize [itex] \overline{c}^T \overline{x} [/itex]

    Subject to [itex] \overline{A} \overline{x} \geq \overline{b} [/itex]

    [itex]x _1 ... x_n \geq 0 [/itex]

    Have you tried constructing the Dual of the problem?

    Also which two nodes are you trying to minimize flow between?
  5. Aug 25, 2011 #4
    Here is the pipe flow network.

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

    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−
    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.
    Last edited by a moderator: May 5, 2017
  6. Aug 25, 2011 #5
    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 ?
  7. Aug 25, 2011 #6
    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?
  8. Aug 25, 2011 #7
    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)
  9. Aug 25, 2011 #8
    Thanks, Hopefully I will be able to solve the rest ;)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook