registration
Quantitative Techniques For Management

Quantitative Techniques For Management

This course contains the basics of Quantitative Techniques For Management

Course introduction
Interview Questions
Pragnya Meter Exam

Quantitative Techniques For Management

Transportation Model

The transportation problem is one of the subclasses of linear programming problem where the objective is to transport various quantities of a single homogeneous product that are initially stored at various origins, to different destinations in  such a way that the total transportation is minimum.

F.I. Hitchaxic developed the basic transportation problem in 1941.  However it could be solved for optimally as an answer to complex business problem only in 1951, when George B. Dantzig applied the concept of Linear Programming in solving the Transportation models.

Transportation models or problems are primarily concerned with the optimal (best possible) way in which a product produced at different factories or plants (called supply origins) can be transported to a number of warehouses (called demand destinations). The objective in a transportation problem is to fully satisfy the destination requirements within the operating production capacity constraints at the minimum possible cost.

Whenever there is a physical movement of goods from the point of manufacture to the final consumers through a variety of channels of distribution (wholesalers, retailers, distributors etc.), there is a need to minimize the cost of transportation so as to increase the profit on sales.  Transportation problems arise in all such cases.

It aims at providing  assistance to the top management in ascertaining how many units 1of a particular product should be transported from each supply  origin to each demand destinations to that the total prevailing  demand for the company’s product is satisfied, while at the same  time the total transportation costs are minimized.

MATHEMATICAL FORMULATION

Mathematically a transportation problem is nothing but a special linear programming problem in which the objective function is to minimize the cost of transportation subjected to the demand and supply constraints.  

The transportation problem applies to situations where a single commodity is to be transported from various sources of supply (origins) to various demands (destinations). Let there be m sources of supply s1, s2, .…..............sm having ai ( i = 1,2,......m) units of supplies respectively to be transported among n destinations d1, d2………dn with bj ( j = 1,2…..n) units of requirements respectively.

Let cij be the cost for shipping one unit of the commodity from source i, to destination j for each route. If xij represents the units shipped per route from source i, to destination j, then the problem is to determine the transportation schedule which minimizes the total transportation cost of satisfying supply and demand conditions.

The transportation problem can be stated mathematically as a linear programming problem as below:

NETWORK REPRESENTATION OF TRANSPORTATION MODEL

The transportation model is represented by a network diagram in Figure

Network Transportation Model

where,
m be the number of sources,
n be the number of destinations,
sm be the supply at source m,
dn be the demand at destination n,
cij be the cost of transportation from source i to destination j, and
xij be the number of units to be shipped from source i to destination j.

The objective is to minimize the total transportation cost by determining the unknown xij, i.e., the number of units to be shipped from the sources and the destinations while satisfying all the supply and demand requirements.

GENERAL REPRESENTATION OF TRANSPORTATION MODEL

 GENERAL REPRESENTATION OF TRANSPORTATION MODEL

The Transportation problem can also be represented in a tabular form as shown in Table
Let Cij be the cost of transporting a unit of the product from ith origin to jth destination.
ai be the quantity of the commodity available at source i,
bj be the quantity of the commodity needed at destination j, and
xij be the quantity transported from ith source to jth destination

Tabular Representation of Transportation Model

If the total supply is equal to total demand, then the given transportation problem is a balanced one.

USE OF LINEAR PROGRAMMING TO SOLVE TRANSPORTATION PROBLEM

Linear Programming Solution

The network diagram shown in Figure represents the transportation model of M/s GM Textiles units located at Chennai, Coimbatore and Madurai. GM Textiles produces ready-made garments at these locations with capacities 6000, 5000 and 4000 units per week at Chennai, Coimbatore and Madurai respectively. The textile unit distributes its ready-made garments through four of its wholesale distributors situated at four locations Bangalore, Hyderabad, Cochin and Goa. The weekly demand of the distributors are 5000, 4000, 2000 and 4000 units for Bangalore, Hyderabad, Cochin and Goa respectively.

The cost of transportation per unit varies between different supply points and destination points. The transportation costs are given in the network diagram.

The management of GM Textiles would like to determine the number of units to be shipped from each textile unit to satisfy the demand of each wholesale distributor. The supply, demand and transportation cost are as follows:

 Production Capacities

Demand Requirements

Transportation cost per unit


A linear programming model can be used to solve the transportation problem.

Let,

