La programmation linéaire est un outil très puissant de la recherche opérationnelle. C'est un outil générique qui peut résoudre un grand nombre de problèmes. En effet, une fois un problème modélisé sous la forme d'équations linéaires, des méthodes assurent la résolution du problème de manière exacte. On distingue dans la programmation linéaire, la programmation linéaire en nombres réels, pour laquelle les variables des équations sont dans IR+ et la programmation en nombres entiers, pour laquelle les variables sont dans IN. Bien entendu, il est possible d'avoir les deux en même temps. Cependant, la résolution d'un problème avec des variables entières est nettement plus compliquée qu'un problème en nombres réels. Une des méthodes les plus connues pour résoudre des programmes linéaires en nombre réels est la méthode du Simplex. En théorie, elle a une complexité non polynômiale et est donc supposée peu efficace. Cependant, en pratique, il s'avère au contraire qu'il s'agit d'une bonne méthode. De plus, de nombreux logiciels intégrant cette méthode existent. Certains sont utilisés via une interface graphique alors que d'autres permettent une communication par fichiers ce qui autorise l'utilisation du programme de manière cachée dans le développement d'un autre logiciel.
La programmation linéaire permet la résolution d'un programme linéaire. Un programme linéaire est un système d'équations ou d'inéquations appelées "contraintes" qui sont linéaires (c'est-à-dire que les variables ne sont pas élevées au carré, ne servent pas d'exposant, ne sont pas multipliées entre elles...). Et à partir de ces contraintes, on doit optimiser une fonction également linéaire appelée objectif.
Contraintes linéaires:
Contraintes non linéaires:
Objectifs:
Pour résoudre un programme linéaire de manière automatique, il faut qu'il ait une certaine forme que l'on appelle "canonique". Dans ce cours, on a choisi la forme canonique suivante: un programme linéaire n'a que des contraintes d'infériorité et l'on tente de maximiser la fonction objectif. De plus toutes les variables sont positives.
Le programme linéaire suivant est sous forme canonique.
Tout programme linéaire quelconque peut être ramené à une forme canonique. Voici quelques exemples de transformations possibles. Si une variable x1 est négative, on la remplace par une variable positive x1' = -x1. Par exemple:
Si une variable n'a pas de contrainte de signe, on la remplace par deux variables positives x1' et x1'' telles que x1 = x1' - x1''. Par exemple:
Si le programme linéaire a une contrainte de supériorité, on la remplace par une contrainte d'infériorité en inversant le signe des constantes. Par exemple:
Si le programme linéaire a une contrainte d'égalité, on la remplace par deux contraintes équivalentes, l'une d'infériorité, l'autre de supériorité. Les variables du programme doivent satisfaire ces deux contraintes, ce qui revient alors à l'égalité de départ. Par exemple:
Une entreprise fabrique 2 produits X et Y. Pour sa conception, chaque produit fini nécessite 3 produits intermédiaires A, B et C. Pour fabriquer un produit X, on a besoin de 2 produits A, de 2 produits B et de 1 produit C. De même, pour fabriquer un produit Y, on a besoin de 3 produits A, de 1 produit B et de 3 produits C. En outre, l'entreprise dispose d'une quantité limitée de produits A, B et C. Elle a 180 produits A, 120 produits B et 150 produits C. Sachant que le prix de revient de X est 3 francs et que celui de Y est de 4 francs, combien de produits X et Y faut-il fabriquer pour maximiser le profit ? On modélise ce problème par un programme linéaire. Soit x et y les quantités de produits X et Y fabriqués. La quantité totale de produits A utilisée est 2x + 3y. Cette quantité ne doit pas dépasser 180, d'où la première contrainte.
De même, pour les produits B et C, on obtient:
Bien entendu, les quantités x et y sont positives.
Enfin, on tente de maximiser le profit qui est le total des bénéfices sur la vente des produits X plus celui des produits Y.
Le programme linéaire est donc le suivant.
On peut représenter le problème dans un espace à deux dimensions.
Les solutions admissibles sont représentées par la zone grisée (a,b,c,d,e). Ce sont les solutions qui satisfont les contraintes. Considérons maintenant la fonction z = 3x + 4y. Pour z = 120, on a une droite D1, 3x + 4y = 120, qui représente les solutions pour lesquelles le profit vaut 120. Si z = 180, on a une autre droite D2, 3x + 4y = 180, qui représente les solutions pour lesquelles le profit vaut 180. On remarque que D2 est parallèle à D1 et on s'aperçoit facilement qu'en déplaçant la droite vers le haut on augmente le profit z. Donc pour résoudre graphiquement le problème, on va faire "glisser" la droite vers le haut jusqu'à ce qu'elle ait un minimum de points communs avec la surface grisée. Le point restant ici est d. Il représente la solution pour laquelle le profit est maximum. En effet, si on prend un profit plus important, représenté par exemple par D4, on s'aperçoit que toutes les solutions sont en dehors de la surface grisée. Donc la solution du problème est de produire 45 produits X et 30 produits Y pour obtenir le profit maximum de z = 3x + 4y = 255 francs.
Globalement, la méthode du Simplex va se déplacer le long de la forme (a,b,c,d,e), de sommet en sommet jusqu'à trouver le meilleur point. Pour essayer de mieux comprendre comment fonctionne cette méthode, considérons le problème de production précédent. Dans un premier temps, les contraintes sont ramenées à des égalités en introduisant de nouvelles variables de la manière suivante.
Ensuite, on va se placer sur le point a = (0;0) qui est une solution admissible du problème. Dans un cas plus général, il faut noter que trouver une solution admissible pour démarrer la méthode du Simplex n'est pas forcément évident. On a alors:
En regardant z = 3x + 4y, on s'aperçoit que la moindre augmentation de x ou de y augmente le profit z. Donc on va augmenter l'une des deux variables au maximum. Par exemple, prenons y et utilisons les contraintes pour exprimer y en fonction de toutes les autres variables.
Comme toutes les variables sont positives, on peut en déduire, à partir de chaque contrainte, une borne maximum pour y (cf. ci-dessus). y doit satisfaire les 3 contraintes. Ici la plus grande valeur de y possible est 50. A l'aide de la contrainte C, on remarque que x doit rester à 0 et que w est forcé à 0. Maintenant, les variables nulles sont x et w. Quant aux autres variables, on s'arrange pour les exprimer uniquement avec x et w de manière à obtenir leur valeur. On fait de même pour le profit z.
On se trouve donc au point b = (x;y) = (0;50) avec un profit z = 200. Maintenant, on reprend le même raisonnement que pour le point a = (0;0). Le profit est exprimé par z = 200 + 5/3x - 4/3w. En augmentant x, on augmente le profit. On regarde de combien on peut augmenter x.
Ici, on prendra x = 30, la valeur maximum qu'il peut atteindre. Les variables qui sont nulles sont u et w d'après la contrainte A. On calcule les nouvelles valeurs des autres variables.
On se trouve donc au point c = (x;y) = (30;40) avec un profit z = 250. On recommence encore une fois le même raisonnement. Le profit est exprimé par z = 250 - 5/3u + 1/3w. En augmentant w, on augmente le profit. On regarde de combien on peut augmenter w.
Ici, on prendra w = 15, la valeur maximum qu'il peut atteindre. Les variables qui sont nulles sont u et v d'après la contrainte B. On calcule les nouvelles valeurs des autres variables.
On se trouve donc au point d = (x;y) = (45;30) avec un profit z = 255. On reprend encore une fois le même raisonnement. Le profit est exprimé par z = 255 - 5/4u - 1/4v. Ni u, ni v ne permettent d'augmenter le profit z. Cela signifie que l'on a obtenu le profit maximum. La solution recherchée est alors représentée par d le point courant. On aboutit bien à la même conclusion que par la représentation graphique. Il faut produire 45 produits X et 30 produits Y pour obtenir un profit maximum de 255 francs.
|