RANSPORTATION MODEL

- is a linear programming problem in which a product is to be transported from a number of sources to a number of destinations at the minimum cost or maximum profit

Key Terms
Destination
a point of demand in a transportation problem.

Origin
the source or supply location.

Unused Squares
squares which represent routes where no quantity is shipped between a source and a destination.

Stone Squares
used squares in a transportation model.

Methods in Establishing the Initial Feasible Region

Northwest Corner Rule (NCR)

- a procedure for obtaining an initial feasible solution to a transportation problem that starts with allocating units to the upper left-hand corner of any transportation problem

Minimum Cost Method (MCM)

- also known as Greedy Method - a systematized procedure used to find an initial feasible solution to a transportation problem; it is easy to use and provides good (but not optimal) solution.

Vogels Approximation Method

- an algorithm that finds an initial feasible solution to a transportation problem by considering the penalty cost of not using the cheapest available route.

Example:

The Epsilon Computers Company sells desktop computers to universities in the university belt, and ship them from three distribution warehouses. The firm is able to supply the following numbers of desktop computers to the universities by the beginning of the academic year:
Distribution Warehouses Supply

Sta. Mesa Taft Avenue Divisoria Total

150 200 50 400

Universities have ordered desktop computers that must be delivered and installed by the beginning of the academic year:
University/ Colleges Demand (Desktop Computers)

CEU FEU UE Total

100 80 220 400

The shipping cost per desktop computer from each distributor to each university are as follows:
At
From 1 2 3 A 7 10 6 B 5 12 3 C 9 10 14

Requirement: Find the initial solution using the three methods.

Establish the transportation tableau

To From
7 5 5 12 12 9

Supply

1
10 10 10 10

150 200
9 9 3 3 14 14

3
Demand 100 80 220

50
400

Observe the variable representation in each square. To A

7 7 1 10 10 2 12 12 10 200

B
5 5

C
9

Supply

From
150

99
3 Demand 100 80

3 3

14 14 50 220 400

Objective Function

Minimize
Constraints

Subject to:

NORTHWEST CORNER RULE

Step 1
To

NORTHWEST CORNER RULE

A
7 7

B
5 5

C
9

Supply
50 (150)

From
1

100
10 10 12 12 10

200

9
3 Demand (100) 80

3 3

14 14
50 220 400

Step 2.
To From

NORTHWEST CORNER RULE

A
7 7

B
5 5 50 10 10 12 12

C
9

Supply

100

(150) 10 200

9
3 Demand (100) 30 (80)

3 3

14
50 220 400

NORTHWEST CORNER RULE

Step 3.
To From
7 7 1 5 5 50 10 10 2 30 12 12 10 9 (150) 170 (200)

Supply

100

9
3 Demand (100) (80)

3 3

14
50 220 400

Step 4.
To From

NORTHWEST CORNER RULE

A
77

B
5 5 50 10 10 12 12 30

C
9

Supply

100

(150) 10 10 170 3 3 14 14 50 (200)

9
3 Demand (100) (80)

50 (220)

400

NORTHWEST CORNER RULE

Step 5.
To A
7 7 1

B
5 5 50 10 10 12 12 30

C
9

Supply

From
100
(150) 10 170 (200)

99
3 Demand (100) (80)

3 3
50

14 14
(50) 400 (220)

MINIMUM COST METHOD

MINIMUM COST METHOD

STEP 1

To From

A
7 7

B
5 5

C
99

Supply

150

10 10
2 99

12 12

10 10
200

3 3

14 14

3
Demand 100

50
30 (80) 220

50
400

MINIMUM COST METHOD

STEP 2

To

A
77

B
5 5 30 10 10 12 12

C
99

Supply
120 (150)

From
1

10 10 200

99
3 Demand 100 50 80

3 3

14 14 50 220 400

MINIMUM COST METHOD

To From

A
7 7

B
5 5 30

C
9

Supply
20 (150)

100

10 10
2 9 9

12 12

10 10
200

3 3

14 14

3
Demand 100

50
80 220

50
400

MINIMUM COST METHOD

STEP 4

To From

A
7 7

B
5 5 30

C
9 20

Supply

100

150

10
2 9 9

12 12

10 10
200

3 3

14 14

3
Demand 100

50
80 200 (220)

50
400

MINIMUM COST METHOD

STEP 5

To

A
7 7

B
5 5 30 10 10 12 12

C
9 20 10 200

Supply

