

Operations
Research (MTH601)
195
a)
Develop an optimum transportation
schedule and give the
minimum transportation
cost.
b) Is it
possible to have more than
one optimum schedule? If so,
give at least one more
optimum
schedule.
13.
Peru
enterprise has three
factories at location A, B and C, which
supplies three warehouses,
located at
D,
E and F. Monthly factory capacities
are 10, 18 and 15 units
respectively. Monthly
warehouse
requirements
are 75, 20 and 50 units
respectively.
Warehouse
Factory
D
E
F
A
5
1
7
B
6
4
6
C
3
2
5
The
penalty costs for not
satisfying demand at the warehouses
D,
E and
F
are
Rs. 5, Rs. 3, and Rs.
2
per
unit respectively. Determine
the optimal distribution for
Peru using any of the
known algorithms.
14.
A
fleet operator has in his
three depots P, Q and R 1
bus and 8 buses and 7
buses respectively. He
has
to
allocate them to those bus
stands X, Y and Z, which
require 2, 5 and 9 buses
respectively. The
following
table gives the distances in
kilometers from each depot to
each bus stand. Find
the optimum
allocation.
X
Y
Z
P
6
4
12
Q
10
6
5
R
15
16
8
15.
A
firm has 4 factories, which
produce 8, 7, 9 and 4 units
respectively of a product. The
firm owns three
stores,
which sells 8 units
respectively. The unit
transportation cost is given
below in the table.
Store
Factory
A
B
C
P
10
9
8
Q
10
7
10
R
11
9
7
S
12
14
10
Find
the transportation schedule,
which minimizes the distribution
cost.
DEGENERACY
In
the examples discussed so
far, the solution procedure
yielded exactly (m + n  1) strictly
positive
allocations,
in independent positions indicating
nondegenerate basic feasible
solution. When either of
the
conditions
for conducting optimality is
absent it results in a degenerate
solutions. The circumstances in
many
cases
may not yield result,
which satisfy conditions for
optimality tests. We may
have less number of
cells
alloted
even in the initial basic
feasible solution, found,
either by North West Corner
rule or other methods
described
previously. It may be sometimes nondegenerate in
the initial basic feasible
solution but at any
intermediate
iteration (while we conduct
the optimality test) it may
lead to a case of a degenerate
feasible
solution.
This particularly occurs when a row
and a column simultaneously vanish,
while making allocations
initially
by any of the methods. Th
situation of degeneracy can be
resolved as explained in the
next paragraph.
195
Operations
Research (MTH601)
196
A
feasible solution with independence,
but with fewer than the
required number of
individual
allocations
is changed to become permissible in
the following way. We have
to choose the required
number of
cells,
such that this number plus
the existing allocation come to exactly
(m
+ n  1)
cells should be in
independent
positions. Then, an infinitesimal
but positive allocation, say an
amount equal to is allotted to
each
of
the chosen unoccupied cells.
This fictitious allotment does not
change the physical nature
of the original set
of
allocations, but will be helpful to
carry out the iterations.
This small fictitious quantity plays an
auxiliary role
and
it is removed when the
optimum is reached.
Sometimes
a feasible solution may degenerate to
m
+ n  3 or
even fewer independent allocations.
In
such
cases, if the transportation
method is to be adopted in finding a
solution to the problem, we will
have to
introduce
two or more infinitesimal
variables (∈).
The ∈'s
are also placed in various
independent positions
and
can
be distinguished from each
other by subscripts.
Example:
Solve the following
transportation problem to minimize
the total cost of
transportation.
Destination
Origin
1
2
3
4
Supply
1
14
56
48
27
70
2
82
35
21
81
47
3
99
31
71
63
93
Demand
70
35
45
60
210
Solution:
First
obtain an indicial basic
feasible solution with Vogel's
Approximation Method from the
table 62
Table
62
Destination
Origin
1
2
3
4
Supply
Penalty
70
14
1
56
48
27
70
(13)
2
82
35
21
81
47
(14)
3
99
31
71
63
93
(32)
Demand
70
35
45
60
210
Penalty
(68)
(4)
(36)
(36)
Supply
70 to 1 from 1. Hence row 1
and column 1 are both eliminated.
The reduced matrix is shown
in table 63
Table
63
Destination
Origin
2
3
4
Supply
Penalty
45
21
2
35
81
47
(14)
3
31
71
63
93
(32)
Demand
35
45
60
140
Penalty
(4)
(50)
(18)
Supply
45 to 3 from 2 and hence column 3 is
eliminated, resulting in table 64
196
Operations
Research (MTH601)
197
Table
64
Destination
Origin
2
4
Supply
2
2
35
81
2
(46)
3
63
93
(32)
Demand
35
60
95
Penalty
(4)
(18)
Supply
35 items from origin 2 to
destination 2 and row 2 is
deleted.
Table
65
Destination
Origin
2
4
Supply
33
60
31
63
3
93
Demand
33
60
93
Summarising
the above results we have
the initial feasible allocation as
exhibited in table 66
Table
66
Destination
Origin
1
2
3
4
Supply
1
70
70
2
2
45
47
3
33
60
93
Demand
Cost:
70 x 14 + 2 x 35 + 45 x 21 + 33 x 31 + 60 x 63 = Rs.
6798/
Table
67
Destination
Origin
1
2
3
4
1
14
56
48
27
2
82
35
21
81
3
99
31
31
63
Cost
matrix
To
conduct the optimality test
for the above solution there
must be 6 ( = 3 + 4  1) cells to
which
allocation
must have been made.
But we have made allotment to 5
cells only. Hence this is a
degenerate basic
feasible
solution.
To
resolve the case of
degeneracy, we introduce a very
small quantity ∈
in a
vacant and
independent
cell.
In the above problem we
allot ∈
to
cell (1, 4), which is
independent. The optimality
test can now be
conducted
as shown in the following
tables 68 to 72.
197
Operations
Research (MTH601)
198
Table
68
Destination
Origin
1
2
3
4
∈
1
70
2
2
45
3
33
60
Allotment
matrix
Table
69
Destination
Origin
ui
1
2
3
4
1
14


27
0
u1
2

35
21

40
u2
3
36

31
63
u3
vj
v1
v2
v3
v4
14
5
19
27
Cost
of alloted cells and
(ui + vj)
Table
70
Destination
Origin
1
2
3
4
1
56
48
2
82
81
3
99
71
Cost
of unalloted cells
198
Table of Contents:

