Math 236, Case Study 1: Traffic Flow Analysis
Ashley Hung, Trung Ngyuen, Tuyet-Anh Tran
Part I: Traffic Flow in Fort Lee, New Jersey
Question 1: Write down the linear system
Enter all six constraint equations, one for each intersection. We’ve written the first constraint for you. The left hand side of your equations should be the flow into the intersection, and the right hand side should be the flow out of the intersection.
SOLUTION: Question 1
\[ 200 + x_6 = x_1 + 400 \] \[ 300 + x_1 = x_2 + x_7 \] \[ x_2 + x_3 = 300 \] \[ x_5 + 500 = x_6 + 400 \] \[ x_4 + x_7 = x_5 + 300 \] \[ x_3 + x_4 = 400 \]
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.
SOLUTION: Question 2
\[ -x_1 + x_6 = 200 \] \[ -x_1 + x_2 + x_7 = 300\] \[ x_2 + x_3 = 300\] \[ x_5 - x_6 = -100\] \[ x_4 - x_5 + x_7 = 300\] \[ x_3 + x_4 = 400\]
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) #the c command combines or concatenates a list of elements into a vector
print(v) # just so you can see what we created## [1] 2 3 6To create a matrix in R, you have may options. I will show you three different ways to do this! First, you can use the command cbind to bind together multiple columns
(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 9Second, use the command rbind to bind together multiple rows, or the command matrix. Here are some examples:
H=rbind(c(1,2,3),c(4,5,6),c(7,8,9))
H #You can also just type the variable name to a display of H## [,1] [,2] [,3]
## [1,] 1 2 3
## [2,] 4 5 6
## [3,] 7 8 9Finally, you can use the matrix command to build a matrix. In this command, you must first include a vector of all the data, the number of rows put into the argument nrow and the number of columns put in to ncol.
I=matrix(data=c(1,2,3,4,5,6,7,8,9),nrow=3,ncol=3)Notice, this is not the same matrix as above. If you want the correct matrix, you need to tell R to read in the entries by the rows (the default is to read in by columns) by adding the argument byrow=TRUE.
I=matrix(data=c(1,2,3,4,5,6,7,8,9),nrow=3,ncol=3,byrow=TRUE)Now that we have some experience creating vectors and matrices in R, use these commands to form the matrix \(A\) and the column vector \(b\) for your linear system from Question 2.
SOLUTION: Question 3
A = matrix(data=c(-1,0,0,0,0,1,0,-1,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,-1,0,0,0,0,1,-1,0,1,0,0,1,1,0,0,0),nrow=6,ncol=7, byrow=TRUE)
print(A)## [,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 0 0 1 -1 0
## [5,] 0 0 0 1 -1 0 1
## [6,] 0 0 1 1 0 0 0b = matrix(data=c(200,300,300,-100,300,400),nrow=6,ncol=1,byrow=TRUE)
print(b)## [,1]
## [1,] 200
## [2,] 300
## [3,] 300
## [4,] -100
## [5,] 300
## [6,] 400Question 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.
SOLUTION: Question 4
\(M=[~A~|~b~]\)
(Ab.aug=cbind(A,b))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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 0 0 1 -1 0 -100
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 1 1 0 0 0 400M=Ab.aug
print(M)## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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 0 0 1 -1 0 -100
## [5,] 0 0 0 1 -1 0 1 300
## [6,] 0 0 1 1 0 0 0 400Question 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!
SOLUTION: Question 5
Reduced Row Echelon Form of Matrix M
S=rref(M)
print(S)## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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 0Parametrized Vector Form
\[ \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 \\ 1 \\ 0 \end{pmatrix} + x_7 \begin{pmatrix} 0 \\ -1 \\ 1 \\ -1 \\ 0 \\ 0 \\ 1 \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_7\) is a function of \(x_6\). Write down the constraint for the minimum value of \(x_7\). Explain.
SOLUTION: Question 6
\(x_6 \geq 200\) because plugging in anything less than 200 to the vector equation above for \(x_6\) would result in a negative value for \(x_1\). If \(x_6\) = 200, then \(x_1\) (the variable with the lowest intercept/constant value) will be zero.
\(0 \leq x_7 \leq 300\) By using the inequality \(x_n\geq0\) and substituting 200 for \(x_6\) into all of the equations of the system (finding all \(x_n\)), since 200 is the minimum value to have positive traffic flow, it is evident that 300 is the maximum value possible for \(x_7\). Anything greater would cause a negative value for \(x_2\). Conversely, looking at \(x_7\) independently from \(x_6\), \(x_7\) must be greater than or equal to 0, otherwise the equation for the free variable \(x_7\) would have a negative result, correlating to a negattive traffic flow on the \(x_7\) segment of road.
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”).
| Street | Can we close it? | What flows are constant? | Constraints on free variable? |
|---|---|---|---|
| \(x_1\) | Yes | \(x_1 = 0\), \(x_5 = 100\), \(x_6 = 200\) | \(0 \leq x_7 \leq 300\) |
| \(x_2\) | Yes | \(x_2 = 0\), \(x_3 = 300\), \(x_4 = 100\) | \(x_7 \geq 300\) |
| \(x_3\) | Yes | \(x_2 = 300\), \(x_3 = 0\), \(x_4 = 400\) | \(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 | \(x_1 = 0\), \(x_2 = 300\), \(x_3 = 0\), \(x_4 = 400\), \(x_5 = 100\), and \[x_6 = 200\] | N/A |
Can we close the street with flow \(x_1\)?
Use this space below to include your calculations for \(x_1\).
(D=rbind(S,c(1,0,0,0,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 1 0 0 0 0 0 0 0(DD=rref(D))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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_1 = 0\] \[x_2 = -x_7 + 300\] \[x_3 = x_7\] \[x_4 = -x_7 + 400\] \[x_5 = 100\] \[x_6 = 200\] \[x_7 = x_7\]
\(x_2 \geq 0\) so \(300 - x_7 \geq 0\) if \(300 - x_7 = 0\) then \(x_7 = 300\) is the maximum value that will maintain \(x_2 \geq 0\) as a true statement and keep all traffic flows positive.
Can we close the street with flow \(x_2\)?
Use this space below to include your calculations for \(x_2\).
(E=rbind(S,c(0,1,0,0,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 0 1 0 0 0 0 0 0(EE=rref(E))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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_1 = x_7 - 300\] \[x_2 = 0\] \[x_3 = 300\] \[x_4 = 100\] \[x_5 = x_7 - 200\] \[x_6 = x_7 - 100\] \[x_7 = x_7\]
\(x_1 \geq 0\) so \(x_7 - 300 \geq 0\) if \(x_7 - 300 = 0\) then \(x_7 = 300\) is the maximum value that will maintain \(x_1 \geq 0\) as a true statement and keep all traffic flows positive.
Can we close the street with flow \(x_3\)?
Use this space below to include your calculations for \(x_3\).
(F=rbind(S,c(0,0,1,0,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 0 0 1 0 0 0 0 0(FF=rref(F))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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_1 = x_7\] \[x_2 = 300\] \[x_3 = 0\] \[x_4 = 400\] \[x_5 = x_7 + 100\] \[x_6 = x_7 + 200\] \[x_7 = x_7\]
Can we close the street with flow \(x_4\)?
Use this space below to include your calculations for \(x_4\).
(G=rbind(S,c(0,0,0,1,0,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 0 0 0 1 0 0 0 0(GG=rref(G))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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_1 = x_7 + 400\] \[x_2 = -100\] \[x_3 = 400\] \[x_4 = 0\] \[x_5 = x_7 - 300\] \[x_6 = x_7 - 200\] \[x_7 = x_7\]
\(x_2\) is negative, so traffic flow is negative here. We can’t close \(x_4\).
Can we close the street with flow \(x_5\)?
Use this space below to include your calculations for \(x_5\).
(H=rbind(S,c(0,0,0,0,1,0,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 0 0 0 0 1 0 0 0(HH=rref(H))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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_1 = -100\] \[x_2 = 200\] \[x_3 = x_7 + 100\] \[x_4 = -x_7 + 300\] \[x_5 = 0\] \[x_6 = 100\] \[x_7 = x_7\]
\(x_1\) is negative, so traffic flow is negative here. We can’t close \(x_5\).
Can we close the street with flow \(x_6\)?
Use this space to include your calculations for \(x_6\).
(I=rbind(S,c(0,0,0,0,0,1,0,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 0 0 0 0 0 1 0 0(II=rref(I))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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_1 = -200\] \[x_2 = -x_7 + 100\] \[x_3 = x_7 + 200\] \[x_4 = -x_7 + 200\] \[x_5 = -100\] \[x_6 = 0\] \[x_7 = x_7\]
\(x_1\) and \(x_5\) are negative, so traffic flow is negative here. We can’t close \(x_6\).
Can we close the street with flow \(x_7\)?
Use this space below to include your calculations for \(x_7\).
(J=rbind(S,c(0,0,0,0,0,0,1,0)))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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
## [7,] 0 0 0 0 0 0 1 0(JJ=rref(J))## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [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\[x_1 = x_6 - 200\] \[x_2 = x_6 + 100\] \[x_3 = -x_6 + 200\] \[x_4 = x_6 + 200\] \[x_5 = x_6 - 100\] \[x_6 = x_6\] \[x_7 = 0\]
If \(x_6 - 200 \geq\) and \(-x_6 + 200 \geq\) then we can conclude that \(x_6 - 200= 0\) and \(x_6 = 200\). So \[x_1 = 0\] \[x_2 = 300\] \[x_3 = 0\] \[x_4 = 400\] \[x_5 = 100\] \[x_6 = 200\] \[x_7 = 0\]
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?
SOLUTION: Question 8
Closing \(x_2\) would no longer be possible because it includes the restraint \(x_7 \geq 300\). After the capacity limit of \(x_7 \leq 250\), \(x_1\), \(x_3\), and \(x_7\) are still available for street closures.