Operations Research | Transportation & Assignment Models Module 5

MODULE 5

Transportation &
Assignment Models
with Microsoft Excel Applications
Operations Research | Linear Programming Applications

MODULE OVERVIEW

Credit Units: 3 units

Prerequisite: Linear Programming Fundamentals
Estimated Time: 18-20 hours (lecture + lab)
Software Required: Microsoft Excel (Solver Add-in enabled)

For educational use only Page 1

Operations Research | Transportation & Assignment Models Module 5

SECTION 1
Module Learning Outcomes & Framework

Learning Outcomes
Upon completion of this module, students will be able to:

LO 1 Formulate transportation and assignment problems as linear programming models

LO 2 Apply the Northwest Corner, Least Cost, and Vogel's Approximation methods

LO 3 Solve transportation problems to optimality using the MODI/Stepping Stone method

LO 4 Solve assignment problems using the Hungarian Method

LO 5 Use Microsoft Excel Solver to solve transportation and assignment models

LO 6 Interpret optimal solutions and analyze sensitivity in the context of real-world logistics

Module Framework
This module is structured into four major learning areas:

PART A PART B PART C PART D

Transportation Model Solution Methods Assignment Model Excel Applications

Foundations
Structure, formulation, NWC, LCM, VAM, MODI, Hungarian Method, Solver setup, sensitivity
balanced vs. unbalanced Stepping Stone maximization, restrictions analysis, case studies

For educational use only Page 2

Operations Research | Transportation & Assignment Models Module 5

SECTION 2
The Transportation Model

Part A: Foundations of Transportation Problems

A.1 Introduction and Definition
The Transportation Model is a special type of linear programming problem concerned with distributing a
commodity from a group of supply sources (origins) to a group of demand destinations (destinations) at
minimum cost. It is one of the most widely applied models in Operations Research due to its broad
applicability in logistics, supply chain management, and resource allocation.

KEY DEFINITION

A Transportation Problem seeks to determine the shipping plan that minimizes total
transportation cost while satisfying all supply and demand requirements.

A.2 Components of the Transportation Model

Component Description Example

Origins (m) Sources of supply — warehouses, Factory A, Factory B, Factory C

factories, or depots

Destinations (n) Points of demand — retail stores, Store 1, Store 2, Store 3, Store 4
customers, regions

Supply (si) Quantity available at each origin 300 units, 400 units, 500 units

Demand (dj) Quantity required at each destination 250, 350, 400, 200 units

Cost (cij) Unit transportation cost from origin i PHP 5/unit, PHP 8/unit, etc.
to destination j

xij Decision variable: units shipped from To be determined (optimal values)

i to j

A.3 Mathematical Formulation

The Transportation Model is formulated as follows:

For educational use only Page 3

Operations Research | Transportation & Assignment Models Module 5

Objective Function (Minimize Total Cost):

Minimize Z = ΣΣ cij · xij (for all i = 1,...,m and j = 1,...,n)

Subject to:
Σj xij = si (Supply constraints: for each origin i)
Σi xij = dj (Demand constraints: for each destination j)
xij ≥ 0 (Non-negativity: all shipments must be non-negative)

A.4 Balanced vs. Unbalanced Problems

A transportation problem is BALANCED when total supply equals total demand:

BALANCED PROBLEM UNBALANCED PROBLEM

Σ si = Σ dj No dummy row/column needed. Solve Σ si ≠ Σ dj Add a dummy origin or dummy
directly. destination with zero costs to balance the
problem.

For educational use only Page 4

Operations Research | Transportation & Assignment Models Module 5

SECTION 3
Transportation Solution Methods

Part B: Initial Basic Feasible Solution (IBFS) Methods

Before applying the optimality test, we must first find an Initial Basic Feasible Solution (IBFS). There are
three common methods:

B.1 Northwest Corner Method (NWC)

When to use: Quickest method; does NOT consider costs. Use only to find a starting
solution when costs are not a priority for speed.

