Opsearch. Vol. 34. No. 2. 1997

0030-3887/95 $ 2.00 + 0.00 © Operational Research Society of India

THEORETICAL PAPERS

A Fuzzifying Approach to Stochastic Programming

c. Mohan(1) and H.T. Nguyen(2) (1) Department of Mathematics, University of Roorkee. Roorkee 247667, India. (2) Section of Mathematics, Agricultural University. Hanoi, Vietnam. Abstract

In this paper a fuzzifying approach is proposed to cope with vagueness appearing in the objecdtives and the constraints of linear as well as of a class of nonlinear stochastic programming problems. An interactive procedure has also been proposed to assist the decision maker in obtaining satisficing solutions of stochastic programming problems using this approach.

1. Introduction

As G.B. Oantzig noted, "stochastic programming is one of the most promising fields for future research". In a stochastic programming problem, single-objective or multi-objective, the uncertainties inherent in the parameters involved are modeled by probability distribution on the basis of the available statistical observations or the theoretical assumptions. In other words, the parameters are treated as random variables. As a result, the objectives and the constraints of such a problem turn to be stochastic ones. There are several approaches for solving single-objective and multi-objective stochastic programming problems, abbreviated as SOSPP's and MOSPP's (see for instance Stancu-Minasian, 1984. Slowinski and Teghem (eds), 1990. Roubens and Teghem, 1991). In a decision making situation leading to a stochastic programming problem (SPP) the decision maker (OM) can choose one of these approaches which in his opinion is best suited to the situation. Approaches for solving SPP's may be conveniently classified by distinguishing the treatment of the objectives and that of the constraints. One of the most commonly used approaches for the treatment of the constraints is the chanceconstrained programming approach in which a minimum probability level is specified by the OM for each of the constraints. A solution to the SPP is considered feasible if and only if all the constraints hold with at least the specified minimum probability levels. For the treatment of the objectives, some of the basic approaches are : (i) E-model which optimizes the expected values of the objectives and (ii) P-model (also referred to as minimum-risk model)

C. MOHAN AND H.T. NGUYEN

74

which consists in maximizing the probabilities, that the values of the objectives are better than certain aspiration levels specified by the OM (for more details see Stancu-Minasian, 1990). It is to be observed that in case the OM applies P-model in combination with the chance-constrained approach, there may be some vagueness in the DM's specifying the minimum probability levels for the constraints and aspiration levels for the objectives. Vagueness may also appear in the OM's understanding of maximizing the probilities related to the objectives. These kinds of vagueness (or imprecision) can be treated following one of the basic approaches of fuzzy programming called flexible programming in which some flexibility is introduced into conventional programming so as to cope with the OM's vagueness in the understanding of the objectives and constraints. Flexible programming has proved so far to be one of the most successful applications of fuzzy set theory initiated by Zadesh (1965) (see for instance Zimmermann, 1987, Sakawa, 1993. Oelgalo et a/. (eds,) 1994). Recently some researchers have also used fuzzy set theory in dealing with stochastic objectives and constraints (Chakraborty et al., 1994, Inuiguchi and Sakawa, 1995). In this paper a fuzzifying approach is proposed for solving SPP's. In this approach, the stochastic constraints are treated using fuzzified chance constraints and the stochastic objectives are treated using extended E-model. The resulting problem however is often complicated requiring a rational and efficient decision making process. To assist the OM in learning the problem inside and updating his decisions while searching for a satisficing solution, an interactive procedure is also proposed. As a numerical tool, a global optimization technique is incorporated in this interactive procedure to provide the OM at each interactive phase with a solution possessing some kind of Pareto optimality. The remaining sections of this paper are organized as follows. Section 2 presents the fuzzifying approach which can be applied to a class of SPP's. In section 3 the proposed interactive procedure is given. Two illustrative examples taken from literature are considered in section 4. Concluding observations on the study are finally made in section 5.

2_ PROPOSED FUZZIFYING APPROACH FOR SOLVING A CLASS OF SPP'S

Consider SPP of the type : Max

fI C k1

Y1 ( X ) + fIck2 Y2 ( X ) + ... + fIckn Yn ( X ) k = 1, 2 , ... , q

X= ( x1 ' x2 , ... , Xp subject to

)

