An Approach to Solve a Possibilistic Linear Programming Problem ()
Keywords:Multi Objective Linear Programming Problem; Fuzzy Set Theory; Trapezoidal Fuzzy Numbers; Possibilistic Linear Programming Problem
1. Introduction
In a supply chain, a distribution planning decision (DPD) problem involves optimizing the distribution plan for transporting goods from a set of sources to a set of destinations. In most real world problems, the decision maker has to often deal with several objectives, which might be conflicting in nature. Also, available supply, forecast demand and related cost/time/profit coefficients, are often imprecise (fuzzy) because of incomplete or (and) unavailable information. Fuzzy set theory was presented by Zadeh [1]. It was taken ahead when Bellman and Zadeh [2] proposed the concept of decision making in fuzzy environments. After the pioneering work on fuzzy linear programming by Zimmermann [3], several kinds of fuzzy linear programming problems have appeared in the literature and different methods have been proposed to solve such problems.
Furthermore, Zimmermann [4] extended his FLP method to a multi-objective linear programming (MOLP) problem. Related studies on solving DPD problems with multiple fuzzy objectives included Hussein [5] and Abd El-Wahed [6]. Moreover, Lai and Hwang [7] developed an auxiliary MOLP model for solving PLP problems with imprecise objective and/or constraint coefficients with triangular distributions. Tien-Fu Liang [8] integrated the available concepts to solve multi-objective DPD problems involving imprecise available supply, forecast demand and unit cost/time coefficients with triangular possibility distributions.
In this article, we deal with a kind of PLP problem involving multiple objectives of conflicting nature. We have considered an MOLP problem whose objective is to simultaneously minimize cost and maximize profit in a supply chain where cost and profit coefficients, and related parameters such as available supply, forecast demand and budget are fuzzy with trapezoidal fuzzy numbers. The proposed methodology provides an interactive framework, which enables the decision maker to suitably alter the solution until a satisfactory solution if obtained. We also show that the method adopted by Lai and Hwang [7] or Tien Fu Liang [8] is a special case of the proposed algorithm.
The proposed methodology can be applied to various real world multi objective problems such as assignment problems, transportation problems and many more such problems in which the information is given in the form of trapezoidal/triangular/interval possibility distributions.
2. Notations
§ Index sets
§ i index for source, for all 
§ j index for destination, for all 
§ g index for objectives, for g = 1, 2
§ Decision variables
§ 
units distributed from source i to destination j (units)
§ Objective functions
§ 
total distribution costs ($)
§ 
total profit ($)
§ Parameters
§ 
distribution cost per unit delivered from source i to destination j ($/unit)
§ 
profit per unit delivered from source i to destination j ($/unit)
§ 
total available supply for each source i (units)
§ 
total forecast demand of each destination j (units)
§ 
total budget ($)
3. Problem Description
A general multi objective distribution programming problem aims to determine the right plan for distributing a homogeneous commodity from m sources to n destinations. Each source has an available supply of the commodity to distribute to various destinations, and each destination has a forecast demand of the commodity to be received from various sources. The available supply for each source, the forecast demand for each destination, and related cost/profit coefficients are generally imprecise over the planning horizon due to incomplete and/or unobtainable information. The proposed PLP method aims to simultaneously minimize the total distribution costs and maximize the total profit with reference to available supply constraint at each source, forecast demand constraint at each destination and the total budget constraint. This work focuses on developing an interactive PLP method for optimizing the distribution plan in uncertain environments.
Thus, all the objectives are imprecise thereby incorporating the variations in the decision maker’s judgments relating to the solutions of the multi objective optimization problems in a framework of fuzzy aspiration levels. The pattern of trapezoidal possibility distribution is adopted to represent the imprecise objective functions and related imprecise numbers. All of the objective functions and the constraints are linear and the cost and profit on a given route are directly proportional to the units distributed.
Mathematically,
(3.1)
(3.2)
Subject to
(3.3)
(3.4)
(3.5)
Here
, 
, 
, 
, 
are all fuzzy with trapezoidal possibility distribution
,
.
4. Methodology
Since all the given parameters are assumed to be fuzzy with trapezoidal possibility distribution so, in particular, cost coefficient 
is written as 
(see Figure 1), where 
is the most optimistic value that has a very low likelihood of belonging to the set of available values ( degree of association = 0),
is the interval of most possible value that definitely belongs to the set of available values (degree of association = 1, if normalized), 
is the most pessimistic value that has a very low likelihood of belonging to the set of available values ( degree of association = 0).
Geometrically, the imprecise objective function for cost is fully defined by four prominent points
, 
, 
and
. Since the objective is to minimize cost so in order to get a minimum cost we shift the trapezium to the left ensuring higher possibility of getting a low value of cost. Thus, we aim to simultaneously minimize
; maximize the possibility of getting a value in region I of Figure 2,
; maximize the possibility of getting a value in region II of Figure 2,
; and minimize the possibility of getting a value in region III of Figure 2,
.
Therefore, the fuzzy cost objective is broken down into the following four crisp objectives
Figure 1. Trapezoidal possibility distribution of
.
Figure 2. Strategy involved for imprecise cost objective.
(4.1)
(4.2)
(4.3)
(4.4)
Similarly, profit coefficient 
is written as
, where 
is the most optimistic value that has a very low likelihood of belonging to the set of available values (degree of association = 0), 
is the interval of most possible value that definitely belongs to the set of available values (degree of association = 1, if normalized), 
is the most pessimistic value that has a very low likelihood of belonging to the set of available values ( degree of association = 0).
Geometrically, the imprecise objective function for profit is fully defined by four prominent points
, 
, 
and
. Since the objective is to maximize profit so in order to get maximum profit we shift the trapezium to the right ensuring higher possibility of getting a higher value of profit. Thus, we aim to simultaneously maximize
; minimize the possibility of getting a value in region I of Figure 3,
; maximize the possibility of getting a value in region II of Figure 3,
; and maximize the possibility of getting a value in region III of Figure 3,
.
So, the fuzzy profit objective is broken down into the following four crisp objectives
(4.5)
(4.6)
(4.7)
(4.8)
Further, the first two sets of constraints, corresponding to available supply and forecast demand, are inequalities with crisp numbers on the left and fuzzy numbers on the right hand side. So, to defuzzify, we apply the weighted approach. Let 
and 
be the associated weights, where
. Let β be the minimum acceptability level. Then, the corresponding crisp constraints are as follows
Figure 3. Strategy involved for imprecise profit objective.
(4.9)
The budget constraint is an inequality with fuzzy numbers on both the sides, so fuzzy ranking method is adopted to defuzzify the constraint. Accordingly, if the minimum acceptable possibility is specified by the DM, the corresponding auxiliary crisp inequality can be represented as
(4.11)
(4.12)
(4.13)
(4.14)
The auxiliary MOLP problem developed above can be converted into an equivalent ordinary LP form using Zimmermann’s [3] linear membership functions to represent all of the fuzzy objectives of the DM, together with the fuzzy decision-making concept of Bellman and Zadeh [2]. First, obtain the corresponding positive ideal solutions (PIS) and negative ideal solutions (NIS) of all the crisp objective functions of the auxiliary MOLP problem, as follows
Note that PIS is the optimum value of the objective over the given set of constraints when all the other objectives are ignored and NIS is the optimum value of its dual over the given set of constraints. Furthermore, the corresponding linear membership function for each of the new objective functions of the auxiliary MOLP problem is defined by
(4.15)
(4.16)
Linear membership functions for objective functions (4.4) and (4.7) are similar to the linear membership function for objective function (4.1) given by the Equation (4.15) and the linear membership function for objective functions (4.3), (4.5), (4.6) and (4.8) are similar to the linear membership function for objective function (4.2) given by the Equation (4.16).
Finally, aggregate all fuzzy sets using the minimum operator of fuzzy decision making concept. Let λ be the auxiliary variable
, which represents the degree of satisfaction of the decision maker. Thus, we aim to maximize the decision maker’s satisfaction, which is nothing but the minimum of the membership functions corresponding to the objectives [2,4]. Then, the corresponding single objective linear programming problem is max λ
s.t 
The above problem is a crisp single objective linear programming problem which can easily be solved using MATLAB.
5. Numerical Illustration
Consider the problem given in Table1
Also, the total budget,
.
Table 1. Problem in consideration.
*denotes the cost coefficient; **denotes the profit coefficient.
Table 2. PIS and NIS values of the objectives.
First, formulate the original multi-objective fuzzy problem using Equations (3.1) to (3.5). Then, develop the new objective functions for the new crisp multi-objective problem using Equations (4.1) to (4.8). Further, defuzzify fuzzy constraints to get crisp constraints using Equations (4.9) to (4.14) at 
assuming 
and
.
Get the PIS and NIS values (given in Table 2) corresponding to all the crisp objectives.
Additionally, the corresponding linear membership function for each of the fuzzy objectives in the auxiliary MOLP can be defined using Equations (4.15) and (4.16). Finally, the auxiliary MOLP can be converted to an equivalent LP model using the minimum operator to aggregate all fuzzy sets. This LP is then solved using MATLAB.
The solutions are imprecise and have trapezoidal possibility distribution, and overall degree of decision maker satisfaction is 0.9686. Thus, the optimal plan by the above method is as follows:
6. CONCLUSIONS
This work develops an interactive method for solving multi-objective problems with imprecise available supply, forecast demand and unit cost/profit coefficients with trapezoidal possibility distributions. The model designed here aims to simultaneously minimize the total distribution costs and maximize the total profit with reference to available supply at each source, as well as forecast demand constraints at each destination and the total budget constraint.
Also, the algorithm provides a systematic framework that facilitates the decision-making process, enabling a DM to interactively modify the imprecise data and related parameters until a set of satisfactory solutions is obtained. As the value of the parameter β is varied over the interval [0,1], a different optimal feasible solution is obtained. Thus, the DM can choose from a set of optimal solutions, the one which suits the DM most. The table below shows the value of λ for different values of β.
The method developed can be easily applied to any real world problem with trapezoidal/triangular/interval distributions such as distribution planning decision problems, assignment problems, job allocation problem and more such problems. The method described by Lai and Hwang is a special case of the algorithm described above. Lai and Hwang have considered triangular possibility distribution with both the objectives to be minimized, so if in the algorithm described above, we take
, for g = 1, 2 and both the imprecise objectives are converted to crisp objectives as in Equations (4.1) to (4.4) then we get the method described by Lai and Hwang. The method described in this paper has an edge over Lai and Hwang method as the method described in the paper covers a broader range of problems.