From
1 100 150

200

99
3 Demand 100 50 80

3 3

14 14
50 220 400

Vogels Approximation Model

Vogels Approximation Method

Step 1
Row /Column Second Lowest Cost Lowest Cost Opportunity Cost

1 2
3 A B C

7 10
6 7 5 10

5 10
3 6 3 9

2 0
3 1 2 1 largest

Vogels Approximation Method

Step 2
To A
7 7 1 10 10 2 12 12 10 200

B
5 5

C
9

Supply

From
150

9
3 Demand 100 50 30 (80)

14
50 220 400

Vogels Approximation Model

Step 3
Row/Column Second Lowest Cost Lowest Cost Opportunity Cost

1
2 A B C

7
10 10 12 10

5
10 7 5 9

2
0 3 7 1 largest

Step 4

Vogels Approximation Model

To A
7 7 1 10 10 2 30 12 12 10 200

B
5

C
9

Supply
120 (150)

From

9
3 Demand 100 50 80

14 14
50 220 400

Vogels Approximation Model

Step 5
Row/Column Second Lowest Cost 9 10 10 10 Lowest Cost Opportunity Cost 2 0 3 1 largest

1 2 A C

7 10 7 9

Vogels Approximation Model

Step 6
To A
7 7 1

B
5 30 10 10 12 12

C
9

Supply
20 (150)

From
100

10 200

9
3 Demand 100 50 30 (80)

14
50 220 400

Vogels Transportation Model

Step 7
To A
7 7 1

B
5 30 10 10 12 12

C
9 20 10 200

Supply

From
100
150

200

9
3 Demand 100 50 30 (80)

14
50 220 400

Methods in Establishing the Optimal Feasible Solution

1.

A procedure for determining if a solution to a transportation problem is optimal that involves tracing closed paths from each unused square through stone squares. The method derives its name from the analogy of crossing a pond using stepping stones. The occupied cells are analogous to the stepping stones, which are used in making certain movements in this method.

Stepping

Stone

Method

(SSM)

2. Modified Distribution Method (MODI) A procedure for determining the per-unit cost change associated with assigning flow to an unused square in the transportation problem

Minimization Problem Using Stepping Stone Method

Example:

The Epsilon Computers Company sells desktop computers to universities in the university belt, and ship them from three distribution warehouses. The firm is able to supply the following numbers of desktop computers to the universities by the beginning of the academic year:
Distribution Warehouses Supply

Sta. Mesa Taft Avenue Divisoria Total

150 200 50 400

Universities have ordered desktop computers that must be delivered and installed by the beginning of the academic year:
University/ Colleges Demand (Desktop Computers)

CEU FEU UE Total

100 80 220 400

The shipping cost per desktop computer from each distributor to each university are as follows:
At
From 1 2 3 A 7 10 6 B 5 12 3 C 9 10 14

With cost minimization as a criterion, Epsilon Company wants to determine how many desktop computers should be shipped from each warehouse to each university. a. Find the initial solution using Northwest Corner Rule (NCR). b. Determine the optimal solution using Stepping Stone Method (SSM) and Modified Distribution (MODI).

Step 1 Establish the Mathematical Model for the problem.

Let 1 2 3 A B C Sta. Mesa Taft Avenue Divisoria CEU FEU UE

Step 2: Establish the transportation tableau.

To A 7 1 10 2 12 10 200 B 5 C 9 150 Supply

From

9
3 Demand 100 80

3
220

14
50 400

Step 3:Set up the initial feasible solution using Northwest Corner Rule (NCR).
To A
7 1

B
5 50 10 12 30

C
9

Supply

From
100
(150) 10 170 (200)

9
3 Demand (100) (80)

3
50 (220)

14
(50) 400

Step 4:Compute the stone squares.

Source-Destination Combination Quantity Shipped x Unit Cost Total Cost

XA XB XB XC XC

100 50 30 170 50

x x x x x

7 5 12 10 14

700 250 360 1,700 700

P 3,710

Total Transportation Cost

Step 5
To From 7 1 5 9 150 A B C Supply

10
2 9

12
3 80 220

10
200 14

3
Demand 100

50
400

Step 6:Compute for closed path and improvement indices for the initial tableau.
Improvement Index is the increase/decrease in a total cost that would result from reallocating one unit to an unused square. Unused Closed Path Computation of Square Improvement Indices XC + XC - XB + XB + 9 5 + 12 10 = XA XC 6 XA + XA - XA + XB + 10 7 + 5 12 = XB XB -4 + XA - XA + XB +6 7 + 5 12 + XB + XC - XC 10 14 = -12 + XB - XB + XC + 3 12 + 10 14 XC = -13

