Recherche opérationnelle
Le programme linéaire et ses formes
- 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 2 : Le programme linéaire et ses formes
La forme générale
Écriture développée
Un programme linéaire
\max \; Z = c_1x_1 + \dots + c_nx_n
\text{sous} \quad \begin{cases} a_{11}x_1 + \dots + a_{1n}x_n \leq b_1\\ \qquad\qquad\vdots\\ a_{m1}x_1 + \dots + a_{mn}x_n \leq b_m\\ x_j \geq 0, \quad j = 1,\dots,n \end{cases}
Écriture matricielle
La même chose, en trois lettres
\max \; Z = \mathbf{c}'\mathbf{x} \qquad \text{sous} \qquad \mathbf{A}\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0}
\mathbf{A} est m \times n : m contraintes, n variables.
Pourquoi on préfère cette écriture
Elle ne dépend plus de la taille du problème. Ce qu’on démontre pour \mathbf{A} vaut pour deux variables comme pour deux mille.
C’est la même raison qui fait préférer \mathbf{X} à un tableau de données en statistique.
Canonique et standard
Les deux formes normalisées
Forme canonique
Un maximum, des contraintes \leq, des variables \geq 0.
C’est la forme dans laquelle on écrit un problème de production.
Forme standard
Un maximum, des contraintes en égalités, des variables \geq 0.
C’est la forme dont le simplexe a besoin, parce qu’il résout des systèmes linéaires.
Passer de l’une à l’autre
Les variables d’écart
On ajoute à chaque contrainte \leq une variable positive qui absorbe la différence :
2x + y \leq 100 \qquad\Longleftrightarrow\qquad 2x + y + e_1 = 100, \quad e_1 \geq 0
Ce que la variable d’écart signifie
e_1 est le nombre d’heures de découpe non utilisées.
Ce n’est pas un artifice de calcul : c’est une grandeur de gestion, et sa valeur à l’optimum se lit directement dans le tableau final.
Les quatre conversions à connaître
Tout problème se ramène à la forme standard
| Si l’on a | On écrit |
|---|---|
| \min Z | \max (-Z) |
| \sum a_jx_j \leq b | \sum a_jx_j + e = b, e \geq 0 |
| \sum a_jx_j \geq b | \sum a_jx_j - e = b, e \geq 0 |
| x de signe quelconque | x = x^+ - x^-, avec x^+, x^- \geq 0 |
La conséquence
Un seul algorithme suffit pour tous les programmes linéaires du monde.
C’est ce qui fait la puissance du simplexe : la variété des énoncés se réduit à une forme unique avant tout calcul.
L’atelier sous forme standard
Le passage
Avant
\max \; Z = 30x + 25y \qquad \begin{cases} 2x + y \leq 100\\ \phantom{2}x + y \leq \phantom{0}80\\ x, y \geq 0 \end{cases}
Après
\max \; Z = 30x + 25y + 0e_1 + 0e_2
\begin{cases} 2x + y + e_1 \phantom{{}+e_2} = 100\\ \phantom{2}x + y \phantom{{}+e_1} + e_2 = \phantom{0}80\\ x, y, e_1, e_2 \geq 0 \end{cases}
Ce que le passage a changé
Deux inéquations, quatre variables
On avait 2 variables et 2 inéquations. On a maintenant 4 variables et 2 équations.
Un système de 2 équations à 4 inconnues a une infinité de solutions : il reste 4 - 2 = 2 degrés de liberté.
Solution de base
On fixe n - m variables à zéro — les variables hors base — et l’on résout pour les m autres, les variables de base.
Ici : 4 - 2 = 2 variables à zéro, 2 à calculer.
Le polyèdre des solutions
Le vocabulaire
Trois mots
Le domaine réalisable est l’ensemble des \mathbf{x} \geq 0 vérifiant \mathbf{Ax} \leq \mathbf{b}.
C’est un polyèdre convexe : l’intersection d’un nombre fini de demi-plans.
Ses sommets sont les points où n contraintes se coupent.
Convexe : ce que cela veut dire ici
Si deux points sont réalisables, tout le segment qui les joint l’est aussi.
Conséquence décisive : il n’y a pas d’optimum local qui ne soit global. Une fois qu’on ne peut plus améliorer, on a terminé.
Le théorème fondamental
Le résultat qui rend le simplexe possible
Si un programme linéaire admet un optimum fini, alors au moins un sommet du polyèdre est optimal.
Ce qu’il fait gagner
Le domaine contient une infinité de points. Les sommets sont en nombre fini — au plus \binom{n}{m}.
Chercher parmi les sommets au lieu de chercher partout : le problème passe de l’infini au fini. Tout l’algorithme du chapitre 4 consiste à parcourir ces sommets intelligemment.
Solutions de base et sommets
La correspondance
Toute solution de base réalisable — de base, et à composantes positives — correspond à un sommet du polyèdre, et réciproquement.
Sur l’atelier
4 variables, 2 équations : \binom{4}{2} = 6 choix de base possibles.
Quatre d’entre eux donnent des solutions positives — les quatre sommets (0,0), (50,0), (20,60), (0,80). Les deux autres donnent des valeurs négatives : ils sont hors du domaine.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Un programme linéaire s’écrit \max \mathbf{c}'\mathbf{x} sous \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}.
- Quatre conversions ramènent tout problème à la forme standard.
- Les variables d’écart sont les ressources inutilisées : elles ont un sens de gestion.
- Le domaine réalisable est un polyèdre convexe : pas d’optimum local piège.
- Si l’optimum est fini, il est atteint en au moins un sommet.
- Sommets et solutions de base réalisables sont la même chose : le fini remplace l’infini.
La suite
Le chapitre 3 dessine ce polyèdre. À deux variables on peut tout voir — et voir une fois vaut mieux que calculer dix fois.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)