Step-by-Step Procedure:
1. Start at the upper-left (northwest) cell of the transportation table.
2. Allocate as much as possible: assign the minimum of the available supply and demand.
3. If supply is exhausted, move DOWN to the next row (same column).
4. If demand is satisfied, move RIGHT to the next column (same row).
5. If both are satisfied simultaneously, move diagonally (down and to the right).
6. Repeat until all supply and demand are satisfied.

Worked Example — NWC Method:

Consider a problem with 3 origins (Factories A, B, C) and 4 destinations (Stores 1–4):

Store 1 Store 2 Store 3 Store 4 Supply

Factory A 2 3 11 7 300

Factory B 1 0 6 1 400

Factory C 5 8 15 9 500

Demand 250 350 400 200 1200

NWC Solution (allocations shown in bold blue cells):

Store 1 Store 2 Store 3 Store 4 Supply

For educational use only Page 5

Operations Research | Transportation & Assignment Models Module 5

Factory A 250 50 — — 300

Factory B — 300 100 — 400

Factory C — — 300 200 500

Demand 250 350 400 200 1200

Total Cost (NWC) = (250×2)+(50×3)+(300×0)+(100×6)+(300×15)+(200×9) =

500+150+0+600+4500+1800 = PHP 7,550

B.2 Least Cost Method (LCM)

When to use: Better than NWC because it considers costs. Allocate first to the cheapest
available cell. Generally produces a better starting solution.

Step-by-Step Procedure:
7. Identify the cell with the LOWEST unit cost in the entire table.
8. Allocate as much as possible to that cell (minimum of supply and demand).
9. Cross out (eliminate) the satisfied row or column.
10. From the remaining cells, find the next lowest cost cell.
11. Repeat until all supply and demand are satisfied.
12. In case of a tie, select arbitrarily (or choose the one that allows larger allocation).

B.3 Vogel's Approximation Method (VAM)

When to use: Best IBFS method — closest to the optimal solution. More work but reduces
iterations needed for optimization.

Step-by-Step Procedure:
1. For each row and column, compute the PENALTY: difference between the two lowest costs.
2. Select the row or column with the HIGHEST penalty.
3. Allocate as much as possible to the minimum cost cell in that row/column.
4. Eliminate (cross out) the exhausted row or column.
5. Recompute penalties for remaining rows/columns.
6. Repeat until all supply and demand are satisfied.

For educational use only Page 6

Operations Research | Transportation & Assignment Models Module 5

Part B continued: Optimality Test — MODI Method

B.4 Modified Distribution (MODI) / U-V Method
After finding an IBFS, we test for optimality using the MODI method. The MODI method finds the
opportunity costs for non-basic cells to determine if improvements are possible.

Step-by-Step MODI Procedure:

1. Assign row values (ui) and column values (vj) such that: ui + vj = cij for all BASIC (occupied)
cells.
2. Set u1 = 0 (or any convenient value) and solve for remaining u and v values.
3. For each NON-BASIC (unoccupied) cell, compute: dij = cij - ui - vj
4. If all dij ≥ 0, the current solution is OPTIMAL. STOP.
5. If any dij < 0, select the most negative dij cell as the ENTERING cell.
6. Trace a STEPPING STONE path (closed loop) starting and ending at the entering cell.
7. Add/subtract quantities along the path. The minimum in the negative (-) cells is the transfer
amount.
8. Update the allocation table and repeat from Step 1.

⚠ STEPPING STONE PATH RULES:

• The path must form a CLOSED LOOP with horizontal and vertical moves only.
• The path must pass through OCCUPIED cells only (except the entering cell).
• Each row and column in the path must appear exactly TWICE (once as + and once
as −).
• The path may skip over unoccupied cells.

For educational use only Page 7

Operations Research | Transportation & Assignment Models Module 5

SECTION 4
The Assignment Model

Part C: Assignment Problem & Hungarian Method

