Discrete Structures Problem

Network Analysis

One application of systems of linear equations is an area sometimes referred to as network analysis. I will give you a number of different applications, many from students, to give you an idea of the variety of these types of problems. You should be prepared to make up a meaningful example like the following. Directed graphs can be used as models for a variety of situations in disciplines such as: computer science, traffic analysis, electrical engineering and economics. A directed graph is also referred to as a network and the analysis of the given problem as network analysis. Directed graphs are composed of nodes (also called vertices or junctions), and directed edges. In the graph below, figure 1, the nodes are the “circles” labeled 1,2,3 and 4. “Dots”, with labels, are also used in place of circles. The edges are the “arrows” in the graph. We assume in the following flow examples that the sum of the flow into any (intermediate) vertex is equal to the sum of the flow out of that vertex. Below are several examples. Example 1. The flow of traffic (in vehicles per hour) through a network of streets is shown in the figure 1: Solve this system for , i = 1, 2, 3, 4. ix Find the traffic flow when 03 =x Find the traffic flow when 1003 =x

x2

4

1

400

1x

3x

200

400

F

2

3

4x

200

IGURE 1

Solution a) From figure 1, we have the following linear equations: Junction 1: 31 200 xx =+ Junction 2: 12 400 xx =+ Junction 3: 42 200 xx =+ Junction 4: 34 400 xx =+ The augmented matrix for this system is:

⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢

⎣

⎡

−− −− −− −−

4001100 2001010 4000011 2000101

Gauss-Jordan elimination produces the matrix

⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢

⎣

⎡

− −−

−

00000 4001100 6000110

2001001

This matrix gives us the following equations: x1 – x4 = 200 x2 – x3 = -600 x3 – x4 = 400 Note you could have obtained these equations directly from the given system of equations. So x1 = 200 – x4 x2 = -200 + x4 Why? x3 = 400 + x4 . Since x4 (and therefore the other variables) stands for a number of vehicles it must be an integer. Can it be negative? Zero? Another way of describing the solutions is to use a dummy variable, say s as used below. Let we have: sx =4 sx += 2001 sx +−= 2002 sx += 4003 where s is any real number. Thus this system has an infinite number of solutions. (More about this later.) Note the solutions could have been described without using s (see the above).

b) If x3 = 0 then 0 = 400 + s so that x4 =s = -400. This tells us that x1 =-200, x2 = -600. What this means is when the traffic flow along street x3 is restricted to 0, that is, when this street is closed the flow along the other streets is: x1 = -200, x2 = -600 and x4 = -400. Which of course does not make any sense. Why? If: x3 =100 then 100 = 400 + s so that Systems of Equations Which Do Not Have A Unique Solution = s = -300. This tells us that x1 =-100, x2 = -500 and x4 = -300, which still does not make any sense. Can you determine the minimum value of s (or x4) which will make sense in this problem? That is, what is the smallest value of x4 which will make the other variables nonnegative? In addition, for this problem to be realistic we should have a maximum capacity for each edge. That is, each road or edge cannot handle an infinite number of cars per hour. The number of vehicles that can travel along a road is determined by several factors, for example: the width of the road, its surface (how smooth etc.), and how straight it is, speed limit etc. So there are a maximum number of cars per hour that can travel along each road. You should make up a realistic maximum capacity for each edge. Example 2 The flow of traffic (in vehicles per hour) through a network of streets is shown in the figure 3: Solve this system for , i = 1, 2,..,5. ix Find the traffic flow when and 03 =x 505 =x Find the traffic flow when 5053 == xx FIGURE 3 Solution a) From figure 3, we have the following linear equations:

1

4 3

2

4x 3x

2x

1x 300 200

150 50

5x

Junction 1: 12 200 xx =+ Junction 2: 431 300 xxx +=+ Junction 3: 5054 =+ xx Junction 4: 150532 =++ xxx The augmented matrix for this system is:

⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢

⎣

⎡ −

−−

15010110 5011000 30001101 20000011

Gauss-Jordan elimination produces the matrix

⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢

⎣

⎡ −

−−

0000000 5011000

10001110 20000011

If we let and we have: sx =5 tx =3 tsx −−= 3501 tsx −−= 1502 sx −= 504 where s and t are integers. b) For an example if we let: t or 03 =x and let s or 505 =x we obtain for the other variables: x1 = 300, x2 = 100 and x4 = 0

300

1

4 3

2

0 0

100

300 200 150 50

50

c) If we let: 5053 == xx 50==⇒ st

1

4 3

2

0 50

50

50

300

150

200

250

50 Follow the same rationale we did on example 2 so that the results of this problem make sense in the “real world”. Example 4. A student example (good if you know electric circuits). A particular circuit has current sources connected across ports ab and cd. If Iac=50 Amps and Icd=20 amps the flow of current in the circuit is demonstrated in the figure.

x7

A

x6 B

F

C D

x3 x4 x5

E x1 x2

50 A

20 A With the sources fixed at their particular values. Find the flow between each node when the path between F & E is an open circuit ( x2 = 0 ) and when the path is a short circuit at 10 amps.

By Kirchoff's current law, the sum of the voltages entering a node is equal to that leaving the node, so: (NOTE: Two of the following equations are wrong. Which two? Check the flow equations for nodes C and D.) 50 = x1 + x3 50 = x3 + x6 x1 - x4 = x2 x2 = x5

x5 = x7 + 20 20 = x4 + x4

The augmented matrix for this system is:

1 0 1 0 0 0 0 50

0 0 1 0 0 1 0 50

1 -1 0 -1 0 0 0 0

0 1 0 0 -1 0 0 0

0 0 0 0 1 0 -1 20

0 0 0 -1 0 1 0 20 Gauss-Jordan elimination produces:

0 0 1 0 0 0 0 50

0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0

0 1 0 1 0 0 0 0

0 0 0 1 1 0 0 0

0 0 0 1 0 0 1 -20 In other words x3 = 50 x6 = 0 x1 = 0 x2 + x4 = 0 x4 + x5 = 0 x3 + x3 = -20

This implies that the current from the 50A source follows the shortest path possible and does not go over to the other side of circuit. For the open circuit case x2 = 0 This results in: x4 = 0, x5 = 0, and x7 = -20 as all the current flows between C and D. When the path x2 permits 10 Amps the results become: x4 = -10, x5 = 10, and x7 = -10 this is an example of a current division as half flows through one path and the remaining current flows through another. Example 5. The internet is a network of servers; servers receive requests of information from client PCs (i.e. individual’s PCs), or send the requested information to the client PCs. A person (the sender) sends a large file over the internet to second person (the receiver). Before the file is sent, it is split into small packets. Then the packets are routed through the network using routers to avoid congestion; routers are set up to regulate the flow of data. In this problem, the network contains four routers named A, B, C, and D. The bandwidth of the network is measured in megabytes per second (Data is represented in binary inside a computer, 0 or 1, which is called a bit. A unit of byte contains of 8 bits. A unit of kilobyte contains 1024 bytes. A unit of megabytes contains 1000 kilobytes). Suppose the file contains 80 megabytes of data, which are sent to the routers A and C as illustrated below. The complete network is illustrated below:

A B

C D

50

5x

4x

3x2x

50

30

Receiver Sender

1x

According to the above figure, the 80-megabytes file is split into 2 packets, 30-megabytes and 50-megabytes. The two packets are then routed through the routers, and split into more packets. At the routers B and D, these small packets are combined and sent to the receiver. Note that the received file must contain exactly 80 megabytes of data such as when it is sent by the sender.

Solve this system the data flow represented by , i = 1, 2, ..5. ix Find the network flow pattern when 02 =x Find the network flow pattern when 302 =x Solution a) From the figure , we have the following linear equations: Junction A: 3021 =+ xx Junction B: 5031 =+ xx Junction C: 5043 =+ xx Junction D: 542 xxx =+ Junction RECEIVER: 80505 =+x The augmented matrix for this system is:

