MAST20018 – Discrete Mathematics and Operations Research Assignment 3 Place in your tutor's box by 5pm Wednesday 5th October 2016 1. The following project consists of 8 activities, which have been labelled A to H: Activity Time (days) Precedences A. 5 — B. 7 — C. 6 — D. 3 A E. 4 B,C F. 2 C G. 6 A,D H. 5 E,F (a) Draw the corresponding AON network for the project. (b) Draw the corresponding AOA network for the project. (c) Calculate the total float for each activity. (d) Find all critical paths in the AON network. (e) Find the minimum amount of time required to complete the project. (f) What is the e↵ect on minimum completion time if F is delayed by 3 days? (g) What is the e↵ect on minimum completion time if E is delayed by 3 days? 1MAST20018 – Discrete Mathematics and Operations Research 2. Consider the network below: s q y x w t u p (a) Write down the node-node adjacency matrix for the given network using the formula A = [aij], aij = 8<: 1, if nodes i and j are connected by an edge 0, otherwise. (b) Assume that the nodes are ordered as s, p, q, y, u, x, w, t in the rows and columns of A. Without doing any matrix multiplication, write down the top row of A2, and explain your reasoning. (c) Draw a tree, with root s, indicating a shortest path from s to all the other nodes. (d) Using the data in your tree, employ the recursive algorithm from class to compute the number of shortest paths from s to t. (e) Without doing any matrix multiplication, state the entry in the row of node s and the column of node t in A3. 2MAST20018 – Discrete Mathematics and Operations Research 3. (a) For the AON activity network write down the matrix Q relevant to the max-plus calculation of the earliest start times. (b) Without doing any explicit max-plus matrix calculations, give the value of h0 !1 !1 !1 !1 !1 !1 !1i ⌦ Q5 (c) Consider an AON activity network. Let p equal the maximum number of directed edges in a path of the network. Give a description for a matrix Q ˜, a column vector ~ x, and an analogue of a max-plus operation ⌦ ˜ such that computing Q ˜p⌦ ˜ ~ x will give the latest finish times at each node. Demonstrate your method on the AON network below. 3