مسابقة دكتوراه 2016 — Université des Sciences et de la Technologie Houari Boumediène (USTHB)

التمرين 1

Exercice 1 — Équilibre de l'utilisateur sur un réseau de transport urbain

#transport-network#user-equilibrium#wardrop-equilibrium#optimization#traffic-assignment

On considère le réseau de transport urbain de la figure ci-dessous. Il y a deux paires origine-destination : $1$ - $2$ et $3$ - $2$ respectivement. Les temps de parcours des différents arcs sont donnés par

t_a(x_a) = a_a + b_a x_a

où le temps de traversée de l'arc est exprimé en minutes en fonction du flot sur l'arc. Les coefficients sont : arc 1 $(A\to B): a_1=21, b_1=0.01$ , arc 2 $(A\to C): a_2=8, b_2=0.1$ , arc 3 $(B\to D): a_3=6, b_3=0.1$ , arc 4 $(C\to B): a_4=4, b_4=0.02$ , arc 5 $(C\to D): a_5=19, b_5=0.01$ .

Deux paires OD : de $A$ vers $D$ avec flux $q_{AD}=50$ véhicules/heure, et de $C$ vers $D$ avec $q_{CD}=50$ véhicules/heure.

Formuler le problème $(P)$ de l'équilibre de l'utilisateur.
Les flux d'équilibre obtenus par Excel sont : $f_1=0.00, f_2=13.12, f_3=36.88, f_4=9.96, f_5=40.04$ . En déduire les flux d'arcs, les temps de traversée des arcs et les temps des chemins.
Vérifier si cette solution satisfait les conditions de l'équilibre de l'utilisateur.
Un autre logiciel donne : $f_1=0.00, f_2=0.00, f_3=50.00, f_4=23.08, f_5=26.92$ . Cette solution est-elle d'équilibre ? Conclure.
Suite à une information de radioguidage erronée, une faible partie des usagers du chemin 3 empruntent le chemin 1 : $f_1=f_2=0, f_3=49, f_4=23, f_5=27$ . Calculer l'effet sur le temps total passé par l'ensemble des usagers sur le réseau. Est-on encore à une solution d'équilibre ?

◀الحل

1.

Le problème d'équilibre de l'utilisateur se formule comme un programme de Beckmann : minimiser

\sum_{a\in A} \int_0^{x_a} t_a(s)ds

sous les contraintes de conservation des flots OD et de non-négativité des flots de chemins.

2.

Les flots d'arcs se déduisent des flots de chemins. Puis on calcule

t_a = a_a + b_a x_a

pour chaque arc. Les temps des chemins sont les sommes des temps d'arcs correspondants.

3.

Une solution est un équilibre de Wardrop si tous les chemins utilisés entre une même paire OD ont le même temps minimal, et tout chemin non utilisé a un temps supérieur ou égal. On compare les temps des chemins actifs et inactifs.

4.

On refait le calcul des temps de chemins avec la deuxième solution. Si un chemin utilisé est plus long qu'un chemin non utilisé pour la même paire OD, ce n'est pas un équilibre.

5.

Le temps total sur le réseau est

TT = \sum_a x_a t_a(x_a).

On compare $TT$ avant et après perturbation. Si les conditions de Wardrop ne sont plus satisfaites, la solution n'est plus un équilibre.

\boxed{\text{Il faut recalculer les temps de chemins et } TT = \sum_a x_a(a_a+b_ax_a)}

التمرين 1

Exercice 1 — Arbres, forêts et poids maximum

#graph-theory#maximum-spanning-tree#forest#integer-programming

Rappels : un arbre est un graphe connexe et sans cycle, une forêt est un graphe sans cycle.

Question 1. Montrer que les propriétés suivantes sont équivalentes et caractérisent un graphe $T$ qui est un arbre : (i) $T$ est connexe et ne possède pas de cycle. (ii) $T$ ne contient aucun cycle et possède $n-1$ arêtes. (iii) $T$ est connexe et possède $n-1$ arêtes. (iv) $T$ est connexe et chaque arête est un isthme. (v) Deux sommets quelconques de $T$ sont reliés par une unique chaîne. (vi) $T$ ne contient aucun cycle mais l'adjonction à $T$ d'une quelconque nouvelle arête $\{i,j\}$ crée exactement un cycle $C_{ij}$ .

Question 2. Soit $G=(V,E)$ connexe avec un poids $p(i,j)$ sur chaque arête.

Montrer qu'un arbre $T=(V,F)$ est de poids maximum ssi pour chaque arête $\{i,j\} \in E\setminus F$ et toute arête $\{k,l\} \in C_{ij}$ , on a $c(i,j) \leq c(k,l)$ .
Décrire et justifier un algorithme glouton pour trouver une forêt de poids maximum de $G$ .
Donner une condition nécessaire et suffisante pour qu'une forêt de poids maximum soit un arbre.
Quelle modification apporter à l'algorithme pour qu'il donne un arbre de poids maximum ?

Question 3. On considère le programme entier $(F)$ pour la forêt de poids maximum.

Montrer que $(F)$ formule bien le problème.
Quelle contrainte ajouter pour obtenir une formulation de l'arbre de poids maximum ?
Montrer qu'on peut remplacer une contrainte par des contraintes de coupure.

◀الحل

1.

Toutes les caractérisations des arbres sont classiques et s'obtiennent par comptage des arêtes, connexité et unicité des chaînes.

2.1.

Critère d'échange sur un cycle : si une arête hors arbre était plus lourde qu'une arête du cycle fondamental, on pourrait échanger et augmenter le poids total.

2.2.

Algorithme glouton : trier les arêtes par poids décroissant et ajouter une arête si elle ne crée pas de cycle. On obtient une forêt de poids maximum.

2.3.

Une forêt de poids maximum est un arbre ssi elle est connexe.

2.4.

Pour obtenir un arbre de poids maximum, on impose la connexité ou on continue jusqu'à avoir $n-1$ arêtes.

3.

La formulation entière standard avec contraintes d'acyclicité et binaire est correcte. L'ajout de $\sum x_{ij} = n-1$ force une structure d'arbre. Les contraintes de cycle peuvent être remplacées par des contraintes de coupure.

التمرين 1

Exercice 1 — Programmation linéaire bi-objectif et solutions efficaces

#multiobjective-optimization#linear-programming#efficient-solutions#weighted-sum

On considère le programme linéaire bi-objectif suivant

(P) \begin{cases} \min \{-2x_1 + x_2\} \\\\ \min \{-4x_1 - 3x_2\} \\\\ \text{s.t. } x_1 + 2x_2 \leq 10, \; x_1 \leq 5, \; x_1,x_2 \geq 0. \end{cases}

Écrire le programme linéaire paramétrique associé $LP(\lambda)$ .
Calculer l'ensemble des bases efficientes, des points extrêmes efficients, des arêtes efficientes $Eff_{f\mu}$ , l'ensemble de toutes les solutions efficientes $X_{eff}$ et l'ensemble de tous les vecteurs critères non dominés $Y_N$ .
Donner les équations des courbes paramétriques relatives aux valeurs critiques de $\lambda$ et retrouver graphiquement les résultats obtenus.
En utilisant le cône polaire semi positif, retrouver graphiquement $X_{eff}$ et $Y_N$ .

◀الحل

1.

Le problème paramétrique pondéré est

LP(\lambda): \min \; \lambda(-2x_1+x_2) + (1-\lambda)(-4x_1-3x_2)

sous les mêmes contraintes, avec $\lambda \in [0,1]$ .

2-4.

On résout le problème pour les valeurs critiques de $\lambda$ où l'optimum change de base. Les points extrêmes admissibles se déterminent géométriquement. Les solutions efficientes sont celles non dominées dans l'espace des décisions, et $Y_N$ est leur image dans l'espace des critères.

Le cône polaire semi-positif permet de caractériser graphiquement les points efficaces via les normales de support.

\boxed{\text{Les solutions efficientes se déterminent par analyse des sommets et arêtes actives}}

التمرين 2

Exercice 2 — Arbre de poids maximum et formulations en nombres entiers

#graph-theory#maximum-spanning-tree#integer-programming#greedy-algorithm#forest

Soit $G=(V,E)$ un graphe simple et connexe et soit $p:E\to \mathbb{R}$ une application poids. On note $|V|=n$ et $E=\{e_1,e_2,\dots,e_m\}$ avec $p(e_i) \leq p(e_{i+1})$ .

