Intelligence Artificielle et Recherche Opérationnelle

FORMULAIRE FINAL — INTELLIGENCE ARTIFICIELLE ET RECHERCHE OPÉRATIONNELLE

Programmation linéaire

Étape	Règle
Forme standard	$\le$ : $+ s_i$ (écart) ; $\ge$ : $- e_i + a_i$ (excédent + artificielle)
Méthode graphique	Optimum en un sommet ; pente de l'objectif $-c_1/c_2$
Simplexe : entrante	Coefficient le plus négatif de la ligne $Z$ (max)
Simplexe : sortante	Plus petit ratio second membre / coefficient strictement positif
Optimalité (max)	Aucun coefficient négatif dans la ligne $Z$
Non borné	Colonne entrante sans coefficient positif

Dualité

$$\max c^{T}x,\; Ax \le b,\; x \ge 0 \quad \Longleftrightarrow \quad \min b^{T}y,\; A^{T}y \ge c,\; y \ge 0 \qquad Z^* = W^* \qquad y_i\,s_i = 0 \qquad x_j\,e_j = 0$$

Prix fictif $y_i = \partial Z^* / \partial b_i$ = coût réduit de $s_i$ dans le tableau optimal, valable dans l'intervalle où les variables de base restent positives.

Transport et affectation

$$m + n - 1 \text{ cases occupées} \qquad u_i + v_j = c_{ij} \text{ (cases occupées)} \qquad \delta_{ij} = c_{ij} - u_i - v_j \ge 0 \text{ (optimalité)}$$

Vogel : pénalité = écart entre les deux plus petits coûts. Hongroise : réduire lignes et colonnes, couvrir les zéros, retrancher le plus petit non couvert, l'ajouter aux intersections.

Graphes et projets

Outil	Règle
Dijkstra	Fixer la plus petite étiquette, mettre à jour les voisins
Kruskal	Arêtes croissantes sans cycle, $n - 1$ arêtes
PERT	$ES$ = max des $EF$ des prédécesseurs ; $LF$ = min des $LS$ des successeurs
Marges	$MT = LS - ES$ ; $ML = \min ES_{succ} - EF$ ; critique si $MT = 0$
PERT probabiliste	$(a + 4m + b)/6$ ; variance $((b - a)/6)^2$

Heuristiques et apprentissage

$$\text{Recuit : } P = e^{-\Delta/T} \qquad A^* : f = g + h \qquad Gini = 1 - \sum p_c^2 \qquad d = \sqrt{\sum (x_j - y_j)^2}$$

$$\text{Exactitude} = \frac{VP + VN}{n} \qquad \text{Précision} = \frac{VP}{VP + FP} \qquad \text{Rappel} = \frac{VP}{VP + FN} \qquad F_1 = \frac{2PR}{P + R}$$

CONSEILS POUR L'EXAMEN

1. Modélisez avant de calculer : définissez chaque variable avec son unité, puis l'objectif et les contraintes ; une bonne formulation rapporte une part importante des points.
2. Vérifiez toujours la solution dans les contraintes d'origine, et l'égalité $Z^* = W^*$ quand vous utilisez le dual.
3. Simplexe : présentez chaque tableau et indiquez les opérations sur les lignes ; une erreur de pivot se propage à tous les tableaux suivants.
4. Transport : comptez les cases occupées ($m + n - 1$) avant de calculer les potentiels.
5. PERT : présentez un tableau unique avec durées, dates, marges ; vérifiez que la durée du chemin critique est égale à celle du projet.
6. Heuristiques : dites clairement si votre résultat est optimal ou seulement une bonne solution, et comparez-le à l'optimum quand il est calculable.
7. Apprentissage automatique : écrivez la matrice de confusion avec ses totaux et interprétez chaque indicateur en mots (« parmi les clients signalés… »).
8. Pour les rappels de statistique, voyez les cours de statistique descriptive et de probabilités.