Recherche opérationnelle

Fiches de cours et sous-notions liées à ce chapitre.

Pas assez de questions pour un entraînement ciblé sur cette notion.

Programmation linéaire

Non commencé

Définitions

Programmation linéaire (PL) : $\min c^Tx$ sous contraintes linéaires $Ax \leq b$ , $x \geq 0$ . Région réalisable = polyèdre convexe. Théorème fondamental : optimum atteint en sommet (extrême point) si borné. Simplexe : parcours arêtes améliorant $c^Tx$ .

Dual : $\max b^Ty$ s.c. $A^Ty \leq c$ ; faible/forte dualité. Variables duales = prix ombre contraintes. Applications : allocation ressources, flux, planification.

PL : $\min c^Tx$ s.c. $Ax\leq b$ , $x\geq 0$ . Optimum en sommet. Simplexe. Dualité faible/forte ; prix ombre.

Applications : allocation, transport, planning.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$\min c^Tx \text{ s.c. } Ax \leq b,\ x \geq 0$
$\max b^Ty \text{ s.c. } A^Ty \leq c,\ y \geq 0$
$\text{Dualité faible : } c^Tx \geq b^Ty$
$\text{Optimum PL : sommet polyèdre}$

Exemples

Exemple 1

Dualité faible.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Pour $x$ et $y$ faisables : $c^Tx\geq b^Ty$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$c^Tx\geq b^Ty$ .

Exemple 2

Où est l'optimum ?

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Si le polyèdre est non vide et le problème borné : sommet optimal. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Optimum en sommet.

À retenir

Flots

Non commencé

Définitions

Théorie des flots : réseau $G=(V,E)$ , capacités $c(u,v)$ , source $s$ , puits $t$ . Flot $f$ respecte capacité et conservation. Valeur flot $|f| = \sum f(s,v)$ . Max-flow min-cut : flux max = capacité coupe min. Ford-Fulkerson : chemins augmentants ; Edmonds-Karp $O(VE^2)$ .

Couplage biparti réduit à flot. Applications : réseaux transport, assignation, connectivité.

Flots : capacités, conservation, valeur. Max-flow min-cut. Ford-Fulkerson / Edmonds-Karp. Couplage biparti via flot.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$0 \leq f(u,v) \leq c(u,v) \quad ; \quad \sum_v f(u,v) = 0 \text{ si } u \notin \{s,t\}$
$|f| = \sum_{v} f(s,v) - \sum_u f(u,s)$
$\max |f| = \min_{S} \mathrm{cap}(S, \bar{S})$
$\text{Couplage max biparti } = \text{ flot max sur graphe transformé}$

Exemples

Exemple 1

Théorème max-flow min-cut.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Valeur max du flot $=$ capacité min d'une coupe $s$ - $t$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$\max|f|=\min\mathrm{cap}(S,\bar S)$ .

Exemple 2

Couplage biparti.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Réduire à un flot unitaire sur graphe transformé. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Couplage max = flot max.

À retenir

Programmation dynamique

Non commencé

Définitions

Programmation dynamique (PD) : problème avec sous-structure optimale — optimum global construit d'optima sous-problèmes. Bellman : $V(i) = \min_j \{ c_{ij} + V(j) \}$ . Mémoïsation ou tabulation bottom-up. Sac à dos 0-1 : $O(nW)$ pseudo-polynomial.

Plus court chemin : Bellman-Ford, Floyd-Warshall. PD stochastique pour décisions séquentielles sous incertitude.

PD : sous-structure optimale + recouvrement. Bellman. Sac à dos $O(nW)$ . Floyd-Warshall, distances d'édition.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$V(n) = \mathrm{opt}_{x} \{ g(x) + V(n-1, \mathrm{next}(x)) \}$
$\text{Sac à dos : } V(i,w) = \max(V(i-1,w), v_i + V(i-1, w-w_i))$
$\text{Floyd : } d_{ij}^{(k)} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)})$
$\text{Complexité sac : } O(n \cdot W)$

Exemples

Exemple 1

Sac à dos 0-1 : récurrence.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) $V(i,w)=\max(V(i-1,w), v_i+V(i-1,w-w_i))$ si $w_i\leq w$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Récurrence standard $O(nW)$ .

Exemple 2

Floyd-Warshall.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) $d_{ij}^{(k)}=\min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Plus courts chemins tous couples $O(n^3)$ .