# The Intelligence of Dual Simplex Method to Solve Linear Fractional Fuzzy Transportation Problem

Authors: S. Narayanamoorthy; S. Kalyani
Journal: Computational Intelligence and Neuroscience
 (2015)

---

## Abstract

An approach is presented to solve a fuzzy transportation problem with linear fractional fuzzy objective function. In this proposed approach the fractional fuzzy transportation problem is decomposed into two linear fuzzy transportation problems. The optimal solution of the two linear fuzzy transportations is solved by dual simplex method and the optimal solution of the fractional fuzzy transportation problem is obtained. The proposed method is explained in detail with an example.


---

## Body

## 1. Introduction

The transportation problem refers to a special case of linear programming problem. The basic transportation problem was developed by Hitchcock in 1941 [1]. In mathematics and economics transportation theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French Mathematician Gaspard Monge. Tolstoi was one of the first person to study the transportation problem mathematically. Transportation problem deals with the distribution of single commodity from various sources of supply to various destinations of demand in such a manner that the total transportation cost is minimized. In order to solve a transportation problem the decision parameters such as availability, requirements and the unit transportation cost of the model must be fixed at crisp values.When applying OR-methods to engineering problems, for instance, the problems to be modelled and solved are normally quite clear cut, well described, and crisp. They can generally be modelled and solved by using classical mathematics which is dichotomous in character. If vagueness enters, it is normally of the stochastic kind which can properly be modelled by using probability theory. This is true for many areas such as inventory theory, traffic control, and scheduling, in which probability theory is applied via queuing theory. One of the most important areas of the kind in which the vagueness is of a different kind compared to randomness is probably that of decision making. In decision making the human factor enters with all its vagueness of perception, subjectivity, and attitudes of goals and of conceptions. In transportation problem supply, demand and unit transportation cost may be uncertain due to several factors; these imprecise data may be represented by fuzzy numbers. When the demand, supply, or the unit cost of the transportation problem takes a fuzzy value then the optimum value of that problem is also fuzzy, so it becomes a fuzzy transportation problem.Linear fractional programming deals with that class of mathematical programming problem in which the relations among the variables are linear; the constraint relation must be in linear form and the objective function to be optimized must be a ratio of two linear functions. The field of linear fractional programming problem was developed by Hungarian mathematician B. Matros in 1960. The linear fractional programming problem is an important planning tool for the past decades which is applied to different disciplines like engineering, business, finance, and economics. Linear fractional problem is generally used for modelling real life problems with one or more objective(s) such as profit-cost, inventory-sales, actual cost-standard cost, and output-employee; multiple level programming problems are frequently encountered in a hierarchical organization, manufacturing plant, logistic companies, and so forth. From practical point of view, it becomes necessary to consider the large structured programming problem. Even it is theoretically possible to solve this problem, in practical it is not easy to solve. There are certain limitations which restrict the endeavours of the analyst. Chief among these limitations is the problem of dimensionality. This suggests the idea of developing methods of solution that should not use simultaneously all the data of the problem; one such approach is the decomposition principle due to Dantzig [2] for linear programs. The principle requires the solution of a series of linear programming problems of smaller size than the original problem. In this paper, we proposed a new method to find the optimal solution of the fractional fuzzy transportation problem based on dual simplex approach.This paper is organised as follows. In Section2 related work is presented. Section 3 provides preliminary background on fuzzy set theory. The linear fractional fuzzy programming problem is explained in Section 4. In Section 5 problem formulation of fractional fuzzy transportation problem appeared. The procedure for the proposed method is given in Section 6. An illustrative example is provided to explain this proposed method and the conclusions are given in Sections 7 and 8, respectively.


## 2. Related Work

Fractional fuzzy transportation problem is a special type of linear programming problem and it is an active area of research. There are a lot of articles in this area which cannot be reviewed completely and only a few of them are reviewed here. Charnes and Cooper [3] developed a transformation technique z=1/(q′x+β) to convert fractional programming method to linear programming method, Swarup [4] introduced simplex type algorithm for fractional program, and Bitran and Novaes [5] converted linear fractional problem into a sequence of linear programs and the method is widely accepted. Tantawy [6] developed a dual solution technique for the fractional program. Hasan and Acharjee [7] used the conversion of linear fractional problem into single linear programming and computed inMATHEMATICA. Joshi and Gupta [8] solved the linear fractional problem by primal-dual approach. Sharma and Bansal [9] proposed a method based on simplex method in which the variables are extended. Jain et al. [10] proposed ABC algorithm for solving linear fractional programming problem using C-language. Sulaiman and Basiya [11] used transformation technique.Verma et al. [12] developed an algorithm which ranks the feasible solutions of an integer fractional programming problem in decreasing order of the objective function values. Metev and Yordanova-Markova [13] applied reference point method. Pandian and Jayalakshmi [14] used decomposition method and the denominator restriction method to convert fractional problem to linear problem. Chandra [15] proposed decomposition principle for solving linear fractional problem. Sharma and Bansal [9] gave an integer solution for linear fractional problem. Dheyah [16] gave optimal solution for linear fractional problem with fuzzy numbers. Güzel et al. [17] proposed an algorithm using first order Taylor series to convert interval linear fractional transportation problem into linear multiobjective problem. Madhuri [18] gave a solution procedure to minimum time for linear fractional transportation problem with impurities. Jain and Arya [19] solved an inverse transportation problem with linear fractional objective function.Motivated by the work of Güzel et al. [17], in this paper the author proposes a new method to find the optimal solution of the fractional fuzzy transportation problem. Some of the limitations in the existing methods are that, in Charnes and Coopers methods to obtain the solution, one needs to solve the linear problem by two-phase method in each step which becomes lengthy and clumsy. In Bitran and Novae’s method one needs to solve a sequence of problems which sometimes may need many iterations. In this method if p(x)<0 for all x then this method fails. In Swarup’s method when the constraints are not in canonical form then this method becomes lengthy and its computational process is complicated in each iteration. In Harvey’s method he converts the linear fractional problem max⁡⁡z=cx+α/dx+β to linear problem under the assumption that β≠0. If β=0 this method fails.To overcome these limitations, in this paper a new method is proposed such that the linear fractional transportation problem is decomposed into two linear fuzzy transportation problems under the assumption thatα, β values are zero. These linear transportation problems are solved by dual simplex method.


## 3. Preliminaries

In this section, we present the most basic notations and definitions, which are used throughout this work. We start with defining a fuzzy set.


### 3.1. Fuzzy Set [20]

LetX be a set. A fuzzy set A on X is defined to be a function A:X→[0,1] or μA:X→0,1. Equivalently, a fuzzy set is defined to be the class of objects having the following representation: A=x,μA(x),x∈X where μA:X→0,1 is a function called membership function of A.


### 3.2. Fuzzy Number [20]

The fuzzy numberA is a fuzzy set whose membership function satisfies the following conditions.(i)
μA(x) is piecewise and continuous.(ii)
A fuzzy setA of the universe of discourse X is convex.(iii)
A fuzzy set of the universe of discourseX is called a normal fuzzy set if there exists xi∈X.


### 3.3. Trapezoidal Fuzzy Number [20]

A fuzzy numbera~=(a1,a2,a3,a4) is said to be a trapezoidal fuzzy number if its membership function is given by
(1)μa~=0,x≤a1x-ab-a,a1≤x≤a21,a2≤x≤a3c-xd-c,a3≤x≤a40,x≥a4.


### 3.4. Arithmetic Operations

Leta~=a1,a2,a3,a4 and b~=(b1,b2,b3,b4) be two trapezoidal fuzzy numbers; the arithmetic operators on these numbers are as follows.Addition:(2)a~+b~=a1+b1,a2+b2,a3+b3,a4+b4.Subtraction:(3)a~-b~=a1-b1,a2-b2,a3-b3,a4-b4.Scalar multiplication:(4)ka~=ka1,ka2,ka3,ka4,k>0,ka~=ka4,ka3,ka2,ka1,k<0.


### 3.5. Ranking Function

