Transportation and Assignment Chapters Theory #pdf

323 times

150 KB

**File Content -**

C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 1 of 8
CHAPTER 12 : TRANSPORTATION
Transportation Problems are a special category LPPs’ where the objective is
to minimise total transportation cost (subject to some constraints, if any)
and where there are M delivery points located at different places requi ring
the materials to be catered by N production facilities which are also lo cated
at different places and costs of transportation from each production facility
to respective places requiring the material varies.
Question State the methods in which initial feasible solution can be arrived
at in a transportation problem
Answer
The methods by which initial feasible solution can be arrived at in a
transportation model are as under:
1. North West Corner Method.
2. Least Cost Method
3. Vogel’s Approximation Method (VAM)
North West Corner Method: The steps involved are:
1. First it should be ensured that the requirements and availability are
same. If not, they are to be made same by adding dummy row or
column.
2. First allocation is made in to the cell in the upper left han d corner and
the full requirement or availability of that cell is allotted.
3. Then we move to the next cell either sidewards or downwards
depending on the initial allocation and allot that cell’s requ irement or
availability in full.
4. The above step is repeated till all the quantities of requir ements and
availability are exhausted. By this time we will be coming to the last
row / column for final allotment.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 2 of 8
5.
This method does not use transportation costs as basis for making
allotments.
Least Cost Method: Steps involved in this method ar e:
1. First it should be ensured that the requirements and availability are
same. If not, they are to be made same by adding dummy row or
column.
2. Least cost cell in the matrix is identified and maximum allocation is
done to it so that the requirement or availability of that cell is
completed.
3. Then the next least cost cell is identified and maximum allocation i s
done to this cell also so that the requirement or availability of that cell
is completed.
4. This process is repeated till all the quantities and requirements are
exhausted. In case there is a tie between one or more cells, the cell to
be allotted is identified on arbitrary basis.
Vogel’s Approximation Method: This is a superior method than the North
West Corner method as this uses transportation costs as basis for initial
allocation and this will be nearer to optimal solution.
Steps involved in this method for initial allocation are:
1. First it should be ensured that the requirements and availability are
same. If not, they are to be made same by adding dummy row or
column.
2. Difference between the least cost cell and second least cost cell of
each row and column are to be identified.
3. Of the differences arrived at 2 above, the maximum difference amount
is to be identified whether it is in column or row. If the maximum
difference is in column, then in that column, the least cost cell is to b e
identified and maximum allocation is made to that cell so that t he
requirement or availability of that cell is completely met. Similarly, if
the maximum difference is in row, then the least cost cell in that row is
identified and maximum allocation is made to that cell so that t he
requirement or availability of that cell is completely met.
In case there is a tie in the differences in amounts of one row o r
column with another row or column, then the row or column having
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 3 of 8
the least cost cell is considered. In case there is tie here also, then
the cell which utilises maximum value of resources or requirements is
considered. In case there is a tie at this stage also, allocation
to one
of the cells is made on arbitrary basis.
4. Having made the first allocation, that row or column whose resources
or requirements are exhausted is not to be considered till all allocati on
is complete.
5. Steps 2 and 3 are to be repeated till allocation of all requi rements and
availability is completed and at each allocation, the row or column
whose requirement or availability is completed should not be
considered till balance allocation is completed.
The difference between the least cost cell and the second least cost cel l in a
row or column indicates the penalty that we will incur for not making
allocation to such cell. Hence we will be decreasing the penalty by making
maximum possible allocations to the cell which has the highest pe nalty
successively till all the requirements and availabilities are completed.
With the above steps, the allocation will be complete. But we d o not know
whether it is optimal or not. Hence, this needs to be tested for optimal ity.
Following steps are involved.
1. First we need to check the number of cells that have been allotted
quantities. If this number is equal to m+n-1 (where m is the nu mber
of rows and n is number of columns), then we can go to the next step.
If not, then we need to allot e (epsilon, an infinitely small quantity) to
the least cost independent unallotted cell or cells till this
requirement is met. Independent cell is the one with which we cannot
form a loop with this cell and other allotted cells.
2. A zero is put against a cell or row which has maximum allocations
(infact, this zero can be put against any row or column but by putt ing
here, it will be easy and comfortable for further calculations.)
3. Let us refer each cell costs as C ijs’. Suppose a zero, referred as U i is
put against a row. Now we need to work out U is’ and Vjs’ for rest of
the columns and rows based on the allotted cells. V js’ are worked out
in such a way that for any cell, C ij = Ui + V j. For the columns, where
there are allotments in this particular row, C i = V j since U i is zero. This
process has to be repeated till all the values of U is’ (for rows) and V js’
(for columns) are obtained on the basis of allotted cells.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 4 of 8
4.
In case of unallotted cells, the sum of respective U is’ and V js’ are
entered in respective cells in a corner.
5. Now Δ ijs’ are calculated for unallotted cells by the formula Δ ij = Cij – ( U i
+ V j). If all the values of Δij are either 0 or +ve, then the solution is
optimal.
6. In case if we get some of the Δ ijs’ as – ve then the solution is not
optimal and we need to do further calculations to make it optimal . For
this we need to transfer as much quantity as possible to the most
negative cell from the allotted quantities of that cells row or column.
Quantity to be transferred to the vacant cell is arrived by forming a
closed loop (which is the one and only one loop that can be formed)
with this unallotted cell and three other allotted cells. The lo op may
run through some or all allotted cells also. Maximum quantity that can
be transferred is the minimum figure of the diagonal figures of th e
loop. Hence this figure is to be subtracted from the diagonal figure s
where they exist and added to the unallotted cell and the cell
diagonally opposite to the unallotted cell.
7. Having done this, again we need to check for optimality by repe ating
the steps 1 to 6 till we end at step 5.
Question
How do you know whether an alternative solution exists for a transportation
problem?
Answer
The Δ ij matrix = Δ ij = C ij – (u i + v j)
Where c i is the cost matrix and (u i + v j) is the cell evaluation matrix for
allocated cell.
If the Δij matrix has one or more ‘Zero’ elements, indicating that, if that cell
is brought into the solution, the optimal cost will not chang e though the
allocation changes.
Thus, a ‘Zero’ element in the Δ ij matrix reveals the possibility of an
alternative solution.
Question
Explain the term degeneracy in a transportation problem.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 5 of 8
Answer
If a basic feasible solution of
a transportation problem with m origins and n
destinations has fewer than m + n – 1 positive xij (occupied cells) the
problem is said to be a degenerate transportation problem. Such a situa tion
may be handled by introducing an infinitesimally small allo cation e in the
least cost and independent cell.
While in the simple computation degeneracy does not cause any serious
difficulty, it can cause computational problem in transportation problem . If
we apply modified distribution method, then the dual variable ui and vj are
obtained from the Cij value to locate one or more Cij value which sho uld be
equated to corresponding Cij + Vij.
Question
Will the initial solution for a minimization problem obtained by Vogel’s
approximation Method and the Least Cost Method be the same? Why?
Answer
The initial solution need not be the same under both methods.
Vogel’s Approximation Method uses the differences between the min imum
and the next minimum costs for each row and column.
This is the penalty or opportunity cost of not utilising the next best
alternative. The highest penalty is given the 1 st preference. This need not be
the lowest cost.
For example if a row has minimum cost as 3, and the next minimum as 2,
penalty is 1; whereas if another row has minimum 4 and next minimum 6,
penalty is 2, and this row is given preference.
But least cost gives preference to the lowest cost cell, irrespective of the
next cost.
Vogel’s Approximation Method will result in a more optimal solution than
least cost.
They will be the same only when the maximum penalty and the mini mum
cost coincide.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 6 of 8
Special Points on Transportation Problems:
1. Transportation algorithm is essentially a minimisation algorithm. But
this can be used for maximisation issues also. This is done by
subtracting all the elements from the biggest element in the matrix
and solving the resulting matrix by applying the algorithm.
2. Cells with allocations and through which a loop can be formed with
other allotted cells are called dependent cells. Cells without alloca tions
and through which loop cannot be formed with other allocated cells are
called independent cells.
3. If some routes are to be prohibited, then this is done by all otting very
high cost M to such route thus driving it out of the solution.
4. The criteria of m+n-1 allocations is to be tested for every iteration of
the algorithm. This may arise during intermediate stage also. In case
allocations are lesser, then this is resolved by allotting e (epsilon,
infinitely small quantity) to the least cost independent cell.
5. A transhipment problem can be formulated as transportation problem
by addition of another origin and destination.
CHAPTER 13: ASSIGNMENT
These are also another category of LPPs’ and are similar to transportation
problems. It occurs when n jobs are to be assigned to n faciliti es on a one-
to -one basis with a view to optimising the resource required. The steps
involved in solving these types of problems are as below:
1. First it needs to be checked whether the problem is balanced or not. If
it is not balanced, then it is to be made a balanced problem by add ing
dummy row(s) / column(s) similar to transportation problems.
2. Subtract the minimum element of each row from all the elements in
that row. From the resulting matrix, the minimum element of each
column is to be subtracted from all the elements of that column. The
resulting matrix is the one which needs to be tested for optimality.
3. Optimality test is done by drawing minimum horizontal and vertical
lines (not diagonal lines) over the rows and columns of the matrix in
such a way that all zeros are covered. If the number of lines required
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 7 of 8
to cover zeros is equal to the order of the matrix then it is opti
mal
solution. If the lines required to cover zeros is not equal to t he order
of the matrix, then we need to do the following to increase the zeros in
the matrix.
4. From the elements that are not covered by any lines in the matrix, t he
least element is selected. This value is deducted from all elements
uncovered by lines in the matrix. Further, the least element selected
should be added to all the elements at intersecting points in the
matrix. Care should be taken to ensure that Elements covered by
lines in the matrix are retained as they are and are not changed.
5. Now optimality test as indicated in point 3 is to be carried on . If the
findings go through the test, then it is ready for allocation. If not,
point 4 is to be repeated and then point 3 till optimality is reached.
6. Once optimality is reached, allocations are made by encircling the
zeros in rows / columns. First the rows and columns containing single
zeros are encircled. Rest of the allocations are made in such a way
that each column and row has only one zero encircled meaning the tie
up between resources and requirements. For the sake of convenience,
once an allotment is made respective row and column are shaded so
that these will not be considered again for allocation.
Rationale of the Assignment Algorithm:
The relative cost of assigning facility i to job j is not changed by the
subtraction (or addition also) of a constant from either a column or a row of
the original cost matrix.
An optimal assignment exists if total reduced cost of the assignment is z ero.
This is the case when the minimum number of lines necessary to cover all
zeros is equal to the order of the matrix. If, however, it is less than n, a
further reduction of the cost matrix has to be undertaken.
Question
Just after row and column minimum operations, we find that a particular ro w
has 2 zeroes. Does this imply that the 2 corresponding numbers in t he
original matrix before any operation were equal? Why?
Answer
The prerequisite to assign any job is that each row and column must ha ve a
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 8 of 8
zero value in its corresponding cells. If any row or column does not hav
e any
zero value then to obtain zero value, each cell values in th e row or column is
subtracted by the corresponding minimum cell value of respective rows or
columns by performing row or column operation. This means if any row or
column have two or more cells having same minimum value then these row
or column will have more than one zero. However, having two zeros doe s
not necessarily imply two equal values in the original assignment matrix jus t
before row and column operations. Two zeroes in a same row can also be
possible by two different operations i.e. one zero from row operation and
one zero from column operation.
Question
Under the usual notation, where a 32 means the element at the intersection of
the 3rd row and 2nd column, we have, in a 4 × 4 assignment problem, a 24
and a 32 figuring in the optimal solution. What can you conclude about the
remaining assignments? Why?
Answer
The order of matrix in the assignment problem is 4 × 4. The total
assignment (allocations) will be four. In the assignment problem when any
allocation is made in any cell then the corresponding row and column
become unavailable for further allocation. Hence, these corresponding row
and column are crossed mark to show unavailability. In the given
assignment matrix two allocations have been made in a 24
(2 nd
row and 4 th
column) and a 32
(3 rd
row and 2 nd
column). This implies that 2 nd
and 3 rd
row
and 4 th
and 2 nd
column are unavailable for further allocation.
Therefore, the other allocations are at either at a 11 and a
43 or at a
13 and a
41.
Special Points on Assignment Problems:
1. Assignment algorithm is essentially a minimisation algorithm. But this
can be used for maximisation issues also. This is done by subtracting
all the elements from the biggest element in the matrix and solving
the resulting matrix by applying the algorithm.
2. If some persons are not to be allotted jobs, then this is done by
allotting very high cost M to such person thus driving it out of the
solution.
2
3

GST Practitioner Certificate Course Evening 33rd Batch

CA Arun Chhajer

Become GST Expert like a PRO

CA Abhishek Raja Ram

- Handbook on Annual Return under GST
- Compliance Sheet for the month of December 2022
- Revised disclosures checklist for Ind AS
- Knowledge Capsule - Nov 2022 Edition
- Tax Connect (With GST) - 378th Issue
- Compliance Calendar for the m/o November, 2022
- ICMAI - 124th Volume of Tax Bulletin
- The Construction and Application and Use of Life Tables
- ICAI submits Pre-Budget Memoranda-2023
- Why NCD/Bonds Investment Ideal and most preferred by Investors?