Using Harmonic Mean to Solve Multi-Objective Linear Programming Problems

Show more

Received 11 November 2015; accepted 15 January 2016; published 20 January 2016

1. Introduction

Linear programming is a relatively new mathematical discipline, dating from the invention of the simplex method by G. B. Dantzig in 1947. He proposed the simplex algorithm as an efficient method to solve a linear programming problem.

A multi-objective linear programming problem is introduced by Chandra Sen [1] and suggests an approach to construct the multi-objective function under the limitation that the optimum value of individual problem was greater than zero. [2] studied the multi-objective function by solving the multi-objective programming problem, using mean and mean value. [3] solved the multi objective fractional programming problem by Chandra Sen’s technique. In order to extend this work, we have defined a multi-objective linear programming problem and investigated the algorithm to solve linear programming problem for multi-objective functions. By new technique, we use harmonic mean (HM) of the values of objective functions. The computer application of our algorithm has also been discussed by solving some numerical examples. Finally we have showed results and comparison among the new technique and Chandra Sen’s approach [1] and Sulaiman’s approach [2] .

2. Mathematical Definition of Multi-Objective Programming Problems (MOPP)

A deterministic (MOPP) model is usually formulated to maximize and/or minimize several objectives simultaneously subject to a constraint set with “≥” and/or “≤” relationships the equality constraints may be expressed as a combination of both of inequality constraints.

Mathematically, the MOPP problems can be defined as:

(1.1)

subject to:

(1.2)

(1.3)

where x is an n-dimensional vector of decision variables c is n-dimensional vector of constants, B is m-dimen- sional vector of constants, r is the number of objective function to be maximized, s the number of objective function to maximized plus minimized, is the number of objective that is to be minimized, A is a matrix of coefficients all vectors are assumed to be column vectors unless transposed, are scalar constants, are linear factors for all feasible solutions [3] .

If; for all, then the mathematical form become:

(2.1)

subject to:

(2.2)

(2.3)

The problem said to be multi-objective linear programming problem (MOLPP) if all the objective functions and constraint functions are linear, and all the variables are continuous variables.

3. The New Technique for Solving MOLPP by Using Harmonic Mean

Before solving MOLPP, and preface an algorithm to it, we will need to define Harmonic Mean.

Harmonic Mean [4]

Harmonic mean of a set of observations is defined as the reciprocal of the arithmetic average of the reciprocal of the given values. If are n observations,

4. Multi-Objective Functions Formulation

Suppose we optimize (maximize or minimize) all the objective functions individually in (2.1), (2.2) and (2.3) and obtain the values as follows.

(3.1)

where are the values of objective functions.

We require the common set of decision variable to be the best compromising optimal solution [5] . Here we can determine the common set of decision variables from the following combined objective function.

Formulate the multi-objective linear programming problem given in (1.1) can be translated by our technique to:

(3.2)

where

(3.3)

And; subject to the same constraints (1.2), (1.3) and the optimum value of the functions may be positive or negative, the value of harmonic mean of maximized and the value of harmonic mean of minimized., if then the combined formula (3.2) becomes.

If then the function. We can solve this (MOLPP) by Chandra Sen’s approach [1] -[3] by using mean and median and algorithms in above researches for solving MOLPP as explained in [1] - [3] .

4.1. Algorithm

This algorithm is to obtain the optimal solution for the MOLPP defined previously can be summarized as follows.

Step 1: Assign arbitrary values to each of the individual objective functions that to be maximized and minimized.

Step 2: Solve the first objective function { subject to constraints (1.2) and (1.3)} by simplex method.

Step 3: Check the feasibility of the solution in step 2, if it is feasible then go to step 4, otherwise, use dual simplex method to remove infeasibility.

Step 4: Assign a name to the optimum value of the first objective function f1 say

Step 5: Repeat step 2, for for the kth objective function, for all

Step 6: Determine Harmonic Mean Hm1 for and for

Step 7: Optimize the combined objective function under the same constraints (1.2) and (1.3) by repeating Steps 2-4.

4.2. Used Notation

The following notations were used in our algorithm:

where = The value of objective function which is to be maximized, and

= The value of objective function which is to be minimized.

= The value of Harmonic mean of maximized.

= The value of Harmonic mean of minimized.

4.3. Numerical Examples

Ex. (1)

(4.1)

s.to:

(4.2)

Solution:

After finding the value of each of individual objective function by simplex method the results as below in (Table 1): by using Harmonic Mean technique (3.3) we get and

After that using equation (3.2) for transform we get:

(4.3)

Solving (4.3) by simplex method we get:

Solve (4.1) by:

1. Using Chandra Sen’s approach, [1] : after convert the MOLPP to the single objective problem we get subject to the same constraints (4.2) by simplex method it is optimal solution.

Table 1. Results of example (1).

2. Using modified approach, [2] :

A-using Mean: after convert the MOLPP to the single objective problem we get subject to the same constraints (4.2) by simplex method it is optimal solution

B-using Median: after convert the MOLPP to the single objective problem we get subject to the same constraints (4.2) by simplex method it is optimal solution.

Ex. (2)

(5.1)

Subject to:

(5.2)

Solution:

After finding the value of each of individual objective function by simplex method the results as below in (Table 2): by using Harmonic Mean technique (3.3) we get and.

After that using equation (3.2) for transform we get:-

(5.3)

Solving (5.3) by simplex method we get:

Solve (5.1) by:

1. using Chandra Sen approach, [1] : after convert the MOLPP to the single objective problem we get subject to the same constraints (5.2) by simplex method it is optimal solution.

2. using modified approach, [2] :

A-using Mean: after convert the MOLPP to the single objective problem we get subject to the same constraints (5.2) by simplex method it is optimal solution.

B-using Median: after convert the MOLPP to the single objective problem we get

Table 2. Results of example (2).

Table 3. Comparison between results obtained by different numerical approaches.

subject to the same constraints (6.2) by simplex method it is optimal solution.

5. Conclusions

Our aim was to develop an approach for solving multi-objective programming problem (MOLPP) and to suggest a new algorithm to convert the MOLPP into a single LPP by using harmonic mean of the values of objective functions and its computer application by using programming mathematical language (Matlab Programming). Moreover, we used different methods to solve the problems, and applied our technique and the other methods to the same examples in order to compare the results.

From this comparison, we observed that our technique gave identical results with that obtained by the other methods, for this see Table 3. So we conclude that this method is better than other methods considered in solving MOLP problems.

NOTES

^{*}Corresponding author.

References

[1] Chandra, S. (1983) A New Approach Objective Planning. The Indian Economic Journal, 30, 91-96.

[2] Sulaiman, N.A. and Sadiq Gulnar, W. (2006) Solving the Multi-Objective Programming Problem; Using Mean and Median Value. Ref. J of Comp & Math’s, 3.

[3] Abdul-Kadir, M.S. and Sulaiman, N.A. (1993) An Approach for Multi-Objective Fractional Programming Problem. Journal of College of Education, University of Salahaddin, 3, 1-5.

[4] Jothikumar, J. (2004) STATISTICS. 60 G.S.M Paper, p.100.

[5] Azapagic, A. and Clift, R. (1999) Life Cycle Assessment and Multi Objective Optimization. Journal of Cleaner Production, 7, 135-143.

http://dx.doi.org/10.1016/S0959-6526(98)00051-1