Characteristics of Multi-Objective Linear Programming Problem and Multi-Objective Linear Fractional Programming Problem Taking Maximum Value of Multi-Objective Functions

Samsun Nahar¹, Md. Asadujjaman^2,3, Khadiza Begum^2,3,   Mahede-Ul-Hassan⁴, Md. Abdul Alim⁵

¹Department of Basic Sciences and Humanities, University of Asia Pacific, Dhaka, Bangladesh.
²Department of Mathematics, University of Dhaka, Dhaka, Bangladesh.
³Computer Science and Engineering Department, Prime University, Dhaka, Bangladesh.
⁴Department of Mathematics and Statistics, Bangladesh University of Business and Technology, Dhaka, Bangladesh.
⁵Department of Mathematics, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh.

DOI: 10.4236/am.2024.151003                

Abstract

In this paper, a new statistical averaging technique is proposed for finding an optimal solution to a multi-objective linear fractional programming problem (MOLFPP) and multi-objective linear programming problem (MOLPP) by using new arithmetic averaging method and new geometric averaging method. It is significantly noticeable same characteristics among all the technique while taking maximum or minimum among all optimized values for multi-objective functions using simplex algorithm. The characteristics provided from the problems are verified by the numerical examples.

Keywords

MOLPP, MOLFPP, New Arithmetic Averaging Method, New Geometric Averaging Method

1. Introduction

The problem of multiple objectives linear programming (MOLP) arises when several linear objective functions have to be maximized (or minimized) on a convex polytope. Different approaches have been suggested for solving this problem, among which are the ones suggested by Evans and Steuer (1973), Tamura and Mura (1977). Gal (1977), Isermann (1977), Ecker and Kauda (1978) and Ecker, Hegren and Kauda (1980). Recent work concerning (MOLP) has been made by Schechter and Steuer (2005), Steuer and Pircy (2005). More researches involve the objective space analysis of multiple objective linear programming has been studied by Dauer and Liu (1990), also Dauer and Saleh (1990) in their article gave an algebraic representation of the objective space for (MOLP). Relation between faces of the decision space and those of the objective space was early investigated by Dauer (1987) and the reason for his investigation is to show that the objective space may have fewer dimensions than those of the decision space under the linear mapping [1] [2] [3] .

Fractional programming is used for modeling real-life problems such as industrial planning, production planning, financial and corporate planning, healthcare, and hospital planning. In recent years, several solution techniques and methods are proposed for solving the MOLFP problems in the literature. Chakraborty and Gupta (2002) explored a solution procedure for finding an efficient solution to the MOLFP problems based on a fuzzy set theoric approach and reduced the complexity of solving the considered problems. Costa (2005) developed an interactive method for computing the preferred non-dominated solution in MOLFP problems using some branch and bound techniques. The aim of the computation phase of the algorithm is to optimize one of the fractional objective functions while constraining the others. Guzel and Sivri (2005) presented a method via goal programming for finding an efficient solution to the MOLFP problems. Wu (2009) focused on a solution procedure for implementing the weighted max-ordering approach to obtain a weakly efficient solution to a MOLFP problem. The proposed approach needs a solution to a min-max auxiliary problem and thus he used the Taylor series method to linearize the auxiliary problem for computing efficiently [4] [5] .

Lotfi et al. (2010) proposed an LP approach to test the strongly and weakly efficient solutions in the MOLFP problems by applying a simple geometrical interpretation. Dangwal et al. (2012) used Taylor polynomial series approach to find a solution for the MOLFP problems via the vague set. Dheyab (2012) proposed a complementary method where the LFP problem is transformed into an LP problem by maximizing and minimizing the numerator and denominator, respectively, of the fractional objective function being maximized. Stanojevic and Stanojevic (2013) presented two procedures using the efficiency test introduced in the study of Lotfi et al. (2010) for generating strongly and weakly efficient solutions in MOLFP problems starting from any feasible solution. Sulaiman and Abdulrahim (2013) presented a number of transformation techniques from the MOLFP problem to the single-objective LFP problem by using average mean and average median values of objective functions to find the optimal solution and solved the problem by the modified simplex method. Jain (2014) presented a method using the Gauss elimination technique to derive a numerical solution of the MOLFP problem by extending his previous study proposed for finding a solution to the MOLP problem. Porchelvi et al. (2014) presented an algorithm for solving MOLFP problems for both crisp and fuzzy cases using the complementary method proposed in the study of Dheyab (2012). In the algorithm, any objective function of the MOLP problem is optimized subject to the original constraints and the additional constraints, which are the remaining objective functions. Tantawy (2014) proposed a feasible direction method only applicable only for a special class of MOLFP problems to find all efficient solutions [6] .

