Comptes Rendus MATh.en.JEANS 00-11

Atelier MATh.en.JEANS du lycée Henri Moissan de Meaux (77), année 1999-2000.
Enseignant : Sandrine Lefranc.
Chercheur : Olivier Bodini (Laboratoire de Combinatoire, Paris)

 

---

[Article vérifié et commenté (voir note 1): les passages entre crochets sont des éditeurs]

Sujet

[ Des forages ont permis de localiser des gisements de pétrole et de décider d'emplacements pour des puits de pétrole : A,B,C,D,etc. Ces puits devront être reliés à une raffinerie par un réseau de pipes-lines. La figure 1 montre un exemple de projet pour 6 puits A,B,C,D,E,F : les puits sont reliés par 6 pipes-lines rectilignes [AB],[BC],[CD],[DE],[EF] et [FA]; la raffinerie R est placée à mi-chemin entre A et B. Pouvons-nous améliorer ce projet initial en proposant un réseau plus court ?]

Figure 1

[On suppose que le coût ne dépend que de la longueur totale des pipes-lines. Le problème est donc celui de trouver un réseau de liaison de longueur totale minimum (note 2).]

Introduction

Nous nous sommes fixés au départ comme règle qu'il devait y avoir un point de ralliement n'appartenant pas [obligatoirement] au tracé de la figure représenté par les pipes-lines [du projet initial : c'est là que sera placé la rafinerie. Le problème devient alors celui de trouver le meilleur point de ralliement possible (note 3) :

Des points A,B,C,... étant donnés dans le plan, où placer un point R de telle manière que la somme des distances RA+RB+RC+... soit minimum ?

Un tel point R sera appelé point solution. Nous ferons l'hypothèse que des points solutions existent, dans tous les cas de figure (voir note 4)]

Nous avons débuté par des cas particuliers ([pour lesquels nous avons des] démonstrations), avant d'essayer d'étendre [à des cas généraux] ([pour lesquels nous n'avons] que des conjectures, hélas).

Démonstrations

Le cas de deux points.

Pour deux puits de pétrole, la meilleure solution est évidemment la ligne droite, la raffinerie R doit se trouver sur le pipeline entre les deux puits.

Figure 2

Pour une infinité [un nombre quelconque] de points alignés

 

Pour des points alignés, la plus courte distance est une ligne droite entre le premier point et le dernier point.

Figure 2

Pour 3 points formant un triangle équilatéral

[Théorème : Pour 3 points formant un triangle équilatéral, le point solution est le centre du triangle.]

[Démonstration (note 5)]

Hypothèses: ABC : triangle équilatéral M : un point quelquonque (d) : la parallèle à (BC) passant par M C' : le symétrique de C par rapport à d K : {K} = [BC'](d)

Figure 3

• On a :
            (1) KAMA.

  car AM [est] l'hypothénuse du [triangle] AKM, rectangle en K. [note 6]

• [Dans la symétrie d'axe (d), les points M et K sont conservés. Puisque les symétries axiales conservent les distances, on a : KC=KC' et MC=MC', d'où :]

            KB+KC=KB+KC' [et MB+MC'= MB+MC].

  Or , KB+KC' MB+MC, car la ligne droite est le plus court chemin entre deux points. Donc :

            (2) KB+KC MB+MC

  [Des inégalités (1) et (2) on déduit :

            (3) KA+KB+KCMA + MB + MC

  On remarquera que si K et M sont distincts, cette inégalité (3) est stricte (note 7)]

• Dans [le triangle] BCC', K est le milieu de [CC'] et Kd [qui est parallèle à (BC)]. Donc, d'après le théorème des milieux, K [est le] milieu de BC' . On a donc KC'=KB, d'où KB=KC. [Le point] K [appartient donc] à la médiatrice de [BC].

  [En utilisant la remarque précédente, on peut conclure que si M n'est pas sur la médiatrice de [BC], le point K est un meilleur point de concours que M. Autrement dit :]
            (4) Un point solution est sur la médiatrice de [BC]

  De même pour les deux autres cotés. [Donc, si M n'est pas sur les trois médiatrices du triangle, il n'est pas solution. En conclusion :] dans [le cas d'] un triangle équilatéral, le point de concours pour que la distance soit la plus courte est [ne peut être que] le centre du cercle circonscrit ([point de concours des médiatrices]) [voir note 8].

Conjectures

Pour 3 puits [en position quelconque] : des angles de 120°.

[...]

[Cas favorable] [Le triangle déterminé par les 3 points obéit à la] condition : Aucun [des] angles ne doit être superieur à 120°.  Conjecture : Le point [solution] est  le point se trouvant entre deux Pipe-Lines avec un écartement [d'où chaque coté est vu sous un angle] de 120°. [...]	[Autres cas] [L'un des angles est supérieur à 120°]   Conjecture : [Le point solution est le sommet de cet angle.]
Figure 4 : quand tout va bien	Figure 5 : quand un des angles, ici â, est supérieur à 120°.

Ceci n'est pas démontré mais vérifié expérimentalement par mesure et par une maquette reproduisant un phénomène physique : sur un bout de carton ou une feuille assez rigide, on fait trois trous. Puis on passe un bout de ficelle dans chaque trou et on fait un noeud au dessus du support de tel manière à relier les trois ficelles. Ensuite, en dessous du support on fixe [trois] poids d'égales masses, [un] au bout de chaque ficelle. On voit alors que [la position d'équilibre du] noeud est le sommet de trois angles de 120°. [Pour une explication voir note 9]

[Figure 6]

Pour 4 puits

[...] Si aucun des puits n'est aligné avec un autre, nous constatons que la figure obtenue est un quadrilatère. Or, nous pouvons diviser un quadrilatère en au moins 2 triangles différents. [..]Tentons donc la méthode vue auparavant concernant 3 puits de pétrole placés d'une manière quelconque sur ce quadrilatère divisé en 2 triangles (note 10). Résultat: A chaque essai, nous avons constaté une longueur de pipe-lines utilisée inférieure aux longueurs [..] obtenues par d'autres méthodes.
Conclusion : Il semblerait que diviser le quadrilatère en 2 triangles pour appliquer ensuite la solution obtenue pour 3 puits indifféremment placés à [aux sommets de l'un de] ces 2 triangles nous donne la [une] solution optimale. [Il y aurait ainsi plusieurs solution optimales, selon la manière dont on a divisé le quadrilatère en triangles et suivant le triangle choisi.]

Pour n puits

- Il en est de même pour n pipe-lines, il y a [aurait] alors plusieurs points de rencontre.

1. Les élèves n'ont pu nous fournir qu'un premier jet de leur article. C'est donc à partir d'une version très provisoire (que professeur et chercheur n'ont pu revoir,...dommage!) que avons bâti le texte présenté ici.

retour au texte

2. Ce problème, connu sous le nom de problème de Steiner est le sujet 01S01 du LaboraToilepour l'année 2001. Des Échos de la recherche sur ce sujet sont disponibles.

retour au texte

3. On reconnaitra le thème du "meilleur point de rencontre", sujet n° 82 du projet "es p  ace", traité par d'autres ateliers de recherche. voir les Échos de la recherche sur ce thème.

retour au texte

4. Bien que les auteurs ne l'aient pas formulée explicitement, l'existence de solutions ne faisant à leur yeux aucun doute, cette hypothèse clarifie les raisonnements présentés dans la suite de l'article. L'existence de points solutions peut être justifiée de manière directe, si on est capable de prouver qu'un point bien défini S réalise effectivement le minimum de la somme SA+SB+SC+..., ou encore de manière indirecte, comme une conséquence de théorèmes très généraux garantissant l'existence d'un minimum pour des fonctions numériques d'un certain type : ces théorèmes généraux peuvent par exemple résulter de propriétés de "convexité" (existence d'un minimum pour une fonction concave définie sur un domaine convexe) ou de propriétés de "compacité" (existence d'un minimum pour les fonctions continues définies sur un domaine fermé et borné).

retour au texte

5. Nous avons reconstitué et complété cette preuve à partir des notes des auteurs.

retour au texte

6. Pourquoi le triangle AKM est-il rectangle en K ? En fait, comme les auteurs le démontrent plus loin, le point K est sur la médiatrice du segment BC : la droite (AK) est ainsi perpendiculaire à (BC), donc à (d). On remarquera que si K et M ne sont pas confondus, l'inégalité (1) est stricte.

retour au texte

7. Car l'inégalité (1) est stricte (voir note précédente).

retour au texte

8. Tel est ce qui a été démontré : un point différent du centre n'est pas solution. Grâce à l'hypothèse d'existence faite en introduction, on en déduit que le centre est effectivement l'unique point solution.

retour au texte

9. L'idée de cette expérience physique fut donnée par le chercheur. Pourquoi fournit-elle effectivement un point solution ? Une explication physique s'obtient en utilisant le concept d'énergie potentielle et le "principe de Dirichlet" : un système isolé est en équilibre lorsque son énergie potentielle est minimum. Appelons A,B,C les sommets du triangle, M le point de concours des trois ficelles et A'B'C' les centres de gravité des poids placés respectivement au bout des ficelles passant par A,B et C. On sait que l'énergie potentielle d'un corps pesant est proportionnelle à la hauteur de son centre de gravité ; l'énergie potentielle de notre système (on néglige les frottements ainsi que le poids des ficelles) est donc de la forme U=U₀-k(AA'+BB'+CC') , où U₀ est l'énergie du système lorsque les points d'attache des poids sont dans les positions A,B et C respectivement. Ainsi, en désignant par a,b et c les longueurs des ficelles, obtient-on U= U₀-k(a+b+c)+k(MA+MB+MC). Cette expression montre que U est minimum lorsque la somme MA+MB+MC est elle-même minimum : à l'équilibre, M est donc bien un point solution.

retour au texte

10. Nous n'avons pas compris la méthode proposée : il s'agit apparemment de choisir arbitrairement 3 des 4 sommets du quadrilatère.

retour au texte

réseau minimum steiner distance puits_de_pétrole point_de_rencontre triangle equilatéral toricelli fermat

Comptes Rendus MATh.en.JEANS 00-11

© MATh.en.JEANS 2002. Tous droits réservés.