Donner au moins trois caractérisations différentes des arbres et montrer leur équivalence.
Montrer que dans un graphe connexe, si $T$ et $T'$ sont deux graphes partiels distincts qui sont des arbres, alors $T$ contient une arête dont le rajout à $T'$ crée un unique cycle.
Soit la famille $T_i$ définie par : $T_i = E$ si $i=0$ , et pour $i \gt 0$ , $T_i = T_{i-1} \setminus \{e_i\}$ si $(V, T_{i-1} \setminus \{e_i\})$ est connexe, sinon $T_i = T_{i-1}$ . Montrer que $T_m$ est un arbre de poids maximum dans $G$ .
Donner la complexité de l'algorithme pour obtenir $T_m$ .
Comment modifier l'algorithme pour déterminer une forêt de poids maximum de $G$ ?
Donner, dans le graphe fourni, un arbre et une forêt de poids maximums.
Prouver que si $\forall e,e' \in E$ , $p(e) \neq p(e')$ , alors l'arbre de poids maximum est unique.
Montrer que si $G$ possède un cycle ayant une arête de poids inférieur à celui de toute autre arête de ce cycle, alors cette arête n'appartient à aucun arbre de poids maximum de $G$ .
On considère deux formulations entières $(F_1)$ et $(F_2)$ pour l'arbre de poids minimum. Montrer que $(F_1)$ et $(F_2)$ formulent ce problème et que $(F_2)$ est meilleure.

◀الحل

1.

Caractérisations équivalentes d'un arbre :

connexe et sans cycle,
connexe avec $n-1$ arêtes,
sans cycle avec $n-1$ arêtes,
entre deux sommets quelconques, il existe une unique chaîne.

2.

Comme $T \neq T'$ , il existe une arête $e \in T \setminus T'$ . L'ajout de $e$ à $T'$ crée un cycle unique car $T'$ est un arbre.

3.

C'est l'algorithme glouton de suppression des arêtes de plus faible poids tout en conservant la connexité. On montre par l'argument d'échange qu'il produit un arbre de poids maximum.

4.

En vérifiant la connexité à chaque suppression, complexité naive $O(m(n+m))$ .

5.

Pour une forêt de poids maximum : on n'impose plus la connexité globale, on supprime les arêtes qui appartiennent à un cycle, en gardant les plus lourdes dans chaque composante.

6.

On choisit les arêtes de plus grand poids sans créer de cycle.

7.

Si les poids sont tous distincts, l'algorithme glouton a des choix forcés. Donc unicité.

8.

Dans un cycle, l'arête strictement la plus légère ne peut appartenir à aucun arbre de poids maximum, sinon on peut l'échanger contre une arête plus lourde du cycle.

9.

$(F_1)$ et $(F_2)$ décrivent le polytope des arbres couvrants. $(F_2)$ est meilleure car ses contraintes de coupure donnent une relaxation linéaire plus serrée.

التمرين 2

Exercice 2 — Caractérisation scalaire des solutions efficaces

#multiobjective-optimization#efficient-solutions#scalarization

Soit $x^0$ une solution réalisable de l'ensemble $X = \{x \in \mathbb{R}^n : Ax=b, x \geq 0\}$ et $(P)$ le problème multi-objectif défini par $\min\{Cx : x \in X\}$ où $C \in \mathbb{R}^{p\times n}$ . Montrer que :

x^0 \text{ est solution efficiente si et seulement si il existe un vecteur } \lambda \in \mathbb{R}_+^p \setminus \{0\} \text{ tel que } \lambda^T C x^0 \leq \lambda^T Cx, \forall x \in X.

◀الحل

C'est le théorème classique de scalarisation linéaire sous convexité du domaine admissible.

$\Rightarrow$ Si $x^0$ est efficient, il existe un hyperplan de support au point $Cx^0$ du polytope des critères, de normale $\lambda \in \mathbb{R}_+^p \setminus \{0\}$ . Donc $\lambda^T Cx^0 \leq \lambda^T Cx$ pour tout $x \in X$ .

$\Leftarrow$ Si une telle inégalité est vraie et s'il existait $x$ dominant strictement $x^0$ , alors on aurait $Cx \leq Cx^0$ composante par composante avec une stricte inégalité pour au moins une composante, d'où $\lambda^T Cx \lt \lambda^T Cx^0$ , contradiction.

\boxed{x^0 \text{ est efficient } \iff \exists \lambda \geq 0, \lambda \neq 0, \lambda^T Cx^0 \leq \lambda^T Cx, \forall x \in X}

التمرين 2

Exercice 2 — Programmation linéaire bi-objectif et ensembles efficaces

#multiobjective-optimization#linear-programming#efficient-solutions#weighted-sum

On considère le programme linéaire bi-objectif

(P) \begin{cases} \max \; 3x_1 + x_2 \\\\ \max \; -x_1 - 2x_2 \\\\ x_1 + 2x_2 \geq 2, \; x_1 \leq 4, \; x_2 \leq 3, \; x_1,x_2 \geq 0. \end{cases}