The following ranking function defined here is used to compare the fuzzy values when we perform the dual simplex method. A ranking functionR:FR→R, which maps each fuzzy number into the real line. F(R) represents the set of all trapezoidal fuzzy numbers. If R is any ranking function, then Ra~=a~1+a~2+a~3+a~4/4.


### 3.6. Efficient Point

A feasible pointx0∈P is said to be an efficient solution for P if there exists no other feasible point x of the problem P such that zix≥zix0 and i=1,2.


### 3.7. Ideal Solution

Letx0 be the optimal solution to the problem Pt, t=1,2; then the value of the objective function ztx0, t=1,2, is called the ideal solution to the problem P.


### 3.8. Best Compromise Solution

An efficient solutionx0∈P is said to be the best compromise solution to the problem P, if the distance between the ideal solution and the objective value at x0, ztx0, t=1,2, is minimum among the efficient solution to the problem P.Lemma 1.
The feasible solution for the problemP is considered to be efficient if and only if there exist no other feasible solutions for which we obtain a better value at least for one criterion for which the value of the rest of criteria remains unmodified.Theorem 2.
IfXt is the set of efficient points for problem Pt, t=1,2, then Xt is a subset of the set of all efficient points X of P.Proof.
LetX1 be the set of efficient points of P1. Let X2 be the set of efficient points of P2. As Xt⊂X, t=1,2. The set of all efficient points of P1, P2 is contained in P.Theorem 3.
Letx-0={xij,xij∈P} be an optimal solution of P1 and let x_0={xij,xij∈P2} be an optimal solution of P2; then x=x-0/x_0 is an optimal solution of the given problem P where all of x11,x12,x21,x22,… are elements of P1, P2.Proof.
Letx-0 be an optimal solution of P1. This solution is an efficient solution if there is no feasible solution; these sets of efficient solutions are contained in x. Similarly the set of efficient solutions of P2 are contained in x. So, by Theorem 2, these solutions are the set of efficient solutions of P.


## 3.1. Fuzzy Set [20]

LetX be a set. A fuzzy set A on X is defined to be a function A:X→[0,1] or μA:X→0,1. Equivalently, a fuzzy set is defined to be the class of objects having the following representation: A=x,μA(x),x∈X where μA:X→0,1 is a function called membership function of A.


## 3.2. Fuzzy Number [20]

The fuzzy numberA is a fuzzy set whose membership function satisfies the following conditions.(i)
μA(x) is piecewise and continuous.(ii)
A fuzzy setA of the universe of discourse X is convex.(iii)
A fuzzy set of the universe of discourseX is called a normal fuzzy set if there exists xi∈X.


## 3.3. Trapezoidal Fuzzy Number [20]

A fuzzy numbera~=(a1,a2,a3,a4) is said to be a trapezoidal fuzzy number if its membership function is given by
(1)μa~=0,x≤a1x-ab-a,a1≤x≤a21,a2≤x≤a3c-xd-c,a3≤x≤a40,x≥a4.


## 3.4. Arithmetic Operations

Leta~=a1,a2,a3,a4 and b~=(b1,b2,b3,b4) be two trapezoidal fuzzy numbers; the arithmetic operators on these numbers are as follows.Addition:(2)a~+b~=a1+b1,a2+b2,a3+b3,a4+b4.Subtraction:(3)a~-b~=a1-b1,a2-b2,a3-b3,a4-b4.Scalar multiplication:(4)ka~=ka1,ka2,ka3,ka4,k>0,ka~=ka4,ka3,ka2,ka1,k<0.


## 3.5. Ranking Function

The following ranking function defined here is used to compare the fuzzy values when we perform the dual simplex method. A ranking functionR:FR→R, which maps each fuzzy number into the real line. F(R) represents the set of all trapezoidal fuzzy numbers. If R is any ranking function, then Ra~=a~1+a~2+a~3+a~4/4.


## 3.6. Efficient Point

A feasible pointx0∈P is said to be an efficient solution for P if there exists no other feasible point x of the problem P such that zix≥zix0 and i=1,2.


## 3.7. Ideal Solution