X11 be number of units shipped from source1 (Chennai) to destination 1 (B’lore).
X12 be number of units shipped from source1 (Chennai) to destination 2 (Hyderabad).
X13 number of units shipped from source 1 (Chennai) to destination 3 (Cochin).
X14 number of units shipped from source 1 (Chennai) to destination 4 (Goa) and so on.
Xij = number of units shipped from source i to destination j, where i = 1,2,……..m and, j = 1,2,………n.

FORMULATION OF LP MODEL

Objective function: The objective is to minimize the total transportation cost. Using the cost data table, the following equation can be arrived at:

Transportation cost for units
shipped from Chennai = 5x11+6x12+9x13+7x14
Transportation cost for units
shipped from Coimbatore = 7x21+8x22+2x23+4x24
Transportation cost for units
shipped from Madurai = 6x31+3x32+5x33+3x34

Combining the transportation cost for all the units shipped from each supply point with the objective to minimize the transportation cost, the objective function will be,
Minimize Z = 5x11+6x12+9x13+7x14+7x21+8x22+2x23+4x24+6x31+3x32+5x33+3x34

Constraints:
In transportation problems, there are supply constraints for each source, and demand
constraints for each destination.

Supply constraints:
For Chennai, x11+ x12+ x13+ x14< 6000
For Coimbatore, x21+ x22+ x23+ x24< 5000
For Madurai, x31+ x32+ x33+ x34< 4000

Demand constraints:
For B’lore, x11+ x21+ x31 = 5000
For Hyderabad, x12 + x22 + x32 = 4000
For Cochin, x13 + x23 + x33 = 2000
For Goa, x14 + x24 + x34 = 4000

The linear programming model for GM Textiles will be write in the next line. Minimize
Z = 5x11 + 6x12 + 9x13 + 7x14 + 7x21 + 8x22 + 2x23 + 4x24 + 6x31 + 3x32 + 5x33 + 3x34
Subject to constraints,
x11+x12+x13+x14< 6000      .........................(i)
X 21+x22+x23+x24< 5000    .........................(ii)
x31+x32+x33+x34< 4000      .........................(iii)
x11+x21+x31 = 5000            ..........................(iv)
x12+x22+x32 = 4000            ..........................(v)
x13+x23+x33 = 2000            ..........................(vi)
x14+x24+x34 = 4000             .........................(vii)
Where, xij> 0 for i = 1, 2, 3 and j = 1, 2, 3, 4.

SOLVING TRANSPORTATION PROBLEM USING COMPUTER

Input screen for solving TP & LP models using TORA

 TORA Screen for TP Model

Output screen using TP & LP models

TORA Screen for LP Model

Example : Consider the following transportation problem and develop a linear programming (LP) model.

 Transportation Problem

Solution: Let xij be the number of units to be transported from the source i to the destination

j, where i = 1, 2, 3,…m and j = 1, 2, 3,…n.

The linear programming model is

Minimize Z = 15x11+20x12+30x13+10x21+9x22+15x23+14x31+12x32+18x33

Subject to constraints,
x11+x12+x13< 350   ...................(i)
x21+x22+x23< 200   ...................(ii)
x31+x32+x33< 400   ...................(iii)
x11+x12+x31 = 250   ...................(iv)
x12+x22+x32 = 400   ...................(v)
x13+x23+x33 = 300   ...................(vi)
xij> 0 for all i and j.

In the above LP problem, there are m × n = 3 × 3 = 9 decision variables and m + n = 3 + 3 = 6 constraints.

BALANCED TRANSPORTATION PROBLEM

When the total supplies of all the sources are equal to the total demand of all destinations, the problem is a balanced transportation problem.

Total supply = Total demand

UNBALANCED TRANSPORTATION PROBLEM

When the total supply of all the sources is not equal to the total demand of all destinations, the problem is an unbalanced transportation problem.

Total supply ≠ Total demand

Demand Less than Supply

In real-life, supply and demand requirements will rarely be equal. This is because of variation in production from the supplier end, and variations in forecast from the customer end. Supply variations may be because of shortage of raw materials, labour problems, Transportation Model improper planning and scheduling. Demand variations may be because of change in customer preference, change in prices and introduction of new products by competitors.

These unbalanced problems can be easily solved by introducing dummy sources and dummy destinations. If the total supply is greater than the total demand, a dummy destination (dummy column) with demand equal to the supply surplus is added. If the total demand is greater than the total supply, a dummy source (dummy row) with supply equal to the demand surplus is added. The unit transportation cost for the dummy column and dummy row are assigned zero values, because no shipment is actually made in case of a dummy source and dummy destination.

