Operations Research | Module 2 | Page 1

MODULE II
TRANSPORTATION & ASSIGNMENT PROBLEMS
PS04EMTH30 – Operations Research
[Link]. Mathematics – Semester IV
Reference: Hamdy A. Taha, Operations Research: An Introduction, 9th Edition (Prentice-Hall)

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 2

PART A: INTRODUCTION TO OPERATIONS RESEARCH

TRANSPORTATION PROBLEMS

1. The Real-World Motivation

Let us start with a simple, concrete example to understand what a Transportation Problem is.

Suppose a company called MG Auto has three car manufacturing plants – one in Rajkot, one
in Delhi, and one in Mumbai. The company also has two major distribution centers – one in
Chennai and one in Kolkata. Every quarter (three months), the company must decide how
many cars to ship from each plant to each distribution center. The plants have limited
production capacity (called supply), and the distribution centers have specific requirements
(called demand).

The transportation costs per car differ on each route because the distances are different. The
company wants to meet all the demands of the distribution centers, use up all the supply from
the plants, and do this at the minimum total transportation cost.

This is exactly a Transportation Problem! Notice how naturally it arises in the real world.

Example (MG Auto Model) [Taha, p. 163; Lecture Notes, p. 90]: Consider MG Auto with
three plants in Rajkot, Delhi, Mumbai and two distribution centers in Chennai and Kolkata.

From / To Chennai (Dest. 1) Kolkata (Dest. 2) Supply (Cars)

Rajkot (Source 1) ₹80 per car ₹215 per car 1000
Delhi (Source 2) ₹100 per car ₹108 per car 1500
Mumbai (Source ₹102 per car ₹68 per car 1200
3)
Demand (Cars) 2300 1400 Total: 3700
Table 1: MG Auto Transportation Cost Table [Taha, p. 163; Lecture Notes, p. 91]

Observe: The total supply = 1000 + 1500 + 1200 = 3700 cars. The total demand = 2300 +
1400 = 3700 cars. When total supply equals total demand, the problem is called a Balanced
Transportation Problem.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 3

2. Formal Definition of the Transportation Problem

Definition (Transportation Model) [Taha, p. 163; Lecture Notes, p. 90]: A transportation
model consists of m sources (supply points) and n destinations (demand points). The supply
at source i is aᵢ units. The demand at destination j is b ⱼ units. The cost of transporting one unit
from source i to destination j is cᵢⱼ. The decision variable xᵢ ⱼ represents the number of units
transported from source i to destination j. The objective is to minimize the total transportation
cost while satisfying all supply and demand requirements.

3. Mathematical Formulation (LP Model)

The Transportation Problem can be written as a Linear Programming Problem (LPP) as
follows:

Minimize Z = Σᵢ Σⱼ cᵢⱼ xᵢⱼ

Subject to:

Supply constraints: Σⱼ xᵢⱼ = aᵢ for each source i = 1, 2, ..., m (Each source's supply is fully
used)

Demand constraints: Σᵢ xᵢⱼ = bⱼ for each destination j = 1, 2, ..., n (Each destination's

demand is fully met)

Non-negativity: xᵢⱼ ≥ 0 for all i and j (We cannot ship a negative quantity)

For the MG Auto example, the LP formulation would be:

Minimize Z = 80x₁₁ + 215x₁₂ + 100x₂₁ + 108x₂₂ + 102x₃₁ + 68x₃₂

Subject to: x₁₁ + x₁₂ = 1000 (Rajkot plant capacity)

x₂₁ + x₂₂ = 1500 (Delhi plant capacity)

x₃₁ + x₃₂ = 1200 (Mumbai plant capacity)

x₁₁ + x₂₁ + x₃₁ = 2300 (Chennai demand)

x₁₂ + x₂₂ + x₃₂ = 1400 (Kolkata demand)

xᵢⱼ ≥ 0 for all i, j

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 4

4. The Transportation Table

A key feature of the transportation problem is that it can be neatly represented in a table
called the Transportation Table (or Transportation Tableau). In this table:

• Rows represent sources (supply points)

• Columns represent destinations (demand points)

• Each cell (i, j) shows the unit transportation cost cᵢⱼ and the amount shipped xᵢⱼ

• The last column shows supply amounts

• The last row shows demand amounts

The transportation table is much more compact and convenient than writing out the full LP
model, especially when there are many sources and destinations.

5. Balanced vs. Unbalanced Transportation Problems

Balanced Transportation Problem: A transportation problem is said to be balanced if the
total supply equals the total demand, i.e., Σᵢ aᵢ = Σ ⱼ b ⱼ. The transportation algorithm works
directly on balanced problems.

Unbalanced Transportation Problem: If total supply does not equal total demand, the
problem is unbalanced. An unbalanced problem must be converted to a balanced one before
applying the algorithm.

There are two cases of imbalance:

Case 1 – Supply < Demand: When total supply is less than total demand, not all demand can
be met. We add a dummy source (phantom supply point) with zero transportation cost to
make up the shortfall. The demand at this dummy source equals the shortage.

Case 2 – Supply > Demand: When total supply exceeds total demand, not all supply will be
used. We add a dummy destination (phantom demand point) with zero transportation cost to
absorb the surplus supply.

Note: The transportation costs to/from dummy sources and destinations are always set to
zero, since no actual transportation takes place. [Taha, pp. 168–169; Lecture Notes, pp. 92–
93]

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 5

Example: In the MG Auto model, if the Delhi plant can only produce 1300 cars (instead of
1500), then Supply = 1000 + 1300 + 1200 = 3500 < Demand = 3700. We add a dummy plant
with capacity 200 and zero transportation cost to balance the model. [Lecture Notes, p. 92]

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 6

PART C: THE TRANSPORTATION ALGORITHM

[Taha, pp. 168–190]

1. Overview of the Algorithm

The Transportation Algorithm is a specialized version of the Simplex Method, adapted to
take advantage of the special structure of the transportation problem. It is much more
efficient than the general Simplex Method for transportation problems.

The algorithm proceeds in two main stages:

Stage 1 – Finding the Starting Basic Feasible Solution:

We start by finding an initial allocation that satisfies all supply and demand requirements
(even if it is not optimal). Three methods are available for this:

• Northwest Corner Method

• Least-Cost Method (Minimum Cost Method)

• Vogel's Approximation Method (VAM)