⎥ ⎥ ⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢ ⎢ ⎢

⎣

⎡

− 3010000 011010

5001100 5000101 3000011

Gauss-Jordan elimination produces the matrix:

⎥ ⎥ ⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢ ⎢ ⎢

⎣

⎡

000000 3010000 5001100 3001010 3000011

Let we have: sx =4 sx =1 sx −= 302 sx −= 503 305 =x where s is real numbers. Thus this system has an infinite number of solutions. b) If , then we have the following graph: 02 =x

A B

C D

30

30

20 0

50

50

30

Receiver Sender

30

a) If , then we have the following graph: 302 =x

30

A B

C D

0

30

50

50

50

30

Receiver Sender

0

Example 6. Now, we understand the concept of how a file is sent through the network of internet. We can consider the next problem. A student at MIT wants to download a 1-megabyte graphic computer file located on a server at U. C. Berkley in Oakland, CA. If the file is sent out as a sequential data stream, it will take too long. So the file is broken up into ten 100-kilobytes “packets” and routed via multiple servers located in different cities around the country, and reassembled at MIT into one file.

Solution a) From the figure, we have the following linear equations: Junction BERKLEY: 1043 1 =++ x Junction SEATTLE: 365 =+ xx Junction CHICAGO: 476 =+ xx Junction LA: 132 xxx =+ Junction ATLANTA: 443 =+ xx Junction DENVER: 24 7452 ++=++ xxxx Junction MIT: 1044 8 =++ x The augmented matrix for this system is:

⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢

⎣

⎡

−−−

−

210000000 201011010

400001100 000000111 401100000 300110000 300000001

Gauss-Jordan elimination produces the matrix:

SEATTLE CHICAGO

U.C. BERKLEY

MIT

LA ATLANTA

DENVER

6x

5x 4 7x(1megabyte)

10 packets 3

8x4

4 2 x

3x

4x1 x

⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢

⎣

⎡

−−

000000000 210000000 401100000 101010000

400001100 300000110 300000001

Let and , we have: tx =4 sx =7 31 =x tx +−= 12 tx −= 43 sx +−= 15 sx −= 46 28 =x where s and t are real numbers. Thus this system has an infinite number of solutions. b) If , then we have the following graph: 074 == xx

3

1

SEATTLE CHICAGO

U.C. BERKLEY

MIT

LA ATLANTA

DENVER

0

0

2

4

1 4

4

4

3 (1megabyte) 10 packets

4 c) If and 43 =x 26 =x , then we have the following graph:

SEATTLE CHICAGO

U.C. BERKLEY

LA ATLANTA

DENVER

3

4 2

2

2

1

0

4

1 4

4 3 (1megabyte)

10 packets

MIT

Example 7. A train carries 1000 people into Boston. Once there everybody must immediately get to the Government Center to go to work. There are several different subways, which go to the Government Center. The network of the subways in this problem is illustrated below:

A B

C D 4x

500

500

E

6x

5x

3x

2x 7x

Government center

Station

x1

Let the nodes A, B, C, D, and E represent the different subways, A, B, C, D, and E. Solution a) From the figure, we have the following linear equations:

Junction A: 50021 =+ xx Junction B: 71 xx = Junction C: 50043 =+ xx Junction D: 64 xx = Junction E: 532 xxx =+ The augmented matrix for this system is:

⎥ ⎥ ⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢ ⎢ ⎢

⎣

⎡

− −

−

00010110 00101000

5000001100 01000001

5000000011

Gauss-Jordan elimination produces the matrix:

⎥ ⎥ ⎥ ⎥ ⎥ ⎥

⎦

⎤

⎢ ⎢ ⎢ ⎢ ⎢ ⎢

⎣

⎡

−

−

10001110000 00101000

5000001100 5001000010

01000001

Let and , we have: sx =6 tx =7 tx =1 tx −= 5002 sx −= 5003 sx =4 tsx −−= 10005 where s and t are real numbers. Thus this system has an infinite number of solutions. b) If and , then we have the following graph: 06 =x 07 =x

A B 0

E

0 500

1000 500

Government C t

If and then we have the following graph: 2006 =x 3007 =x

300

A B

C

300

D 200 200

500

E 500

300 200 500

Government Center

Station

Example 8. RAVMAK Corporation developed a DSP (digital signal processor) that can translate voice over IP (Internet protocol) signals. The DSP processor can take a data signal, a fax in, and a voice input from one port and can send it out over IP. The way the processor works is it has internal currents that translate analog to digital signals, and digital to analog signals. The processor takes these currents at different frequencies and combines them and translates them out back to the port, and then sends it out over IP. Within the processor there are 4 digital to analog converters. These converters handle the entire analog to digital conversions. These converters are labeled 1, 2, 3, and 4 on the flow chart. The current coming into the processor is 20 mA at converter 4, and the current that leaves converters 1 and 3 is 10 mA. The currents combine at converters 1

and 3 to the total current that originally entered the circuit that was 20 mA. There is one limitation to the circuit design, it has a limiting factor of circuit, and the circuit can only handle a maximum of 25 mA per node, so the input and combination of currents at any node can never exceed 25 mA. The complete network is illustrated below:

1

Just as a second reminder the DSP circuit cannot exceed 25mA per a node and the total input at converter 4 must equal to sum of the outputs of converters 1 and 3. A.) Solve this system for current flow for Xi, i = 1, 2, 3, 4.

X1

1 2

X3

X2

X4

3 4 10 20

Solution: From the figure, we have the following linear equations: Converter 1: X2 + X3 – X1 = 10 Converter 2: X1 + X4 = 0 Converter 3: X2 + X4 = -10 Converter 4: X3 = 20 The augmented matrix for this system is: -1 1 1 0 10 1 0 0 1 0 0 –1 0 –1 10 0 0 1 0 20 Gauss-Jordan elimination produces the matrix: 0 0 0 0 0 1 0 0 1 0 0 –1 0 –1 10 0 0 1 0 20

Let X4 = s we have: X1 = -s -X2 – 10 = s X3 = 20 where s is a real number. Thus this system has an infinite number of solutions. Find the current flow pattern when X2 = 0 If X2 = 0, then we have the following graph:

1

C.) Find the current flow pattern when X2 = 10

10

-10

20 0

10

204 3

2 1

If X2 = 10, then we have the following graph:

10

0

20 10

10

204 3

2 1

Example 9

The following figure shows flights per day from selected airports in various cities to other cities’ airports. The routes shown can be interpreted as alternative ways to travel from Los Angeles airport to Boston airport. In this problem, we will analyze the effects of changing the number of flights to and from intermediate cities’ airports. The results can be used as a means to decide which path(s) to take when flying from Los Angeles to Boston. The more number of flights might lead to increased delay times which might prevent a traveler from choosing that route (edge). On the other hand, the more number of flights means more frequent flights per day, which might make impatient travelers prefer this route.

X6

Houston

Washington D.C

Los Angeles

Boston

Denver

Atlanta X5

X4

X3

X2

X1

40

50

60

Chicago 70

100

Solving the system From the figure, we have the following linear equations: Junction Denver: 60 = x1 + x2 + x3 Junction Houston: 100 = x4 + x5 + x6 Junction Chicago: x1 + x4 = 70 Junction Atlanta: x3 + x6 = 40 Junction DC: x2 + x5 = 50 Re-organizing the equations, we have: x1 + x2 + x3 = 60 x4 + x5 + x6 = 100 x1 + x4 = 70 x3 + x6 = 40 x2 + x5 = 50 The augmented matrix for this system is:

1 1 1 0 0 0 60 0 0 0 1 1 1 100 1 0 0 1 0 0 70 0 0 1 0 0 1 40 0 1 0 0 1 0 50 Gauss-Jordan elimination produces the matrix: 1 0 0 1 0 0 70 1 1 0 0 0 -1 20 0 0 1 0 0 1 40 0 1 0 0 1 0 50 0 0 0 0 0 0 0 This matrix gives us the following equations: x1 + x4 = 70 x1 + x2 – x6 = 20 x3 + x6 = 40 x2 + x5 = 50 Further simplification of the equations leads to the following: x6 = x1 + x2 – 20 = (70 – x4 ) + (50 – x5 ) – 20 = 100 – x4 – x5 => x4 = 100 – x5 – x6 x1 = 70 – x4 = 70 – 100 + x5 + x6 = x5 + x6 – 30 Putting the variables in order, we have: x1 = x5 + x6 - 30 x2 = 50 – x5 x3 = 40 – x6 x4 = 100 – x5 – x6 Letting x5 = s and x6 = t, we get: x1 = s + t –30, x2 = 50 – s, x3 = 40 – t, x4 = 100 – s – t

where s and t are real numbers. Thus this system has an infinite number of solutions. Using the equations that are just found, we are now ready to analyze the traffic under different circumstances. a) What is the traffic load when there is no flights from Houston to Atlanta and only 30 flights per day from Houston to Washington DC? This problem states that s = 30, t = 0 x1 = 30 + 0 – 30 = 0 x2 = 50 – 30 = 20 x3 = 40 – 0 = 40 x4 = 100 – 30 – 0 = 70 b) What is the traffic load when there is no flights from Houston to Washington DC and only 35 flights from Houston to Atlanta? According to the problem, we have s = 0, t = 35 x1 = 0 + 35 – 30 = 5 x2 = 50 – 0 = 50 x3 = 40 – 35 = 5 x4 = 100 – 0 – 35 = 65 c) How is the traffic when there is no flights from Denver to Chicago, but no other restrictions flights to other cities? From the problem statement, we have x1 = 0 0 = x5 + x6 – 30 => x5 + x6 = 30 x2 = 50 – x5 x3 = 40 – x6 x4 = 100 – x5 – x6 = 100 – (x5 + x6 ) = 100 – (30) = 70

as a result of no flights from Denver to Chicago, we see that the number of flights from Houston to Chicago must be 70 per day and the total number of flights from Houston to Washington DC and Atlanta must be 30 per day. d) What if there were no flights to Washington DC? This states that x2 = x5 = 0, x1 = 0 + x6 – 30 0 = 50 – 0 => 0 = 50 here, we see that there is no solution to this problem. This is because there are 50 flights per day going from Washington DC to Boston but if the incoming flights are restricted, there is no way 50 flights can be going out. e) How about the case when there is no flights from Houston to Atlanta and the number of flights from Houston to Washington DC is restricted to 10? From this statement, we have s = 10, t = 0 x1 = 10 – 30 = -20 x2 = 50 – 10 = 40 x3 = 40 – 0 = 40 x4 = 100 – 10 = 90 In this case we see that x1 is a negative number. This doesn’t make sense because it is impossible to have a negative number of flights from a city to another one. It might be possible to have a number of flights in the reverse direction however, that is not what is being analyzed here, that is, we are analyzing flights going in one direction. As for the capacity of the routes (edges), there is theoretically no limit since infinite number of planes can be in the air simultaneously (assuming there is no limit to the sky) however, this does not mean that the airports can handle all the traffic. So the capacity limits are the result of airport limitations and not the routes themselves. f) What are the ranges of s and t, assuming that negative numbers don’t make sense? Since negative numbers don’t make sense, the minimum either variable can be is 0 (zero), that is, smin = tmin = 0. Letting s = smin = 0, we get: x1 = x6 – 30 x2 = 50 – 0 = 50

