• Nu S-Au Găsit Rezultate

View of An algorithm for multicriteria transportation problems

N/A
N/A
Protected

Academic year: 2022

Share "View of An algorithm for multicriteria transportation problems"

Copied!
6
0
0

Text complet

(1)

REVUE D'ANALYSE NUMÉRIQUE

EI'DE

THÉORIE DE L'APPROXIMATION Tome 28, Nu 2, 1999, pp. 16!172

AN ALGORITHM FOR MULTICRITERIA

TRANSPORTATION PROBLEMS

LIANA LtiP,SA, EUCENIA DUCA and DOREL L DUCA

1. PRELIMINARIES

It is

known that many applications

of

rinear programming

in

managing economic processes come to the solving some transportation

probl.rr. A

such model was presented for instance'in [8].

A

transportation problem (of the cost type) is. a linear programming prob- lem of the following rype

(c)

'nin

f

l', D",=¡,,,r,¡

subject to

2",=,*',= a¡' ie

{l'

""m1

2','--,*u =

b¡, ie

{1, " ', n) x¡j

)

0,(r,

j)'e

ll,'..., mlx {1,.,,, n}, as usually represented in a table qf the f'ollowing type

A1 C t,,

cnn b,

cll cnl bl

Any feasible solution of the probrem

(c)

is called a transport plan. A chain is any system ofcells ofthe type

(it,it), ft¡i),

(iz, jz), Qz,

jù.

,..

or

"

(it,

jù,(iz,.i),(iz,

jz),(iz,

jù,

199 I AMS Subject Classificarion; 90C29. 90C08

(2)

-1

'

IVlulticriteria Transpoltatioñ Prnblenrs

f*(x)=)I.,Í',,

nlÙ

ke {1.,,..p},

ló5

for

all

,X = (.r¡¡ )e lR./'tx'r , and the constr.aints are

)r=,

ttt

=

tt¡'

ie {l" ",

nr}

sr, i

L,=,r,¡

=

h,,

.i e {1...., n}

.tu

t0,

(i,

j)e {1..,,.m}x{1....,n}

By analogy with the scala case. a rnulticriteria transporration problem (MTp)

will

be represented by

4,,,

c'fi¡'','.,cf];

('),,r' .;..Ç!1,,i

b,

..t

..t,

Lll'.'.riLIl

clrrl , P

nl bl

The set of the feasible solution of the problern (MTP)

will

be denotecr'by

s.

A transport plan X

e

S is called Pareto (or min-effìcient) if rhere is no l,

e

.f such that

.fk(Y)<.f*(x), ke {1, ..,p1.

at least one of the inequalities being strict. Because any Pareto transport plan is a

Pareto solution of a multicriteria linear programnring problem, some interesting properties of the Pareto transpoft plan set can be found for insrance in [7].

on

the other hands, for the determinatjon of a Pareto transpôrt plan, we can use any algo-- rithms given in l2l, l9l,

[0ì

etc, lf, in addition, .r,; ((i,

j)

{ 1, . .., m}

x

{ 1, ...,'n } )

must he integer, the algorithrn,given

in

[7] allows us to cletermine all the equi- valence classes of the Pare,to transpqrt plans. Note that we can also solve a mul-

ln

the following we

will

denote by (1r) (k

e

(1,, ..., lt

|)

rhe scalar rrans-

portation problem

o'in

)1'1,2]=,,,!,r,

subject to

¡=r i=r

Eugenia Duca and Dorel I. Duca 2

t64

,

Liana LuPça'

not contain anY cYcle:

Itisknowrrthat,ifatransportattonproblernadmitsatransportplan,thenit

t(,,j) e

{1,

...,

rn)

xl l, "''

n}:

x¡> 0}'

be denoted bY Sel(X).

The acyclic transport plan X = (x¡) is called potential with respect to a se- lection set A

Sel(Ð,

if

there exist the real numbers

U1,,'., \'lnp Vl, "', ltil which satisfY the conditions

(l) v¡-u¡Sc¡forall (i'¡)e {l'""nr}x{l'""rt}

and

(2) ri-

ü¡= c¡ for all

(i'i)

e A'

If

the real numbers tt1,

".,

t1,,¡, v¡,

"',

v, satisfy

(l)-(2)'

then the

(n

+ n)-tuple

(nq,

..,' t'tr'Y¡,.'.,

vu) is called apotential system forA'

THEOREMl.l.(see,forexampletlll)'ThetransportplanXisanoptimal

planifanrtonbifthereisasetAesel(X)suchthatXisapotentialplanwith

respect to A.

2. MULTICRITERIA TRANSPORTATION PROBLEMS

In

the following we call a multicriteria transportation problem of the cost type, denoted by

ffîP),

a multicriteria linear programming problem

in

which the objective function is a vector function.f =

([r ...,1) '

R"rx'r

-+

R.P, given by

(3)

M ulticri teria Transportation probleins

t67

for each (i,

j) e

{

l,

..., m)

x ll,

....

nl

and k

{1, ...,

p}.

Obviously o,f.< 0, for all (i,;j) e Ap := {

l,

...,

ml xl I,

..., n }. Let

= {Q,

ìe

Ag:o,rl = 6¡

We presume that ør?

10,

for all (i,7)e

A|

, and we denote by A? =

l(i,,r)e

Aty :af, =0¡ .

We continue in the same way: if there is k

e

11, ..,, p

_l

), f.or which

af

<

0

for

all

(r,

j)e

Aþ) ,wedenore by

=le, j)e

tþ-t

:uf,=g¡

A necessary condition for the pareto-efficiency

is given by the foilowing result.

THEoREM 2.2. lf there exists q

c

{1, . .., p _

l}

such thtat

o!,=O,forail (i,.i)e

Aþ_t,andfre {1,

:..,q),

ancl if there e.rists (r, s) e A'1, =

{(i,,/)e

A,!-t :ul, =01 , with of"*l > 0 , rhe, there is a Íransport pktn

y

having the property

that

and

.fi(Y) =

fog)

for each k

e lt,

...,

ql

5

if ,t*tU) < ,fq*t(X), tvhich tneans that X is not pareØ_fficient

.

e

This will

s

r) and we

otedly

+ form a semichain

rl:ÌXonil:

nichain L_. We analyse the elements xry

of the transport pran

x

situated in the semichain

L

and we define 0 = min{x¿ : (i,

j) e L-!,

which is attained, for exampre, in the ce, (u,l). From the erements _r¡ which cor_

respond to the semichain

L-

we substract the number g, and to the elements r,, corresponding to the semichain L+ we add the number 0. The

",h".;..;;1

which are not in the cycre 'í, remain trt" ,um". we obtain a new transport pran ), to which wc attach the

set -

---

t66 Liana Lup¡a, Eugenia,Duca and Dorel I..Duca

>;='

'Y¡¡ =4¡'; i e

{1""' n}

E'i=,r,,

=

b¡, ie

{1,..., r¡}

20,

(i, j)e.{1,

...,

mlx{1,..,,n}.

LetX=(x¡¡)be

an acyclic transportplan and letA

e

Sel(X). Foreach k

e

{1.

p |, let (uf ,

...,rf,,, ,f

, . , ., r,f ) be a solution of the system

,l -

uf = c,f,, G,

i)e ¡

.

We denote by

for each

(i,f) e

{1, ...,

ml x ll,

...,

nl

and k

e

{1, ...,

p}.

The following result gives a sufficient condition for tbe

Pareto-efficiency:

:

THEoREM 2.1.

kt

ft

e

{ 1, ...,

pI. lf

X is a potential plan of the problem (T¡,),with respect

n

A

e

Sçl(Ð a4d

tf

(3) .for each

where

(i,

j) e

{1, .,,,

ml xU,

...,

n} 'ii4

@f

,...,uf,,, ,f ,.'.,vf,) vj -u! =cf,, (t,j)

e A

then X is a Pqreto transport plan

for

the multicriteria transpottatiol,problem'

(MTP).

:

,

,.;

Proof. rf

x

is a potential plan for the pfobrem'(r¿), rhen it is an óptimal plan

eachk€

I1,..,,p)

let @f

,,...,r!,,

rf

,...,vf,)

beasolutionof thesysrem

4

df¡

=,f -r! -rf¡

is a solulion oJ'the system

(4)

We denote by (5)

uf¡=rj-u!-cf,<o

ul -r! =rf, {i,j) e

A

ef¡

='j -

uf

-

"!,

(4)

6,

We compare kto p.

a)

If

k = ¿r, then

x

is a pareto transporf pran for the rnurticriteria transporta_

tion problern (MTp) and the algoritirmistops.

b) If & < 2, then we go te step 7.

7.

We put

Af =le, Ðe

Afr-t

:uf,

=Oy.

8.

We cornpare

¿f I ¿

to the empty se[.

a)

If Af \.A=Ø,

then

X is

a pareto transport pran f.or the murticriteria transportation problem (MTp) and the algorithm

srops.

:

b)

Il

Afr

\A*Ø,

then we go to step 9.

and we define

7 Mul,tiç^ritcriaTransportatien P¡.ohlenls

r69

0 = min{,rü : (i,

j) e

L_},

which is attained, forexample, in the,cell

(t,

r). From the elements.r¡ which ccrrrespond to the semichain

L-

we substract the number 0, and to the ele_

ments -{iJ corresponding to the semichain L+ weiadd the number 0. The other elements, which are not in the cycre ,(, remain thè same.

we

obta.in a new transport plan X to which we attach the.set

A:=

Av {(r,s)} \

{(u,¡)}.

We go back to step 3.

In orcler to illustrate the above algorithnr we nulnerical example.

conclude with' the following E.tample. Ler us consider rhe (MTp) problem given by Table I .

In thiscase wehavep

=3,m=3,1=4. Weputit= i

ancl

A* =ll.ä.:l

x

{ I , 2, 3, 4 }. An acyclic oprimal rransporr plan X fbr rhe problern iZ:,; is

Liana Lupga, Eugenia D-uca artd Dorel l. Duca

(6) ; B=Aw1(r,s)) 'r{(ø,¡)}

Let us denote by

M

the set of the cells which are not in the cycle 'é. Then, fot

each k

e

{

l,

.... 4), we have

fr(Y)=2,,.¡ur,fit¡¡ +Lç,¡rt

c!¡ti¡ +

),,.r=r

'fù¡¡ =

=Lu,i*'r''|¡''¡ *2,,,¡*r

''f¡Q'¡+ 0)+

Itr,;=.-

r:'f

(x, -

0) =

=

l*(X)-

0of,, =

fk6).

Calculating

fr*i(),

we obtain

I

q *íY ) =

D

¡,. ¡ p

r'''¡*t

I ¡

* 2

r,.,* r' tl¡n' y'¡

* ),,.,

=

t

cf¡+ | v', =

=E¡,,¡*r'lit', +2,,,,Frcfl*t

{x',

*

9; +

Iri¡t *r-'l*'

(x¡

-

0) =

= .fqrr(x)_ 0crÍ.nt <.f,t*Jx).

Hence, the transport plan X is not a Pareto one'

E

3. THE ALGORITHM

Using theorems 2.1 and2.2, we can state the following algorithm for the determination of a Pareto transport plan for multicriteria transportation problems,

Algorithm 1.

Weputk- I

and Ap =

[1,...,rn] x {1,.,.,n}.

2.

One determines an cyclic optimal transport plan X = (.r¡) for the problem

(I¡)

and we attach to

it

a set A

e

Sel(,I).

3.

We determine a Potential system

(u(,...,

uf,,,

rf ,'..,vf,)

given by (1)

4.

We consider

af¡

='j -

u!

-'!¡

for each (i:

j)e

Ahl .

5,

tWe compare to'zero each of the

numbers i

'

.:

crf

.

(,.

/)€ Af-' \

A

6

(5)

9 Multicriteria Transporration Problenis l7t ' Since there

is

(1, 2) ,€

4j(

'\

A

so thar oiz =

0

and o¡1 S

0 for

each (i,

j)

e

.

A.l,'

\ A

and k < p, we go ro step 7. We have

Arx =

{(t, l), (1,2),(1,4),(2,/¡,12,4¡,(3,

l), (3, 2), (3, 3)}, since

A| '\A

+

Ø

we put fr = 3 and go to srep 3. A solution of the system (7) is

(r? ,

r),r¡,, ,i,

u!, ul, uf ) = {0, -5, 4, s, 7, I I , t3).

There is ( 1, 4) e

Ai

'f

¿

such rhat ol+ = 9 > 0. Then we go to step 10. We have

, L*= {(1,4),(2,2),(3,1)},L-=

{(1,

l), (2,4),(3,2)},

0=40'

A= 1lt,

t),

(r,4),

(2,2),(2,4), (3, r), (3,3)),

and

(8)

X-

A solution of the system (7) is

(ul,u),ul,rl,rl,

ul, vl¡ ={0,

4, 4,s,

-2,

n,

4).

Since

af.<0, forall (i,7)

e A.?

tA,wehavetharXgivenby (g)isapareto

transport plan for the multicriteria transportation problem given by Table L

REFERENCES

f lf R. Avram-Nitchi, Abour the Mulriple Ob.jet'tive Fuzzl Operoîorial Transportrtrion problems, Seruinarul itinerant de ecuatii functionale. aproximare si convexitate. Cluj-Napoca, 2l-26 mai,

1991,14.

[2] A. Baciu, A. Pascu, E. Puscas, Appliculions oJ'tlu Opcrutklts Researt'h (in Roumanian), Bu- curesti, Ed, Milirarã, 1988.

[3]A. Gupta, S. Khanna, M. C. Puri. Paradoxical Situations in Transportation Problems. Cahier.s du C.E.R.O., 34,1 (t992).3j49.

l4l D. S Hochbaurn, S. P. Hong. On the Complexity of, the P¡oduction-Transporrarion Problem, SIAM J. Optimizution,6, I (1996),250-264.

[-5] L. Lupça, E. Duca, D. l. Duca, On the Structure of the Set of Points Dominared and Nondomi- nated in an Optimization Problem. Revue tl'uttul. nun. et lo théorie de I'appro.rination,22, 2 (ì993). t9.1-199.

l6l L. Lupça, D. I' Duca, E. Duca, On the Balanccd and Nonbalallced Vector Optimization Problems.

Ret'ue d'anal.,tut,r. et lu th¿jorie de I'up¡tro.rinution.24. / (1995). l12-124.

l7lL. Lupsa. D. f. Duca, E. Duca, Equivalence Classes in the .Ser of Efficienr .solutions. ¿r,¡r¿,

I'uttul. ttutt¡ et lu tltét.,t'ìe de l'up¡tnttirttutiott.25, i -2 ( 1996), l2l_136.

62 0 040 0tz} 0

14

89 0123

0 Liana Lup¡a, Eugenil Duca antl Dorel l; Ducu

Tohlc I

170

We have

X=

48 0

0,54

103

33, 0

0

08983

0

A = t(1,

l),

(1,4),

(2,1),(2:2),(3,2):

(3, 3)Ì.

A solution oi the sYstem (7) is

@l, rL, rå, r1, vi. v{, u}) = 10, 2,0, 4. 3.

Since. there

is (1,,2)

A9

\A

such

that ,ol, =0

and' 6¿li

S0 tbr

each

(i,

j)e

Ap

\;4,

and k < p. we go to step 7: We have ; '

. : ': | ,.1

Since

Af.\ A+Ø

w:èput k = 2 and we go to step 3. A.solution of the system (7) is

@?,r?,r1,r?,rî.,r1,v1¡

= 10, -1, -3, 3,

l,

3, 8).

Since rhere ]s (2, 4) e

Af \,4

sttch that afa =

4>0,

we go to step 10. we have '.!.

L* = {(1, l), (2, 4)} and L- = t(2,

l),

(1, 4)}, 0 = 54 and ].-.:

ti,

,

A = {(l

,l),(2,l),(2.2),(2,4),(3,1),

(3,2)' (3' 3ì}

A solution of the sYstem (7) is

l'

@?, uì, uî, t?, rzz',

ul,vl

) = 10. - l, -3, 3,

l,

3, 4).

Sincethereis(3,

l)ee| \A

sothat

aït=4>0,

wegot,o$tcp l0.WchavcL+

=

l(2,2),(3.

l)1, L- = l(2,1). (3' 2)) and 0 = 49' The newA is

A = {(l , l), (2, l), (2.2), (2,4), (3,

l),

(3,2), (3', 3)}.

. .; , : i

A solution of the sYstem (7)

is

-

- 1 1 I 1 I ,'

¿ii'', (rrf..{r?2,l/il,r'i.vl,t'','.,ì)-(0.

. 3;

l,

3.5,7, 8).

l'12 '102

l5l t22 83 ,54

4

t343567981

(6)

REVUE D'ANALYSE NUMÉRIQUE T'I' NR.THÉ.ORIE DN L'APPROXINIATION -Iomc

28, N" 2, 1999, pp.

t7!l??

A NEW PROOF FOR THE APPROXIMATION

OF UE LOG-FUNCTION BY KANTOROVICH'

POLYNOMIALS IN THE ¿2-NORM

VOLKtsR MAIER

,t 1

Twenty years ago the author solved the saturation problenr

tbr

the Kan- torovich Polynomials

in

the

L;norm (cf.

[2]). The mosr

difficult

part

of

this saturation problem had becn the proof of the direct theorem and hcrein especially the estimate for the approximation of the Log-f'unction. In the meantime this re- sult was often used in other papers.

we

are now able to give a new and'essentially shofter proof with a smaller constant of the estimate

ll4, Iog- tosllr =

o(rri

+ D=r

).

:

The approximation, in rhe L,,-nonn ior ¡t

> I

is due to RiemenschnéiiJer [-j], who therein uses an inec¡uality of the proof for the

L;norm Il].

Now we are also

able to give a very short form fbr Riemenschneider's proof.

For an .f

e

L1U.),1* =

(0,'l).

thè nfft,Kanrorovich Polynomial on

/*

is de- fined by

,.

, P,,(f'" .t) = with the kernel Kr(,.-) given by

ff

r,,r,;, t).t:'\t)dt

'] :

K,, (.t, f ) =

É

p,,,* (".) (n + l)xt^(t ),

(-=0

where Xt,

denotes

the

characteristic function

on

I k'.=

k k+l n+l'¡r+l

and

p,,

{r)=[,ll'-,'

X )u

-(

Let

F(.r¡ =

J'

.t'Q)dt , then there is a relation between the Kantorovich and the

199 I AMS Subject Classilìcation: 4lAl0.

t't2 Liana Lupsa, EugeniaDuca and Dorel l. Duca t0

f gl L. LupSa. D. I. Duca, E. Duca, On Bicriterial Transportation Problenrs. Ret'ue d'unttl,,M,n, et la théorie tle I'a¡tproxintttion,2T, / (199S), àì-90'

t9l V. V. podinovsky, V. D. Noghin, Pareto-Optinul Solutiotts t¿f ' Mulrit'riteria Problents (in Russian), Moscow, Nauka, 1982.

tl0l M. Zcleny, Multiple criteriu Dat'isiott lt(akittg; New York,,McGraw-Hitl 1982'

illi

S. f. Zuhóvicki, L. l. Aud..uu, Lùear und Cont,e-r Progrununin¿4 (in Russian), Moscow.

Nauka

1964.

:

Received September l0r 1998 Liatrtt Lupça and Dorel L Duca Faculh' o.f Mathenatics,

" Babe ¡ - Bolt tt i " U ni ¡'e rsit )' 3400 CI ttj - N aplcu, Ronuilis,

e-nuil:

dduca@ math.urcluj.ro Eugenia Ductt Departme nt o.f M at he maticu

Technical Universim^

-1400 Clui'Napoca Ronrutùrt e-mail:

educa@ nta¡h. utclui. ro

Referințe

DOCUMENTE SIMILARE

(1 − α)C, with α ∈ (0, 1), G, C being the geometric and anti-harmonic means, and we find the range of values of α for which the weighted mean is still greater or less than

The aim of this paper is to characterize the sets of weakly-efficient solutions and efficient solutions for multicriteria optimization problem involving generalized unimodal

In Section 4, for the particular case of the vector maximization set-valued fractional programming problem, we obtain some characterizations properties of efficient and

Lups ¸a , Bicriteria transportation problems, in Research on Theory of Allure, Approximation, Convexity and Optimization, Editura SRIMA, Cluj–Napoca, Romania, 1999, 52–71.

Here we present some of our existence results for the efficient (Pareto minimum) points which generated their corresponding implications for Pareto maximum points

Yanushkevich, The Conditions of Pareto' Optimality in a Discrete Vector Problem on a System of Subsels, Comp.. Brucker, Discrete Parameter Optínizalion Problem

Hackbusch, Integral Equations Theory and Numerical Treatment, Birkhäusor Verlag, Basol-Borlin, 1995.. Micula, Funclii spline Si aplicalii,

That is why, in Talisse view, the argumentation of Habermas’s theory concerning the legitimacy of political decisions is circular: “it justifies democracy only to those who