On a Paradox in Linear Plus Linear Fractional Transportation Problem
Textonly Preview
MATEMATIKA, 2010, Volume 26, Number 2, 167178
c
Department of Mathematics, UTM.
On a Paradox in Linear Plus Linear Fractional
Transportation Problem
1Vishwas Deep Joshi and 2Nilama Gupta
1,2Department of Mathematics, Malaviya National Institute of Technology,
J.L.N. Marg, Jaipur302017, CityplaceRajasthan, countryregionIndia
email: [email protected], 2n1 [email protected]
Abstract A paradoxical situation arises in a linear plus linear fractional transporta
tion problem (LPLFTP), when value of the objective function falls below the optimal
value and this lower value is attainable by transporting larger amount of quantity. In
this paper, a new heuristic is proposed for finding initial basic feasible solution for
LPLFTP and a sufficient condition for the existence of a paradoxical solution is es
tablished in LPLFTP. Two numerical examples are proposed for explanation of the
algorithms.
Keywords Transportation problem; linear plus linear fractional function; morefor
less paradox.
1
Introduction
The source of the socalled transportation paradox is unclear. Apparently, many researchers
have discovered independently from each other the following behavior of the transportation
problem: In certain cases of the transportation problem (TP), an increase in the supplies
and demands may lead to a decrease in the optimal transportation cost. In other words, by
moving bigger amount of goods around, one may save a lot of money. This surely sounds
paradoxical [1]. The moreforless (MFL) paradox in a TP occurs when it is possible to
ship more total goods for less (or equal) total cost, while shipping the same amount or
more from each origin and to each destination and keeping all the shipping costs non
negative. The occurrence of MFL in TP is not a rare event, and the existing literature has
demonstrated the practicality of identifying cases where the paradoxical situation exists [2].
The information of the occurrence of an MFL situation is useful to a manager in deciding
which warehouse or plant capacities are to be increased, and which markets should be
sought.
It could also be a useful tool in analyzing and planning company acquisition,
mergers, consolidations and downsizes. The so called MFL paradox in the transportation
paradox has been covered from a theoretical stand point by Charnes and Klingman [3],
and Charnes et al. [4]. Robb [5] provides an intuitive explanation of the transportation
occurrence. Adlakha and Kowalski [6], Adlakha et al. [7, 8] have given an algorithm for
solving paradoxical situation in linear transportation problem. They have already discussed
MFL paradox in linear transportation problem [6] as well as fixed charge [7] and mixed
constraints [8].
The LPLFTPs do exist especially when a compromise between absolute and relative
terms is to be maximized [9]. For example, the above problem arises when one wishes
to maximize the linear combination of income and profitability. Khurana and Arora [10]
presented an algorithm to solve LPLFTP. They considered two special cases of the problem,
where the transportation flow is either restricted or enhanced.
168
Vishwas Deep Joshi and Nilama Gupta
In section 2, the mathematical formulation of LPLFTP is discussed, in section 3, finding
a better initial basic feasible solution (IBFS) through fractional cost penalty method is pre
sented. Sections 4, 5 and 6 deals with the moreforless situation and a sufficient condition
for paradox in LPLFTP. Numerical examples are presented in sections 3 and 6 respectively
for the explanation of algorithms.
2
Mathematical Formulation of LPLFTP
Consider the following LPLFTP problem
m
n
m
n
s
i=1
j=1
ij xij
(P 1) Minimize Z =
r
ij xij +
m
n
tijxij
i=1 j=1
i=1
j=1
n
subject to
xij = ai,
i = 1, 2, ......, m
(1)
j=1
m
xij = bj,
j = 1, 2, ......, n
(2)
i=1
xij 0, i = 1, 2, ......, m; j = 1, 2, ......, n
(3)
m
n
ai =
bj = F 0
(4)
i=1
j=1
ai > 0, bj > 0, i = 1, 2, ......, m; j = 1, 2, ......, n
where
m
n
m
n
m
n
rijxij 0,
sijxij 0,
tijxij > 0 , tij > 0, sij 0 and rij 0,
i=1 j=1
i=1 j=1
i=1 j=1
rij= Per unit capital in transporting quantities from ith supply point to jth destination,
sij= Per unit depreciation in transporting quantities from ith supply point to jth destina
tion,
tij= Per unit profit earned in transporting quantities from ith supply point to jth destina
tion,
xij= Amount transported from the ith origin to the jth destination
ai= Amount available at the ith origin
bj= Demand of jth destination
Define the index sets I = {1, 2, ....., m} , J = {1, 2, ....., n} and K = I x J.
Let X = {xij/(i, j) K, xij satisfying the constraints (1)(3)} be a feasible solution of the
problem (P 1). Denote Ix = {(i, j) K/xij > 0, xij X}, the set of nondegenerate basic
cells. Due to constraint (4) each nondegenerate basic solution will contain (m + n  1)
positive components. Now we consider the dual variables u1, u2, u3 for i I and v1, v2, v3
i
i
i
j
j
j
for j J such that u1 + v1 = r
+ v2 = s
+ v3 = t
i
j
ij , u2
i
j
ij and u3
i
j
ij for (i, j) Ix.
On a Paradox in Linear Plus Linear Fractional Transportation Problem
169
Also for nonbasic variables, let
r
= r
+ v1)
ij
ij  (u1
i
j
s
= s
+ v2)
(5)
ij
ij  (u2
i
j
t
= t
+ v3) f or (i, j) K  I
ij
ij  (u3
i
j
x
The system (5) has (m + n  1) equations and can be solved independently. Let xlj is a
basic variable then arbitrarily set u1 = 0, u2 = 0, u3 = 0 and solve for other dual variables.
l
l
l
Having determined the dual variables u1, u2, u3for i I; v1, v2, v3 for j J, use these
i
i
i
j
j
j
values for determining r , s , t
for all nonbasic variables. Then from [10]
ij
ij
ij
m
n
m
n
V1 =
aiu1 +
b
=
r
i
j v1
j
ij xij ,
i=1
j=1
i=1 j=1
m
n
m
n
V2 =
aiu2 +
b
=
s
i
j v2
j
ij xij ,
i=1
j=1
i=1 j=1
m
n
m
n
V3 =
aiu3 +
b
=
t
i
j v3
j
ij xij ,
i=1
j=1
i=1 j=1
The necessary and sufficient condition for optimality in LPLFTP as given in [10] is given
below.
Theorem 1.1. A basic feasible solution X = (x )is a local optimum solution of problem
ij
(P1) if Rij = r (V
V
V
ij
3)2 + sij 3  tij 2 0 non basic variable xij .
The determination of dual variablesu1, u2, u3 for i I and v1, v2, v3 for j J would
i
i
i
j
j
j
facilitate the calculation of Rij for nonbasic variables. The solution can be improved if
Rij < 0 for at least one nonbasic variable xij.
Remark: If there exist one or more Rij < 0, then we choose Ri
= min {R
0 j0
ij /Rij < 0}
and introduce the nonbasic variable xi
into the basis thereby improving the value of Z.
0 j0
The variable which leaves the basis and the value of the new basic variable in the basis can
be determined using [10].
3
Heuristic for finding IBFS for LPLFTP
An IBFS to problem (P 1) can be obtained by using following method
Step 1. Calculate the value of rij + sij for each cell and prepare the new matrix of fractional
tij
values.
Step 2. For a minimization problem calculate the penalty parameter for each row and
each column by subtracting the lowest cost of the associated row (column) in question from
the next lowest cost in that row/column (if both cost i.e. lowest and next lowest cost are
the same, then the penalty is zero). Then an allocation is made to the lowestcost cell of
the row or column with the highest penalty parameter. The procedure continues until all
the allocations are made, ignoring rows or columns where the supply from a given source is
depleted.
170
Vishwas Deep Joshi and Nilama Gupta
For a maximization problem begin by finding the variable xi
which corresponds to
1 j1
the highest profit (highest value ofrij + sij ). Assign x
its largest possible value, i.e.
t
i
ij
1 j1
xi
= min(b , a ). Mark (cross out) row i
1 j1
i1
j1
1 and column j1 and reduce the corresponding
supply and demand by the value of xi
. Repeat the procedure using only those cells that
1 j1
do not lie in the crossed out rows and columns. Continue this process until there is only
one cell in the transportation tableau that can be chosen.
The heuristic presented is based on the fractional cost concept and hence will be referred to
as the "Fractional Cost Penalty Method" (FCPM) (Joshi and Gupta [11] ). The FCPM uses
rij + sij whereas Vogel's Approximation Method (VAM) uses only one of the three values
tij
rij,sij or tij giving this heuristic a computational advantage over VAM. We demonstrate
this heuristic by a numerical example.
Numerical Example 1
Take the following minimization problem. Its optimal IBFS isX13 = 7, X21 = 2, X23 =
8, X31 = 3,X32 = 8withZ0 = 147 + 78 = 147.36. LPLFTP is given in Table 1. In Table 3
217
the optimal solution of the LPLFTP is presented.
Calculate the ratio of rij + sij and using ratio find out the penalties corresponding to
tij
the rows and columns that are given in Table 2. The values in the brackets are the IBFS
whereas the values outside the brackets arerij + sij .
tij
The IBFS of the minimization problem is X13 = 7, X21 = 2, X23 = 8, X31 = 3, X32 = 8 with
all other Xij = 0 and the objective function Z0 = 147 + 78 = 147.36 by the method FCPM
217
presented in this paper whereas VAM method gives X12 = 7, X21 = 5, X23 = 5, X32 =
1, X33 = 10 with Z = 154 + 182 = 155.36, implying the superiority of the method FCPM
134
for the minimization problem. For finding the optimal solution from IBFS obtained, the
procedure of [10] is used. It can be observed that the optimal solution is obtained in lesser
iterations (in fact IBFS is the optimal solution in this particular problem), if FCPM is used
as compare to VAM (in this particular problem it uses two more iterations).
On a Paradox in Linear Plus Linear Fractional Transportation Problem
171
Table 2: Penalty Matrix using FCPM
B1
B2
B3
Supply
Penalties
(1)
(2)
A1
8.25
2.6
(7) 9.76
7
5.65
1.51
A2
(2) 3.4
9.58
(8) 5.22
10
1.82
1.82
A3
(3) 8.58
(8) 2.11
15
11
6.47
6.42
Demand
5
8
15
28
Penalties 4.85
.49
4.54
4
MoreforLess Paradox in LPLFTP
The MFL (or nothing) paradox in the LPLFTP occurs when it is possible to ship more
total goods for less (equal) total cost even if at least the same amount is shipped from each
origin to destinations and all shipping costs are non negative. The MFL paradox is based
on relaxing the equality constraint for a given LPLFTP.
m
n
m
n
s
i=1
j=1
ij xij
(P 2) Minimize Z =
r
ij xij +
m
n
tijxij
i=1 j=1
i=1
j=1
n
subject to
xij ai,
i = 1, 2, ......, m
j=1
m
xij bj,
j = 1, 2, ......, n
i=1
xij 0, i = 1, 2, ......, m; j = 1, 2, ......, n
m
n
ai =
bj = F 0
i=1
j=1
172
Vishwas Deep Joshi and Nilama Gupta
ai > 0, bj > 0, i = 1, 2, ......, m; j = 1, 2, ......, n
where
m
n
m
n
m
n
rijxij 0,
sijxij 0,
tijxij > 0 , tij > 0, sij 0 and rij 0
i=1 j=1
i=1 j=1
i=1 j=1
Clearly an optimal feasible solution of (P 1) is a feasible solution of (P 2), yielding the
objective function flow pair(Z0, F 0).
Definition (Paradoxical solution):
A solution Xp of (P 2) yielding the objective functionflow pair (Zp, F p) is called a `Para
doxical solution', if for any other feasible solution of (P 2) yielding a flow pair (Z, F ), we
have
(Z, F ) > (Zp, F p)
or
Z = Zp, but F < F p
or
F = F p , but Z > Zp
Let the optimal feasible solution of (P 1)yield a value Zo = R0 + S0 of the objective
T 0
functionR(X) + S(x) . Then the condition for a paradoxical situation in a LPLFTP is given
T (x)
by the following theorem.
5
Sufficient Condition for Paradoxical Solution in LPLFTP
Theorem 1.2: If there exist a cell (i, j)in the table corresponding to the optimal solution
X0of the problem(P 1), such that
[ [
]
]
T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3) < 0
i
j
i
j
i
j
i
j
and the basis corresponding to a basic feasible solution of the problem(P 1)with aireplaced
by ai + and bjby bj + is the same as that corresponding to X0, then there exist a
paradoxical situation.
Proof: At an optimal basic feasible solution of(P 1).
S0
s
iI
jJ
ij xij
Z0 = R0 +
=
r
ij xij +
T 0
tijxij
iI jJ
iI
jJ
(u2 + v2)x
iI
jJ
i
j
ij
=
(u1 + v1)x
i
j
ij +
(u3 + v3)xij
iI jJ
iI
jJ
i
j
(xij = 0, non  basic cells (i, j))
a
+
b
iI
iu2
i
jJ j v2
j
=
a
iu1 +
b
+
i
j v1
j
aiu3 +
bjv3
iI
jJ
iI
i
jJ
j
On a Paradox in Linear Plus Linear Fractional Transportation Problem
173
Suppose ai is replaced by ai + and bjby bj + for some > 0, and then consider the
problem (P 2) as
S(X)
(P 3) Minimize Z = R(X) + T(X)
subject to
xij =
ai,
i I
jJ
xij = bj, j J
iI
xij 0
where
ak = ak
k I  {i} and ai = ai +
bl = bl
l J  {j} and bj = bj +
for > 0
Clearly, every feasible solution of (P 3)is a feasible solution of(P 1).
The basis corresponding to optimal basic feasible solution of (P 1)will yield a basic
feasible solution for(P 3), for which value of the objective function
Zwould be given as
Z =
aku1 +
b
+ (a
+ (b
k
lv1
l
i + )u1
i
j + )v1
j
k=i
l=j
a
+
b
+ (a
+ (b
k=i
k u2
k
l=j lv2
l
i + )u2
i
j + )v2
j
+
a
+
b
+ (a
+ (b
k=i
k u3
k
l=j lv3
l
i + )u3
i
j + )v3
j
aku2 +
blv2 + (u2 + v2)
i
j
=
a
kI
k
lJ
l
k u1 +
b
+ (u1 + v1) +
k
lv1
l
i
j
aku3 +
blv3 + (u3 + v3)
kI
lJ
kI
k
lJ
l
i
j
S0 + (u2 + v2)
i
j
= R0 + (u1 + v1) +
i
j
T 0 + (u3 + v3)
i
j
S0 + (u2 + v2)
i
j
Z  Z0 = R0 + (u1 + v1) +
 R0  S0
i
j
T 0 + (u3 + v3)
T 0
i
j
[ [
]
]
T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
Z  Z0 =
[
]
< 0
T 0 T 0 + (u3 + v3)
i
j
Z < Z0
Thus new flow
F =
a
b
kI
k + =
lJ l + = F 0 + . Thus the value of the objective
function has fallen below the optimal value of (P 1) and flow has increased.
Thus for flow F 0 + , there exist one feasible solution with value of objective function
less than Z0. This implies that for flow F 0 + , optimal value of the objective function will
be strictly less than Z0. This implies that `Paradoxical Solution' exists.
174
Vishwas Deep Joshi and Nilama Gupta
6
Heuristic for finding Paradoxical Solution in LPLFTP
First of all find the optimal solution of given LPLFTP. After it the process of calculating
shadow price matrices for R(X), S(X) and D(X) is exactly the same as evaluating cells
using the modified distribution method (MODI). Prepare the matrix M
(
[ [
]
])
i.e. M = T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
using optimal solution and shadow price matrix. Suppose an unloaded cell (q, r) appear
in Table 4 and its corresponding value in matrix M with negative value Mqras shown in
Table 5 Cell(q, r) is not loaded so there must be at least one other loaded cell in row
q and in column r each (in Table 4), lets take (k, r) and (q, p), to satisfy demand and
supply requirement. The value Xkr and Xqp represent the optimal load at those locations
respectively (in Table 4), the superscript * represents the location with the negative value
in matrix M as indicated within brackets (in Table 5).
Table 5: Identifying Negative Values in M
Column r
Column p
Row k
Mkr

Row q
(Mqr)
Mqp
Now notice (in Table 4) that if cell (k, r) (or cell (q, p)) is only loaded cell in that column
(or row), than by eliminating column r (or row q ) we eliminate the negative value from
matrix M (in Table 5) and associated loaded cell without affecting the values of the other
negative values of matrix M. This means that the remaining LPLFTP has no MFL solution
(without changing the initial transportation route). Therefore, the load causing the MFL
phenomena is located in the column r (on the row q ). The same analysis holds if more than
one negative entries in matrix M of an optimal solution. Hence to explore the possibility of
existence of an MFL situation, the first step is to prepare the matrix M using an optimal
solution of a LPLFTP.
On a Paradox in Linear Plus Linear Fractional Transportation Problem
175
Search for mfl Solution
As already mentioned, the mfl phenomenon is based on relaxing the equality constraints for
a given LFtp. Since
xij in the mfl is greater than the corresponding sum in nominal
LPLFtp due to constraint relaxation, the gain resulting from moving load from a cells with
a lowest cost coefficient dij or cij (minimize or maximize) to a cell with a smaller/larger
cost coefficient must offset the extra cost resulting from the additional load.
A given LPLFtp is called perfect if the optimal solution has the max(m, n) loaded cells.
In the MFL phenomenon, sometimes moving load from a larger cost coefficient cell to a
smaller cost coefficient cell (vice versa) reduces the size of the basis, causing the LFTP
to move closer to perfection, and this gives rise to the problem of degeneracy. Since the
optimal shipping route is kept the same, the problem of degeneracy is resolved by loading
zero shipments to the cells which were initially in the basis.
Table 7: Assigning Allotments
Column r
Column?
Row k
Max (ak , br )
0
Row?
0
Assume that there is a cell (k, r)which yields some gain (decrease of the total cost)
during the decomposition process (refer Table 6 and Table 7). While increasing the load at
cell (k, r) by , the same value is subtracted from other cell(s) in row k and column r, and
then the rest of the load is distributed optimally in compliance with the equality/inequality
constraints. Following this procedure, there will be an instance when the load in either row
k or column r will be exhausted and only one loadmaximum of ak or br would remain.
Notice that during this process, the equality constraint is relaxed, as the final load of
max(ak, br) is greater than one of the values ak or br. Since this assignment of maximum
load at cell (k, r) satisfies the column and row constraints simultaneously, we take a step
towards decomposition of the LPLFtp. The proposed algorithm for finding an mfl solution
of LPLFTP is as follows:
MFL Procedure
This procedure is similar to the procedure given in [5] with some modification for LPLFTP.
In this procedure rij + sij [in Step 6] is used to pick out the cell (k, r)unlike the cost
tij
coefficient in [5].
176
Vishwas Deep Joshi and Nilama Gupta
Step 1. Solve (P 2) using any method and find the optimal solution.
[ [
]
]
Step 2. Create M = T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
matrix using optimal solution and shadow prices corresponding to R0,S0 and T 0.
Step 3. Identify negative entries in the matrix M and related columns and rows.
Step 4. Pick out the rows and columns of the matrix M with most negative entries.
Step5. Pick out rows/columns with single loading cell among those identified in Step 4.
If the loading cells are more than one among these rows/columns then pass on to the next
number of negative entries in the rows/columns and pick the rows/columns with single
loading cell among them. Continue the process until a row/column with a single loading
cell is obtained.
Step 6. Pick out the single loading cell (k, r) with the lowest/highest value of rij + sij (for
tij
minimization /maximization) among those identified in Step 5.
Step 7. Assign Xkr = max(ak, br).
Step 8. Delete kth row and rth column from the cost matrix and the related matrix (M ).
Step 9. If the reduced matrix M contains any negative entry, go to Step 3.
Step 10. Solve the reduced problem as a regular unbalanced LPLFTP.
Remark: In our method we increase the total demand or supply corresponding to the
value of max(ak, br) (not going beyond the value of max(ak, br)) to the cell (k, r) (where
(k, r) is any single loading cell identified in most entries of negative values corresponding to
row or column).
Numerical Example 2
Step 1. The optimal solution of numerical example 1 is X13 = 7, X21 = 2, X23 = 8, X31 = 3,
X32 = 8 and all other Xij = 0 with Z0 = 147+ 78 = 147.36 and flow 28. Table 8 represents
217
the optimal solution.
[ [
]
]
Step 2. Create M =
T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
matrix using above optimal solution and shadow prices corresponding to R0,S0 andT 0.
Table 9, 10 and 11 represents the shadow prices with respects to rij, sij and tij.
Step 3. Identify negative entries in the Table 12 corresponding to the columns and rows.
Step 4. Row A2 and column B2 each have four negative entries in matrix M.
Step 5. Column B2 have single loading cell.
Step 6. Choose column B2 as it has single loading cell.
Step 7. AssignX32 = max(a3, b2) = 11.
Step 8. Delete row A3 and column B2 from Table 12.
Since there are no more negative entries as shown in Table 13, solve the reduced cost matrix
as a LPLFTP. Hence, the MFL solution to the problem is X13 = 7, X21 = 5 X23 = 8, X32 =
c
Department of Mathematics, UTM.
On a Paradox in Linear Plus Linear Fractional
Transportation Problem
1Vishwas Deep Joshi and 2Nilama Gupta
1,2Department of Mathematics, Malaviya National Institute of Technology,
J.L.N. Marg, Jaipur302017, CityplaceRajasthan, countryregionIndia
email: [email protected], 2n1 [email protected]
Abstract A paradoxical situation arises in a linear plus linear fractional transporta
tion problem (LPLFTP), when value of the objective function falls below the optimal
value and this lower value is attainable by transporting larger amount of quantity. In
this paper, a new heuristic is proposed for finding initial basic feasible solution for
LPLFTP and a sufficient condition for the existence of a paradoxical solution is es
tablished in LPLFTP. Two numerical examples are proposed for explanation of the
algorithms.
Keywords Transportation problem; linear plus linear fractional function; morefor
less paradox.
1
Introduction
The source of the socalled transportation paradox is unclear. Apparently, many researchers
have discovered independently from each other the following behavior of the transportation
problem: In certain cases of the transportation problem (TP), an increase in the supplies
and demands may lead to a decrease in the optimal transportation cost. In other words, by
moving bigger amount of goods around, one may save a lot of money. This surely sounds
paradoxical [1]. The moreforless (MFL) paradox in a TP occurs when it is possible to
ship more total goods for less (or equal) total cost, while shipping the same amount or
more from each origin and to each destination and keeping all the shipping costs non
negative. The occurrence of MFL in TP is not a rare event, and the existing literature has
demonstrated the practicality of identifying cases where the paradoxical situation exists [2].
The information of the occurrence of an MFL situation is useful to a manager in deciding
which warehouse or plant capacities are to be increased, and which markets should be
sought.
It could also be a useful tool in analyzing and planning company acquisition,
mergers, consolidations and downsizes. The so called MFL paradox in the transportation
paradox has been covered from a theoretical stand point by Charnes and Klingman [3],
and Charnes et al. [4]. Robb [5] provides an intuitive explanation of the transportation
occurrence. Adlakha and Kowalski [6], Adlakha et al. [7, 8] have given an algorithm for
solving paradoxical situation in linear transportation problem. They have already discussed
MFL paradox in linear transportation problem [6] as well as fixed charge [7] and mixed
constraints [8].
The LPLFTPs do exist especially when a compromise between absolute and relative
terms is to be maximized [9]. For example, the above problem arises when one wishes
to maximize the linear combination of income and profitability. Khurana and Arora [10]
presented an algorithm to solve LPLFTP. They considered two special cases of the problem,
where the transportation flow is either restricted or enhanced.
168
Vishwas Deep Joshi and Nilama Gupta
In section 2, the mathematical formulation of LPLFTP is discussed, in section 3, finding
a better initial basic feasible solution (IBFS) through fractional cost penalty method is pre
sented. Sections 4, 5 and 6 deals with the moreforless situation and a sufficient condition
for paradox in LPLFTP. Numerical examples are presented in sections 3 and 6 respectively
for the explanation of algorithms.
2
Mathematical Formulation of LPLFTP
Consider the following LPLFTP problem
m
n
m
n
s
i=1
j=1
ij xij
(P 1) Minimize Z =
r
ij xij +
m
n
tijxij
i=1 j=1
i=1
j=1
n
subject to
xij = ai,
i = 1, 2, ......, m
(1)
j=1
m
xij = bj,
j = 1, 2, ......, n
(2)
i=1
xij 0, i = 1, 2, ......, m; j = 1, 2, ......, n
(3)
m
n
ai =
bj = F 0
(4)
i=1
j=1
ai > 0, bj > 0, i = 1, 2, ......, m; j = 1, 2, ......, n
where
m
n
m
n
m
n
rijxij 0,
sijxij 0,
tijxij > 0 , tij > 0, sij 0 and rij 0,
i=1 j=1
i=1 j=1
i=1 j=1
rij= Per unit capital in transporting quantities from ith supply point to jth destination,
sij= Per unit depreciation in transporting quantities from ith supply point to jth destina
tion,
tij= Per unit profit earned in transporting quantities from ith supply point to jth destina
tion,
xij= Amount transported from the ith origin to the jth destination
ai= Amount available at the ith origin
bj= Demand of jth destination
Define the index sets I = {1, 2, ....., m} , J = {1, 2, ....., n} and K = I x J.
Let X = {xij/(i, j) K, xij satisfying the constraints (1)(3)} be a feasible solution of the
problem (P 1). Denote Ix = {(i, j) K/xij > 0, xij X}, the set of nondegenerate basic
cells. Due to constraint (4) each nondegenerate basic solution will contain (m + n  1)
positive components. Now we consider the dual variables u1, u2, u3 for i I and v1, v2, v3
i
i
i
j
j
j
for j J such that u1 + v1 = r
+ v2 = s
+ v3 = t
i
j
ij , u2
i
j
ij and u3
i
j
ij for (i, j) Ix.
On a Paradox in Linear Plus Linear Fractional Transportation Problem
169
Also for nonbasic variables, let
r
= r
+ v1)
ij
ij  (u1
i
j
s
= s
+ v2)
(5)
ij
ij  (u2
i
j
t
= t
+ v3) f or (i, j) K  I
ij
ij  (u3
i
j
x
The system (5) has (m + n  1) equations and can be solved independently. Let xlj is a
basic variable then arbitrarily set u1 = 0, u2 = 0, u3 = 0 and solve for other dual variables.
l
l
l
Having determined the dual variables u1, u2, u3for i I; v1, v2, v3 for j J, use these
i
i
i
j
j
j
values for determining r , s , t
for all nonbasic variables. Then from [10]
ij
ij
ij
m
n
m
n
V1 =
aiu1 +
b
=
r
i
j v1
j
ij xij ,
i=1
j=1
i=1 j=1
m
n
m
n
V2 =
aiu2 +
b
=
s
i
j v2
j
ij xij ,
i=1
j=1
i=1 j=1
m
n
m
n
V3 =
aiu3 +
b
=
t
i
j v3
j
ij xij ,
i=1
j=1
i=1 j=1
The necessary and sufficient condition for optimality in LPLFTP as given in [10] is given
below.
Theorem 1.1. A basic feasible solution X = (x )is a local optimum solution of problem
ij
(P1) if Rij = r (V
V
V
ij
3)2 + sij 3  tij 2 0 non basic variable xij .
The determination of dual variablesu1, u2, u3 for i I and v1, v2, v3 for j J would
i
i
i
j
j
j
facilitate the calculation of Rij for nonbasic variables. The solution can be improved if
Rij < 0 for at least one nonbasic variable xij.
Remark: If there exist one or more Rij < 0, then we choose Ri
= min {R
0 j0
ij /Rij < 0}
and introduce the nonbasic variable xi
into the basis thereby improving the value of Z.
0 j0
The variable which leaves the basis and the value of the new basic variable in the basis can
be determined using [10].
3
Heuristic for finding IBFS for LPLFTP
An IBFS to problem (P 1) can be obtained by using following method
Step 1. Calculate the value of rij + sij for each cell and prepare the new matrix of fractional
tij
values.
Step 2. For a minimization problem calculate the penalty parameter for each row and
each column by subtracting the lowest cost of the associated row (column) in question from
the next lowest cost in that row/column (if both cost i.e. lowest and next lowest cost are
the same, then the penalty is zero). Then an allocation is made to the lowestcost cell of
the row or column with the highest penalty parameter. The procedure continues until all
the allocations are made, ignoring rows or columns where the supply from a given source is
depleted.
170
Vishwas Deep Joshi and Nilama Gupta
For a maximization problem begin by finding the variable xi
which corresponds to
1 j1
the highest profit (highest value ofrij + sij ). Assign x
its largest possible value, i.e.
t
i
ij
1 j1
xi
= min(b , a ). Mark (cross out) row i
1 j1
i1
j1
1 and column j1 and reduce the corresponding
supply and demand by the value of xi
. Repeat the procedure using only those cells that
1 j1
do not lie in the crossed out rows and columns. Continue this process until there is only
one cell in the transportation tableau that can be chosen.
The heuristic presented is based on the fractional cost concept and hence will be referred to
as the "Fractional Cost Penalty Method" (FCPM) (Joshi and Gupta [11] ). The FCPM uses
rij + sij whereas Vogel's Approximation Method (VAM) uses only one of the three values
tij
rij,sij or tij giving this heuristic a computational advantage over VAM. We demonstrate
this heuristic by a numerical example.
Numerical Example 1
Take the following minimization problem. Its optimal IBFS isX13 = 7, X21 = 2, X23 =
8, X31 = 3,X32 = 8withZ0 = 147 + 78 = 147.36. LPLFTP is given in Table 1. In Table 3
217
the optimal solution of the LPLFTP is presented.
Calculate the ratio of rij + sij and using ratio find out the penalties corresponding to
tij
the rows and columns that are given in Table 2. The values in the brackets are the IBFS
whereas the values outside the brackets arerij + sij .
tij
The IBFS of the minimization problem is X13 = 7, X21 = 2, X23 = 8, X31 = 3, X32 = 8 with
all other Xij = 0 and the objective function Z0 = 147 + 78 = 147.36 by the method FCPM
217
presented in this paper whereas VAM method gives X12 = 7, X21 = 5, X23 = 5, X32 =
1, X33 = 10 with Z = 154 + 182 = 155.36, implying the superiority of the method FCPM
134
for the minimization problem. For finding the optimal solution from IBFS obtained, the
procedure of [10] is used. It can be observed that the optimal solution is obtained in lesser
iterations (in fact IBFS is the optimal solution in this particular problem), if FCPM is used
as compare to VAM (in this particular problem it uses two more iterations).
On a Paradox in Linear Plus Linear Fractional Transportation Problem
171
Table 2: Penalty Matrix using FCPM
B1
B2
B3
Supply
Penalties
(1)
(2)
A1
8.25
2.6
(7) 9.76
7
5.65
1.51
A2
(2) 3.4
9.58
(8) 5.22
10
1.82
1.82
A3
(3) 8.58
(8) 2.11
15
11
6.47
6.42
Demand
5
8
15
28
Penalties 4.85
.49
4.54
4
MoreforLess Paradox in LPLFTP
The MFL (or nothing) paradox in the LPLFTP occurs when it is possible to ship more
total goods for less (equal) total cost even if at least the same amount is shipped from each
origin to destinations and all shipping costs are non negative. The MFL paradox is based
on relaxing the equality constraint for a given LPLFTP.
m
n
m
n
s
i=1
j=1
ij xij
(P 2) Minimize Z =
r
ij xij +
m
n
tijxij
i=1 j=1
i=1
j=1
n
subject to
xij ai,
i = 1, 2, ......, m
j=1
m
xij bj,
j = 1, 2, ......, n
i=1
xij 0, i = 1, 2, ......, m; j = 1, 2, ......, n
m
n
ai =
bj = F 0
i=1
j=1
172
Vishwas Deep Joshi and Nilama Gupta
ai > 0, bj > 0, i = 1, 2, ......, m; j = 1, 2, ......, n
where
m
n
m
n
m
n
rijxij 0,
sijxij 0,
tijxij > 0 , tij > 0, sij 0 and rij 0
i=1 j=1
i=1 j=1
i=1 j=1
Clearly an optimal feasible solution of (P 1) is a feasible solution of (P 2), yielding the
objective function flow pair(Z0, F 0).
Definition (Paradoxical solution):
A solution Xp of (P 2) yielding the objective functionflow pair (Zp, F p) is called a `Para
doxical solution', if for any other feasible solution of (P 2) yielding a flow pair (Z, F ), we
have
(Z, F ) > (Zp, F p)
or
Z = Zp, but F < F p
or
F = F p , but Z > Zp
Let the optimal feasible solution of (P 1)yield a value Zo = R0 + S0 of the objective
T 0
functionR(X) + S(x) . Then the condition for a paradoxical situation in a LPLFTP is given
T (x)
by the following theorem.
5
Sufficient Condition for Paradoxical Solution in LPLFTP
Theorem 1.2: If there exist a cell (i, j)in the table corresponding to the optimal solution
X0of the problem(P 1), such that
[ [
]
]
T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3) < 0
i
j
i
j
i
j
i
j
and the basis corresponding to a basic feasible solution of the problem(P 1)with aireplaced
by ai + and bjby bj + is the same as that corresponding to X0, then there exist a
paradoxical situation.
Proof: At an optimal basic feasible solution of(P 1).
S0
s
iI
jJ
ij xij
Z0 = R0 +
=
r
ij xij +
T 0
tijxij
iI jJ
iI
jJ
(u2 + v2)x
iI
jJ
i
j
ij
=
(u1 + v1)x
i
j
ij +
(u3 + v3)xij
iI jJ
iI
jJ
i
j
(xij = 0, non  basic cells (i, j))
a
+
b
iI
iu2
i
jJ j v2
j
=
a
iu1 +
b
+
i
j v1
j
aiu3 +
bjv3
iI
jJ
iI
i
jJ
j
On a Paradox in Linear Plus Linear Fractional Transportation Problem
173
Suppose ai is replaced by ai + and bjby bj + for some > 0, and then consider the
problem (P 2) as
S(X)
(P 3) Minimize Z = R(X) + T(X)
subject to
xij =
ai,
i I
jJ
xij = bj, j J
iI
xij 0
where
ak = ak
k I  {i} and ai = ai +
bl = bl
l J  {j} and bj = bj +
for > 0
Clearly, every feasible solution of (P 3)is a feasible solution of(P 1).
The basis corresponding to optimal basic feasible solution of (P 1)will yield a basic
feasible solution for(P 3), for which value of the objective function
Zwould be given as
Z =
aku1 +
b
+ (a
+ (b
k
lv1
l
i + )u1
i
j + )v1
j
k=i
l=j
a
+
b
+ (a
+ (b
k=i
k u2
k
l=j lv2
l
i + )u2
i
j + )v2
j
+
a
+
b
+ (a
+ (b
k=i
k u3
k
l=j lv3
l
i + )u3
i
j + )v3
j
aku2 +
blv2 + (u2 + v2)
i
j
=
a
kI
k
lJ
l
k u1 +
b
+ (u1 + v1) +
k
lv1
l
i
j
aku3 +
blv3 + (u3 + v3)
kI
lJ
kI
k
lJ
l
i
j
S0 + (u2 + v2)
i
j
= R0 + (u1 + v1) +
i
j
T 0 + (u3 + v3)
i
j
S0 + (u2 + v2)
i
j
Z  Z0 = R0 + (u1 + v1) +
 R0  S0
i
j
T 0 + (u3 + v3)
T 0
i
j
[ [
]
]
T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
Z  Z0 =
[
]
< 0
T 0 T 0 + (u3 + v3)
i
j
Z < Z0
Thus new flow
F =
a
b
kI
k + =
lJ l + = F 0 + . Thus the value of the objective
function has fallen below the optimal value of (P 1) and flow has increased.
Thus for flow F 0 + , there exist one feasible solution with value of objective function
less than Z0. This implies that for flow F 0 + , optimal value of the objective function will
be strictly less than Z0. This implies that `Paradoxical Solution' exists.
174
Vishwas Deep Joshi and Nilama Gupta
6
Heuristic for finding Paradoxical Solution in LPLFTP
First of all find the optimal solution of given LPLFTP. After it the process of calculating
shadow price matrices for R(X), S(X) and D(X) is exactly the same as evaluating cells
using the modified distribution method (MODI). Prepare the matrix M
(
[ [
]
])
i.e. M = T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
using optimal solution and shadow price matrix. Suppose an unloaded cell (q, r) appear
in Table 4 and its corresponding value in matrix M with negative value Mqras shown in
Table 5 Cell(q, r) is not loaded so there must be at least one other loaded cell in row
q and in column r each (in Table 4), lets take (k, r) and (q, p), to satisfy demand and
supply requirement. The value Xkr and Xqp represent the optimal load at those locations
respectively (in Table 4), the superscript * represents the location with the negative value
in matrix M as indicated within brackets (in Table 5).
Table 5: Identifying Negative Values in M
Column r
Column p
Row k
Mkr

Row q
(Mqr)
Mqp
Now notice (in Table 4) that if cell (k, r) (or cell (q, p)) is only loaded cell in that column
(or row), than by eliminating column r (or row q ) we eliminate the negative value from
matrix M (in Table 5) and associated loaded cell without affecting the values of the other
negative values of matrix M. This means that the remaining LPLFTP has no MFL solution
(without changing the initial transportation route). Therefore, the load causing the MFL
phenomena is located in the column r (on the row q ). The same analysis holds if more than
one negative entries in matrix M of an optimal solution. Hence to explore the possibility of
existence of an MFL situation, the first step is to prepare the matrix M using an optimal
solution of a LPLFTP.
On a Paradox in Linear Plus Linear Fractional Transportation Problem
175
Search for mfl Solution
As already mentioned, the mfl phenomenon is based on relaxing the equality constraints for
a given LFtp. Since
xij in the mfl is greater than the corresponding sum in nominal
LPLFtp due to constraint relaxation, the gain resulting from moving load from a cells with
a lowest cost coefficient dij or cij (minimize or maximize) to a cell with a smaller/larger
cost coefficient must offset the extra cost resulting from the additional load.
A given LPLFtp is called perfect if the optimal solution has the max(m, n) loaded cells.
In the MFL phenomenon, sometimes moving load from a larger cost coefficient cell to a
smaller cost coefficient cell (vice versa) reduces the size of the basis, causing the LFTP
to move closer to perfection, and this gives rise to the problem of degeneracy. Since the
optimal shipping route is kept the same, the problem of degeneracy is resolved by loading
zero shipments to the cells which were initially in the basis.
Table 7: Assigning Allotments
Column r
Column?
Row k
Max (ak , br )
0
Row?
0
Assume that there is a cell (k, r)which yields some gain (decrease of the total cost)
during the decomposition process (refer Table 6 and Table 7). While increasing the load at
cell (k, r) by , the same value is subtracted from other cell(s) in row k and column r, and
then the rest of the load is distributed optimally in compliance with the equality/inequality
constraints. Following this procedure, there will be an instance when the load in either row
k or column r will be exhausted and only one loadmaximum of ak or br would remain.
Notice that during this process, the equality constraint is relaxed, as the final load of
max(ak, br) is greater than one of the values ak or br. Since this assignment of maximum
load at cell (k, r) satisfies the column and row constraints simultaneously, we take a step
towards decomposition of the LPLFtp. The proposed algorithm for finding an mfl solution
of LPLFTP is as follows:
MFL Procedure
This procedure is similar to the procedure given in [5] with some modification for LPLFTP.
In this procedure rij + sij [in Step 6] is used to pick out the cell (k, r)unlike the cost
tij
coefficient in [5].
176
Vishwas Deep Joshi and Nilama Gupta
Step 1. Solve (P 2) using any method and find the optimal solution.
[ [
]
]
Step 2. Create M = T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
matrix using optimal solution and shadow prices corresponding to R0,S0 and T 0.
Step 3. Identify negative entries in the matrix M and related columns and rows.
Step 4. Pick out the rows and columns of the matrix M with most negative entries.
Step5. Pick out rows/columns with single loading cell among those identified in Step 4.
If the loading cells are more than one among these rows/columns then pass on to the next
number of negative entries in the rows/columns and pick the rows/columns with single
loading cell among them. Continue the process until a row/column with a single loading
cell is obtained.
Step 6. Pick out the single loading cell (k, r) with the lowest/highest value of rij + sij (for
tij
minimization /maximization) among those identified in Step 5.
Step 7. Assign Xkr = max(ak, br).
Step 8. Delete kth row and rth column from the cost matrix and the related matrix (M ).
Step 9. If the reduced matrix M contains any negative entry, go to Step 3.
Step 10. Solve the reduced problem as a regular unbalanced LPLFTP.
Remark: In our method we increase the total demand or supply corresponding to the
value of max(ak, br) (not going beyond the value of max(ak, br)) to the cell (k, r) (where
(k, r) is any single loading cell identified in most entries of negative values corresponding to
row or column).
Numerical Example 2
Step 1. The optimal solution of numerical example 1 is X13 = 7, X21 = 2, X23 = 8, X31 = 3,
X32 = 8 and all other Xij = 0 with Z0 = 147+ 78 = 147.36 and flow 28. Table 8 represents
217
the optimal solution.
[ [
]
]
Step 2. Create M =
T 02 + T 0(u3 + v3) (u1 + v1) + T 0(u2 + v2)  S0(u3 + v3)
i
j
i
j
i
j
i
j
matrix using above optimal solution and shadow prices corresponding to R0,S0 andT 0.
Table 9, 10 and 11 represents the shadow prices with respects to rij, sij and tij.
Step 3. Identify negative entries in the Table 12 corresponding to the columns and rows.
Step 4. Row A2 and column B2 each have four negative entries in matrix M.
Step 5. Column B2 have single loading cell.
Step 6. Choose column B2 as it has single loading cell.
Step 7. AssignX32 = max(a3, b2) = 11.
Step 8. Delete row A3 and column B2 from Table 12.
Since there are no more negative entries as shown in Table 13, solve the reduced cost matrix
as a LPLFTP. Hence, the MFL solution to the problem is X13 = 7, X21 = 5 X23 = 8, X32 =