Recherche opérationnelle
Le simplexe, les cas particuliers
- 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 5 : Le simplexe, les cas particuliers
Quatre situations
Ce qui peut arriver
Les quatre cas
- Optimum multiple — plusieurs solutions donnent la même valeur.
- Dégénérescence — une variable de base vaut zéro.
- Solution non bornée — l’objectif croît sans limite.
- Domaine vide — aucune solution ne respecte toutes les contraintes.
Pourquoi il faut les connaître
Chacun se lit dans le tableau, à un endroit précis. Un praticien qui ne les reconnaît pas prend un message d’erreur pour une panne du logiciel.
Les cas 3 et 4 signalent presque toujours une erreur de modélisation, pas un problème sans solution.
L’optimum multiple
Comment le repérer
Le signe dans le tableau
À l’optimum, une variable hors base a un coût réduit nul.
On peut la faire entrer sans rien changer à Z : il existe un autre sommet optimal.
Sur l’atelier, si la marge de A valait 50
\max Z = 50x + 25y : la pente de l’objectif devient -2, exactement celle de la contrainte de découpe.
Alors (50,0) et (20,60) donnent tous deux Z = 2\,500 — et tout le segment entre les deux aussi.
Ce que cela signifie en gestion
Une bonne nouvelle, pas un ennui
Plusieurs plans de production donnent la même marge. On peut donc choisir sur un second critère que le modèle ignorait : la charge de travail, la trésorerie, le risque commercial.
L’optimum multiple offre une liberté — encore faut-il savoir qu’elle existe.
La forme de l’ensemble des optima
C’est toujours une face du polyèdre : un segment en dimension deux, une arête ou une facette au-delà.
Toute combinaison convexe de deux sommets optimaux est optimale.
La dégénérescence
Ce que c’est
Une variable de base nulle
Une solution de base est dégénérée si l’une de ses variables de base vaut zéro.
Géométriquement : plus de contraintes se coupent au sommet qu’il n’en faut pour le définir.
Comment cela arrive
Une égalité dans les rapports au moment de choisir la variable sortante : deux lignes bloquent en même temps.
L’une sort, l’autre reste dans la base à la valeur zéro.
Sa conséquence
Le pivotage sur place
L’itération suivante peut changer la base sans changer la solution : on reste au même sommet, et Z n’augmente pas.
Si cela se répète en boucle, l’algorithme cycle et ne s’arrête jamais.
Le remède
La règle de Bland — à égalité, choisir la variable de plus petit indice — garantit la terminaison.
En pratique le cyclage est rarissime, et les solveurs perturbent légèrement les seconds membres pour l’éviter. La dégénérescence, elle, est très fréquente : ce n’est pas une pathologie.
La solution non bornée
Le signe
Une colonne sans rapport positif
Une variable a un coût réduit positif, mais tous les coefficients de sa colonne sont \leq 0.
Aucune ligne ne la bloque : elle peut croître indéfiniment, et Z avec elle.
Un exemple
\max Z = x + y \qquad \text{sous} \qquad x - y \leq 2, \quad x, y \geq 0
Prendre x = y = t vérifie la contrainte pour tout t, et Z = 2t \to +\infty.
Ce qu’il faut en conclure
Un profit infini n’existe pas
Aucune entreprise ne peut gagner sans limite. Un problème non borné est un problème mal posé.
Presque toujours : une contrainte de capacité a été oubliée — la matière première, la demande, la trésorerie.
Le réflexe
Ne pas chercher à réparer l’algorithme. Relire l’énoncé et chercher la ressource qu’on n’a pas écrite.
Le domaine vide
Le signe
Une variable artificielle survivante
Pour démarrer avec des contraintes \geq ou =, on ajoute des variables artificielles, pénalisées dans l’objectif.
Si l’une reste positive à l’optimum, c’est qu’aucune solution réalisable n’existe.
Des contraintes incompatibles
x + y \leq 10 \qquad\text{et}\qquad x + y \geq 20
Le domaine est vide : il n’y a rien à optimiser.
Ce qu’il faut en conclure
Le message est une information
Un domaine vide dit que les exigences dépassent les capacités : le contrat promet plus que l’atelier ne peut produire.
C’est la réponse la plus utile que le modèle puisse donner — à condition de la lire comme telle et non comme un échec.
Le diagnostic pratique
Relâcher les contraintes une à une pour trouver laquelle rend le problème impossible.
La contrainte coupable est celle qu’il faudra renégocier.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Optimum multiple : coût réduit nul hors base — une liberté de choix, pas un problème.
- Dégénérescence : variable de base nulle, causée par une égalité des rapports.
- Elle peut faire cycler l’algorithme ; la règle de Bland l’en empêche.
- Non borné : coût réduit positif et colonne entièrement négative.
- Un problème non borné signale une contrainte oubliée.
- Domaine vide : variable artificielle survivante — les exigences dépassent les capacités.
La suite
Le chapitre 6 découvre que tout programme linéaire en cache un second, qui pose la question inverse — et dont la solution était déjà dans la dernière ligne de notre tableau.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)