11.5 Solving Balanced Transportation Models

Once a transportation model is confirmed to be balanced—that is, the total supply equals the total demand—it can be solved using one of several initial feasible solution methods. These methods differ in their approach and efficiency in minimizing total transportation cost. The goal of each is to generate a starting solution that satisfies all supply and demand constraints.

Common Initial Feasible Solution Methods:

1. North-West Corner Rule (NWCR):
   This is the most basic method. It begins at the top-left (north-west) cell of the transportation tableau and allocates as much as possible to that cell, then moves either right or down based on remaining supply and demand. While simple, it does not consider transportation costs and often results in suboptimal solutions.
2. Least Cost Method (LCM):
   This method improves upon NWCR by selecting the cell with the lowest transportation cost for allocation first. It continues to allocate to the next lowest-cost cell, adjusting supply and demand accordingly. This approach generally yields a better starting solution than NWCR.
3. Vogel’s Approximation Method (VAM):
   VAM introduces the concept of opportunity cost by calculating penalties for not using the least-cost routes. It selects allocations based on the highest penalty, thereby balancing cost efficiency with strategic allocation. VAM typically produces the most cost-effective initial solution among the three methods.

These methods will be illustrated using the following example.

Example: Mega Farms Inc.

Mega Farms Inc. operates three strawberry farms—S1, S2, and S3—which supply four regional markets—D1, D2, D3, and D4. The supply capacities and market demands are as follows:

• Supply Capacities:
  • S1: 60 cases
  • S2: 80 cases
  • S3: 100 cases
• Market Demands:
  • D1: 50 cases
  • D2: 70 cases
  • D3: 80 cases
  • D4: 40 cases

The transportation cost per case (in $) from each farm to each market is provided in the following tableau:

Mega Farms Inc. wants to determine how many cases should be sent from which farm to which market so that the total cost of transportation is minimized.

Determining the Total Transportation Cost Using the North-West Corner Method

The North-West Corner Method (NWCM) is a straightforward technique used to generate an initial feasible solution for a balanced transportation model. While it does not consider transportation costs during allocation, it provides a valid starting point for further optimization.

This method is named after the north-west (upper-left) cell of the transportation tableau, where the allocation process begins. The steps are as follows:

1. Start at the North-West Cell (Top-Left Corner):
   Allocate as much as possible to the cell in the first row and first column (cell (1,1)), subject to the available supply and demand.
2. Adjust Supply and Demand:
   Subtract the allocated quantity from both the supply of the row and the demand of the column.
3. Eliminate Satisfied Rows or Columns:
   If the supply for a row or the demand for a column is fully satisfied (i.e., reduced to zero), that row or column is considered complete and is crossed out (highlighted in grey in visual representations).
4. Move to the Next Available Cell:
   Proceed to the next cell to the right (if a row is still active) or downward (if a column is completed) and repeat the allocation process.
5. Continue Until Completion:
   Repeat the above steps until all supply and demand values are fully allocated.

Once the initial allocation is complete, the total transportation cost can be calculated by multiplying the quantity allocated to each cell by its corresponding unit transportation cost and summing the results across the tableau.

The tableau for this model is shown below:

The steps in solving this problem are:

Step 1: Allocate to (S1, D1)

• Allocation: min (60, 50) = 50 units
• Update:
  • S1 remaining supply = 60 – 50 = 10
  • D1 demand fulfilled = 50 – 50 = 0

Step 2: Allocate to (S1, D2)

• Allocation: min(10, 70) = 10 units
• Update:
  • S1 exhausted
  • D2 remaining demand = 70 – 10 = 60

Step 3: Allocate to (S2, D2)

• Allocation: min(60, 80) = 60 units
• Update:
  • S2 remaining supply = 80 – 60 = 20
  • D2 demand fulfilled

Step 4: Allocate to (S2, D3)

• Allocation: min(20, 80) = 20 units
• Update:
  • S2 exhausted
  • D3 remaining demand = 80 – 20 = 60

Step 5: Allocate to (S3, D3)

• Allocation: min(60, 100) = 60 units
• Update:
  • S3 remaining supply = 100 – 60 = 40
  • D3 demand fulfilled

// Table missing? 

Step 6: Allocate to (S3, D4)

• Allocation: min(40, 40) = 40 units
• Update:
  • S3 exhausted
  • D4 demand fulfilled

After completing the allocation process using the North-West Corner Method, all market demands have been fully satisfied, and the available supply from all farms has been completely utilized. This indicates that a feasible solution has been reached.

To determine the total transportation cost of this initial solution, we multiply the quantity allocated to each cell by its corresponding unit transportation cost and sum the results:

Total Cost = (20×2) + (10×3) + (10×4) + (20×2) + (50×6) + (10×2) + (60×12) + (20×10) + (60×6) + (40×4)

Cost = 40 + 30 + 40 + 40 + 300 + 20 + 720 + 200 + 360 + 160 = $1760

Thus, the initial basic feasible solution obtained using the North-West Corner Method results in a total transportation cost of $1760.

It is important to note that while this method provides a valid starting point, it does not guarantee the optimal solution. Therefore, in the following sections, we will evaluate the total transportation cost using two more refined methods:

• Least Cost Method (LCM)
• Vogel’s Approximation Method (VAM)

These methods incorporate cost considerations during the allocation process and are likely to yield more cost-efficient solutions

Determining the Total Transportation Cost Using the Least Cost Method

The Least Cost Method (LCM) is a more cost-conscious approach to generating an initial feasible solution for a balanced transportation model. Unlike the North-West Corner Method, LCM prioritizes allocations based on minimizing transportation costs from the outset.

Steps for Applying the Least Cost Method:

1. Identify the Cell with the Lowest Transportation Cost:
   Scan the entire transportation tableau and locate the cell with the minimum unit cost.
2. Allocate the Maximum Possible Quantity to This Cell:
   Assign as much as possible to the selected cell, based on the available supply and demand.
3. Adjust Supply and Demand:
   Subtract the allocated quantity from the corresponding row (supply) and column (demand).
4. Eliminate Satisfied Rows or Columns:
   If a row or column is fully satisfied (i.e., reduced to zero), it is crossed out or marked as complete.
5. Repeat the Process:
   Continue selecting the next lowest-cost cell from the remaining tableau and repeat the allocation process until all supply and demand constraints are met.

This method typically results in a lower total transportation cost than the North-West Corner Method, as it incorporates cost efficiency into the allocation process from the beginning.

The model tableau is shown below:

Step 1: Select Cell with Lowest Cost – (S1, D2), Cost = $2

• Allocation: min (60, 70) = 60 units
• Update:
  • S1 supply exhausted
  • D2 remaining demand = 70 – 60 = 10

Step 2: Next Lowest Cost – Tie at $4 (S2, D1) and (S3, D4)

• Randomly select (S2, D1)
• Allocation: min (80, 50) = 50 units
• Update:
  • S2 remaining supply = 80 – 50 = 30
  • D1 demand fulfilled

Step 3: Next Lowest Cost – (S3, D4), Cost = $4

• Allocation: min (100, 40) = 40 units
• Update:
  • S3 remaining supply = 100 – 40 = 60
  • D4 demand fulfilled

Step 4: Next Lowest Cost – Tie at $6 (S3, D2) and (S3, D3)

• Randomly select (S3, D3)
• Allocation: min (60, 80) = 60 units
• Update:
  • S3 supply exhausted
  • D3 remaining demand = 80 – 60 = 20

Step 5: Next Lowest Cost – (S2, D3), Cost = $10

• Allocation: min 30, 20) = 20 units
• Update:
  • S2 remaining supply = 30 – 20 = 10
  • D3 demand fulfilled

Step 6: Final Allocation – (S2, D2), Cost = $12

• Allocation: min(10, 10) = 10 units
• Update:
  • S2 exhausted
  • D2 demand fulfilled