Letx0 be the optimal solution to the problem Pt, t=1,2; then the value of the objective function ztx0, t=1,2, is called the ideal solution to the problem P.


## 3.8. Best Compromise Solution

An efficient solutionx0∈P is said to be the best compromise solution to the problem P, if the distance between the ideal solution and the objective value at x0, ztx0, t=1,2, is minimum among the efficient solution to the problem P.Lemma 1.
The feasible solution for the problemP is considered to be efficient if and only if there exist no other feasible solutions for which we obtain a better value at least for one criterion for which the value of the rest of criteria remains unmodified.Theorem 2.
IfXt is the set of efficient points for problem Pt, t=1,2, then Xt is a subset of the set of all efficient points X of P.Proof.
LetX1 be the set of efficient points of P1. Let X2 be the set of efficient points of P2. As Xt⊂X, t=1,2. The set of all efficient points of P1, P2 is contained in P.Theorem 3.
Letx-0={xij,xij∈P} be an optimal solution of P1 and let x_0={xij,xij∈P2} be an optimal solution of P2; then x=x-0/x_0 is an optimal solution of the given problem P where all of x11,x12,x21,x22,… are elements of P1, P2.Proof.
Letx-0 be an optimal solution of P1. This solution is an efficient solution if there is no feasible solution; these sets of efficient solutions are contained in x. Similarly the set of efficient solutions of P2 are contained in x. So, by Theorem 2, these solutions are the set of efficient solutions of P.


## 4. Introduction to Linear Fractional Fuzzy Programming Problem (LFFPP)

One of the main aims of this paper is to extend the linear fractional problem into linear fractional fuzzy programming problem.The LFFPP can be presented in the following way:(5)max⁡hhhhfx=p(x)q(x)subjecttox∈S⊂Rn,
where p(x) and q(x) are linear functions and the set S is defined as S=x/Ax=b,x>0. Here A is a fuzzy m×n matrix; we will suppose that S is a bounded polyhedron and q(x)>0 for all x∈S. It is well known that the goal function in max f(x) has a global maximum function S and has not any other local maxima. This maximum is obtained at an extreme point of S.LFFPP (5) can now be written as
(6)max⁡hhhlhp(x)subjecttohhx∈S⊂Rnmax⁡hhhhq(x)subjecttox∈S⊂Rn.
Then by Theorem 3, if px/q(x)>0  ∀i and ∀x∈S then the set of efficient points for problem Pt, t=1,2, is a subset of the set of all efficient points of P.


## 5. Problem Formulation

The proposed fuzzy transportation model is based on the following assumption.Index Set. Consider the followingi is source index for all i=1,2,3,…,m.j is destination index for all j=1,2,3,…,n.Parameters. Consider the followingxij is the number of units transported from source i to destination j.cij is per unit profit cost of transportation from source i to destination j.dij is per unit cost of transportation from source i to destination j.Objective Function. Consider the following.(i)
Fractional transportation problem(7)min⁡⁡z=∑i=1m∑j=1ncijxij∑i=1m∑j=1ndijxij.
The values of cij and dij are considered to be trapezoidal fuzzy number.Constraints. Consider the following.(i) Constraints on supply available for all sourcesi(8)∑i=1mxij=ai∀i.(ii) Constraints on demand for each destinationj(9)∑j=1nxij=bj∀j.Nonnegative Constraints. Consider the following.(i) Nonnegative constraints on decision variables(10)xij≥0.
The above LFFTP will have a basic feasible solution only when ∑i=1mai=∑j=1nbj.


## 6. Procedure for Proposed Method

Here we present a new method for solving linear fractional fuzzy transportation problem.Consider the linear fractional fuzzy transportation problem as(11)P:min⁡hhhhhhz=∑i=1m∑j=1ncijxij∑i=1m∑j=1ndijxijP:subjectto∑i=1mxij=aiP:subjecto∑j=1nxij=bjP:subjectoxij≥0.
Since the objective function is a fractional objective function, we take the problem P into two linear fuzzy transportation problems by (6) as follows:
(12)P1:lmin⁡P1:hzN=∑i=1m∑j=1ncijxijNP1:subjectto∑i=1mxijN=aiP1:subjectlo∑j=1nxijN=bjP1:subjectoltxijN≥0P1:lmin⁡P1:hlzD=∑i=1m∑j=1ncijxijDP1:subjectto∑i=1mxijD=aiP1:subjectt∑j=1nxijD=bjP1:subjecttlxijD≥0.
We solve these two linear fuzzy transportation problems by dual simplex methods. Thus the solution is obtained for min⁡zN and min⁡zD separately. By Theorem 3, the optimum solution of P is obtained when the optimal solution of P1 and P2 is obtained.


