The Modified Sequential Linear Goal Programming Method for Solving Multiple Objectives Linear Programming Problems
Geleta Tadele Mohammed, Birhanu Guta Hordofa
Department of Mathematics, Addis Ababa University, College of Computational and Natural Science, School of Graduate Studies, Addis Ababa, Ethiopia
Email address:
To cite this article:
Geleta Tadele Mohammed, Birhanu Guta Hordofa. The Modified Sequential Linear Goal Programming Method for Solving Multiple Objectives Linear Programming Problems. Pure and Applied Mathematics Journal. Vol. 5, No. 1, 2016, pp. 1-8. doi: 10.11648/j.pamj.20160501.11
Abstract: Most of real world decision making problems have multiple objectives, which cannot be optimized simultaneously due to the conflicting nature of the objectives. Such problems can be solved by various methods to obtain the best-compromise solutions. Modified Sequential Linear Goal Programming (MSLGP) method can be used to solve Multiple Objective Linear programming Problems. In this paper, the use of existing single objective Linear Programming (LP) techniques is there, and the information required for MSLGP in each iteration are taken from the previous iteration. In this study, there is a great Revised Multi-phase Simplex Algorithm, which is used to solve MSLGP Accordingly within small number of computations as much as possible. This method is illustrated by some numerical examples, and provides ‘best compromise’ solution.
Keywords: Multiple Objectives Linear Programming, Modified Sequential Linear Goal Programming, Revised Multi-Phase Simplex Algorithm for MSLGP Algorithm
1. Introduction
A real world decision making problems arise in management and engineering often involve multiple and conflicting objectives. Such decision making problems can be generally modeled as multiple objective optimization problems. The rapid development of Multiple Criteria Decision Making (MCDM) has led to an enormous diversity of models and methods. A number of methodologies have been developed to address the problem of multiple objectives. Goal Programming (GP) is an important technique for decision-makers (DM) to solve Multi-Objective Decision Making (MODM) problems in finding a set of satisfying solutions. And also GP is the extension of LP that permits more than one objective to be stated. It was first introduced by Charnes and Cooper [1] and further developed by Lee [6], Ignizio [4], Tamiz et al. [10] and Romero [8]. Ignizion [3], Romero et al. [7], established a framework that can lead to a better understanding and presentation of the different MCDM approaches. At first, Ignizio developed under the name of MULTIPLEX, a unified structure encompassing the optimization methods such as: lexicographic vector minimization, Archimedean GP, lexicographic GP, and MINIMAX (Chebyshev) GP.
The GP (goal programming) model is one in which all objectives are converted into goals. This conversion is accomplished by an ‘aspiration level’ to the right hand side of each objective. Then one seeks the solution that minimizes the distances between that solution and the aspired solution. This fundamental idea leads to the following analytical framework. The general structure of the goal can be expressed as:
, i = 1, 2, . . . ,, where = total number of goals.
: The mathematical expression for the attribute (i.e., a linear function of decision vector.)
: The target value for the goal .
: The negative deviational variable, i.e., quantification of the under achievement of goal.
: The positive deviational variable, i.e., quantification of the over achievement of goal After the formulation of all K number of goals, the next aim is to detect the unwanted deviation variables. The variables are unwanted in the sense that these are the variables that DM (decision maker) wants to minimize. To illustrate this procedure the following cases are presented:
1. Let us consider , as Case I where goal is attached to a maximization type objective. In this case the DM does not want under achievement with respect to target. consequently, the unwanted deviational variable to be minimized.
2. Let us consider , as Case II where goal is attached to a minimization type objective. In this case the DM does not want over achievement with respect to target .Consequently, the unwanted deviational variable to be minimized.
3. Let us consider , as Case III where goal is to be achieved exactly. In this case the neither wants over-achievement nor under-achievement with respect to target. Hence both the negative deviational variable and positive deviational variable are equally unwanted, making it necessary to minimize .
The purpose of GP is to minimize the deviations between the achievement of goals and their aspiration levels. The minimization process can be accomplished with different GP variant. Basically, there are only three GP variants reported in literature. The most widely used is Lexicographic Goal Programming (LGP), which attaches preemptive priorities to the different goals in order to minimize the unwanted deviation variables in a lexicographic order. The second one is Weighted Goal Programming (WGP), which attempts to minimize a composite objective function formed by a weighted sum of unwanted deviation variables. The third is MINIMAX (Chebyshev) Goal Programming, which attempts to minimize the maximum deviation from stated goals. An extensive survey [9] shows that around 75% of the applications reported use the LPG option, 20% the WGP one and only 5% the MINI- MAX (Chebyshev) option. The basic approach to the solution of the linear goal programming model with an achievement function is to be lexicographically minimized. That is, we shall be working within a preemptive priority structure or Lexicographic Linear Goal programming within a preemptive priority structure has been one of the most widely used techniques considered in solving multiple objective problems. There are three different methods for solving goal programming problem.
They are the following:
• Graphical method (Applied to two variables).
• Sequential goal programming method.
• Multi-phase simplex method.
Our main purpose is to illustrate the modified Sequential goal programming method. A quite different approach to the solution of the Lexicographic Linear Goal Programming (LLGP) model was developed in 1967 by Ignizio [5]. This approach, denoted as Sequential Linear Goal Programming (SLGP), was based on the observation by Paul Huss that one could solve an LLGP model via a sequence of conventional LP models. Based upon the solution of the previous LP, an ’augmented constraint’ is added to the subsequent models. The purpose of this augmented constraint is to assure that all solutions to the subsequent LP models do not degrade those solutions previously obtained for higher priority goals, (See [2], [3]).The paper is organized as follows: Section 2 contains multi-objective linear programming model, which is then converted to its corresponding goal programming model. In Section 3 MSLGP algorithm is given, and in section 4 we have the suitable simplex Algorithm for the algorithm in section 3. And also a few numerical examples are provided in section 5 to justify the methodology.
2. Multiple Objectives Linear Programming Model [11]
In real life, virtually all problems have several objectives, not just one. For example, if a manufacturing company concentrates only on cost containment, it might neglect the environmental or social concerns of the society it serves. If a health care company concentrates only on top quality health care, its owners’ profit could be inconsiderable. If a publishing Company puts too much emphasis on developing an error free textbook, the amount of time spent reviewing a potential text might push the publishing date beyond that required for adoptions. In short, finding optimal solution to a model formulated with a single objective can seriously affect other aspirations and goals that are important to an organization. A goal programming model seeks to simultaneously take into account several objectives or goals that are of concern to a decision maker. While a linear programming model consists of constraints and single objective function to be maximized or minimized, a goal programming model consists of constraints and a set of goals that are prioritized in some sense. In both linear and goal programming problems, if the constraints are inconsistent, there are no feasible solutions for the model. In goal programming, however, one can expect that although there is a set of feasible solutions satisfying the constraints, none of them may simultaneously satisfy all the conflicting goals of the organization. The objective of goal programming is to find a solution that satisfies the true constraints and comes closest to meeting the stated goals. Goal programming approaches analyze how much a proposed solution deviates from each stated goal. Accordingly, for each goal a pair of deviation variables is defined (one equaling the amount by which the solution over-achieves the goal; the other equaling the amount by which it fails to meet the goal).
The basic approach of goal programming is to establish a specific numeric goal for each of the objectives, formulate an objective function for each objective, and then seek a solution that minimizes the (weighted) sum of deviations of these objective functions from their respective goals.
Goal programming problems can be categorized according to the type of mathematical programming model (linear programming, integer programming, nonlinear programming, etc.) that it fits except for having multiple goals instead of a single objective.
Another categorization is according to how the goals compare in importance. In one case, called non-preemptive goal programming, all the goals are of roughly comparable importance. In another case, called preemptive goal programming, there is a hierarchy of priority levels for the goals, so that the goals of primary importance receive first priority attention, those of secondary importance receive second-priority attention, and so forth (if there are more than two priority levels).In this report goal refers to a criterion and a numerical level, known as a target level which the decision maker(s) desire to achieve on that criterion, where, a criterion is a single measure by which the goodness of any solution to a decision problem can be measured, and also the decision maker(s) refers to the person(s), organization(s), or stakeholder(s) to whom the decision problem under consideration belongs. Instead of trying to optimize all of the objectives, we set goals for the objective values, and try to meet these goals instead. And also, this report, we only consider preemptive linear goal programming.
Consider the situation in which the set of feasible decisions and set of K criteria (we assume that there are at least two criteria) for evaluating the decisions can be described in the form of the maximization of K linear objective functions subject to m linear constraints. Formally, a Multiple Objective Linear Programming Model (MOLPM) can be described as: Find , so as to
(2.1)
Subject to
(2.2)
(2.3)
Now, a general linear goal programming model for the above multi-objective linear programming model is:
Find , so as to
(2.4)
(2.5)
(2.6)
(2.7)
(2.8)
Where is the number of priorities in the achievement function A. The achievement function A is an ordered vector of priority levels, each containing at least one unwanted deviational variable.
3. Modified Sequential Linear Goal Programming (MSLGP) Algorithm [11]
Step 1. Set k = 1 (where k is used to represent the priority level under consideration and P is the total number of priorities).
Step 2. Establish the mathematical model for priority level 1(P 1) only. That is,
Lexicographically)
Subject to , ∈ p1
, j=1: m
, η ≥ 0, ρ≥ 0,
The resultant problem is simply a single-objective linear programming problem and may be solved by simplex method.
Step 3. Solve the single-objective problem associated with the priority level k via simplex algorithm. (Before solving the problem expresses the basic variables in terms of non-basic variables if it is there in a goal). Let the optimal solution to this problem be given as a∗, where a∗ is the optimal value of gk (η, ρ).
Step 4. Set k = k + 1. If k > P, go to Step 7.
Step 5. Establish the equivalent, single-objective model for the next priority level (P k). This model is given by:
Lexicographically min:
subject to +−=
, η ≥ 0, ρ≥ 0,
where s = 1, ..., k − 1, t = set of subscripts associated with those ‘goals ‘or constraints included in priority levels 1, 2, ..., k.
Step 6. Express the basic variables in terms of non-basic variables if it is there in a goal. Go to Step 3
Step 7. The solution vector x^{∗} associated with the last single-objective model solved, is the optimal vector for the original goal programming model.
This is an algorithm used to solve multiple objective linear programming problems when there is a priority among the objectives. That is, if there is an order such that one goal is more important than the other and next to this goal if there is another goal which is more important than the rest of the other. In such away if all goals are ordered one can use modified sequential linear goal programming algorithm to solve multiple objective linear programming problems. There are several short methods which may be used to reduce the computational procedures. The simplex method we use in this report for this MSLGP algorithm is stated in the next page.
4. Revised Multi-phase Simplex Algorithm for MSLGP Algorithm
To solve the problem
Find , so as to
Lexicographicall min:
Subject to
Where is the number of priorities in the achievement function. We have the following corresponding simplex algorithm:
Step 1: Set and have an initial simplex table for the problem under step 2 of MSLGP algorithm in format of the following, where the corresponding spaces of are empty.
Then, got to step 2.
Step 2: Compute for all non-basic variables. Then go to step 3.
Step 3: Optimality condition
If all for all non-basic variables, then the current table is optimal table. Then go to Step 4. Otherwise go to step 5
Step 4:
Set . If , the drop all columns with < 0 from the optimal table of iteration and express basic variables in terms of non-basic variable from the optimal table of iteration if it there in a goal. Then add this constraint correspondingly in the bottom of optimal table of iteration after the removal of all columns with < 0.
Then go to step 2. Otherwise, the current optimal solution is the optimal solution for the original problem of MSLGP algorithm.
Step 5: Select Entering Variable
The entering variable is the non-basic variable with the most positive . Then by having this at hand go to step 6.
Step 6: Determine Leaving Variable
The leaving variable is determined as usual in primal simplex algorithm by minimum ratio test, and all condition like unboundedness is the same as in that of simplex method. Then if it is bounded go to step 7.
Step 7:
Since from step 6 we have that pivot element say and pivot column, then do the pivot operations we have in usual simplex method .Then rename this table by table before. Multiply the elements pivot column of table we have obtained from step 6 by - the pivot element, and also replace the pivot element of this pivot column by except Then replace this pivot column to the table before, and rename this table to be table after. This table is final table of this step. Then by having this final table at hand go to step 3.
♣ Note that this algorithm is almost the integration of simplex algorithm and Modified sequential linear Goal Programming (MSLGP) algorithm.
5. Some Explanatory Numerical Examples
Example 1. [12] A firm produces two products, namely product A and product B. Product A has a net return of $10 per unit and product B returns $8 per unit produced. Total assembly time is 120 hours per week, but some overtime is possible. If product A and B are produced on over time it takes 3 and 2 hours respectively. However, if overtime is utilized, the net return on both products is reduced by $1 per unit produced on overtime. Under a present contract, the firm must supply the customer with minimum of 30 units per week of both products. Based on conversations with the owners, we establish the following:
(i) The contract to the customer must be satisfied and only 120 hours of regular time is available.
(ii) Overtime is to be minimized. (iii) Profit is to be maximized.
Let
: Number of units of product A produced, per week, on regular time,
: Number of units of product A produced, per week, on overtime,
: Number of units of product B produced, per week, on regular time,
: Number of units of product B produced, per week, on overtime.
Then the base line model can be written as
Subject to
(5.1)
(5.2)
(5.3)
(5.4)
(5.5)
(5.6)
In this model, equation (4.2) is due to reduction of return by $1 per unit produced on over time.
Equation (4.3), (4.4) are for on regular and over time of product A and B respectively.
The management observes that comparative profit increases with increase in overtime up to certain limit, but after the limit the comparative profit decreases with increase in over time. Therefore it wishes to hold overtime less than 20 hours per week and the profit is to be $800 per week. Given that the contracts must be satisfied with the minimization overtime ranked higher than the maximization of profit. Then the resultant lexicographic linear goal programming having five goals, three priority levels and four decision variables can be Represented as
(5.7)
(5.8)
(5.9)
(5.10)
(5.11)
(5.12)
(5.13)
(5.14)
In equation (4.7) a1 = η1 + η2 + ρ3 come from:
Since we went to maximize the number of products A and B, then we do not want under achievement in , + 30, and in we do not need over achievement. So we minimize a1 = η1 + η2 + ρ3.
In equation (4.7), comes from:
Since equation (4.1) is minimizing over time, so, we do not need over achievement. Hence, we minimize ρ4.
In equation (4.7), comes from:
Since equation (4.2) is maximizing profit, so, we do not need under achievement. Hence, we minimize .
From Step 1 and step 2 of the MSLGP algorithm, we have that
Min:
Subject to
Now also from Step 3 of the MSLGP algorithm and the corresponding simplex algorithm, we have the following simplex tableau:
Note: In this paper of all tables, the last row is. In this row the most positive Indicates the entering variable and as usual simplex method minimum ratio test is used to determine leaving variable. To understand this algorithm knowing the optimality conditions of sequential linear goal programming algorithm is necessary.
We obtain Table 3 as an optimal simplex tableau. Since the indicator row elements below the column , and are negative, these three columns may be dropped from the tables.
From Step 4 and Step 5 of MSLGP algorithm, we that
Then we express basic variable in terms of non-basic variables. From the above Table we obtain
Now by using goal 4
Then we solve the problem using step 3 of MSLGP algorithm as follows:
The obtained simplex table is optimal. Since the indicator row elements below the column η_{3}, η_{4}, ρ_{1} and ρ_{2} are negative; these columns may be dropped from the table. Using Step 4 and Step 5 of MSLGP algorithm, we establish
Lexicographically min: a_{3} =η_{5}
From the above table we have that
Now by using goal 5 we obtain
Then according to the MSLGP algorithm we solve the problem using step 3 of MSLGP
Algorithm as follows:
From step 3 of MSLGP algorithm the obtained solution is the following:
Where the value of the achievement function is A= (0, 10, 270).
Example 2. [11] Consider the following problem which involves five goals, three priority levels and two decision variables.
(5.15)
(5.16)
(5.17)
(5.18)
(5.19)
(5.20)
(5.21)
(5.22)
From step 1 and step 2 of MSLGP algorithm, we have that
And also from step 3 of the MSLGP algorithm, we have the following simplex tableau (Table 1-Table 2):
We obtain Table 2 as an optimal simplex tableau. Since the indicator row elements below the column η2, η3, ρ1, ρ2 and ρ3 are negative; these columns may be dropped from the table. From Step 4 and Step 5 of MSLGP algorithm, we obtain
Lexicographically min
Subject to (4.15) − (4.19)
Then we express basic variables in terms of non-basic variables if it is there in the goal. Using the goal (4)
We obtain
ρ4 − η4 = 2
Then we solve the problem by using step 3 of MSLGP algorithm as follows:
The obtained simplex table is optimal. Since the indicator row below η4 is negative, this Column may be dropped from the table. Using Step 4 and Step 5 of MSLGP algorithm, we establish
Lexicographically min:
Subject to (4.15) − (4.20)
Then we express basic variable in terms of non-basic variables if it is there in the goal. Using the goal (5)
We obtain
Then we solve the resultant problem by using step 3 of MSLGP algorithm as follows:
From Step 3 0f MSLGP algorithm the obtained solution is the following: .
Where the value of achievement function is (0, 2, 3) =A.
Note that, this paper is a joint of the two journals cited at bibliography of this paper of number 11 and 12. In general, I have a great thanks to both authors of these two journals especially.
6. Conclusions
The MSLGP algorithm uses a series of conventional LP models. This is accomplished by partitioning the GP model according to priority levels. It also involves the solution to an interrelated sequence of conventional LP models. It may not be very easy to solve man- ally a GP problem. One may use a computer code to solve a GP by MSLGP. Unless we express the basic variable in terms of non-basic variables a problem cannot be solved manually. The MSLGP algorithm also assures best-compromise solution like other GP algorithm.
As you have seen above that my Revised Multi-phase Simplex Algorithm for MSLGP Algorithm reduces a lot of computations and steps. So, What I can recommend you is that you have search another way which is better than this method at all in any way.
Acknowledgement
I express my sincere gratitude to my advisor and instructor Dr. Berhanu Guta for helping me on every difficult step of this paper. I would also like to thank my classmates for giving me suggestions regarding this paper.
On top of this, my thank goes to Arba Minch University for its financial support in attending this degree of masters of Science in mathematics.
References