Welcome to Transportation Problems!
Ever wondered how a massive company like Amazon or a supermarket chain gets products from their warehouses to your local store without spending a fortune on fuel? That is exactly what we are going to solve in this chapter. We are looking for the most efficient way to move "stuff" from sources (where things are made) to destinations (where things are needed) while keeping the total cost as low as possible.
Don’t worry if this seems a bit "data-heavy" at first. Once you learn the rhythm of the tables, it’s like solving a giant logic puzzle!
Quick Review: The Golden Rule
Before we start any problem, the total Supply must equal the total Demand. If they aren't equal, we have to create a "fake" source or destination called a Dummy to balance the books.
1. Finding a Starting Point: The North-West Corner Method
In Decision Mathematics, we usually start with a "Basic Feasible Solution." This is a fancy way of saying "a plan that works, even if it isn't the cheapest yet." The easiest way to find one is the North-West Corner Method.
How it works (Step-by-Step):
Imagine your data table is a map. The "North-West" cell is the one in the top-left corner.
1. Start in the top-left cell.
2. Look at the Supply for that row and the Demand for that column.
3. Allocate as much as possible to that cell (the smaller of the two numbers).
4. Subtract this amount from both the supply and demand totals.
5. If the supply for that row is now zero, move down one cell. If the demand for that column is now zero, move right one cell.
6. Repeat until you reach the bottom-right cell.
Memory Aid: Think of it like reading a book. You start at the top left and work your way across and down!
Example: If Warehouse A has 20 units and Shop 1 needs 15, you put 15 in the top-left box. Shop 1 is now happy (Demand = 0), so you move right to Shop 2 to give away Warehouse A’s remaining 5 units.
Key Takeaway: The North-West Corner method gives us a valid starting plan, but it completely ignores the costs! It’s fast, but rarely the cheapest option.
2. Can We Make it Better? The Stepping-Stone Method
Once we have a starting plan, we use the Stepping-Stone Method to see if we can save money by moving units to different cells.
Checking for "Shadow Costs"
To check if a cell is a good candidate for moving units, we calculate Improvement Indices. We first need to find values for each row (\(u_i\)) and each column (\(v_j\)).
For every occupied cell (a cell with units in it), we use the formula:
\(u_i + v_j = \text{Cost of that cell}\)
Tip: Always start by setting \(u_1 = 0\). This gives you a starting point to calculate all the other \(u\) and \(v\) values.
Calculating the Improvement Index (\(I_{ij}\))
For every empty cell, we calculate the potential saving:
\(I_{ij} = \text{Cost of cell} - u_i - v_j\)
Did you know? If an improvement index is negative, it means moving units to that cell will reduce the total cost. We want to pick the most negative index to improve our solution!
Key Takeaway: If all improvement indices are 0 or positive, you have found the optimal solution (the cheapest plan possible). If any are negative, you can still save money!
3. Making the Move: Entering and Exiting Cells
When you find a cell with a negative index, it becomes the Entering Cell. To move units there, we must complete a closed-loop path.
The Rules of the Loop:
- The loop must start and end at the entering cell.
- All other "corners" of the loop must be occupied cells.
- You can only move horizontally and vertically.
- Assign \(+\) and \(-\) signs alternately to the corners of the loop, starting with a \(+\) at the entering cell.
Identifying the Exiting Cell:
Look at the cells with a \(-\) sign in your loop. Find the smallest number of units in these cells. This is the amount you will move. The cell that drops to zero units is your Exiting Cell.
Common Mistake: Students often try to make diagonal moves in the loop. Remember: Horizontal and vertical only—just like a Rook in chess!
Key Takeaway: Moving units around the loop keeps the supply and demand totals balanced while lowering the overall cost.
4. Dealing with Special Cases: Dummies and Degeneracy
Dummy Locations
If Total Supply \(>\) Total Demand, we create a Dummy Destination. If Total Demand \(>\) Total Supply, we create a Dummy Source. The cost of shipping to/from a dummy is always 0.
Degeneracy
For the stepping-stone method to work, you must have a specific number of occupied cells. This number is:
\(R + C - 1\)
(where \(R\) is the number of rows and \(C\) is the number of columns).
If you have fewer than this, the problem is degenerate. To fix this, we place a tiny, imaginary amount (represented by the Greek letter \(\epsilon\)) into one of the empty cells to "trick" the algorithm into working.
Quick Review Box:
- Supply \(\neq\) Demand? Use a Dummy.
- Too few occupied cells? You have Degeneracy; use \(\epsilon\).
- Optimal solution? All improvement indices \(\ge 0\).
5. Formulating as a Linear Programming Problem
Sometimes, the exam will ask you to write the transportation problem as a Linear Programming (LP) model. This is just a formal way of writing down our goals and rules.
The Variables:
Let \(x_{ij}\) be the number of units transported from source \(i\) to destination \(j\).
The Objective Function:
We want to Minimize the total cost. It looks like this:
\(\text{Minimize } Z = \sum (\text{Cost}_{ij} \times x_{ij})\)
The Constraints:
1. Supply Constraints: The total units leaving a warehouse cannot exceed its supply.
Example: \(x_{11} + x_{12} + x_{13} \le \text{Supply}_1\)
2. Demand Constraints: The total units arriving at a shop must meet its demand.
Example: \(x_{11} + x_{21} + x_{31} = \text{Demand}_1\)
3. Non-negativity: You can't ship a negative number of items! (\(x_{ij} \ge 0\)).
Key Takeaway: LP formulation is just "Math-speak" for the table we've been using. The rows are supply constraints, the columns are demand constraints, and the cell costs make up the objective function.
Final Encouragement: Transportation problems can feel like a lot of arithmetic, but the steps are always the same. Practice one full cycle—from North-West Corner to the final Optimal Solution—and you’ll see how it all fits together!