Transportation problems

Transportation problems Flashcards

Spec 1.1–3 · 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.

14 cards

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

See all 14 cards
What is a balanced transportation problem?
Total supply equals total demand.
How many occupied cells does a non-degenerate basic solution have?
m+n−1m+n-1 (for mm sources and nn destinations).
What does the north-west corner method do?
Allocates as much as possible starting from the top-left cell, moving right or down, ignoring costs.
What is degeneracy?
A solution with fewer than m+n−1m+n-1 occupied cells.
How do you fix a degenerate solution?
Place a 0 in an unoccupied cell (without making a closed loop of occupied cells).
When do you add a dummy destination?
When supply exceeds demand.
When do you add a dummy source?
When demand exceeds supply.
What are the costs to and from a dummy?
Zero.
How are shadow costs found?
Ri+Kj=CijR_i+K_j=C_{ij} for every occupied cell, with R1=0R_1=0.
Formula for the improvement index?
Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j
When is a solution optimal?
When all improvement indices are ≥0\ge0.
Which cell enters?
The unoccupied cell with the most negative improvement index.
How is θ\theta chosen in the stepping-stone loop?
The smallest quantity in a −- cell; that cell exits.
What are the LP constraints for a transportation problem?
Row sums equal the supplies and column sums equal the demands, with xij≥0x_{ij}\ge0.

Flashcards