Example : Check whether the given transportation problem shown in Table is a balanced one. If not, convert the unbalanced problem into a balanced transportation problem.

Transportation Model with Supply Exceeding Demand

Solution: For the given problem, the total supply is not equal to the total demand.

The given problem is an unbalanced transportation problem. To convert the unbalanced transportation problem into a balanced problem, add a dummy destination (dummy column). i.e., the demand of the dummy destination is equal to,

Thus, a dummy destination is added to the table, with a demand of 100 units. The modified table is shown in Table which has been converted into a balanced transportation table. The unit costs of transportation of dummy destinations are assigned as zero.

 Dummy Destination Added

Similarly,

Demand Greater than Supply

Example : Convert the transportation problem shown in Table into a balanced problem.

Demand Exceeding Supply

Solution: The given problem is,

The given problem is an unbalanced one. To convert it into a balanced transportation problem, include a dummy source (dummy row) as shown in Table

Balanced TP Model

PROCEDURE TO SOLVE TRANSPORTATION PROBLEM

Step 1: Formulate the problem.

Formulate the given problem and set up in a matrix form. Check whether the problem is a balanced or unbalanced transportation problem. If unbalanced, add dummy source (row) or dummy destination (column) as required.

Step 2: Obtain the initial feasible solution.

The initial feasible solution can be obtained by any of the following three methods:

  1. Northwest Corner Method (NWC)
  2. Least Cost Method (LCM)
  3. Vogel’s Approximation Method (VAM)

The transportation cost of the initial basic feasible solution through Vogel’s approximation method, VAM will be the least when compared to the other two methods which gives the value nearer to the optimal solution or optimal solution itself. Algorithms for all the three methods to find the initial basic feasible solution are given.

Algorithm for North-West Corner Method (NWC)

  1. Select the North-west (i.e., upper left) corner cell of the table and allocate the maximum possible units between the supply and demand requirements. During allocation, the transportation cost is completely discarded (not taken into consideration).
  2. Delete that row or column which has no values (fully exhausted) for supply or demand.
  3. Now, with the new reduced table, again select the North-west corner cell and allocate the available values.
  4. Repeat steps (ii) and (iii) until all the supply and demand values are zero.
  5. Obtain the initial basic feasible solution.

Algorithm for Least Cost Method (LCM)

  1. Select the smallest transportation cost cell available in the entire table and allocate the supply and demand.
  2. Delete that row/column which has exhausted. The deleted row/column must not be considered for further allocation.
  3. Again select the smallest cost cell in the existing table and allocate. (Note: In case, if there are more than one smallest costs, select the cells where maximum allocation can be made)
  4. Obtain the initial basic feasible solution.

Algorithm for Vogel’s Approximation Method (VAM)

  1. Calculate penalties for each row and column by taking the difference between the smallest cost and next highest cost available in that row/column. If there are two smallest costs, then the penalty is zero.
  2. Select the row/column, which has the largest penalty and make allocation in the cell having the least cost in the selected row/column. If two or more equal penalties exist, select one where a row/column contains minimum unit cost. If there is again a tie, select one where maximum allocation can be made.
  3. Delete the row/column, which has satisfied the supply and demand.
  4. Repeat steps (i) and (ii) until the entire supply and demands are satisfied.
  5. Obtain the initial basic feasible solution.

Remarks: The initial solution obtained by any of the three methods must satisfy the following conditions:

  1. The solution must be feasible, i.e., the supply and demand constraints must be satisfied (also known as rim conditions).
  2. The number of positive allocations, N must be equal to m+n-1, where m is the number of rows and n is the number of columns.

DEGENERACY IN TRANSPORTATION PROBLEMS

Step 3: Check for degeneracy

In a standard transportation problem with m sources of supply and n demand destinations, the test of optimality of any feasible solution requires allocations in m + n – 1 independent cells. If the number of allocations is short of the required number, then the solution is said to be degenerate.

If number of allocations, N = m + n – 1, then degeneracy does not exist. Go to Step 5.
If number of allocations, N ¹ m + n – 1, then degeneracy does exist. Go to Step 4.

Step 4: Resolving degeneracy

In order to resolve degeneracy, the conventional method is to allocate an infinitesimally small amount e to one of the independent cells i.e., allocate a small positive quantity e to one or more unoccupied cell that have lowest transportation costs, so as to make m + n – 1 allocations (i.e., to satisfy the condition N = m + n – 1).

In other words, the allocation of e should avoid a closed loop and should not have a path. Once this is done, the test of optimality is applied and, if necessary, the solution is improved in the normal was until optimality is reached. The following table shows independent allocations.

 Independent Allocations

The following Tables 6.10 (a), (b) and (c) show non-independent allocations.

Non-Independent Allocations

Optimal Solution

Step 5: Test for optimality

The solution is tested for optimality using the Modified Distribution (MODI) method (also known as U-V method).
Once an initial solution is obtained, the next step is to test its optimality.

An optimal solution is one in which there are no other transportation routes that would reduce the total transportation cost, for which we have to evaluate each unoccupied cell in the table in terms of opportunity cost. In this process, if there is no negative opportunity cost, and the solution is an optimal solution.

(i) Row 1, row 2,…, row i of the cost matrix are assigned with variables u1, u2, …,ui and the column 1, column 2,…, column j are assigned with variables v1, v2, …,vj respectively.

(ii) Initially, assume any one of U Transportation Model i values as zero and compute the values for u1, u2, …,ui and v1, v2, …,vj by applying the formula for occupied cell.

For occupied cells,

cij + ui + vj = 0

(iii) Obtain all the values of cij for unoccupied cells by applying the formula for unoccupied cell.

For unoccupied cells,

Step 6: Procedure for shifting of allocations

Select the cell which has the most negative C ij value and introduce a positive quantity called ‘q’ in that cell. To balance that row, allocate a ‘– q’ to that row in occupied cell. Again, to balance that column put a positive ‘q’ in an occupied cell and similarly a ‘-q’ to that row. Connecting all the ‘q’s and ‘-q’s, a closed loop is formed.

Two cases are represented in Table In Table if all the q allocations are joined by horizontal and vertical lines, a closed loop is obtained.

The set of cells forming a closed loop is

CL = {(A, 1), (A, 3), (C, 3), (C, 4), (E, 4), (E, 1), (A, 1)}

The loop in Table 6.11(b) is not allowed because the cell (D3) appears twice.

Showing Closed Loop

Conditions for forming a loop

(i) The start and end points of a loop must be the same.
(ii) The lines connecting the cells must be horizontal and vertical.
(iii) The turns must be taken at occupied cells only.
(iv) Take a shortest path possible (for easy calculations).

Remarks on forming a loop

(i) Every loop has an even number of cells and at least four cells
(ii) Each row or column should have only one ‘+’ and ‘–’ sign.
(iii) Closed loop may or may not be square in shape. It can also be a rectangle or a stepped shape.
(iv) It doesn’t matter whether the loop is traced in a clockwise or anticlockwise direction.

Take the most negative '– q' value, and shift the allocated cells accordingly by adding the value in positive cells and subtracting it in the negative cells. This gives a new improved table. Then go to step 5 to test for optimality.

Step 7: Calculate the Total Transportation Cost.

Since all the C ij values are positive, optimality is reached and hence the present allocations are the optimum allocations. Calculate the total transportation cost by summing the product of allocated units and unit costs.

Example : The cost of transportation per unit from three sources and four destinations are given in the following table Obtain the initial basic feasible solutions using the following methods.

(i) North-west corner method
(ii) Least cost method
(iii) Vogel’s approximation method

Transportation Model

Solution: The problem given in Table is a balanced one as the total sum of supply is equal to the total sum of demand. The problem can be solved by all the three methods.

North-West Corner Method: In the given matrix, select the North-West corner cell. The North-West corner cell is (1,1) and the supply and demand values corresponding to cell (1,1) are 250 and 200 respectively. Allocate the maximum possible value to satisfy the demand from the supply. Here the demand and supply are 200 and 250 respectively. Hence allocate 200 to the cell (1,1) as shown in Table.

Conditions for forming a loop

(i) The start and end points of a loop must be the same.
(ii) The lines connecting the cells must be horizontal and vertical.
(iii) The turns must be taken at occupied cells only.
(iv) Take a shortest path possible (for easy calculations).

Remarks on forming a loop

(i) Every loop has an even number of cells and at least four cells
(ii) Each row or column should have only one ‘+’ and ‘–’ sign.
(iii) Closed loop may or may not be square in shape. It can also be a rectangle or a stepped shape.
(iv) It doesn’t matter whether the loop is traced in a clockwise or anticlockwise direction.

Take the most negative '– q' value, and shift the allocated cells accordingly by adding the value in positive cells and subtracting it in the negative cells. This gives a new improved table. Then go to step 5 to test for optimality.

 Allocated 200 to the Cell (1, 1)

Now, delete the exhausted column 1 which gives a new reduced table as shown in the following tables. Again repeat the steps.

