Transportation Simplex
Method:
A Special-Purpose Solution
Procedure
Presented by:
De Castro, Cleoandrea
Laureles, Charichelle
Lucero, Gem Margaret
Silva, Jaimeh Rose
TRANSPORTATION SIMPLEX METHOD
Transportation Problem – The objective is to minimize the cost of shipping
/distributing a product from origins to the destinations.
The special-purpose solution for the transportation problem.
Two-phase Procedure
PHASE I: Finding an Initial Feasible Solution
PHASE II: Iterating to the Optimal Solution
TRANSPORTATION TABLEAU
Table representing a transportation problem in which each cell correspond to a
variable or arch.
TRANSPORTATION TABLEAU
(example)
Transportation Tableua composed of:
12 Cells – Correspond to the 12 Routes from one origin to one destination.
Each Cell – correspond to a variable in the linear programming programming
formulation.
Entries in the right-hand margin – indicate the supply at each origin.
Entries in bottom margin – indicate the demand at each destination.
Entries in right-hand corner of each cell – show the transportation cost per unit
shipped over the corresponding route.
Each row – Correspond to a supply node.
Each column – Correspond to demand node.
Note: Transportation simplex method can be applied only to a balance problem (total
supply = total demand) If the total supply is not equal to total demand add dummy origin
or dummy destination.
Transportation Problem (minimize the cost)
Transportation problem faced by Foster Generators, this problem involves the
transportation of a product from three plants to four distribution centers. Foster
Generators operates plants in Cleveland, Bedford, and York. Production capacities over
the next three months planning period for one particular type of generator are as follows:
Origin Plant Three-month production
capacity (units)
1 Cleveland 5000
2 Bedford 6000
3 York 2500
Total: 13500
The firm distributes its generators through four regional distribution centers located in
Boston, Chicago, St. Louis, and Lexington; the three-month forecast of demand for the
distribution centers is as follows:
Destination Distribution Center Three-month demand
forecast (units)
1 Boston 6000
2 Chicago 4000
3 St. Louis 2000
4 Lexington 1500
Total: 13500
Transportation Cost per unit for the Foster Generators
Destination
Origin Boston Chicago St. Louis Lexington
Cleveland 3 2 7 6
Bedford 7 5 2 5
York 2 5 4 5
The objective is to determine the routes to be used and the quantity to be shipped
via each route that will provide the minimum total transportation cost.
Steps in PHASE I: Finding an initial Feasible Solution
STEP 1: Identify the cell in the Transportation tableau with the lowest cost.
STEP 2: Reduced the row supply and the column demand by the amount of flow
allocated to the cell identified in step 1.
STEP 3: If all row supply and column demands have been exhausted, then stop
otherwise, continue with step 4.
STEP 4: If the row supply is now zero, eliminate the row from further considerations by
drawing a line through it. If the column demand is now zero, eliminate the column by
drawing a line through it.
STEP 5: Compute the total cost of the initial feasible solution.
Applying the Steps in the Transportation Problem
STEP 1: Identify the cell in the Transportation tableau with the lowest cost. Using the
Heuristic/Minimum cost Method
STEP 2:
Reduced the row supply and the column demand by the amount of flow allocated to the
cell identified
in step 1.
Cleveland-Chicago = 4,000
Bedford-St. Louis = 2,000
York-Boston = 2,500
STEP 3: If all row supply and column demands have been exhausted, then stop
otherwise, continue with step 4.
STEP 4: If the row supply is now zero, eliminate the row from further considerations by
drawing a line through it. If the column demand is now zero, eliminate the column by
drawing a line through it.
STEP 2: Reduced the row supply and the column demand by the amount of flow
allocated to the cell identified in step 1. (part 2)
Cleveland-Boston = 1,000
Bedford-Lexington = 1,500
STEP 3: If all row supply and column demands have been exhausted, then stop
otherwise, continue with step 4. (part 2)
STEP 4: If the row supply is now zero, eliminate the row from further considerations by
drawing a line through it. If the column demand is now zero, eliminate the column by
drawing a line through it. (part 2)
STEP 2: Reduced the row supply and the column demand by the amount of flow
allocated to the cell identified in step 1. (part 3)
Bedford-Boston = 2,500
STEP 3: If all row supply and column demands have been exhausted, then stop
otherwise, continue with step 4. (part 3)
The supply and demand are now zero
STEP 4: If the row supply is now zero, eliminate the row from further considerations by
drawing a line through it. If the column demand is now zero, eliminate the column by
drawing a line through it. (part 3)
Final Tableau showing the Initial Feasible Solution obtained using the minimum
cost method
STEP 5: Compute the total cost of the initial feasible solution.
Multiply the Units shipped to Cost per unit to get the total cost.
Steps in PHASE II: Iterating to the Optimal Solution
Step 1: Look for the unoccupied cells.
Step 2: Identify the unoccupied cell with the smallest or Most negative value by
allocating - and + alternatively to corners of the selected closed path.
Step 3: Calculate the improvement index
Step 4: Select the most negative unoccupied cell and allocate as much as you can to that
unoccupied cell that will also makes the demand and supply equal to zero.
Step 5: Compute the total cost.
Step 6: Calculate again the improvement index, if there is still negative value select it
and Repeat the allocation till the improvement index is ≥0 for all unoccupied cells, if the
improvement index is now≥ 0, the solution is Optimal.
Applying the Steps in the Transportation Problem
Step 1: Look for the unoccupied cells.
UNOCCUPIED CELLS:
Cleveland-St. Louis
Cleveland-Lexington
Bedford-Chicago
York-Chicago
York-St. Louis
York-Lexinton
Step 2: Identify the unoccupied cell with the smallest or Most negative value by
allocating - and + alternatively to corners of the selected closed path and calculate the
improvement index.
Cleveland-St. Louis = 7-2+2-3+7-2 = 9
Cleveland-Lexington = 6-3+2-2+3-7+2 = 1
Bedford-Chicago = 5-2+3-7 = -1
York-Chicago = 5-2+7-3+2-2+3 = 10
York-St. Louis = 4-2+2-3+7-2 = 6
York-Lexington = 5-3+2-2+3-7+2 = 0
Note: The positive value means, there will be an increase in transportation cost and the
most negative value means, there will be an increase in transportation cost. So that you
must select the most negative value to minimize the transportation cost.
Step 3: Select the most negative unoccupied cell and allocate as much as you can to that
unoccupied cell that will also makes the demand and supply equal to zero.
Cleveland-St. Louis = 7-2+2-3+7-2 = 9
Cleveland-Lexington = 6-3+2-2+3-7+2 = 1
Bedford-Chicago = 5-2+3-7 = -1
York-Chicago = 5-2+7-3+2-2+3 = 10
York-St. Louis = 4-2+2-3+7-2 = 6
York-Lexington = 5-3+2-2+3-7+2 = 0
Step 4: Compute the total cost.
Route
From To Units Cost Total Cost
shipped per
unit
Cleveland Boston 3,500 3 $10,500
Cleveland Chicago 1,500 2 3,000
Bedford Chicago 2,500 5 12,500
Bedford St. Louis 2,000 2 4,000
Bedford Lexington 1,500 3 4,500
York Boston 2,500 2 5,000
Total cost= $39,500
Step 5: Calculate again the improvement index
Cleveland-St. Louis =7-2+5-2 = 8
Cleveland-Lexington = 6-3+2-5+2-3+2 = 1
Bedford-Boston = 7-3+2-5 = 1
York-Chicago = 5-5+2-3+2 = 1
York-St. Louis = 4-2+5-2+3-2 = 6
York-Lexington = 5-3+2-5+2-3+2 = 0
There is no more Most Negative unoccupied cell, therefore the Solution is
Optimal.
FOR ACTIVITY:
A company has three factories X, Y, and Z and three warehouses A, B, and C. It is
required to schedule factory production and shipments from factories to warehouses in
such a manner so as to minimize total cost of shipment and production. Unit variable
manufacturing cost (UVMC) and factory capacities and warehouse requirements are
given below: