Fiche de révision : Recherche opérationnelle et programmation linéaire

📋 Plan du Cours

1. Formulation d’un programme linéaire
2. Résolution graphique et cas possibles
3. Forme standard et géométrie linéaire
4. Principe de la méthode du simplexe
5. Itérations de la méthode du simplexe
6. Initialisation par phase I
7. Dualité et optimalité

📖 1. Formulation d’un programme linéaire

🔑 Notions clés & Définitions

• Programmation linéaire : Programme qui cherche à maximiser ou minimiser une fonction linéaire de plusieurs variables soumises à des contraintes linéaires.

★ À maîtriser

• Pour produire x tonnes de A et y tonnes de B, avec des stocks de 300 tonnes de M1, 400 tonnes de M2 et 250 tonnes de M3, le profit à maximiser est $P=50x+100y$ sous les contraintes $x+y\leq300$, $2x+y\leq400$, $y\leq250$, $x\geq0$ et $y\geq0$.

Compléments

• La méthode du simplexe a été développée par G. B. Dantzig à partir de 1947.

📖 2. Résolution graphique et cas possibles

★ À maîtriser

• Dans l’exemple de production, le point B(50,250) donne un profit maximal de 27 500 Dh.

• Lorsqu’une solution finie existe, elle se trouve à un sommet du domaine des solutions admissibles.

Compléments

• 🔄 La résolution graphique se déroule ainsi :

  1. Représenter chaque programme par un point (x,y).
  2. Délimiter l’ensemble admissible par les contraintes.
  3. Déplacer parallèlement une droite de niveau de l’objectif pour chercher le meilleur point admissible.

• Le programme $\min 3x+4y$ sous $x+y\geq5$, $2x+y\leq4$, $x\geq0$ et $y\geq0$ n’a aucune solution admissible, car son domaine est vide.

• Pour le programme $\max 10x+20y$ sous $x+y\leq4$, $5x+10y\leq30$, $x\geq0$ et $y\geq0$, chaque point du segment AB est optimal.

• Pour le programme $\max 2x+5y$ sous $x+3y\geq3$, $5x+y\geq5$, $x\geq0$ et $y\geq0$, le maximum n’est jamais atteint et la solution est infinie.

• Un programme linéaire peut avoir les cas suivants :

  • Une solution unique
  • Aucune solution
  • Une infinité de solutions optimales
  • Une solution infinie

💡 Astuce mémo

Déplacer une droite de profit parallèle jusqu’au dernier point du domaine admissible.

📖 3. Forme standard et géométrie linéaire

🔑 Notions clés & Définitions

• Forme standard : Forme d’un programme linéaire donnée par $\min c^Tx$ sous $Ax=b$ et $x\geq0$, avec des seconds membres supposés non négatifs après multiplication éventuelle d’une équation par −1.
• Solution admissible : Vecteur x qui vérifie $Ax=b$ et $x\geq0$.
• Solution optimale : Pour un problème de minimisation, solution admissible x* telle que $c^Tx^*\leq c^Tx$ pour toute solution admissible x.
• Matrice de base : Pour une matrice A de rang m, matrice carrée formée de m colonnes linéairement indépendantes de A; elle est non singulière.
• Solution de base : Vecteur obtenu en choisissant une matrice de base, en fixant à zéro les n−m variables hors base, puis en résolvant le système pour les m variables de base.
• Ensemble convexe : Ensemble C de Rⁿ tel que, pour tous x et y de C et tout λ dans [0,1], le point λx+(1−λ)y appartient à C.
• Polyèdre : Ensemble des vecteurs de Rⁿ qui vérifient un système fini d’inégalités linéaires; tout polyèdre est convexe.

★ À maîtriser

• 🔄 Les transformations possibles sont :

  1. Transformer une maximisation en minimisation de l’opposé.
  2. Remplacer une inégalité par une égalité avec une variable d’écart ou de surplus non négative.
  3. Inverser une équation dont le second membre est négatif.
  4. Remplacer une variable libre par la différence de deux variables non négatives.
  5. Remplacer une variable non positive par l’opposé d’une variable non négative.

• Pour le système $Ax=b,\ x\geq0$, un point est extrémal de l’ensemble admissible si et seulement s’il est une solution de base admissible.

• Si un programme linéaire admet une solution optimale, il admet une solution de base optimale et un point extrémal optimal.

Compléments