Exhausted Column 1 Deleted

Table after deleting Row 1

 Exhausted Row 1 Deleted

Table after deleting column 2

 Exhausted Column 2 Deleted

Finally, after deleting Row 2, we have

 Exhausted Row 2 Deleted

Now only source 3 is left. Allocating to destinations 3 and 4 satisfies the supply of 500. The initial basic feasible solution using North-west corner method is shown in the following table

Initial Basic Feasible Solution Using NWC Method

Transportation cost     = (4 × 200) + (2 × 50) + (7 × 350) + (5 × 100) +(2 × 300) + (1 × 300)
                                 = 800 + 100 + 2450 + 500 + 600 + 300
                                 = Rs. 4,750.00

Least Cost Method

Select the minimum cost cell from the entire table, the least cell is (3,4). The corresponding supply and demand values are 500 and 300 respectively. Allocate the maximum possible units. The allocation is shown in Table.

 Allocation of Maximum Possible Units

From the supply value of 500, the demand value of 300 is satisfied. Subtract 300 from the supply value of 500 and subtract 300 from the demand value of 300. The demand of destination 4 is fully satisfied. Hence, delete the column 4; as a result we get, the table as shown in the following table.

Exhausted Column 4 Deleted

Now, again take the minimum cost value available in the existing table and allocate it with a value of 250 in the cell (1,2).
The reduced matrix is shown in Table

Exhausted Row 1 Deleted

In the reduced table, the minimum value 3 exists in cell (2,1) and (3,3), which is a tie. If there is a tie, it is preferable to select a cell where maximum allocation can be made. In this case, the maximum allocation is 200 in both the cells. Choose a cell arbitrarily and allocate. The cell allocated in (2,1) is shown in Table. The reduced matrix is shown in Table.

Reduced Matrix

Now, deleting the exhausted demand row 3, we get the matrix as shown in the following table

Exhausted Row 3 Deleted

The initial basic feasible solution using least cost method is shown in a single table

Initial Basic Feasible Solution Using LCM Method

Transportation Cost = (2 × 250)+ (3 × 200) + (7 × 150) + (5 × 100)+ ( 3 × 200) +(1 × 300)
                             = 500 + 600 + 1050 + 500 + 600 + 300 = Rs. 3550

Vogel’s Approximation Method (VAM): The penalties for each row and column are calculated (steps given on pages 176-77) Choose the row/column, which has the maximum value for allocation. In this case there are five penalties, which have the maximum value 2. The cell with least cost is Row 3 and hence select cell (3,4) for allocation. The supply and demand are 500 and 300 respectively and hence allocate 300 in cell (3,4) as shown in Table

Penalty Calculation for each Row and Column

Since the demand is satisfied for destination 4, delete column 4. Now again calculate the penalties for the remaining rows and columns.

Exhausted Column 4 Deleted

In the following table shown, there are four maximum penalties of values which is 2. Selecting the least cost cell, (1,2) which has the least unit transportation cost 2. The cell (1, 2) is selected for allocation as shown in the previous table. The following table shows the reduced table after deleting row l.

Row 1 Deleted

After deleting column 1 we get the table as shown in the table below.

Column 1 Deleted

Finally we get the reduced table as shown in the following table.

 Final Reduced Table

The initial basic feasible solution is shown in the following table.

Initial Basic Feasible Solution

Transportation cost = (2 × 250) + (3 × 200) + (5 × 250) + (4 × 150) + (3 × 50) +(1 × 300)
                             = 500 + 600 + 1250 + 600 + 150 + 300
                             = Rs. 3,400.00

Example : Find the initial basic solution for the transportation problem and hence solve it.

Transportation Problem

Solution: Vogel’s Approximation Method (VAM) is preferred to find initial feasible solution.
The advantage of this method is that it gives an initial solution which is nearer to an optimal solution or the optimal solution itself.

Step 1: The given transportation problem is a balanced one as the sum of supply equals to sum of demand.

Step 2: The initial basic solution is found by applying the Vogel’s Approximation method and the result is shown in the following table.

Initial Basic Solution Found by Applying VAM

Step 3: Calculate the Total Transportation Cost.

Initial Transportation cost = (2 × 250) + (3 × 200) + (5 × 250) + (4 × 150) + (3 × 50) + (1 × 300)
                                     = 500 + 600 + 1250 + 600 + 150 + 300
                                     = Rs. 3,400

