1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Equations

  1. Mar 20, 2008 #1
    1. The problem statement, all variables and given/known data
    The figure attached shows a network of one way streets. On a particular day the traffic flow was measured at each of the intersections a b c and d. The numbers in the figure represent the average number of vehicles per minute through the four intersections.

    A) Set up and solve a system of linear equations to find x1,x2,x3, and x4
    B) Street AD is temporarily closed due to an accident. What will be the average traffic flow on the other streets?


    2. Relevant equations



    3. The attempt at a solution

    I reached the equations;
    50=x1+x2
    40=x2+x4
    40=x3+x4
    50=x1+x3

    Which gave me x1=0, x2=50, x3=50,x4=-10

    However... I think I did this incorrectly.
     

    Attached Files:

    Last edited: Mar 20, 2008
  2. jcsd
  3. Mar 20, 2008 #2
    What kind of class is this for? Linear algebra?

    This is a somewhat tricky problem. It is similar to an electrical network problem.

    Part A.
    All you have to do is set it up so it looks like a matrix:

    [ 1*x1 + 1*x2 + 0*x3 + 0*x4 ]......[50]
    [ 0*x1 + 1*x2 + 0*x3 + 1*x4 ]..=..[40]
    [ 0*x1 + 0*x2 + 1*x3 + 1*x4 ]......[40]
    [ 1*x1 + 0*x2 + 1*x3 + 0*x4 ]......[50]

    which becomes:

    [ 1 1 0 0 ]......[x1]....[50]
    [ 0 1 0 1 ]..*..[x2].=.[40]
    [ 0 0 1 1 ]......[x3]....[40]
    [ 1 0 1 0 ]......[x4]....[50]

    Having done this, if you attempt to solve it with a calculator that can do matrix arithmetic, you may get an error because the 4x4 matrix is singular; it has rank 3.

    But, the augmented matrix also has rank 3, so the system has an infinite number of solutions.

    The solution you got satisfies the system, but there are other solutions. Do you know how to find them? Will any solution satisfy your instructor, or do you need to show how to find them all?

    Part B.

    The equations become:

    50=x1+0*x2=x1
    40=0*x2+x4=x4
    40=x3+x4
    50=x1+x3

    Right away you can see that x1=50 and x4=40.
     
  4. Mar 21, 2008 #3
    I'm glad you got the same matrix as me for this problem.
    This problem is for math108 (1st year Uni).

    The question just says to set up and solve a system of linear equations to find the variables...
    I'm assuming by that I don't have to mention there is an infinite number of solutions?

    Thanks alot for your help
     
  5. Mar 21, 2008 #4
    You know, in looking over your question again, I notice that the original statement of the problem says that the streets are one way. So your solution which has x4 = -10, while mathematically correct, has the cars going the wrong way on a one way street!

    This probably won't be an acceptable solution!

    Note that the solution to part B, x1 = 50, x2 = 0, x3 = 0, x4=40 is also a solution to part A.

    But there is a solution to part A which has less traffic on all the roads. You might get extra credit if you point out that there are an infinite number of solutions to part A, although the smallest solution is non-integer. A real world solution has to be in integers because you can't have a fraction of a car on the road, can you?
     
  6. Mar 21, 2008 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    … only solve what the question asks for …

    Hi Bob! :smile:

    Read the question carefully …

    A) only asks you to set up the equations.

    It doesn't ask you to solve them, does it?

    So when you've answered A) … go straight on to B)!

    Let y1 y3 and y4 be the new figures when street AD is closed.

    From A), what are y1 y3 and y4 in terms of x1 x2 x3 and x4 … ? :smile:
     
  7. Mar 21, 2008 #6
    A) Set up and SOLVE a system of linear equations....

    Looks to me like it says solve them.
     
  8. Mar 21, 2008 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    oops!

    Oh dear … I need glasses … :redface:

    In that case, my advice is the exact opposite … don't do what the question says … you can't solve A) completely, so go straight on to B)! :smile:

    Let y1 y3 and y4 etc …

    Thanks, Electrician!
     
  9. Mar 21, 2008 #8
    Bob Ho - I don't get the same system as you.

    I get the following:

    A) 30 + 20 - X1 - X2 = 0

    B) X1 + X3 - 15 - 35 = 0

    C) 25 + 15 - X3 - X4 = 0

    D) X2 + X4 - 20 - 20 = 0

    Which yieds

    1 1 0 0 = 50
    1 0 1 0 = 50
    0 0 1 1 = 40
    0 1 0 1 = 40

    Which still results in an indeteriminate solution (?)
     
  10. Mar 21, 2008 #9
    If you perform an elementary row operation--exchange rows 2 and 4--on your system, you will have his system.
     
  11. Mar 21, 2008 #10
    Man! - I thought I gave that a good looked just for that - I don't know how I missed it. Maybe age <groan>
     
  12. Mar 21, 2008 #11
    You are right, thanks alot! I will change my working for that question and definitely include there are infinite solutions.

    Unfortunately, now i'm stuck on a further subquestion which relates to the same diagram.

    Q.) What are the maximum and minimum possible traffic flows on each street?

    I assumed you can make every entering car turn down the side streets, so I worked out a maximum cars for street AD=90, AB=90, CB=90, and CD=90 also. Feel free to prove me wrong, as I most likely am as the numbers represent average numbers of vehicles per minute.

    I put the minimum as just 0.....
     
    Last edited: Mar 21, 2008
  13. Mar 22, 2008 #12
    I'm surprised that you're getting questions like this in a first course. The answer requires more sophistication than I would expect.

    Let the problem be formulated as a matrix problem:

    [ 1 1 0 0 ]......[x1]....[50]
    [ 0 1 0 1 ]..*..[x2].=.[40]
    [ 0 0 1 1 ]......[x3]....[40]
    [ 1 0 1 0 ]......[x4]....[50]

    this can be written as:

    A * x = B

    The system has an infinite number of solutions which are 4 element vectors:

    [ x1 x2 x3 x4 ]

    Vectors have a Euclidean length which is the square root of the sum of the squares of the elements. One of the infinite solutions has a minimum Euclidean length; it is:

    [ x1 x2 x3 x4 ] = [ 27.5 22.5 22.5 17.5 ]

    You can test any proposed solution by premultiplying the alleged solution vector by the A matrix; if you get the B vector (column matrix), then you have a solution.

    Consider the vector [ -.5 .5 .5 -.5 ]. If you premultiply this vector by the A matrix you will get [ 0 0 0 0 ]; this means that [ -.5 .5 .5 -.5 ] is in the null space of A. Any multiple of this null space vector can be added to a good solution vector to get another solution vector.

    The infinite number of solutions can thus be expressed as:

    [ x1 x2 x3 x4 ] = [ 27.5 22.5 22.5 17.5 ] + n * [ -.5 .5 .5 -.5 ]

    where n can be any number. You can see why; any multiple of [ -.5 .5 .5 -.5 ] when premultiplied by A simply gives [ 0 0 0 0 ] which when added to the product of A times any good solution vector doesn't change anything.

    Now, look carefully at:

    [ x1 x2 x3 x4 ] = [ 27.5 22.5 22.5 17.5 ] + n * [ -.5 .5 .5 -.5 ]

    I you add some multiple of [ -.5 .5 .5 -.5 ] to a good solution vector, you will be adding a negative quantity to x1 and x4, and a positive quantity to x2 and x3. Since the streets are one way, we can't let any of the x's become negative. If we let n = 35, and evaluate the expression above, we will get:

    [ x1 x2 x3 x4 ] = [ 10 40 40 0 ]

    which is a solution of the original system. We can't use a value of n larger than 35 because the traffic on x4 would become negative, and that isn't allowed on one way streets.

    Now let n = -45 and evaluate the above expression. we get:

    [ x1 x2 x3 x4 ] = [ 50 0 0 40 ]

    also a valid solution of the original system. We can't let n be more negative than -45 because x2 and x3 would become negative which isn't allowed on the one way streets.

    I'm assuming that when you are asked:

    Q.) What are the maximum and minimum possible traffic flows on each street?

    what is meant is "over all valid solutions, what are the min and max flows?"

    No valid solution allows for flows of 90 on any one street, because to do so would require a negative value for the flow on some other street. Such a solution can happen mathematically, but would violate the one way restriction.

    So, it appears that the minimums are:

    x1 = 10, x2 = 0, x3 = 0, x4 =0

    and the maximums are:

    x1 = 50, x2 = 40, x3 = 40, x4 = 40

    I hope you see why x1 can never be less than 10 in a valid solution. It's because that would require some other flow to be negative which is not allowed.
     
  14. Mar 22, 2008 #13

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No it doesn't!

    It's really easy! :smile:

    Bob Ho, your original equations were correct:
    Then just let y1 y3 and y4 be the new figures when street AD is closed.

    From the four equations above, what are y1 y3 and y4 in terms of x1 x2 x3 and x4 … ? :smile:

    (Alternatively, just look at the diagram with AD rubbed out … :redface:)
     
  15. Mar 22, 2008 #14
    tiny-tim, you seem to be referring to part B) in Bob Ho's original post, but he has added a third question. That is what I was responding to .
     
  16. Mar 22, 2008 #15

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Ah! :redface: … though bold would have helped …

    Sorry … but it's still really easy.

    From equations 2 and 4:
    x2 = x3
    and therefore:
    x1 = x4 + 10.​
    And also:
    x1 + x2 = 50,
    x4 + x2 = 40.​
    And, of course
    x1 x2 x3 and x4 are all ≥ 0.
    These are the only constraints.

    The first equation imposes no max or min.

    The second equation imposes only x1 ≥ 10.

    The third imposes x1 and x2 ≤ 50.

    The fourth x4 and x2 ≤ 40.

    So, combining them, and taking the lesser of the two maxima for x2:
    10 ≤ x1 ≤ 50, 0 ≤x2 = x3 ≤ 40, 0 ≤x4 ≤ 40. :smile:
     
  17. Mar 22, 2008 #16
    Assuming that your numbering of the equations given by Bob Ho in his original post is:

    Equation 1: 50=x1+x2
    Equation 2: 40=x2+x4
    Equation 3: 40=x3+x4
    Equation 4: 50=x1+x3

    How does it follow from equations 2 and 4 that x2 = x3?

    It seems to me that the most you can say from those two equations is that x2=40-x4 and x3=50-x1, not that x2=x3.

    And without x2=x3 you can't conclude that x1=x4+10, etc.
     
    Last edited: Mar 22, 2008
  18. Mar 22, 2008 #17

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    … to prove x2 = x3 …

    Hi Electrician! :smile:
    Equation 2: 40=x2+x4
    Equation 3: 40=x3+x4

    :smile: subtracting: x2 - x3 = 0. :smile:
     
  19. Mar 22, 2008 #18
    Or you could use equations 1 and 4 to obtain the same result.

    But if you'll look at your post again, you'll see that you said to use equations 2 and 4, from which it does NOT follow that x2=x3.

    You then said:

    "and therefore:
    x1=x4+10"

    as though it followed from x2=x3 without explaining that THEN is the time to use equations 2 and 4, substituting x2=x3 into one of them. Or you could have explained that the result x1=x4+10 can be obtained from equations 1 and 2 together, or 3 and 4 together.

    But using only equations 2 and 4 (or 1 and 3) together gets you nothing.

    You got the correct final answer, but the beginning stages of your exposition were not clear and complete.

    In one of your earlier posts, you said:

    "In that case, my advice is the exact opposite … don't do what the question says … you can't solve A) completely, so go straight on to B)!"

    This isn't true. I gave the complete solution in my post (#12) about the third question, and my comment about the level of sophistication was mostly directed at part A). I wanted to show that if part A) were completely solved, the other questions could be answered using that result.

    Part A) can be solved with Gaussian elimination, finding a free variable and then back substituting, with the free variable taking on any value thus giving all the infinite solutions. But the concept of adding a multiple of a vector in the null space causing no change in the solution is powerful and elegant, and worth demonstrating.
     
  20. Mar 22, 2008 #19

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    … plain and simple cooking …

    hmm … my main object was to help the OP by showing him a very unsophisticated method which would still impress the examiners. :smile:

    So which method would you recommend to Bob Ho …
    your sophisticated method in post #12, with its matrix, Euclidean lengths, and Gaussian elimination,
    or my unsophisticated one (with the lines renumbered, and adding "there are 41 solutions, one for each value of x2 = x3 from 0 to 40, for each of which, x1 = 50 - x2, x4 = 40 - x2") in post#15?
     
  21. Mar 23, 2008 #20
    "...which method would you recommend to Bob Ho.."

    I would recommend any correct exposition rather than an incorrect one. And, of course, a corrected version of post #15 would be acceptable.

    However much the examiners might be impressed by any solution to question 3, they definitely wouldn't be impressed if the OP took your advice from post #7:

    "my advice is the exact opposite … don't do what the question says … you can't solve A) completely, so go straight on to B)!"

    Apparently you've changed your mind about this.

    I don't think your method is "very unsophisticated". If it were, you wouldn't have been saying in post #7 "you can't solve A)" and then taking until post #19 (making several careless errors along the way) to provide a solution to part A). Your "method" is, in fact, an elimination method, equivalent to gaussian elimination; it's just not organized in a systematic way.

    When you say "...with the lines renumbered..." are you acknowledging that the initial part of your exposition in post #15 was incorrect? The examiners wouldn't have been very impressed if he had turned that in, would they?

    I don't know exactly what the content of the OP's course is, but I suspect the examiners might be more impressed by a knowledge of methods that will work with any linear system rather than an ad hoc method that works with one particular system, or a few such.

    Gaussian elimination is such a general method and probably one of the topics he's been studying, and a demonstrated knowledge of it is probably what the examiners are looking for.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?