Matching and Allocation Problems (VCE SSCE General Mathematics): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Bipartite graph
Bipartite graph
Graph with 2 groups; edges only connect different groups
Complete bipartite graph
Complete bipartite graph
Every vertex in one group connects to all in other group
Allocation problem
Allocation problem
Matching items from one group to items in another group
Cost matrix
Cost matrix
Table showing cost of each allocation between two groups
Hungarian algorithm purpose
Hungarian algorithm purpose
Find optimal allocation to minimise total cost
Hungarian algorithm Step 1
Hungarian algorithm Step 1
Subtract smallest value in each row from all values in row
Hungarian algorithm Step 3
Hungarian algorithm Step 3
Subtract smallest value in column from column (if no zero)
Hungarian Step 5a: smallest uncovered value operation
Hungarian Step 5a: smallest uncovered value operation
Add to cells with 2 lines; subtract from uncovered cells
Matrix for final cost calculation in Hungarian algorithm
Matrix for final cost calculation in Hungarian algorithm
Original cost matrix, not transformed matrix
Method for simple allocation problems
Method for simple allocation problems
Identify forced assignments (one edge) and use elimination