Stage 2 – Optimizing (Iterative Improvement):

Starting from the initial solution, we use the optimality condition of the Simplex Method to
check if the current solution can be improved. If yes, we find the entering and leaving
variables, update the solution, and repeat. We stop when no further improvement is possible.

2. Key Concept: Basic Feasible Solution

In a transportation problem with m sources and n destinations, the number of variables is m ×
n. However, because the problem has m + n constraints (m supply constraints and n demand
constraints), but only m + n – 1 of these are independent (the total supply equals total
demand, making one constraint redundant), a basic feasible solution has exactly m + n – 1
basic variables (allocated cells). All other cells are non-basic (zero allocation).

For the SunRay Transport example (3 silos, 4 mills): m + n – 1 = 3 + 4 – 1 = 6 basic

variables. So exactly 6 cells in the table will have allocations, and the remaining 12 – 6 = 6
cells will be empty (zero).

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 7

3. The SunRay Transport Problem

We will use the SunRay Transport Problem as our running example throughout this section to
illustrate all three methods and the optimization procedure.

SunRay Transport Problem [Taha, p. 170]: SunRay Transport Company ships truckloads
of grain from three silos (sources) to four mills (destinations). The supply at each silo,
demand at each mill, and unit transportation cost are given below.

Source \ Dest. Mill 1 Mill 2 Mill 3 Mill 4 Supply

(truckloads)
Silo 1 10 2 20 11 15
Silo 2 12 7 9 20 25
Silo 3 4 14 16 18 10
Demand 5 15 15 15 Total: 50
(truckloads)
Table 2: SunRay Transport Model [Taha, p. 170;] (Costs in hundreds of ₹)

Observe: Total supply = 15 + 25 + 10 = 50. Total demand = 5 + 15 + 15 + 15 = 50. The

problem is balanced.

4. Method 1: The Northwest Corner Method

[Taha, p. 171; Lecture Notes, p. 94]

4.1 Why is it called 'Northwest Corner'?

The method gets its name from the starting point: the top-left corner of the transportation
table. In map terminology, 'northwest' refers to top-left. The method makes allocations
starting from this corner and systematically moves toward the bottom-right corner.

4.2 Steps of the Northwest Corner Method

Step 1: Begin at the northwest (top-left) corner cell (1, 1) of the transportation table.

Step 2: Allocate as much as possible to the current cell – this is the minimum of the
remaining supply of the current row and the remaining demand of the current column.

Step 3: Adjust the supply and demand by subtracting the allocated amount from both.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 8

Step 4: If the row's supply becomes zero, move down to the next row. If the column's
demand becomes zero, move right to the next column. If both become zero simultaneously,
cross out only one (say the row) and leave a zero supply/demand in the other.

Step 5: Repeat Steps 2–4 until all supplies and demands are satisfied (i.e., you reach the
bottom-right corner).

4.3 Application to SunRay Problem

Applying the Northwest Corner Method to the SunRay problem step by step:

• Start at cell (1,1): Supply of Silo 1 = 15, Demand of Mill 1 = 5. Allocate min(15, 5) = 5.
Silo 1 supply becomes 10, Mill 1 demand becomes 0. Cross out Column 1. Move right.

• Cell (1,2): Supply of Silo 1 = 10, Demand of Mill 2 = 15. Allocate min(10, 15) = 10. Silo
1 supply becomes 0, Mill 2 demand becomes 5. Cross out Row 1. Move down.

• Cell (2,2): Supply of Silo 2 = 25, Demand of Mill 2 = 5. Allocate min(25, 5) = 5. Silo 2
supply becomes 20, Mill 2 demand becomes 0. Cross out Column 2. Move right.

• Cell (2,3): Supply of Silo 2 = 20, Demand of Mill 3 = 15. Allocate min(20, 15) = 15. Silo
2 supply becomes 5, Mill 3 demand becomes 0. Cross out Column 3. Move right.

• Cell (2,4): Supply of Silo 2 = 5, Demand of Mill 4 = 15. Allocate min(5, 15) = 5. Silo 2
supply becomes 0, Mill 4 demand becomes 10. Cross out Row 2. Move down.

• Cell (3,4): Supply of Silo 3 = 10, Demand of Mill 4 = 10. Allocate min(10, 10) = 10. Both
become 0. Done.

Mill 1 Mill 2 Mill 3 Mill 4 Supply

Silo 1 x₁₁ = 5 x₁₂ = 10 – – 15

Silo 2 – x₂₂ = 5 x₂₃ = 15 x₂₄ = 5 25
Silo 3 – – – x₃₄ = 10 10
Demand 5 15 15 15 50
Table 3: Northwest Corner Starting Solution

Starting solution: x₁₁ = 5, x₁₂ = 10, x₂₂ = 5, x₂₃ = 15, x₂₄ = 5, x₃₄ = 10 (exactly 6 = m + n
– 1 basic variables)

Total cost = 5×10 + 10×2 + 5×7 + 15×9 + 5×20 + 10×18 = 50 + 20 + 35 + 135 + 100 + 180 =
₹520 hundred

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 9

