Further Maths AT 4.1 2009 Name:
YEAR 12 FURTHER MATHEMATICS
ASSESSMENT TASK 4.1, 2009
NETWORKS AND DECISION MATHS
NAME:ANSWERS
TEACHER:
TIME:5 minutes reading time85 minutes working time
Please note: The grade for this task is only part of the internal assessment for this unit. Your total school assessed coursework score may change as a result of statistical moderation by the VCAA.
Answer each of the following in the space provided.
Question 1
The hierarchy of a business is outlined by the directed network below where each vertex represents an employee.
indicates A has dominance over D
a)Determine which employeeshave one-step dominance over employee D.
A, B and E
b)Use a matrix method to determine which employee has the greatest influence.
Row Totals
A = 6
B = 10
C = 1
D = 5
E = 6
F = 0
G =1
Answer: B has the greatest influence
[1+4=5 marks]
Question 2
The Sew-Sew Sewing Machine Manufacturing Co Ltd have 5 people on their assembly line. Each has been trained to perform the 5 tasks required (called A, B, C, D and E) to assemble the sewing machines. The average time (in minutes) each employee takes to complete each task is given in the following table.
Person / A / B / C / D / EGinny / 12 / 11 / 14 / 18 / 10
Dianne / 11 / 16 / 19 / 15 / 10
Anit / 14 / 14 / 17 / 18 / 9
Rhonda / 13 / 11 / 16 / 16 / 13
Phil / 15 / 13 / 13 / 17 / 12
(a)Given that each person must complete one of the tasks, use the Hungarian Algorithm to find what task should be allocated to each person.
NOTE: There may be more than one solution – you are only required to find ONE.
Row
Reduction
ColumnCovering
Reduction zeros
Possible Solutionsor
Name / Solution 1 / Solution 2Ginny / A / B
Dianne / D / A
Anit / E / E
Rhonda / B / D
Phil / C / C
(b) What is the optimal time on the production line?
60 minutes
[5+1=6marks]
Question 3.
Recyclable materials are to be collected from households in a part of a particular suburb. The network below represents this area, where the numbered dots are street intersections and the edges are the streets. The numbers indicate the lengths (in metres) of the streets between intersections.
(a)Explain what is meant by the description of this network as planar.
No edges cross each other
(b)What is the degree of vertex 7?4
(c)Verify Euler’s formula for this network.
V = 10, E = 15, F = 7V = E – F + 2
10 = 15 – 7 + 2
(d)The collectors wish to travel along each street once only in order to keep travel distance to a minimum. What sort of path is needed? Determine this path.
EULER PATH
Eitherstart at 2 and finish at 5ORstart at 5 and finish at 2
(They should have 16 numbers in their path including the starting 2/5 and finishing 2/5. They need to have two of each number except 1, 4, 8 10)
(e)As well as the criterion mentioned in part (c) above, they would also like to start and finish at the same intersection. What is the name given to this type of route? If this is possible, determine this route. If it is not, what would need to happen for it to be possible?
EULER CIRCUIT
This is not possible unless there was another street/edge joining 2 and 5
OR
Every vertex needs to be even.
(f)The Transport Department has placed traffic density monitors at each intersection. Beginning at intersection 1, determine a route that a departmental officer could take in order for her to collect all the monitors. What is the name given to this type of path?
HAMILTONIAN PATH
Their path should mention each vertex only once
(g)A taxi driver wants to transport a customer from 1 to 10. Determine the shortest distance for him to travel between intersections 1 and 10 and indicate this path.
Distance = 450 metresPath = 1-3-6-9-10
[1+1+2+2+2+2+2=12 marks]
Question 4
Jack’s construction company is building the new BigtownUniversity. The company has constructed nine new faculty buildings in a layout as shown below. The minimum distances in metres between adjacent buildings in the university are also shown.
A computer network is to be built to serve the whole university.
(a)Draw a network that will ensure that all the buildings are connected to the network but that the amount of cable used is minimized.
(b)What is the minimum length of cable required?
1820 metres
[3+1=4 marks]
Question 5
The following network shows the major road systems through a busy city. The numbers represent the maximum number of cars per minute that can flow along each road.
(a) (i)List all the possible ways of travelling from A to C.
A-B-CA-B-E-CA-E-CA-D-E-C
[2 marks]
(b) (i)Can roads BC and BE have a maximum flow at the same time?
Explain your answer.
NO.
For BC and BE to both have maximum flow at the same time, you would need a total outflow of 40 from B, but there is only a flow of 30 into B.
(ii)What is the maximum flow from A to G?
110 cars per minute
(iii)Draw the cut on the diagram whose capacity is equal to the maximum
flow obtained.
see cut on diagram
[2+2+1=5marks]
Due to the construction of a tunnel to provide another link for traffic between A and C, the road BE is closed to traffic.
(c) How does this road closure affect your answer to (b) (ii)?
This reduces the maximum flow to 100 cars per minute
[2 marks]
Once the tunnel is completed it will be able to carry a maximum of 40 cars per minute from A to C and the road BE is to remain closed to traffic.
The network is redrawn below with these changes made.
(d) Calculate the maximum flow with the new tunnel in operation.
140 cars per minute (cut is shown)
[3 marks]
The State Government indicates that funds will be made available to upgrade one road only, to carry an extra 10 cars per minute, if it can be shown that this will increase the maximum flow of the entire network.
(e)Is there such a road in this network where an increase of 10 cars per minute will increase the total flow of the entire network? Give reasons to support your answer.
The following roads could be given as an answer – AD or AE
It would need to be one of the roads on the minimum cut. Increasing the flow on BC or AC doesn’t help as CG can’t handle any more than 60 cars per minute.
[3 marks]
Question 6
The local council in the town of Dodge plans to turn the main street of the town into a mall. The planning phase involves a number of activities as shown in the diagram below.
(a)Use this diagram to perform a forward and backward scan.
(see above)
[4 marks]
(b)Determine the two missing values from table 1 below.
Table 1Activity / Earliest start time (day) / Latest start time (day)
A / 0 / 0
B / 0 / 2
C / 5 / 7
D / 10 / 10
E / 10 / 12
F / 14 / 16
G / 15 / 17
H / 15 / 15
I / 22 / 22
J / 21 / 23
[2 marks]
(c)Name all of the activities which must have been completed before activity G can begin?
A, B, C and D
[1 mark]
(d)(i)State the critical path in this network.
A-D-H-I
(ii)Determine the length of the critical path.
27 days
[2 marks]
The completion times for some activities are able to be shortened. Table 2 below containsthe information about the 'crash time' (possible time to which the activity time can be shortened) and the daily cost of this 'crashing'.
Table 2: Crash times and costsActivity / Normal Completion time (days) / Crash time (days) / Cost of crashing per day ($)
A / 10 / 8 / 400
B / 5 / 5 / -
C / 3 / 2 / 400
D / 5 / 4 / 600
E / 4 / 4 / -
F / 6 / 5 / 500
G / 6 / 4 / 200
H / 7 / 5 / 300
I / 5 / 5 / -
J / 4 / 3 / 400
(e)(i)By completing the diagram again using all of the values given in the ‘crash time’ column, OR OTHERWISE, fill in Table 3.
Table 3: New times using allcrashed dataActivity / Earliest start time (day) / Latest start time (day)
A / 0 / 0
B / 0 / 1
C / 5 / 6
D / 8 / 8
E / 8 / 8
F / 12 / 12
G / 12 / 15
H / 12 / 12
I / 17 / 17
J / 16 / 19
(ii)Determine the shortest time in which the project can now be finished.
22 days
(iii)What is the minimum cost for achieving this new time in part (ii)?
(C, G, and J don’t need to be crashed)
Minimum cost A$ 800
D$ 600
F$ 500
H$ 600
______
TOTAL$2500
(iv)Apart from A, what three other activities must be shortened so that the project will be completed in this new minimum time stated in (ii)?
D, F and H
[2+1+3+3=9 marks]
Page 1 of 12