(1'1)

and Yk ( X) for k= 1 ,2, ... , n (1)

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

J~k'1Y1(X)+ ~k'2Y2(X)+

1ai :-;;

...

+

~k'nYn(X):-;;

bk,k'= 1,2, ... ,q'

75 (1ii)

i = 1 , 2 , ... p (1 iii)

x; ~ b;

where Yk (X) -tr k are linear or non linear functions of x1 ' X2 ' ... , xp and " stands for randomness. If q == 1 then (1) is a SOSPP, otherwise it is MOSPP. In problem (1), each function Yk

=

Yk (X) 17'- k is defined in domain

[~, b2 ] x . . . x [ ap ' bp] C RP. Denote Y= Y( X) == (Y1 ( X) , Y2 ( X) , ... , Yn ( X) ) , then Y= Y( X) is a vector function defined

S= [a1 ' b 1

] x

in S. In case p == nand Yk == xk -tr k. problem (1) becomes a stochastic linear programming problem (SLPP).

Max

k= 1,2, ... q

subject to fI

a k'

11

fI

1

x1 + a k' 2 X2 + ... + a k'

n Xn ~

fI

bk ,

k'= 1,2, ...

q'

i== 1,2, ... ,n

We also assume that each random parameter follows a probabilly distribution with mean m( . ) and standard deviation cr (.). For the sake of simplicity and clarity of the subsequent work it shall be assumed that random parameters are independent (so that the co-variance matrix is an identity matrix) and follow normal distributions as given below 11

ck ;

==

1\

ak ,. I

I!.

bk ,

fI

N( m( Cki ), a (

11

k= 1 ,2, ... , q

C ki) )

fI

N( m (a k ,.) , a ( I

ak ,.>

1\

I

N(m(b"k ,), a(bk ,» 1\

)

k'=1,2, ... ,q'

(2)

k'= 1 ,2, ... , q'

where m( .) denotes mean and a ( .) the standard deviation of the normal distribution.

2.1. Treatment of the Constraints Stochastic constraints (1 ii) may be interpreted on the basis of fuzzified chance constraints as below. Suppose the DM has specified a fuzzy aspiration

76

C. MOHAN AND H.T. NGUYEN

level of probability Pk , at which k' -th stochastic constraint should be held, i.e. :

(3) k'= 1,2, ... ,q' The above fuzzy inequality reads as : LHS probability should be substantially greater than or equal to Pk , , where Pk , is a fuzzy number. The membership of fuzzy number

,!!

can be in general of any form. However it is usually

as a fuzzy triangular number

modeled

Pk'

Pk ,

and

k'

Pk'

Pk , =

(P k ,

,!!

k"

Pk'

) LR

with

being its mean value, left and right spreads to indicate

that where as Pk is the most acceptable value, values with neighborhood up to Pk on the right and Pk on the left are also acceptable but with gradually decresing importance (for the sake of simplicity the left and right reference functions Land R have been assumed to be linear in our present study).

Pk , !? k'

For specifying aspiration level value Pk , and its left spread consequence to

Pk ' =

(

Pk

, ,

Pk , )

the DM needs to indicate only its mean since the right spread

Pk'

(3) (hence

can be

written

Pk ,

is of no

in brief

form

Ll.. Compared to the conventional chance constraint approach,

the fuzzified chance constraini approach gives the OM more flexibility in dealing with the minimum probability level of thestochastic constraint, which is usually understood vaguely by him. Writing for brevity ELk' ( Y)

=

ak ,

1

Y1 + ELk'

2

Y2 + ... + EL k ' n Yn ' the above inequality can be treated as

Prob

~

[ ak , (

{

A

Y) - b k

J.1 C::k , ( Prob [

A

ak

,

sOl

, (Y) -

~

~

Pk ,

-

Pk

,

b k , sO]) ~ max

(4) (5)

(4) means that the stochastic constraints should be held at least at the level Pk , - !! k' . In (5) 'Ck , stands for the resulting fuzzy goal related to k' - th stochastic constraint so that J.1 ~

[ ak '

( Y) -

C (.) is membership function of Prob k'

A

b k ' sO] and represents the subjective evaluation of the probability

with regard to

Pk ' .

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

Writing

Prob Prob k'

11

= Prob [ ak , (

A

Y) - bk,:S:

77

01· J..l C ' ( .) can be k

defined as

o Probk,-(Pk,-f! k')

",*

E ~, '" * +

(P k ' -

Prob k ' - P ak ' a

f! k') (1 - le *)

Pk,-Ek'

1

f! k' ~ Probk , ~ E :' (6)

if Pk , -

if P

:,:s:

Prob k ,:s: P k '

if Prob k , ~ P k'

where!! : ' is preference level corresponding to the critical membership level le * specified by the OM for Prob k, at which the J<-th stochastic constraint should be held. le * represents, in fact, the DM's minimum satisfaction level

on the fuzzy goal Ck , and usually is taken as 0.5. Graph of J..lC

k'

shown in Fig. 1.

MC (.) k'

1 A*

.....................................\

, I

Fig. 1.

Prob k ,

(.) is

78

C. MOHAN AND H.T. NGUYEN

Now since

m ( "ak , ( Y)

Prob k ' == Prob

~

"b k

, )

a ( "ak , ( Y) - "b k ' )

m(a"k , (Y)- b" k

q,[-"

,)

"

ak , ( Y) - b k ' )

0' (

1

(where q, is the standard normal variate N ( 0 , 1 ) . ).

Hence, the inequality (4) may be rewritten as

m ( a"k

<=>

n"

L i=:1

m(

8 k , i)

b "k

, ( Y) -

q, [ - " a( ak ,

"

bk

( Y) -

"

Yj - m ( bk

, )

' )

')

~

Pk ,

-

P k'

+ n 2" 22" L a (a k' ,) Y , + a (b k ,) i= 1 I I

1112 ~

(7)

0

2.2. Treatment of the Objective Stochastic objectives (11) which are to be interpreted on the basis of extended E-model may be treated as below. First, for each of the stochastic objectives, the maximum expected value (denoted asek ) is computed subject to constraints (7), i.e. ek is obtained from the following single-objective optimization problem : n

Max L E ( &k') y.(E stands for mathematical expectation) i=: 1

I

I

subject to (7) and 8 i ~ Denoting ~ k

Xj

$

b i ' i == 1, 2 , ... , P .

the permissible leeway value from the value

specified by the OM for the k-th stochastic objective, the value

ek which is ek -

!

k

can

n be considered as a minimum threshold for L &Yk, -+ ., Applying minimum-risk i= 1

I

approach for the specified minimum threshold ek - ~ k ' the k -th stochastic

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

79

objective may be expressed as : ~

Max

Now treating this objective as a fuzzy goal in the manner of flexible programming. it may be written as Prob [ where

nk

:1

n " Cki Yi -

(e k -

~k ] ~

nk

(8)

is a fuzzy aspiration level specified by the DM for the LHS probability.

Suppose "k = (h k

.!! k) L L

• Then treating (8) in exactly the same way as

(3) it can be expressed as :

l

prob [

£ Ck,y. -

i= 1

I

I

(e k - __8 k ).;:: 0] ;:::

n fI !lG- (Prob [ L C k' Y. i= 1

k

I

I

(8 k - __8 k );:::

h k ,- _hk

0] ) ~

(9)

(10)

where 'Gk stands for the resulting fuzzy goal related to the k-th stochastic n objective. Writing Prob k = Prob [ L Ck.y. - (ek - e k ) ~ 0] the memberi= 1

I

I

=

ship function !le, ('P rob k)' which represents the DM' subjective evaluation k

of the probability Prob k' can then be defined as

o A * 'Prob k - (hk -

!J k)

!! ~ -: ( hk - !J k )

!!c (.) = k

1

(11 )

80

C. MOHAN AND H.T. NGUYEN

1 ..... ".................................................. .

A*

o h -h

k -k Fig. 2.

In (11)

!J ~

E

(h k -

!!. k '

h k ) is a DM specified value and has a meaning

similar to the meaning given to

E ~, .

The graph of

!la (.)

is shown in

k

Fig. 2. It may be noted that 'Prob k is the probability with which the k -th stochastic objective can take a value not less than

.! k and !!. ~

ek -

is preference

level specified by the OM for this probability regarding the earlier chosen critical membership level le * Now since by definition

'Prob k =

Prob [

ek - _!!

k -

cr (

1 -

ek ,j,

'I'

[

-

.! k

n " m (L C k' Y. ) n" i=1 I I

m(

n "

L C k' y.) i= 1 I I

]

n " L C k' y.) ;= 1 I I

-

cr (L

;= 1

C k' I

]

k= 1,2, ... ,q.

y.) I

where ~ denotes the standard normal variate N(O,1). In view of this inequality (9) may be rewritten as :

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

e- e

= k

k

- m n

n

81

11

(L Ck, Y. ) i=1 1 1 2

11

hk -

!! k

0'( ~ C k'Y.) i= 1

1 1

or

<=>

n

~ i= 1

11

m ( Ck ,) Y. + $ 1

-1

[ 1 - ( h - h )1 k

1

-k

[£i= 1 0'2 (

~

,) kl

y 2 11/2 1

(12)

2.3. Using Pay-off Information in Specifying

!

k

In order to help the DM in specifying his preference level on permissible leeway value !! k from the value ek for the k-th stochastic objective, the following pay-off type information ,inherent in the problem structure may be provided to him. Let

X: '

1, 2 , ... , q, be the optimal solutions of the following q

5 =

single-objective optimization problems which correspond to the q stochastic objectives. n

11

Max ,L E ( c/i) Yi subject to (7) and 1=

a,1 S

1

x,1 s b"1 i = 1 , 2 , ... , p. for

1= 1 , 2 , ... , q.

(13)

x: '

The lower bound of all the expected values of the k-th stochastic objective 5 = 1, 2 , ... , q, is then calculated by : achieved at

!l. k

=

. n 11 * Mm { ~ E ( Ck' ) Y. } i= 1

1

1

where minimization is taken on the set {

Y:

=

Y(

X:),

5=

1,2, ... ,q}.

The value (e k - !t k) may be taken as the maximum permissible leeway value

82

C. MOHAN AND H.T. NGUYEN

for ~ k '

and threfore the OM may specify values of ~ k in the range

[ 0 , . ek - ~ k] . The determination of the leeway levels! k as done above for the stochastic objectives is, in fact, based on pay-off type information inherent in the problem structure. However, if desired, the DM may also specify these levels with or without incorporating the above pay-off information.

2.4. Deterministic equivalent of SPP For the numerical solution of realistic problems it will be convenient to rewrite SPP in its equivalent deterministic form as a single objective optimization problem. With the above interpretation and treatment of the objectives and the constraints SPP (1) can be rewritten as : Max

!lG ( . )

k= 1 ,2, ... q

!le ' ( .)

k' = 1 , 2 , ... , q ,

k

Max

k

Subject to (7). (12) and a1 :$

Xi :$

bj

,

(14)

i = 1 , 2 , ... , q.

For the numerical computations using Bellman-Zadeh's min-operator as aggregation operator, (14) may be transformed into the following max-min type deterministic single-objective optimization problem.

j f

Max Min

j=1,2, ... ,q

/lGj' ( . )

k'

/le (.) k'

subject to (7), (12) and aj :$

xi

:$

= 1 ,2 •...

(15)

, q'

bj , i = 1 , 2 , ... q .

The disadvantages inherent in the use of min-operator used for aggregating the fuzzy goals of the objectives and the constraints as well as the fact that the OM usually has only limited information can be compensated by adopting an interactive algorithm for solving (15). Such an iterative process enables him to learn gradually during the interactive process about the true nature of the problem structure. As a result while searching for a satisfying solution of this problem he can also iteraratively update his assumptions toward more realistic values.

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

83

3. THE PROPOSED INTERACTIVE PROCEDURE In this section we propose an interactive procedure for solving SSP of type (1). Initialization

(The work "specity" is referred to the OM's actions) and Pk , ,!! k' '.P k ~ E [P k , - !? k' , Pk , ] , obtain ek , !t k , k= 1 ,2, ... ,q. Next, specify

Sp ec ify 'A * k'= 1 ,2, ... ,q', to

!

k

k =

[0, ek - !t k 1 for k = 1 , 2 , ... , q, and hk

E

,!1 k' IJ ~ E

[

!J k '

hk -

hk

1,

1, 2 , ... , q, Set 1 = 1 .

Iterations

Step 1 : Solve the deterministic optimization problem (15) and provide the OM with: (i) The compromising solution X1 = (x ~, x ~ , ... , x ~) and the corresponding objective function value

A,1 •

n

(ii) The expected values of the stochastic objectives L m ( Ck . ) y. and the ;= 1

corresponding probatilities

ek

greater than

-

!. k

I

I

Prob k with which the objectives can take values

' k=

1 , 2, ... , q.

(iii) The expected values of the LHS's of the stochastic constraints n 1\ L m ( ak , .) y. and the corresponding probabilities Prob k , with which the

i= 1

'

I

constraints are likely to be satisfied, k' = 1, 2 , ... , q' . Step 2 :

I

(i) If

A,1 -

'A * I < /) (where /) is the OM prescribed small positive value)

the interactive procedure may be terminated with the satisficing solution X1 . (ii) If

A,1 >

'A* + 8 , and the OM is satisfied with X1 the interactive procedure

may also be terminated with the satisficing solution X1• However if the OM wishes

to

continue the exploration he can

increase at least one of :

C. MOHAN AND H.T. NGUYEN

84

si: ' j = 1 , 2 , ... , m; !J ~, k = 1, 2 , ... , q ; !? k ~ /

or

decrease

~k,k=

at least

of:

E;,

,j'

k'

= 1 , 2 , ... , q ,and

=

1,2, ... , rn':

1,2, ... ,q.

(iii) If A1 < A, *

-

cS, then

increase at least one of : and/ or

one

,

b;, ,

decrease at least

1 ,2, ... , q;

!?:'

X;

is not a satisfactory solution. The OM can

j ,

=

1 , 2 , ... , rn': ~ k ' k = 1 , 2 , . . . • q

one of

sif,j=1,2, ... ,m.; !J~,k=

,k' = 1 • 2, ... , q'

(iv) Set 1= 1+ 1 and go back to step 1. It may be noticed that if A1 < A, * - cS (in step (2iii)) then the values of some of the membership functions

!la ( .) k

and J..l

ck ' ( .)

are less than A*

meaning that the corresponding preference levels have °not been achieved. The OM may relax these preference levels and/or he may relax also other preference levels in order to gain the formers. If A,1 > A * + cS (in setp (211)) it will mean that all preference levels have been achieved and therefore the OM may tighten some of the preference levels. In the proposed interactive algorithm, the OM's preferences with regard to the objectives and the constraints are progressively articulated through the critical membership level A* thereby enabling the OM to suitably compromise his preferences to arrive at a satisficing solution. This interactive style is in fact in line with interactive method FULPAL of Rommelfanger (1990) which has been developed for solving fuzzy programming problems. The proposed interactive procedure incorporates RST2AN algorithm of Mohan and Naguyen (1996a) as a numerical tool for solving the resulting optimization problem in step 1. (The user can use any other suitable numerical optimization algorithm available to him) or ready reference, a summary of this algorithm is given in appendix 1 to this paper. Since RST2AN algorithm search as for a global rather than a local optimal solution of (15), at each interactive phase the OM is likely to be provided with an efficient solution possessing some kind of Pareto optimality (see appendix 2 to this paper, for more detail one may refer to Nguyen, 1996). Keeping in view the practical considerations, different priorities may have to be assigned to achievement of different objectives. In the present method this can be achieved by incorporating his preference in the iterative procedure. The proposed procedure can also be used if some or all constraintgs (or objectives) are deterministic by assuming

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

85

that the right and the left spreads of the corresponding determinstic numbers are zero. 4. ILLUSTRATIVE EXAMPLES

In this section we demonstrate the working of the proposed interactive procedure on two test problems taken from literature. Assuming that the solutions of these problems reported in the source are taken by the (hypothetical) OM as the target solutions, efforts have been made to reach these target solutions. 1. This problem is given in Goicoechea et al. (1982).

Example

fI

Max~

N(2,4)X,+ N(3,2)x2

Minfl~

2 2 N(1, 1)x 1 + N(1,1)x 2

fI

Max ~

subject to

N ( 4 , 3 ) x1 + N ( 1 , 1) x2

x~ + x~:s; 25 ; 3 x1 + x2 :s; 12 ; O:s; x1 :s; 4, 1 x2

$;

5.

This example is a multi objective stochastic programming problem which was solved in the source using Protrade method of Golcoechea et al. The problem has three stochastic objectives and two crisp constraints. The results obtained by Protrade method as reported in Stancu-Minasian (1984) are : x1 = 2.28, x2 = 2. , and Prob

fI

(~ fI

Prob

(~

Prob

(~

fI

(X') > 11.84) = 0.45,

, (X) > - 12.52) = 0.70, (X') > 13.68) = 0.36.

(To solve the problem with the proposed interactive procedure, the second fI 2 2 objective is rewritten as Max 22' = - N (1 , 1 ) X 1 - N ( 1, 1) x 2 ) . Initialization

Set A * =

0.5. The computer system provides the DM with the following

C. MOHAN AND H.T. NGUYEN

86

pay-off type information on values of the stochastic objectives e1 := 18.006872, ~1 = 3, e2 = - 1 . '~2 = - 24, e3 = 15.666667, ~3 = 1 . The OM prefers to start with relatively large leeway levels

!

as

1t- k

k

well as low preference levels on the probability of the stochastic objectives h ~ 1t- k (assuming that the corresponding fuzzy aspiration levels nk have been already h1

:=

h3 =

specified by

him)

0.55, 111 = 0.2, 11 ~ = 0.4, h2 = 0.08, 0.1

and h~

=

!

and sets

11 2

1 :=

= 8, !

0.2,

2

= 14,

h ~ = 0.65,

!

3

=

h3

=

0.4

4, I

O. 32 .

Iterations Stoch obj. 1 (prob)

Stoch obj.2 (prob)

Stoch obj. 3 (prob)

Crisp const.1 (LHS)

Crisp const. 2 (lHS)

11.015129 Prob = 0.544479

-9.401619 Prob = 0.794478

10.045362 prob = 0.397101

9.401619

8.133266

Iter No

1

0.981594

>G

= (1.912096, 2.393976)

The OM aspires for smaller leeway levels for all the objectives. For this, he tightens all the preference levels ; e = 7,6 = 13, e = 4,

!J. f = 0.42, 2

12~ = 0.67,

0.808813

!J. 8= 0.34.

11.013778 prob = 0.500291 ~ =

=

1

=

-9.540536 10.588855 prob = prob = 0.750296 = 0.377061

2

=

9.540536

3

8.513577

(2.075279, 2.287740)

The OM is still not satisfied with the obtained results and decides to further tighten all the preference levels ; 8 1 = 6.16,62 = 11.52,63 = 1.98, =

=

!J. f = 0.445, 12 ~ 3

0.512237

=

= 0.695,

10.540056 prob. = 0.447541

X3

12 ~

= 0.335.

-9.147946 prob. = 0.697570

11.071051 prob. = 0.356108

9.147946

8.803741

= (2.267309, 2.001813)

The OM is satisfied with the obtained solution which is very close to the target solution.

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

87

x1=

2.267309,

It may be noticed that the solution as obtained above is

x2

=

2.001813, and

"

Prob Prob Prob

(Z1 (

-

11,846872 )

X) >

- > (22" (X) " (~( X) > I

-12.5200

=

)=

13.686667 )

=

0.447541, 0.697570, 0.356168.

Example 2. Determination of optimal cattle feed is a well-known application of linear programming. A particular case of the problem is described as follows. Given the percentage protein content and percentage fat content of the raw materials (barley, oats, sesame flakes, and ground nut meal), the required percentage content of protein and fat in the feed mix, the cost per ton of the four raw materials, the problem is to determine a mix with minimum cost per ton that satisfies the nutritive requirements. The ncessary data is given in the table below. Content of

Barley

Oats

Sesame Flakes

Groundnut Meal

Requirement

Protein (%)

N(12.0, .28}

N (11.9,.19)

N (41.8, 20.5)

N(52.1,.52}

21

Fat (%)

2.3

5.6

11.1

1.3

5

Cost per ton

24.55

26.75

39.00

40.50

where N ( m, er 2) denotes a random variables with normal distribution whose mean value is rn, and dispersion is er 2. The mathematical model as given in Bracken and McCormic (1968) is : Min f ( X)

=

24.55 x1 , + 26.75 x2 + 39.00 x3 + 40.54 x4

subject to : N(12.0,.28)x1 +

N(11.9,.19)x 2

+ N(41.8, 20.5)x3 + N(52.1, .62)x4

~ ~

21;

5 ; 1 ;

X. ~ I

0 , 1 == 1, 2 , 3 , 4 .

C. MOHAN AND H.T. NGUYEN

88

Also in the above model the specification is made that the probability of achieving a protein content of 21 % be at least 0.95. Namely, the following chance constraint is introduced : Prob[N12.0, .28)X1 + N(11.9, .19)X 2 + N(41.8,20.5)x3 + N ( 52.1, . 62) x4 ~ 21]] ~ 0.95

However, it is likely that the minimum probability level can only understood by the DM with some vagueness. Hence, we propose to introduce some flexibility in the chance constraint, which results in a fuzzy goal. The fuzzy aspiration level for the LHS porbability is set as (1.0.15) i.e. the lower bound for the probability is 0.85, and the upper bound is . This approach provides the OM with a 'soft' specification of the probability level of the chance constraint and enables him to explore the best satisfactory probability level by trading-off the cost objective function and the probability level of the chance constraint during the interactive solution process.

Lt'

The resulting model is as follows : Min

f ( X)

= 24. 55x1 + 26.75x2 + 39.00 x3 + 40.54 x4

subject to : Prob [ N ( 12.0, . 28 ) x1 + N ( 11.9 , . 19 ) x2

+ N ( 41.8, 20.5 ) x3 + N ( 52.1 , . 62) x4

~

~

21] > p

1= (

1 , 0.15 ) LL ;

5

Xi~

0, i= 1,2,3,4

There is only a single objective in which the coefficients involved are crisp ones. In order to illustrate the working of the interactive procedure proposed in section 3, we have considered the objective as a stochastic objective wherein the coefficients involved are taken as random variables following normal distribution with dispersion zero, and the minimization of the objective function has been rewritten as : Max f I (X) = - f ( X). All the inequality constraints have been converted from ~ into::;:; for the same reason. The crisp equality constraint has been used to reduce the dimension of the problem by expressing .x4 through the remaining variables.

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

89

The solution as given in the source is X = (0.6359, 0., 0.3127, 0.0515) with f = 29.89. This solution has been taken as the target solution to be achieved by the hypothetical DM.

Initialization

=

Set A. *

0.5 and P1

=

1, P~ = 0.9 and p 1

- 29.547873. Set and; 1 = 1 and h1 =

!J ~

= 7)1=

=

0.15 to obtain e1

1 .

Iterations Iter No 0.988309

(Stochastic) objective value

Stochastic cons!. (mean value)

Crisp constraint

- 30.547863 (with probability Value = 1)

-24.52445 with probability value = 0.997662

-5.000027

Xl = (0.503157,

0.109769,0.278034, 0.109010)

The OM is not satisfied with the obtained solution. He wants to further decrease the cost objective value at the expense of the probability level of satisfaction of the stochastic constraint. For this he sets;; 1 = 0.5 and -

2

p a 1

= 0.93

0.792779

to obtain -30.047867 (with probability value = 1)

X2 =

-23.622787 with probability value = 0.970989

-5.000006

(0.587899, 0.145618, 0.297536, 0.068847)

The OM still not satisfied with the obtained solution. He wants to further decrease the cost objective value at the expense the probability level of the satisfaction of stochastic constraint. For this he sets : e = 0.35 and = 1

-

3

p a 1

=

0.95.

0.499883

-29.897871 ( with probability value = 1)

Xl = (0.622921,

-23.253762 with probability value = 0.950178

-5.000093

0.014936, 0.307444, 0.054699)

The OM is satisfiedc with the obtained solution since it is close to the target solution.

C. MOHAN AND H.T. NGUYEN

90

5. CONCLUDING OBSERVATIONS In this paper a fuzzifying approach is proposed for solving a class of SPP's. The stochastic objectives and constraints are fuzzified on the basis of the extended E-model using fuzzified chance-constrained programming. This gives the DM more flexibility in dealing with the vagueness appearing in the stochastic objectives and the stochastic constraints which is ofen encountered in realistic situations. A simple but efficient interactive procedure is also proposed in this paper to assist the OM in updating his decisions while searching for a satisficing solution. During the interactive solution process, the DM can learn more and more about the problem inside and compromise his preference levels of the objectives and constraints. Through the two examples given in section 4 it is seen that RST2AN algorithm as a numerical tool incorporated in the proposed procedure proves quite efficient in searching satisficing numerical solutions to SPP's which possess some kind of Pareto optimality. With the above observations, it is recommended to apply the fuzzifhying approach as well as the interactive procedure proposed in this paper for solving realistic SPP's. REFERENCES [1]

BRACKEN, J. AND MCCORMIC, G. P. 'Selected applications of nonlinear programJohn Wiley & Sons. New York (1968).

ming'~

[2]

CHAKRABORTY, D., RAO, J.R. AND TIWARI R.N. "Interactive decision making in mixed (fuzzy and stochastic) environment", Opsearch, 31, 89-107, (1994).

[3]

DELGALO, D., KACPRZYK, J., VERDEGAY, J.L. AND VILA, M.A. (Eds) 'Fuzzy optimization: Recent advances'~ Physica Verlag. Germany, (1994).

[4] GOICOECHEA, A., HANSEN, D.R. AND DUCKSTEIN, L. 'Multiobjective decision making wsith engineering and business applications'~ John Wiley & Sons, New York, (1982). [5]

INUGUCHI, M. AND SAKAWA, M. HA possibilistic linear program is equivalent to a stochastic linear program in a special case", 'Fuzzy Sets and Systems, 76, 309-317, (1995).

[6]

MOHAN, C. AND NGUYEN, H.T. "A controlled random search technique for global optimization incorporating simulated annealing concept", submitted for publication in The Journal of Global Optimization (1996 a).

[7] MOHAN, C. AND NGUYEN, H.T. "A controlled random search technique incorporated simulated annealing concept for solving integer and mixed integer global optimization problems", submitted for publication in Computational Optimization and Applications (1996 b). [8]

MOHAN C. AND SHANKER, K. "A control random search technique for global optimization using quadratic approximation", Asia-Pacific Journal of Operational Research, 11, 93-101, (1994).

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING [9]

91

NGUYEN, H.t 'Some global optimization techniques and their use in solving optimization problems in crisp and fuzzy environments", Ph.D. Thesis submitted in Department of Mathematics, University of Roorkee, India, (1996).

[10J PRICE, W.L. "Global optimization by controlled random search", Journal of Optimization: Theory and Applications, 40, 333-348, (1983). [11J ROMMELFANGER, H. "FULFAL - An interactive method for solving multiobjective fuzzy linear programming problems", in SLOWINSKI, R. AND TEGHEM, J. (Eds.) 'Stochastic versus fuzzy approaches to multlobjective mathematical programming under uncertainty", Kluwer Academic Publisher, Dordrecht, Holland, 279-299, (1990). [12] ROUBENS, M. AND TEGHEM, J. "Comparison of methodologies for fuzzy and stochastic multiobjective programming", Fuzzy Sets and Systems, 42, 119-132, (1991 ). [13] SAKAWA, M. 'Fuzzy sets and interactive multiobjective Press, New York, (1993).

optimization'~

Plenum

[14] SLOWINSKI, R. AND TEGHEM, J. (Eds.) 'Stochastic versus fuzzy approaches to multi objective mathematical programming under uncergtainty': Lluwer Academic Publishers, Dordrecht, Holland, (1990). [15] STANCU-MINASIAN, I.M. 'Stochastic programming with multiple objective functions", D. Reidel, Dordrecht, Holland, (1984). [16] STANCU-MINASIAN, I.M. "Overview of different approaches for solving stochastic programming problems with multiple objective functions", In Slowinski, r. and Teghem, J. (Eds.) 'Stochastic versus fuzzy approaches to multiobjective mathematical programming under uncertainty", Kluwer Academic Publisher, Dordrecht, Holland, 103-116, (1990). [17] ZADEH, L.A. "Fuuy sets", Information and ContrOl, 8, 338-353, (1965).

[18] ZIMMERMANN, H.J. 'Fuzzy set, decision making and expert Academic Publisher. Dordrecht, Holland, (1987).

systems'~

Kluwer

c.

92

MOHAN AND H.T. NGUYEN

APPENDIX 1. RST2AN ALGORITHM

RST2AN algorithm has been designed by Mohan and Nguyen (1996a) for solving global optimization problems of the type Min !( X), X= (Xl' X2 , • .. , Xn)

E

Rn

subject to g/ X) ~ 0 g.( X} = 0

{a

J i

~

x.I

~

bi

(16; ) j= 1 ,2, ... , k j=K+1,k+2, ... m (16ii)

;= 1,2, ... ,n.

(16)

(16 iii )

The algorithm works iteratively in two phases called the global phase and the local phase. In the global phase, a suitably large number of feasible paints are randomly generated and stored in an array A (the point with the minimum function value is stored as L and the point with the maximum function value is stored as M). In the local phase, these pOints are suitably manipulated in order to get a better point for an estimate of global minima. In this phase, point X·, the possible point of minima of the quadratic curve passing through L and two other points randomly chosen from array A, is determined. If X· is feasible then X· is accepted in place of M in array A if f( X*) ~ !(M) otherwise X· is accepted with probability p= exp (- p ( f( X*) - f( M )/( f( X*) - f( L) » for a suitably chosen constant value of the parameter P> O. If X* is not feasible or X* is feasible but not acceptable, the .trial is discarded and a new set of points is selected from the array A and the process repeated. As the algorithm proceeds the current set of stored points in array A tends to cluster around a golbal minimum. RST2AN algorithm is essentially based on a suitable modified version of controlled random search algorithm of Price (1983) as developed by Mohan and Shanker (1994) incorporating simulated annealing concept of accepting occasional uphill moves. The philosophy of the RST2AN algorithm is that while following the global strategy of Price's method, in the local phase it incorporates the simulated annealing concept in the quadratic approximation of Mohan and Shanker (1994). This helps the algorithm in avoiding clustering to a non-global solution and also makes the clustering process more effective. heuristicallY through use of the simulated annealing concept, the algorithm is discouraged from premature termination by accepting occasional uphill moves.

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

93

Computational steps of RST2AN algorithm can be summarized as below.

Step 1. Randomly generate a suitably large number N of feasible points and store these points along with their function values in an array A. Set counter for the number of iterations ITER = 0, and counter for the number of consecutive trials for which objective function has not improved 15=0. Also set FL=O (FL is used to store the best function value found in the previous iteration). Step 2 : Rearrange the points of array A in ascending order of their function values and find M and L, the points with the greatest and the smallest function values f(M) and f(L) respectively. Set counter for the number of consecutive failures IFAIL=O. If FL"# f( L) set IS=O and FL= f(L) , and go to step 3. If FL = f( L) set IS = IS + 1. If IS>ISLAST (where ISLAST is a large positive number used to restrict the number of consecutive searches in which the objective function value fails to improve) go to step 8. .. . Step 3 : Ch eck stopping criterion

FM

=

f (M) if

I

f ( M)

I>

~ 2'

I (f---( --M )Rvi------ f ( L ) ) I ::;

€ 1 '

h were

else FM:= 1 ( r. 1 and r. 2 are user prescribed

small positive numbers). If the stopping criterion is satisfied indicate that the global solution has been achieved and stop.

Step. 4: From the array A choose 8 1

=

L and two other distinct random

points 8 2 and 83 . Determine the next trial point X* using quadratic approximation formula :

( 17)

If x * lies within the specified range a1 :: x* b. i= 1 , 2 , ... , n then go I I I to

step

x *1

:=

5,

otherwise set

x.* = b j for those I

i for which x.*I > b j and

a. for those i for which x.*I < aI.. I

Step 5: Check feasibility of X*. If X* is not feasible go to step 7, else find f ( X * ) . Generate a random number r between 0 and 1 and compute

C. MOHAN AND H.T. NGUYEN

94

p

== [1

exp(- ~(f(X*)- f( M))/(fX*)- f( L»)

if f(x*)~ f( M) otherwise (18)

for specified ~, where X* and replace M by

P

X'

is a suitable chosen constant >0. If P > , accept in array A and go to step 6, else go to step 7.

Step 6 : Set ITER=ITER+1. If ITER>ITLAST (where ITLAST is a large number specifying the maximum number of iterations to be performed in the search of the global optimal solution) go to step 8, else go to step 2. Step 7 : Set IFAIL=IFAIL+1. If IFAIL>IFLAST (where IFLAST is the maximum number of consecutive failures of the algorithm permitted by the user in search of new acceptable trial point) go to step 8, else go to step

4.

Step 8 : Stop with the indication that the current point L is the point with the best objective function value which could be found by the algorithm. The feasible random points can be generated using any random number generator which generates uniformly distributed random numbers between 0 and 1. The random number r.I between 0 and 1 after being generated is scaled between lower and upper bounds ai and b; of the coordinate x; to obtain its random value: xi = point X =

(x 1

' X 2"

8; + (b i - ai ) 'i' i = i, 2, .' .. , n. The random .. , xn ) thus generated is then tested for feasibility.

The algorithm is best suited for solving essentially unconstrained optimization problems wherein only the lower and upper bounds on the values of the variables are specified. However, it can also be used to solve both inequality as well as equality constrained problems. Whereas statisfaction of inequality constraint is ensured by checking that the randomly generated point X does not violate these constraints, for equality constrained problems, the strategy as adopted by Mohan and Shanker (1994) can be used. Namely, whenever possible equality constraints be used to reduce the dimension of the problem. The equality constraints which can not be handled in this fashion be appended to the objective function using penalty function approach. For solving integer and mixed integer global optimization problems an updated and suitably modified version of RST2AN algorithm. called RST2ANU algorithm, has been designed by Mohan and Nguyen (1996b). This algorithm can be incorporated in the proposed interactive procedure in place of RST2AN algorithm in case some or all decision variables in the SPP to be solved are req~ired to be integer. In order to satisfy the integer restrictions imposed on

A FUZZIFYING APPROACH TO STOCHASTIC PROGRAMMING

95

some or all variables, a special truncation procedure has been proposed. Namely, whenever a new point X = (X1 ' X2 ' ••• , Xn) requiring the integer restrictions is to be generated, it is first randomly generated without imposing the integer restrictions. For each component xi' which is restricted to have integer value,

x.I is integer

x. I

xi

=

is truncated (rounded) to an integer value X., I

otherwise

x. takes on either value [ x. ] I

I

xi

by the rule : If

or [ x.I ] + 1 each

with probability 0.5 ([ x.I ] is the integer part of x.) . I The details of RST2AN and RST2ANU algorithms and their performance on a number of test problems are reported in Mohan and Nguyen (1996a), (1996b) and Nguyen (1996). APPENDIX 2. PL-PARETO OPTIMALlTY CONCEPT

For SPP's of type (1) the following concept of PI-Pareto optimal solutions (PL stands for probability level) may be defined. Definition 1 : A solution X of (14) will be called weak PL-Pareto optimal for the given MOFSPP (1) at the specified leeway levels! k "\f"" k, if there does not exist another solution x of (14) at which all the probability levels of the stochastic objectives and the stochastic constraints ('Prob k' -V- k; Probk' ' -V- k') are respectively better than those attained at X.

Definition 2 : A solution X of (14) will be called PI-Pareto optimal for the original MOFSPP (1) at the specified leeway levels ! k if- k, if there does not exist another solution X' of (14) at which all the probability levels of the stochastic objectives and stochastic constraints are respectively not worse than those ones attained at X, and in at least one case one of these values is better than the corresponding value attained at X. Theorem 1 : (i) If X is a global optimal solution of (15) with 0 < A. < 1 ( A. is the optimal objective function value for problem (15) achieved at X) then X is a weak PL-Pareto optimal solution of the original SPP (1) at the chosen levels

!k

-V- k.

(ii) If X is the unique global optimal solution of (15) then X is a PL-Pareto optimal solution of the original SPP (1) at the chosen leeway, levels

!k

-V- k.

C. MOHAN AND H.T. NGUYEN

96

Proof : Suppose if possible there exists another solution X' to (14) at the same preference levels such that :

Prob k at x' Prob k , at x'

Without

!le (.) k'

loss

Prob k at X

>

>

of

Prob k , at X

generality

if- k'} is uniquely

membership functions

if- k,

suppose

A= min {

k

k, and !le

k

(20)

if- k'

achieved at !la (.)

!la (.) if-

(19)

X

!la ( . ) if-

k,

k

for k = 1. Since the

( . ) if- k' are increasing func-

k'

tions, (19) and (20) imply : !la (.) k

!lCk , ( .)

and

l1a (.) 1

at X' ~ at X' ~

l1a

k

at X

(.)

!lck , (.)

at X' > l1a

1

at X

if-k if- k'

(.) at X

(since l1a ( . ) at X = A E (0, 1 ) , !la ( . ) is strictly increasing at X). Hence 1

1

min { !la ( . ) -v- k ,w (.) if- k'} is greater than X'. k Ck ,

!la 1 ( .) at X

= A=

min { l1a ( . ) -V- k,!le (.) if- k'}. This contradicts the assumption that X k k' X is a global optimal solution of (15): The proof of the first part of the theorem is thus completed. The second part of the theorem can be proved similarly.