After completing the allocation process using the Least Cost Method, all supply capacities have been fully utilized, and all market demands have been satisfied. This confirms that a feasible solution has been reached.

To compute the total transportation cost, we multiply the quantity allocated to each cell by its corresponding unit transportation cost and sum the results:

Total Cost = (50×4) + (60×2) + (10×12) + (20×10) + (60×6) + (40×4)

Total Cost = 200 + 120 + 120 + 200 + 360 + 160 = $1160

Thus, the initial basic feasible solution obtained using the Least Cost Method results in a total transportation cost of $1160.

This solution is significantly more cost-efficient than the one obtained using the North-West Corner Method ($1760), as it incorporates transportation costs into the allocation process. However, while this method often yields a near-optimal solution, it does not guarantee optimality.

To explore the possibility of further cost reduction, we now turn to Vogel’s Approximation Method (VAM)—a more refined approach that considers both cost and opportunity cost in its allocation strategy.

Determining the Total Transportation Cost Using Vogel’s Approximation Method (VAM)

Vogel’s Approximation Method (VAM) is a heuristic technique used to generate an initial feasible solution for a balanced transportation problem. It is widely regarded as one of the most effective initial allocation methods, as it incorporates both cost efficiency and opportunity cost into the decision-making process.

Steps for Applying VAM:

1. Calculate Penalty Costs for Each Row and Column:
   For every row and column in the transportation tableau, compute the penalty by finding the difference between the two lowest unit transportation costs in that row or column. This penalty reflects the opportunity cost of not choosing the lowest-cost option.
2. Identify the Row or Column with the Highest Penalty:
   Select the row or column with the largest penalty value. This indicates where the cost of making a suboptimal allocation would be greatest.
3. Allocate to the Lowest-Cost Cell in the Selected Row or Column:
   Within the selected row or column, allocate as much as possible to the cell with the lowest transportation cost, based on the available supply and demand.
4. Adjust Supply and Demand and Eliminate Satisfied Rows or Columns:
   Update the tableau by subtracting the allocated quantity and crossing out any row or column where supply or demand has been fully met.
5. Recalculate Penalties and Repeat:
   Recompute the penalties for the remaining rows and columns and repeat the process until all supply and demand constraints are satisfied.

This method typically results in a lower total transportation cost than both the North-West Corner and Least Cost methods, making it a preferred choice for generating high-quality initial solutions.

Step 1: Calculate Row and Column Penalties

The first step in Vogel’s Approximation Method is to compute the penalty values for each row and column. These penalties represent the opportunity cost of not choosing the lowest-cost allocation in a given row or column. The penalty is calculated as the difference between the two lowest unit transportation costs in each row or column.

Row Penalties:

• S1: 6 − 2 = 4
• S2: 10 – 4 = 6
• S3: 6 − 4 = 2

Column Penalties:

• D1: 6 – 4 = 2
• D2: 6 − 2 = 4
• D3: 10 – 6 = 4
• D4: 8 − 4 = 4

Step 2: Select the Row or Column with the Highest Penalty

Among all the calculated penalties, the highest is 6, which corresponds to row S2. This indicates that failing to allocate to the lowest-cost cell in this row would result in the greatest cost inefficiency.

• The lowest-cost cell in row S2 is S2 → D1, with a unit transportation cost of $4.

Allocation:

• Allocate the minimum of the available supply and demand:

Min (80,50) = 50 units

Update:

• S2 supply is reduced to 80−50=30 units
• D1 demand is fully satisfied, and the column is eliminated from further consideration