C.1 Introduction to the Assignment Model
The Assignment Problem is a special case of the transportation problem where each supply equals 1
and each demand equals 1. It involves assigning n workers (agents) to n tasks (jobs) on a one-to-one
basis to minimize total cost or maximize total profit.

Formal Definition:
Given n agents and n tasks with cost matrix cij, find a one-to-one assignment of agents to
tasks such that:
Minimize Z = ΣΣ cij · xij where xij ∈ {0, 1}
Σj xij = 1 (each agent assigned to exactly one task)
Σi xij = 1 (each task assigned to exactly one agent)

C.2 The Hungarian Method (Step-by-Step)

Step Name Action

1 Row Subtract the minimum value in each row from all entries in that row.
Reduction

2 Column Subtract the minimum value in each column from all entries in that column.
Reduction

3 Cover Zeros Draw the MINIMUM number of horizontal and vertical lines to cover all
zeros.

4 Optimality If lines = n (matrix size), proceed to assignment (Step 6). Otherwise,

Check continue.

5 Further Find the minimum UNCOVERED value (k). Subtract k from all uncovered
Reduce cells. Add k to cells at intersections of two lines. Keep covered (non-
intersection) cells unchanged.

Return to Step 3.

6 Assign Make the optimal assignment: find rows/columns with exactly one zero.
Assign that zero, then cross out its row and column. Repeat until all
assignments are made.

For educational use only Page 8

Operations Research | Transportation & Assignment Models Module 5

C.3 Special Cases in Assignment Problems

Case Handling Procedure

Unbalanced (n ≠ m) Add dummy rows or columns with zero costs to make the matrix square (n×n).

Maximization Convert to minimization: Subtract all values from the MAXIMUM value in the
matrix. Apply Hungarian Method on the resulting matrix.

Prohibited Assign a very large cost (M or ∞) to prohibited cells to prevent them from
Assignment being selected.

Multiple Optima When multiple assignments yield the same minimum cost, all are equally
optimal. Report all optimal solutions.

For educational use only Page 9

Operations Research | Transportation & Assignment Models Module 5

SECTION 5
Excel Applications — Step-by-Step Guide

Part D: Solving Transportation & Assignment Problems in Excel

💻 PREREQUISITE: Enable Excel Solver Add-in
• Open Excel → File → Options → Add-ins
• At the bottom, select Manage: Excel Add-ins → Go
• Check 'Solver Add-in' → Click OK
• Solver will now appear under the Data tab → Analyze group

D.1 Excel Setup for Transportation Model

Use the same 3×4 example from Section 3. We will now solve it in Excel using Solver.

STEP 1: Build the Cost Matrix

In a new worksheet named 'Transport', set up your table as follows:

Cell Address Content Cell Address Content Notes

B2 Label Store 1 F2 Supply "Supply" Header

B3 Label Factory A F3 Supply A 300 Value

C3 Cost 2 B7 Demand 1 250 Value

C4 Cost 1 ... ... Continue...

💡 Excel Layout Tip: Organize your spreadsheet into 3 zones: (1) COST TABLE in rows 2-
6, (2) DECISION VARIABLES table in rows 9-14, (3) CONSTRAINTS and OBJECTIVE in
rows 16-25.

STEP 2: Set Up Decision Variables (xij)

In rows 9-14, create an identical-sized table for the decision variables (quantities to ship). Label it
clearly 'Shipments'. Leave cells C10:F12 empty — these are your changing cells for Solver.

For educational use only Page 10

Operations Research | Transportation & Assignment Models Module 5

STEP 3: Set Up Constraints

Supply constraints (in column H):
• H10: =SUM(C10:F10) [Total shipped from Factory A — must = 300]
• H11: =SUM(C11:F11) [Total shipped from Factory B — must = 400]
• H12: =SUM(C12:F12) [Total shipped from Factory C — must = 500]

Demand constraints (in row 14):

• C14: =SUM(C10:C12) [Total received at Store 1 — must = 250]
• D14: =SUM(D10:D12) [Total received at Store 2 — must = 350]
• E14: =SUM(E10:E12) [Total received at Store 3 — must = 400]
• F14: =SUM(F10:F12) [Total received at Store 4 — must = 200]

STEP 4: Set Up the Objective Function

In cell B17, enter the SUMPRODUCT formula:

=SUMPRODUCT(C3:F5, C10:F12)

This multiplies each cost (cij) by the corresponding shipment quantity (xij) and sums all
products. This is your Total Transportation Cost to minimize.

STEP 5: Configure and Run Excel Solver

9. Click the Data tab → Solver (in the Analyze group).
10. Set Objective: Click 'Set Objective' field → click cell B17 (your total cost formula).
11. Set To: Select 'Min' (minimize).
12. By Changing Variable Cells: Select C10:F12 (the 12 decision variable cells).
13. Add Constraints (click Add):

Cell Reference Operator Constraint Value Meaning

H10:H12 = F3:F5 (Supply) Supply constraints satisfied

C14:F14 = B7:E7 (Demand) Demand constraints satisfied

C10:F12 ≥ 0 Non-negativity

14. Select Solving Method: Choose 'Simplex LP' from the dropdown.
15. Click SOLVE. Solver will find the optimal solution.
For educational use only Page 11
Operations Research | Transportation & Assignment Models Module 5

16. Select 'Keep Solver Solution' and check 'Answer Report' for a summary.

✅ Reading the Solver Answer Report:

• Objective Cell Final Value: Your minimum total cost
• Variable Cells: Optimal shipment quantities for each route
• Constraints: Slack/surplus values (should all be 0 for equality constraints)
• Binding constraints indicate no slack; non-binding indicates unused capacity

For educational use only Page 12

Operations Research | Transportation & Assignment Models Module 5

D.2 Excel Setup for Assignment Model

Step-by-step guide for solving a 4×4 assignment problem (e.g., assigning 4 workers to 4 projects).

STEP 1: Create the Cost/Efficiency Matrix

Set up a 4×4 cost matrix with Workers in rows (B3:B6) and Projects in columns (C2:F2). Enter cost
values in C3:F6.

STEP 2: Create Decision Variable Matrix

In a separate area (e.g., C10:F13), create a 4×4 table for assignment variables (xij = 0 or 1). Leave
empty for Solver to fill.

STEP 3: Set Constraints for One-to-One Assignment

• Row sums (each worker assigned to exactly 1 project): H10:H13 = 1 using =SUM(C10:F10) etc.
• Column sums (each project assigned to exactly 1 worker): C15:F15 = 1 using =SUM(C10:C13)
etc.
• Binary constraint: Set C10:F13 as binary (0 or 1) — add this in Solver constraints.

STEP 4: Objective Function

=SUMPRODUCT(C3:F6, C10:F13)

STEP 5: Solver Settings for Assignment

• Set Objective: Your SUMPRODUCT cell → Min
• Changing Cells: C10:F13
• Constraints: Row sums = 1, Column sums = 1, C10:F13 = binary
• Solving Method: Select 'Simplex LP' or 'GRG Nonlinear'
• Click SOLVE

💡 BINARY CONSTRAINT TIP:

When adding the binary constraint in Solver, select the cell range C10:F13, then in the
operator dropdown select 'bin' (binary). This forces each cell to be either 0 (not assigned) or
1 (assigned).

For educational use only Page 13

Operations Research | Transportation & Assignment Models Module 5

For educational use only Page 14

Operations Research | Transportation & Assignment Models Module 5

SECTION 6
Seatwork Exercises

Seatwork Exercises
📋 Instructions: Show complete solutions for all manual methods. Label each step clearly.
For Excel portions, submit your .xlsx file with properly labeled worksheets.

SEATWORK 1 — Transportation Problem (Manual Methods)

PROBLEM: XYZ Manufacturing has three plants (P1, P2, P3) and four warehouses (W1,
W2, W3, W4). The transportation costs (in PHP per unit), supply, and demand are given
below.

