Embed Size (px)
Citation preview
25
RECHERCHE DE LA CONFIGURATION OPTIMALE D'UN R~,SEAU DE T~LI$,,COMMUNICATIONS
AVEC FONCTIONS DE COUT CONCAVES
p a r
Michel M I N O U X
Ancien 61~ve de l 'Ecole Polytechnique *
P~I~SUMI~. - - Cet article prdsente une sgnthkse des thdories malhdmatiques et des diff6rentes mdthodes num6riques permeltanl de rdsoudre, sur ealculateur, le problkme de la structuration optimale f long terme (au moindre co~t actualisd) des rdseaux de tdldcommunieations. II regroupe, dans un contexte uni fcateur , l'ensemble des travaux entrepris depuis 1970 au C N E T dans ce domaine, el qui ont abouli au ddveloppement du programme O S I R I S (Planification des investissements en rdseau interurbain, avril 1973) . Historiquement, c'esl en effet dans le contexle lrks particulier du rdseau inlerurbain que ce type de probl&me a d'abord dtd renconlrd. On s'esl rendu comple, par la suite, qu'il s'agissait l& d'une classe beaucoup plus gdndrale de probl~mes : ceux qui se posent chaque fois qu'on eherche ~ rdaliser, au moindre cofit, l'extension d'un rdseau mailld de tdldcommuni- cations proche de la saturation. A ins i les thdories ddveloppdes ici trouvent-elles tout nalurellement leur appli- cation aussi bien darts le domaine de la planification des rdseaux urbains que dans celui de la planification des rdseaux rdgionaux. Darts tous ces cas, l'hypoth~se de base - - ~ savoir la ddcroissanee des cofils moyens
par circuit en fonction de la eapacild des syst~mes - - se lrouve rdalisde.
PLAN. - - / r e p a r t i e : FONDEMENTS M A T H I ~ M A T I Q U E S . �9 I : I n t r o d u c f f o n �9 I I : Vers une ~ormu/ut ion m u t h d m u t i q u e du probl~.me I I .1 . Description du rdseau el des diffdrentes demandes ; I I .2 . Les codls des capacitds installdes sur le rdseau; I I .3 . Les hypotheses sur les fonclions de codt; I I .4 . Princ ipaux types de fonctions rencontrds ; I I .5 . Premiere formulation du probl~me ; I I .6 . Ddfinitions ; I I .7 . Seconde formulation du probl~me. � 9 : Caructdrisution des solutions I I I . 1 . Thdor~me 1 ; I I I . 2 . Rdseaux uniroutds, ddfi- ni t ion; I I I . 3 . Lemme 1; I I I . 4 . Thdor~me 2 �9 IV : Propri~t~s des solutions opt imales IV.1 . Lemme 2; IV.2. Lemme 3; IV.3 . Lemme 4; IV.4. Thdor~me 3; IV.5. Thdor~me 4; IV.6. Thdor~me 5; IV.7 . Thdor~me 6; IV.8. Vers une caractdrisation des optimums loeaux; IV.9. Thdor~me 7; IV.10. Thdor&me 8; IV.11. Les probl~mes soulevds par la recherche de l 'optimum absolu; IV.12. Exemple montranl la multiplicitd des opti- mums locaux. �9 V : L a recherche des op t imums locaux V.1. Recherche d'un point extreme satisfaisant les conditions ndcessaires d'oplimalitd locale; V.2. Propridld 1; u Propridld 2; V.4. Thdorkme de conver- gence; V.5. Vdrification de l'optimalitd locale; V.6. Gdndralisalion aux fonclions non conlinF~ment diffdren- liables ; V.7. Etude de la rapiditd de convergence sur un exemple ; V.8. Influence du rdseau de ddpart sur le point de convergence; V.9. Co~ls f xes el fonetions de coFd arlificielles. Conclusion. Bibliographic (16 r6f.).
P R E M II~IRE P A R T I E
F O N D E M E N T S M A T H E M A T I Q U E S
I. I N T B O D U C T I O N
L o r s q u ' u n r6 seau de t 6 1 d c o m m u n i c a t i o n s , d e v a n t
s a t i s f a i r e u n e d e m a n d e (*) c r o i s s a n t e au cours du
t e m p s , a r r i v e h s a t u r a t i o n , l a q u e s t i o n se pose de
s a v o i r off e t q u a n d rda l i s e r les e x t e n s i o n s ndcessa i res
de fa~on h s a t i s f a i r e la d e m a n d e d a n s l ' a v e n i r i m m 6 -
d i a t . C ' e s t le p r o b l ~ m e des investissements gl court lerme su r le rd seau , e t c ' e s t ce lu i qu i i n t 6 r e s s e au p l u s
h a u l p o i n t les s e rv i ces spdcia l i s6s clans la p r 6 v i s i o n
des i n v e s t i s s e m e n t s .
S ' i l ne s ' a g i s s a i t q u e de fa i re c r o i t r e le r6 seau
h o m o t h 6 t i q u e m e n t h l u i - m ~ m e en u t i l i s a n t les a r t~ re s
e x i s t a n t e s , le p r o b l ~ m e s e r a i t f a c i l e m e n t r6solu. Mais
ce s e r a i t p o s t u l e r i m p l i c i t e m e n t q u e la s t r u c t u r e e t
les r o u t a g e s des f a i s c e a u x de c i r c u i t s , t e l s qu ' i l s
e x i s t e n t a c t u e l l e m e n t , s o n t e t r e s t e r o n t d 6 f i n i t i v e m e n t
les m e i l l e u r s . Ce s e r a i t p o s t u l e r 6 g a l e m e n t q u e le
r 6 s eau a u r a i t d u n s v i n g t a n s u n e s t r u c t u r e i d e n t i q u e
la s t r u c t u r e a c t u e l l e ( m ~ m e h o m b r e d ' a r t ~ r e s ( * * ) ) .
Or ce la e s t d ' a u t a n t p lus diffici le h a d m e t t r e q u e
le r 6 s eau f r an ~a i s es t a c t u e l l e m e n t , e t p o u r u n b o n
* Ing~nieur contractuel au CNET-Issy, groupement RECHERCHES ET CONTROLE DE COMMUTATION, d6par tement INGI~- NIERIE DES SYST~MES DE COMMUTATION.
(*) Demande en voies t61~phoniques point h point, liaisons sp6cialis~es, etc. (**) Une art~re de transmission entre deux centres i e t ] est d6finie ici comme l 'ensemble des moyens de transmission
reliant directement les centres i et ]. Par exemple, une art~re de t ransmission peut-~tre constitu6e par un faisceau hertzien 1800 voies et quatre paires coaxiales 2700 voies. Dans la suite une art~re entre i e t ] sera repr6sent6e par un arc non orient~ d'origine i et d 'extrdmit6 ], l 'ensemble des art~res const i tuant un graphe non orientd (graphe des art~res).
] / 1 8 A. T~LI~C., 29, n ~ 1-2, 1974
26 M. M I N O U X . - C O N F I G U R A T I O N O P T I M A L E D ' U N RI~SEAU D E T I ~ L I ~ C O M M U N I C A T I O N S
n o m b r e d 'ann6es encore, en r~gime de croissance exponent ie l le .
Si, au contra i re , on adme t que de nouvel les art~res
puissent ~tre cr66es, que d ' anc iennes art~res puissent
ne pas @tre d6velopp6es, que les rou tages des fa isceaux de c i rcui ts puissent va r ie r au cours du t emps , le pro-
b lame dev i en t in f in iment plus complexe . On se rend
compte , en par t icul ier , q u ' u n e 6rude h court terme ne
pou r r a p r a t i q u e m e n t j amais r e c o m m a n d e r la cr6at ion
d 'une nouve l le art~re : le poids de l ' ex i s t an t 6 tant
dnorme, on cherchera s y s t 6 m a t i q u e m e n t h ut i l iser les
capaci t6s disponibles et h diff6rer l ' i nves t i s semen t
lourd. Cependan t , si l 'on 6tudie le d d v e l o p p e m e n t du
rdseau sur une p6riode plus longue (moyen ou long
terme) , il p e u t appa ra i t r e a v a n t a g e u x de r6aliser un tel inves t i s sement .
Ainsi une solut ion sa t i s fa isantc du probl~me h
court lerme ne p e u t ~tre donn6e que si l 'on dispose
d ' i n f o r m a t i o n s suffisantes sur le d d v e l o p p e m e n t prd-
visible et souha i t ab le h long te rme. I nve r sem en t , on
p e u t tr~s bien t r a i t e r le probl~me h long terme ind6-
p e n d a m m e n t du court lerme : le poids 6conomique de
l ' e x i s t a n t en 1973, m~me apr~s ac tua l i sa t ion , est tr~s
faible sur une pdriode de dix ou v i n g t a n s : que l 'on
songe h l 'effet d ' dc ra semen t dfi h la croissance expo- nent ie l le des fa i sceaux de circuits.
I1 f a u t done re ten i r que l 'on ne p e u t gu~re ut i l iser
le rdseau ex i s t an t pour guider les choix dconomiques du f u t u r lo inta in . Le probl~me est alors celui de la
synth~se op t ima le d ' u n r~seau su ivan t un crit~re ~co-
n o m i q u e qui p e u t ~tre (par exemple) la min imal i -
sa t ion du cofit de d6ve loppemen t sur la pdriode (O, T) ehoisie.
L ' o b j e t de cet ar t ic le est pr6cis6ment l ' 6 tude des
m6thodes m a t h 6 m a t i q u e s et numdr iques p e r m e t t a n t de dd te rmine r pa r p rog ramme , et en un t e m p s de
ealcul ra i sonnable , la conf igura t ion op t ima le h long
t e r m e d ' u n rdseau en expansion. Les d6ve loppemen t s
th~or iques qui v o n t suivre se rven t de base au pro-
g r a m m e OSIRIS qui a d6jh 6t6 prdsent6 en [1]. Bien
qu ' en cours d '6 tude , les probl~mes concc rnan t l 'u t i l i - sat ion des r6sul ta ts h long t e rme en r u e de la planifi-
ca t ion h cour t t e rme , ne seront pas abord6s ici.
II. VERS U N E F O R M U L A T I O N M A T H 2 M A T I Q U E DU PBOBL~.ME
II.1. Description du r@seau et des diff@rentes demandes.
Soit JV ~ {1, 2 , . .... N} un ensemble de N centres
(ou nveuds) qui p e u v e n t ~tre, pa r exemple , des centres de t r ans i t dans le r6seau in te ru rba in , ou des cen t r aux
td ldphoniques en rdseau urbain. D ' a u t r e pa r t , on
appe l le ra G le g raphe comple t (non oriental) cons t ru i t sur ces N centres.
On suppose que l ' on se donne, pour tou t couple
de centres (i, j ) une d e m a n d e d 0 qui peu t ~tre expr im6e en nombre de c i rcui ts (voies) t616phoniques, ou en
nombre de groupes pr imai res (1 G.P. = 12 circuits) ,
secondaires (1 G.S. = 5 G.P.) ou ter t ia i res (1 G.T.
= 5 G.S.). C o m m e les circui ts t616phoniques qui
jo ignent deux cent res i et j sont uti l isables pa r du
t raf ic t616phonique dans les deux sens (i vers j ou
j vers i), les d e m a n d e s dij sont des quant i t6s non
orient6es. I1 s ' ensu i t que la m a t r i c e [D] = [d~j]i=l ..... N J = l . . . . , N
est sytn6tr ique, c ' es t -h-d i re que l 'on a dll = dll
et chacun des nombres d~j (ou dj~) reprdsente le h o m b r e
de circuits d e v a n t ex is te r ent re les deux centres i et j ,
sans d is t inc t ion d 'o r ig ine et de dest inat ion. L ' in for -
ma t ion sur les demandes peu t ainsi ~tre r6dui te h la
demi-mat r ice des nombres d~j pour i ~ j (on a
dii ~ 0 Vi ~ 1 . . . . . N). La mat r ice [D] = [d~j]l=l ..... N e s t ob tenue en
]=1 . . . . . N
pra t ique h pa r t i r des donndes de t raf ic en t re c o m m u -
t a teurs et t i en t c o m p t e des r~gles d ' a c h e m i n e m e n t
en v igueur sur le rdseau [2].
Ceci dit, pour sat isfa i re la d e m a n d e centre h cen t re
[di#], il f au t cons t ru i re en t re les N centres donn6s
un r6seau (ou encore : un sous-graphe G' de G) don t
les art~res (ou arcs) (*) soient dot6es de moyens de
t ransmiss ion de capaci t6s suffisantes.
II.2. Les cofits des capacit@s install6es sur le r@seau.
On peu t a d m e t t r e , en t o u t e g6ndralit6, que l ' on
peu t ins ta l ler des m o y e n s de t ransmiss ion en t re deux
centres que lconques k et I du r6seau (en p ra t ique , cer ta ines a t t i r e s sont in te rd i tes , soit pour des raisons
physiques , soit p o u r des raisons techniques) .
Le nombre d ' a r t~ res possible a priori est 6gal au nombre d 'arcs dans le graphe comple t G h N som-
mets , soit M = C ~ - N ( N - - 1) 2 �9 L ' ensemble des
arcs (non orient6s) de G, c 'es t -h-di re l ' ensemble des
couples u = (k , l ) , k ~ JN ~ et l E 2~(', sera not6, U.
L ' ensemble U est de cardinal i t6 M. On supposera , pa r la suite, que l 'on p e u t ddfinir
pour chaque ar t~re u = (k, l) (u va r i an t de 1 h M)
une fonct ion de cofit O u ( X u ) d ' ins ta l l a t ion de la capacit6 X u �9 Ce sera en g6n6ra], le cofit de d6velop-
p e m e n t de l ' a r t~re sur une p6riode de temps donn6e [1]. R e m a r q u o n s aussi que si l ' a r t~re u est interdite dans la solut ion (c 'es t -h-dire que l 'on ne p e u t pas d6velopper l ' a r t~re en quest ion) , les hypotheses pr6c6-
dentes p e r m e t t e n t d ' en t en i r c o m p t e au n iveau de la fonct ion Ou(Xu) : il suffit cn effet de poser :
�9 ( I )u (Xu)= + o0 pour Xu > O.
(*) P a r c o n v e n t i o n , n o u s a p p e l l e r o n s arcs ce q u i e s t g 6 n ~ - r a k m e n t d 6 s i g n 6 p a r ardtes e n t h 6 o r i e d e s g r a p h e s .
�9 Ce s i g n e t y p o g r a p h i q u e i n d i q u e les f o r m u l e s e n c a d r ~ e s o u s o u l i g n 6 e s s u r le m a n u s c r i t .
A. T~LI~C., 29, n ~ 1-2, 1974 2/18
M. M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A U D E T ] ~ L ] ~ C O M M U N I C A T I O N S 27
II .3 . Les h y p o t h e s e s sur les f o n e t i o n s de eoht .
Les h y p o t h 6 s e s q u e n o u s fe rons sur les f o n c t i o n s
(I)u(Xu) s o n t les s u i v a n t e s .
A. E l les s o n t ddf in ies su r [O,-r c o ] , c o n t i n u e s sur
] 0 , § ~ ] e t p o s i t i v e s s t r i c t e m e n t c ro i s s an t e s sur [ 0 , § ~ ] . D ' a u t r e p a r t , (I)u(O) = O, ( V u = 1 . . . . . . M )
e t (I)u(Xu) ~ 0 p o u r X u ~ O.
B. E l les s o n t concaves, c ' e s t - h - d i r e qu ' e l l e s vdr i - f ien t :
r + Z2X~) ~< Z~Ou(XX~)+ Z2Ou(X~) ,
a v e c X~ /> 0, X2 ~> 0 e t X z + X 2 = 1 .
Remarques.
L ' h y p o t h ~ s e A e x p r i m e s i m p l e m e n t le f a i t que
r o u t e i n s t a l l a t i o n de c a p a c i t d s n p p l d m e n t a i r e es t coO-
reuse. D ' a u t r e p a r t , le c o o t do i t ~tre nu l si l ' o n n ' in s - t a l l e r ien.
D a n s le cas off la f o n c t i o n qb~(Xu) es t d d r i v a b l e sur
] 0 , + ~ ] , l ' h y p o t h ~ s e /3 r e v i e n t h s u p p o s e r q u e la dqbu
d~r ivde ~ es t m o n o t o n e dde ro i s s an t e (au sens
large) . D ' u n p o i n t de r u e p r a t i q u e , ce la t r a d u i t le fa i t q u e le c o o t m a r g i n a l du c i r cu i t (coOt d ' u n c i r cu i t
s u p p l d m e n t a i r e ) d i m i n u e a v e c la c a p a c i t d de l ' a r t~ re .
Les d i f fd ren tes d tudes d c o n o m i q u e s ef fec tudes sur les
m a t 6 r i e l s de t r a n s m i s s i o n e x i s t a n t s c o n f i r m e n t plei-
n e m e n t e e t t e h y p o t h ~ s e .
II .4 . P r i n e i p a u x types de f o n e t i o n s reneontr6s .
Fonctions de t ype 1.
F o n c t i o n s m o n o t o n e s c ro i s s an t e s c o n t i n u e s sur
[ 0 , + ~ ] e t d 6 r i v a b l e s su r ] 0 , § ~ ] . P a r e x e m p l e , des f o n e t i o n s du t y p e :
Ou = K ( X u ) c~,
off K es t u n e c o n s t a n t e e t a un p a r a m ~ t r e c o m p r i s
e n t r e 0 e t 1 ( s o n v e n t vo i s in de 0,5) (Fig. 1).
CoOt de I'arc u
FIG. 1. - - Fonctions de type 1.
Capacit~
Xu
Fonc~ons de type 2.
F o n c t i o n s l inda i res p a r m o r c e a u x , c o n t i n u e s su r
[ 0 , § cx~], m a i s n o n p a r t o u t ddr ivab les . E l l e s s o n t
s o u v e n t u t i l i sdes c o m m e des a p p r o x i m a t i o n s des
f o n c t i o n s de type 1 (Fig . 2).
CoOt de I'arc u
I I I
I t I t I I I I
FIG. 2. - - Fonctions de type 2.
] Capacit~ X u
Fonctions de t ype 3.
F o n c t i o n s l inda i res a y a n t p o u r o r d o n n d e ~ l ' o r i g i n e
8u e t p o u r p e n t e T u . E l l e s s o n t n o n c o n t i n u e s p o u r
X u = O.
(I)u(0) = 0 , (I)u(r = ~u. (F ig . 3).
CoOt de I'arc u
~ ~ Capacit6 Xu
FIG. 3. - - Fonctions de types 3 et 4. Type 3 : ~u ~ 0, type 4 : ~u = 0.
Fonctions de t ype 4.
F o n c t i o n s l inda i res a v e c o r d o n n d e nu l le h l ' o r i g i n e
(~u = 0) (F ig . 3).
I I . 5 . P r e m i b r e f o r m u l a t i o n d u p r o b l ~ m e .
A y a n t ddf ini le c o o t de mise en p l a c e d ' u n e c a p a -
ci td X q u e l c o n q u e s u r c h a c u n e des a r t6 res du rdseau ,
nous p o n v o n s f o r m u l e r n o t r e p r o b l 6 m e de la m a n i 6 r e s u i v a n t e :
Trouver le r6seau permettant de satisfaire ( s imul ta- ndment) toutes les demandes [d/j] au moindre coot.
3/18 A. T]kI,~,c., 29, n ~ 1-2, 1974
2 8 M . M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A U D E T E L t ~ C O M M U N I C A T I O N S
II.6. D6finitions. III.1. Th6orSme 1.
Le r e s e a u m u n i des c a p a c i t e s :
X 1 , X 2 , �9 . . . . X M
sera d i t a d m i s s i b l e ( s o u s - e n t e n d u : p o u r la d e m a n d e
[D] = [d0.]) si les c a p a c i t e s X u ( u = 1, ... M ) p e r m e t t e n t
d ' d c o u l e r s i m u l t a n e m e n t les d i f fd ren t s f lots d ~ j .
Le v e c t e u r X = X2 e a r a c t 6 r i s e le r e seau q u e
M
l ' o n v e u t c o n s t r u i r e (*). P o u r c e t t e r a i son nous l ' a p p e l -
l e rons v e c t e u r d e s e r i p t i f du rdseau.
L ' e n s e m b l e des v e c t e u r s ~ de sc r ip t i f s de r e s e a u x
admis s ib l e s (pou r u n e d e m a n d e [ D ] = [dij] dormde)
f o r m e uu s o u s - e n s e m b l e ~) de R M+. N o u s l ' a p p e l l e r o n s
d o m a i n e d ' a d m i s s i b i l i t 6 ( s o u s - e n t e u d u : r e l a t i f h la d e m a n d e [D]).
II.7. Seconde formulat ion du probl~me.
le p r o b l e m e de m a n i e r e m a t h e m a t i q u e m e n t
r i gou reuse .
�9 (P)
Les de f in i t i ons p r d c e d e n t e s p e r m e t t e n t de f o r m u l e r
p lus
M
M i n i m a l i s e r (I)(X?)= ~ ~ u ( X u ) , tz=l 1 ]
X2 a v e c X : = X u c ~ ,
M
X u >~ 0 p o u r u = 1 , . . . , M ,
~ R M+ = d o m a i n e d ' a d m i s s i b i l i t 6
r e l a t i f a u x d e m a n d e s [di j ] i=l ..... N , J = l . . . . . N .
L ' a p p a r t e n a n c e du v e c t e u r X: au d o m a i n e ~ ~ R M+
de f in i t l ' e n s e m b l e des c o n t r a i n t e s du p r o b l 6 m e (P).
I1 es t donc i m p o r t a n t de p o u v o i r c a r a c t d r i s e r faci le- m e n t un v e c t e u r X: de ~ a v a n t de r e c h e r c h e r les p ro -
p r i e t e s des so lu t ions o p t i m a l e s de (P).
I I I . C A R A C T I ~ . R I S A T I O N D E S S O L U T I O N S
Le d o m a i n e d ' a d m i s s i b i l i t d ~f) r e l a t i f h u n e n s e m b l e
de d e m a n d e s [D] ~ [d0.]~=l ..... N es t un p o l y 6 d r e : j = l . . . . . N
c o n v e x e de R M+. De p lus il es t n o n borne .
Ddmons t ra t ion .
Soi t d e u x r e s e a u x a d m i s s i b l e s c o n s t r u i t s h p a r t i r
du mf ime e n s e m b l e 0X' de nceuds e t d o n t les v e c t e u r s
desc r ip t i f s son t r e s p e c t i v e m e n t
Iill X~= x 2
M Iill Y2 et Y =
M
Soi t ~ un n o m b r e rdel 0 ~< ~ ~< I e t
I1 es t c la i r q u e le v e c t e u r Z X es t de sc r ip t i f d ' u n
rdseau a d m i s s i b l e p o u r les d e m a n d e s
[D ' ] = [d ' i j ] ddf inies p a r : d'~j = k d o ;
de m ~ m e le v e c t e u r (1 - - k ) Y p o u r les d e m a n d e s
[D"] = [d"iJ] d6f inies p a r : d"~i = ( 1 - ~ . )d i j .
Le r6seau d e n t le v e c t e u r d e s c r i p t i f es t ~ p e u t e t r e
cons iddr6 c o m m e la s u p e r p o s i t i o n de d e u x r6 seaux
d e n t l ' u n p e r m e t d ' d c o u l e r s i m u l t a n e m e n t t o u s les
f lots d'~j e t l ' a u t r e , t o u s l e s f lots d", ; . .
P u i s q u e d' 0 + d" 0 = d 0 , on en d d d u i t que ~ est d e s c r i p t i f d ' u n rdseau a d m i s s i b l e . D 'o f l la c o n v e x i t 6 . Le f a i t q u e ~ so i t u n p o l y e d r e de R M+ rdsu l te de
ce q u e l ' e n s e m b l e des c o n t r a i n t e s qu i le ddf in i ssen t
s e n t des c o n t r a i n t e s l inda i res (el les expriment la
c o m p a t i b i l i t 4 d ' u u r iot de p l u s i e u r s p r o d u i t s su r un
g r a p h e n o n o r i en t6 a v e c c o n t r a i n t e s de capac i td s su r
les arcs).
~D est n o n bo rne . E n ef fe t :
si X es t le v e c t e u r d e s c r i p t i f d ' n n r6seau admiss ib l e ,
a lors ~ = X + B (oil /~ es t un M - v e c t e u r non n e g a t i f
q u e l c o n q u e ) es t e n c o r e d e s c r i p t i f d ' u n r e seau a d m i s -
sible. D 'o f l la p ropr id t6 .
Le p o l y e d r e ~ c o m p o r t e doric u n c e r t a i n n o m b r e
de r a y o n s e x t r ~ m a u x ( d i r e c t i o n s inf in ies) . ( P o u r t o u t e s
ces de f in i t ions , on p o u r r a se r e p o r t e r a u x r e fe rences [3]
ou [4]).
N o u s a p p e l l e r o n s s o l u t i o n du p r o b l e m e (P) v e c t e u r .~ a p p a r t e n a n t au d o m a i n e ~ .
n n
(*) Certaines composantes X u peuvent ~tre nulles : cela signifie simplement qu 'on ne construit rien sur l 'art6re u.
III.2. R6seaux unirout6s. D6finition.
P a r m i les r d seaux admis s ib l e s , c ' e s t - h - d i r e c e u x d o n t
les v e c t e u r s desc r ip t i f s a p p a r t i e n n e n t au d o m a i n e ~ , c e r t a in s v o n t j o u e r un rSle t r6s i m p o r t a n t . Ce s o n t
les r d s e a u x d o n t les v e c t e u r s d e s c r i p t i f s son t o b t e n u s
h l ' a i d e de la p r o c d d u r e s u i v a n t e .
A. T~L~C., 29, n ~ 1-2, 1974 4 / 1 8
M. M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R E S E A U D E T I ~ L I ~ C O M M U N I C A T I O N S 29
Pour chaque demande d 0 , choisir un chemin (*) jo ignant les deux centres i et j ,
Installer sur chaque arc du chemin une capacitd suppldmentaire ~gale ~ la valeur di].
N o u s a p p e l l e r o n s de t e l s r6 seaux des Hseaux uni- routds. L a p r o c 6 d u r e q u i p e r m e t de les o b t e n i r es t appe l6e le routage des demandes.
L ' i n t ~ r ~ t des r 6 s e a u x u n i r o u t 6 s a p p a r a i t dans le
t h~or~me 2 q u e n o u s a l lons 6noncer . Mais a u p a r a v a n t
nous 6 t ab l i rons u n l e m m e .
I I I . 3 . L e m m e 1 .
La so lu t ion o p t i m a l e du p r o b l ~ m e (P) dans l eque l
t o u t e s les f o n c t i o n s (I)u(Xu) son t l indaires , sans cofi t
c o u r t c h e m i n au sens des l o n g u e u r s y u , p o u r
u = 1, ..., M) . C ' e s t d o n e u n r6seau un i rou t6 .
Ceci 6 t an t , il p e u t a r r i v e r q u e le rdseau o p t i m a l ne so i t pas un ique . C ' e s t le cas l o r s q u ' i l ex i s t e d e u x
c h e m i n s de m ~ m e cof l t d a n s le g r aphe . D a n s ces
c o n d i t i o n s , le p r o g r a m m e ( P L ) a d m e t une in f in i t6
de so lu t ions o p t i m a l e s (on d i t q u ' i l y a ddg6ndres-
cence) . Mais on p e u t a f f i rmer q u ' i l ex i s t e au m o i n s
u n e so lu t ion o p t i m a l e e o r r e s p o n d a n t h un rdseau
u n i r o u t 6 ( o b t e n u e en c h o i s i s s a n t a r b i t r a i r e m e n t un
e h e m i n p a r t i c u l i e r , l o r s q u ' i l ex i s t e p lus ieurs c h e m i n s
6qu iva l en t s ) . R e m a r q u o n s m a i n t e n a n t q u e , le d o m a i n e ~ 6 t a n t
n o n born6, le m i n i m u m Z* de ( P L ) p e u t ne pas 8tre
h d i s t a n c e finie. C ' e s t le cas s'il existe un cycle de eo~t ndgatif dans le g r a p h e des ar t~res .
D o n n o n s - n o u s p a r e x e m p l e le g r a p h e de la f igure 4,
off t o u s l e s cofi ts s o n t 6 g a u x h 4- 1 sur un c h e m i n
~ 8 : " 1
77 = - 1 F ~ " ) ' 9 = - 1
I ~'2 = 1 "?s - 1
FIG. 4. - - Exemple de r6seau avec cycle de eofit n~gatif.
f ixe ( fonc t ions de type 4) c o r r e s p o n d (en g6n6ral) h
un r6seau u n i r o u t 6 .
DdmonstraLion.
L o r s q u e les f o n c t i o n s r son t l in6aires de la f o r m e ~Pu(Xu) = y u X u , off yu est le eof i t de pa s sage
d ' u n e un i t6 de f lo t su r l ' a r c u, le p r o b l ~ m e (P) d e v i e n t
le p r o g r a m m e l i n6a i r e : M
m i n i m a l i s e r ~ . ~ = ~ yuXu , l l=t
a v e c R ~ c R M +
�9 ( P L )
of] y = [~'1, ~'2 . . . . . yM] ; - ~ = X2 �9
M
[ R e m a r q u o n s q u e , en t o u t e gdndral i t6 , le v e e t e u r y
p e u t a v o i r des e o m p o s a n t e s pos i t i ve s ou ndga t ives . ]
D a n s ees c o n d i t i o n s , le cof i t de pa s sage d ' u n e un i t6 de f lo t su r u n a rc u q u e l e o n q u e du g r a p h e ne
d d p e n d pas de la c a p a c i t 6 e f fec t ive X u de Fare.
A u t r e m e n t d i t , le eof i t du r o u t a g e de e h a q u e d e m a n d e
es t i n d ~ p e n d a n t du r o u t a g e effeet i f des au t re s
d e m a n d e s . D a n s ces c o n d i t i o n s , le rdseau de cofl t m i n i m a l es t o b t e n u p a r u n i r o u t a g e de e h a q u e d e m a n d e
s u r le e h e m i n de m o i n d r e cof i t ( e ' e s t -h -d i re , le p lus
(*) Le terme chemin est utilis6 ici, dans le cas d 'un graphe non orient6, pour ddsigner ce que l 'on appelle en g~n6ral chalne en th~orie des graphes.
de i h j e t h - - 1 sur u n cyc le de 5 arcs v e n a n t
s ' a r t i c u l e r su r le c h e m i n ; e t c o n s i d 6 r o n s une d e m a n d e
[dlj] de v a l e u r 1.
L a v a l e u r de la f o n c t i o n d c o n o m i q u e est alors :
Z = 5 (on ne pa s se p a s p a r le cycle) ,
Z = 0 (on passe u n e fois p a r le cycle) ,
Z = - 5 (on passe d e u x lo is p a r le cycle) ,
etc.
R 6 c i p r o q u e m e n t , un m i n i m u m Z* h d i s t a n c e finie
i m p l i q u e l ' a b s e n c e de cyc les de cof i t ndgat i f .
I I I . 4 . T h ~ o r ~ m e 2 .
Les p o i n t s e x t r S m e s du p o l y ~ d r e ~ c o r r e s p o n d e n t h des v e c t e u r s desc r ip t i f s de r 6 s e a u x un i ron t6s .
D ~ m o n s t r a t i o n .
On sa i t q u ' u n o p t i m u m ~ * h d i s t a n c e finie d ' u n p r o g r a m m e l in6a i re :
m i n i m a l i s e r Y" -Y,
�9 (PL) X ~ ~), p o l y ~ d r e c o n v e x e de R M + ,
se s i tue (en l ' a b s e n c e de d6gdn6rescence ) en un p o i n t
e x t r e m e du p o l y ~ d r e 9). N o u s p o u v o n s d o n e ca rac td -
r i s e r l ' e n s e m b l e des p o i n t s e x t r e m e s de ~ c o m m e
6 t a n t l ' e n s e m b l e des s o l u t i o n s o p t i m a l e s n o n d6g6-
ndr~es e t h d i s t a n c e f in ie du p r o g r a m m e (PL) ,
5 / 1 8 A. TI~L]~C., 29, n o8 1-2, 1974
30 M. M I N O U X . - C O N F I G U R A T I O N O P T I M A L E D ' U N R ] ~ S E A U D E T E L t ~ C O M M U N I C A T I O N S
lorsque ~ pa rcou r t 1~ M . Le lemme 1 permet alors d 'aff irmer que les poin ts extremes sont ob tenus pour des vecteurs ~, tels qu ' i l n 'ex is te pas de cycles de cofit n4gat if et que, duns ce eas, ils cor responden t h des r6seaux unirout6s . D'ofl le th6or6me.
Remarque.
Deux r6seaux uni rout6s ob tenus h pa r t i r d 'ensem- bles de plus courts chemins diff6rents p e u v e n t avoir le m~me vec teu r descriptif. Pa r suite, la correspon- dance :
points extremes de ~ -~ r6seaux uni rout4s est, en g6n6ral, in ject ive.
IV, PROPRI]~TI~.S DES SOLUTIONS OPTIMALES
A v a n t de d o n n e r les caract6r isat ions des solutions opt imales du probl6me (P), nous 6 tabl i rons un cer- t a in n o m b r e de r6sultats , applicables aux fonet ions non lin6aires quelconques , mais eon t in f lmen t diff6- ren t iab les d ' u n e par t , et d ' au t r e pa r t aux fonct ions concaves sans hypoth6se de diff6rentiabili t6.
Certains des th6or6mes ci-dessous r e p r e n n e n t des r4sul ta ts connus sur les solut ions opt imales de pro- grammes non lin6aires sous cont ra in tes lin6aires, et on pour ra les r e t rouve r par exemple duns [6]. D 'aut res , par contre, 6 tabl i ssent des r6sul tats similaires dans le cas de fonct ions non con t in f iment diff6rentiables.
~ ' = {X e RM / .~ >~ 0 ; [A]X: /> b*}.
les condit ions de K u h n et Tucker en X[ ~ sont ndcessaires pour que X7 ~ soit op t i mum du pro- bl6me (P) ' [6] et pa r cons6quent p e r m e t t e n t de caract6riser l ' op t ima l i t6 locale d ' une solution. Giles s '6crivent :
::1 ~ = (~L1 , ~L 2 . . . . . . ~ t p ) ~> O ~ tel que :
t g ~ d O(.~ ~ -k ~ [A] = 0', (K.T.) I ~([ A l 2 ~ b) = 0.
Or les condi t ions K .T . sont 4galement les condi- t ions de K u h n et Tucker , 6crites en ~o, pour le pro- gramme (PL) ' . Comme le p rogramme (PL) ' est lindaire, on salt que K.T. sont des condi t ions n6ces- saires et suffisantes d 'op t ima l i t6 globale. On en d6dui t la propri6t6 annonc6e , ainsi que la par t icular i t6 q u ' u n op t imum local ~o de (P) ' (tel que g ~ d (I)(,~ ~ =/= O) est, soit un po i n t extr4me, soit un po in t de la fron- ti6re du poly6dre ~ ' (duns ce cas la solution du pro- gramme (PL) ' est d6g6n6r6e).
Remarque.
Nous avons suppos6 que l ' on avai t g a d (I)(R ~ va 0. Sans cette hypoth6se, en effet, le p rogramme (PL) ' n ' a u r a i t pas de sens. P o u r le cas qui nous int6resse, les fonctions Ou(Xu) 6 t a n t monotones s t r i c t emen t croissantes, on a tou jours : g a d qb(~) > 0 pour t ou t .~ ~ RM+.
D'au t r e par t , (I)(.~) doi t ~tre suppos6e con t in f imen t diff6rentiable de fa~on h pouvo i r appl iquer les condi- t ions de K u h n et Tucker .
IV.1. L e m m e 2.
Soit O(~:), ~ G RM+, une fonct ion non lin4aire con t in f imen t diff6rentiable des var iables :
X 1 , X 2 , . . . , X M ,
Soit [A] une mat r ice P • M h coefficients r6els et un vec teur h P composantes .
Si _~o (tel que gi'~d r "~ va 6) est un o p t i m u m local du p rog ramme (P) ' :
min ima l i se r (I)(~:),
�9 (P) ' avec [A] ~ /> ~,
2~>o_ alors ~0 est une solut ion opt imale du p rog ramme lindaire :
min ima l i se r ( ~ - .~o). gFAd qb(~o),
�9 (PL)' [AI R /> b ~, 2 > 1 6 .
Ce rdsu l ta t s ' app l ique en par t ieu l ie r si ~o est o p t i m u m global de (P').
D d m o n s t r a t i o n .
Comme le domaine des cont ra in tes de (P ' ) est un poly6dre eonvexe ~ ' de RM+,
IV.2. L e m m e 3.
Soit (I)(X), ~: ~ R M+, une fonct ion non lin6aire concave des var iab les X 1 , X~ , ..., X M sur le poly6dre if) convexe.
Si ~0 est un o p t i m u m global du probl6me :
m in ima l i s e r (I)(~),
�9 (P) avec ~: ~ ~ ,
alors .~o est so lu t ion op t ima le du p rogramme lin6aire :
m in ima l i s e r ( X - .~o). s -gAd (I)(x~ �9 (PL) avec ~ ~ ~),
off s-gr~d 0 ( ~ ~ est u n sons-gradient de �9 en ~o.
D d m o n s t r a t i o n .
Rappelons q u ' u n e fonc t ion dp(~) concave propre (c 'est-h-dire [(:I)(X:)[ ~ q- oo sur son domaine de d6finition) poss~de u n sous gradient , s -gAd (I)(~:~ en tou t point ~0 in t6 r ieur h son domaine de d6fini t ion
et on a :
(I)(~) ~< (I)(x ~ + (X - - ~o) . s - g ~ d qb(~o),
pour t ou t X a p p a r t e n a n t au domaine de d6fini t ion de (I) [7, th6or6me 2, p. 495].
A. TI~LI~C., 29, n ~ 1-2, 1974 6/18
M. M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A U D E TI~LF, C O M M U N I C A T I O N S 31
Si _~o est o p t i m u m globa l de (P), on a :
O(R) > O(Ro) , v R � 9 9 ,
d'ofl :
(I)(R ~ ~< (I)(~) ~< dP(R ~ q- (~i~ _ Ro) �9 s - g ~ d (I)(R~
et p a r sui te : ( ~ : - - R ~ ~ 1> 0, V R �9 ~), ce qui p r o u v e que R ~ est o p t i m u m du p r o g r a m m e l indaire (PL) .
Remarque.
Le l e m m e 3 ne suppose r ien sur la cont inui t6 ou la d i f f6rent iabi l i t6 de la fonc t ion (I)(R). I1 est 6tabl i en s u p p o s a n t la seule concav i t6 de (I)(R).
IV.3. L e m m e 4.
Soit (I)(.~), R �9 RM+, une fonct ion non l in6aire concave des va r i ab le s X z , X 2 , ..., X M sur le poly~dre ~) convexe.
Si R ~ est un o p t i m u m local du probl~me :
m in ima l i s e r (1)(X),
�9 (P) avec ~ �9 ~D,
X t > 0 ,
alors R ~ est so lu t ion o p t i m a l e du p r o g r a m m e lin6aire :
m in ima l i s e r (X - - R0) �9 s - g ~ d (I)e~~
�9 (PL) avec R �9 ~),
R ~ > 0 ,
oh s - g ~ d (I)(R ~ est un sous -g rad ien t de (I) en R ~
D d m o n s t r a t i o n .
Soit R ~ o p t i m u m local de (P). Cela veu t dire qu ' i l exis te un vo is inage r de R ~ te l que R ~ soit o p t i m u m global p o u r ~D N cU. O r on p e u t choisir ~U convexe. C'est le eas si on a d o p t e la no rme :
I R - - R ~ = Max I I X i - - R ~ i
et si on eonsid~re un vo is inage :
"u= (XlllX-Roll < ,} ,
pour r donn6.
Dans ces condi t ions , R ~ est o p t i m u m global de (I)(R) sur le d o m a i n e ~ N qY convexe , et on peu t app l ique r le lemme 3. D'ofl la propr idtd .
I V . 4 . T h 6 o r S m e 3. [6, pp. 90-93]
Si la fonc t ion (I)(R) es t concave , alors l ' o p t i m u m globa l du p rob l~me ( P ) :
m in ima l i s e r Z = q)(R),
(P) avec .~ �9 if) po ly~dre convexe de RM+
est, en gdndral , un po in t e x t r e m e de ~ et il exis te t o u j o u r s un p o i n t e x t r e m e de ~ qui soi t o p t i m u m global du p rob l~mc (P). D ' a u t r e p a r t , si l ' o p t i m u m global es t a t t e i n t en p lus ieurs po in t s ex t rSmes , il est a t t e i n t en une inf ini t6 de poin ts , combina i sons l in6aires convexes de ces po in t s ex t remes .
D ~ m o n s t r a t i o n .
Soit R ~ l ' o p t i m u m global (absolu) du p rob l~me (P) et s - g ~ d (I)(R ~ un sous -g rad ien t de (I) en .~o.
Si la so lu t ion op t ima le du p r o g r a m m e (PL) :
m i n i m a l i s e r (X - - X~ �9 s - g ~ d (I)(X~ (PL) avec R �9 9 ,
est un ique (non ddgdn6r6e), alors le lemme 3 p e r m e t d ' a f f i rmer que R ~ est un p o i n t e x t r e m e du doma ine 9 , e t c o r r e spond p a r cons6quent h u n r6seau uni routd . Supposons donc que la so lu t ion o p t i m a l e de (PL) soit d6g6n6r6e, e t que R ~ puisse ~tre exp r im6 c o m m e c o m b i n a i s o n l in6aire convexe de deux po in t s ex t r emes
et V de 9).
Posons B = ~ - - V, (-~ =/= 6 ) ,
on a : ~ = R ~ ocB
= Ro _ (1 - - ~)_~,
0 ~ I .
L a fone t ion (I) est concave, e t en u t i l i s a n t la p ro- pri6t6 d ' u n e fonc t ion concave :
O(~ § ~) ~< (I)(~) + ~ . s-grai l r
on p e u t derire :
q~(~) ~< qb(Ro) + ~B �9 s - ~ - d O(Ro),
r ~< O(Xo) - - (1 - - ~) n �9 s - ~ O(Ro).
On ne p e u t pas avo i r H . s - g ~ qb(R ~ < 0, car cela i m p l i q u e r a i t 0 ( ~ ) < O(R~ De mSme, on ne p e u t pas a v o i r H . s - ~ - d O ( R ~ > 0, ca r cela impl i - q u e r a i t O(V) < O(R~
P a r sui te , H - s - ~ O ( R ~ = 0, e t on a :
�9 O ( ~ ) = O ( ~ ) = O(Xo).
Dans ces cond i t ions , nous m e t t o n s en dvidence un p o i n t e x t r e m e de ~ qui est o p t i m u m g loba l de (P) : p a r e x e m p l e le p o i n t ~ .
Venons -en h la deuxi~me p a r t i e du thdor~me.
Supposons qu ' i l exis te deux po in t s ex t rSmes ~ et F de 9 , te ls que O(U) = O(V) = M i n O ( R ) .
L a eoncav i t6 de la fonc t ion p e r m e t d '~cr i re :
o ( x ~ + ( 1 - - x ) V) < x o ( ~ ) + ( ~ - - x ) o ( V ) ,
d'of i O(XUq- ( 1 - X)V) ~< O ( ~ ) = (I)(V),
quel que so i t k.
Or si q ) ( ~ ) = (I)(V) est la v a l e u r m i n i m a l e de (P sur ~D, on do l t avo i r :
�9 (I)(XU + (1 - - X) V) = O ( ~ ) = O(V),
et p a r su i te (I)(X:) = (I)(~) = 0 ( ~ ) , g R �9 IU, V].
7 / 1 8 A. T~LE, C., 29, n ~ 1-2, 1974
32 M. M I N O U X . - - C O N F I G U R A T I O N O P T I M A L E D ' U N IRI~SEAU D E T ] ~ L I ~ C O M M U N I C A T I O N S
IV.5. Th6orSme 4.
Si la f o n c t i o n (])(.~) es t s t r i c t e m e n t concave, alors
l ' o p t i m u m g loba l du p r o b l 6 m e (P) es t u n i q u e . C 'es t un p o i n t ex t r f ime du p o l y 6 d r e ~ .
D d m o n s t r a t i o n .
Soi t ~ e t V d e u x p o i n t s e x t r e m e s de ~ te ls que :
O ( U ) = dO(~) = Min d)(.~),
Y'eCO e t a # F.
Alors , p o u r 0 < k < 1 on p e u t dcr i re :
( I ) ( Z U + ( l - - k ) ~ ) < XgP(~)+ ( l - -X) ~ ( ~ ) = d P ( ~ ) =a lP(g) ,
ce q u i c o n t r e d i t l ' o p t i m a l i t d g l o b a l e de ~ e t V. D 'of i
le t h d o r ~ m e .
IV.6. Th6or6me 5.
Si la f o n c t i o n (I)(x) es t s t r i c t e m e n t c o n c a v e , e t si Xo es t l ' o p t i m u m g loba l ( u n i q u e ) du p r o b l 6 m e (P),
a lors le p r o b l ~ m e ( P L ) a d m e t Xo c o m m e so lu t ion
u n i q u e (non ddgdndrde).
D d m o n s t r a t i o n .
Si le p r o b l 6 m e ( P L ) a u n e s o l u t i o n o p t i m a l e ddgd-
ndrde, a lors il ex i s t e au m o i n s un p o i n t e x t r e m e =/= Xo te l q u e ~ . s -gra i l (I)(.~ ~ = ~:o . s ~ (I)(X7 ~
d ' a p r ~ s la p r o p r i d t d de c o n c a v i t d s t r i c t e :
(I)(~) < dP(X7 ~ + ( ~ - - X: ~ �9 s - g r a d (I)(X:o),
on a u r a i t :
dp(~) < ap(X:0),
ce q u i c o n t r e d i t l ' o p t i m a l i t d (g loba le ) de A7 ~
IV.7. Th6or~me 6.
M
Soi t ( I ) ( , ~ ) = ~, dPu(Xu) u n e f o n c t i o n sdpa rab le ll=t
des v a r i a b l e s X~ , X 2 , ..., X M �9
Si les f o n c t i o n s dPu(Xu) s o n t concaves , alors l ' op t i -
m u m g l o b a l du p r o b l 6 m e (P) n ' e s t pas n d c e s s a i r e m e n t
u n i q u e (ddgdndrescence) , m a i s il e x i s t e u n p o i n t e x t r e m e ( rdseau u n i r o u t d ) o p t i m u m g l o b a l du p ro - b l a m e (P).
Si les f o n c t i o n s dPu(Xu) s o n t s t r i c t em en t concaves,
a lors l ' o p t i m u m g l o b a l de (P) es t u n i q u e , e t c ' e s t un p o i n t e x t r e m e de ~ ( rdseau un i rou td ) .
D d m o n s t r a t i o n .
II suff i t de r e m a r q u e r q u e (I)(~7) es t c o n c a v e (ou s t r i c t e m e n t c o n c a v e s u i v a n t les cas) c o m m e s o m m e
de f o n c t i o n s c o n c a v e s (ou s t r i c t e m e n t concaves ) . On a p p l i q u e alors les t h d o r ~ m e s 3 e t 4.
IV.8. Vers une caract6risation des optimums locaux.
Les t h d o r ~ m e s 3, 4 e t 6 q u i p r d c ~ d e n t d o n n e n t des
c o n d i t i o n s ndcessaires d ' o p t i m a l i t d loca le ou globale .
Mais nous s o m m e s s u r t o u t in tdressds p a r le c a r a c t ~ r e
suf f i sant ou n o n de t e l l es cond i t i ons . N o u s a l lons
vo i r , su r des e x e m p l e s , q u e dans c e r t a i n s cas la c o n d i t i o n :
.~o est s o l u t i o n o p t i m a l e de ( P L )
n ' e s t pa s suf f i sante .
a) P r e n o n s le cas, d ' a b o r d , de f o n c t i o n s concaves
et c o n f i n e m e n t d i f f d ren t i ab l e s ( d o n c c o n t i n u e s e t diffd- r en t i ab le s ) . Cons idd rons le cas de la f igure 5 : la
- - grad q) (X~ \
I
Fro. 5. - - X ~ est un minimum dans la direction d.u gradient, mais il y a ddg6ndreseenee et ce n'est pas un optimum global.
c o u r b e ( I ) (X : )= (I)(_~ ~ es t t a n g e n t e en Xo h une des
c o n t r a i u t e s .
Le p r o g r a m m e l inda i re ( P L ) a d m e t X ~ c o m m e
so lu t i on o p t i m a l e , m a i s il y a ddgdndrescence e t t o u s
les p o i n t s du s e g m e n t IX ~ U] son t des so lu t ions o p t i m a l e s de (PL) . D a n s ces c o n d i t i o n s , X ~ n ' e s t pas
o p t i m u m local , c a r t o u t d d p l a c e m e n t d a n s l a d i r e c t i o n
= ( ~ _ .~o) e n t r a i n e u n e ddc ro i s sance s t r i c t e de ~(~).
b) P r e n o n s m a i n t e n a n t le cas de f o n c t i o n s c o n c a v e s ,
c o n t i n u e s en ~0 , m a i s n o n n d c e s s a i r e m e n t d i f fdren-
t i ab les . S u p p o s o n s q u e la c o u r b e (I)(X) = (I)(X ~ prd- s en t e en X ~ un p o i n t a n g u l e u x .
Su r la f igure 6, X ~ es t s o l u t i o n o p t i m a l e u n i q u e
~ ~ (X+o)
Fro. 6. - - X ~ est un minimum absolu (unique) dans la direc- tion d 'un sous-gradient de q) (mais pas pour t o u s l e s sous-
gradients en X ~ et X ~ n 'est pas optimum local de q).
A. T~LkC., 29, n ~ 1-2, 1974 8 / 1 8
M. M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R ] ~ S E A U D E T I ~ L ] ~ C O M M U N I C A T I O N S 33
(non ddgdndrde) de (PL) . E t p o u r t a n t , X ~ n ' e s t pas un o p t i m u m loca l de (P).
Les thdor~mes qui v o n t suivre von t prdciser les cas dans lesquels on p e u t conclure h l ' o p t i m a l i t d locale.
IV .9 . T h 6 o r S m e 7.
Soit (I)(.~) une fonc t ion concave con t in f imen t diffd- r en t i ab le des v a r i a b l e s X t , X e , . . . , X M �9
Soit .~o un p o i n t de ~D (poly~dre eonvexe) te l que ~:o soit so lu t ion o p t i m a l e u n i q u e (non d6gdndrde) de :
m i n i m a l i s e r XT. g ~ d (I)(~o), �9 (PL) avec .Y ~ ~D.
Alors ~ o es t un o p t i m u m local de (P).
Ddmonstration.
Si .~o est so lu t ion o p t i m a l e non ddg~ndrde de (PL),
alors on a : ( . ~ - _~o).gr~d (I)(X: ~ > 0,
pour t ou t X e ~ ( R v e Xo).
Soit .~t un p o i n t que lconque de ~ (_~ r ~o). Posons ~ = ~ t Xo.
Consid6rons F e n s e m b l e des po in ts :
X = + X ~ , X > 0 .
D 'apr~s la convex i t~ de ~I), il existe a ~ 0 tel que :
D 'apr~s l ' h y p o t h ~ s e pos6e on peu t dcrire :
�9 g ~ d ( I ) ( X ~ k > 0.
D ' a u t r e p a r t on a :
(I)(.~) = (I)(X ~ + (_~ - - .~o). gr'ad (D(X~ (_~-- .~o). ~((XS,
off ( R - RO).H(X) /> o, V R RM,
et off II )ll- o, q u a n d X - + .~o.
P a r sui te :
0 ( )~) = ~b(~o) + k d �9 g ~ d (I)(A: ~ - - k g �9 H ( ~ ) .
On a ~ v i d e m m e n t i [ . H ( X ) ~> O,
et I -m >I -< II ll II CX>ll �9 Puisque o q u a n d ~: - -~ ~:o, il exis te ~q > 0
tel que I 1 . ~ - ~:o[1 ~ ~ ~ [[H(X-)][ ~< ] ] d [ [ k / 2 ,
a lors p o u r II x - - X~ < o n a :
o <~ g . W ( ( x ~) <~ k]2,
et p a r sui te
(I)(~) t> (I)(-~ ~ + k [ d . g ~ d (I)(_~ 0) - - k [ 2 ] ,
&off O(,K) /> (I)(x ~ + k k ] 2 ,
et �9 ( p ( ~ ) > q ) ( ~ o ) , p o u r [1~--~olI < ~ e t ~ = / = ~ o ,
Ceci p r o u v e l ' o p t i m a l i t 6 locale de .~.
IV.10. T h 6 o r S m e 8.
Soit (I)(~) une fonc t ion c o n c a v e des va r i ab le s
X 1 , X 2 , . . . , X M .
Si .~o ~ ~D est so lu t ion o p t i m a l e u n i q u e (non ddgd- n6rde) de P L :
m i n i m a l i s e r X . s - g r a d (I)(.~~ (PL) avec X ~ 9 .
pou r t o u s l e s sous -g rad i en t s de (I) en ~o, alors ~ o est un o p t i m u m local de (P).
Ddmonstration.
Les hypo the se s son t ici :
( ~ _ ~o). ? > o,
pour t ou t ~ :/: .~o, ~ ~ 9 , et pour tous les sous- g rad ien t s ~ en ~0.
R a p p e l o n s d ' a b o r d q u ' u n e fonc t ion concave p r o p r e (c 'es t -h-d i re te l le que [(I)(~)[ < + oo) poss~de un sous -grad ien t en t o u t p o i n t in td r i eur de son ensemble de ddfini t ion [7, th6or~me 2, p. 495].
R e m a r q u o n s e n s u r e que l ' ex i s tence d ' u n sous- g r a d i e n t en ~ o i m p l i q u e l ' ex i s t ence des d6rivdes d i rec t ionnel les D:(I) d6finies p a r :
D:(I)(d) = l im (I)(-~~ + k ~ - (I)(_~~ X->o+ ~. k
pou r t o u t ff dJ~:~ M.
En effet, la fonc t ion g(k) ~ (I)(X:~ + X~) - - ( I ) ( ~ ~ 6 t an t concave, la fone t ion y(X) = g(X)/k a la p ropr id td d ' e t r e non d6cro i s san te ( q u a n d X d6eroit) .
D ' a u t r e p a r t , pu i squ ' i l ex i s te un sous -g rad ien t ~ :
cp(~o + z ~ ) ~ (I)(~o) .<< zd. ?,
&off y (k) ~< d . T, Vk .
On en d6du i t l ' ex i s t ence d ' u n e l imi te :
D:(I)(d) = l im y (k ) ~< ft. ~ . k---)- 0 +
I1 en r~sul te q u ' u n e cond i t i on n~eessaire et suffi- sau te pour que T soi t un sous -g rad ien t est que :
�9 d . T /> D :(I)(d), V d E R M
I1 est de p lus poss ib le de d~mon t r e r que :
(2) D:(I)(~) = Min (~ . -~) ,
off ~ est l ' e n s e m b l e des sous -g rad ien t s en ~:o [7, th6or~me 16, p. 512].
I1 en r6sul te q u ' u n e cond i t i on ndcessaire et sum- sau te pour que D:qb(~) > 0 est que l ' on a i t :
~ . ? > o, v ? e ~ .
D'apr~s les h y p o t h e s e s fa i tes , ce t te cond i t ion es t rdalis6e pou r 3 (d i r ec t i on rdal isable) , ce qui v e u t dire que D:(I)(~) ~ 0, V d (d i rec t ion rdal isable) .
D'ofl l ' o p t i m a l i t 6 locale de .~o.
9/18 A. T~:L~C., 29, n ~ 1-2, 1974
34 M. M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A U D E T I ~ L I ~ C O M M U N I C A T I O N S
I V . 1 1 . Les probl~mes soulev6s par la recherche d'un optimum absolu,
Le t h 6 o r ~ m e 6 p e r m e t de l i m i t e r la r e c h e r c h e de
la so lu t ion o p t i m a l e X * de (P) a u x p o i n t s e x t r e m e s du
p o l y ~ d r e c o n v e x e ~ . D ' a p r ~ s le thdor~me 2, on p e u t
a j o u t e r q u e la r e c h e r c h e se l i m i t e h l ' e x a m e n des
v e c t e u r s d e s c r i p t i f s de r 6 s e a u x un i rou t6s . I1 n ' e n
r e s t e pas m o i n s q u e le n o m b r e de r6 seaux u n i r o u t 6 s o b t e n u s h p a r t i r d ' u n g r a p h e , m ~ m e de t a i l l e mod6r6e ,
es t en g6n6ra l co lossa l (des mi l l i a rds ) . Les c o n d i t i o n s n6cessa i r e s d ' o p t i m a l i t d (lemmes 3
el 4) p e r m e t t e n t de r e j e t e r a priori un g r a n d n o m b r e
de r6 seaux u n i r o u t 6 s : ce s o n t les v e c t e u r s Xo qu i
ne s o n t pas s o l u t i o n s o p t i m a l e s du p r o b l ~ m e l in6aris6 (PL) en Xo.
E n f i n , l o r s q u e les c o n d i t i o n s n6cessa i res s o n t sa t i s -
fa i tes , les lhdor~mes 7 el 8 p e r m e t t e n t de conc lu re ,
la p l u p a r t du t e m p s (cas de d6g6n6rescence mis
pa r t ) h l ' o p t i m a l i t d ( loca le) de la so lu t ion . Ceci 6 t an t ,
il n ' e s t pas poss ib l e de d6f in i r l ' o p t i m u m abso lu de
n o t r e p r o b l ~ m e , a u t r e m e n t q u e c o m m e le meilleur opt imum local.
L a r a i son e n e s t q u e le p r o g r a m m e (P) :
ra in (I)(~) c o n c a v e
�9 ( P ) a v e c X ~ ~ p o l y ~ d r e e o n v e x e ,
n'est pas un programme math~matique convexe.
(Si la f o n c t i o n qb(~) 6 t a i t convexe au l ieu d ' e t r e
concave, alors il en s e r a i t t o u t a u t r e m e n t , les cond i - t i ons de K u h n e t T u c k e r 6 t a n t n6eessa i res e t suffi-
s an t e s dans le eas de f o n e t i o n s (I) G CI).
L a q u e s t i o n se p o s e a lors de s a v o i r si l ' d n u m 6 r a t i o n
P u r e e t s i m p l e es t h e n v i s a g e r ou non. L ' e x e m p l e qui ' su i t p e r m e t de se f a i r e u n e idde de l ' o r d r e de g r an -
d e u r du n o m b r e d ' o p t i m u m s l o e a u x p o u r u n p e t i t
r6seau.
IV.12. Exemple montrant la multiplicit6 des optimums locaux.
Le rdseau q u e n o u s a l lons 6 t u d i e r c o m p r e n d 7 nceuds
n u m 6 r o t 6 s de 1 h 7, il e s t e x t r a i t du r6seau n a t i o n a l
f ran~ais :
1 P A R I S
2 AMIENS
3 ROUEN 4 ORL1~ANS
5 C H A L O N S
6 BEAUVAIS
7 LE M A N S
L a m a t r i c e des d e m a n d e s [ D ] = [d,j] es t cel le du
t a b l e a u I. Les f o n c t i o n s de cof l t r son t de la f o r m e :
~ u ( X u ) = luq~(Xu), oh la f o n c t i o n ~0 r e p r d s e n t e le cof i t en k i l o f r ancs p a r k i l o m ~ t r e de c o n s t r u c t i o n de l a
c a p a c i t 6 X u et :
T&BI,EAU I
Mortice des demandes (exemple & 7 n~uds )
2 3 4 5 6
17,7 41,9 36,4
5,1 0,9
4,9
17,4 6,4 17,8
3,9 0 0 2,3 1,0 1,6
1 0 0,4
0 0
i ~(Xu) = O, p o u r Xu = O, T(Xu) = 24 + 3,55 Xu p o u r 0 ~< Xu <~ 28,8,
T(Xu) = 42,2 + 2,92 X u p o u r 28,8 ~ Xu �9
lu es t la l o n g u e u r k i l o m 6 t r i q u e de l ' a r c u.
E l les son t r ep r6sen t6es f igu re 7.
(Xu)
en k F
24
X u
28,8
FIG. 7. - - Courbes de cofit 9(Xu) en kilofrancs par unit~ de longueur dans l 'exemple h 7 nc0uds.
E n f i n , la m a t r i c e des l o n g u e u r s k i l o m 6 t r i q u e s lu des
d i f f6rents arcs u = (k, l) ~ U es t donn6e t a b l e a u II .
TABLEAU I I
Matrice des longueurs kilomdtriques des arcs pour l'exemple & 7 centres
1 2 3 4 5 6 7
126 118 117
110 210
180
173 83 214
210 59 250 210 82 170
210 180 130
140 310 210
A p a r t i r de ees donn6es , on p e u t ob ten i r , p a r
e x e m p l e , les d i f f6ren ts o p t i m u m s l o c a u x des f igures 8
h 12 (la m 6 t h o d e e m p l o y 6 e se ra expos6e au c h a p i t r e V).
D a n s c h a q u e cas, on a i n d i q u 6 en ca rac t~ re s i t a -
l iques sur les arcs du r6seau la v a l e u r des flots eumuMs
les e m p r u n t a n t . Les e i n q o p t i m u m s l o c a n x q u e nous v e n o n s de
d o n n e r n ' e n r e p r 6 s e n t e n t q u e q u e l q u e s - u n s p a r m i b e a u c o u p d ' a u t r e s . D ' u n e f a~on gdn6ra le , l e u r n o m b r e
es t tr~s 61ev6, s u r t o u t p o u r des r6 seaux de t a i l l e
A. T~:L~C., 29, n ~ 1-2, 1974 10/18
M. M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A U D E T I ~ L I ~ C O M M U N I C A T I O N S 3 5
52"x A
7 v- / 4 4
4
FIG. 8. - - Rdseau 1, coot 104 278 kilofrancs.
5 2
5 25 .'*
4 FIG. 9. - - Rdseau 2, coot 102 849 kilofrancs.
2
1 7 9 25 ...-.e5 7 ~ 63
4
FIG. 10. - - R6seau 3, coot 102 253 kilofranes.
2
3 ~ 6 ~ 8 5
57~t j 25
7 2 ( ~ ~ 63
4 FxG. l l . - - l:16seau 4, cofit 102089 (minhnum) kilofrancs.
2
o 25
4 FIO. 12. - - R6seau 5, coot 105 409 kilofranes.
i m p o r t a n t e . I1 se ra , p a r c o n s 6 q u e n t , h o r s d e q u e s t i o n
de les 6 n u m 6 r e r t o u s d a n s l a p r a t i q u e .
C e p e n d a n t , que l l e s q u e s o i e n t les p r o c 6 d u r e s a lgo-
r i t h m i q u e s e m p l o y 6 e s p o u r l i m i t e r l a c o m b i n a t o i r e
d u p r o b l ~ m e , o n c o n ~ o i t b i e n q u e l e u r ef f icaci t6
d 6 p e n d r a , e n p r e m i e r l i eu , de l a r a p i d i t d a v e c l a q u e l l e
o n p o u r r a c a l c u l e r des o p t i m u m s l o c a u x . C ' e s t s u r ce
p o i n t q u e n o u s a l l o n s i n s i s t e r m a i n t e n a n t .
V. LA RECHERCHE DES O P T I M U M S LOCAUX
D a n s ce q u i su i t , n o u s c o n s i d ~ r e r o n s le cas off les
f o n c t i o n s (~u(Xu) s o n t c o n c a v e s e t c o n t i n f i m e n t
d i f f d r e n t i a b l e s su r ]0, + o0] .
D a n s ce cas , u n e condition ndcessaire p o u r q u e ~ 0
so i t o p t i m u m local de (P ) e s t q u e X0 s o i t u n e s o l u t i o n
o p t i m a l e d e ( P L ) :
m i n i m a l i s e r (~7 - - .,~o). g ~ d aP(.XT~
�9 (PL) X7 ~ ~) C I~M+,
(cf. lemme 2, w IV).
I n v e r s e m e n t , si X ~ e s t s o l u t i o n o p t i m a l e unique d e ( P L ) , a l o r s _~o es t c e r t a i n e m e n t o p t i m u m loca l d u
p r o b l ~ m e (cf. thdor~me 7, w IV) .
Ceci d i t , si l ' o n se r6 f~re a u x r d s u l t a t s d u c h a -
p i t r e IV , o n e s t n a t u r e l l e m e n t c o n d u i t h e n v i s a g e r
u n e p r o c 6 d u r e e n d e u x p h a s e s .
Premiere phase.
O n c o m m e n c e p a r r e c h e r c h e r u n p o i n t e x t r e m e ~:l
de ~ s a t i s f a i s a n t l a e o n d i t i o n n ~ c e s s a i r e d u lemme 2.
Deuxi~me phase.
O n v~r i f i e e n s u i t e q u e l a c o n d i t i o n s u f f i s a n t e d u
thdor~me 7 e s t s a t i s f a i t e , ou a l o r s o n m e t e n 6 v i d e n e e
u n a u t r e p o i n t e x t r e m e ~:1+1 t e l q u e q) ( .~ l+l ) < r
V.1. Recherche d'un point extreme satis- faisant les conditions n6cessaires d'optimalit6 locale.
U n e m d t h o d e c l a s s i q u e de r 6 s o l u t i o n d ' u n p r o b l b m e
d ' o p t i m a l i s a t i o n de f o n c t i o n n o n l i n d a i r e sous c o n -
t r a i n t e s l i n 6 a i r e s e s t l a m d t h o d e de s l i n 6 a r i s a t i o n s
s u c c e s s i v e s [5] : p a r t a n t d ' u n p o i n t e x t r 6 m e ( r 6 s e a u
u n i r o u t 6 ) ~ : l ~ ~ , o n e n g e n d r e u n e s u i t e :
X l, X 2, ..... X~
d e p o i n t s e x t r e m e s de ~) t e l l e q u e :
aP(X 1) 1> aP(X 2) /> ........ /> r
1 1 / 1 8 A. T~L~C., 29, n ~ 1-2, 1974
36 M. MINOUX. -- CONFIGURATION OPTIMALE D'UN RI~SEAU DE TEL]~COMMUNICATIONS
Le p o i n t X i+~ es t o b t e n u h p a r t i r du p o i n t X i en
r d s o l v a n t le p r o g r a m m e l in6a i re :
m i n i m a l i s e r (_~ - - ~ i ) . g r~d (I)(.~i), (PL) ~ a 9).
P a r su i t e (_~i+~ - - ~ / ) - g ~ d r = O,
et ~:/ es t auss i s o l u t i o n o p t i m a l e de (PL) . D 'o f l la
propr id t~ .
L a r e c h e r c h e s ' a r r S t e l o r s q u ' o n a o b t e n u d e u x
p o i n t s cons6cu t i f s X ~ e t X ~+~ te ls q u e :
�9 (I)(X i+1) = (I)(X/).
N o u s a v o n s v u , p a r a g r a p h e I I I . 3 , c o m m e n t s 'effec-
t u e la r d so lu t i on du p r o b l ~ m e ( P L ) : r a p p e l o n s s im-
p l e m e n t q u e c h a q u e a rc du rd seau ~ t a n t m u n i d ' u n e
l o n g u e u r ( d ' u n cof i t )
d O u T u - d X u (X/u)
on r e c h e r c h e l ' e u s e m b l e des p lus c o u r t s c h e m i n s sur
le g r a p h e r e l a t i f a u x l o n g u e u r s Tu(U = I . . . . . . M).
L a s o l u t i o n o p t i m a l e .~i+~ de ( P L ) es t a lors le v e c t e u r d e s c r i p t i f du r6seau o b t e n u p a r r o u t a g e de la d e m a n d e
au p lus c o u r t chemin .
Ce q u i p r e c e d e p e u t ~tre r~sum~ d a n s la procddure 1.
Procddure 1 ( r e c h e r c h e d ' u n o p t i m u m local) .
1) P a r t i r d ' u n e so lu t ion i n i t i a l e d o n n 6 e ~:0.
2) A l ' i t 6 r a t i o n i c a l cu l e r
dO(X/u) T ~ , dX/u , p o u r u = 1 . . . M.
3) D6f in i r .~i+~ c o m m e la so lu t ion , o p t i m a l e de :
M m i n i m a l i s e r ~ / . . ~ : y], T/u X u
( P L ) .=, '
a v e c ~ ~ 9). ,~
4) Si 0 ( ~ l) va ( I ) (Xi+l) , f a i r e i = i + 1 e t r e t o u r n e r
en 2). ........
5) si O(R9 = O(SV+~), fin.
R e m a r q u o n s dbs m a i n t e n a n t q u ' i l e x i s t e des a lgo-
r i t h m e s de ea lcu l de p lus c o u r t s c h e m i n s [8, 9, 10],
t r6s eff icaces m 6 m e p o u r des g r a p h e s de t a i l l e i m p o r -
t a n t e : a ins i la m d t h o d e de g d n 6 r a t i o n d e s o p t i m u m s l o e a u x q u i es t d i seu tde iei p e u t - e l l e 6 t re t rbs efficace.
V.2. Propri6t6 1.
Sous r d s e r v e de c o n v e r g e n c e , la m d t h o d e des l inda-
r i s a t i o n s success ives ( P r o c d d u r e 1) p r o d u i t un p o i n t e x t r S m e s a t i s f a i s a n t les c o n d i t i o n s ndcessa i res d ' o p t i -
m a l i t 6 loca le .
E n effet , d ' a p r ~ s la c o n c a v i t 6 , on p e u t 6crire :
( I ) ( . ~ i ) _ ( I ) (~ /+ l ) ~ ( I ) (~ t )_~ ( ~ i + 1 .~ i ) . g~dCI) (Xi ) ,
d 'o f l l a c o n d i t i o n : (.~i+~ __ X / ) - g r a d (I)(.~ i) ~> O.
Mais ~i+~ d t a n t la so lu t ion o p t i m a l e de (PL) , on a :
(Xi+~ __ ~ t ) . g ~ d (I)(.~ i) ~< O.
V.3. Propri6t6 2.
L a su i te des v a l e u r s (I)(~1), d p ( ~ ) ....... (I)(~i) es t
m o n o t o n e d ~ c r o i s s a n t e au cou r s des i t e r a t i ons .
E n effet on a :
(I)(~i+l) ~ (I)(~i) + (~i+1 _ . ~ i ) . g ~ d (I)(.~t),
e t ( R ~ + 1 - . ~ i ) . g r ~ d (I)(.~ i) ~< 0,
p a r su i t e : (D(~: ~+1) ~< qb()~l) p o u r t o u t i,
d 'o f l la p rop r i6 t6 .
V.4. Th6orSme de convergence.
L a m 6 t h o d e des l i n d a r i s a t i o n s success ives c o n v e r g e
en un h o m b r e fini d ' i t d r a t i o n s , vers un p o i n t sa t i s -
f a i s a n t les condi t ions ndcessaires d ' o p t i m a l i t ~ loca le .
Le c a r a c t ~ r e f ini de l a c o n v e r g e n c e p r o v i e n t du fa i t qu ' i l e x i s t e u n n o m b r e fini de p o i n t s e x t r e m e s
de ~ ( rdseaux u n i r o u t d s ) , d~s lors que l ' o n a r e m a r q u d
q u ' a u c u n c y c l a g e ne p e u t se p r o d u i r e a v a n t q u e l ' o n
a i t o b t e n u un p o i n t X ~ v d r i f i a n t :
�9 (I)(.~ 1+1) = O ( x i ) .
E n effet, p o u r k ~ j ~< i on a t o u j o u r s :
e t (I)(.~ h) ~< (I)(~1), p o u r h > ],
i n t e r d i t q u e l ' o n p u i s s e a v o i r ~ h = ~ g .
V.5. V6rification de l'optimalit6 locale.
A y a n t d d t e r m i n d p a r la m 6 t h o d e des l i n d a r i s a t i o n s
suecess ives un p o i n t ~:i s a t i s f a i s a n t les c o n d i t i o n s
ndeessa i res d ' o p t i m a l i t d , il n ' e s t pa s c e r t a i n p o u r a u t a n t q u e ce p o i n t so i t r d e l l e m e n t un o p t i m u m local .
On p e u t p r o c d d e r de l a m a n i 6 r e s u i v a n t e : on s ' a s -
sure q u e la c o n d i t i o n s u i v a n t e es t sa t i s fa i te . Condit ion 1 : t o u s l e s po in t s extrdmes ~ k solut ions
optimales de ( P L ) sont tels que :
�9 apCy, k) >10(R+). Si oui, on p e u t a f f i rmer q u e .~i es t un o p t i m u m
local . R e m a r q u e r q u e ce cas e o u v r e les h y p o t h 6 s e s
du thdor~me 7 : en effet , l o r s q u ' i l y a un ic i td de la so lu t ion de (PL) , la condi t ion 1 est v~rif ide.
Si non , a lors on m e t en ~v idence un p o i n t e x t r e m e
~ k de ~) te l q u e :
0 ( 2 ~ ) < r
h. T~.L~C. 2~. ,lo8 1-2. J~74 12/18
M . M I N O U X . -- C O N F I G U R A T I O N OPTIMALE D ' U N R I ~ S E A U DE TI~.LECOMMUNICATIONS 37
Ce po in t p e u t servir de poin t de ddpar t pour la
m d thode des l in6arisat ions successives, j u squ ' h obtenir
un au t re po in t ~:t. La quest ion peut , 6ventue l lement ,
se poser encore pour le nouveau po in t ex t r eme ainsi
ddtermin6. . , e t ainsi de suite.
E n t ou t e g6ndralitd, on vo i t doric que l 'on cst
condu i t h ~numdrer les solutions opt imales du pro- b lame lindaris6 (PL), 6num6ra t ion qui peu t dans cer-
rains cas ddfavorables ~tre longue.
N~anmoins , dans la p ra t ique , et no t re exp6rience
l ' a confirm6, on p e u t a d m e t t r e que la solut ion de
(PL) est non ddgdn6r6e et, par consequent , que le point de convergence de la mdthode des lindarisations successives est en gdndral un opt imum local du probl~me ( P ) .
Nous t e rmine rons par une r e m a r q u e concernant
les fonct ions strictemenl concaves. Lorsque (sons cet te hypoth~se) la solut ion ~ du probl6me (PL) n ' e s t pas
unique , t o u t po in t e x t r e m e ~ k =/= ~J solution
0p t imale de (PL) v6rifie :
ap(~) < r
En effet, p o u r des fonct ions s t r i c t emen t concaves, o n a :
O ( . ~ ) < qb(~J )+ (~:~-- ~ J ) . g~d6p( .~i) (pour ~ k =/: ~J ) .
Dans ce cas par t icul ie r , la v6r i f iea t ion de l 'opt i -
mal i t6 locale ne n6eessite pas l '6nuin6ra t ion de tous
les . ~ : si la solut ion de (PL) n ' e s t pas unique, il
suffit de dd te rmine r un quelconque des points exlrgmes . ~ r X ~ solut ion op t ima le de (PL). On est alors cer ta in que (I)(.~ ~) < (I)(Xi), et on peu t app l iquer de
n o u v e a u la md th ode des l in6ar isat ions sueeessives h
pa r t i r de ~:k. D ' u n e fayon p ra t ique , eela v e u t dire qu ' i l v a u t
m ieux t r a i t e r des fonet ions s t r i c t emen t concaves de
type 1 (of. ehap i t r c I) p lu t6 t que des fonet ions lin6aires pa r m o r c e a u x de type 2 ou 3. D'a i l leurs , ces derni~res
n ' 6 t a n t pas eon t in f imen t ddrivables, la m6thode
p r 6 e d d e m m e n t expos6e ne pou r r a i t pas ~tre appliqu6e
(le g rad ien t n ' 6 t a n t pas d~fini en t o u t point) .
V.6 . G 6 n 6 r a l i s a t i o n a u x f o n c t i o n s n o n c o n t i -
n f i m e n t d i f f 6 r e n t i a b l e a .
La g~n6ral isat ion de la m6thode des l in6arisations
successives au cas des fonct ions concaves non diff6-
rent iables ne pr6sente pas de difficult6 du po in t de vue thdor ique , du moins : il suffit de considdrer les
sous-gradients au lieu du g rad ien t en un point . D 'un
poin t de r u e p ra t ique , si l 'on d6sire app l iquer la
condi t ion d ' op t ima l i t 6 locale donn6e par le lhdo- r~me 8, on cons t a t e qu ' i l f au t la vdrifier pour tous les sous-gradients en ~0. Or une fonct ion concave peut
a d m e t t r e une infini t6 de sous-gradients en un point.
Dans le eas off la fonc t ion d)(~:) est s6parable, c 'est-h-
dire ( I ) ( X ) ~ ~( I )u (Xu) , l ' ensemble des sous-gradients u
en .~0 est un ensemble convexe don t les points ex t remes
sont donn6s par les d6riv6es h droi te et h gauche de
chacune des fonc t ions (I)u en X ~ I1 est alors facile de d6mont re r que la cond i t ion du
thdor~me 8 p e u t 6tre r6dui te aux seuls points ex t r6mes du c6ne des sous-gradients en ~:o. Mais on s ' aper$o i t
que si le n o m b r e M des arcs du r6seau est g rand , il reste en g6n6ral une dnum~rat ion assez p rod ig ieuse
(de l ' o rd re de 2M possibili t6s) h effectuer pour v6r i f ier
la condi t ion d 'op t ima l i t6 . De tou tes fa$ons, une telle g6n6ral isat ion ne pr6-
sente pas un g rand int6r~t p ra t ique . Dans la sui te
de cet exposd, nous appl iquerons la m 6 t h o d e des
l in6arisat ions successives h des fonct ions concaves et con t in f imen t diff6rentiables, en r u e de la g6n~rat ion
des o p t i m u m s locaux du probl~me (P).
V .7 . E t u d e de l a r a p i d i t ~ de c o n v e r g e n c e su r u n e x e m p l e .
I1 est tr~s difficile d 'ob ten i r , seu lement pa r des
d6ve loppements th6or iques , une borne sup6r ieure du
nombre d ' i t6 ra t ions dans la m6 thode des l in6ar isa t ions successives. Pa r cont re , l ' exp6r ience conf i rme qu ' e l l e
converge tr~s rdgul i~rement en un pe t i t nornbre
d ' i t6 ra t ions (de l ' o rd re d ' une dizaine au m a x i m u m ) ,
el ceci quasimcnt quelle que soil la laille du rdseau traild.
L ' e x e m p l e que nous allons prdsenter eor respond au
sous-r~seau de la rdgion ouest du r6seau n a t i o n a l
franyais. I1 c o m p r e n d les douze eentres su ivants :
I - - P A R I S
2 - - N A N T E S
3 - ROUEN 4 - ORLEANS
5 - - R E N N E S
6 - TOURS 7 - CAEN
8 -- LE MANS
9 - BEAUVAIS
1 0 - - C H A R T R E S
11 - ]~VREUX 12 -- BREST
Les demandes en circui ts t616phoniques en t r e les
diff6rents centres ne sont donn6es q u ' h t i t re ind iea t i f ,
et sont cens6es represen te r , aussi f id~lement que pos-
sible, la d e m a n d e p r6vue en 1975 ( tab leau I I I ) . D ' a u t r e pa r t , le t ab l eau IV donne les l ongueur s
k i lom~tr iques , lu , des ares a p p a r t e n a n t h la s t r u c t u r e
de d6part . Le rdseau de d6par t comprend 39 arcs ( n ' o n t dt6
re tenus , p a r m i les arcs du g raphe eomple t , que ceux
qui 6 ta ient suseept ibles d ' in te rveni r ) . Le r o u t a g e de
d6par t se fai t au plus cour t chemin g6ographique . Comme dans l ' e x e m p l e du pa r ag raphe IV-12, les
fonct ions de cofit ~ u ( X u ) sont de la forme :
~)u(Xu) = tu~(Xu) ,
13/18 A. T ~ L s 29, n ~ 1 -2 , 1 9 7 4
38 M. MINOUX. - CONFIGURATION OPTIMALE D'UN RESEAU DE TELECOMMUNICATIONS
1 - -
2 -
3 -
4 -
5 -
6 -
7 -
8 -
9 -
1 0 -
1 1 -
1 2 -
P A R I S
N A N T E S
R O U E N
O R L E A N S
R E N N E S
T O U R S
C A E N
L E M A N N
B E A U V A I S
C H A R T R E S
~ V R E U X
B R E S T
TABLEAU I [ I
Demande en circuits entre les 12 centres de la rdgion ouesl
1 -- P A R I S
1 236
1 020 84
72O I 132 72
516- I 228 96 84
576 I 168 36 396
696 I 84 276 84
396 420 60 60
312 48
324 240--
240 300
120 72 24
2 -- N A N T E S
3 - ROUEN
4 - O R L E A N S
5 - R E N N E S
60
120
84
252
6 -- TOURS
7 - CAEN
36 8 -- L E M A N S
_ 1 4 4 l ~ - ~ 9 - BE~ B E A U V A I S
~ 10 -" CHARTRES
- - I - - - - U 1 , - VREUX - - 12 - BBEST
1 - - P A R I S
2 - NANTES
3 - ROUEN
4 - O R L E A N S
5 - - R E N N E S
6 -- T O U R S
7 - - C A E N
8 - - L E M A N N
9 - BEAUVAIS
10 - CHARTRES
11 - ~VREUX
1 2 - B R E S T
T A B L E A U I V
Matrices des longueurs kilomdtriques des arcs pour l'exemple ~ 12 cenlres
-- P A R I S
2 -- N A N T E S
342 3 - ROUEN
110 4 -- ORLEANS
111 271 5 -- RENNES
307 100 250 6 -- TOURS
205 169 108 7 -- CAEN
199 236 107 1 5 3 ~ 8 - L E M A N N
184 157 172 128 140 77 137 - - 9 - BEAUVAIS
65 72 - - 1 0 - CHARTRES
76 266 68 133 ~ 1 1 0 ~ ~ ~ l l - - ~ V R E U X
88 46 231 111 133 82 68 ~ 12 -- BREST
256 21o ~ 1 - - - - I - - ' ]
o h ? ( X u ) e s t l a f o n c t i o n d u co f i t p a r k i l o m ~ t r e :
? ( X u ) ~ 7,5 ( X u ) ~ 4 ( k i l o f r a n c s - k i l o m ~ t r e ) .
N . B. - - Ces c o u r b e s a p p r o x i m e n t d ' u n e f a ~ o n
c o r r e c t e les c o u r b e s d e c o f i t d e d 6 v e l o p p e m e n t h l o n g
t e r m e e f f e c t i v e m e n t e n r e g i s t r 6 e s s u r le r 6 s e a u n a t i o n a l
f r a n ~ a i s .
L a c o n v e r g e n c e e s t o b t e n u e a u b o u t d e qualre
i ldrat ions s e u l e m e n t e t les r d s e a u x s u c c e s s i v e m e n t
r e n c o n t r 6 s s o r t c e u x d e s f i g u r e s 13 h 16.
7 3 9
12 ~ ~ 4 1 6 2
FIG. 13. - - R6seau 1, r ou t age au plus cour t chemin g6ogra- ph ique sur le r6seau de d6part . Cofit 353,8 MF.
7 3 9
12 1
6 2
FIG. 14. - - R6seau 2 : cofit 257,6 MF (19 arcs).
7 3
2 6
Fla . 15. - - R~seau 3 : eodt 225,13 MF (15 ares).
O n p o u r r a i t p e n s e r q u e l a r a p i d i t 6 de c o n v e r g e n c e
d d p e n d b e a u c o u p d e l a t a i l l e d u r d s e a u t r a i t 6 . D e
f a i t , il n ' e n e s t r i e n . M ~ m e p o u r d e s r 6 s e a u x de
50 n c e u d s e t p l u s , e l le c o n v e r g e e n g 6 n 6 r a l e n m o i n s
A . T E L ~ C . , 2 9 , n ~ 1 - 2 , 1 9 7 4 14/18
hi . M I N O U X . -- C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A U D E T I ~ L I ~ C O M M U N I C A T I O N S 39
3 7 3 7 - - 9 9
2 6 2 6
FIG. 16. - - R6seau 4 : coot 225,11 MF. Le rdseau 4 ne diff~re FI~. 18. R6seau 6 : coot 210,97 MF. t)ARIS-t~ENNES (1-5) pas du r6seau 3 par la structure, mais par les valeurs des et PAam-CaEN (1-7) interdits.
riots sur les arcg.
de cinq i t6ra t ions , et t ou jours en moins de dix i tdrations.
Ceci 6tant , il f a u t r e m a r q u e r que le rdseau 4 n 'es t
q u ' u n o p t i m u m local pa rmi beaucoup d 'au t res , et il
n ' a aucune ra ison d ' e t r e une bonne app rox im a t ion de l ' o p t i m u m global du probl~me. L ' id6e qui v ien t
alors n a t u r e l l e m e n t h l ' e sp r i t consiste h rechercher si
un au t re r~seau de d6par t pour ra i t conduire h u n o p t i m u m local plus int6ressant .
V.8. I n f l u e n c e d u r 6 s e a u de d6part sur le po in t de c o n v e r g e n c e .
Supposons q u ' a u l ieu de p rendre le rdseau 1 (Fig. 13) comme r6seau de d6par t , on ai t 6limin6 a priori l ' a rc
Paris-Rennes. On au ra i t ob t enu ainsi un au t re r6seau
de ddpar t c o m p o r t a n t 38 arcs, mais peu diff6rent du prdc6dent.
La m~me m 6 t h o d e (l indarisations successives), appl iqu6e h p a r t i r de ce n o u v e a u point de d6par t (*),
avec les m~mes fonc t ions de cofit, aura i t alors condui t h l ' o p t i m u m local de la figure 17.
7 3 . 9
6 2
Fro. 17. - - R6seau 5 : coot 225,01 MF. PARIS-PtENNES (1-5) interdit.
E t si, de plus, on a v a i t in te rd i t l ' a r t~re Paris-
Caen (1-7), le r6su l t a t au ra i t 6t6 encore mei l leur (Fig. 18).
(*) Le routage de d6part est en g6n6ral (sauf mention contraire) un routage au plus court chemin g6ographique sur la structure de d6part.
Le rdseau 4 et le rdseau 6 des figures 16 et 18 four-
n issent deux exemples d ' o p t i m u m s locaux de coots assez diffdrents (diff6rence de 7 %), ob tenus cependan t
h pa r t i r de r6seaux de d~par t voisins (diff6rant pa r
deux arcs seulement) .
Ainsi, l ' inf luence du r6seau de ddpar t appara i t -e l le
p r6ponddran te sur la qual i t6 du rdsul ta t fourni pa r
la m6thode des l in6ar isat ions successives. T a n t et si bien que, munis ddsormais d ' u n e m6thode efficace
de g6n6rat ion des o p t i m u m s locaux, le v6r i table pro-
b lame h rdsoudre est le s u i v a n t :
trouver un rdseau de ddpart (et un routage de ddpart
sur ce rdseau) conduisant, par la mdthode des lindari-
sations successives au meilleur op t imum local.
Le probl~me ainsi posd, on r e t r o u v e l ' a spec t combi - na to i re dvoqud au p a r a g r a p h e IV.11. Mais a v a n t
d ' a b o r d e r l ' e x a m e n des diff6rentes m6thodes de rdso-
lu t ion heur is t iques appl icables aux r6seaux de tai l le impor t an t e , nous allons g6n6raliser la mdthode des
l indarisat ions successives h des fonct ions de coo t
diffdrentes des fonct ions de coo t e f fec t ivement ut i -
lis6es comme crit~re 6conomique , en in t rodu i san t la
no t ion de fonctions de coot artificielles.
V.9 . CoSts f ixes et f o n c t i o n s de cof i t art i f ic ie l les .
Si O1(~: ) et qb2(~ ) sont deux fonct ions 6conomiques concaves ne diff~rant que p a r une cons tan te , la
m6 thode des l indar isa t ions successives abou t i t h la
m~me solution. E n effet, les g rad ien ts de (Pl et (P2 sont ident iques en t o u t po in t (Fig. 19).
Supposons, pa r exemple , c o m m e au pa ragraphe V.7
que les fonc t ions de coo t pa r k i lom~tre soient iden-
t iques sur chacun des arcs du r6seau, et consid~rons
deux courbes de coo t (par k i lom6tre) CI(Xu ) et C~(Xu).
Supposons que : Cx(0 ) ~ 0, (pas de coo t fixe),
C2(0) ~ 8, (coOt fixe positif),
P o u r chacune des deux fonct ions M
�9 l ( x ) = E tu a~(xu), I I = |
M
q~2(x) = ~ l= c2(Xu), u--t
15/18 A. T~:L~:C., 29, ,l ~ 1-2, 1974
40 M. M I N O U X . - - C O N F I G U R A T I O N O P T I M A L E D ' U N R I ~ S E A . U D E T ] ~ L I ~ C O M M U N I C A T I O N S
C~ (0) =
C= (0) = 0
CoOt C~ (X u) i - - ' ~ ' ' ' ~ ' ' ' ' ~ - ~
~ ' ~ (Xu)
Nu c a p a c i t : d e Varc u
Fie. 19. - - Les deux fonctions CI(Xu) et C~(Xu) ont mfime d~riv~e en tous points.
la m ~ t h o d e des l i n d a r i s a t i o n s s u c c e s s i v e s a b o u t i t ,
c o m m e il a d td d i t p l u s h a u t , a u m ~ m e o p t i m u m local ,
quelle que soit la ualeur du co~t fixe 8. Or, o n c o n ~ o i t b i e n q u e l o r s q u e le cof i t f ixe ~ e s t
i m p o r t a n t , ]e n o m b r e d ' a r c s d a n s le r d s e a u o p t i m a l
d o l t ~ t r e p l u s f a i b l e p o u r le d e u x i ~ m e c r i t 6 r e ~cono-
m i q u e q u e p o u r le p r e m i e r . A la l i m i t e , l o r s q u e le
cof i t f ixe ~ d e v i e n t t r~ s g r a n d d e v a n t l a d~ r iv~e h
l ' ~ C ~ u u j X u : 0 , le r ~ s e a u o p t i m a l c o m -
p r e n d u n n o m b r e d ' a r c s m i n i m a l p o u r a s s u r e r l a
c o n n e x i t ~ , c ' e s t - h - d i r e N - 1 arcs . C ' e s t a lo r s u n
arbre et c ' e s t m S m e l 'arbre m in ima l pour les longueurs lu(u : 1 , . . . , M) (en effet , c h a q u c a r c co f i t e a lo r s lu8 que l l e q u e so i t l a q u a n t i t ~ de f lo t q u i le t r a v e r s e ) .
O n m e t a i n s i e n d v i d e n c e u n e i n s u f f i s a n c e de l a
m d t h o d e des l i n ~ a r i s a t i o n s s u c c e s s i v e s , t e l l e q u e n o u s
l ' a v o n s e x p o s d e j u s q u ' i c i . L a r a i s o n e n e s t q u e la
d~ r iv~e dCPu( Xu) d X u e n u n p o i n t e x p r i m e b i e n le cof i t
d ' u n p e t i t a c c r o i s s e m e n t de f lo t s u r u n a r c , m a i s
e x p r i m e t r~s r e a l le co f i t rde l de l ' a r c . A u c o n t r a i r e , le coFzl moyen,
O~(X~) Y u ( X u ) - - Xu '
e x p r i m e t r~s b i e n le cof i t rde l d ' u n a rc u a u v o i s i n a g e
de l a c a p a c i t ~ X u p o u r l a q u e l l e il a dtd ca lcu ld . D 'of i
l ' i dde d ' u t i l i s e r l a m d t h o d e de l i n d a r i s a t i o n s s u c c e s - d~Pu( Xu)
s i r e s en e m p l o y a n t , n o n p l u s le c o f i t ' m a r g i n a l dXu
r su r c h a q u e a rc , m a i s le c o h t m o y e n : Y u ( X u ) -- Xu
S i l a f o n c t i o n r es t c o n c a v e c o n t i n u e e t
m o n o t o n e c r o i s s a n t e s u r ]0, + ~ ] , la f o n c t i o n de cof i t
m o y e n e s t c o n t i n u e e t m o n o t o n e d d c r o i s s a n t e su r
]0, + c ~ ] t o u t c o m m e la d d r i v d e dr (F ig . 20 d X u
e t 21).
O~(Xu) D ' a u t r e p a r t , l a f o n c t i o n Y u ( X u ) -- Xu p e u t
~ t re c o n s i d d r d e c o m m e la d d r i v d e de l a f o n c t i o n :
F~(Xu) = /x~ (Pu(X) x d x , (r ~ 0 ) ,
q u i e s t c o n c a v e e t m o n o t o n e c r o i s s a n t e s u r ]0, + o~] .
CoOt de I'arc u
'l,u (Xu)
Xu capacitd
FIG. 20. - - Fonct ion ffPu(Xu), concave, continue, monotone croissante sur ]0, + ~ ] .
CoOt par
circuit
I I
I X u c a p a c i t ~
FIG. 21. - - Fonct ions cofit moyen et cofit marginal, elles sont toutes les deux monotones d6croissantes.
D a n s ces c o n d i t i o n s , si l ' o n p r e n d la f o n c t i o n
F ( X ) = ~ F u ( X u ) c o m m e c r i t ~ r e d c o n o m i q u e d a n s u
l a m d t h o d e des l i n d a r i s a t i o n s succcs s ives ,
c o n d u i t h la procddure 2.
Procedure 2.
1) P a r t i r d ' u n e s o l u t i o n i n i t i a l e ~:0.
o n e s t
A. T~L~C., 29, n ~ 1-2, 197/,. 16 /18
M. M I N O U X . - - C O N F I G U R A T I O N O P T I M A L E D ' U N R E S E A U D E T I ~ L I S ~ C O M M U N I C A T I O N S 41
2) A l ' i td ra t ion i ca lculer :
Ou( X~u) y / u - Xi u (pour u = 1 .... M) .
3) D6finir X I+1 c o m m e la solut ion opt imale d e :
M
y u X u , (PL) min ima l i se r ~ i . ~ = ,,=t ~ i
avec ~ e ~ .
4) Fai re i = iq - 1 et al ler en 2.
5) Arr~ter les i t6 ra t ions lo rsque ~i.V~l -- ~i.Y~l+ L
La convergence de la m6 thode d6coule de la pro-
pri6t6 d~ concavi t6 de la fonc t ion Pu(Xu) , en appli-
q u a n t les r6sul ta ts donn6s au d6but de ce chapitre.
I1 fau t bien r e m a r q u e r que l 'on ob t ien t alors un
o p t i m u m local du p rob l6me pour la fonct ion 6co- nomique :
M
P(~) = E Pu(Xu), , 1 = I
mais non pas pour la v6r i t ab le fonct ion 6conomique
(celle qui nous int6resse) :
M
o ( Y O = EOu(Xu). 1, ]
Cet o p t i m u m local de F( .~) peut , par cons6quent,
servir de po in t de d6par t h la m6thodc des lin6arisa-
t ions successives appl iqu6e ce t t e fois h la fonctiou 6conomique r6elle (I)(~).
On est ainsi condu i t h une proc6dure en deux temps, soit la procddure 3.
Procddure 3. Premier temps : d6grossir le probl6me h l ' a ide d 'une
fonct ion 6conomique ar t i f ic ie l le (u t i l i sa t ion par exem-
pie des cofits moyens p l u t 6 t que des coflts marginaux) .
Deuxi~me temps : affiner la solut ion obtenue h l 'a ide de la fonct ion 6conomique r6elle j u squ ' h obtenir un
o p t i m u m local du probl6me pos6.
On peu t g6n6raliser ce qui pr6c6de en disant que
la m6thode des l in6ar isa t ions successives peu t 4tre
employ6e (pour fourn i r une solut ion de d6par t accep-
table) avec une fonc t ion de cofit abso lument quel-
conque, p o u r v u qu 'e l le soit diff6rent iable et pr6sente la concavi t6 voulue.
Pa r exemple , dans la r6f6rence [11], on a propos6
de remplace r le cofit ma rg ina l pa r une combinaison lindaire convexe du cofit m o y e n et du cofit marginal .
Les cofits renvoy6s h c h a q u e i t6ra t ion au probl6me lin6aris6 (PL) 6 tan t :
d / / y u = k \ dXu /X u=X~-k ( 1 - - k) X ~ '
off k est un p a r a m 6 t r e (fixe ou var iable) compris en t re 0 et 1.
I1 fau t observer que le succ6s de telles m6thodes
n ' e s t pas ga ran t i en g6n6ral, mais qu ' i l fau t h chaque
fois t r o u v e r la bonne v a l e u r du pa ram6t r e k, ou encore
t r o u v e r la fonc t ion art if iciel le la m i e u x adapt6e au
cas pa r t i cu l i e r que l 'on d6sire t ra i te r .
P a r exemple , dans le cas de fonct ions 6conomiques
l in6aires avec ordonn6e h l 'or igine, le cofit marg ina l
est i n d 6 p e n d a n t de la quan t i t6 de flot sur l ' a rc et on
aura en g6n6ral int6r~t h ut i l iser le cofit m o y e n
( k = 0).
P a r cont re , dans le cas de fonct ions (I)u(Xu) de la
fo rme : (I)u(Xu) = (Xu) ~ (off cr cs t un e x p o s a n t compris
en t re 0 et 1), on a tou jours :
Yu(Xu) = (Xu) ~-1 ,
d(I)u( Xu) - - o ~ ( X u ) ~ - 1 ,
d Xu
d(l)u(Xu)] Y u ( X u ) = cons tan te . I1 est et pa r sui te d X u |
alors indiff6rent d 'u t i l i se r le cofit ma rg ina l ou le coflt
moyen .
P o u r ce qui nous concerne, nous n 'u t i l i se rons pas
d ' au t r e s fonct ions artif icielles que lcs fonc t ions de coflt moyen , su ivan t la procddure 3, pour d6grossir le pro-
bl6me a v a n t de rechercher l ' o p t i m u m local (pour les
fonct ions aut res que (Xu) ~. E n effet, il f au t voi r que m~me avec une tr6s bonne
fonc t ion art if iciel le, la qual i t6 du r6su l ta t p rov i en t
p r inCipa lement du r6seau de d6par t que l 'on utilise (cf. w V.8). L 'e f for t pr incipal dev ra donc por t e r sur
la recherche d ' une bonne solut ion de d6part .
C O N C L U S I O N
Nous avons, au cours de ce t t e premi6re par t ie ,
pass6 en r evue les propri6t6s m a t h 6 m a t i q n e s g6n6-
rales du probl6me (P). Cet te approche nous a permis
de d 6 m o n t r e r en par t icu l ie r que, p a r m i l ' ensemble (infini) de tou tes les solutions possibles, on p o u v a i t
se r e s t r e ind re h u n sous-ensemble fini (mais tr6s
g rand I) de solut ions co r re spondan t :
- - aux r6seaux unirout6s, d ' u n e par t ,
- - aux o p t i m u m locaux de (P), d ' a u t r e par t .
Une m 6 thode i t6 ra t ive (la m 6 thode des l indarisa- t ions successives) p e r m e t de ca lculer e l l i cacement un
o p t i m u m local X* h par t i r d ' une so lu t ion que lconque (non l oca l em en t opt imale) ~0.
N6anmoins , un exemple de pe t i t e ta i l le suffit h
m o n t r e r que le nombre d ' o p t i m u m s locaux cst en
g6n6ral f a n t a s t i q u e m e n t grand. Ainsi le probl6me
appara i t , au t e r m e des d 6 v e l o p p e m e n t s pr6c6dents,
c o m m e un probl6me essen t ie l lement com b ina to i r e :
pa rmi tons les o p t i m u m s locaux, t r o u v e r l ' o p t i m u m local de cofit minimal .
Nous avons vu au chap i t re V c o m m e n t on p o u v a i t
associer, h u n graphe par t ie l connexe G' du graphe G, un o p t i m u m local X*(G ' ) :
17/18 A. T~L~C., 29, n ~ 1-2, 1974
42 M. MINOUX. - CONFIGURATION OPTIMALE D ' U N RI~SEAU DE TI~LI~COMMUNICATIONS
�9 en ddf inissant ~o comme d tan t le vec teur des- cr ipt i f ob t enu par rou tage de la demande au plus cour t chemin gdographique sur le graphe par t ie l G',
�9 puis en ca lcu lan t :~*(G') par la mdthode des l indar isa t ions successives, h pa r t i r de ~:o.
On peu t ainsi formuler le probl~me de fa~on tou t h fait 6quiva len te : t rouver le g raphe par t ie l connexe G' c o n d u i s a n t h l ' o p t i m u m local ,X*(G') de cofit minimal .
Nous passerons en revue, dans la deuxi~me part ie de cet' article, diffdrentes mdthodes susceptibles de rdsoudre ce probl~me, en i n s i s t an t par t i cu l i~rement sur celles qui p e r m e t t e n t de t r a i t e r les rdseaux de g rande tai l le (une cen ta ine de nceuds et plus) en un t emps de calcul ra i sonnable sur ca lcu la teur 61ectro- nique.
(A suivre.)
Manuscrit re~u le 19 novembre 1973.
BIBLIOGRAPHIE
[t] B~Gu~ (J.), MINOUX (M.). Planification des inves- tissements en rdseau interurbain : le programme osiais. Echo des recherches, Fr. (avr. 1973), pp. 22- 35. (Hors commerce.)
[2] AYMAR (J. P.). voIcI : un programme permettant d'dvaluer les besoins futurs dans le rdseau inter- urbain. Echo des recherches, Fr. (oct. i970), pp. 15-21. (Hors commerce.)
[3] DANTZlG (G. B.). Linear programming and exten- sions (Programmation lin~aire et prolongements). Princeton Uni~. Press (1963), 632 p.
[/i] SIMONNARD (M.). Programmation lin6aire. Dunod, Paris (1962), 420 p.
[5] HUARD (P.). Tour d'horizon en programmation non lindaire. Bull. Direct. Etudes et recherches, Eleetricitd de France, Fr. (197i), s6rie C, n ~ 1, pp. 35-70.
[6] HADLEY ((~.). Nonlinear and dynamic programming (Programmation non lin6aire et dynamique). Addison- Wesley, Beading, Mass., U. S. A. (i970), 48r p.
[7] LASDON (L.). Optimization theory for large systems (Thdorie de l 'optimalisation des grands syst~mes). MacMillan, London (1970), 523 p.
[8] Hu (T. C.). Integer programming and network flows (Programmation en nombres entiers et flots dans les rdseaux). Addison-Wesley, Beading, Mass., U. S. A. (1969), 452 p.
[9] DANTZIG (Cx. B. ) . All shortest routes in a graph (Les plus courts chemins dans un graphe). Technical report n ~ 66-3. Stan]ord Unir Calif. (1966).
[10] GRASSIN (J.), MINOUX (M.). Variations sur un algo- rithme de Dantzig. Application it la recherche de plus courts chemins dans les grands rdseaux. Be~. It., Automat., In/ormat., Bech. opdrat. (mars t973), 7, n ~ V-l, pp. 53-62.
[11] YAGED (B.). Long range planning for telecommuni- cation networks (Planification it long terme des rdseaux de tdldcommunication). Polytechnic Inst. Brooklyn (1971), 147 p.
[12] FOnD (L. R.), FULKEaSON (D. R.). Flows in net- works (Flots dans les rdseaux). Princeton, New Jersey (t962), 194 p.
[13] KLEINROCK (L.), FRATTA (L.), GERLA (M.) . The flow- deviation method : a new approach to the analysis and synthesis of store and forword communication networks design (La mdthode du (( flot ddvid )) : une nouvelle mani~re d'aborder l 'analyse et la synth~se des r~seaux de transmission it enregistrement et retransmission). Netwoorks, U. S.A. (1973), 3, n ~ 2, pp. 97-133.
[lf~] VERKEN (C.), BARCIA (P.), VARIOT (P.), MADELEINE- PERDRILLAT (C.). Le programme AUaOaE : prdsen- tation et premiers essais. Service des programmes et des dtudes dconomiques. Direction g~ndrale des tdld- communications, Minist~re des Postes et Tdldcommu- nications (oct. 1972), n ~ 10, pp. 27-39. (Hors commerce.)
[15] YAGED (B.). Minimum cost routing for static net- work models (Routage it cofit minimal pour mod61es de rdseaux statiques). Networks, U. S. A. (1971), 1, no 2, pp. 139-171.
[16] ZANGWILL (W. I.). Non linear programming an unified approach (Programmation non lindaire, une approche unifide). Prentice hall (1969), 336 p.
A. TELEC., 29, n ~ 1-2, 1975 18/18
