This course contains the basics of Quantitative Techniques For Management

Course introductionTest Your Caliber

Interview Questions

Pragnya Meter Exam

##### List of Topics

- QUANTITATIVE TECHNIQUES – INTRODUCTION
- Measures of Central Tendency
- Mathematical Model
- Linear Programming: Graphical Method
- Linear Programming: Simplex Method
- Transportation Model
- ASSIGNMENT MODEL
- NETWORK MODEL
- WAITING MODEL (QUEUING THEORY)
- PROBABILITY
- THEORETICAL PROBABILITY DISTRIBUTIONS
- PROBABILITY DISTRIBUTION OF A RANDOM VARIABLE
- INVENTORY MODEL
- Game Theory
- Simulation

**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.

Mathematically a transportation problem is nothing but a special linear programming problem in which the ob_{j}ective function is to minimize the cost of transportation sub_{j}ected 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 s_{1}, s_{2}, .…..............s_{m} having ai ( i = 1,2,......m) units of supplies respectively to be transported among *n *destinations d_{1}, d_{2}………d_{n} with b_{j} ( j = 1,2…..n) units of requirements respectively.

Let c_{ij} 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:

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,

s_{m} be the supply at source m,

d_{n} be the demand at destination n,

c_{ij} be the cost of transportation from source i to destination j, and

x_{ij} 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 x_{ij}, 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**

The Transportation problem can also be represented in a tabular form as shown in Table

Let C_{ij} be the cost of transporting a unit of the product from ith origin to jth destination.

a_{i} be the quantity of the commodity available at source i,

b_{j} be the quantity of the commodity needed at destination j, and

x_{ij} 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.

** 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,

X_{11} be number of units shipped from source1 (Chennai) to destination 1 (B’lore).

X_{12} be number of units shipped from source1 (Chennai) to destination 2 (Hyderabad).

X_{13} number of units shipped from source 1 (Chennai) to destination 3 (Cochin).

X_{14} number of units shipped from source 1 (Chennai) to destination 4 (Goa) and so on.

X_{ij} = number of units shipped from source i to destination j, where i = 1,2,……..m and, j = 1,2,………n.

** 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 = 5x_{11}+6x_{12}+9x_{13}+7x_{14}

Transportation cost for units

shipped from Coimbatore = 7x_{21}+8x_{22}+2x_{23}+4x_{24}

Transportation cost for units

shipped from Madurai = 6x_{31}+3x_{32}+5x_{33}+3x_{34}

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 = 5x_{11}+6x_{12}+9x_{13}+7x_{14}+7x_{21}+8x_{22}+2x_{23}+4x_{24}+6x_{31}+3x_{32}+5x_{33}+3x_{34}

Constraints:

In transportation problems, there are supply constraints for each source, and demand

constraints for each destination.

Supply constraints:

For Chennai, x_{11}+ x_{12}+ x_{13}+ x_{14}< 6000

For Coimbatore, x_{21}+ x_{22}+ x_{23}+ x_{24}< 5000

For Madurai, x_{31}+ x_{32}+ x_{33}+ x_{34}< 4000

Demand constraints:

For B’lore, x_{11}+ x_{21}+ x_{31} = 5000

For Hyderabad, x_{12} + x_{22} + x_{32} = 4000

For Cochin, x_{13} + x_{23} + x_{33} = 2000

For Goa, x_{14} + x_{24} + x_{34} = 4000

The linear programming model for GM Textiles will be write in the next line. Minimize

Z = 5x_{11} + 6x_{12} + 9x_{13} + 7x_{14} + 7x_{21} + 8x_{22} + 2x_{23} + 4x_{24} + 6x_{31} + 3x_{32} + 5x_{33} + 3x_{34}

Subject to constraints,

x_{11}+x_{12}+x_{13}+x_{14}< 6000 .........................(i)

X _{21}+x_{22}+x_{23}+x_{24}< 5000 .........................(ii)

x_{31}+x_{32}+x_{33}+x_{34}< 4000 .........................(iii)

x_{11}+x_{21}+x_{31} = 5000 ..........................(iv)

x_{12}+x_{22}+x_{32} = 4000 ..........................(v)

x_{13}+x_{23}+x_{33} = 2000 ..........................(vi)

x_{14}+x_{24}+x_{34} = 4000 .........................(vii)

Where, x_{ij}> 0 for i = 1, 2, 3 and j = 1, 2, 3, 4.

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 x

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

The linear programming model is

Minimize Z = 15x_{11}+20x_{12}+30x_{13}+10x_{21}+9x_{22}+15x_{23}+14x_{31}+12x_{32}+18x_{33}

Subject to constraints,

x_{11}+x_{12}+x_{13}< 350 ...................(i)

x_{21}+x_{22}+x_{23}< 200 ...................(ii)

x_{31}+x_{32}+x_{33}< 400 ...................(iii)