Step 4: Check for degeneracy. For this, verify the condition,
Number of allocations, N= m + n – 1
                                 6 = 3 + 4 – 1
                                 6 = 6
Since the condition is satisfied, degeneracy does not exist.

Step 5: Test for optimality using modified distribution method. Compute the values of U i and vj for rows and columns respectively by applying the formula for occupied cells.

cij+ui+vj = 0

Then, the opportunity cost for each unoccupied cell is calculated using the formula C ij = cij + ui + vj and denoted at the left hand bottom corner of each unoccupied cell. The computed valued of uj and vi and are shown in the table below.

Calculation of the Opportunity Cost

Calculate the values of ui and vj, using the formula for occupied cells. Assume any one
of ui and vj value as zero (U3 is taken as 0)

                   cij + ui + vj = 0
         4 + 0 + v2 = 0, v2 = – 4
         5 + v2– 3 = 0, u2 = – 2
         3 – 2 + v1 = 0, v1 = – 1
         2 – 4 + u1 = 0, u1 = 2

Calculate the values of C ij , using the formula for unoccupied cells

C ij = cij + ui + vj
c11 = 4+2 –1 = 5
c13 = 7+2 –3 = 6
c14 = 3+2 –1 = 4
C22 = 7–2 – 4 = 1
C24 = 8–2 – 1 = 5
C31 = 9 +0 –1 = 8

Since all the opportunity cost, C ij values are positive the solution is optimum.
Total transportation cost = (2 × 25) + (3 × 200) + (5 × 250) + (4 × 150) + (3 × 50)+ (1 × 300)
                                    = 50 + 600 +1250 + 600 + 150 + 300
                                    = Rs 2,950/-

Example : Find the initial basic feasible solution for the transportation problem given in Table.

Transportation Problem

Solution : The initial basic feasible solution using VAM is shown in table below.

Initial Basic Feasible Solution Using VAM

Check for degeneracy,
The number of allocations, N must be equal to m + n – 1.
i.e.,  N = m+n – 1
        5 = 3+3 – 1
since 4 ≠5, therefore degeneracy exists.

To overcome degeneracy, the condition N = m + n – 1 is satisfied by allocating a very small quantity, close to zero in an occupied independent cell. (i.e., it should not form a closed loop) or the cell having the lowest transportation cost. This quantity is denoted by e.

This quantity would not affect the total cost as well as the supply and demand values. Table shows the resolved degenerate table.

Resolved Degenerate Table

Total transportation cost = (50 × 1)+ (90 × 3) + (200 × 2) + (50 × 2) + (250 × e)
= 50 + 270 + 400 + 100 + 250 e
= 820 + 250 e = Rs. 820 since e ® 0
Example : Obtain an optimal solution for the transportation problem by MODI method given in Table.

Transportation Problem

Solution:
Step1: The initial basic feasible solution is found using Vogel’s Approximation Method as shown in Table.

Initial Basic Feasible Solution Using VAM


Total transportation cost  = (19 × 5) + (10 × 2) + (40 × 7) + (60 × 2) + (8 × 8) +(20 × 10)
                                     = 95 + 20 + 280 + 120 + 64 + 200
                                     = Rs. 779.00
Step 2: To check for degeneracy, verify the number of allocations, N = m+n – 1.
In this problem, number of allocation is 6 which is equal m+n – 1.
∴ N = m + n – 1
    6 = 3 + 4 – 1
    6 = 6 therefore degeneracy does not exist.

Step 3: Test for optimality using MODI method. In Table 6.36 the values of Ui and Vj are calculated by applying the formula Cij + Ui + Vj = 0 for occupied cells.

 Optimality Test Using MODI Method

Find the values of the dual variables Ui and Vj for occupied cells.

Initially assume Ui = 0,
Cij + Ui + Vj = 0,

19 + 0 + V i = 0, V1 = – 19
10 + 0 + V4 = 0, V4 = – 10
60 + U2 – 10 = 0, U2 = – 50
20 + U3 – 10 = 0, U3 = – 10
8 – 10 + V2 = 0, V2 = 2
40 – 50 + V3 = 0, V3 = 10

C12 = 30 + 0 + 2 = 32
C13 = 50 + 0 + 10 = 60
C21 = 70 – 50 – 19 = 1
C22 = 30 – 50 + 2 = –18
C31 = 40 – 10 – 19 = 11
C33 = 70 – 10 + 10 = 70

In Table the cell (2,2) has the most negative opportunity cost. This negative cost has to be converted to a positive cost without altering the supply and demand value.

