An achievement rate approach to linear programming problems with an interval objective function
- PDF / 197,556 Bytes
- 9 Pages / 596 x 842 pts (A4) Page_size
- 65 Downloads / 227 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
An achievement rate approach to linear programming problems with an interval objective function M Inuiguchi and M Sakawa Hiroshima University, Japan In this paper, we focus on a treatment of a linear programming problem with an interval objective function. From the viewpoint of the achievement rate, a new solution concept, the maximin achievement rate solution, is proposed. Nice properties of this solution are shown: a maximin achievement rate solution is necessarily optimal when a necessarily optimal solution exists, and if not, then it is still a possibly optimal solution. An algorithm for a maximin achievement rate solution is proposed based on a relaxation procedure together with a simplex method. A numerical example is given to demonstrate the proposed solution algorithm. Keywords: fractional programming; fuzzy sets; linear programming; optimization
Introduction Linear programming is a well established technique to solve real world problems, for example feed mix problem, production scheduling, diet problem, assignment problem, and so on. A linear programming problem is a mathematical program in which the objective function is linear in the decision variables and constraints consist of linear equalities and linear inequalities. It is known that any linear programme can be transformed into the following form:
1
max cx; x 2X
where X
fxjAx b
;
x
6
5 0g R
n
;
2
where A
aij is an m n matrix. c
c1 ; c2 ; . . . ; cn and b
b1 ; b2 ; . . . ; bm t . x
x1 ; x2 ; . . . ; xn is the decision variables. When the coefficients of the objective function are specified subjectively by the decision maker or obtained through speculations by experts, it is difficult to determine them as real numbers. In such a case, the interval representation of the objective function coefficients might be useful. Thus, the problem becomes a linear programme, with an interval objective function: max gx;
g g
g
x2X
3
g
where g
1 ; 2 ; . . . ; n and i is a possibilistic variable restricted by an interval li ; ui . The interval li ; ui shows the range in which the true coefficient possibly lies. Correspondence: M Inuiguchi, Department of Industrial and Systems Engineering, Faculty of Engineering, Hiroshima University, 4-1, Kagamı´yama 1 chome, Higashi-Hiroshima, Hiroshima 739, Japan.
Namely, the true coefficients are not known exactly, but the possible range is known. For the sake of simplicity, let
y fc
c
1 ; c2 ; . . . ; cn
jli 4 ci 4 ui
;
i 1; 2; . . . ; ng;
4
y
l
l1 ; l2 ; . . . ; ln and u
u1 ; u2 ; . . . ; un . shows the possible range of g. In this paper, we focus on the linear programming problem with an interval objective function. Two major approaches, namely the optimizing approach and the satisficing approach, have been proposed in the literature1–8. In the former, the optimizing approach1,2,6,8, possibly and necessarily optimal solutions are naturally defined. The set of p
Data Loading...