x_{11}+x_{12}+x_{31} = 250 ...................(iv)

x_{12}+x_{22}+x_{32} = 400 ...................(v)

x_{13}+x_{23}+x_{33} = 300 ...................(vi)

x_{ij}> 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.

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

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

** 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*

*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:

- Northwest Corner Method (NWC)
- Least Cost Method (LCM)
- 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) *

- 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).
- Delete that row or column which has no values (fully exhausted) for supply or demand.
- Now, with the new reduced table, again select the North-west corner cell and allocate the available values.
- Repeat steps (ii) and (iii) until all the supply and demand values are zero.
- Obtain the initial basic feasible solution.

*Algorithm for Least Cost Method (LCM)*

- Select the smallest transportation cost cell available in the entire table and allocate the supply and demand.
- Delete that row/column which has exhausted. The deleted row/column must not be considered for further allocation.
- 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)
- Obtain the initial basic feasible solution.

*Algorithm for Vogel’s Approximation Method (VAM)*

- 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.
- 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.
- Delete the row/column, which has satisfied the supply and demand.
- Repeat steps (i) and (ii) until the entire supply and demands are satisfied.
- Obtain the initial basic feasible solution.

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

- The solution must be feasible, i.e., the supply and demand constraints must be satisfied (also known as rim conditions).
- 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.

*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 requ_{i}res allocations in ** m + n – 1 **independent cells. If the number of allocations is short of the requ

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 u_{1}, u_{2}, …,u_{i} and the column 1, column 2,…, column j are assigned with variables v_{1}, v_{2}, …,v_{j} respectively.

(ii) Initially, assume any one of U Transportation Model i values as zero and compute the values for u_{1}, u_{2}, …,u_{i} and v_{1}, v_{2}, …,v_{j} by applying the formula for occupied cell.

**For occupied cells,**

c_{ij} + u_{i} + v_{j} = 0

(iii) Obtain all the values of c_{ij} 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 v

c_{ij}+u_{i}+v_{j} = 0

Then, the opportunity cost for each unoccupied cell is calculated using the formula C ij = c_{ij} + u_{i} + v_{j} 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 u_{i} and v_{j}, using the formula for occupied cells. Assume any one

of u_{i} and v_{j} value as zero (U3 is taken as 0)

c_{ij} + u_{i} + v_{j} = 0

4 + 0 + v_{2} = 0, v_{2} = – 4

5 + v_{2}– 3 = 0, u_{2} = – 2

3 – 2 + v_{1} = 0, v_{1} = – 1

2 – 4 + u_{1} = 0, u_{1} = 2

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

C ij = c_{ij} + u_{i} + v_{j}

c_{11} = 4+2 –1 = 5

c_{13} = 7+2 –3 = 6

c_{14} = 3+2 –1 = 4

C_{22} = 7–2 – 4 = 1

C_{24} = 8–2 – 1 = 5

C_{31} = 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**

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*

- Formulate the problem to maximize profits.
- Determine the solution using TORA.
- 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

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 /-

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 (x_{ij}) 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

x_{ij} be the number of units shipped from node i to node j,

x_{13} be the number of units shipped from Coimbatore to Chennai,

x_{24} 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 = 4x_{13}+ 7x_{14}+ 6x_{23}+ 3x_{24}+ 7x_{35}+ 4x_{36}+ 3x_{37}+ 5x_{38}+ 5x_{45}+6x_{46}+ 7x_{47}+ 8x_{48}

**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:

x_{13}+ x_{14}< 800 …………………….. (i)

Similarly, for Pune facility

x_{23}+ x_{24}< 600 ……………………...(ii)

Now, considering the node 3,

Number of units shipped out from node 1 and 2 are,

x_{13}+ x_{23}

Number of units shipped out from node 3 is,

x_{35} + x_{36} + x_{37} + x_{38}

The number of units shipped in must be equal to number of units shipped out, therefore

x_{13} + x_{23} = x_{35} + x_{36} + x_{37} + x_{38}

Bringing all the variables to one side, we get

– x_{13}– x_{23} + x_{35} + x_{36} + x_{37} + x_{38} = 0 ………….(iii)

Similarly for node 4

– x_{14}– x_{24} + x_{45}+x_{46} + x_{47} + x_{48} =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

x_{35} + x_{45} = 350 ................(v)

Similarly for nodes 6, 7, and 8, we get,

x_{36} + x_{46} = 200 ……...........(vi)

x_{37} + x_{47} = 400 ……...........(vii)

x_{38} + x_{48} = 450 ……...........(viii)

Linear Programming formulation,

Minimize Z = 4x_{13}+7x_{14}+6X22+3x_{24}+7x_{35}+4x_{36}+3x_{37}+5x_{38}+5x_{45}+6x_{46}+7x_{47}+8x_{48}

Subject to constraints