De and Deb (2015) used the Taylor series approach to solve MOLFP problems in the fuzzy environment. Taylor series approach is used to transform the MOLFP problems into the MOLP problems by introducing imprecise aspiration levels to each objective, and the additive weighted method is used to find the solution. Hossein-Abadi and Payan (2016) proposed a linearization procedure to present an interactive method for solving an MOLFPP which includes a simple calculation process [7] [8] .

The final solution is intended to meet the judgments of the decision-maker by interacting with one. Pramy and Islam (2017) proposed a method, modifying the studies of Dheyab (2012) and Porchelvi et al. (2014), presenting multiple efficient solutions by solving the MOLFP problems. The method provides the decision-makers flexibility to choose a better option among alternatives. Peric et al. (2017) presented a solution method to the MOLFP problems via the goal programming method by analyzing the applicability of linearization techniques, which are Taylor’s polynomial linearization approximation, the method of variable change, and a modification of the method of variable change. Nahar and Alim (2017) suggested a statistical average approach where a single-objective function is developed from multi-objective functions to optimize the objective function, compared the proposed technique with some other techniques, such as arithmetic averaging and geometric averaging, and showed the effectiveness of the approach. Bhati et al. (2017) presented a review of the MOFP problems excluding various technical parts of fractional programming. In the review, the MOFP problems are classified into two classes: general MOFP problems and MOLFP problems. Then, these classes were sub-classified based on the basis of the proposed algorithm and optimality criteria [9] [10] .

Sulaiman and Sadiq (2006) used mean and median to study the multi-objective function (MOF) by solving multi-objective programming problem (MOLPP). Hamad-Amin (2008) used arithmetic mean to study MOLPP. Sulaiman and Mustafa (2016) transformed the MOLPP to the single objective linear programming problem using harmonic mean for values of functions. A popular technique named as Chandra Sen’s technique has been used to solve the multi-objective linear fractional programming problem (MOLFPP) by Chandra Sen (1983). To solve these problems, there are several methods which were discussed by Abdil-Kadir and Sulaiman (1993). Nahar and Alim (2017) proposed a new geometric average technique to solve MOLFPP. The paper published by Sing (1981) shows a useful study about the optimality condition in fractional programming. Sulaiman and Othman (2007) conducted a study on MOLFPP. Nahar and Alim (2017) used different methods such as Chandra sen’s approach, statistical averaging method and new statistical averaging method to solve MOLPP. It is found that harmonic averaging gives better result than rest in these two methods [11] [12] .

In this paper, a new averaging method is applied for both MOLPP and MOLFPP which is taken the maximum value among optimized values for each objective function using simplex algorithm. In both problems, they show the same characteristics.

2. An Example for MOLFPP

Consider the following multi-objective linear fractional programming problems [3] ,

$\begin{array}{l}\max z_1=\frac{3x_1-2x_2}{x_1+x_2+1}\\ \max z_2=\frac{9x_1+3x_2}{x_1+x_2+1}\\ \max z_3=\frac{3x_1-5x_2}{2x_1+2x_2+2}\\ \min z_4=\frac{-6x_1+2x_2}{2x_1+2x_2+2}\\ \min z_5=\frac{-3x_1-x_2}{x_1+x_2+1}\end{array}$ s/t $\begin{array}{l}{x}_1+x_2\le 2\\ 9x_1+x_2\le 9\\ x_1,x_2\ge 0\end{array}$ (1)

The optimal values of the objective functions with same constraints by using modified simplex method [3] , are (Table 1):

Taking maximum among optimal values from the above last two columns;

Let the maximum values be m₁ = 4.5 and m₂ = 1.5.

2.1. New Arithmetic Averaging Technique (Table 2)

Applying new arithmetic averaging between m₁ and m₂

$\frac{m_1+m_2}{2}=3$

To generate a single objective function from multi-objective functions [3] ,