Step 4: Construct a closed loop . Introduce a quantity + q in the most negative cell (S2, D2 ) and a put – q in cell (S3, D2 ) in order to balance the column D2. Now, take a right angle turn and locate an occupied cell in column D4. The occupied cell is (S3, D4) and put a + q in that cell. Now, put a – q in cell (S2, D4 ) to balance the column D4. Join all the cells to have a complete closed path. The closed path is shown in Figure.

Closed Path

Now, identify the – q values, which are 2 and 8. Take the minimum value, 2 which is the allocating value. This value is then added to cells (S2, D2 ) and (S3, D4 ) which have ‘+’ signs and subtract from cells (S2, D4 ) and (S3, D2 ) which have ‘–’ signs. The process is shown in Figure.

 Closed Path

The table after reallocation is shown in Table below.

After Reallocation

Now, again check for degeneracy. Here allocation number is 6.
Verify whether number of allocations,
N = m + n – 1
6 = 3 + 4 – 1
6 = 6
therefore degeneracy does not exits.

Again find the values of Ui, Vj and cij for the Table 6.39 shown earlier.

For occupied cells, Cij + Ui + Vj = 0

19 + 0 + V1 = 0, V1 = – 19
10 + 0 + V4 = 0, V4 = – 10
20 + U3 – 10 = 0, U3 = – 10
8 – 10 + V2 = 0, V2 = 2
30 + U2 + 2 = 0, U2 = – 32
40 – 50 + V3 = 0, V3 = – 10

C12 = 30 + 0 + 20 = 50
C13 = 50 + 0 – 8 = 42
C21 = 70 – 32 – 19 = 19
C24 = 60 – 32 – 10 = 18
C31 = 40 – 10 – 19 = 11
C33 = 70 – 10 – 8 = 52

The values of the opportunity cost cij are positive. Hence the optimality is reached.
The final allocations are shown in Table.

 Final Allocation

V1 = – 19 V2 = 2 V3 = – 8 V4 = – 10

Total transportation cost = (19 × 5) + (10 × 2) + (30 × 2) + (40 × 7) + (8 × 6) + (20 × 12)
                                    = 95 + 20 + 60 + 280 + 48 + 240
                                    = Rs. 743

Example : Solve the transportation problem

The problem is unbalanced if S ai = S bj, that is, when the total supply is not equal to the total demand. Convert the unbalanced problem into a balanced one by adding a dummy
row or dummy column as required and solve.

Here the supply does not meet the demand and is short of 2 units. To convert it to a balanced transportation problem add a dummy row and assume the unit cost for the dummy cells as zero as shown in Table and solve.

Dummy Row Added to TP

MAXIMIZATION IN A TRANSPORTATION PROBLEM

There are certain types of transportation problems where the objective function is to be maximized instead of being minimized. These problems can be solved by converting the maximization problem into a minimization problem.

Example : A manufacturing company has four plants situated at different locations, all producing the same product. The manufacturing cost varies at each plant due to internal and external factors. The size of each plant varies, and hence the production capacities also vary. The cost and capacities at different locations are given in the following table:

Cost and Capacity of Different Plants

The company has five warehouses. The demands at these warehouses and the transportation costs per unit are given in the Table below. The selling price per unit is Rs. 30/-

 Transportation Problem

  1. Formulate the problem to maximize profits.
  2. Determine the solution using TORA.
  3. Find the total profit

Solution:
The objective is to maximize the profits. Formulation of transportation problem as profit matrix table is shown in Table. The profit values are arrived as follows.

Profit = Selling Price – Production cost –Transportation cost

Profit Matrix

Converting the profit matrix to an equivalent loss matrix by subtracting all the profit values from the highest value 13. Subtracting all the values from 13, the loss matrix obtained is shown in the Table

 Loss Matrix

(ii) To determine the initial solution using TORA

Input Screen:

TORA, Input Screen for TP Max Problem

Output Screen

 TORA Output Screen (Vogel’s Method)

The first iteration itself is optimal, hence optimality is reached.

(iii) To find the total cost:

The total maximization profit associated with the solution is
Total Profit

= (6 × 10) + (4 × 20) + (10 × 120) + (3 × 180) + (9 × 70) + (10 × 20)+ (13 × 80) +  (15 × 70)
= 60 + 80 + 1200 + 540 + 630 + 200 + 1040 + 1050
= Rs 4800.00

PROHIBITED ROUTES PROBLEM

