Hungarian algorithm as a linear programme 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 mean in the assignment formulation?
- if worker does task , and otherwise.
- What values may take?
- or only (binary).
- Write the cost objective function for an problem.
- Minimise .
- How is a maximum profit problem written as an LP?
- Maximise , using the profit matrix directly.
- What constraint says worker does exactly one task?
- .
- What constraint says task is done by exactly one worker?
- .
- How many variables and equality constraints in an problem?
- variables and equality constraints.
- With more workers than tasks, what changes in the worker constraints?
- Each worker does at most one task: .
- How is an impossible pairing handled in an LP?
- Omit its variable, or add .
- What does mean?
- Worker 2 does task 3.
- Why can an extra condition such as 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 with costs , ?
- .