Table 1. Optimal values of objective functions.

Table 2. Simplex table.

$\max z=\left({\displaystyle \underset{i=1}{\overset{r}{\sum }}{z}_i}-{\displaystyle \underset{i=r+1}{\overset{s}{\sum }}{z}_i}\right)/A.Av=\frac{39x_1-3x_2}{3\times 2\left(x_1+x_2+1\right)}=\frac{6.5x_1-0.5x_2}{x_1+x_2+1}$

Thus the new problem becomes

$\max z=\frac{6.5x_1-0.5x_2}{x_1+x_2+1}$ $\text{s/t}$ $\begin{array}{l}{x}_1+x_2\le 2\\ 9x_1+x_2\le 9\\ x_1,x_2\ge 0\end{array}$

Applying modified simplex method [5] ,

$c=\left(6.5,-0.5\right),d=\left(1,1\right),\alpha =0,\beta =1,A_1=\left(1,1\right),A_2=\left(9,1\right),\text{}{b}_1=2,b_2=9$

$\max H\left(y\right)=\left[Iy\right]+j=\frac{c\beta -d\alpha }{\beta }\left[y\right]+0=\left(6.5,-0.5\right)\cdot \left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]=6.5y_1-0.5y_2$

For first constraint,

$K_1=\left(1,1\right)\cdot 1+2\left(1,1\right)=\left(1,1\right)+\left(2,2\right)=\left(3,3\right)$

$Ky\le L\Rightarrow \left(3,3\right)\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)\le 2\Rightarrow 3y_1+3y_2\le 2$

For second constraint,

$K_2=\left(9,1\right)\cdot 1+9\left(1,1\right)=\left(9,1\right)+\left(9,9\right)=\left(18,10\right)$

$Ky\le L\Rightarrow \left(18,10\right)\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)\le 9\Rightarrow 18y_1+10y_2\le 9$

Thus

$\begin{array}{l}\max H\left(y\right)=6.5y_1-0.5y_2\\ \text{s/t}3y_1+3y_2\le 2\\ 18y_1+10y_2\le 9\\ y_1,y_2\ge 0\end{array}$ $\iff$ $\begin{array}{l}\max H=6.5y_1-0.5y_2\\ \text{s/t}3y_1+3y_2+s_1=2\\ 18y_1+10y_2+s_2=9\\ \text{where}{y}_1,y_2,s_1,s_2\ge 0\end{array}$

Thus

$y_1=1/2,y_2=0$

Now

$\left(x_1,x_2\right)=\frac{\left(y_1,y_2\right)\beta }{1-d\left(y_1,y_2\right)}=\frac{\left(1/2,0\right).1}{1-\left(1,1\right)\left(1/2,0\right)}=\frac{\left(1/2,0\right)}{1-1/2}=\frac{\left(1/2,0\right)}{1/2}=\left(1,0\right)$

Thus max Z = 3.25 with x₁ = 1, x₂ = 0.

2.2. New Geometric Average Technique

Applying new geometric averaging between m₁ and m₂.

For m₁ = 4.5, m₂ = 1.5; So $G.Av=\sqrt{4.5\times 1.5}=2.598$ .

To generate a single objective function from multi-objective functions [3] ,

$\begin{array}{c}\max z=\left({\displaystyle \underset{i=1}{\overset{r}{\sum }}{z}_i}-{\displaystyle \underset{i=r+1}{\overset{s}{\sum }}{z}_i}\right)/G.Av=\frac{39x_1-3x_2}{2\times 2.598\left(x_1+x_2+1\right)}\\ =\frac{39x_1-3x_2}{5.196\left(x_1+x_2+1\right)}=\frac{7.506x_1-0.577x_2}{x_1+x_2+1}\end{array}$

Thus

$\max z=\frac{7.506x_1-0.5777x_2}{x_1+x_2+1}$ s/t $\begin{array}{l}{x}_1+x_2\le 2\\ 9x_1+x_2\le 9\\ x_1,x_2\ge 0\end{array}$

Applying modified simplex method [5] ,

$c=\left(7.5,-0.58\right),d=\left(1,1\right),\alpha =0,\beta =1,A_1=\left(1,1\right),A_2=\left(9,1\right),\text{}{b}_1=2,b_2=9$

