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

التمرين 1

Exercice 1 — Programme linéaire et dualité

#linear-programming#duality#standard-form#complementary-slackness

On considère le programme linéaire

\min Z = 5x_1 + 6x_2 + 3x_3 + 3x_4 + 5x_5 + 4x_6

s.c.

x_1 + x_2 + x_3 \le 550,\quad x_4 + x_5 + x_6 \le 350,\quad x_1 + x_4 \ge 400,\quad x_2 + x_5 \ge 300,\quad x_3 + x_6 \ge 200,\quad x_i \ge 0.

Montrer que les deux programmes linéaires $(P_1)$ et $(P)$ ont le même ensemble de solutions réalisables.
Écrire le dual $(D)$ de $(P_1)$ .
Montrer que si $y^*=(y_1,y_2,y_3,y_4,y_5)^T$ est une solution réalisable optimale de $(D)$ , alors $y^*+\alpha$ est aussi une solution réalisable optimale de $(D)$ pour tout $\alpha=(a,a,-a,-a,-a)^T$ .
Pour le vecteur $x=(x_1,\ldots,x_6)^T$ avec $x_1=50, x_2=300, x_3=200, x_4=350, x_5=x_6=0$ , chercher une solution réalisable de $(D)$ satisfaisant la condition que pour tout $i \in \{1,\ldots,6\}$ , si $x_i \gt 0$ alors la $i$ -ième contrainte du dual est une égalité. En déduire que $x$ est une solution optimale de $(P)$ .

◀الحل

On met d'abord le problème en forme standard. Le dual se construit en associant une variable à chaque contrainte. La structure particulière des contraintes entraîne une invariance par translation $\alpha=(a,a,-a,-a,-a)^T$ .

En utilisant la condition de complémentarité sur le vecteur proposé $x$ , on cherche $y$ tel que les contraintes duales associées aux variables strictement positives soient saturées. Une fois $y$ trouvé réalisable, la dualité forte et les écarts complémentaires donnent l'optimalité de $x$ .

التمرين 1

Exercice 1 — Graphes : chaînes maximales, cycles et parité

#graph-theory#paths#cycles#parity

Soit $G=(V,E)$ un graphe connexe simple.

Montrer que si $P=(v_1,v_2,\ldots,v_k)$ est une plus longue chaîne élémentaire dans $G$ , alors tous les voisins de $v_1$ sont dans $P$ .
Montrer que si tous les degrés des sommets de $G$ sont supérieurs ou égaux à deux, alors $G$ possède un cycle élémentaire.
Montrer que si tous les degrés des sommets de $G$ sont supérieurs ou égaux à $k \geq 2$ , alors $G$ possède un cycle élémentaire de longueur supérieure ou égale à $k+1$ .
Démontrer que deux chaînes de longueur maximum $P$ et $Q$ de $G$ ont au moins un sommet commun. Ont-elles une arête commune ?
En déduire que si $G$ possède deux chaînes de longueur maximum elles sont obligatoirement de longueur paire. Où se situe le sommet commun ?

◀الحل

1.

Si un voisin de $v_1$ n'était pas dans $P$ , on pourrait prolonger $P$ en ajoutant ce voisin devant $v_1$ , contradiction avec la maximalité de $P$ .

2.

Soit $P$ une plus longue chaîne élémentaire. Par 1, tous les voisins de $v_1$ sont dans $P$ . Comme $deg(v_1) \geq 2$ , il existe un voisin $v_i$ avec $i \geq 3$ . Alors $(v_1,v_2,\ldots,v_i,v_1)$ est un cycle élémentaire.

3.

Même argument : $v_1$ a au moins $k$ voisins tous dans $P$ , donc il existe un voisin $v_i$ avec $i \geq k+1$ , donnant un cycle de longueur au moins $k+1$ .

4.

Deux chaînes de longueur maximum ont au moins un sommet commun, sinon en prenant une plus courte liaison entre elles on construirait une chaîne plus longue. Elles n'ont pas forcément une arête commune.

5.

Si elles ont même longueur maximale et un sommet commun central, elles se croisent en leur milieu. Cela impose une longueur paire quand les deux moitiés ont même longueur.

التمرين 2

Exercice 2 — Graphes bipartis et planarité

#graph-theory#bipartite-graphs#planar-graphs#euler-formula

Soit $G=(X\cup Y,E)$ un graphe biparti simple et connexe ayant $n$ sommets et $m$ arêtes.

Donner les bornes supérieure et inférieure du nombre d'arêtes.
Montrer qu'il existe un sommet dans $G$ de degré au plus $m/n$ .
Montrer que si $G$ est régulier de degré $r$ , alors $|X|=|Y|$ .

Exercice 3. La maille d'un graphe $G$ est la longueur d'un plus petit cycle de $G$ . Soit $G$ un graphe planaire simple et connexe ayant $n$ sommets, $m$ arêtes et $f$ faces. Supposons que la maille de $G$ est $k$ ( $k \ge 3$ ).

Montrer que $kf \le 2m$ .
En déduire que $m \le \frac{k(n-2)}{k-2}$ .
Vérifier pour $k=3,4,5$ que $K_5$ , $K_{3,3}$ et le graphe de Petersen ne sont pas planaires.

◀الحل

Pour un graphe biparti simple connexe, $n-1 \le m \le |X||Y| \le n^2/4$ .

Il existe un sommet de degré au plus $2m/n$ par moyenne des degrés. Si le graphe est régulier biparti de degré $r$ , alors $r|X|=m=r|Y|$ , d'où $|X|=|Y|$ .

Pour le graphe planaire de maille $k$ , chaque face a au moins $k$ arêtes et chaque arête borde deux faces : $kf \le 2m$ . Avec Euler $n-m+f=2$ , on déduit $m \le \frac{k(n-2)}{k-2}$ . Les cas $K_5$ , $K_{3,3}$ et Petersen violent cette borne pour les valeurs données de $k$ .

التمرين 2

Exercice 2 — Optimisation linéaire et problème du sac à dos

#linear-programming#duality#knapsack#complementary-slackness

(A) On considère le problème d'optimisation linéaire

\max Z(x)=4x_1-3x_2

s.c.

-x_1+x_2 \le 6, \quad x_1+x_2=4, \quad -2x_1+4x_2 \ge 2, \quad x_1\in[-3,2], x_2\ge 0.

Résoudre ce problème à l'aide de l'algorithme dual et détailler les étapes.
Écrire le problème dual.
Trouver les valeurs des variables duales.
Vérifier le théorème des écarts complémentaires.

(B) On considère le problème du sac-à-dos avec objets de poids $(2,3,4,5)$ et valeurs $(3,4,5,6)$ .

Écrire le programme linéaire correspondant.
Décrire une méthode autre que le simplexe pour le résoudre.

◀الحل

(A)

On met le problème sous forme standard puis on construit le dual. La résolution peut se faire par tableau dual-simplexe. Les contraintes actives à l'optimum déterminent les variables duales par complémentarité.

Le problème dual associe une variable à chaque contrainte, avec les signes dépendant du type de contrainte. Après résolution, on vérifie les écarts complémentaires entre les variables primales et duales.

(B)

Le programme du sac-à-dos 0-1 est :

\max 3x_1+4x_2+5x_3+6x_4

s.c.

2x_1+3x_2+4x_3+5x_4 \le b, \quad x_i \in \{0,1\}.

Méthode autre que le simplexe : programmation dynamique, branch-and-bound, ou algorithme pseudo-polynomial classique du sac-à-dos.