CONTROLE DE CONNAISSANCES 2018/2019

Etudiants 1ère année (EI1) – Juin 2019

MAT3602 – CF1 – Durée : 3h00
Coordonnateur : J. Neto

Documents autorisés : le polycopié du cours exclusivement (pas d’autres feuilles manuscrites,

polycopiés ou annales, livres, etc.). Calculatrices non autorisées.
On demande aux candidats d’accorder une attention toute particulière à la justification de leurs
réponses ainsi qu’à la rédaction qui sera prise en compte dans l’évaluation. Le barème est donné à
titre indicatif.

PARTIE 1
Exercice 1 – Algorithme de Prim [2 points]
Appliquer l’algorithme de Prim sur le graphe pondéré sur les arêtes (poids entre crochets) de la
figure 1, en prenant A pour sommet de départ. Pour ce faire, vous préciserez dans un tableau les
valeurs de marquage et voisins associés à chaque sommet pour chaque itération. Indiquez la solution
finale fournie par cet algorithme et son coût.

Figure 1 - Exercice 1

Page 1 sur 5
Exercice 2 – Arbres de recouvrement et connexité [2 points]
Etant donné un graphe G, on appelle point d’articulation de G un nœud dont la suppression (avec les
arêtes qui lui sont incidentes) augmente strictement le nombre de composantes connexes. Etant
donné un arbre T, on appelle feuille de T un nœud de degré 1 dans T.

1. Soit G un graphe connexe d’ordre N≥2. Déterminez (en justifiant votre réponse) si une feuille d’un
arbre de recouvrement de G peut correspondre à un point d’articulation de G.

2. Déterminez si tout graphe connexe d’ordre N≥2 comporte toujours au moins deux sommets qui ne
sont pas des points d’articulation.

Exercice 3 – Plus court chemin [2 points]

1. Quel algorithme de plus court chemin convient-il d’employer pour un graphe pondéré sur les arcs
tel que celui représenté ci-dessous (avec les poids entre crochets) ? Justifiez.

Figure 2 - Exercice 3

2. Mettre en œuvre cet algorithme sur le graphe donné en figure 2 en prenant A pour sommet de
départ. Détaillez les étapes de calculs dans un tableau où seront reportés, pour chaque itération k et
chaque sommet v, la longueur d’un plus court chemin de A à v comportant au plus k arcs, ainsi que le
prédécesseur de v sur un tel chemin. Interprétez les résultats obtenus.

Exercice 4 – Réseau de distribution d’eau [4 points]

Trois villes, désignées par J, K et L, sont alimentées en eau potable provenant de quatre réserves
A,B,C,D. Les réserves journalières disponibles sont de 15 milliers de mètres cubes d’eau pour A, de 10
pour B, de 15 pour C, et de 15 pour D. Le réseau de distribution est représenté par le graphe de la

Page 2 sur 5
figure 3. Les débits maximaux des canalisations sont indiqués sur chaque arc entre crochets en
milliers de mètres cubes d’eau par jour.

En pleine évolution, ces trois villes souhaitent améliorer leur réseau d’alimentation afin de satisfaire
des besoins futurs plus importants. Une étude a été faite et a permis de déterminer les demandes
maximales probables, à savoir : 15 milliers de mètres cubes par jour pour J, 20 pour K et 15 pour L.

1. Un ingénieur propose d’utiliser le réseau avec les flux indiqués en gras sur le graphe de la figure 3
(à côté des capacités données entre crochets). Partant des valeurs proposées par l’ingénieur,
déterminez un flot de valeur maximum. Pour ce faire, vous préciserez l’algorithme utilisé, le graphe
sur lequel celui-ci est appliqué (en complétant le graphe donné), et détaillerez les étapes permettant
d’aboutir au résultat. Indiquez la valeur du flot maximum.

Figure 3 - Réseau de distribution (Exercice 4)

2. Déterminez une coupe de capacité minimum. (Méthode et description précise demandées.)

3. La valeur de flot maximum obtenue précédemment est jugée nettement insuffisante. Aussi, le
conseil régional décide de rénover les canalisations (A,E) et (I,L) (exclusivement) et d’accroître leurs
capacités. Les travaux prévus sont longs et conséquents : il ne peuvent être réalisés simultanément
sur les deux canalisations.
Indiquez dans quel ordre il convient d’entreprendre les travaux sur les deux canalisations et
déterminez les capacités à prévoir sur (A,E) et (I,L) afin de maximiser le flot total vers les villes J, K et L
après tous les travaux. (Les valeurs proposées ne doivent pas correspondre à un
surdimensionnement : ces canalisations doivent être utilisées au maximum de leurs capacités dans
un flot maximum après la fin de tous les travaux sur (A,E) et (I,L).) Indiquez la valeur du flot
maximum après les travaux ainsi qu’une coupe de capacité minimum. Justifiez toutes vos réponses.

Page 3 sur 5
 PARTIE 2
Exercice 1 – Algorithme du simplexe [4 points]
1. Résoudre le programme linéaire (P) de minimisation suivant en utilisant l’algorithme du simplexe
(forme dite « du tableau »). Pour chaque itération, lorsque plusieurs variables peuvent entrer en
base on choisira toujours celle de plus petit indice. Détaillez les étapes de calculs (en précisant la
base courante, le pivot, …), donnez la solution optimale du problème et son coût.
2. Formulez le problème dual (D) de (P).
3. En utilisant les résultats obtenus en ‘1’, déterminez une solution optimale du problème dual (D) en
justifiant votre réponse.

(P)

Exercice 2 – Programmation non linéaire sans contrainte [2 points]

1. Déterminez l’ensemble des points stationnaires de la fonction (R désignant l’ensemble
des nombres réels), définie par :

2. Pour chaque point stationnaire trouvé : s’agit-il d’un maximum local (strict) ? d’un minimum
local (strict) ? Justifiez votre réponse.

3. On considère la mise en œuvre de la méthode de « plus forte pente » avec la règle de « pas
optimal » pour résoudre le problème de minimisation de la fonction f sans contrainte.

Effectuez une seule itération de cet algorithme et précisez les résultats obtenus (avec justifications)
en considérant les deux options suivantes pour le point de départ : et .

Exercice 3 – Programmation non linéaire avec contraintes [4 points]

On considère le problème (Q) de programmation non linéaire de maximisation suivant :

Page 4 sur 5
1. La fonction f qui définit l’objectif est-elle convexe ? concave ? Justifiez. (Une fonction f est dite
concave si et seulement si la fonction –f est convexe).

2. Le problème (Q) admet-il une solution optimale ? Justifiez.

3. Toute solution réalisable du problème (i.e. tout vecteur vérifiant les contraintes de (Q)) est-elle un
point régulier de (Q) ? Justifiez.

4. Formulez le lagrangien du problème posé.

5. Formulez les conditions nécessaires d’optimalité du premier ordre pour ce problème (i.e. toutes
les contraintes qui doivent être vérifiées par une solution optimale du problème, sous l’hypothèse
qu’une telle solution existe). (Développez les expressions des contraintes pour ce problème
particulier.)

6. Déterminez si la première contrainte (i.e. ) peut ne pas être active à l’optimum.

Justifiez.

7. Déterminez s’il existe une solution qui satisfait les conditions établies en 5 ainsi que l’équation
. Et si oui, cette solution est-elle unique ?

8. Déterminez l’ensemble des solutions du système de contraintes établi en 5 et vérifiant .

9. Donnez l’ensemble des solutions optimales de (Q).

Page 5 sur 5