$\begin{array}{c}\max H\left(y\right)=\left[Iy\right]+j=\frac{c\beta -d\alpha }{\beta }\left[y\right]+0=\left(7.506,-0.577\right)\cdot \left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]\\ =7.506y_1-0.577y_2\end{array}$

For first constraint,

$K_1=\left(1,1\right)\cdot 1+2\left(1,1\right)=\left(1,1\right)+\left(2,2\right)=\left(3,3\right)$

$Ky\le L\Rightarrow \left(3,3\right)\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)\le 2\Rightarrow 3y_1+3y_2\le 2$

For second constraint,

$K_2=\left(9,1\right)\cdot 1+9\left(1,1\right)=\left(9,1\right)+\left(9,9\right)=\left(18,10\right)$

$Ky\le L\Rightarrow \left(18,10\right)\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)\le 9\Rightarrow 18y_1+10y_2\le 9$

Thus (Table 3)

$\begin{array}{l}\max H\left(y\right)=7.5y_1-0.58y_2\\ \text{s/t}3y_1+3y_2\le 2\\ 18y_1+10y_2\le 9\\ y_1,y_2\ge 0\end{array}$ $\iff$ $\begin{array}{l}\max H=7.5y_1-0.58y_2\\ \text{s/t}3y_1+3y_2+s_1=2\\ 18y_1+10y_2+s_2=9\\ \text{where}{y}_1,y_2,s_1,s_2\ge 0\end{array}$

Thus

$y_1=1/2,y_2=0$

Now

Table 3. Simplex table.

$\left(x_1,x_2\right)=\frac{\left(y_1,y_2\right)\beta }{1-d\left(y_1,y_2\right)}=\frac{\left(1/2,0\right)\cdot 1}{1-\left(1,1\right)\left(1/2,0\right)}=\frac{\left(1/2,0\right)}{1-1/2}=\frac{\left(1/2,0\right)}{1/2}=\left(1,0\right)$

Thus max Z = 3.753 with x₁ = 1, x₂ = 0 (Table 4).

3. An Example for MOLPP

Consider the following multi-objective linear fractional programming problems.

Multi-objective functions:

$\max z_1=x_1+2x_2$

$\max z_2=x_1$

$\min z_3=-2x_1-3x_2$

$\min z_4=-x_2$

Subject to

$6x_1+8x_2\le 48$

$x_1+x_2\ge 3$ (2)

$x_1\le 4$

$x_2\le 3$

$x_1,x_2\ge 0$

The optimal values of the objective functions with same constraints by using simplex method [3] , are (Table 5):

Taking maximum among optimal values from the above last two columns;

Let the maximum values be m₁ = 10, m₂ = 17.

3.1. New Arithmetic Averaging Technique

Applying new arithmetic averaging between m₁ and m₂

$\frac{m_1+m_2}{2}=13.5$

Table 4. Comparison table.

Table 5. Optimal values of given objective functions.

To generate a single objective function from multi-objective functions [3] ,

$\begin{array}{c}\max z=\left({\displaystyle \underset{i=1}{\overset{r}{\sum }}{z}_i}-{\displaystyle \underset{i=r+1}{\overset{s}{\sum }}{z}_i}\right)/A.Av\\ =\frac{1}{13.5}\left[4x_1+6x_2\right]\\ =0.296x_1+0.444x_2\end{array}$

Thus the problem becomes

$\max Z=0.296x_1+0.444x_2$

Subject to

$6x_1+8x_2\le 48$

$-x_1-x_2\le -3$

$x_1\le 4$

$x_2\le 3$

$x_1,x_2\ge 0$

Using slack variables, the problem can be written as

$\max Z=0.296x_1+0.444x_2$

Subject to

$6x_1+8x_2+s_1=48$

$-x_1-x_2+s_2=-3$

$x_1+s_3=4$

$x_2+s_4=3$

$s_1,s_2,s_3,s_4,x_1,x_2\ge 0$

Thus the optimal solution from Table 6 is $x_1=4$ , $x_2=3$ and $z_{\max }=2.516$ .

Table 6. Simplex table.

3.2. New Geometric Averaging Technique

Applying new geometric averaging between m₁ and m₂,

$\sqrt{m_1{m}_2}=13.038$

To generate a single objective function from multi-objective functions [3] ,

