Operations Research :- Unit III The Transportation Problem and Assignment Problem

Unit III The Transportation Problem and Assignment Problem

Syllabus:

Finding an initial feasible solution - North West corner method, Least cost method, Vogel’s Approximation method, Finding the optimal solution, optimal solution by stepping stone and MODI methods, Special cases in Transportation problems - Unbalanced Transportation problem. Assignment Problem: Hungarian method of Assignment problem, Maximization in Assignment problem, unbalanced problem, problems with restrictions, travelling salesman problems.

3.1 Finding an initial feasible solution - North West corner method, Least cost method, Vogel’s Approximation method

In general, any basic feasible solution of a transportation problem with m origins (such as factories) and n destinations (such as warehouses) should have ‘m + n - l’ non zero basic

variables.

A transport problem is said to be a degenerate transport problem if it has a basic feasible solution with number of nonzero basic variables less than m + n - 1.

According to Must fit, “A degenerate basic feasible solution in a transportation problem exists if and only if some partial sum of availabilities (row) is equal to a partial sum of requirements (column)”.

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

Method I : Least Cost Method (or LCM)

Method II : Northwest Comer Method (or NWCM)

Method III : Vogel’s Approximation Method (or VAM)

Let us discuss these methods one by one as under:

Method I: Least Cost Method (or LCM)

The practical steps involved in the Least Cost Method are given below:

Step 1: Make maximum possible Allocation to the Least. Cost Cell depending upon the demand/supply for the Column Row containing that Cell. In case of Tie in the Least Cost Cells, make allocation to the Cell by which maximum demand or capacity is exhausted.

Step 2: Make allocation to the Second Lowest Cost Cell depending upon the remaining demand/supply for the Row/Column containing that Cell.

Step 3: Repeat the above Steps till all Rim Requirements are exhausted, Le., entire demand and supply is exhausted.

Example

Find the initial basic feasible solution by Least Cost Method.

Solution

Initial Feasible Solution by Least Cost Method (LCM)

Method II: North-west Corner Method (or NWCM)

The practical steps involved in the North-West Comer Method are given below:

Step 1:Make maximum possible allocation to the Upper-Left Comer Cell (also known as North-West Comer Cell) in the First Row depending upon the availability of supply for that Row and demand requirement for the Column containing that Cell.

Note: Unit transportation cost is completely ignored.

Step 2:Move to the Next Cell of the First Row depending upon remaining supply for that Row and the demand requirement for the next Column. Go on till the Row total is exhausted.

Step 3:Move to the next Row and make allocation to the Cell below the Cell of the preceding Row in which the last allocation was made and follow Steps I and 2.

Step 4:Follow Steps I to 3 till all Rim requirements are exhausted, i.e., the entire demand and supply is exhausted.

Example

Find initial feasible solution by North West Comer Method in Problem.

Solution

Method III: Vogel’s Approximation Method (or VAM)

The practical steps involved in Vogel’s Approximation Method (or VAM) are given below:

Step 1: Row Difference: Find the difference between Smallest and Second Smallest element of each Row, representing the. Opportunity Cost of not making the allocation to the Smallest

Element Cell, and write the difference on the right-hand side of the concerned Row. In case of tie between two smallest elements, the difference should be taken as zero.

Step 2: Column Difference: Find the difference between Smallest and Second Smallest element of each column, representing the Opportunity Cost of not making the allocation to the Smallest Element Cell, and write the difference below the concerned Column. In case of tie between two smallest elements, the difference should be taken as zero.

Step 3: Make the Largest Difference amongst all Differences by an arrow indicating the allocation to be made to the row/ column having largest difference. Allocate maximum possible quantity to the Least Cost Cell of the Selected row/column depending upon the quantity available. In case of tie between the Differences, select the row or column having least cost cell.

However, in case of tie even in case of Least Cost, make allocation to that Cell by which maximum requirements are exhausted.

Step 4: Shade the Row/Column whose availability or requirement is exhausted so that it shall not be considered for any further allocation.

Step 5: Repeat Step 3 and 4 till entire demand and supply is exhausted.

Step 6: Draw the Initial Feasible Solution Table obtained after the above steps.

Example

Find the initial feasible solution by Vogel’s Approximation Method.

Note: Cell entries are the unit transportation costs

Solution

Introducing a Dummy warehouse with zero cost per unit as the total demand is not equal to total supply in order to make the problem balanced one.

Initial Feasible Solution by Vogel’s Approximation Method

(VAM)

3.2 Finding the optimal solution, optimal solution by stepping stone and MODI methods

