CHAPTER 3 TRANSPORTATION PROBLEM Transportation problems are linear programming problems which involve transporting or shipping goods or products from several sources (plants) to several destinations...

CHAPTER 3



TRANSPORTATION PROBLEM

• 
  Transportation problems
  are linear programming problems which involve transporting or shipping goods or products from several sources (plants) to several destinations (warehouses) at minimum costs.

• It was first presented by F. L. Hitchcock in 1941 and later expanded by T. C. Koopmans.

To From	Supply
Demand

1. 
   Balanced Transportation Problems
   
   

A

balanced transportation problem

has equal number of units of demand and supply. That is, .
Steps in solving balanced transportation problem:

1. Construct a transportation model of the problem.

• The transportation model is a table showing the sources (written in rows) while the destinations (written in columns) of the items to be transported. The last row of the table shows the demand and the last column shows the supply. The cost of transportation of each source to each receiving outlet is written on the upper right corner of each cell formed.

1. Obtain the initial feasible solution by using
   
   
   
   1. 
      
      Northwest Corner Rule
      
      
   
   
   
   

1. Start allocating the units on the upper – left – hand cell (northwest corner) of the tableau. Allocate the lower of the supply and demand corresponding to that cell.

1. From the northwest corner, move to the next row if the supply available in that row is not yet exhausted or move to the next column if the demand available in that column is not yet met.

1. The allocation of units will end at the lower – right – hand cell (south – east corner) of the tableau.

1. 
   
   Minimum Entry Method
   
   

1. Choose the cell with the lowest available cost and allocate the shipment so as to exhaust either the production of plant or meet the requirements of warehouse or both.

1. Delete the ith row or the jth column, depending on whether the allocation exhausts the supply at source or meets the requirement of warehouse . If both of these occur simultaneously (degenerate case), delete the ith row unless it is the only row remaining in which case delete the jth column.

1. Adjust the supply remaining at plant or the unfilled demand of warehouse .

1. If there remains two or more rows or columns not yet deleted, go to step (i); otherwise, the initial basic feasible solution is obtained.

1. 
   
   Vogel’s Approximation Method
   
   

1. Compute the difference between the costs of two cheapest routes for each origin and each destination. Each individual difference is interpreted as a penalty for not choosing the cheapest route and is marked opposite each row and column.

1. Identify the row or column with the largest difference. Allocate the shipment to the lowest cost cell in that row or column so as to exhaust either the supply at a particular source or meet the demand at a warehouse.

1. Drop the ith row or the jth column, depending on whether the allocation exhausts the supply at plant or meet the requirements of warehouse . If both of these occur simultaneously (degenerate case), delete the ith row unless it is the only row remaining, in which case drop the jth column.

1. Adjust the supply remaining at source or the demand of the warehouse not yet met.

1. Go to step (i) and repeat the procedure until an initial assignment using cells is obtained.

1. Evaluate the optimal solution using the
   
   Stepping Stone Method
   .
   
   
   
   • 
     
     Stepping Stone method
     
     is a process to evaluate each vacant cell by tracing its path.
   
   
   
   

• The term
  
  “stepping stone”
  
  was used because the process of doing the stepping – stone is like crossing a stream by moving form one stone to another stone (occupied cells).

1. Used the table done by the northwest corner rule.

1. Determine the vacant cells. For each vacant cell, trace a path (horizontal and vertical directions) that will pass through the occupied cells and will end in the same vacant cell being evaluated.

1. Give alternating signs (+/–) starting with a positive sign from the cost of the vacant cell being evaluated to the next costs in the path.

1. Determine the improvement (a decrease in cost) for each vacant cell by adding the costs determined in step (iii). The
   
   most negative cell
   
   evaluation implies a most decrease in cost.

1. Choose the best cell improvement. The
   
   most negative cell
   
   evaluation gives the best cell improvement; then shift as many units as possible to that vacant cell.

1. Repeat steps (ii) to (v) until an optimal solution is obtained. An optimal solution is obtained if each cell evaluation has
   
   positive or zero
   
   result.

Name: _________________________________________________ Score: _____________
Course/Year: ____________________ Room: ________________ Date: _____________
Day: _______________ Time: ________________ Professor: _________________________

Exercise No. 5


Balanced Transportation Problem

1. Solve the following transportation problems:

1. Costales manufacturing company operates plants P₁, P₂
   and P₃
   in different regions. The weekly production of these plants is as follows:

Plants Weekly Production / Supply
P₁
110
P₂
90
P₃
55
Total 255
The total supply of the company is absorbed by warehouse W₁, W₂
and W₃. Their weekly requirement is as follows:
Warehouses Weekly Requirement / Demand
W₁
100
W₂
70
W₃
85
Total 255
The transportation cost from each plant to each warehouse is given below.
Warehouses
Plants From \ To W₁
W₂
W₃

P₁
P9 P11 P7
P₂
8 5 10
P₃
14 13 9
A. Determine the minimum cost transportation schedule using an initial basic feasible solution obtained by each of the following methods:

1. Northwest Corner Rule

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________

1. Minimum Entry Method

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________

1. Vogel’s Approximation Method

To From	W1	W2	W3	Supply	Row Difference
P1
P2
P3
Demand
Column Difference

Cost = ____________________________________________________________
= _______________________
B. Find the optimal solution using stepping stone method.

Iteration 1

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Final Tableau

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

1. Enriquez manufacturing company must ship its products from three plants to three warehouses. The weekly production of the plants is 120, 75 and 55. The weekly requirements of the warehouses are 100, 90 and 60. The shipping cost from each plant to the warehouse is given below:

Warehouses
Plants From \ To W₁
W₂
W₃

P₁
P9 P13 P7
P₂
4 6 8
P₃
6 5 10
Find the following:

1. the minimum cost transportation schedule using an initial basic feasible solution obtained by each of the following methods:

1. Northwest Corner Rule

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________

1. Minimum Entry Method

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________

1. Vogel’s Approximation Method

To From	W1	W2	W3	Supply	Row Difference
P1
P2
P3
Demand
Column Difference

Cost = ____________________________________________________________
= _______________________

1. the optimal solution using stepping stone method.

Iteration 1

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 3

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Final Tableau

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

1. 
   Unbalanced Transportation Problems
   
   

An

unbalanced transportation problem

has unequal number of units of demand and supply. That is,
(1) Or Supply is less than Demand
(2) or Supply is greater than Demand
Steps in solving unbalanced transportation problem:
Case 1: Or Supply is less than Demand
(i) Add a dummy row to the transportation table. Give zero (0) cost to each dummy cell.
(ii) Follow the procedure in finding the optimal solution in the balanced transportation problem using the Stepping Stone method.
Case 2: or Supply is greater than Demand
(i) Add a dummy column to the transportation table. Give zero (0) cost to each dummy cell.
(ii) Follow the procedure in finding the optimal solution in the balanced transportation problem using the Stepping Stone method.
Name: _________________________________________________ Score: _____________
Course/Year: ____________________ Room: ________________ Date: _____________
Day: _______________ Time: ________________ Professor: _________________________

Exercise No. 6


Unbalanced Transportation Problem

I. Solve the following transportation problems using Stepping Stone Method:

1. Rendon Manufacturing Firm operates three plants that ship their goods to three regional warehouses. The production capacity of the plants and the requirements of the warehouses are given below:

Plants Capacity Warehouses Requirements
P₁
80 W₁
95
P₂
90 W₂
55
P₃
75 W₃
70
Total 245 Total 220
Warehouses
Plants From \ To W₁
W₂
W₃

P₁
P5 P4 P6
P₂
11 7 8
P₃
2 6 10
Solution:

Initial Tableau

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Iteration 1

To From	W1	W2	W3	dummy	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

To From	W1	W2	W3	dummy	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 3

To From	W1	W2	W3	dummy	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 4

To From	W1	W2	W3	dummy	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Final Tableau

To From	W1	W2	W3	dummy	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

To From	W1	W2	W3	W4	Supply
P1	11	17	12	10
			240
P2	12	14	16	13
			280
P3	20	11	10	17
			230
Demand	250	200	340	110	900 / 750

Solution:

Iteration 1

To From	W1	W2	W3	W4	Supply
P1	11	17	12	10
P2	12	14	16	13
P3	20	11	10	17
dummy
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

To From	W1	W2	W3	W4	Supply
P1	11	17	12	10
P2	12	14	16	13
P3	20	11	10	17
dummy
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 3

To From	W1	W2	W3	W4	Supply
P1	11	17	12	10
P2	12	14	16	13
P3	20	11	10	17
dummy
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 4

To From	W1	W2	W3	W4	Supply
P1	11	17	12	10
P2	12	14	16	13
P3	20	11	10	17
dummy
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

1. 
   Degenerate Transportation Problems
   
   

The

degeneracy