Note: The Northwest Corner Method is simple and easy to apply but generally gives the
worst starting solution among the three methods, because it ignores transportation costs
entirely and just follows a mechanical path. [Taha, p. 172

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 10

5. Method 2: The Least-Cost Method (Minimum Cost Method)

[Taha, p. 173; Lecture Notes, p. 95]

5.1 The Idea Behind This Method

Unlike the Northwest Corner Method, the Least-Cost Method actually looks at the
transportation costs before making allocations. The basic idea is: always allocate as much as
possible to the cheapest available route. This way, we use the most economical routes first,
leading to a better starting solution.

5.2 Steps of the Least-Cost Method

Step 1: Find the cell with the smallest unit transportation cost in the entire table (break ties
arbitrarily).

Step 2: Allocate as much as possible to this cell – the minimum of the remaining supply of
that row and the remaining demand of that column.

Step 3: Adjust supply and demand, and cross out the satisfied row or column. If both are
satisfied simultaneously, cross out only one.

Step 4: From the remaining uncrossed cells, again find the cell with the smallest unit cost and
repeat Steps 2–3.

Step 5: Continue until exactly one row or column remains uncrossed. The remaining
allocations are made for the last uncrossed row or column.

5.3 Application to SunRay Problem

Applying the Least-Cost Method step by step:

• The cheapest cell in the table is (1,2) with cost 2. Allocate min(15, 15) = 15. Both Silo 1
supply and Mill 2 demand are exactly satisfied. Cross out Column 2 (arbitrary choice).
Silo 1 supply becomes 0. x₁₂ = 15.

• Next cheapest uncrossed cell is (3,1) with cost 4. Allocate min(10, 5) = 5. Mill 1 demand
satisfied. Cross out Column 1. Silo 3 supply becomes 5. x₃₁ = 5.

• Next cheapest is (2,3) with cost 9. Allocate min(25, 15) = 15. Mill 3 demand satisfied.
Cross out Column 3. Silo 2 supply becomes 10. x₂₃ = 15.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 11

• Only Column 4 remains. Cheapest available cell in Column 4 with supply: (1,4) with cost
11 but Silo 1 has 0 supply, so x₁₄ = 0 (degenerate). Silo 2: allocate min(10, 15) = 10. x₂₄
= 10. Mill 4 demand becomes 5. Then Silo 3: allocate min(5, 5) = 5. x₃₄ = 5. Done.

Mill 1 Mill 2 Mill 3 Mill 4 Supply

Silo 1 – x₁₂ = 15 – x₁₄ = 0* 15

Silo 2 – – x₂₃ = 15 x₂₄ = 10 25
Silo 3 x₃₁ = 5 – – x₃₄ = 5 10
Demand 5 15 15 15 50
Table 4: Least-Cost Method Starting Solution [Lecture Notes, p. 96] (* degenerate allocation)

Total cost = 15×2 + 0×11 + 15×9 + 10×20 + 5×4 + 5×18 = 30 + 0 + 135 + 200 + 20 + 90 =
₹475 hundred

Note: The Least-Cost Method gives a better starting solution (₹475) compared to the
Northwest Corner Method (₹520). This is because it considers costs when making
allocations. [Lecture Notes, p. 96]

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 12

6. Method 3: Vogel's Approximation Method (VAM)

[Taha, pp. 174–176; Lecture Notes, pp. 96–99]

6.1 Why VAM is Better

Vogel's Approximation Method (VAM) is generally the best of the three methods for finding
a starting solution. It gives a starting solution that is often equal to or very close to the
optimal solution, which means fewer iterations are needed to reach the optimum.

The key insight in VAM is the concept of a penalty. The penalty for a row or column is the
difference between the two cheapest costs in that row or column. This penalty represents the
cost we would incur if we are forced to use the second-cheapest route instead of the cheapest
one. VAM allocates as much as possible to the cheapest cell in the row or column with the
highest penalty. This approach minimizes the 'regret' of not being able to use the best route.

6.2 Steps of VAM

Step 1: For each row, compute the row penalty = (2nd smallest cost in row) – (smallest cost
in row). Similarly for each column. These penalties measure the 'opportunity cost' or 'regret'
of not using the cheapest route.

Step 2: Identify the row or column with the largest penalty (break ties arbitrarily). In that row
or column, allocate as much as possible to the cell with the smallest unit cost.

Step 3: Adjust supply and demand, cross out the satisfied row or column (as in the Least-
Cost Method).

Step 4: Recompute penalties for the remaining rows and columns (excluding crossed-out
rows and columns) and go back to Step 2.

Step 5: Stop when only one uncrossed row or column remains. Use the Least-Cost Method
for final allocation.

6.3 Application to SunRay Problem

Let us compute the initial penalties for the SunRay problem:

Mill 1 Mill 2 Mill 3 Mill 4 Supply Row Penalty

(c=10) (c=2) (c=20) (c=11)
Silo 1 10 2 20 11 15 11–2 = 9
←LARGEST
Silo 2 12 7 9 20 25 9–7 = 2

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 13

Mill 1 Mill 2 Mill 3 Mill 4 Supply Row Penalty

(c=10) (c=2) (c=20) (c=11)
Silo 3 4 14 16 18 10 14–4 = 10
←2nd
Col. 10–4=6 7–2=5 16–9=7 18–
Penalty 11=7
Table 5: Initial VAM Penalties

The largest penalty is in Row 1 (Silo 1) with penalty = 9. In Row 1, the smallest cost is 2 (at
cell (1,2) – Mill 2). Allocate min(15, 15) = 15. Both Silo 1 supply and Mill 2 demand are
exactly satisfied. Cross out Column 2. x₁₂ = 15.

Recompute penalties with Column 2 crossed out:

Mill 1 Mill 3 Mill 4 Supply Row Penalty

(c=10) (c=20) (c=11)
Silo 1 10 20 11 0 –
(crossed
)
Silo 2 12 9 20 25 20–9 = 11
←LARGEST
Silo 3 4 16 18 10 16–4 = 12
←LARGEST
Col. 12–4=8 16–9=7 20–
Penalty 11=9
Table 6: VAM Penalties after 1st assignment

Row 3 (Silo 3) has the largest penalty = 12. In Row 3, the smallest cost is 4 (at cell (3,1) –
Mill 1). Allocate min(10, 5) = 5. Mill 1 demand satisfied. Cross out Column 1. Silo 3 supply
becomes 5. x₃₁ = 5.

Continuing this process, next largest penalty is in Row 2 (Silo 2) with penalty 11. Cheapest in
Row 2 (uncrossed columns 3 and 4): Mill 3 with cost 9. Allocate min(25, 15) = 15. Mill 3
satisfied. Cross out Column 3. Silo 2 supply becomes 10. x₂₃ = 15.

Only Mill 4 (Column 4) remains uncrossed. Apply Least-Cost Method: Cheapest available
cell is (1,4) with cost 11 but Silo 1 has 0 supply → x₁₄ = 0. Next is (3,4) with cost 18, Silo 3
has 5 → x₃₄ = 5. Finally x₂₄ = 10 (remaining demand and supply both = 10).

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 14

Mill 1 Mill 2 Mill 3 Mill 4 Supply

Silo 1 – x₁₂ = 15 – x₁₄ = 0* 15

Silo 2 – – x₂₃ = 15 x₂₄ = 10 25
Silo 3 x₃₁ = 5 – – x₃₄ = 5 10
Demand 5 15 15 15 50
Table 7: VAM Starting Solution

Total cost = 15×2 + 0×11 + 15×9 + 10×20 + 5×4 + 5×18 = 30 + 0 + 135 + 200 + 20 + 90 =
₹475 hundred

Note: In this case, VAM and Least-Cost Method give the same starting cost of ₹475, which is
better than the Northwest Corner starting cost of ₹520. In general, VAM is expected to give
the best starting solution, but this is not guaranteed in every case.

Method Starting Cost (₹ Number of Basic Quality

hundred) Variables
Northwest Corner 520 6 (= m+n−1) Worst
Method (ignores
costs)
Least-Cost Method 475 6 (= m+n−1) Better (uses
costs)
Vogel's Approximation 475 6 (= m+n−1) Best
(VAM) (minimizes
regret)
Table 8: Comparison of Starting Solution Methods

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 15

7. Stage 2: Finding the Optimal Solution (Method of Multipliers)

[Taha, pp. 177–185]

7.1 Overview
Once we have a starting basic feasible solution, we use the transportation equivalent of the
Simplex Method to optimize it. The key steps are:

• Use the Method of Multipliers (u-v method) to check optimality (find if any non-basic
cell has a negative reduced cost for a minimization problem).

• If the optimality condition is not met, determine the entering variable (most positive
reduced cost for minimization problems in standard form).

• Construct a closed loop to determine the leaving variable.

• Update the solution. Repeat until optimality.

7.2 The Method of Multipliers (u-v Method)

For each basic variable xᵢⱼ, we define multipliers (dual variables) uᵢ for each row i and v ⱼ for
each column j such that:

uᵢ + vⱼ = cᵢⱼ for every basic variable (i, j)

Since there are m + n – 1 basic variables but m + n multipliers (m values of u and n values of
v), we have one degree of freedom. We set one multiplier to zero (typically u₁ = 0) and solve
for the rest.

Once all multipliers are found, we compute the reduced cost (opportunity cost) for each non-
basic cell (i, j):

d̄ ᵢⱼ = uᵢ + vⱼ – cᵢⱼ for every non-basic (i, j)

Since this is a minimization problem:

• If all d̄ ᵢⱼ ≤ 0: The current solution is optimal. STOP.

• If any d̄ ᵢⱼ > 0: The current solution can be improved. Choose the cell with the most
positive d̄ ᵢⱼ as the entering variable.

7.3 Iteration 1: Starting from Northwest Corner Solution

We use the Northwest Corner starting solution: x₁₁ = 5, x₁₂ = 10, x₂₂ = 5, x₂₃ = 15, x₂₄ =
5, x₃₄ = 10.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 16

Setting u₁ = 0 and solving the u-v equations for all basic cells:

Basic Cell (i,j) u-v Equation Solution

x₁₁ = 5 u₁ + v₁ = 10 u₁ = 0 → v₁ = 10
x₁₂ = 10 u₁ + v₂ = 2 u₁ = 0 → v₂ = 2
x₂₂ = 5 u₂ + v₂ = 7 v₂ = 2 → u₂ = 5
x₂₃ = 15 u₂ + v₃ = 9 u₂ = 5 → v₃ = 4
x₂₄ = 5 u₂ + v₄ = 20 u₂ = 5 → v₄ = 15
x₃₄ = 10 u₃ + v₄ = 18 v₄ = 15 → u₃ = 3
Table 9: u-v Multipliers for Iteration 1

Now compute d̄ ᵢⱼ = uᵢ + vⱼ – cᵢⱼ for all non-basic cells:

Non-basic Cell uᵢ + vⱼ − cᵢⱼ Value

x₁₃ (Silo 1 → Mill 3) 0 + 4 − 20 −16
x₁₄ (Silo 1 → Mill 4) 0 + 15 − 11 +4
x₂₁ (Silo 2 → Mill 1) 5 + 10 − 12 +3
x₃₁ (Silo 3 → Mill 1) 3 + 10 − 4 +9 ← Most
positive
(ENTERING)
x₃₂ (Silo 3 → Mill 2) 3 + 2 − 14 −9
x₃₃ (Silo 3 → Mill 3) 3 + 4 − 16 −9
Table 10: Reduced Costs for Iteration 1

Since x₃₁ has the most positive reduced cost (+9), it is the entering variable. This means: by
shipping one truckload from Silo 3 to Mill 1 (currently unused route), we reduce the total cost
by ₹9 hundred per truckload.

7.4 The Closed Loop and Leaving Variable

To bring x₃₁ into the solution, we must construct a closed loop. A closed loop is a path that:

• Starts at the entering variable cell (3,1)

• Alternates between horizontal and vertical moves

• Touches only basic cells (allocated cells) at the corner points

• Returns to the starting cell

The closed loop for x₃₁ is: (3,1) → (1,1) → (1,2) → (2,2) → (2,4) → (3,4) → (3,1)

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 17

Wait – actually, let us find the correct minimal loop. The loop is: (3,1) → (1,1) → (1,2) →
(2,2) → (3,4) is not right. The correct closed loop is: (3,1)[+θ] → (1,1)[−θ] → (1,2)[+θ] →
(2,2)[−θ] → (2,4)[+θ] → (3,4)[−θ] → back.

We assign +θ to the entering cell and alternately subtract and add θ to corner cells. The
maximum value of θ is limited by the requirement that all allocations remain non-negative:

• x₁₁ = 5 − θ ≥ 0 → θ ≤ 5

• x₂₂ = 5 − θ ≥ 0 → θ ≤ 5

• x₃₄ = 10 − θ ≥ 0 → θ ≤ 10

Therefore, θ = min(5, 5, 10) = 5. Both x₁₁ and x₂₂ reach zero simultaneously. We choose
x₁₁ as the leaving variable (arbitrary tie-breaking). Cost improvement = 9 × 5 = ₹45
hundred. New cost = 520 – 45 = ₹475 hundred.

7.5 Iteration 2 and Optimal Solution

After updating, the new basic variables are: x₃₁ = 5, x₁₂ = 15, x₂₃ = 15, x₂₄ = 5+5 = 10...
(after loop adjustment).

Continuing the iterations (the full details are in the lecture notes, pp. 101–103), after two
more iterations we reach the optimal solution:

From Silo To Mill Number of Cost per Truckload (₹ Total Cost (₹

Truckloads hundred) hundred)
Silo 1 Mill 2 5 2 10
Silo 1 Mill 4 10 11 110
Silo 2 Mill 2 10 7 70
Silo 2 Mill 3 15 9 135
Silo 3 Mill 1 5 4 20
Silo 3 Mill 4 5 18 90
OPTIMAL TOTAL 435
Table 11: Optimal Solution to SunRay Transport Problem

Optimal Cost = ₹435 hundred = ₹43,500

Note: We know the solution is optimal because all reduced costs d̄ ᵢⱼ = uᵢ + vⱼ – cᵢⱼ ≤ 0 for all
non-basic cells. No further improvement is possible.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 18

PART D: ASSIGNMENT PROBLEMS

[Taha, Chapter 5, pp. 197–215]

1. Introduction and Real-World Motivation

Consider the following practical situation: You are the head of a department and you have
four workers (say A, B, C, D) who need to be assigned to four different jobs (say Job 1, Job
2, Job 3, Job 4). Each worker has different skills, so the cost (or time) of completing each job
varies from worker to worker. The question is: how should you assign workers to jobs so that
the total cost is minimized?

This is the essence of an Assignment Problem. Notice that each worker does exactly one job,
and each job is done by exactly one worker. This one-to-one matching is the defining feature
of an assignment problem.

Other real-world examples of assignment problems:

• Assigning machines to manufacturing tasks to minimize production time

• Assigning ships to ports to minimize idle time

• Assigning sales representatives to territories to maximize sales revenue

• Assigning teachers to classrooms to minimize travel time

• Matching students to projects in a course to optimize learning outcomes

2. Formal Definition of the Assignment Problem

Definition (Assignment Model) [Taha, p. 197; Lecture Notes, p. 103]: The classical
assignment problem involves assigning n workers to n jobs on a one-to-one basis. Let cᵢ ⱼ be
the cost of assigning worker i to job j. The decision variable xᵢ ⱼ = 1 if worker i is assigned to
job j, and xᵢⱼ = 0 otherwise. The goal is to find a complete assignment of workers to jobs that
minimizes total cost.

3. Mathematical Formulation (LP Model)

The Assignment Problem is formulated as follows:

Minimize Z = Σᵢ Σⱼ cᵢⱼ xᵢⱼ

Subject to:

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 19

Row constraints (each worker does exactly one job): Σⱼ xᵢⱼ = 1 for i = 1, 2, ..., n

Column constraints (each job is done by exactly one worker): Σᵢ xᵢⱼ = 1 for j = 1, 2, ..., n

Binary constraints: xᵢⱼ = 0 or 1 for all i, j

4. Relationship Between Assignment and Transportation Problems

The Assignment Problem is a special case of the Transportation Problem where:

• Workers correspond to sources (m = n sources)

• Jobs correspond to destinations (n destinations)

• Supply at each source = 1 (each worker can do exactly one job)

• Demand at each destination = 1 (each job needs exactly one worker)

• Cost of 'transporting' worker i to job j is cᵢⱼ

Since all supply and demand amounts equal 1, the transportation algorithm could solve the
assignment problem. However, this special structure allows a much simpler and more
efficient algorithm: the Hungarian Method.

5. The Assignment Table

Just as the transportation problem has a transportation table, the assignment problem is
represented in an Assignment Table (also called a cost matrix):

Workers \ Jobs Job 1 Job 2 Job 3 ... Job n

Worker 1 c₁₁ c₁₂ c₁₃ ... c₁ₙ
Worker 2 c₂₁ c₂₂ c₂₃ ... c₂ₙ
Worker 3 c₃₁ c₃₂ c₃₃ ... c₃ₙ
... Worker n cₙ₁ cₙ₂ cₙ₃ ... cₙₙ
Table 12: General Assignment Model

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 20

6. The Hungarian Method

[Taha, pp. 198–208]

6.1 The Key Theorem Behind Hungarian Method

The Hungarian Method is based on the following fundamental theorem from combinatorics
and linear programming:

Theorem (Optimality of Reduced Cost Matrix): If a constant is added to or subtracted

from every element of any row or column of the cost matrix, the optimal assignment remains
unchanged. The total cost changes by that constant, but the optimal assignment (which cell
gets xᵢⱼ = 1) does not change.

This theorem allows us to subtract values from rows and columns to create zeros in the cost
matrix without changing the optimal assignment. An optimal assignment exists among the
zero elements if we can find an assignment that covers all rows and all columns using only
zero-cost cells.

6.2 Steps of the Hungarian Method

Step 1 – Row Reduction: For each row i, find the minimum element pᵢ and subtract it from
every element in that row. This creates at least one zero in each row.

Step 2 – Column Reduction: In the matrix obtained after Step 1, find the minimum element
qⱼ in each column j and subtract it from every element in that column. This creates at least
one zero in each column.

Step 3a – Find Optimal Assignment: Try to find a complete feasible assignment using only
zero-element cells (i.e., an assignment where xᵢⱼ = 1 only when the reduced cost is 0). If
successful, this is the optimal assignment – STOP.

Step 3b – Additional Reduction (if Step 3a fails): If no complete zero-element assignment

can be found:

• Draw the minimum number of horizontal and vertical lines to cover all zero elements in
the matrix.

• Find the smallest uncovered element (call it d).

• Subtract d from every uncovered element.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 21

• Add d to every element that lies at an intersection of two covering lines (double-covered
elements).

• Repeat Step 3a with the new matrix. If still no complete assignment, repeat Step 3b.

6.3 Example 1: 3×3 Assignment Problem (DOMSPU Model)

[Taha, p. 199; Lecture Notes, p. 105]
Problem Statement: The Department of Mathematics, SPU is renovating the Assembly Hall.
There are three types of jobs: Flooring, Painting, and Furniture work. Three workers (A, B,
C) are available. The cost (in ₹ thousands) of each worker doing each job is given below.
Find the optimal assignment.

Worker \ Job Flooring (Job 1) Painting (Job 2) Furniture (Job 3)

Worker A ₹15 ₹10 ₹9
Worker B ₹9 ₹15 ₹10
Worker C ₹10 ₹12 ₹8
Table 13: DOMSPU Assignment Problem

Step 1: Row Reduction

Row minima: p₁ = min(15, 10, 9) = 9; p₂ = min(9, 15, 10) = 9; p₃ = min(10, 12, 8) = 8

Subtract 9 from Row A, 9 from Row B, 8 from Row C:

Worker \ Job Flooring Painting Furniture Row Min

Subtracted
Worker A 15−9 = 6 10−9 = 1 9−9 = 0 9
Worker B 9−9 = 0 15−9 = 6 10−9 = 1 9
Worker C 10−8 = 2 12−8 = 4 8−8 = 0 8
Table 14: After Row Reduction

Step 2: Column Reduction

Column minima after row reduction: q₁ = min(6, 0, 2) = 0; q₂ = min(1, 6, 4) = 1; q₃ = min(0,

1, 0) = 0

Subtract 0 from Column 1, 1 from Column 2, 0 from Column 3:

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 22

Worker \ Job Flooring Painting Furniture

Worker A 6 1−1 = 0 0
Worker B 0 6−1 = 5 1
Worker C 2 4−1 = 3 0
Table 15: After Column Reduction

Step 3a: Find Assignment from Zero Elements

Look for a complete assignment using only the zero cells:

• Worker A has zeros in Painting (0) and Furniture (0)

• Worker B has zero in Flooring (0)

• Worker C has zero in Furniture (0)

If Worker A takes Furniture (0), then Worker C has no zero left. So Worker A must take
Painting. Then Worker C takes Furniture. Worker B takes Flooring. This gives a complete
assignment!

Assignment Worker Job Cost from Original

Table
1 Worker A Painting ₹10 thousand
2 Worker B Flooring ₹9 thousand
3 Worker C Furniture ₹8 thousand
TOTAL ₹27 thousand
OPTIMAL
COST
Table 16: Optimal Assignment for DOMSPU

The optimal cost can also be computed as: (p₁ + p₂ + p₃) + (q₁ + q₂ + q₃) = (9+9+8) +
(0+1+0) = 26 + 1 = ₹27 thousand.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 23

6.4 Example 2: 4×4 Assignment Problem (with additional Step 3b)

[Taha, p. 202]
This example illustrates Step 3b (additional reduction) which is needed when the zero
elements after Steps 1 and 2 do not yield a complete assignment.

Problem Statement: Four workers (A, B, C, D) are to be assigned to four jobs (1, 2, 3, 4)
with costs given below:

Worker \ Job Job 1 Job 2 Job 3 Job 4

Worker A ₹1 ₹4 ₹6 ₹3
Worker B ₹9 ₹7 ₹10 ₹9
Worker C ₹4 ₹5 ₹11 ₹7
Worker D ₹8 ₹7 ₹8 ₹5
Table 17: 4×4 Assignment Cost Matrix

Step 1: Row Reduction

Row minima: p₁ = 1 (Row A), p₂ = 7 (Row B), p₃ = 4 (Row C), p₄ = 5 (Row D)

Worker \ Job Job 1 Job 2 Job 3 Job 4

Worker A 1−1=0 4−1=3 6−1=5 3−1=2
Worker B 9−7=2 7−7=0 10−7=3 9−7=2
Worker C 4−4=0 5−4=1 11−4=7 7−4=3
Worker D 8−5=3 7−5=2 8−5=3 5−5=0
Table 18: After Row Reduction

Step 2: Column Reduction

Column minima after row reduction: q₁ = 0, q₂ = 0, q₃ = 3, q₄ = 0

Subtract 0 from Col 1, 0 from Col 2, 3 from Col 3, 0 from Col 4:

Worker \ Job Job 1 Job 2 Job 3 Job 4

Worker A 0 3 5−3=2 2
Worker B 2 0 3−3=0 2
Worker C 0 1 7−3=4 3
Worker D 3 2 3−3=0 0
Table 19: Reduced Cost Matrix after Steps 1 & 2

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 24

Step 3a: Check for Complete Zero Assignment

Zero cells: (A,1), (B,2), (B,3), (C,1), (D,3), (D,4). Let us try to find a complete assignment:

• If A → Job 1: Then C cannot use Job 1. C has no other zero.

• If A → nothing (no zero in row A except Job 1), same problem.

• If B → Job 2: Then D has no zero in Job 2. D can use Job 3 or Job 4.

• If B → Job 3 and D → Job 4: Then A must use Job 1 and C has no zero. Fails.

No complete zero assignment can be found. We proceed to Step 3b.

Step 3b: Additional Reduction

Draw the minimum number of lines to cover all zeros:

• Line 1: Cover Column 1 (covers zeros in A1 and C1)

• Line 2: Cover Row B (covers zeros in B2 and B3)

• Line 3: Cover Row D (covers zeros in D3 and D4)

These 3 lines cover all zeros: (A1), (B2), (B3), (C1), (D3), (D4). The minimum number of
lines = 3.

Uncovered elements (not on any line): A2=3, A3=2, A4=2, C2=1, C3=4, C4=3

Smallest uncovered element = d = 1 (at C2)

Subtract 1 from every uncovered element. Add 1 to every intersection (doubly-covered)

element:

• Doubly covered: B1 (Row B ∩ Col 1), D1 (Row D ∩ Col 1)

• Singly covered (subtract 1): everything else uncovered

Worker \ Job Job 1 (covered) Job 2 Job 3 Job 4

(uncovered) (uncovered) (uncovered)
A (uncovered) 0+0=0* 3−1=2 2−1=1 2−1=1
B (covered) 2+1=3 0 0 2
C (uncovered) 0* 1−1=0 4−1=3 3−1=2
D (covered) 3+1=4 2 0 0
Table 20: Revised Cost Matrix after Step 3b (*unchanged covered zeros)

Step 3a again: Find Complete Zero Assignment

Department of Computing and Artificial Intelligence MLMCE
 Operations Research | Module 2 | Page 25

New zero cells: (A,1), (B,2), (B,3), (C,1), (C,2), (D,3), (D,4)

Try to find a complete assignment:

• A → Job 1 (zero at A1)

• C → Job 2 (zero at C2, since A took Job 1, C can't use C1)

• B → Job 3 (zero at B3)

• D → Job 4 (zero at D4)

This gives a complete assignment!

Assignment Worker Job Original Cost

1 Worker A Job 1 ₹1
2 Worker B Job 3 ₹10
3 Worker C Job 2 ₹5
4 Worker D Job 4 ₹5
TOTAL ₹21
OPTIMAL
COST
Table 21: Optimal Assignment for 4×4 Problem

Verify: Total cost = (p₁+p₂+p₃+p₄) + (q₁+q₂+q₃+q₄) + d = (1+7+4+5) + (0+0+3+0) + 1 =

17 + 3 + 1 = ₹21 ✓

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 26

PART E: SPECIAL CASES AND IMPORTANT CONCEPTS

1. Degeneracy in Transportation Problems

[Taha, pp. 185–186]
Degeneracy: A transportation problem is said to be degenerate if the number of basic
variables (allocated cells) is less than m + n – 1. This can occur when two cells
simultaneously reach zero during an allocation step.

In the Least-Cost Method example for SunRay, when we allocated x₁₂ = 15, both Silo 1's
supply (15) and Mill 2's demand (15) became zero simultaneously. We needed to artificially
include x₁₄ = 0 as a degenerate basic variable to maintain m + n – 1 = 6 basic variables. A
degenerate basic variable has value zero but is still counted as a basic (allocated) cell.

Why does degeneracy matter? Because the Method of Multipliers requires exactly m + n – 1
basic variables to determine all the u and v values. Without a degenerate cell, we would have
too few equations to solve for all multipliers.

Handling Degeneracy: Simply add an allocation of zero (ε → 0, an infinitesimally small

quantity) to an appropriate empty cell. This cell is treated as a basic variable with zero
allocation.

2. Unbalanced Assignment Problems

When the number of workers does not equal the number of jobs, the assignment matrix is not
square. This is handled as follows:

More workers than jobs (m > n): Add dummy job columns with cost 0. The workers
assigned to the dummy job will be idle.

More jobs than workers (n > m): Add dummy worker rows with cost 0. The jobs assigned
to dummy workers will be left undone (or outsourced).

After adding dummy rows or columns, the Hungarian Method is applied as normal.

3. Maximization Assignment Problems

Sometimes the goal is to maximize total profit (or efficiency) instead of minimizing cost. The
Hungarian Method can be adapted by converting the maximization problem to a
minimization problem:

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 27

Method: Let M = maximum element in the entire profit matrix. Replace each element cᵢ ⱼ by
M – cᵢⱼ. This creates a cost matrix where the optimal assignment (minimum cost) corresponds
to the maximum profit in the original problem.

Alternatively: Multiply the entire profit matrix by –1 and apply the Hungarian Method for
minimization. The same assignment will give the maximum profit.

4. Comparison: Transportation vs. Assignment Problems

Feature Transportation Problem Assignment Problem

Nature Goods shipped from sources to Workers (resources) assigned to jobs on
destinations in varying quantities a one-to-one basis
Supply/ aᵢ ≥ 1 (any positive integer) Supply = Demand = 1 for each
Demand source/destination
Variables xᵢⱼ ≥ 0 (continuous) xᵢⱼ = 0 or 1 (binary)
Matrix Shape m × n (not necessarily square) n × n (always square, or made square)
Solution Northwest Corner / Least Cost / VAM + Hungarian Method (steps 1, 2, 3a, 3b)
Method u-v Method
Starting Multiple methods needed Direct from Hungarian Method
Solution
Special Case? General LP model Special case of Transportation Problem
Table 22: Comparison of Transportation and Assignment Problems

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 28

PART F: REAL-WORLD APPLICATIONS

1. Applications of Transportation Models

1. Supply Chain Management: Deciding which factory should supply which retail store to
minimize shipping costs. This is exactly the classical transportation problem. Companies like
Amazon and Walmart use transportation models daily.

2. Production Planning: When a company has multiple production plants running in

different months (time periods play the role of sources) and the products must meet demand
in future months (time periods as destinations), transportation models help in optimal
planning.

3. Agricultural Planning: Distributing agricultural produce from farming regions (sources)

to processing centers or markets (destinations) at minimum transportation cost.

4. Military Logistics: Transporting troops, equipment, and supplies from bases (sources) to
operational zones (destinations) at minimum cost/time.

5. Energy Distribution: Routing electricity from power plants to substations, or distributing

fuel from refineries to service stations.

2. Applications of Assignment Models

1. Personnel Assignment: Assigning employees to jobs, posts, or departments to optimize
performance and minimize cost. For example, assigning bank officers to different branches.

2. Machine-Job Scheduling: Assigning machines to jobs to minimize total production time

or setup cost. Used extensively in manufacturing scheduling.

3. Project Allocation: Assigning project teams to different projects to minimize project

completion time or resource usage.

4. Travel Salesman Simplification: Some routing problems can be decomposed into

assignment problems.

5. Matching Problems: Matching medical interns to hospitals, students to universities

(admissions), or buyers to sellers in two-sided markets.

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 29

PART G: MODULE SUMMARY AND EXAMINATION TIPS

1. Module Summary
This module covered two important special types of Linear Programming Problems:

Transportation Problems:

• A transportation problem involves m sources and n destinations, where goods are shipped
at minimum total cost while satisfying all supply and demand requirements.

• A balanced problem has total supply = total demand. Unbalanced problems are made
balanced by adding dummy sources or destinations with zero cost.

• Three methods find a starting basic feasible solution: Northwest Corner Method
(simplest, worst), Least-Cost Method (better), VAM (best).

• The optimal solution is found using the Method of Multipliers (u-v method) combined
with closed-loop adjustments.

• A basic feasible solution always has exactly m + n – 1 basic variables. Degeneracy occurs
when this count falls short.

Assignment Problems:

• An assignment problem involves assigning n workers to n jobs on a one-to-one basis to

minimize total cost.

• It is a special case of the transportation problem where all supply and demand values
equal 1.

• The Hungarian Method solves assignment problems efficiently in three steps: row
reduction, column reduction, and finding a complete zero-element assignment (with
additional reduction if needed).

• Unbalanced problems (unequal workers and jobs) are handled by adding dummy rows or
columns with zero cost.

• Maximization problems are converted to minimization by replacing each element with (M

– cᵢⱼ).

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 30

2. Key Formulas and Rules

Concept Formula / Rule

Number of basic variables m + n – 1 (for balanced m×n transportation problem)
Feasibility check (balanced) Σᵢ aᵢ = Σⱼ bⱼ (total supply = total demand)
u-v equations (for basic cells) uᵢ + vⱼ = cᵢⱼ (set u₁ = 0 to start)
Reduced cost (non-basic cells) d̄ ᵢⱼ = uᵢ + vⱼ − cᵢⱼ
Optimality condition (minimization) d̄ ᵢⱼ ≤ 0 for all non-basic cells → current solution is optimal
Entering variable Non-basic cell with most positive d̄ ᵢⱼ
Optimal assignment cost (Hungarian) (Σᵢ pᵢ) + (Σⱼ qⱼ) + (sum of d values used in Step 3b)
Maximization → Minimization Replace cᵢⱼ by (M – cᵢⱼ) where M = max of all elements
Table 23: Key Formulas Summary

3. Step-by-Step Problem-Solving Guide for Examinations

For Transportation Problems:

Step 1: Check if problem is balanced (total supply = total demand). If not, add dummy
source or destination.

Step 2: Set up the transportation table with all costs, supplies, and demands.

Step 3: Find initial basic feasible solution using VAM (preferred for exams as it gives better
starting point).

Step 4: Verify that you have exactly m+n−1 allocated cells. If degenerate, add ε to an
appropriate empty cell.

Step 5: Apply the u-v Method: Set u₁ = 0, solve for all u and v values from basic cell
equations.

Step 6: Compute reduced costs d̄ ᵢⱼ = uᵢ + vⱼ – cᵢⱼ for all non-basic cells.

Step 7: If all d̄ ᵢⱼ ≤ 0, the current solution is optimal. STOP and compute total cost.

Step 8: If any d̄ ᵢⱼ > 0, identify the entering variable (most positive d̄ ᵢⱼ), construct a closed
loop, find θ, update the solution, and return to Step 5.

For Assignment Problems:

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 31

Step 1: Check if the cost matrix is square (n×n). If not, add dummy rows/columns with zero
costs.

Step 2: Row Reduction – Subtract the row minimum from each row.

Step 3: Column Reduction – Subtract the column minimum from each column.

Step 4: Attempt to find a complete assignment using only zero cells. If successful, compute
the total cost from the original matrix and STOP.

Step 5: If no complete zero assignment exists, draw minimum covering lines, find the
smallest uncovered element d, subtract d from uncovered elements, add d to doubly-covered
elements.

Step 6: Repeat Step 4. Keep repeating Steps 4–5 until a complete zero assignment is found.

4. Common Mistakes to Avoid

• Always check that total supply equals total demand before starting. Failing to balance the
problem leads to wrong answers.

• In the u-v method, always set one multiplier to zero before solving. Not doing so gives a
system with no unique solution.

• Do not forget the non-negativity of all xᵢⱼ. The leaving variable is the one that reaches
zero first (minimum θ).

• In the Hungarian Method, after row and column reduction, do not confuse covered cells
(on a line) with uncovered cells. The rule is: subtract d from uncovered elements, add d to
doubly-covered elements, and leave singly-covered elements unchanged.

• For maximization problems, remember to convert to minimization first (use M – cᵢⱼ), not
just apply the method directly.

• Count basic variables carefully. You should always have exactly m+n−1 allocated cells.
If you have fewer, the problem is degenerate and needs a ε allocation.

5. Reference Book Details

The primary textbook for this module is:

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 32

Hamdy A. Taha, Operations Research: An Introduction, 9th Edition, Prentice-Hall / Pearson

Education.

Relevant chapters and page numbers:

• Chapter 5: Transportation Model and Its Variants – pp. 163–230 (Taha 9th ed.)

• Section 5.1: Definition of Transportation Model – pp. 163–167

• Section 5.2: Northwest Corner Method – pp. 171–173

• Section 5.3: Least-Cost Method – pp. 173–174

• Section 5.4: Vogel's Approximation Method – pp. 174–177

• Section 5.5: Iterative Computations (u-v Method) – pp. 177–186

• Section 5.6: The Assignment Model – pp. 197–208

• Section 5.6.1: The Hungarian Method – pp. 198–208

Lecture Notes Reference (Dr. Jay Mehta, Sardar Patel University):

• Section 3.2 Transportation Model – pp. 89–102

• Section 3.2.2 Starting Solutions – pp. 94–99

• Section 3.2.6 Iterative Computations – pp. 99–102

• Section 3.3 The Assignment Model – pp. 103–108

• Section 3.3.1 The Hungarian Method – pp. 104–108

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 33

PART H: PRACTICE PROBLEMS FOR EXAMINATION

Transportation Problem Exercises

[Adapted from Exercise 3.2 onwards, Lecture Notes pp. 109–110; Taha, Chapter 5 Exercises]
Exercise 1: A company has three factories (F1, F2, F3) and four warehouses (W1, W2, W3,
W4). The supply, demand, and transportation costs are given below. Find the minimum cost
transportation schedule.

Factory \ W1 W2 W3 W4 Supply
Warehouse
F1 3 1 7 4 300
F2 2 6 5 9 400
F3 8 3 3 2 500
Demand 250 350 400 200 1200
Table 24: Exercise 1 – Transportation Costs

(a) Find the starting solution using each of the three methods and compare costs.

(b) Find the optimal solution using the u-v method.

(c) What is the minimum total transportation cost?

Exercise 2: The following transportation table is unbalanced. Balance it and find the optimal
solution.

Source \ Dest. D1 D2 D3 Supply

S1 8 5 6 120
S2 15 10 12 80
S3 3 9 10 80
Demand 150 70 90 —
Table 25: Exercise 2 – Unbalanced Transportation Problem

Assignment Problem Exercises

Exercise 3: Four programmers (P1, P2, P3, P4) are available to work on four programs (Prog
A, B, C, D). The estimated time (in hours) for each programmer to complete each program is

Department of Computing and Artificial Intelligence MLMCE

 Operations Research | Module 2 | Page 34

shown. Find the assignment of programmers to programs that minimizes total completion
time.

Programmer \ Prog A Prog B Prog C Prog D

Program
P1 120 100 80 90
P2 80 90 110 70
P3 110 140 120 100
P4 90 90 80 90
Table 26: Exercise 3 – Programmer-Program Assignment

Exercise 4: A sales manager wants to assign five salespeople to five sales territories to
maximize total expected sales (in ₹ lakhs). The expected sales matrix is:

Salesperson \ T1 T2 T3 T4 T5
Territory
S1 35 27 28 37 32
S2 28 34 29 40 33
S3 35 24 32 33 38
S4 24 32 25 28 30
S5 24 34 30 34 35
Table 27: Exercise 4 – Maximization Assignment Problem

Hint: Convert to minimization by replacing each element cᵢ ⱼ with (M – cᵢ ⱼ) where M = 40

(maximum element).

Department of Computing and Artificial Intelligence MLMCE