Special Topic 3 - Graph Theory

Assignment 2

Due 30/3/99 This assignment contributes 10% of the mark for Special Topic 3.

Equal marks for each of the following questions. The solutions should demonstrate core network models and use excel solver software.

  1. The manager of a courier service is advertising speedy delivery. To reduce delivery time he asks you to construct a table of shortest times between the courier office (node 1) and each of six frequent customers. You have measured the following times (in minutes): c12 = 5, c13 = 1, c24 = 7, c25 = 1, c26 = 6, c32 = 2, c34 = 6, c35 = 7, c43 = 7, c46 = 4, c47 = 6, c54 = 3, c56 = 5, c57 = 9, c67 = 2.
  2. Warehouses A,B,C,D can supply respectively 8, 14, 18 and 4 units of a product. Customers a,b,c,d,e have ordered respectively16, 6, 14, 4, 4 of these units. No more than 10 units can be transported on any route. The unit delivery costs are given in the following table:
    3.
     

    a

    b

    c

    d

    e

    A

    5

    8

    4

    9

    3

    B

    6

    9

    12

    8

    13

    C

    3

    -2

    0

    3

    3

    D

    10

    14

    8

    10

    13

     

  3. Find the maximum possible flow from node 1 to node 9 in a network whose arc capacities are: u12=2, u13=3, u24=3, u34=4, u36=2, u37=2, u45 no limit, u56=3, u59=2, u64=4, u69=3, u78=4, u86=5, u89=4. Arcs not listed, such as 14, do not exist.
  4. Seven types of packages are to be delivered by five trucks.There are three packages of each type, and the capacities of the five trucks are 6, 4, 5, 4, and 3 packages respectively. To minimise the chance that all packages of a given type are lost in delivery, the packages are loaded (if possible) so that no truck carries two packages of the same type. Set up a maximum flow problem to determine whether the loading is possible.