W1 W2 W3 W4 Supply

P1 4 8 1 5 120

P2 7 2 3 9 80

P3 3 6 4 2 100

Demand 60 90 70 80 300

Required:
17. Verify that the problem is balanced.
18. Find the IBFS using the Northwest Corner Method. Compute the total cost.
19. Find the IBFS using the Least Cost Method. Compute the total cost.
20. Find the IBFS using Vogel's Approximation Method. Compute the total cost.
21. Apply the MODI method to the VAM solution to check for optimality. If not optimal, find the
optimal solution.
22. Compare all total costs and identify which IBFS method gave the best starting solution.

SEATWORK 2 — Unbalanced Transportation Problem

PROBLEM: A logistics company has two depots (D1, D2) with supplies of 500 and 300
units respectively. There are three retail outlets (R1, R2, R3) with demands of 200, 250, and
280 units. Unit shipping costs are given below.

For educational use only Page 15

Operations Research | Transportation & Assignment Models Module 5

R1 R2 R3 Supply

D1 5 3 7 500

D2 4 6 2 300

Demand 200 250 280

Required:
23. Identify whether supply exceeds demand or demand exceeds supply. Compute the difference.
24. Add the appropriate dummy origin or dummy destination to balance the problem.
25. Solve using Vogel's Approximation Method.
26. Apply MODI method to achieve the optimal solution.

SEATWORK 3 — Assignment Problem (Hungarian Method)

PROBLEM: A project manager must assign 4 engineers (E1-E4) to 4 tasks (T1-T4). The
matrix below shows estimated time (in days) for each engineer-task combination.

Task T1 Task T2 Task T3 Task T4

Engineer E1 12 10 15 22

Engineer E2 10 18 25 15

Engineer E3 11 17 11 19

Engineer E4 6 8 8 13

Required:
1. Apply the Hungarian Method step by step showing all iterations of the reduced matrix.
2. Draw all covering lines at each iteration. Show the minimum uncovered element used for
reduction.
3. Determine the optimal assignment and total minimum time.
4. Suppose Engineer E2 cannot be assigned Task T3 (prohibited). Show how to handle this and
re-solve.

For educational use only Page 16

Operations Research | Transportation & Assignment Models Module 5

SECTION 7
Practice Problems for Students

Practice Problems
Practice Set Instructions: These problems are designed for independent practice. Each
problem indicates whether to solve manually, using Excel, or both. Difficulty is marked as ★
(Basic), ★★ (Intermediate), or ★★★ (Advanced).

PRACTICE 1 — Transportation [Basic ★]

A bakery has two production centers (C1: 200 units/day, C2: 150 units/day) and three stores (S1: 130,
S2: 120, S3: 100 units/day). Daily delivery costs (PHP/unit) are:

S1 S2 S3

C1 6 4 9

C2 3 8 5

a) Solve using NWC and LCM. b) Find the optimal solution using MODI. c) Solve using Excel Solver
and compare.

PRACTICE 2 — Assignment [Intermediate ★★]

A call center manager must assign 5 agents (A1–A5) to 5 shifts (Sh1–Sh5). The matrix shows
performance scores (higher = better). MAXIMIZE total performance.

Sh1 Sh2 Sh3 Sh4 Sh5

A1 87 91 78 95 82

A2 75 88 92 79 96

A3 93 72 85 88 77

A4 84 95 91 83 89

A5 79 81 87 94 90

For educational use only Page 17

Operations Research | Transportation & Assignment Models Module 5

a) Convert to minimization. b) Apply Hungarian Method manually. c) Solve using Excel Solver with
binary variables. d) What is the maximum total performance score and the optimal assignment?

PRACTICE 3 — Real-World Case: Logistics Optimization [Advanced ★★★]

A pharmaceutical company distributes vaccines from 3 production sites to 5 distribution centers. The
data is as follows:

DC1 DC2 DC3 DC4 DC5 Supply

Site A 12 8 15 10 6 1,500

Site B 9 14 7 12 11 2,000

Site C 6 11 13 8 9 1,200

Demand 800 600 1,000 700 900 4,000

Additional Information: Site B cannot ship to DC2 (prohibited route). Site C has a minimum shipment
requirement of 200 units to DC4.

Required:
5. Check balance. If unbalanced, add appropriate dummy.
6. Handle the prohibited route for Site B → DC2.
7. Find the optimal solution using VAM + MODI.
8. Set up and solve in Excel Solver. Include sensitivity analysis.
9. Interpret the Sensitivity Report: identify routes with zero reduced cost.
10. Management considers increasing Site A capacity by 300 units. Using your Excel model,
determine if and how the optimal solution changes.

PRACTICE 4 — Excel Lab Exercise [All Levels]

💻 EXCEL LAB: Build a Reusable Transportation Solver Template

Create a dynamic Excel workbook named 'Transport_Solver_Template.xlsx' with the

following worksheets:

Worksheet 1 — 'NWC_Manual': Set up a 4×4 transportation table with conditional formatting to

highlight allocations. Create formulas that automatically check if supply = demand.

For educational use only Page 18

Operations Research | Transportation & Assignment Models Module 5

Worksheet 2 — 'Solver_Model': Full Solver-ready model with cost matrix, decision variables,
supply/demand totals, and objective function. Include a Reset button using a simple macro.
Worksheet 3 — 'Sensitivity': After running Solver, copy the sensitivity report here and create charts
showing (a) shadow prices for supply constraints and (b) allowable ranges for costs.
Worksheet 4 — 'Assignment': Build a complete assignment model with Hungarian Method display area
and Solver model for comparison.

⭐ Bonus Challenge:
Use Excel Data Validation to create drop-down inputs for problem size (3×3, 4×4, 5×5) and
automatically resize your model using named ranges and dynamic array formulas.

For educational use only Page 19

Operations Research | Transportation & Assignment Models Module 5

SECTION 8
Module Summary & Assessment Guide

Module Summary
Topic Key Concepts Excel Application

Transportation Model Structure, formulation, SUMPRODUCT objective, Solver

balanced/unbalanced with equality constraints

IBFS Methods NWC, LCM, VAM — trade-off Manual verification against Solver
between ease and solution quality output

Optimality MODI method, stepping stone path, Solver Answer & Sensitivity Reports
opportunity costs

Assignment Model 1-to-1 assignment, Hungarian Binary Solver, SUMPRODUCT,

Method, special cases maximization conversion

Sensitivity Analysis Shadow prices, reduced costs, Solver Sensitivity Report, what-if
allowable ranges data tables

Assessment Rubric
Criterion Excellent (4) Good (3) Satisfactory Needs
(2) Improvement (1)

Problem Formulation Correct & Minor errors Partial setup Incorrect formulation
complete

Manual Calculations All steps shown Steps shown, Some steps Steps not shown
correctly minor math missing
errors

Excel Model Solver setup Setup mostly Model has errors No Excel file submitted
perfect, results correct but attempted
match

Interpretation Clear, insightful Adequate Brief explanation No interpretation

analysis explanation only

Quick Reference: Key Formulas

Formula / Concept Expression

Objective Function Min Z = ΣΣ cij · xij

Balance Check If Σsi = Σdj: balanced; otherwise add dummy with cij = 0

IBFS Count A feasible IBFS must have exactly (m + n - 1) basic cells

For educational use only Page 20

Operations Research | Transportation & Assignment Models Module 5

MODI Optimality dij = cij - ui - vj ≥ 0 for all non-basic cells (minimization)

Excel Objective =SUMPRODUCT(cost_range, decision_variable_range)

Hungarian (Max) Subtract all values from MAX value → apply minimization algorithm

END OF MODULE 5

Transportation & Assignment Models | Operations Research

For educational use only Page 21