Math 236, Case Study 1: Traffic Flow Analysis
Due: Monday, September 22, 2014
Stephanie Duong, Hanyue Xu
Part I: Traffic Flow in Fort Lee, New Jersey
The diagram above represents a street plan in the busiest first two blocks in the downtown of Fort Lee, New Jersey. All streets have one-way traffic.
The traffic control center has installed electronic sensors that count the numbers of vehicles passing through the 10 streets that lead into and out of the downtown area.
The arrows represent the one-way direction of each street and the numbers shown below are the numbers of vehicles per hour that pass through these streets.
Cars are not allowed to park on the streets, which means that the total flow of cars into an intersection must equal the total flow of cars out of an intersection. This is called conservation of flow. It leads to a system of six linear equations that model the traffic flow. The system can be written as a matix equation \[ Ax=b, \] where
\(A\) is a \(6 \times 7\) matrix. The six rows correspond to the six intersections. The seven columns correspond to the (unknown) traffic flow on the seven streets in the downtown
\(x\) is a \(7 \times 1\) column matrix (vector) of the flow of cars on each street
\(b\) is a \(6 \times 1\) column matrix (vector) of the net flow of cars through the intersection
We will refer to the seven entries in the \(x\) vector as \(x_1,x_2,x_3,x_4,x_5,x_6,x_7\).
Note that cars coming into the intersection count as positive flow and cars leaving an intersection count as negative flow. For example, the constraint for the upper left hand intersection is
\[ 200 + x_6 = x_1 + 400\]
Question 1: Write down the linear system
Enter all six constraint equations, one for each intersection. We’ve written the first constraint for you.
\[ 200 + x_6 = x_1 + 400\] \[ 300 + x_1 = x_2 + x_7\] \[ x_2 + x_3 = 100 + 200\] \[ 200 + 200 = x_4 + x_3\] \[ x_7 + x_4 = x_5 + 300\] \[ x_5 + 500 = 400 + x_6\]
Question 2: Put the linear system into standard form
Now rewrite your equations so that the variables are on the left hand side and the constants are on the right hand side. Be sure to get the positive/negative signs correct! We’ve written the first one for you.
\[ -x_1 + x_6 = 200\] \[ x_1 - x_2 - x_7 = -300\] \[ x_2 + x_3 = 300\] \[ x_4 + x_3 = 400\] \[ x_4 - x_5 + x_7 = 300\] \[ x_5 - x_6 = -100\]
Question 3: Create the vector \(b\) and the matrix \(A\)
Here is an example of how to create a vector in R:
v=c(2,3,6)
print(v) # just so you can see what we created## [1] 2 3 6b=c(200,-300,300,400,300,-100)To create a matrix in R, you can either use the command cbind to bind together multiple columns, or the command rbind to bind together multiple rows. Here are some examples:
(G=cbind(c(1,4,7),c(2,5,8),c(3,6,9))) # note that if you put parentheses around the entire line, the result is printed## [,1] [,2] [,3]
## [1,] 1 2 3
## [2,] 4 5 6
## [3,] 7 8 9(H=rbind(c(1,2,3),c(4,5,6),c(7,8,9)))## [,1] [,2] [,3]
## [1,] 1 2 3
## [2,] 4 5 6
## [3,] 7 8 9Use these commands to form the matrix \(A\) and the column vector \(b\) for your linear system from Question 2.
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0b=c(200,-300,300,400,300,-100)
print(b)## [1] 200 -300 300 400 300 -100Question 4: Create an augmented matrix
You can also bind together two matrices, side-by-side. Here’s an example:
(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6Create the augmented matrix \(M=[~A~|~b~]\) for your linear system from Question 2.
(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100Question 5: Solve the linear system with reduced echelon form
Unlike Mathematica and MATLAB, the basic version of R does not have a built-in function to put a matrix in reduced row echelon form, but the package pracma does have such a function, which is called rref. If you first install the package, you then have access to this function.
require(pracma)Now use rref(M) to reduce your augmented matrix into echelon form. You should find that your system has five basic variables. (If not, go back and check your work.) The two free variables will be \(x_6\) and \(x_7\). Express the solution set in parametric form by using the template below. Be sure to get your positive and negative signs correct!
R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 -1 0 -200
## [2,] 0 1 0 0 0 -1 1 100
## [3,] 0 0 1 0 0 1 -1 200
## [4,] 0 0 0 1 0 -1 1 200
## [5,] 0 0 0 0 1 -1 0 -100
## [6,] 0 0 0 0 0 0 0 0\[ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{pmatrix} = \begin{pmatrix} -200 \\ 100 \\ 200 \\ 200 \\ -100 \\ 0 \\ 0 \end{pmatrix} + x_6 \begin{pmatrix} 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} + x_7 \begin{pmatrix} 0 \\ -1 \\ 1 \\ -1 \\ 0 \\ 0 \\ 0 \end{pmatrix}\]
Question 6: Interpreting the solution
Not every solution is a valid one. In particular, every flow must be non-negative: a negative flow would correspond to cars driving the wrong way on a one way street!
- What is the minimum value allowed for \(x_6\)? Explain.
The minimum value for \(x_6\) is 200 because that would bring \(x_1\) to equal zero (a non-negative) and \(x_5\) to equal 100 (a non-negative).
- The minimum value for \(x_7\) is a function of \(x_6\). Write down the constraint for the minimum value of \(x_7\). Explain.
The constraint with respect to \(x_7\) are given by:
\[ x_2=100+x_6-x_7 \] \[ x_3=200-x_6+x_7 \] \[ x_4=200+x_6-x_7 \]
Since all the traffic flow has to be non-negative,
\[ 100+x_6-x_7 \geq 0 [1]\] \[ 200-x_6+x_7 \geq 0 [2]\] \[ 200+x_6-x_7 \geq 0 [3]\]
[1] and [3] gives the constraint for the maximum value of \(x_7\) while [2] gives the constraint for its minimum value of \[ x_7 \geq x_6-200 \] In part a) we figured out the minimum constraint for \(x_6\) which is 200. Therefore the constraint for the minimum value of \(x_7\) is 0.
Part II: Traffic Diversion Study
In order to plan for upcoming road construction, the Traffic Control Center (TCC) wants to study possible traffic diversion policies. The flows into and out of downtown cannot be changed. The TCC wants to know which roads they can close down during the day. For each of those roads, they want to know the impact of the traffic diversion.
Remember that a road closure is acceptable if there is a solution to the resulting system in which all of the flows are non-negative.
Figuring out whether we can close a road is actually very easy. We just need to add a seventh constraint to our system! For example, if we want to close the street corresponding to \(x_1\), we just add the constraint
\[ x_1 = 0, \]
and then solve the corresponding linear system, which now has seven rows instead of six! Note that now you will have six basic variables and one free variable (because you have added one new constraint).
Question 7: Which streets can we close?
Decide whether we can close each street and still maintain traffic flow in downtown Fort Lee. Again, this means that every street must have non-negative flow.
Summarize your results in the table below. For each street, answer YES or NO depending on whether we can close it. If a closure is possible, then state which other streets are forced to have constant flow, and then state any constraints on the free variables. If the closure is not possible, just write N/A in the other two columns (for “Not Applicable”).
\(x_1\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(1,0,0,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 1 0 0 0 0 0 0b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 1 0 0 0 0 0 0 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 0 0 0
## [2,] 0 1 0 0 0 0 1 300
## [3,] 0 0 1 0 0 0 -1 0
## [4,] 0 0 0 1 0 0 1 400
## [5,] 0 0 0 0 1 0 0 100
## [6,] 0 0 0 0 0 1 0 200
## [7,] 0 0 0 0 0 0 0 0\(x_2\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(0,1,0,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 0 1 0 0 0 0 0b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 0 1 0 0 0 0 0 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 0 -1 -300
## [2,] 0 1 0 0 0 0 0 0
## [3,] 0 0 1 0 0 0 0 300
## [4,] 0 0 0 1 0 0 0 100
## [5,] 0 0 0 0 1 0 -1 -200
## [6,] 0 0 0 0 0 1 -1 -100
## [7,] 0 0 0 0 0 0 0 0\(x_3\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(0,0,1,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 0 0 1 0 0 0 0b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 0 0 1 0 0 0 0 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 0 -1 0
## [2,] 0 1 0 0 0 0 0 300
## [3,] 0 0 1 0 0 0 0 0
## [4,] 0 0 0 1 0 0 0 400
## [5,] 0 0 0 0 1 0 -1 100
## [6,] 0 0 0 0 0 1 -1 200
## [7,] 0 0 0 0 0 0 0 0\(x_4\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(0,0,0,1,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 0 0 0 1 0 0 0b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 0 0 0 1 0 0 0 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 0 -1 -400
## [2,] 0 1 0 0 0 0 0 -100
## [3,] 0 0 1 0 0 0 0 400
## [4,] 0 0 0 1 0 0 0 0
## [5,] 0 0 0 0 1 0 -1 -300
## [6,] 0 0 0 0 0 1 -1 -200
## [7,] 0 0 0 0 0 0 0 0\(x_5\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(0,0,0,0,1,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 0 0 0 0 1 0 0b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 0 0 0 0 1 0 0 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 0 0 -100
## [2,] 0 1 0 0 0 0 1 200
## [3,] 0 0 1 0 0 0 -1 100
## [4,] 0 0 0 1 0 0 1 300
## [5,] 0 0 0 0 1 0 0 0
## [6,] 0 0 0 0 0 1 0 100
## [7,] 0 0 0 0 0 0 0 0\(x_6\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(0,0,0,0,0,1,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 0 0 0 0 0 1 0b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 0 0 0 0 0 1 0 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 0 0 -200
## [2,] 0 1 0 0 0 0 1 100
## [3,] 0 0 1 0 0 0 -1 200
## [4,] 0 0 0 1 0 0 1 200
## [5,] 0 0 0 0 1 0 0 -100
## [6,] 0 0 0 0 0 1 0 0
## [7,] 0 0 0 0 0 0 0 0\(x_7\) = 0
(A=rbind(c(-1,0,0,0,0,1,0),c(1,-1,0,0,0,0,-1),c(0,1,1,0,0,0,0),c(0,0,1,1,0,0,0),c(0,0,0,1,-1,0,1),c(0,0,0,0,1,-1,0),c(0,0,0,0,0,0,1)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,] -1 0 0 0 0 1 0
## [2,] 1 -1 0 0 0 0 -1
## [3,] 0 1 1 0 0 0 0
## [4,] 0 0 1 1 0 0 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 0 0 1 -1 0
## [7,] 0 0 0 0 0 0 1b=c(200,-300,300,400,300,-100,0)
print(b)## [1] 200 -300 300 400 300 -100 0(G.aug=cbind(G,v))## v
## [1,] 1 2 3 2
## [2,] 4 5 6 3
## [3,] 7 8 9 6(A.aug=cbind(A,b))## b
## [1,] -1 0 0 0 0 1 0 200
## [2,] 1 -1 0 0 0 0 -1 -300
## [3,] 0 1 1 0 0 0 0 300
## [4,] 0 0 1 1 0 0 0 400
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 0 0 1 -1 0 -100
## [7,] 0 0 0 0 0 0 1 0require(pracma)R=rref(A.aug)
print(R)## b
## [1,] 1 0 0 0 0 -1 0 -200
## [2,] 0 1 0 0 0 -1 0 100
## [3,] 0 0 1 0 0 1 0 200
## [4,] 0 0 0 1 0 -1 0 200
## [5,] 0 0 0 0 1 -1 0 -100
## [6,] 0 0 0 0 0 0 1 0
## [7,] 0 0 0 0 0 0 0 0| Street | Can we close it? | What flows are constant? | Constraints on free variable? |
|---|---|---|---|
| \(x_1\) | \[YES\] | \[x_5,x_6\] | \[0 \leq x_7 \leq 300\] |
| \(x_2\) | \[YES\] | \[x_3,x_4\] | \[x_7 \geq 300\] |
| \(x_3\) | \[YES\] | \[x_2,x_4\] | \[x_7 \geq 0\] |
| \(x_4\) | \[NO\] | \[N/A\] | \[N/A\] |
| \(x_5\) | \[NO\] | \[N/A\] | \[N/A\] |
| \(x_6\) | \[NO\] | \[N/A\] | \[N/A\] |
| \(x_7\) | \[YES\] | \[N/A\] | \[x_6 = 200\] |
Question 8: Capacity limit
Suppose that the street corresponding to \(x_7\) has a capacity of 250 cars per hour. Which of the street closures above would no longer be available? We won’t be able to close off street \(x_2\) because we need \(x_7\) \(\geq\) 300, but the capacity of 250 cars per hour would leave us with a negative flow for \(x_1\).