in transportation problems occurs when

Total number of occupied cells


That is, there are lacking occupied cells to evaluate the vacant cells.
Degeneracy
may occur in the following:

1. In the initial feasible solution


2. In the succeeding solutions.

Rules in Solving Degenerate Transportation Problem

1. Degeneracy in the initial feasible solution

1. Apply the North – West Corner Rule. In this step, the
   stair path
   pattern would be broken. Complete the stair path by using zero entry in the cell with a lower cost for a minimization problem.


2. Follow the procedure in finding the optimal solution in the balanced transportation problem using the Stepping Stone method

1. Degeneracy in the succeeding solutions

There will be atleast one vacant cell for which an evaluation path may not be constructed. Degeneracy occurs in the succeeding solutions using the Stepping Stone method, in this case allocate zero entry to this cell to complete the evaluation path.
Name: _________________________________________________ Score: _____________
Course/Year: ____________________ Room: ________________ Date: _____________
Day: _______________ Time: ________________ Professor: _________________________

Exercise No. 7


Degenerate Transportation Problem

I. Solve the following transportation problems using Stepping Stone Method:

1. Given the problem in table below, find the minimum cost.

To From	W1	W2	W3	Supply
P1	12	10	13
		150
P2	8	12	6
		100
P3	9	10	10
		125
Demand	130	120	125	375

Solution:

Iteration 1

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Final Tableau

To From	W1	W2	W3	Supply
P1
P2
P3
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

1. Santos Printing Press delivers books from their three branches to three bookstores. Bookstore A requires 180 boxes of books each year, bookstore B requires 145, and bookstore C requires 170. Branch D can supply 120 books, branch E can supply 205 books and branch F can supply 170 books. Using the cost information given below, compute the optimal transportation cost.

From	To Bookstore A	To Bookstore B	To Bookstore C
Branch D	P 25 / box	18	22
Branch E	22	25	20
Branch F	15	24	20

Solution:

Iteration 1

To From	A	B	C	Supply
D	25	18	22
E	22	25	20
F	15	24	20
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

To From	A	B	C	Supply
D	25	18	22
E	22	25	20
F	15	24	20
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 3

To From	A	B	C	Supply
D	25	18	22
E	22	25	20
F	15	24	20
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

1. Janet, a fruit dealer, sells fruits to customers in Manila, Pampanga and Bulacan. The monthly demand is 4000 kilos in Manila, 2500 kilos in Pampanga and 1000 kilos in Bulacan.

The fruits are shipped from three farms located in Laguna, Davao and Cebu. The monthly supply available in Laguna is 5600 kilos, in Davao 900 kilos and Cebu 3200 kilos.
The shipping cost per kilo is shown in the table below.

From	To Manila	To Pampanga	To Bulacan
Laguna	P 5 / kilo	P11	P7
Davao	50	55	52
Cebu	25	21	27

Help the dealer to decide what schedule of shipments will obtain the lowest transportation cost.
Solution:

Initial Tableau

To From	Manila	Pampanga	Bulacan	Supply
Laguna
Davao
Cebu
Demand

Iteration 1

To From	Manila	Pampanga	Bulacan	dummy	Supply
Laguna
Davao
Cebu
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

To From	Manila	Pampanga	Bulacan	dummy	Supply
Laguna
Davao
Cebu
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Final Tableau

To From	Manila	Pampanga	Bulacan	dummy	Supply
Laguna
Davao
Cebu
Demand

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost

1. Given the problem in table below, find the minimum cost.

C	D	E	F	G	Supply
A	70	85	70	62	67	46
B	75	98	64	58	72	88
Demand	46	29	36	22	27	160 / 134

Solution:

Iteration 1

C	D	E	F	G	Supply
A	70	85	70	62	67	46
B	75	98	64	58	72	88
Dummy	0	0	0	0	0
Demand	46	29	36	22	27	160 / 160

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 2

C	D	E	F	G	Supply
A	70	85	70	62	67	46
B	75	98	64	58	72	88
Dummy	0	0	0	0	0
Demand	46	29	36	22	27	160 / 160

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:

Iteration 3

C	D	E	F	G	Supply
A	70	85	70	62	67	46
B	75	98	64	58	72	88
Dummy	0	0	0	0	0
Demand	46	29	36	22	27	160 / 160

Cost = ____________________________________________________________
= _______________________
Cell Evaluation:
Decision:

From	To	No. of Units for Shipment	Cost / Unit	Shipment Cost
Total Cost