REVUE D'ANALYSE NUMÉRIQUE
EI'DE
THÉORIE DE L'APPROXIMATION Tome 28, Nu 2, 1999, pp. 16!172AN ALGORITHM FOR MULTICRITERIA
TRANSPORTATION PROBLEMS
LIANA LtiP,SA, EUCENIA DUCA and DOREL L DUCA
1. PRELIMINARIES
It is
known that many applicationsof
rinear programmingin
managing economic processes come to the solving some transportationprobl.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 typeA1 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
-1
'
IVlulticriteria Transpoltatioñ Prnblenrsf*(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 by4,,,
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'bys.
A transport plan Xe
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 wewill
denote by (1r) (ke
(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 numbersU1,,'., \'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 byffîP),
a multicriteria linear programming problemin
which the objective function is a vector function.f =([r ...,1) '
R"rx'r-+
R.P, given byM 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 }. LetAþ = {Q,
ìe
Ag:o,rl = 6¡We presume that ør?
10,
for all (i,7)eA|
, 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 whichaf
<0
forall
(r,j)e
Aþ) ,wedenore byAþ
=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 thtato!,=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 pktny
having the propertythat
and
.fi(Y) =
fog)
for each ke lt,
...,ql
5
if ,t*tU) < ,fq*t(X), tvhich tneans that X is not pareØ_fficient
.
e
This wills
r) and weotedly
+ form a semichainrl:ÌXonil:
nichain L_. We analyse the elements xry
of the transport pran
x
situated in the semichainL
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¡}x¡
20,
(i, j)e.{1,...,
mlx{1,..,,n}.LetX=(x¡¡)be
an acyclic transportplan and letAe
Sel(X). Foreach ke
{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 ke
{1, ...,p}.
The following result gives a sufficient condition for tbePareto-efficiency:
:THEoREM 2.1.
kt
fte
{ 1, ...,pI. lf
X is a potential plan of the problem (T¡,),with respectn
Ae
Sçl(Ð a4dtf
(3) .for each
where
(i,
j) e
{1, .,,,ml xU,
...,n} 'ii4
@f
,...,uf,,, ,f ,.'.,vf,) vj -u! =cf,, (t,j)
e Athen 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 planeachk€
I1,..,,p)
let @f,,...,r!,,
rf,...,vf,)
beasolutionof thesysrem4
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
Aef¡
='j -
uf-
"!,
6,
We compare kto p.a)
If
k = ¿r, thenx
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 putAf =le, Ðe
Afr-t:uf,
=Oy.8.
We cornpare¿f I ¿
to the empty se[.a)
If Af \.A=Ø,
thenX is
a pareto transport pran f.or the murticriteria transportation problem (MTp) and the algorithmsrops.
: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 semichainL-
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.setA:=
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
anclA* =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, foteach k
e
{l,
.... 4), we havefr(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 obtainI
q *íY ) =D
¡,. ¡ pr'''¡*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 Ae
Sel(,I).3.
We determine a Potential system(u(,...,
uf,,,rf ,'..,vf,)
given by (1)
4.
We consideraf¡
='j -
u!-'!¡
for each (i:
j)e
Ahl .5,
tWe compare to'zero each of thenumbers i
'.:
crf
.
(,./)€ Af-' \
A6
9 Multicriteria Transporration Problenis l7t ' Since there
is
(1, 2) ,€4j(
'\A
so thar oiz =0
and o¡1 S0 for
each (i,j)
e.
A.l,'\ A
and k < p, we go ro step 7. We haveArx =
{(t, l), (1,2),(1,4),(2,/¡,12,4¡,(3,
l), (3, 2), (3, 3)}, sinceA| '\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
1489 0123
0 Liana Lup¡a, Eugenil Duca antl Dorel l; DucuTohlc I
tì 170
We have
X=
48 0
0,54103
33, 0
008983
0A = 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
suchthat ,ol, =0
and' 6¿liS0 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
sothataï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 isA = {(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
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 Polynomialsin
theL;norm (cf.
[2]). The mosrdifficult
partof
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 estimatell4, 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 theL;norm Il].
Now we are alsoable 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 byff
r,,r,;, t).t:'\t)dt'] :
K,, (.t, f ) =É
p,,,* (".) (n + l)xt^(t ),(-=0
where Xt,
denotesthe
characteristic functionon
I k'.=k k+l n+l'¡r+l
andp,,
{r)=[,ll'-,'
X )u-(
Let
F(.r¡ =J'
.t'Q)dt , then there is a relation between the Kantorovich and the199 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