Multiflots Dynamiques de Cout Actualisé Minimal

51

MULTIFLOTS DYNAMIQUES DE COUT ACTUALISI~

p a r

Michel M I N O U X

Ancien 61bye de l 'Ecole Polytechnique, ing6nieur contractuel *

MINIMAL

R~SUM~. - - On dtudie dans cet article les mdthodes permettant de ddfinir une politique optimale d'extension d'un rdseau de tdldcommunications (rdseaux tdldphoniques, rdseaux de tdldvision, rdseaux de transmission de donndes, etc.). Le probl~me est d'abord formuld dans le langage de la thdorie des graphes, puts rdsolu, clans un cas particulier, grace ~ la programmalion dgnamique. Deux mdthodes de rdsolution approchde sont ensuite proposdes pour le cas gdndral. Les rdsultats obtenus sur des exemples pratiques permettenl de conclure qu'une politique basde sur un crit~re dconomique ~ mogen terme est toujours prdfdrable d~ une politique procddant par

drapes successives en recherchant d ehaque dtape un opt imum dconomique d court terme.

PLAN. - - �9 I : Introduction. �9 I I : P o s i t i o n d ~ p r o b l { } m e P I I .1 . Les donndes de base; I I .2 . Rdseaux admissibles et m-admissibles; I I .3 . Taux d'actualisation et co~ts actualisds ; I I .4 . D~finition du probl~me. �9 I I I : R d s o - l u t i on du probl~me P' par programmation dynamique I I I . 1 . Ddfinition du graphe sdquenliel -G ; I I I . 2 . Caractdrisation du chemin optimal dans G; I I I . 3 . Une condition suffisante d'optimalitd pour P. �9 I V : Rs d u p r o b l ~ m e P IV.1. Un exemple; I u Premiere mdthode; IV.3. Seconde md~pde.

�9 V : Conclusion. Bibliographic (12 r6f.).

I . I N T B O D U C T I O N

R e c h e r c h e r un m u l t i f l o t d y n a m i q u e de c o o t a c t u a -

lisd m i n i m a l es t l ' o b j e c t i f e ssen t ie l en m a t i ~ r e de

p l a n i f i c a t i o n des r d s e a u x de t d l 6 c o m m u n i c a t i o n s ( rdseaux t d l d p h o n i q u e s u r b a i n ou i n t e r u r b a i n , r d s e a u x

de t616vis ion, de t r a n s m i s s i o n de donndes , etc.) .

P o u r l ' e x p o s d du p r o b l b m e gdn6ral , n o u s r e n v o y o n s [1]. R a p p e ] o n s s i m p l e m e n t q u ' i l s ' a g i t d ' a p p o r t e r

u n e r~ponse h c h a c u n e des t ro i s q u e s t i o n s s u i v a n t e s :

Q 1 : O h i n v e s t i r ? ( d d t e r m i n a t i o n de la s t r u c t u r e o p t i m a l e du g r a p h e des e x t e n s i o n s ) .

Q 2 : Q u o i i n v e s t i r ? (par ro t t o u s les m a t d r i e l s de

t r a n s m i s s i o n u t i l i s ab l e s , que l s s o n t c e u x qu i p e r m e t t e n t de r d p o n d r e ~ l a d e m a n d e de la fa~on la p lus d c o n o m i q u e ) .

Q 3 : Q u a n d i n v e s t i r ? ( d ~ t e r m i n a t i o n des d a t e s op t i -

m a l e s des n o u v e a u x i n v e s t i s s e m e n t s - - i n f ra - s t r u c t u r e e t e x t e n s i o n s - - su r c h a q u e a r t~re du r~seau) .

C e p e n d a n t , n o u s a v o n s m o n t r d d a n s [1] que la t r6s

g r a n d e t a i l l e des p r o b l b m e s rdels ne p e r m e t pas la

r e c h e r c h e de l ' o p t i m u m e x a c t (il s ' a g i t de p r o g r a m m e s

en H o m b r e s e n t i e r s c o m p o r t a n t des d i za ines de mi l l i e r s

de v a r i a b l e s en t i~res ) e t la m d t h o d e de rd so lu t i on a d o p t d e se d d c o m p o s e en d e u x p h a s e s :

Phase 1 : r~ponse h Q 1 e t h Q 2 ( p l a n i f i c a t i o n h

l o n g t e r m e ) . L e p r o b l ~ m e d y n a m i q u e es t r a m e n d h

un p r o b l b m e s t a t i q u e de m u l t i f l o t h cof i t m i n i m a l ,

a v e c f o n c t i o n s de cof i t c o n c a v e s [2,4].

Phase 2 : r dponse h l a q u e s t i o n Q 3 ( p l a n i f i c a t i o n

h m o y e n t e r m e ) . On r d s o u t le p r o b l ~ m e d y n a m i q u e ( d a t a t i o n des i n v e s t i s s e m e n t s ) , c o m p t e t e n u des

r d s u l t a t s o b t e n u s d a n s l a phase 1 [5].

Ce t a r t i c l e sera consac r6 h la r 6 so lu t i on des p r o -

b l6mes sou levds au cou r s de la phase 2. Les r 6 s u l t a t s o b t e n u s en phase 1 ( p l a n i f i c a t i o n h long t e r m e ) s e r o n t

donc cons id6r~s c o m m e des donndes de base , h s a v o i r :

- - la s t r u c t u r e du rdseau des e x t e n s i o n s ( l i s te des a r t~res f a i s a n t l ' o b j e t de n o u v e a u x i n v e s t i s s e m e n t s

dans le m o d u l e h l o n g t e r m e ) ,

- - su r c h a q u e a r t b r e du rdseau p rdc~den t , l a suc- cess ion des i n v e s t i s s e m e n t s p r d v u s en p r ~ c i s a n t la

n a t u r e des m a t d r i e l s de t r a n s m i s s i o n ut i l isds , l e u r

c a p a c i t ~ e t l e u r cof i t .

I I . P O S I T I O N D U P B O B L ] ~ M E

I I . 1 . L e s d o n n 6 e s d e b a s e .

On se d o n n e un g r a p h e G = [X, U] non o r i en td off

X = {xl , x 2 , ..., XN} es t l ' e n s e m b l e des nceuds e t off U c X 2 es t l ' e n s e m b l e des a r~ tes (] U[ = M) . L ' i n t e r -

va l l e de t e m p s [0, T] (p~r iode d ' ~ t u d e ) es t ddcoupd

en T i n t e r v a l l e s q u e n o u s s u p p o s e r o n s tous , p o u r

s impl i f i e r , de du rde dgale h l ' u n i t d (en g6n~ra l : u n e

* A u CNET-Issy, groupement R E C H E R C H E E T C O N T R O L E D E C O M M U T A T I O N , d6partement I N G I ~ N I E R I E D E S SYSTI'~MES D E

C O M M U T A T I O N .

1/8 A. TELEC., 30, n ~ 1-2, 1975

5 2 M. M I N O U X . -- M U L T I F L O T S D Y N A M I Q U E S D E C O U T A C T U A L I S I ~ M I N I M A L

a n n 6 e ; l ' i n s t a n t l = 0 r e p r d s e n t e a l o r s l ' a n n d e o r i g i n e

e t t = T l ' a n n 6 e horizon d e l ' 6 t u d e ) . A e h a q u e i n s -

