D2 1.1 - The north-west corner method
You will read a transportation table, use the north-west corner method to obtain an initial basic feasible allocation, and calculate its cost without confusing quantities sent with unit costs.
Costs, supplies, demands and allocations
Could an algorithm send stock along a route costing pounds per unit while a route costing is still unused? The north-west corner method can. Its first job is to satisfy supplies and demands; finding the cheapest solution comes later.
You already know
A total cost is a unit cost multiplied by the quantity sent. A non-negative quantity can be zero. No earlier Decision Mathematics option content is needed for this lesson.
Rows represent supply points and columns represent demand points. In the following table, the middle entries are costs in pounds per unit, while the margins give quantities.
| Supply point | Supply | |||
|---|---|---|---|---|
| Demand |
The total supply and demand are both . This is a balanced transportation problem: all available stock can be assigned while meeting every demand exactly.
Feasible transportation allocation
An allocation specifies a non-negative quantity sent from each source to each destination. For a balanced exact-demand problem, each row sum equals that source's supply and each column sum equals that destination's demand.
The entry in cell is a cost, not an instruction to send six units. If an allocation sends units there, its contribution to total cost is pounds.
[DIAGRAM: asset_name: Costs and allocations are separate tables; asset_slug: 9fm0-d2-180-costs-and-allocations; caption: Unit costs describe routes; allocations describe how many units are sent.; description: Two clearly labelled three-by-three tables with rows A,B,C and columns P,Q,R: left costs8,6,10;9,7,4;3,4,2, right allocations15,5,blank;blank,25,blank;blank,5,25, with supplies20,25,30 and demands15,35,25.]
Key idea
Check units first. Costs belong to routes; allocations must add to the supplies and demands. A feasible allocation is not automatically a minimum-cost allocation.
Use the same cell to distinguish all three quantities.
Following the north-west corner rule
Begin with the top-left cell of the table in its given row and column order. Allocate as many units as possible there, then update the remaining supply and demand before moving.
North-west corner method
At the current upper-left available cell, allocate the smaller of the remaining row supply and column demand. If the column demand is met, move right. If the row supply is exhausted, move down. If both are exhausted together, mark both complete, discard that row and column, and continue at the next north-west available cell. Continue until all supply and demand are assigned.
Use the original table order: do not sort costs or jump to a cheap cell. Each allocation finishes at least one remaining row or column. The resulting staircase is an initial basic feasible solution: it gives a starting allocation for a later improvement algorithm.
Not in the formula booklet: learn it.
Worked example 1: a complete allocation trace
Question. Apply the north-west corner method to supplies and demands , in that order.
Plan. At each cell take the smaller remaining margin, then cross off the completed row or column.
| Cell | Allocation | Remaining row supply | Remaining column demand | Next action |
|---|---|---|---|---|
| Move right | ||||
| Move down | ||||
| Move down | ||||
| Move right | ||||
| Complete |
Why send only units from to ? The already sent to used part of 's original supply; use the remainder, not again.
Answer. The non-zero allocations are
All other cells are empty, representing no shipment.
Check. Row totals are ; column totals are . All allocations are non-negative.
Worked example 2 transfers units of available stock from to . Total supply and all demands remain unchanged.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account