## 7. Numerical Example

To illustrate the proposed method, consider the following example for linear fractional fuzzy transportation problem:(13)P:min⁡hhhhhhz=0,2,4,6x11+1,2,6,7x12P:min⁡hhhhhh+1,4,5,6x21+3,4,5,8x22P:min⁡hhhhhh·0,1,3,4x11+2,3,5,6x12P:min⁡hhhhhhhhl+1,3,5,7x21+2,6,7,9x22-1P:subjecttox11+x12≤60P:subjecttox21+x22≤45P:subjecttox11+x21≥50P:subjecttox12+x22≥55P:subjecttox11,x12,x21,x22≥0.
The problem P is a linear fractional fuzzy transportation problem in which the objective function has trapezoidal fuzzy number; supply and demand values are crisp values. Now by our computation technique the above problem can be written as
(14)P1:min⁡hhhhhhzN=0,2,4,6x11+1,2,6,7x12P1:minhhhhhhhhhh+1,4,5,6x21+(3,4,5,8)x22P1:subjecttox11+x12≤60P1:minhhhhhhx21+x22≤45P1:minhhhhhhx11+x21≥50P1:minhhhhhhx12+x22≥55P1:minhhhhhhx11,x12,x21,x22≥0,P2:min⁡hhhhhhzD=0,1,3,4x11+2,3,5,6x12hhhhhhhhhhhhhhhhh+1,3,5,7x21+2,6,7,9x22P2:subjecttox11+x12≤60P2:subjecttox21+x22≤45P2:subjecttox11+x21≥50P2:subjecttox12+x22≥55P2:subjecttox11,x12,x21,x22≥0.Consider P1: The linear problem can be expressed in standard form as(15)P1:min⁡hhhhhlhzN=0,2,4,6x11+1,2,6,7x12hhhhhhhhhhhhhhhhhh+1,4,5,6x21+(3,4,5,8)x22P1:subjecttox11+x12+s1=60P1:subjecttohx21+x22+s2=45P1:subjecttohx11+x21-s3=50P1:subjecttohx12+x22-s4=55P1:subjecttohx11,x12,x21,x22,s1,s2,s3,s4≥0.
Now P1 is solved by the dual simplex method.The initial iteration of the problem is given in Table1.Table 1
C
j
(−6, −4, −2, 0)
(−7, −6, −2, −1)
(−6, −5, −4, −1)
(−8, −5, −4, −3)
0
0
0
0
Y
B
X
B
X
11
X
12
X
21
X
22
S
1
S
2
S
3
S
4
0
S
1
60
1
1
0
0
1
0
0
0
0
S
2
45
0
0
1
1
0
1
0
0
0
S
3
−50
−1
0
−1
0
0
0
1
0
0
S
4
−55
0
−1
0
−1
0
0
0
1
z
=
0
(0, 2, 4, 6)
(1, 2, 6, 7)
(1, 4, 5, 6)
(3, 4, 5, 8)
0
0
0
0
R
(
⋯
)
3
4
4
5
0
0
0
0
↑
↓From the initial iteration we can see that the nonbasic variableX12 enters the basis and the basic variable S4 leaves the basis.Proceeding the dual simplex method and after few iterations we get Table2. In Table 2 all the values of XB are positive and the optimum solution is obtained as follows:
(16)min⁡⁡zN=100,390,755,995,x11=5,x12=55,x21=45.Consider P2: The linear problem can be expressed in standard form as(17)P2:min⁡hhhhhhzD=0,1,3,4x11+2,3,5,6x12hhhhhhhhhhhhhhhhhh+1,3,5,7x21+2,6,7,9x22P2:subjecttox11+x12+S1=60P2:subjecttox21+x22+S2=45P2:subjecttox11+x21-S3=50P2:subjecttox12+x22-S4=55P2:subjecttox11,x12,x21,x22,S1,S2,S3,S4≥0.
Now P2 is solved by the dual simplex method.Table 2
C
j
(−6, −4, −2, 0)
(−7, −6, −2, −1)
(−6, −5, −4, −1)
(−8, −5, −4, −3)
0
0
0
0
Y
B
X
B
X
11
X
12
X
21
X
22
S
1
S
2
S
3
S
4
(−8, −5, −4, −3)
X
21
45
0
0
1
1
−1
0
−1
−1
0
S
2
0
0
0
0
0
1
1
1
1
(−6, −5, −4, −1)
X
11
5
1
0
0
−1
1
0
0
1
(−7, −6, −2, −1)
X
12
55
0
1
0
1
0
0
0
−1
z
=
(
-
995
,
-
755
,
-
390
,
-
100
)
0
0
0
(−5, 8, 6, 9)
(−5, 0, 3, 6)
0
(1, 4, 5, 6)
(−4, 2, 9, 13)The initial iteration of the problem is given in Table3.Table 3
C
j
(−4, −3, −1, 0)
(−6, −5, −3, −2)
(−7, −5, −3, −1)
(−9, −7, −6, −2)
0
0
0
0
Y
B
X
B
X
11
X
12
X
21
X
22
S
1
S
2
S
3
S
4
0
S
1
60
1
1
0
0
1
0
0
0
0
S
2
45
0
0
1
1
0
1
0
0
0
S
3
−50
−1
0
−1
0
0
0
1
0
0
S
4
−55
0
−1
0
−1
0
0
0
1
z
=
0
(0, 1, 3, 4)
(2, 3, 5, 6)
(1, 3, 5, 7)
(2, 6, 7, 9)
0
0
0
0
R
(
⋯
)
2
4
4
6
0
0
0
0
↑
↓From the initial iteration we can see that the nonbasic variableX12 enters the basis and the basic variable S4 leaves the basis.Proceeding the dual simplex method and after few iterations we get Table4. In Table 4 all the values of XB are positive and the optimum solution is obtained as follows:
(18)min⁡⁡zD=155,305,515,665,x11=5,x12=55,x21=45.
By Theorem 3 the optimum solution of the fractional fuzzy transportation problem is obtained.Table 4
C
j
(−4, −3, −1, 0)
(−6, −5, −3, −2)
(−7, −5, −3, −1)
(−9, −7, −6, −2)
0
0
0
0
Y
B
X
B
X
11
X
12
X
21
X
22
S
1
S
2
S
3
S
4
(−7, −5, −3, −1)
X
21
45
0
0
1
1
−1
0
−1
−1
0
S
2
0
0
0
0
0
1
1
1
1
(−4, −3, −1, 0)
X
11
5
1
0
0
−1
1
0
0
1
(−6, −5, −3, −2)
X
12
55
0
1
0
1
0
0
0
−1
z
=
(
-
665
,
-
515
,
-
305
,
-
155
)
0
0
0
(8, −2, 3, 3)
(−3, 0, 4, 7)
0
(1, 3, 5, 7)
(−1, 3.9, 13)Thus(19)min⁡⁡z=(100,390,755,995)(155,305,515,665).


## 8. Conclusion

The present paper proposes a method for solving linear fractional fuzzy transportation problem where the trapezoidal fuzzy numbers are used in the objective function. The limitations of the existing methods are discussed. The advantage of the computational technique is that the method works even whenα, β values are zero. The dual simplex method is one of the best methods to get the optimal solution. The method can be easily implemented to solve any type of transportation problem. The solution procedures have been illustrated by an example. The result shows the high efficiency of the solution and this can be extended to fractional quadratic problems. The simplex method can be used instead of dual simplex if all the constraints are of ≤ type constraints.



---

*Source: 103618-2015-02-24.xml*