Sometimes there may be situations, where it is not possible to use certain routes in a transportation problem. For example, road construction, bad road conditions, strike, unexpected floods, local traffic rules, etc. Such restrictions (or prohibitions) can be handled in the transportation problem by assigning a very high cost (say M or [infinity]) to the prohibited routes to ensure that routes will not be included in the optimal solution and then the problem is solved in the usual manner.

Example :The following transportation table shows the transportation cost per unit (in Rs.) from sources 1,2, and 3 to destinations A, B, C. Shipment of goods is prohibited from source 2 to destination C. Solve the transportation problem using TORA

Problem for TORA Solution

Solution: The entries of the transportation cost are made using TORA
Input Screen:

TP Prohibited Route TORA (Input Screen)

Output Screen:

TP Prohibited Route (TORA Output Screen)

From the output Schedule, there are no goods that are to be shipped from source 2 to destination C. The total transportation cost is Rs 4600 /-

TRANSHIPMENT PROBLEM

One requirement of the transportation problem is advance knowledge of the method of distribution of units from each source i to each destination j, so that the corresponding cost per unit (xij) can be determined. Sometimes, however, the best method of distribution is not clear because of the possibility of transshipments, whereby shipments would go through intermediate transfer points (which might be other sources or destinations).  

Such possibilities for transshipments could be investigated in advance to determine the cheapest route from each source to each destination. However, this might be a very complicated and time-consuming task if there are many possible intermediate transfer points. Therefore, it may be much more convenient to let a computer algorithm solve simultaneously for the amount to ship from each source to each destination and the route to follow for each shipment so as to minimize the total shipping cost.

This extension of the transportation problem to include the routing decisions is referred to as the transshipment problem. This problem is the special case of the minimum cost flow problem where there are no restrictions on the amount that can be shipped through each shipping lane (unlimited arc capacities). The network representation of such a problem, where each two-sided arrow indicates that a shipment can be sent in either direction between the corresponding pair of locations.

The objective of the transshipment problem is to determine how many units should be shipped over each node so that all the demand requirements are met with the minimum transportation cost.

Considering a company with its manufacturing facilities situated at two places, Coimbatore and Pune. The units produced at each facility are shipped to either of the company’s warehouse hubs located at Chennai and Mumbai. The company has its own retail outlets in Delhi, Hyderabad, Bangalore and Thiruvananthapuram. The network diagram representing the nodes and transportation per unit cost is shown in Figure. The supply and demand requirements are also given.

Manufacturing Warehouses Retail Outlets Demand facility (Origin nodes) (Transshipment nodes) (Destination nodes)

Network Representation of Transshipment Problem

Solving Transshipment Problem using Linear Programming

Let
xij be the number of units shipped from node i to node j,
x13 be the number of units shipped from Coimbatore to Chennai,
x24 be the number of units shipped from Pune to Mumbai, and so on

The following table shows the unit transportation cost from sources to destination.

TP of the Shipment

Objective
The objective is to minimize the total cost
Minimize
Z = 4x13+ 7x14+ 6x23+ 3x24+ 7x35+ 4x36+ 3x37+ 5x38+ 5x45+6x46+ 7x47+ 8x48

Constraints: The number of units shipped from Coimbatore must be less than or equal to 800. Because the supply from Coimbatore facility is 800 units. Therefore, the constraints equation is as follows:

x13+ x14< 800                                …………………….. (i)
Similarly, for Pune facility
x23+ x24< 600                                ……………………...(ii)
Now, considering the node 3,
Number of units shipped out from node 1 and 2 are,
x13+ x23
Number of units shipped out from node 3 is,
x35 + x36 + x37 + x38
The number of units shipped in must be equal to number of units shipped out, therefore
x13 + x23 = x35 + x36 + x37 + x38
Bringing all the variables to one side, we get
– x13– x23 + x35 + x36 + x37 + x38 = 0        ………….(iii)
Similarly for node 4
– x14– x24 + x45+x46 + x47 + x48 =0           …………..(iv)

Now considering the retail outlet nodes, the demand requirements of each outlet must be
satisfied. Therefore for retail node 5, the constraint equation is
x35 + x45 = 350                                          ................(v)
Similarly for nodes 6, 7, and 8, we get,
x36 + x46 = 200                                         ……...........(vi)
x37 + x47 = 400                                         ……...........(vii)
x38 + x48 = 450                                         ……...........(viii)
Linear Programming formulation,
Minimize Z = 4x13+7x14+6X22+3x24+7x35+4x36+3x37+5x38+5x45+6x46+7x47+8x48
Subject to constraints

Searches relevant to you
Top