$\begin{array}{c}\max z=\left({\displaystyle \underset{i=1}{\overset{r}{\sum }}{z}_i}-{\displaystyle \underset{i=r+1}{\overset{s}{\sum }}{z}_i}\right)/G.Av\\ =\frac{1}{13.038}\left[4x_1+6x_2\right]\\ =0.307x_1+0.4602x_2\end{array}$

Thus the problem becomes

$\max Z=0.307x_1+0.4602x_2$

Subject to

$6x_1+8x_2\le 48$

$-x_1-x_2\le -3$

$x_1\le 4$

$x_2\le 3$

$x_1,x_2\ge 0$

Table 7. Simplex table.

Table 8. Comparison table.

Using slack variables, the problem can be written as

$\max Z=0.307x_1+0.4602x_2$

Subject to

$6x_1+8x_2+s_1=48$

$-x_1-x_2+s_2=-3$

$x_1+s_3=4$

$x_2+s_4=3$

$s_1,s_2,s_3,s_4,x_1,x_2\ge 0$

Thus the optimal solution from Table 7 is $x_1=4$ , $x_2=3$ and $z_{\max }=2.6086$ .

4. Conclusion

In both MOLFPP and MOLPP, geometric averaging gives better result than arithmetic averaging. Difference between these results in MOLFPP and MOLPP is same while taking minimum and maximum among optimized values for each objective function. It is proved that, the results while taking minimum are similar to the results while taking maximum (Table 8).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Abdil-Kadir, M.S. and Sulaiman, N.A. (1993) An Approach for Multi Objective Fractional Programming Problem. Journal of the College of Education, 3, 1-5.
[2]	Hamad-Amin, A.O. (2008) An Adaptive Arithmetic Average Transformation Technique for Solving MOLPP. MSc. Thesis, University of Koya, Koya.
[3]	Nahar, S. and Alim, M.A. (2017) A New Geometric Average Technique to Solve Multi-Objective Linear Fractional Programming Problem and Comparison with New Arithmetic Average Technique. IOSR Journal of Mathematics, 13, 39-52. https://doi.org/10.9790/5728-1303013952
[4]	Nahar, S. and Alim, M.A. (2017) A New Statistical Averaging Method to Solve Multi-Objective Linear Programming Problem. International Journal of Science and Research, 6, 623-629.
[5]	Saha, S.K., Hossain, M.R., Uddin, M.K. and Mondal, R.N. (2015) A New Approach of Solving Linear Fractional Programming Problem (LFP) by Using Computer Algorithm. Open Journal of Optimization, 4, 74-86. https://doi.org/10.4236/ojop.2015.43010
[6]	Sen, C. (1983) A New Approach for Multi Objective Rural Development Planning. The Indian Economic Journal, 30, 91-96.
[7]	Sing, H.C. (1981) Optimality Condition in Functional Programming. Journal of Optimization Theory and Application, 33, 287-294. https://doi.org/10.1007/BF00935552
[8]	Sulaiman, N.A. and Mustafa, R.B. (2016) Using Harmonic Mean to Solve Multi-Objective Linear Programming Problems. American Journal of Operations Research, 6, 25-30. https://doi.org/10.4236/ajor.2016.61004
[9]	Sulaiman, N.A. and Othman, A.Q. (2007) Optimal Transformation Technique to Solve Multi-Objective Linear Programming Problem. Journal of University of Kirkuk, 2, 122-131.
[10]	Sulaiman, N.A. and Sadiq, G.W. (2006) Solving the Linear Multi-Objective Programming Problems; Using Mean and Median Value. Al-Rafiden Journal of Computer Sciences and Mathematics, 3, 69-83. https://doi.org/10.33899/csmj.2006.164037
[11]	Lotfi, F., Noora, A., Jahanshahloo, G., Khodabakhshi, M. and Payan, A. (2010) A Linear Programming Approach to Test Efficiency in Multi-Objective Linear Fractional Programming Problems. Applied Mathematical Modelling, 34, 4179-4183. https://doi.org/10.1016/j.apm.2010.04.015
[12]	Porchelvi, R., Vasanthi, L. and Hepzibah, R. (2014) On Solving Multi-Objective Fractional Linear Programming Problems. International Journal of Current Research, 6, 8095-8102.