Linear System - Network Flow Matrices

In summary, the minimum flow along AC when ED is closed due to roadwork is 20 cars per minute, assuming all roads have non-negative flow.
  • #1
1LastTry
64
0

Homework Statement


Consider the network of streets with intersections a,b,c,d and e below. The arrows indicate the direction of traffic flow along the oneway streets, and the numbers refer to the exact number of cars observed to enter or leave a,b,c,d and e during one minute. Each xi denotes the unknown number of cars which passed along the indicated streets during the same period.
See Attached Image
Linear System:
x1+x6-x5=55
x5-x4=35
x6+x3-x4=60
x3-x2=40
x1-x2=70

Reduced row-echelon form
1 0 0 0 -1 1 | 55
0 1 0 0 -1 1 |-15
0 0 1 0 -1 1 |25
0 0 0 1 -1 0 |-35
0 0 0 0 0 0 |0
s t
General Solution:
x1=55+s-t
x2=-15+s-t
x3=25+s-t
x4=-35-s
x5=s
x6=t

The question is: if ED were closed due to roadwork, find the minimum flow along AC, using your results in the general solution.
Note: x2 = ED therefor x2=0, and AC is x6

Homework Equations





The Attempt at a Solution



I know x2=0 and no idea what to do with S and T...
what I did is set x2=0 so -15+s-t=0 so S=t+15
And sub it into the general solution you get:
x1=70
x2=0
x3=40
x4=-20+t
x5=15+t
x6=t

so x4≥0 when t≥20
x6≥0 when t≥0
So minflow is 0?
 

Attachments

  • IMG_0238.jpg
    IMG_0238.jpg
    29.3 KB · Views: 447
Physics news on Phys.org
  • #2
1LastTry said:

Homework Statement


Consider the network of streets with intersections a,b,c,d and e below. The arrows indicate the direction of traffic flow along the oneway streets, and the numbers refer to the exact number of cars observed to enter or leave a,b,c,d and e during one minute. Each xi denotes the unknown number of cars which passed along the indicated streets during the same period.
See Attached Image
Linear System:
x1+x6-x5=55
x5-x4=35
x6+x3-x4=60
x3-x2=40
x1-x2=70

Reduced row-echelon form
1 0 0 0 -1 1 | 55
0 1 0 0 -1 1 |-15
0 0 1 0 -1 1 |25
0 0 0 1 -1 0 |-35
0 0 0 0 0 0 |0
s t
General Solution:
x1=55+s-t
x2=-15+s-t
x3=25+s-t
x4=-35-s
x5=s
x6=t

The question is: if ED were closed due to roadwork, find the minimum flow along AC, using your results in the general solution.
Note: x2 = ED therefor x2=0, and AC is x6

Homework Equations





The Attempt at a Solution



I know x2=0 and no idea what to do with S and T...
what I did is set x2=0 so -15+s-t=0 so S=t+15
And sub it into the general solution you get:
x1=70
x2=0
x3=40
x4=-20+t
x5=15+t
x6=t

so x4≥0 when t≥20
x6≥0 when t≥0
So minflow is 0?

No, you are not thinking it through! You need ALL xi >= 0, so you need x4 >= 0 and so you need t >= 20. Just having t >= 0 is not good enough.

RGV
 
  • #3
I am trying to find the MINIMUM flow so...
 

Related to Linear System - Network Flow Matrices

1. What is a linear system?

A linear system is a mathematical representation of a set of linear equations or inequalities. It involves a set of variables and coefficients that are related through linear relationships.

2. What is a network flow matrix?

A network flow matrix is a type of linear system used to model the flow of resources or information in a network. It consists of nodes, which represent points in the network, and arcs, which represent the paths connecting the nodes.

3. How is a network flow matrix used?

A network flow matrix is used to analyze and optimize the flow of resources or information in a network. It can help identify the most efficient routes for transportation, the optimal distribution of goods, or the best way to allocate resources in a supply chain.

4. What are some real-world applications of network flow matrices?

Network flow matrices have many real-world applications, including transportation and logistics, telecommunications, energy distribution, and supply chain management. They are also used in computer network routing algorithms and in analyzing social networks.

5. What are some methods for solving network flow matrices?

There are several methods for solving network flow matrices, including the simplex method, the primal-dual method, and the network simplex method. These methods involve finding the optimal solution by iteratively adjusting the flow through each arc until the desired objective is achieved.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
704
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
1K
Back
Top