A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Bipartite Graph

FM Bipartite Graph

6.2 Methods for Optimum Assignment

Note: if you cannot remember how to represent matching problems in graphs and matrices, revise notes for 6.1 Introduction to Matching Problems.

Optimum Assignment by Inspection

  • In smaller scale matching problems, it may be possible to determine the optimum assignment by inspection.
  • One method is to find the lowest weight assignment for each task, object, etc. being assigned to. If there is any conflict, then consider other tasks, objects, etc.

Example

Teacher

Banjo

Violin

Piano

Dave

10

25

35

Jill

11

15

40

Steve

10

18

46

Above is a matrix representing the time in days required for each teacher at a school to teach a beginner’s course in certain instruments. Only one teacher is required for each course and each teacher must be assigned to a course. As this is a smaller-scale problem, we will use inspection to find the optimum assignment.

Read More »6.2 Methods for Optimum Assignment

6.1 Introduction to Matching Problems

Matching Problems

  • There are many instances in which a several tasks, objects, or other needs to be assigned to a group of people, objects or other. For example, individually assigning a group of people a list of tasks. This is known as a matching problem.
  • Matching problems often have multiple solutions however there is generally one or more optimum solution. This is the one which achieves the intended result while expending the least time or resources.
  • In some cases, multiple assignments may be required for either group (e.g. a task may require many people or a person may be assigned to many tasks).

Bipartite Graph

Read More »6.1 Introduction to Matching Problems