📌 Une solution de base est admissible si toutes ses variables sont positives ou nulles, tandis qu’elle est dégénérée si au moins une variable de base est nulle.

• Si un programme linéaire admet une solution admissible, il admet une solution de base admissible.

📖 4. Principe de la méthode du simplexe

📝 Points essentiels

• Le principe de la méthode du simplexe est de passer d’une solution de base admissible à une autre solution de base admissible en améliorant la fonction objectif.

📖 5. Itérations de la méthode du simplexe

★ À maîtriser

• Pour une solution de base admissible, si $c_j-z_j\geq 0$ pour tout j, cette solution est optimale.

• Si une variable hors base x_q vérifie $c_q-z_q<0$ et peut entrer dans la base, sa valeur positive améliore la fonction objectif à minimiser.

• Si tous les coefficients y_iq de la colonne entrante sont non positifs, le problème possède une solution infinie.

• L’algorithme du simplexe consiste à trouver une base admissible initiale, tester les coûts réduits, choisir une variable entrante de coût réduit négatif, appliquer le test du rapport minimal, puis pivoter et recommencer.

Compléments

• Après élimination des variables de base, la fonction objectif s’écrit $z=z_0+\sum_{j=m+1}^{n}(c_j-z_j)x_j$, où $z_0=\sum_{i=1}^{m}c_i y_{i0}$ et $z_j=\sum_{i=1}^{m}c_i y_{ij}$.

📐 Formule - La valeur maximale admissible de x_q est $\min_{i:y_{iq}>0}\frac{y_{i0}}{y_{iq}}$ ; la ligne pivot p réalise ce minimum.

• Le nombre de solutions de base étant fini, une suite d’itérations strictement améliorantes du simplexe aboutit à l’optimum en un nombre fini d’itérations.

• En cas de dégénérescence, des itérations peuvent ne pas modifier la valeur de la fonction objectif et entraîner un cyclage ; des méthodes existent pour l’éviter.

💡 Astuce mémo

Choisir une variable entrante, tester le rapport minimal, pivoter.

📖 6. Initialisation par phase I

★ À maîtriser

• La phase I construit une solution de base admissible en forme standard, en ajoutant le nombre nécessaire de colonnes unités et les variables artificielles associées, puis en minimisant leur somme.

📌 À l’optimum de la phase I, une somme des variables artificielles non nulle signifie que le problème initial est irréalisable, tandis qu’une somme nulle signifie qu’il admet une solution de base admissible.

Compléments

📌 Quand la somme artificielle est nulle, les variables artificielles hors base sont supprimées ; une variable artificielle de base de valeur nulle est éliminée si sa contrainte est de la forme $\epsilon_i=0$, sinon un pivot peut la rendre hors base.

📖 7. Dualité et optimalité

★ À maîtriser

📐 Formule - Pour le primal $\min c^T x$ sous $Ax\geq b$ et $x\geq0$, le dual est $\max y^T b$ sous $y^T A\leq c^T$ et $y\geq0$.

📌 Pour des solutions admissibles x et y du primal et du dual, la dualité faible donne $y^T b\leq c^T x$ ; si ces valeurs sont égales, x et y sont optimales.

📌 Si l’un des problèmes en dualité admet une solution optimale, l’autre en admet aussi une et leurs valeurs optimales sont égales.

Compléments

• Dans l’exemple de location de machines, les produits A et B rapportent respectivement 4 dh et 5 dh par kilogramme, tandis que leurs besoins en heures sur les machines 1, 2 et 3 sont respectivement (2, 4, 4) et (4, 2, 4), pour des disponibilités de (12, 12, 14) heures.

• Dans la formulation générale de la dualité, maximisation et minimisation s’échangent, la matrice A devient sa transposée, les variables du primal correspondent aux contraintes du dual et inversement, et les conditions de signe et de liberté se correspondent.

📌 Si l’un de deux problèmes en dualité possède une solution infinie, l’autre n’a pas de solution admissible.

📌 Des solutions admissibles x et y du primal et du dual sont toutes deux optimales si et seulement si $x_i>0\Rightarrow y^T a_i=c_i$ et $y_j>0\Rightarrow a_j^T x=b_j$.

• Dans l’exemple des engrais, le coût minimal est de 4 500 DH par hectare pour 30 paquets de type A et 15 paquets de type B.

💡 Astuce mémo

Le primal maximise le profit ; le dual minimise le coût des ressources.

📊 Tableaux de synthèse

Primal et dual en dualité