Recherche opérationnelle
Le simplexe, la méthode
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 4 : Le simplexe, la méthode
L’idée avant l’algorithme
Ce que fait le simplexe
En une phrase
Partir d’un sommet du polyèdre, passer à un sommet voisin qui améliore l’objectif, recommencer, s’arrêter quand aucun voisin n’améliore.
Pourquoi cela suffit
Le polyèdre est convexe : un sommet dont aucun voisin n’est meilleur est le meilleur de tous.
Il y a un nombre fini de sommets, et l’objectif augmente strictement à chaque étape : l’algorithme s’arrête.
Le vocabulaire du tableau
Trois notions
Les variables de base sont celles qu’on calcule ; les hors base sont mises à zéro.
Le coût réduit c_j - z_j d’une variable hors base est ce que l’objectif gagnerait si on l’augmentait d’une unité.
Un coût réduit positif signale un voisin meilleur.
Le tableau initial
Le point de départ
L’atelier, forme standard
\max Z = 30x + 25y \qquad \begin{cases} 2x + y + e_1 = 100\\ x + y + e_2 = 80 \end{cases}
Base de départ : e_1 et e_2, donc x = y = 0. C’est le sommet (0,0) — on ne produit rien.
Le tableau
| Base | x | y | e_1 | e_2 | b |
|---|---|---|---|---|---|
| e_1 | 2 | 1 | 1 | 0 | 100 |
| e_2 | 1 | 1 | 0 | 1 | 80 |
| c_j - z_j | 30 | 25 | 0 | 0 | Z = 0 |
Les deux règles de pivotage
Qui entre
La variable de coût réduit le plus grand — ici x, avec 30.
C’est celle qui rapporte le plus par unité.
Qui sort
Le plus petit rapport positif b_i / a_{ik} sur la colonne entrante :
\frac{100}{2} = 50 \qquad \frac{80}{1} = 80 \qquad\Longrightarrow\qquad e_1 \text{ sort}
Pourquoi le plus petit rapport
x ne peut croître que jusqu’à ce qu’une ressource s’épuise. La découpe s’épuise à 50 sacs, la couture à 80.
C’est la première qui bloque. Aller au-delà rendrait e_1 négative — donc sortirait du domaine.
La première itération
Le pivotage
Deux opérations
- Diviser la ligne du pivot par le pivot — ici 2.
- Retrancher aux autres lignes le multiple qui annule leur coefficient dans la colonne entrante.
Le tableau après la première itération
| Base | x | y | e_1 | e_2 | b |
|---|---|---|---|---|---|
| x | 1 | 0{,}5 | 0{,}5 | 0 | 50 |
| e_2 | 0 | 0{,}5 | -0{,}5 | 1 | 30 |
| c_j - z_j | 0 | 10 | -15 | 0 | Z = 1\,500 |
Ce que ce tableau dit
On est au sommet (50, 0)
x = 50, y = 0, e_1 = 0 — toute la découpe est consommée — et e_2 = 30 : il reste trente heures de couture.
La marge est passée de 0 à 1\,500 DH.
Le coût réduit de y vaut encore 10
Produire un sac B rapporte 25 DH, mais oblige à renoncer à une demi-unité de A, soit 15 DH.
25 - 15 = 10 > 0 \qquad\Longrightarrow\qquad \text{on n'a pas fini}
La seconde itération
Le pivotage
Qui entre, qui sort
y entre : c’est le seul coût réduit positif.
Rapports : 50 / 0{,}5 = 100 et 30 / 0{,}5 = 60. Le plus petit est 60 : e_2 sort.
Le tableau final
| Base | x | y | e_1 | e_2 | b |
|---|---|---|---|---|---|
| x | 1 | 0 | 1 | -1 | 20 |
| y | 0 | 1 | -1 | 2 | 60 |
| c_j - z_j | 0 | 0 | -5 | -20 | Z = 2\,100 |
Le critère d’arrêt
Quand s’arrêter
Tous les coûts réduits sont négatifs ou nuls : aucun voisin n’améliore. La solution courante est optimale.
Le résultat, identique au chapitre 3
x = 20, \qquad y = 60, \qquad Z = 2\,100 \text{ DH}
Deux itérations, deux sommets parcourus : (0,0) \to (50,0) \to (20,60). C’est exactement le trajet que l’œil suivait sur le dessin.
Ce que la dernière ligne contient en plus
Les coûts réduits des variables d’écart
e_1 vaut -5 et e_2 vaut -20.
Au signe près, ce sont les prix des ressources : une heure de découpe supplémentaire rapporterait 5 DH, une heure de couture 20 DH.
Une information que le dessin ne donnait pas
Le graphique donnait la solution ; le tableau donne la solution et sa valeur marginale.
C’est cette information que les chapitres 6 et 7 exploitent — et c’est ce qui, en pratique, intéresse le gestionnaire.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Le simplexe parcourt les sommets en améliorant l’objectif à chaque pas.
- La variable entrante est celle de plus grand coût réduit.
- La variable sortante est donnée par le plus petit rapport positif.
- On s’arrête quand tous les coûts réduits sont \leq 0.
- Sur l’atelier : deux itérations, x=20, y=60, Z = 2\,100 DH.
- La dernière ligne livre en prime les prix des ressources : 5 et 20 DH.
La suite
Le chapitre 5 examine les quatre situations où l’algorithme ne se déroule pas comme ici : optimum multiple, dégénérescence, solution non bornée, domaine vide.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)