Alternative Optimal Solution

A transportation problem has an alternative optimal solution, if zero in the final improvement index solution.
Example 5.3: Solve the given transportation problem using Minimum Cost Method and Stepping Stone Method.
Minimize: Zj = 7x1a + 12X1B + 8x1C + 10X2A + 5X2B +3X2c + 9X3A + 4X3B + 10X3C Subject to:
X1A + X1B + X1C = 40 X2A + X2B + X2C = 45 X3A + X3B + X3C = 30 X1A + X2A + X3A = 35 X1B + X2B + X3B = 20 X1C + X2C +X3C = 60

Xij 0

Solution:
Tableau 1 TO FROM A B C SUPPLY

1 2 3
Demand 35

7
35

12
5

8
40

10
9
20

5
45

3
45

4
10

10
30

20

60

115

Here comes your footer Page 52

Step 2: Solve for the stone squares.

Source-Destination Combination

Quantity X Unit Shipped Cost

Total Cost

X1A X1C X2C X3B X3C

TOTAL TRANSPORTATION COST

35 X 7 5X8 45 X 3 20 X 4 10 X10

245 40 135 80 100

P 600

Here comes your footer Page 53

Step 3. Test the solution for improvement by determining the improvement index Unused Closed Path Computation of
square X1B X2A X2B X3A +X1B X1C + X3C X3B +X2A X1A X1C X2C +X2B X2C + X2C X2B +X3A X1A + X1C X3C Improvement Indices + 12 -8 + 10 4 = 10 +10 7 + 8 3 = 8 +5 -3 + 10 -4 = 8 +9 -7 +8 -10 = 0

Here comes your footer Page 54

The optimal solution and the minimum cost are X1A = 35 X1C = 5 X2C = 45 X3B = 1- X3C 30

Zj = 7(35) + 12(0) + 8(5) + 10(0) + 5(0) + 3(45) +9(0) +4(20) +10(10) =245 + 0 + 40 + 0 + 0 +135 + 0 + 80 + 100 =600
Notice that there is a zero entry in the improvement index. We can select it to obtain an alternative solution without affecting the total transportation cost.

Step 4. Identify the zero entry in improvement index. Find the closed path into X3A and allocate 10 for the amount of X3c; then balance the stone square according to the total amount needed in each row and column

TO FROM

SUPPLY

1 2 3
Demand 35

7
25

12
15

8
40

10

5
45

3
45

9
10 20

4 20 60

10
30

115

Here comes your footer Page 56

Step 5. Solve for the stone squares.

Source-Destination Combination

Quantity X Unit Shipped Cost

Total Cost

X1A X1C X2C X3A X3b

TOTAL TRANSPORTATION COST

25 X 7 15 X 8 45 X 3 10 X 9 20 X4

175 120 135 90 80

P 600

Here comes your footer Page 57

Step 6. Test the solution for improvement by determining the improvement index Unused Closed Path Computation of
square Improvement Indices

X1B X2A X2B X3C

+X1B X1A + X3A X3B +X2A X1A X1C X2C +X2B X2C + X1CX1B+X3A-X3B +X3C X1C + X1A X3A

+ 12 -8 + 10 4 = 10 +10 7 + 8 3 = 8 +5 -3 + 10 -4 = 8 +9 -7 +8 -10 = 0

Here comes your footer Page 58

The optimal solution and the minimum cost are X1A = 35 X1C = 5 X2C = 45 X3B = 10 X3C 30
Zj = 7(25) + 12(0) +8(15) +10(0) + 5(0) + 3(45) + 9(10) + 4(20) + 10(0) =175 + 0 + 120 + 0 + 0 + 135 + 90 + 80 + 0 =600 Observe that the total transportation costs of the two solution sets are equal but they are diferent in shipping assignments.

Here comes your footer Page 59

Balanced and Unbalanced Transportation Model

Balanced Transportation Model -SUPPLY=DEMAND Unbalanced Transportation Model -SUPPLY=DEMAND

Demand exceeds Supply

-add a DUMMY SOURCE

Minimize Zj: 6X1A+10X1B+8X1C+4X2A+12X2B+5X2C+7X3A+11X3B+ 11X3C