x3 = 40 – x6 x4 = 100 – x6 From the equations, we see that in order for x1 to make sense (not be negative), we need x6 to be greater than or equal to 30. for x3 to make sense, we need x6 to be less than or equal to 40. this gives us our range for x6 40 ≥ x6 ≥ 30 Letting t = tmin = 0, we get: x1 = x5 - 30 x2 = 50 – x5 x3 = 40 – 0 = 0 x4 = 100 – x5 From the equations, we see that in order for x1 to make sense, we need x5 to be greater than or equal to 30. in order for x2 to make sense, we need x5 to be less than or equal to 50, giving us the range for x5 50 ≥ x6 ≥ 30 Example 10. The following figure shows hiking trails from a parking lot to a summit of a mountain. The starting point is indicated as Start and the summit as Finish. The number of people hiking to the summit is 200. We assume that all hikers who go out reach the summit.

80 x3

5

x7

Start

2

6

5

7

1

4

3 Finish

x6

120

80

x2 x8

x5

x4

70

50

x1

In the figure we have following linear equations: Junction 1: 50 = x1 + x2 Junction 2: 80 = x4 + x3 Junction 3: 70 + x4 = x5 Junction 4: x2 + x3 = x6 + x7 + 5 Junction 5: x5 + x6 = 120 Junction 6: x1 + 5 = x8 Junction 7: x8 + x7 = 80 After reorganizing the equations: x1 + x2 = 50 x3 + x4 = 80 x4 - x5 = -70 x2 + x3 -x6 - x7 = 5 x5 + x6 = 120 x1 - x8 = -5 x7 + x8 = 80

The augmented matrix for that system is: 1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 1 1 0 0 -1 -1 0 5 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80 R4 = R4 + R5 1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 1 1 0 1 0 -1 0 125 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80 R4 = R4 + R3 1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 1 1 1 0 0 -1 0 55 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80

R4 = R4 – R2 1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 1 0 0 0 0 -1 0 -25 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80 R4 = R4 – R1 1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 -1 0 0 0 0 0 -1 0 -75 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80 R4 = R4 + R6

1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 0 0 0 0 0 -1 -1 -80 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80

R4 = R4 + R7 1 1 0 0 0 0 0 0 50 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 120 1 0 0 0 0 0 0 -1 -5 0 0 0 0 0 0 1 1 80 Exchanging row positions: 1 1 0 0 0 0 0 0 50 1 0 0 0 0 0 0 -1 -5 0 0 1 1 0 0 0 0 80 0 0 0 1 -1 0 0 0 -70 0 0 0 0 1 1 0 0 120 0 0 0 0 0 0 1 1 80 0 0 0 0 0 0 0 0 0 The matrix gives following equations: x1 + x2 = 50 x1 – x8 = -5 x3 + x4 = 80 x4 – x5 = -70 x5 + x6 = 120 x7 + x8 = 80 Further simplification of the equations leads to the following: x1 = x8 – 5 x2 = 50 – x1 x3 = 80 – x4 x4 = x5 – 70 x5 = 120 – x6 x7 = 80 – x8

Letting x8 = s and x6 = t (s and t are non-negative integers), we get: x1 = s – 5 x2 = 50 – s + 5 = 55 – s x5 = 120 – t x4 = 120 – t – 70 = 50 - t x3 = 80 – 50 + t = 30 + t x7 = 80 – s Thus this system has an “infinite number of solutions” with the restrictions mentioned below. Several examples for the above system are: a) Suppose that in last hurricane severally damaged paths x6 and x8. After an

inspection, path x6 was closed for public and path x8 was allowed for use only by 5 people per day.

That leaves us with t = 0 and s = 5. Therefore, x1 = 5 – 5 = 0 (the path was closed as well, even though it wasn’t damaged) x2 = 55 – 5 = 50 x3 = 30 – 0 = 30 x4 = 50 – 0 = 50 x5 = 120 – 0 = 120 x6 = 0 x7 = 80 – 5 = 75 x8 = 5 b) What happens when a large hiking group decides to go for the summit and the

fact becomes widely known? Smaller groups and individual hikers take other routs to avoid the crowded paths, which are x3 and x7. Let’s say that it is a group of 75 hikers (x3 = x7 = 75), and the total number people going for the summit is still 200.

Therefore, x3 = 30 + t = 75, t = 75 – 30 = 45 x7 = 80 – s = 75, s = 80 – 75 = 5 x1 = s – 5 = 5 – 5 = 0 x2 = 55 – s = 55 – 5 = 50 x5 = 120 – t = 120 – 45 = 75

x4 = 50 – t = 50 – 45 = 5 x3 = 30 + t = 30 + 45 = 75 x7 = 80 – s = 80 – 5 = 75 The ranges of s and t are as follows: • Since those numbers represent number of people taking routs x6 and x8 to the

summit, those numbers are integers and cannot be negative. Meaning, s ≥ 0 and t ≥ 0.

• Since there is a path to junction 6 that 5 people hike everyday, there should be a way out for at least 5 people. Therefore, s ≥ 5.

• The maximum number of people who can pass thru junction 6 is 55. Therefore, s cannot be bigger than that number (s ≤ 55).

• On the same token, he maximum number of people who can pass thru junction 4 is 130. 5 out of those 130 must go thru junction 6. Therefore, t ≤ (130 – 5) =125.

Applying that to other equations, we get range values for other routes: 0 ≤ x1 ≤ 50 0 ≤ x2 ≤ 50 0 ≤ x3 ≤ 80 0 ≤ x4 ≤ 80 70 ≤ x5 ≤ 150 0 ≤ x6 ≤ 125 0 ≤ x7 ≤ 125 5 ≤ x8 ≤ 125 Example 11. People get sick. Sometimes in order to receive the proper treatment and medication they must go through certain channels. The following example will outline a scenario in which 150 sick people go to their regular doctor’s office while another 200 sick people go to a specialist’s office with a specific problem over the course of a year. These two groups of people represent the input into the system. A certain number of people who go to the doctor are then referred to the specialist’s office; this is the variable x1. Another group of people going to the doctor are given Drug A; this is the variable x3. The people seeing the specialist are then tested to determine which drug is appropriate for them; this is x2. After this test, 200 people are given Drug B, while the rest are prescribed Drug A; this is x4. There are then 150 people with Drug A. This network is illustrated below:

Figure 1 Solve this system for xi, i = 1, 2, 3, 4 Find the flow of people when x4 = 50 Find the flow of people when x4 = 10 Solution

a) From Figure 1, we have the following linear equations: Junction 1: 200 + x1 = x2 Junction 2: x1 + x3 = 150 Junction 3: x3 + x4 = 150 Junction 4: 200 + x4 = x2 The augmented matrix for this system is: 1 0 1 0 150 -1 1 0 0 200 0 1 0 -1 200 0 0 1 1 150 Gauss-Jordan elimination produces the matrix: 1 0 1 0 150 0 1 0 -1 200 0 0 1 1 150 0 0 0 0 0

This matrix gives the following equations: x1 + x3 = 150 x2 – x4 = 200 x3 + x4 = 150 By substitution we can find that x1 = x4. We can also describe this with a dummy variable, s, where x4 = s. This gives us: x1 = s x2 = 200 + s x3 = 150 - s where s is any real number. This shows that the system has an infinite number of solutions.

b) Let s = x4 = x1 = 50 Then x2 = 250 and x3 = 100

c) Let s = x4 = x1 = 10

Then x2 = 210 and x3 = 140

d) These results make sense for the real world. When x2 = 0, s has a negative value.

This zero flow would occur when the specialist’s office is closed and not conducting the tests. The only limit on the maximum capacity of each edge would be how many patients the doctor and specialist are able to see over a period of time. The number of 350 people being seen in a year is a reasonable maximum capacity.