Unit III: Transportation Problem & Assignment model
Introduction to Transportation Problem
The Transportation Problem is a type of Linear Programming Problem (LPP) which aims to minimize the cost of transporting goods from several sources (like factories) to several destinations (like warehouses or markets) while meeting supply and demand requirements.
Objective
- Minimize (or sometimes maximize) the transportation cost or profit.
Structure
- m supply points (e.g., factories)
- n demand points (e.g., warehouses)
- cᵢⱼ: cost of shipping one unit from supply point i to demand point j
- sᵢ: supply at source i
- dⱼ: demand at destination j
Initial Basic Feasible Solution (IBFS)
Before optimizing the transportation cost, we first need a feasible solution that satisfies all supply and demand constraints. This is the initial basic feasible solution, which can be found using these methods:
(a) North West Corner Method (NWCM)
Steps:
- Start at the top-left (north-west) corner of the cost matrix.
- Allocate as much as possible to that cell (minimum of supply or demand).
- Adjust the supply and demand accordingly.
- Move to the next cell (right or down) based on the exhausted row or column.
- Repeat until all supply and demand is satisfied.
Pros: Simple and fast.
Cons: Ignores costs, hence may not be optimal.
(b) Least Cost Method (LCM)
Steps:
- Identify the cell with the lowest transportation cost.
- Allocate as much as possible (minimum of supply or demand).
- Adjust supply and demand, then cross out the satisfied row or column.
- Repeat the process with the remaining matrix.
Pros: Considers cost, better than NWCM.
Cons: Might not give the best IBFS.
(c) Vogel’s Approximation Method (VAM)
Steps:
- For each row and column, calculate a penalty = difference between the lowest and second lowest cost.
- Select the row/column with the highest penalty.
- In that row/column, allocate to the lowest-cost cell.
- Adjust supply/demand and cross out the satisfied row/column.
- Repeat until complete.
Pros: Gives the best IBFS among the three methods.
Cons: Slightly more complex than NWCM and LCM.
Optimal Solution Methods
Once you have an initial feasible solution, check if it is optimal using these methods:
(a) Stepping Stone Method
Steps:
- For each empty (unused) cell, trace a closed loop (path) by alternating between horizontal and vertical moves through occupied cells.
- Evaluate net cost: Add/subtract costs alternately along the loop.
- If any net cost is negative, there is room to reduce cost—allocate there.
- Repeat the process until no negative cost remains.
Pros: Graphical understanding.
Cons: Time-consuming for large problems.
(b) MODI (Modified Distribution) Method
Steps:
- Calculate dual variables (Uᵢ and Vⱼ) for occupied cells using .
- For unoccupied cells, calculate opportunity cost: Δij=Cij−(Ui+Vj)
- If all Δ ≥ 0 → optimal solution
- If any Δ < 0 → reallocate using loops (like Stepping Stone)
Pros: Faster and more efficient than the Stepping Stone method.
Maximization Transportation Problem
Instead of minimizing cost, the goal is to maximize profit (or utility) from transporting goods.
Approach
- Convert profit values into cost values by subtracting each from the maximum value in the matrix:
- Cost=Max Value−Profit
- Solve using any IBFS and optimization method (like it's a minimization problem).
- After finding the minimum cost, convert back to the maximum profit.
Note: All rules and methods remain the same; only the values are transformed.
What is an Assignment Problem?
An Assignment Problem is a special type of Linear Programming Problem where the goal is to assign tasks (jobs) to agents (workers) in a one-to-one manner while minimizing the total cost or maximizing the total profit.
🎯 Objective:
- Minimize total cost (e.g., time, expense, distance), or
- Maximize total profit, output, or efficiency.
🚩 Characteristics:
- The number of jobs = the number of workers (square matrix).
- Each agent is assigned to only one task.
- Each task is assigned to only one agent.
Hungarian Algorithm (Kuhn-Munkres Method)
The Hungarian Algorithm is the most efficient method to solve an assignment problem.
Let’s explain it for a minimization problem:
🔹 Step-by-step Process:
Step 1: Row Reduction : Subtract the smallest element in each row from all elements of that row.
Step 2: Column Reduction: Subtract the smallest element in each column from all elements of that column.
Step 3: Cover all zeros: Cover all zeros in the matrix using the minimum number of horizontal and vertical lines.
Step 4: Check Optimality:If the number of lines = number of rows (or columns), optimal assignment is possible.
If not, go to Step 5.
Step 5: Modify the matrix
- Find the smallest uncovered element.
- Subtract it from all uncovered elements, and
- Add it to elements at intersections of lines.
Return to Step 3.
Step 6: Make the Assignment
- Find a set of zeroes such that only one zero per row and column is chosen.
- That gives the optimal assignment.
Applications of Assignment Problem
Maximization Assignment Problem
In maximization problems, we aim to maximize profit, efficiency, or satisfaction.
🔹 How to Solve:
Convert to a minimization problem:
- Identify the highest value in the matrix.
- Subtract each element from this highest value:
- New value=Max element−Current value
- Apply the Hungarian Algorithm to the new matrix.
The final assignment gives the maximum total in the original matrix.
Summary Table