t a n t t (0 ~< t ~ T), le g r a p h e G e s t p a r c o u r u p a r

K = N ( N - - 1 ) / 2 ) r io t s inddpendants n o t d s ~0i~. p o u r

i = 1, ..., N ; j = 1, ..., N e t i < j . P a r c o n v e n t i o n ,

le r io t ~01~. a p o u r e x t r d m i t 6 s x~ e t xj (x~ ~ X , xj ~ X )

e t l ' a b s e n c e d ' o r i e n t a t i o n f a i t q u e c h a c u n de ces n c e u d s

p e u t ~ t r e c o n s i d d r 6 a u s s i b i e n c o m m e source q u e

c o m m e pui l s . D ' a u t r e p a r t , l a v a l e u r de c h a q u e

r o t ?i~. ( n o t 6 e v(~0~j)) e s t u n e d o n n d e i m p o s d e dtj( t) h

e h a q u e i n s t a n t l (0 ~ t ~ T).

N. B. - - P o u r t donn6, 6tre nul les ; on peu t t r6s

d~j(t) -- 0

ce qui signifie simplement dans le probl6me.

cer ta ines va leurs dfj(t) p e u v e n t b ien avoi r aussi :

(Vt = 0 ..... T),

que le riot ?t~. n ' i n t e r v i e n t pas

N o u s s u p p o s e r o n s q u e les d~j(t) s o n t des n o m b r e s

e n t i e r s e t q u e l ' o n a : d i j (0 ) ~< d~j(1) ~< ... ~< d ~ ( T )

( V i = 1 . . . . . N ; V j = 1 . . . . . N ; i < j ) .

A c b a q u e a r~ te , u ~ U d e G, o n f e r a c o r r e s p o n d r e

T v a r i a b l e s n o n n 6 g a t i v e s e t e n t i 6 r e s :

Yu(1) , Yu(2) . . . . . Y u ( T ) ,

r e p r ~ s e n t a n t la c a p a c i t 6 i n s t a l l e e s u r l ' a r f i t e u

c h a q u e i n s t a n t de l a p d r i o d e [1, T]. L a c a p a c i t 6 in i -

t i a l e Yu(0) de l ' a r ~ t e u ( c o r r e s p o n d a n t h l ' i n s t a n t

t = 0) e s t u n e d o n n 6 e d u p r o b l ~ m e . E n f i n , p o u r

c h a q u e a r ~ t e u ~ U de G, o n se d o n n e le co f i t d ' i n s -

t a l l a t i o n ~Pu(Yu) de l a c a p a c i t 6 Yu �9 N o u s s u p p o s e r o n s

q u e :

- - les f o n c t i o n s r s o n t d6 f in i e s p o u r Yu~[O, Yu]

off Yu es t u n e b o r n e s u p e r i e u r e d u r io t s u r l ' a r ~ t e u

(Vt = 0, ..., T). R e m a r q u e r q u e la v a l e u r :

Y~a= = ~ d~j(T) e s t u n e b o r n e s u p 6 r i e u r e a d m i s s i b l e

p o u r t o u t u ~ U ;

- - les ~ u ( Y u ) s o n t des f o n c t i o n s n o n n 6 g a t i v e s e t

c r o i s s a n t e s ( a u sens l a r g e ) d e l a c a p a c i t 6 i n s t a l l 6 e Yu �9

Co5~ r 1 6 5

I i I

I I I I

A _ _ I O ' Yu (0)

J -I I J I i t I I

I i i J Capac;t~

Yu

FIc,. 1. - - Sur une ar~te u, le coflt ~Pu(Yu) est une fonetion non ndgative croissante (au sens large) de la capacit6 totale installde (g6n6ralement fonctions lindaires par morceaux et/ou en escalier). Comme la capacitd exis tante h l ' i ns tan t 0 ne

coflte rien, on a ~Pu(Yu) = 0 pour 0 ~ Yu ~ Yu~0).

Ces h y p o t h 6 s e s s o n t t r 6 s g d n 6 r a l e s (e l les e x p r i m e n t

s i m p l e m e n t q u e l ' i n s t a l l a t i o n d e t o u t e c a p a c i t 6 s u p -

p l d m e n t a i r e e s t c o f i t e u s e ) e t r e c o u v r e n t le cas p r a -

t i q u e le p lu s i m p o r t a n t des f o n c t i o n s l i n6a i r e s p a r

m o r e e a u x e t des f o n c t i o n s en esealier (Fig . 1).

II.2. R 6 s e a u x admiss ib les et m-admiss ib le s .