The Modified Distribution Method, also known as MODI method or u-v method, which provides a minimum cost solution (optimal solution) to the transportation problem. The following are the steps involved in this method.

3.3 Special cases in Transportation problems - Unbalanced Transportation problem

The transportation problem is a special type of linear programming problem where the ‘objective is to minimise the cost of distributing a product from a number of sources or origins to a number of destinations. Because of its special structure the usual simplex method is not suitable for solving transportation problems. These problems require a special method of

solution. The origin of a transportation problem is the location from which shipments are dispatched. The destination of a transportation problem is the location to which shipments are

transported. The unit transportation cost is the cost of transporting one unit of the consignment from an origin to a destination.

In the most general form, a transportation problem has a number of origins and a number of destinations. A certain amount of a particular consignment is available in each origin.

Likewise, each destination has a certain requirement. The transportation problem indicates the amount of consignment to be transported from various origins to different destinations so that the total transportation cost is minimised without violating the availability constraints and the requirement constraints. The decision variables Xij of a transportation problem indicate the amount to be transported from the i^th origin to the j^th destination. Two subscripts are necessary to describe these decision variables. A transportation problem can be formulated as a linear programming problem using decision variables with two subscripts.

Example: A manager has four Factories (i.e. origins) and four Warehouses (i.e. destinations). The quantities of goods available in each factory, the requirements of goods in each warehouse and the costs of transportation of a product from each factory to each warehouse are given. His objective is to ascertain the quantity to be transported from various factories to

different warehouses in such a way that the total transportation cost is minimised.

·        Balanced Transportation Problem

Balanced Transportation Problem is a transportation problem where the total availability at the origins is equal to the total requirements at the destinations. For example, in case the total

production of 4 factories is 1000 units and total requirements of 4 warehouses is also 1000 units, the transportation problem is said to be a balanced one.

·        Unbalanced Transportation Problem

Unbalanced transportation problem is a transportation problem where the total availability at the origins is not equal to the total requirements at the destinations. For example, in case the total production of 4 factories is 1000 units and total requirements of 4 warehouses is 900 units or 1,100 units, the transportation problem is said to be an unbalanced one. To make an unbalanced transportation problem, a balanced one, a dummy origins) or a dummy destination (s) (as the case may be) is introduced with zero transportation cost per unit.

·        Dummy Origin/Destination

A dummy origin or destination is an imaginary origin or destination with zero cost introduced to make an unbalanced transportation problem balanced. If the total supply is more than the total demand we introduce an additional column which will indicate the surplus supply with transportation cost zero. Likewise, if the total demand is more than the total supply, an additional row is introduced in the Table, which represents unsatisfied demand with transportation cost zero.

3.4 Assignment Problem: Hungarian method of Assignment problem, Maximization in Assignment problem, unbalanced problem, problems with restrictions, travelling salesman problems.

What Is Assignment Problem?

Assignment Problem is a special type of linear programming problem where the objective is to minimize the cost or time of completing a number of jobs by a number of persons.

The assignment problem in the general form can be stated as follows:

“Given n facilities, n jobs and the effectiveness of each facility for each job, the problem is to assign each facility to one and only one job in such a way that the measure of effectiveness is

optimised (Maximised or Minimised).”Several problems of management have a structure identical with the assignment problem.

Example I: A manager has four persons (i.e. facilities) available for four separate jobs (i.e. jobs) and the cost of assigning (i.e. effectiveness) each job to each person is given. His objective is to assign each person to one and only one job in such a way that the total cost of assignment is minimised.

Example II: A manager has four operators for four separate jobs and the time of completion of each job by each operator is given. His objective is to assign each operator to one and only

one job in such a way that the total time of completion is minimised.

Example III: A tourist car operator has four cars in each of the four cities and four customers in four different cities. The distance between different cities is given. His objective is to assign each car to one and only one customer in such a way that the total distance covered is minimized.

3.4.1 Hungarian method of Assignment problem

Although an assignment problem can be formulated as a linear programming problem, it is solved by a special method known as Hungarian Method because of its special structure. If the

time of completion or the costs corresponding to every assignment is written down in a matrix form, it is referred to as a Cost matrix. The Hungarian Method is based on the principle that if a constant is added to every element of a row and/or a column of cost matrix, the optimum solution of the resulting assignment problem is the same as the original problem and vice versa. The original cost matrix can be reduced to another cost matrix by adding constants to the elements of rows and columns where the total cost or the total completion time of an assignment is zero. Since the optimum solution remains unchanged after this reduction, this assignment is also the optimum solution of the original problem. If the objective is to maximize the effectiveness through Assignment, Hungarian Method can be applied to a revised cost matrix obtained from the original matrix.

Simplex Explanation of the Hungarian Method

3.4.2 Maximization in Assignment problem

Sometimes, the assignment problem deals with the maximization of an objective function rather than to, minimize it. For example, it may be required to assign persons to jobs in such a way that the expected profit is maximum. Such problem may be solved easily by first converting it to a minimization problem and then applying the usual procedure of assignment algorithm. This conversion can be very easily done by subtracting from the highest element, all the elements of the given profit matrix; or equivalently, by placing minus sign before each element of the profit-matrix in order to make it cost-matrix.

Following examples will make the procedure clear.

Example 1. (Maximization Problem). A company has 5jobs to be done. The following matrix shows the return in rupees on assigning I ^th (i = 1,2,3,4,5) machine to the j^th job (j =A, B, C, D, E). Assign the five jobs to the five machines so as to maximize the total expected profit

Solution. Step 1. Converting from Maximization to Minimization:

Since the highest element is ]4, so subtracting all the elements from ]4, the following reduced cost (opportunity loss of maximum profit) matrix is obtained.

Step 2. Now following the usual procedure of solving an assignment problem, an optimal assignment is obtained in the following table:

Example 2. (Maximization Problem). A company has four territories open, and four salesmen available for assignment. The territories are not equally rich in their sales potential.. It is estimated that a typical salesman operating in each territory would bring in the following annual sales:

Four salesmen are also considered to differ in their ability: it is estimated that, working under the same conditions, their yearly sales would be proportionately as follows:

If the criterion is maximum expected total sales, then intuitive answer is to assign the best

salesman to the richest territory, the next best salesman to the second richest, and so on. Verify this answer by the assignment technique.

Solution. Step 1. To construct the effectiveness matrix:

In order to avoid the fractional values of annual sales of each salesman in each territory, it will be rather convenient to consider the sales for 21 years (the sum of proportions: 7 + 5 + 5 + 4 =21), taking Rs. 10,000 as one unit. Divide the individual sales in each territory by 21, if the annual sales by salesman are required.

Thus, the sales matrix for maximization is obtained as follows:

Step 2. (To convert ‘the maximum sales matrix’ to ‘minimum sales matrix’.)

The problem of ‘maximization’ can be converted to ‘minimization’ one, by simply multiplying each element of given matrix (Table) by -I. Thus resulting matrix becomes:

Step 3. Subtracting the smallest element in each row from every element in that row, we get the reduced matrix

Step 4. Subtract the smallest element in each column from every element in that column to get the second reduced matrix

Step5. Since all zeros in Table can be covered by minimum number of lines.(L1 ,L2) , which is less than 4 (the number of rows in the matrix), the optimal assignment is not possible at this stage. In Table select the minimum element’ l’ among all uncovered elements. Then subtract this value 1 from each uncovered element, and add 1 at the intersection of two lines L1,L2 . Thus, the revised matrix is obtained as Table

Step 6. Again repeat Step 5. Since the minimum number of lines (L1, L2) in Table to cover all

zeros is less than 4 (the number of rows/columns), subtract the min. element 1 from all uncovered elements and add 1 at the intersection of lines (L1 ,L2) and (L1 ,L2). Then find the optimal assignment as explained in Step 7.

Step 7. To find an optimal assignment. Since there is a single zero element in row 1and column 4 only, make the zero assignment by putting ‘0 ‘ around these two zeros and cross-out other zeros in column 1 and row 4. Other zero-assignments are quite obvious from the following tables:

Thus, two possible solutions are: (i) A-I, B-II, C-III, D-IV; (ii) A-I, B-III, C-II, D-IV.

Both the solutions show that the best salesman A is assigned to the richest territory I, the worst salesman D to the poorest territory IV. Salesman B and C being equally good, so they may be assigned to either II or III. This verifies the answer.

Practical Steps Problems Involved Solving In Maximisation

Step 1: See whether Number of Rows is equal to Number of Columns. If yes, problem

is a balanced one; if not, then adds a Dummy Row or Column to make the problem a

balanced one by allotting zero value or specific value (if any given) to each cell of the

Dummy Row or Column, as the case may be.

Step 2: Derive Profit Matrix by deducting cost from revenue.

Step 3: Derive Loss Matrix by deducting all elements from the largest element.

Step 4: Follow the same Steps 2 to 9 as involved in solving Minimisation Problems.

3.4.3 Unbalanced Assignment Problem

Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one,

a dummy facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time.

Dummy Job/Facility

A dummy job or facility is an imaginary job/facility with zero cost or time introduced to make an unbalanced assignment problem balanced.

3.4.4 Problems with restrictions

3.4.5 Travelling salesman problems.