Écrire le programme de somme pondérée $LP(\lambda)$ .
Calculer l'ensemble des bases efficientes, des points extrêmes efficients, des solutions efficaces $X_{eff}$ et des vecteurs critères non dominés $Y_N$ .
Donner les équations des courbes de niveaux relatives aux valeurs critiques de $\lambda$ et retrouver graphiquement les résultats.
À l'aide du cône polaire semi-positif, retrouver graphiquement les ensembles $X_{eff}$ et $Y_N$ .

◀الحل

1.

$LP(\lambda): \max \; \lambda(3x_1+x_2) + (1-\lambda)(-x_1-2x_2)$ sous les contraintes.

2-4.

Les ensembles efficaces se déterminent par étude géométrique du polytope admissible et des directions d'amélioration. Les valeurs critiques de $\lambda$ correspondent aux pentes des arêtes efficaces. Le cône polaire semi-positif permet de caractériser les points efficaces.

\boxed{\text{Les solutions efficaces sont les points non dominés du polytope admissible}}

التمرين 3

Exercice 3 — Ordonnancement sur graphe d'incompatibilité et coloration

#graph-theory#scheduling#graph-coloring#optimization

Dans une entreprise, les ouvriers $O$ doivent exécuter un certain nombre de tâches pour achever un projet. L'ensemble de toutes les tâches possibles est $T$ . On désire que tous les ouvriers qui doivent exécuter la tâche $t$ le fassent simultanément. Chaque ouvrier ne pouvant se présenter qu'à une tâche au plus chaque semaine. Le problème consiste à chercher le nombre minimum de semaines nécessaires pour terminer toutes les tâches. Présenter une modélisation mathématique de ce problème sous forme d'un outil de la théorie des graphes.

◀الحل

On construit le graphe d'incompatibilité des tâches : chaque sommet représente une tâche, et deux tâches sont reliées si elles partagent au moins un ouvrier. Deux tâches adjacentes ne peuvent pas être exécutées la même semaine.

Le problème revient alors à colorier les sommets du graphe avec un nombre minimal de couleurs, chaque couleur représentant une semaine.

\boxed{\text{Le nombre minimal de semaines est } \chi(G)}

où $\chi(G)$ est le nombre chromatique du graphe d'incompatibilité.

التمرين 4

Exercice 4 — Graphes planaires, nombre chromatique et graphes parfaits

#graph-theory#planar-graphs#chromatic-number#perfect-graphs#clique-number

Soit $G=(V,E)$ un graphe simple, connexe et non orienté. On note $\chi(G)$ le nombre chromatique, $\omega(G)$ la cardinalité d'une clique maximum, $\alpha(G)$ la cardinalité du plus grand stable et $\theta(G)$ la cardinalité d'une partition minimum en cliques.

Montrer que $\omega(G) \leq \chi(G)$ et en déduire que $\omega(G) \leq \theta(G)$ .
Montrer que $\chi(G)\alpha(G) \geq |V(G)|$ .
Montrer que $\chi(G) \leq \Delta(G) + 1$ .
a) Montrer que tout graphe planaire admet une triangulation. b) En supposant que tout graphe planaire admet au moins un sommet de degré \leq 5, montrer que si $G$ est planaire alors $\chi \leq 5$ .
a) Montrer que $K_5$ n'est pas planaire. b) Montrer que si $G$ est planaire et parfait alors $\chi(G) \leq 4$ .
Si $G$ est planaire non nécessairement parfait, a-t-on toujours $\chi(G) \leq 4$ ? Justifier.

◀الحل

1.

Toute clique nécessite des couleurs distinctes, donc $\omega(G) \leq \chi(G)$ . En dualisant par partition en cliques, on obtient aussi $\omega(G) \leq \theta(G)$ .

2.

Chaque couleur définit une classe stable de cardinal au plus $\alpha(G)$ . Donc $|V| \leq \chi(G)\alpha(G)$ .

3.

Coloration gloutonne : au plus $\Delta(G)+1$ couleurs suffisent.

4.

Tout graphe planaire peut être triangulé en ajoutant des arêtes dans les faces non triangulaires.

Si tout graphe planaire possède un sommet de degré \leq 5 $, une récurrence sur$ |V| $donne$ \chi(G) \leq 6$; avec raffinement, on obtient 5-colorabilité.

5.

$K_5$ n'est pas planaire par la formule d'Euler. Si $G$ est parfait, $\chi(G)=\omega(G)$ . Pour un graphe planaire, $\omega(G) \leq 4$ car $K_5$ n'est pas planaire, donc $\chi(G) \leq 4$ .

6.

Oui, par le théorème des quatre couleurs, tout graphe planaire est 4-colorable.

\boxed{\chi(G) \leq 4 \text{ pour tout graphe planaire}}