E n a s s o c i a n t a u x ar(~tes de G = [X , U] des c a p a -

c i t6s Yx , Ye . . . . , Y M , o n d 6 f i n i t le rdseau R = [ G, Y]

e t le v e c t e u r Y = [ Y 1 , Y2 . . . . . Y M ] T e R M+ s e r a

a p p e l d vecteur descr ip t i f d u r 6 s e a u R.

E t a n t d o n n ~ d e u x r 6 s e a u x R e t R ' de v e c t e u r s des -

c r i p t i f s Y e t Y' o n d 6 f i n i t l a r e l a t i o n de dominance

( a u sens l a r g e ) n o t 6 e oc p a r :

Y__oc Y ' ~ Yu <~ Y ' u ( V u c U) .

O n d i t q u e R ' d o m i n e R ( a u sens l a rge ) , ce q u e

l ' o n n o t e r a p a r e x t e n s i o n : R o r R ' .

O n d 6 f i n i t de m ~ m e u n e r e l a t i o n de dominance

stricte n o t 6 e oc :

Y or Y ' <::> Yu <- Y ' u ( V u ~ U),

e t :

=lu o@ U t e l q u e : Yuo < Y ' U 0 "

P o u r 0 ~< t ~< T, le r 6 s e a u R ( t ) = [G, Y(t) ] de

v e c t e u r d e s c r i p t i f Y( t ) = [Yl ( t ) , Y2(t) . . . . . YM(I) ] T es t

d i t admiss ible s ' i l e x i s t e u n m u l t i f l o t q~ = [?~j] h

c o m p o s a n t e s e n t i ~ r e s , c o m p a t i b l e a v e c les c a p a e i t f s

Yu( t ) e t t e l q u e :

v ( cp~ j ) - di j ( t ) (Vi e t Vj , i < j ) .

N. B. - - La c o n t r a i n t e d ' i u t @ r i t 6 sur les composan t e s des riots q~ij i n t e r v i e n t darts la p l u p a r t des probl6mes pra- t iques ; c e p e n d a n t , t o u t ce qui su i t se gdn6ralise sans diM- cult6 au eas o/1 on dds i re ra i t s ' en af f ranehi r , m o y e n n a n t que lques hypo th6ses s u p p l d m e n t a i r e s , en par t icu l ie r sur les fonc t ions ~ u .

L e r 6 s e a u i n i t i a l (h l ' i n s t a n t t = 0) R ( 0 ) = [G, Y(0 ) ]

e s t s u p p o s 6 a d m i s s i b l e .

Ceci 6 t a n t , n o u s d i r o n s q u ' u n r d s e a u R = [G, Y]

e s t m i n i m a l - a d m i s s i b l e ou , p l u s b r i 6 v e m e n t :

m-admis s ib l e si t o u t r 6 s e a u R ' = [G, Y ' ] t e l q u e

Y ' o c Y ( d o m i n a n c e s t r i c t e ) n ' e s t p a s a d m i s s i b l e .

N o u s v e r r o n s q u e les r 6 s e a u x m - a d m i s s i b l e s j o u e n t

u n r61e i m p o r t a n t d a n s n o t r e ~ t u d e .

II.3. T a u x d 'ac tua l i sa t ion et coht s actual is6s .

P a r d 6 f i n i t i o n , le co f i t a c t u a l i s 6 ( en f r a n c s de

l ' a n n 6 e 0) d ' u n e s u i t e d ' i n v e s t i s s e m e n t s de v a l e u r s :

I (1) , I (2) , ..., I ( T ) r6a l i s6s a u x i n s t a n t s t - - 1, 2 . . . . , T

e s t :

C a - - I (1) + I (2) F -..-4- I ( T ) _ (1 + "r) (1 -)- v) 2 (1 + ~)T

A. T~LEC., 30, n ~ 1-2, 1975 2 / 8

M. M I N O U X . -- M U L T I F L O T S D Y N A M I Q U E S D E C O U T A C T U A L I S I ~ M I N I M A L 53

Le p a r a m ~ t r e T ( g 6 n 6 r a l e m e n t compr i s e n t r e 0,1

e t 0,2) es t appe l6 laux d'actualisation. I1 d 6 p e n d d ' u n

g r a n d n o m b r e de f a c t e u r s d c o n o m i q u e s te ls q u e : le l o y e r de l ' a r g e n t , le t a u x de c ro i s sance de l ' e n t r e -

pr ise , e tc . I1 se ra cons idd rd ici c o m m e u n e donnde

e x t e r n e du p r o b l 6 m e .

11.4. D6finition du problSme (P).

Le p r o b l ~ m e du m u l t i f l o t d y n a m i q u e de cof l t a c t u a -

lis6 m i n i m a l es t de d 6 t e r m i n e r les v a r i a b l e s Yu(l)

(Vu ~ U, t = l , ..., T), v d r i f i a n t les e o n t r a i n t e s :

( I I .4 .1 ) : les T r 6 s e a u x R ( 1 ) = [G, Y(1)],

R(2 ) = [G, Y(2)] ,

R ( T ) = [ G. Y(T) ],

d o i v e n t ~tre a d m i s s i b l e s .

( I I .4 .2 ) : p o u r t o u t t = 1, ..., T, on do i t a v o i r :

Y ( t - 1) or Y(I) ( c o n t r a i n t e de d o m i n a n c e la rge) ,

e t m i n i m a l i s a n t le cof l t a c tua l i s6 :

�9 = E E O u Y u ( ( l ) ) - - O u ( Y u ( l - - 1 ) ) ,

t = l . . . T uC---U ( 1 - 7 T ) t

�9 r e p r 6 s e n t e le co f i t a c t u a l i s 6 t o t a l de d6ve lop -

p e m e n t du r6 seau su r l a p 6 r i o d e [0, T].

L a c o n t r a i n t e ( I I . 4 . 2 ) es t i m p o r t a n t e d ' u n p o i n t de r u e p r a t i q u e ; el le e x p r i m e en effet q u ' u n i nves t i s -

s e m e n t e f fec tud ~ l ' i n s t a n t t n e p e u t p lus ~tre r emis en cause au con r s des ann6es u l t6 r ieures . C o m m e la

p r i n c i p a l e d i f f icu l t6 d u p r o b l ~ m e r6s ide dans la pr ise

en c o m p t e de c e t t e c o n t r a i n t e , nous c o m m e n e e r o n s

p a r 6 tud i e r le p r o b l ~ m e ( P ' ) d 6 d u i t de (P) en r e l a x a n t l a c o n t r a i n t e I I .4 .2 . O n p e u t a lors ca r ac t6 r i s e r de

fa~on s imp le u n e s o l u t i o n o p t i m a l e de (P ' ) e t en d6du i re une c o n d i t i o n su f f i san te d ' o p t i m a l i t 6 p o u r (P).

Ddmonstralion.

S o i e n t T r 6 s e a u x R(1) , R(2) . . . . . R ( T ) de v e e t e u r s

d e s e r i p t i f s Y(1), Y(2), ..., Y ( T ) f o r m a n t u n e so lu t ion

o p t i m a l e de (P ' ) de cof i t (I)*, e t s u p p o s o n s p a r e x e m p l e q u e B( t ) ne so i t pa s m - a d m i s s i b l e . Cela s ignif ie q u ' i l

e x i s t e R' m-admissible de v e c t e u r d e s c r i p t i f Y' e t te l

q u e Y ' ~ Y(I). So i t ~ ' le cof l t de la so lu t ion :

{R(1), R(2) . . . . . R ( t - - 1), R', R(I + 1) . . . . . R (T)}

O n a :

(I)' - - ( I ) * =

d ' o h :

O ' - - q ~ * =

E Ou(Y'u) - - O u ( Y u ( t - - 1)) . E u (1 + T) t-~ +

y , X O u ( V u ( l + 1 ) ) - - O n ( ~ . ) . ~u (1 + T) t

E Ou(Yu(l)) - - O u ( Y u ( t - 1)) .Eu (1 + T) t-1

E Ou(Yu(t + 1)) - - Ou(Yu(t)) , , ~ u (1 + T)t

E O . ( r ~ ) - - o ~ ( Y ~ ( l ) ) uEU (1 + =)t-1 -}-

Ou(Yu(t)) -- aPu( Yu) ~ u (1 + : ) t

E ~u( u ) - - ( I )u (Yu( t ) ) 1 . = . e v (1 + =)t-1 I - - 1 ~

C o m p t e t e n u du f a i t q u e les Ou(Yu) s o n t c ro i s san tes

(au sens la rge) e t q u e T > 0, on a : O ' - - O * ~< 0. C o m m e on ne p e u t pas a v o i r O ' - - O* < 0 (d ' apr~s

l ' o p t i m a l i t 6 de O * ) , n @ e s s a i r e m e n t O ' = (I)*. E n

p r e n a n t s u c c e s s i v e m e n t t = 1, ..., T e t en r @ d t a n t l ' o p d r a t i o n , c h a q u e fois q u e l ' o n r e n c o n t r e un r6seau

q u i n ' e s t pas m - a d m i s s i b l e , on o b t i e n t u n e n o u v e l l e

s o l u t i o n o p t i m a l e , de m ~ m e cof i t O* e t c o n f o r m e

l ' 6 n o n c 6 du t h 6 o r ~ m e 1.

Bernarque.

La propridt6 ne se gdndralise pas au cas du probl6Ine (P) ; en effet, darts la d6mons t ra t ion ci-dessus, on n ' a pas n@es- sa i rement Y(t - - 1)o~ Y'.

O n d d d u i t du thdor~me 1 le co ro l l a i r e :

III. B~,SOLUTION DU PROBL~.ME (P') PAR PROGRAMMATION DYNAMIQUE

Corollaire.

On ne p e r d pas l ' o p t i m a l i t 6 en l i m i t a n t la r e c h e r c h e de la s o l u t i o n de (P ) ' a u x su i t e s {R(1), R(2) . . . . . R (T)}

c o m p o s d e s de r d s e a u x m - a d m i s s i b l e s .

N o u s m o n t r o n s d a n s ce e h a p i t r e c o m m e n t le p ro-

b l a m e (P ' ) ( p r o b l ~ m e (P) sans la c o n t r a i n t e I I .4 .2)

p e u t se f o r m u l e r d a n s le l a n g a g e de la p r o g r a m m a t i o n

d y n a m i q u e [6], ou e n c o r e e o m m e la r e e h e r e h e d ' u n

p lus c o u r t c h e m i n d a n s u n g r a p h e s6quen t i e l G. P o u r

d6f in i r les s o m m e t s de G ( e n s e m b l e des 6ta ts) , nous u t i l i s e rons un r d s u l t a t p r61 imina i re .

Thdor~me I .

P a r m i t o u t e s les s o l u t i o n s o p t i m a l e s de (P ' ) , il en

e x i s t e au m o i n s n n e , c o n s t i t u 6 e de T rd seaux

m-admissibles.

I I I . 1 . D 6 f i n i t i o n du graphe s6quentiel G .

A c h a q u e i n s t a n t t ( l ~< l ~< T) le n o m b r e Pt de

r 6 s e a u x m - a d m i s s i b l e s d i f f6 ren t s es t fini. Cela r6su l te du f a i t q u e les c o m p o s a n t e s des v e c t e u r s de sc r i p t i f

s o n t en t i~res e t bo rndes (*). Les Pt r 6 s e a u x en q u e s t i o n

s e r o n t no t6s RJ(t) ( p o u r 1 <~ j <~ Pt) e t les v e c t e u r s

(*) Dans le cas off on n 'a pas la eontrainte d'int~grit6, un certain nombre d'hypoth~ses suppl6mentaires sont n6cessaires pour avoir eette propri~t&

3/8 A. T~LEC., 30, n ~ 1-2,, 1975

54 M. M I N O U X . -- M U L T I F L O T S D Y N A M I Q U E S D E COUT ACTUALIS]~ M I N I M A L

d e s e r i p t i f s e o r r e s p o n d a n t s : YJ(t) = [Y~u(t)]uEu.

C o n s i d O r o n s a lo r s le g r a p h e G (Fig . 2) d o n t les n c e u d s

R = {2) ~ t (T}

R ~ (2) R Pr (T)

Fro. 2. - - Le graphe sdquentiel G associ6 au probl~me (P'). Les nceuds de G correspondent, pour chaque t -- 1, ..., T, aux Pt r6seaux m-admissibles diff6rents. Le noeud origine correspond an rdseau R(0) (h l ' i ns tan t 0). Pour 1 ~< t ~< T, il existe un are [ R l ( t - 1), R/(t)] de longeuur :

X [~u(Y{,(t)) - - (I)u(Y~,(t - - 1))1/ (1 § z ) t - i . uEU

Les ares jo ignan t les RJ(T) h R (T § 1) (extrdmit6) sont de longueur nulle.

T c o r r e s p o n d e n t a u x p ~, Pt r d s e a u x m - a d m i s s i b l e s

l= t RJ( t ) (1 <~ t <<. T, 1 <~ j <~ Pt). E n o u t r e , o n m u n i t ~ d ' u n n c e u d o r i g i n e ( 6 t a t i n i t i a l ) c o r r e s p o n d a n t a u r 6 s e a u

R ( 0 ) = [G, Y ( 0 ) ] e t d ' u n n c e u d e x t r 6 m i t 6 R ( T + 1)

r e p r 6 s e n t a n t l a r 6 s e a u ~ l ' ~ t a t f ina l . P o u r t o u t

t(1 ~< t ~< T), o n s u p p o s e q u e t o u s les a r c s [ R / ( t - - 1 ) ,

RJ'(t)] e x i s t e n t ( ~ e s t u n g r a p h e s 6 q u e n t i e l c o m p l e t

e t o r i e n t 6 ) e t s o n t m u n i s des l o n g u e u r s ( n o n n 6 g a t i v e s ) :

y [ R i ( t - - 1 ) , R J ( t ) ] = ~ (~u(Yd(t))--(1)u(Yiu(t--1)) ~Eu (1 + = ) t - i

r e p r d s e n t a n t le c o o t ( ac tua l i sO) des i n v e s t i s s e m e n t s

n d c e s s a i r e s p o u r p a s s e r d u r d s e a u R i ( t - - 1 ) h F ins -

t a n t t - - 1, a u r d s e a u RJ( t ) h l ' i n s t a n t t. E n f i n , t o u s

les a rcs [RJ (T ) , R ( T + 1)] e x i s t e n t e t s o n t de l on - g u e u r n u l l e (F ig . 2).

I1 rOsu l t e d e la d d f i n i t i o n de G q u e t o u t c h e m i n

d ' o r i g i n e 13(0) e t d ' e x t r d m i t d R ( T + 1) da r t s G cor -

r e s p o n d h u n e s o l u t i o n d u p r o b l ~ m e ( P ' ) . I1 s ' a g i t

a lo r s de d d t e r m i n e r le p l u s c o u r t c h e m i n de R ( 0 ) h R ( T + 1).

E t a n t d o n n ~ le n o m b r e ~ n o r m e de s o m m e t s de G ,

il es t d v i d e m m e n t e x e l u d e c o n s t r u i r e G p o u r r ~ s o u d r e

(P ' ) . N o u s a l l o n s vo i r , a u e o n t r a i r e , c o m m e n t l ' o n

p e u t c a r a e t d r i s e r de f a g o n s i m p l e le e h e m i n o p t i m a l .

III .2 . C a r a c t 6 r i s a t i o n du c h e m i n o p t i m a l d a n s G.

P o u r u n r 6 s e a u RJ( t ) m - a d m i s s i b l e h l ' i n s t a n t t

(1 <~ j <~ Pt), o n n o t e (I)(RJ(t)) le c o o t non actualisd de R/ ( / ) , h s a v o i r la q u a n t i t ~ :

O ( R J ( t ) ) Z O u ( Y ~ ( t ) ) . u E U

O n n o t e 6 g a l e m e n t R * ( t ) le rOseau m - a d m i s s i b l e

de c o o t m i n i m a l h l ' i n s t a n t t, e ' e s t - h - d i r e :

( I ) ( R * ( t ) ) = m i n {(P(RJ(t))}.

j = l_ .p t

On p e u t a lo r s ~ n o n c e r :

T h d o r d m e 2.

Le c h e m i n { R * ( 1 ) , R * ( 2 ) . . . . , l q * ( T ) } es t u n c h e -

r a in de l o n g u e u r m i n i m a l e d a n s G, c ' e s t - h - d i r e c o r r e s -

p o n d a n t h u n e s o l u t i o n o p t i m a l e de (P ' ) .

Ddmonstration.

C o n s i d ~ r o n s t r o i s i n s t a n t s c o n s ~ c u t i f s t, t + 1, t + 2.

S u p p o s o n s q u e le p l u s c o u r t t h e r e i n (en c o o t a e t u a l i s 6 )

d a n s G p a s s e p a r R ( t ) e t c h e r e h o n s le p l u s c o u r t

c h e m i n e n t r e R ( 0 ) e t R ( t + 2) p o u r u n n c e u d q u e l -

c o n q u e de G h l ' i n s t a n t t - - 2. P o u r a l l e r de R( / ) h

R ( t + 2), o n p e u t p a s s e r :

- - so i t p a r R * ( / § 1),

- - so i t p a r u n a u t r e n c e u d R ( t + 1) =/: R * ( t + 1)

(F ig . 3).

t l + I t ~ - 2

I I 9 ( t + 1 ) ]

" R * ( t + 11 I

L [

+ 2)

Fro. 3. - - Caract6risat ion du chemin optimal darts G' . Pa r d~finition de R*(t + 1), on a : c 1 ~<c a . D 'au t re par t : c 1 + c 2 -- c 3 + c 4. Ceci pe rmet de mont rer que le coot actualis6 du chemin passan t pa r R*(t + 1) est inf6rieur au

coot actualis~ de t ou t autre chemin.

A p p e l o n s r e s p e c t i v e m e n t C 1 , C 2 , C a , C 4 l e s c o o t s ( n o n

ac tua l i s~s ) des a r c s [R( / ) , R * ( t + 1)] ; [ R * ( t + 1),

R ( t § 2 ) ] ; [R( t ) , R ( t + 1)] e t [R( t + 1), R ( t + 2)] .

On a : c i q - c 2 = c a + c4 , e t p a r a i l l eu r s l ' o p t i m a l i t 6

de R * ( t § 1) i m p l i q u e : c 1 ~< c a .

Le c o o t a c t u a l i s 6 d u p r e m i e r c h e m i n e s t a l o r s :

Cl C2 ? i - (1 + v) i + (1 + "r) t+l '

ce lu i d u d e u x i ~ m e c h e m i n :

C3 r Cl Av C2 + 2 - ( 1 - ~ "Y) t ~- ( 1 - ~ % - ) t + 1 - - ( I + %-)t+l ~-

L (1 § "r) t 1 1 + "r

d 'o f l l ' o n d 6 d u i t :

e l - - C3 r ~1 - + 2 - (1 + v)t [_1 - - - 1 ] 4 0 ,

l + v

ce qu i m o n t r e b i e n q u e ~ i ~< ~ 2 . O n d d m o n t r e a l o r s le thdorbme 2 p a r r O c u r r e n c e s u r t .

A. TI~LEC., 30, n ~ 1-2, 1975 4 /8

M. M I N O U X . -- M U L T I F L O T S D Y N A M I Q U E S D E C O U T A C T U A L I S I ~ M I N I M A L 5 5

I I I . 3 . U n e condition suffisante d'optimalit6 la f g u r e 4. On 6 t u d i e son 6 v o l u t i o n sur d e u x p 6 r i o d e s pour (P). ( T : 2) ; le t a u x d ' a c t u a l i s a t i o n es t suppos6 de 15 %.

E n g6n6ra l , l a l o n g u e u r du c h e m i n :

{R*(1) , R * ( 2 ) . . . . . R * ( T ) }

es t une b o r n e i n f6 r i eu r e du cof i t de l ' o p t i m u m de (P) ,

p u i s q u e l ' e n s e m b l e des so lu t ions de (P) es t inc lus da~s ! ' euse rnb !e des so lu t i ons de (P ' ) . Cepe, n d a n t , il

p e u t se f a i r e q u e ce c h e m i n c o r r e s p o n d e 6 g a l e m e n t une s o l u t i o n de (P) , a u q u e l cas c ' e s t aussi u n e

so lu t ion o p t i m a l e de (P) , e t on p e u t 6nonce r :

Th~or~me 3.

Si l ' o n a : R* (1 ) or R*(2 ) or ... ~___ R * ( T ) , a lors

{R*(1), R * ( 2 ) . . . . . R * ( T ) } es t une so lu t i on o p t i m a l e

de (P). L a r ~ s o l u t i o n du p r o b l ~ m e d y n a m i q u e sc r a m ~ n e ,

dans ces c o n d i t i o n s , h la r6so lu t ion de T p r o b l ~ m e s

s t a t i q u e s de mul t . i~0 t h cof i t m i n i m a l .

IV. RI~SOLUTION DU PROBL~.ME (P)

N o u s 6 t u d i o n s ici les m 6 t h o d e s de rd so lu t i on app l i -

cab les au p r o b l ~ m e (P) dans le cas (le p lus f r 6 q u e n t

en p r a t i q u e ) off l a su i t e {R*(1) , R*(2 ) . . . . . R* (T)} ne s a t i s f a i t p a s les c o n t r a i n t e s I I .4 .2 . N o u s i l lus-

t r e r o n s d ' a b o r d ce g e n r e de s i t u a t i o n sur un p e t i t

e x e m p l e . P u i s n o u s p r o p o s e r o n s d e u x m 6 t h o d e s de

r6 so lu t i on a p p r o c h 6 e du p r o b l ~ m e (P) a y a n t la p a r - t i cu l a r i t~ de c o n d u i r e t o u t e s les d e u x h l a so lu t i on

o p t i m a l e l o r s q u e la c o n d i t i o n du lhdor~me 3 es t

sa t i s fa i t e . C e p e n d a n t , en deho r s de ce cas tr~s p a r t i - cu l ie r , n o u s m o n t r e r o n s q u e ees d e u x m 6 t h o d e s s o n t

lo in d ' e t r e 6 q u i v a l e n t e s q u a n t h la qua l i t 6 des r6sul-

t a t s o b t e n u s . D a n s t o u t e la su i t e , nous s u p p o s e r o n s q u e l ' o n

d i spose d ' u n a l g o r i t h m e p o u r la d 6 t e r m i n a t i o n d ' u n m u l t i r i o t ( s t a t i q u e ) de eof i t m i n i m a l (les f o n c t i o n s de

c o o t v 6 r i f i a n t les h y p o t h e s e s exp l i c i tdes au w I I .1) ; ee p r o b l ~ m e es t lo in d ' e t r e t r i v i a l en r a i s o n de la n o n -

c o n v e x i t 6 e t m ~ m e de la n o n - e o n t i n u i t 6 des f o u c t i o n s de cofit . L a m 6 t h o d e de r6so lu t ion p r6con i s6e dans

la r6 f6 rence [5, chap . IV] es t de n a t u r e h e u r i s t i q u e , m a i s s ' a p p l i q u e a u x r d s e a u x de g r a n d e t a i l l e ; e l le

u t i l i se u n a l g o r i t h m e de r e c h e r c h e d ' u n m u l t i f l o t

c o m p a t i b l e d a n s u n g r a p h e non o r i en t6 m u n i de

c a p a c i t ~ s (cf. [7]). P a r a i l leurs , on se r e p o r t e r a u t i - l e m e n t a u x r6 f6 rences [8 h 10] qu i t r a i t e n t de p r o -

b l ames s imi l a i r e s .

IV.1. Un exemple.

C o n s i d 6 r o n s le g r a p h e h 3 nceuds e t 3 ar~tes de

1

~ " ~ ,I~:3 (0)=0

~l~(O) = 0 I ~ r / ~ : (O<Y~IO00)

4']2(Y) = 60

(O<Y r I000)

~P2s rut = u 4~2~ (y) = 40(0<Y<1000)

2

FIG. 4. - - Un graphe h 3 nceuds et 3 ar~tes pris comme exemple. On a indiqu6, en regard de chaque arSte, les caract6ristiques

de la fonction du coflt.

A c h a q u e i n s t a n t (t = 1, 2), le g r a p h e est p a r c o u r u

p a r les r iots s u i v a n t s :

d12(1) = I00, d,2(2) = 100,

d,a(1) = 0, d,a(2) = 700,

d~a(1) = 0, d~a(2) = 600.

D ' a u t r e p a r t , su r c h a q u e ar~te , on p e u t :

- - ne pas i n s t a l l e r de c a p a c i t 6 (cof i t = 0),

- - i n s t a l l e r u n e c a p a c i t 6 de 1 000 (cof i t = 60 su r

( 1 - 2 ) ; cof l t = 50 sur ( 1 - 3 ) ; co( i t = 40 sur (2-3)).

P o u r t = 1, le r~seau de cof l t (non ac tua l i s6 ) m i n i m a l

R*(1 ) c o r r e s p o n d h :

Y*a(1) = 1 0 0 0 ; Y~a(1) = 0 ; Y 'a (1) = 0.

P o u r t = 2, le r6seau de cof i t m i n i m a l R*(2 ) cor -

r e s p o n d h :

Y72(2) = 0 ; Y 'a (2) = 1 000 ; Y~a(2) = 1 000.

On c o n s t a t e b i e n q u e l ' o n n ' a pas , dans ce cas ,

Y*(1) o< Y*(2) , e t il e s t c la i r q u e la s o l u t i o n o p t i -

m a l e du p r o b l ~ m e (P) es t o b t e n u e en i n s t a l l a n t des

c a p a c i t 6 s de 1 000 su r (1-3) e t (2-3) h l ' i n s t a n t t = 1 ( a u c u n e c a p a c i t 6 s u p p l 6 m e n t a i r e n ' e s t a lors n6ces - sa i re h l ' i n s t a n t t = 2 ) ; le cof i t ac tua l i s6 de c e t t e

so lu t i on o p t i m a l e es t ( I ) * = 90.

E n f i n , l a s o l u t i o n {R*(1) , R*(2)} d o n n e , p a r r a p -

p o r t au cof i t de l a s o l u t i o n o p t i m a l e , la b o r n e inf6-

r i eu re s u i v a n t e :

6 0 + ( 5 0 + 4 0 - - 6 0 ) / 1 , 1 5 = 86 (dcar t : 4,5 %) .

I V . 2 . P r e m i S r e m ~ t h o d e .

T o u t c o m m e le p r o b l ~ m e (P ' ) , le p r o b l ~ m e (P) p e u t se f o r m u l e r d a n s le l a n g a g e de l a p r o g r a m m a t i o n

d y n a m i q u e , c ' e s t - h - d i r e en t e r m e s de p lus c o u r t

e h e m i n d a n s u n g r a p h e s 6 q u e n t i e l ~. Les nceuds de d e v r a i e n t a lors e o r r e s p o n d r e h l ' e n s e m b l e de t ous l e s

r6seaux admissibles h t o u s l e s i n s t a n t s ( t ~ 1, ..., T)

5 / 8 A. TI~LEC., 30, n ~ 1-2, 1975

56 M. MINOUX. - -

(et non plus seu lemen t aux rdseaux m-admiss ibles , comme dans le graphe G). Pa r ailleurs, l ' exis tence d ' u n arc [ R / ( / - - 1), Ri(/)] dans G serait subordonn6e h la condi t ion : R / ( t - - 1 ) ~ FU(t). (La longueur des arcs de ~ est 6 v i d e m m e n t d6finie de la m~me mani~re que pour les arcs de G.)

Malheureusement , il n ' e s t plus possible de caract6- riser aussi s imp lemen t que dans G le chemin opt imal dans G. D ' au t r e par t , le nombre 6norme de sommets de ~ in t e rd i san t la r6solut ion classique (par pro- g r a m m a t i o n dynamique ) , il fau t t rava i l le r sur impl ic i tement , et se con ten t e r de solut ions approch6es.

Daus ces condi t ions , la premiere mdthode qui v ien t h l ' espr i t consiste h cons t ru i re de proche en proche,

h par t i r de F((0), u n chemin (R(1), R(2) . . . . . R(T)} en s61ectionnant h chaque lois l ' a rc de G de plus faible longueur. D 'oh :

Procddure 1 (en o~)on~).

1) t - o ; f i (o) = R ( o ) = IV, Y(O)] ; ~ ( o ) = v ( o ) ;

2) t : t + l ;

3) d6finir R(t) ~ [G, ~/(t)] comme le rdseau admis-

sible de cofit (I)(R(t)) m i n i m a l et v6r i f iant :

~ r 1) _~ ~ ( t ) ;

4) s i t ~ T, r e tou rne r en 2), sinon, fin de la proc6dure.

A chaque 6tape t, le rdseau de COflt m i n i m a l com- pat ib le avec les con t ra in te s II .4.2 est re tenu. Remar - quer que, dans le cas Oil les condi t ions du lhdor~me 3 sont satisfaites, on a :

R ( 1 ) = R*(1),

R ( T ) = R*(T) ,

et la procddure 1 condu i r a i t h la solut ion opt imale de (P).

Cependant , l ' exp6r ience m o n t r e que cette proc6dure condui t le plus souven t h des solut ions tr~s mauvaises . Ainsi, sur l ' exemple de la figure 4, elle abou t i r a i t la solut ion :

Y12(1 ) : 1 0 0 0 , "Y12(2) : I 0 0 0 ,

~J(13(1) = 0 , ~(13(2) = I 0 0 0 ,

~t23(1 ) : 0, Y2a(2) = 1 000,

de coflt actualis6 :

60 + (40 + 50)/1,15 = 138,

(6cart de + 50 ~o par r appo r t h la solut ion opt imale I).

L'6chec de la procddure 1 peu t s ' expl iquer par le fait qu 'h c h a q u e 6tape t, il f au t pour satisfaire les con t ra in tes II .4.2 s '6car ter un peu plus de la solut ion id6ale {R*(1) . . . . . R*(T)} du probl~me sans con- t ra intes . I1 en r6sul te des a u g m e n t a t i o n s de coflt successives diffici lement contrSlables ( impossible de pr6dire une borne sup6rieure du cofit de la solut ion

MULTIFLOTS DYNA(EIQUES DE COUT ACTUALISI~ DIINIMAL

ainsi obtenue). La procddure su ivan te 6 r i t e ces inconv6nien ts en u t i l i s an t comme solut ion de ddpar t une borne sup6rieure de qual i t6 .

I V . 3 . S e c o n d e m 6 t h o d e .

Soit R*(T) le rdseau m-admiss ib le de co~t (non- actualis6) min ima l (h l ' i n s t a n t T). Comme les va leurs d~j(t) sont non-ddcroissantes (en fonct ion de l), la s6quence {R*(T), R*(T) . . . . . R*(T)} est une solut ion du probl~me (P) et son coflt qb(R*(T)) est une borne sup6rieure de l ' o p t i m u m de (P) (c 'est aussi la meil- leure des borncs sup6rieures de ce type).

Sur l ' exemple de la figure 4, le r6seau R*(2) condui t h une borne sup6rieure de coflt : 90. Dans ce cas, il y a 6galit6 avec la va leur op t imale , mais cet te s i tua- t ion n ' a rien d ' cxcep t ionne l : en effet, on observe que la borne est d ' a u t a n t plus proche de l ' op t ima l i t6 que le t a u x d ' ac tua l i sa t ion -~ est faible (l '6galit6 cst tou- jours r~alis6e pour ~ 0). Ceci dit, les capacit6s Yu*(T) du r6seau R *( T) 6 t an t en gdn6ral tr~s super- flues pour assurer l ' admiss ib i l i t6 aux i n s t a n t s t : 1, ..., T - - 1 , on pou r r a am6liorer sens ib lement cette solut ion de d6par t en che rchan t h suppr imer tous les inves t i s sements inut i les , d ' abo rd pour t = T - - l , puis t = T - - 2 , etc. D'ofl :

Procddure 2 (en arri~re).

1) t = T ; ]~(T) = R*(T) = [G, Y*(T)I ; ~[(T) : Y*(T) ;

2) t = t - - 1

3) d6finir Ft(t) = [G, Y(t)] c omme le rdseau min ima-

l i san t (I)(R(T)) et v6r i f ian t ~/(t) oc Y(t + 1)

4) si l ~ 0, r e tou rne r en 2 ; s inon, fin de la pro- c6dure.

Si la condi t ion du thdorOme 3 est v6rifide, cette procddure, comme la pr6c6dente , condui t h la solu- t ion optimale. Cependan t , dans la p lupa r t des pro- blames pra t iques qui ne re l~vent pas de ce cas par t i - culier, la procddure 2 se r~v~le tr~s sup6rieure h la procddure 1 (c 'est elle qui est ac tue l l emen t utilisde pour la p lani f ica t ion h m o y e n t e r me des r6seaux de t6Mcommunica t ions td l6phoniques [5]).

Cette supdriorit6 appa ra i t b i en sur l ' exemple de la figure 4, off la procddure 2 c ondu i t h l ' op t imum, tandis que la procddure 1 donne une solut ion de 50 ~o plus cofiteuse.

On a rassembl6 ~galement , dans le t ab leau I, une sdrie de rdsultats compara t i f s ob t enus sur un sons- rdseau h 12 nceuds du r6seau td l6phonique fran~ais ([5], Fig. 8). Six probl~mes de p lan i f ica t ion h moyen t e rme diff6rant soit par les va leurs dij(/), soit par la s t ruc ture du graphe (ensemble des ar~tes), ont 6t6 trai t6s. Dans tous les cas, l ' 6ca r t (en v a l e u r relative) entre les deux mdthodes a p p a r a i t supdrieur h 5 ~o.

A. TELEC., 30, n ~ 1-2, 1975 6/8

M. MINOUX. -- MULTIFLOTS DYNAMIQUES DE COUT ACTUALIS]~ MINIMAL 5 7

TABLEAU I

Comparaison des rdsuttats oblenus (codts exprimds en M . F . ) par les procddures 1 et 2 sur quetques probl~me$ tdmoins (planiflcalion d moyen terme d'un sous-rdseau d 12 nceuds du rdseau tdldphonique interurbain franfais)

Num6ro du probl~me

Caractdristiques du probl~me

Procddure 1 Proeddure 2

Ecar t (procddure 1-proc6dure 2)

1

N = 12 M = 25 T = 4

94 88

6,5 %

N = 12 M-----25 T ~ 6

119 109

9 %

N = 12 M = 22 T = 4

89 82

l 8%

N = 12 M = 22 T = 6

122 106

15 %

N = 12 M = 20 T = 4

89 84

6 %

N = 12 M = 20 T = 6

126 111

13,5 %

m a i s on r e m a r q u e r a q u ' i l p e u t a t t e i n d r e des v a l e u r s b e a u c o u p p lus dlevdes. N o u s a l lons vo i r , en conc lus ion ,

que l les c o n s d q u e n c c s on p e u t t i r e r de ces rdsu l t a t s

d a n s le d o m a i n e de la p l a n i f i c a t i o n des rdseaux.

V. C O N C L U S I O N

D e u x m d t h o d e s de r d s o l u t i o n du p r o b l ~ m e d u

m u l t i f l o t d y n a m i q u e de co f i t ac tua l i sd m i n i m a l o n t

dt6 p rdscn tdes . N o u s a v o n s m o n t r d q u ' i l ex i s te des

cas oh cos m d t h o d e s s o n t l ' u n e e t l ' a u t r e o p t i m a l e s . Darts l e c a s gdndra l , c e p e n d a n t , el les cessen t d ' e t r e

d q u i ~ a l e n t e s , e t la p r o c 6 d u r e en arri~re s ' av~re sys t6-

m a t i q u e m e n t , e t de lo in , m e i l l e u r e q u e la p r o c d d u r e

en avant. C e t t e c o n s t a t a t i o n a d ' i m p o r t a n t e s imp l i - c a t i ons d a n s le d o m a i n e de l a p l a n i f i c a t i o n des r6seaux .

D ' u n p o i n t de r u e 6 c o n o m i q u e , l a p r o c d d u r e en

avant p e u t ~tre cons idd rde c o m m e u n e m d t h o d e de p r o g r a m m a t i o n h court terme : en effet , h c h a q u e 6 tape ,

on ne rda l i se q u e les i n v e s t i s s e m e n t s s t r i c t e m e n t i n d i s p e n s a b l e s p o u r s a t i s f a i r e la d e m a n d e h la pd r iode

s u i v a n t e ; la f o n c t i o n q u e l ' o n m i n i m a l i s e es t a lors u n i q u e m e n t u n e d 6 p e n s e annue l l e . C ' e s t la m d t h o d e

ut i l i s6e en p r a t i q u e : a) so i t en pd r iode de r e s t r i c t i o n

b u d g 6 t a i r e , b) so i t l o r s q u e les v a l e u r s p rdv i s ionne l l e s

de la d e m a n d e f o n t dd fau t .

L a p r o c d d u r e en ar t i s t e , q u a n t fi elle, p e u t ~tre cons iddrde c o m m e u n e m d t h o d e de p l a n i f i c a t i o n

moyen terme : son o b j e e t i f p r i n c i p a l est , en effet, de

m i n i m a l i s e r la s o m m e des ddpenses sur p lus ieurs

pdriodes consdcutives, m ~ m e si eela do i t c o n d u i r e h des

i n v e s t i s s e m e n t s a p p a r e m m e n t m o i n s r e n t a b l c s su r

u n e seule pd r iode ( c o u r t t e r m e ) . Les d d v e l o p p e m e n t s

t h d o r i q u e s q u i p r d c ~ d e n t c o n f i r m e n t , sans 6 q u i v o q u e , q u ' u n e p o l i t i q u e e o h d r e n t e d ' e x t e n s i o n d ' u n rdseau

de t d l d c o m m u n i c a t i o n s (p. ex. : rdseau t d ldphon ique )

ne s a u r a i t en a u e u n eas ~ t re s u b o r d o n n d e exc lus i -

v e m e n t h des o b j e c t i f s fi c o u r t t e r m e ma i s , au con-

t r a i r e , s ' a p p u y e r su r des d t u d e s p r d v i s i o n n e l l e s e t

p r o c d d e r s u e e c s s i v e m e n t du l o n g t e r m e ve r s le m o y e n t e r m e , pu i s du m o y e n t e r m e v e r s le c o u r t t e r m c .

B E M E B C I E M E N TS.

Je remercie Stdphane Guitonneau pour sa contribution a la ddmonstration du thdor~me 2.

M a n u s c r i t recu le 26 fdvrier 1975.

B I B L I O G R A P H I E

[1] AYMAR (J.-P.), MINOUX (M.). Choix des invest is- sements en t ransmission dans le rdseau interurbain. Actes du Congr~s A.F .C.E.T . c( in fo rmat ique et T61dcommunications )), R E N N E S . I .R .1 .A . , Fr. (nov. 1973), pp. 219-227.

[2] YAGED (B.). Min imum cost rou t ing for s ta t ic ne twork models (Routage A cofit min imal pour un module de rdseau s tat ique) . Networks, U. S . A . (1971), 1, n ~ 2, pp. 139-172.

[3] YAGED (B.). Min imum cost rou t ing for dynamic ne tworks models (Routage h cofit min imal pour un module de rdseau dynamique) . Networks, U. S. A. (1973), 3, n ~ 3, pp. 193-224.

[4] B i c s ~ (J.), MINoUX (M.). P lan i f ica t ion des inves- t i ssements en rdseau in te ru rba in : le p rog ramme os i r i s . Echo Bech., Fr. (avr. 1973), n ~ 72, pp. 22-35 (hors commerce) .

[5] Mir~ovx (M.). P lani f ica t ion A cour t e t h moyen te rme d ' u n r~seau de td ldcommunicat ions . Ann . Tdldcorn. Fr. (nov.-ddc. 1974), 29 , n ~ 11-12, pp. 509-536.

[6] BELLMAN (R.). Dynamic P r o g r a m m i n g (Program- mar ion dynamique) . Princeton university Press, Pr ince ton (1957), 342 p.

[8] I:~OTHFARB (B.), GOLDSTEIN (M.). The one t e rmina l Te lepak problem (Le probl~me de la tdlddistribu- t ion a une source). Oper. Bes., U . S . A . (jan.-fdv. 1971), 19 , n ~ 1, pp. 156-169.

[9] STEINBERG (D. I.). The fixed charge problem (Le probl~me avec charges fixes). Nay. Bes. Logist. Quart., U . S . A . (1970), 17 , pp. 217-236.

[10] CHI/ISTOFIDES (N.), BROOKER (P.). Optimal expan-

7/8 A. Tg=LEC., 30, n ~ 1-2, 1975

5 8 M. M I N O U X . -- M U L T I F L O T S D ~ r N A M I Q U E S D E COUT ACTUALIS15. M I N I M A L

sion of an existing network (D6veloppement optimal d 'un rdseau existant). Math. Programming., Nederl. (avril 1974), 6, n ~ 2, pp. 197-211.

[7] Mi~oux (M.). Rdsolution des probl6mes de multiflots en nombres entiers dans les grands rdseaux. Revue autom, in]ormat, rech. opt., Fr. (1975) (h para~tre).

[11] Fond (L. R.), FULKSRSON (D. R.). Constructing

maximal dynamic flows from stat ic flows (Construc- tion de flots dynamiques h par t i r de flots statiques). Oper. Res., U. S. A. (1968), 6, pp. ~19-r

[ 1 2 ] BELLMORE (M.), RAMAKalSHNA (R.V.). On multi- commodity maximal dynamic flows (Multiflots dynamiques maximaux). Oper. Res., U. S. A. (jan.-f6v. 1973), 21, n ~ 1, pp. 10-21.

Le Directeur de la publ icat ion : M me Y. BOURNAT

I m p r i m e r i e J a c q u e s e t D e m o n t r o n d 26, rue E r n e s t - R e n a n - 25 000 B e s a n g o n - - Published in France D 6 p 6 t 16gal 2e t r imes t r e 1975, u o 8785