Step 3: Recalculate Penalties (Excluding Column D1

With D1 now fully satisfied and removed from the tableau, we recalculate the penalty values for the remaining rows and columns.

Updated Row Penalties:

• S1: 8 − 2 = 6
• S2: 12 – 10 = 2
• S3: 6 − 4 = 2

Updated Column Penalties:

• D2: 6 – 2 = 4
• D3: 10 − 6 = 4
• D4: 8 – 4 = 4

Step 4: Select the Row or Column with the Highest Penalty

The highest penalty is 6, corresponding to row S1. This indicates that failing to allocate to the lowest-cost cell in this row would result in the greatest cost inefficiency.

• The lowest-cost cell in row S1 is S1 → D2, with a unit transportation cost of $2.

Allocation:

• Allocate the minimum of the available supply and demand:

Min (60,70) = 60 units

Update:

• S1 supply is now exhausted: 60 – 60 = 0
• D2 demand is partially fulfilled: 70 − 60 = 10

Row S1 is now eliminated from further consideration

Step 5: Recalculate Penalties (Excluding Row S1 and Column D1)

With S1 and D1 now eliminated from the tableau, we recalculate the penalty values for the remaining rows and columns.

Updated Row Penalties:

• S2: 12−10 = 2
• S3: 6 − 4 = 2

Updated Column Penalties:

• D2: 12 – 6 = 6
• D3: 10 − 6 = 4
• D4: 18 – 4 = 14

Step 6: Select the Row or Column with the Highest Penalty

The highest penalty is 14, corresponding to column D4. This indicates that failing to allocate to the lowest-cost cell in this column would result in the greatest cost inefficiency.

• The lowest-cost cell in column D4 is S3 → D4, with a unit transportation cost of $4.

Allocation:

• Allocate the minimum of the available supply and demand:

Min (100,40) = 40 units

Update:

• S3 supply is reduced to 100 – 40 = 60 units
• D4 demand is fully satisfied, and the column is removed from further consideration

Step 7: Recalculate Penalties (Excluding S1, D1, and D4)

With row S1 and columns D1 and D4 now eliminated from the tableau, we recalculate the penalty values for the remaining rows and columns.

Updated Row Penalties:

• S2: 12−10=2
• S3: 6−6=0

Updated Column Penalties:

• D2: 12−6=6
• D3: 10−6=4

Step 8: Select the Row or Column with the Highest Penalty

The highest penalty is 6, corresponding to column D2. This indicates that failing to allocate to the lowest-cost cell in this column would result in the greatest cost inefficiency.

• The lowest-cost cell in column D2 is S3 → D2, with a unit transportation cost of $6.

Allocation:

• Allocate the minimum of the remaining supply and demand:

Min (60,10) = 10 units

Update:

• S3 supply is reduced to: 60−10=50 units
• D2 demand is now fully satisfied, and the column is removed from further consideration

Final Allocation: Completing the Tableau

At this stage, only two unallocated cells remain—one in each of the remaining rows (S2 and S3) and one column (D3). Since no further penalty calculations are meaningful with only one option per row and column, we proceed directly with the final allocations.

Final Allocations:

• Allocate:Min (50,80) = 50 units to S3→D3Remaining supply at S3: 50 − 50 = 0
  Remaining demand at D3: 80 − 50 = 30
• Allocate:Min (30,30) = 30 units to S2→D3Remaining supply at S2: 30 − 30 = 0
  Remaining demand at D3: 30 − 30 = 0

Result:

• All supplies are exhausted
• All market demands are fully satisfied

This completes the initial feasible solution using Vogel’s Approximation Method.

After completing all allocations using Vogel’s Approximation Method, the total transportation cost is calculated as follows:

Total Cost = (50×4) + (60×2) + (10×6) + (30×10) + (50×6) + (40×4)

Total Cost = 200 + 120 + 60 + 300 + 300 + 160 = $1140

Thus, the initial basic feasible solution obtained using VAM results in a total transportation cost of $1140, which is lower than the $1160 obtained using the Least Cost Method and significantly better than the $1760 from the North-West Corner Method.

This outcome highlights one of the key advantages of VAM: it often produces a more cost-effective initial solution by incorporating both transportation costs and opportunity costs into the allocation process.

However, it is important to note that even though VAM typically yields a near-optimal solution, it does not guarantee optimality. In the following sections, we will explore optimization techniques