Transportation Problem Formulation and Basics for CMA Final

Understand Transportation Problem Formulation and Basics

Key rules to remember

Objective function

Minimise Z = ΣΣ cij × xij (i = 1 to m, j = 1 to n)

cij is the unit cost from origin i to destination j. xij is the quantity shipped. Z is total transportation cost.

Supply constraints

Σj xij = ai for each origin i

Shipments from an origin equal its supply. In an unbalanced case with a dummy, this holds after balancing.

Demand constraints

Σi xij = bj for each destination j

Receipts at a destination equal its demand.

Non-negativity

xij ≥ 0 for all i, j

You cannot ship a negative quantity.

Balance condition

Σ ai = Σ bj

Balanced if true. If Σ ai > Σ bj add a dummy destination; if Σ ai < Σ bj add a dummy origin.

Number of variables and constraints

Variables = m × n; constraints = m + n

m origins and n destinations, after balancing.

Basic feasible solution size

Allocated cells = m + n − 1

A non-degenerate basic feasible solution has exactly this many occupied cells. Fewer means degeneracy.

How to solve Transportation Problem Formulation and Basics questions

1. 1Identify the origins and destinations and note the supply at each origin and the demand at each destination.
2. 2Write the unit costs into an m × n matrix, rows for origins, columns for destinations. Mark any prohibited route with a very large cost M, or as not allowed.
3. 3Add total supply and total demand.
4. 4If they are equal, the problem is balanced. If not, add a dummy destination (supply greater) or a dummy origin (demand greater) for the difference, with zero cost in its cells unless the question gives penalty or storage costs.
5. 5Define the variables xij and write the objective function Z = ΣΣ cij xij to be minimised.
6. 6Write the supply constraints, demand constraints and non-negativity condition.
7. 7Check that total supply equals total demand in the final table and that the number of cells and constraints is right.
8. 8State the next step if asked: find an initial basic feasible solution, then test for optimality.

Quickest way: Total-first balance check

Common mistakes in Transportation Problem Formulation and Basics

• Solving an unbalanced problem without adding a dummy

  Students rush to allocate and skip the total check.

  Fix: Always total supply and demand first. Never begin allocation until the table is balanced.

• Adding the dummy on the wrong side

  Confusion between surplus supply and shortage of supply.

  Fix: Surplus supply means unsold stock, so add a dummy destination (column). Shortage means unmet demand, so add a dummy origin (row).

• Putting rows and columns the wrong way round

  Students copy the data order from the question rather than origins as rows.

  Fix: Rows are origins with supply on the right. Columns are destinations with demand at the bottom. Label them clearly.

• Giving a dummy cell a non-zero cost without being told

  Students think every cell must have a cost.

  Fix: Use zero for dummy cells unless the question gives storage, penalty or shortage costs. If it does, use those figures.

• Ignoring a prohibited route

  A statement such as 'no supply from plant B to depot 2' is easy to miss in the case text.

  Fix: Put a very large cost M in that cell so it is never chosen, and underline such conditions as you read.

• Miscounting the basic cells needed

  Students recall m + n instead of m + n − 1.

  Fix: Count after balancing, including dummies, and use m + n − 1.

Worked examples