Hungarian algorithm as a linear programme

Hungarian algorithm as a linear programme Flashcards

Spec 2.2 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
What does xijx_{ij} mean in the assignment formulation?
xij=1x_{ij}=1 if worker ii does task jj, and 00 otherwise.
What values may xijx_{ij} take?
00 or 11 only (binary).
Write the cost objective function for an n×nn\times n problem.
Minimise ∑i=1n∑j=1ncijxij\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}.
How is a maximum profit problem written as an LP?
Maximise ∑∑pijxij\sum\sum p_{ij}x_{ij}, using the profit matrix directly.
What constraint says worker ii does exactly one task?
xi1+xi2+⋯+xin=1x_{i1}+x_{i2}+\dots+x_{in}=1.
What constraint says task jj is done by exactly one worker?
x1j+x2j+⋯+xnj=1x_{1j}+x_{2j}+\dots+x_{nj}=1.
How many variables and equality constraints in an n×nn\times n problem?
n2n^2 variables and 2n2n equality constraints.
With more workers than tasks, what changes in the worker constraints?
Each worker does at most one task: xi1+⋯+xin≤1x_{i1}+\dots+x_{in}\le1.
How is an impossible pairing handled in an LP?
Omit its variable, or add xij=0x_{ij}=0.
What does x23=1x_{23}=1 mean?
Worker 2 does task 3.
Why can an extra condition such as x11+x33≤1x_{11}+x_{33}\le1 not be dealt with by the Hungarian algorithm?
It is not a one-per-worker or one-per-task condition, so the problem is no longer a pure assignment problem.
Total cost of the allocation x12=x21=1x_{12}=x_{21}=1 with costs c12=9c_{12}=9, c21=8c_{21}=8?
9+8=179+8=17.

Flashcards