Solving Linear Equations Homework - x1, x2, x3, x4

[Bob Ho]

Homework Statement

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?

Homework Equations

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.

 

[The Electrician]

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.

 

[Bob Ho]

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 a lot for your help

 

[The Electrician]

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?

 

[tiny-tim]

… only solve what the question asks for …

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?

Hi Bob!

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 … ?

 

[The Electrician]

A) Set up and SOLVE a system of linear equations...

Looks to me like it says solve them.

 

[tiny-tim]

oops!

A) Set up and SOLVE a system of linear equations...

Looks to me like it says solve them.

Oh dear … I need glasses …

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)!

Let y1 y3 and y4 etc …

Thanks, Electrician!

 

[TheoMcCloskey]

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 (?)

 

[The Electrician]

If you perform an elementary row operation--exchange rows 2 and 4--on your system, you will have his system.

 

[TheoMcCloskey]

Man! - I thought I gave that a good looked just for that - I don't know how I missed it. Maybe age <groan>

 

[Bob Ho]

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?

You are right, thanks a lot! 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...

 

[The Electrician]

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 anyone 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.

 

[tiny-tim]

I'm surprised that you're getting questions like this in a first course. The answer requires more sophistication than I would expect.

No it doesn't!

It's really easy!

Bob Ho, your original equations were correct:

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

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 … ?

(Alternatively, just look at the diagram with AD rubbed out … )

 

[The Electrician]

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 .

 

[tiny-tim]

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 .

Ah! … 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. ​

 

[The Electrician]

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.

 

[tiny-tim]

… to prove x2 = x3 …

Hi Electrician!

Equation 2: 40=x2+x4
Equation 3: 40=x3+x4

subtracting: x2 - x3 = 0. ​

 

[The Electrician]

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.

 

[tiny-tim]

… plain and simple cooking …

… The answer requires more sophistication than I would expect. …

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

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?

 

[The Electrician]

"...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.

 

[Bob Ho]

"...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.

Yes you are correct, For the very first question(Solving the system), I made x4=t to prove there are infinite solution. Which got me x1=t+10, x2=t+60, x3=t+60. I'm assuming that proves that the solutions are infinite?

For the Final Subquestion (sorry this will be the last)

Q.) To Reduce congestion, a bypass road joining intersections A and C was built. Solve the new system assuming a traffic flow of x5 on the new road in the direction of C.

My attempt) I formed these Equations;

x1+x2+x5=50
x2+x4+x5=40
x1+x3+x5=50
x3+x5=50
x4+x5=40

From there I got
x1=0,x2=0,x3=0,x4=-10,x5=50

making x1=t ;
x2=t
x3=t
x4=t-10
x5=t+50

Hopefully that is correct. Thanks for your help!

 

[The Electrician]

Sorry I'm so late replying. I had to be out of town for nearly two weeks.

While it's true that mathematically there are an infinite number of solutions, the real world constraints I mentioned in post #4 apply. The streets are one way, so the values of the X's can't be less than zero. Also, the solutions have to be integers since you can't have a fraction of a car.

You don't need to introduce a new variable t; just let X4 be a free variable, able to take on any value mathematically, but only able to take on integer values from zero to some upper limit because of the real world constraints.

Letting X4=t, your solution "x1=t+10, x2=t+60, x3=t+60" is incorrect as can be seen by letting t=0. Then X4=0 and X2 =60, but your second equation in your first post says X2+X4=40; your solution would give X2+X4=60.

The correct solution would be X4=t, X1=t+10, X2=40-t, X3=40-t. You should always do a sanity check by selecting a few values and substituting back in your original equations.

The new bypass road goes from intersection A to intersection C; that is, from upper left to lower right. You still only have 4 intersections, and therefore only 4 equations. The new road just adds an X5 term to two of your original equations, so you should have:

X1+X2+X5=50
X2+X4=40
X3+X4-X5=40
X1+X3=50

This adds one new column and one new variable to the matrix form of the problem:

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

It's now an underdetermined system, with more unknowns than equations. It can still be solved and the Gauss-Jordan method is a good one to use. You have probably have a text that explains this method. I won't go through all the details here, but the solution now has two free variables. Letting X4 and X5 be the free variables, the solution is:

X1 = X4-X5+10
X2 = 40-X4
X3 = X5-X4+40
X4 = X4
X5 = X5

This means that you can pick X4 and X5 to be anything mathematically and you get an infinite number of solutions. But your real world problem constrains X4 and X5 to be integers not less than zero. How large they can be is constrained by the requirement that X1, X2 and X3 can't become less than zero for any values of X4 and X5. This means, for example, that X4 can't be greater than 40, because if it were, then X2 would be negative, and so forth for the others.