La programmation linéaire – cours et exercices corrigés

La programmation linéaire est une technique qui permet de répondre à l’interrogation suivante : le programme des ventes déterminé en amont par les services commerciaux permet-il de saturer les contraintes productives et cela de façon optimale en termes de résultat attendu ?

Sous cette forme, le problème a deux aspects qui seront envisagés successivement :

  • assurer, si possible, le plein emploi des capacités productives (c’est-à-dire les équipements et la majeure partie de la main-d’œuvre) ;
  • choisir une combinaison productive de produits qui maximise la rentabilité.

L’illustration de la programmation linéaire

Élaboration d’un programme de production pour assurer le plein emploi des ateliers

L’illustration de cet outil sera envisagée dans le cadre d’un exemple d’entreprise de l’industrie mécanique.

Exemple applicatif 1

Soit une entreprise de construction mécanique qui produit trois types de roulement : R1, R2 et R3. Les trois types de roulement passent successivement dans trois ateliers. Leurs temps de passage en heures et par atelier sont donnés dans le tableau ci-après :

La programmation linéaire

Pour des impératifs commerciaux, la production des roulements R3 est fixée à 200 unités.

Existe-t-il un programme de production qui assure le plein emploi des capacités ? En cas de réponse négative, quel programme choisir ?
Les contraintes peuvent être mises en équation, en prenant pour acquis la vente et la production de 200 R3. Le choix se situe donc entre les produits R1 et R2.

Ces différentes contraintes peuvent être rapportées sur un graphique.

La programmation linéaire

Équations des contraintes :

atelier A1 → 4R1 + 2R2 + R3 ≤ 2600 d’où 4R1 + 2R2 ≤ 2 600 – (200 R3 × 1) soit 2 400
atelier A2 → 3R1 + 3R2 ≤ 2 500 – (200 R3 × 2) soit 2 100
atelier A3 → 2R1 + 5R2 ≤ 3 000 – (200 R3 × 3) soit 2 400

Démarche générale

Chaque contrainte partage le plan en trois zones :

  • la droite elle-même qui représente toutes les combinaisons de produits qui saturent la contrainte ;
  • une zone en dessous de la contrainte : les combinaisons de cette partie du plan respectent la contrainte mais n’assurent pas le plein emploi de ses capacités ;
  • la partie supérieure du plan : les combinaisons de produits sont inacceptables puisqu’elles nécessitent plus de facteurs de production que l’on en dispose.

Pour assurer le plein emploi simultané des contraintes productives, il faut rechercher la ou les combinaison(s) productive(s) qui saturent toutes les contraintes concernées.

exemple applicatif 1 (suite)

L’ensemble des contraintes définit un polygone de combinaisons acceptables ABCD0. Aucun point de ce domaine ne permet de saturer toutes les contraintes de production.

Seuls les points B et C assurent le plein emploi de deux des trois contraintes de production.

Solution B : intersection de l’atelier A2 et de l’atelier A3, sous-activité de l’atelier A.

Il suffit de résoudre le système d’équation suivant pour obtenir la combinaison de produits :

3R1 + 3R2 = 2 100
2R1 + 5R2 = 2 400

et on obtient 367 R1 et 333 R2.

L’atelier A1 est en sous-emploi de : 2400 – (367 R1 × 4) – (333 R2 × 2) = 266 heures

Solution C : intersection de l’atelier A1 et A2, l’atelier 3 est en sous-activité.

Sur le graphique, on lit la combinaison de produits soit 500 R1 et 200 R2.

L’atelier A3 est en chômage pour : 2400 – (500 R1 × 2) – (200 R2 × 5) = 400 heures

Démarche générale

À cette étape du raisonnement, le choix doit se faire entre le coût relatif du chômage de chaque atelier.

Il intégrera le montant des charges fixes spécifiques mais également les possibilités d’obtenir des travaux de sous-traitance sur les ateliers en sous-activité afin de réduire cette dernière.

Compte tenu des résultats précédents, l’entreprise peut également chercher des solutions qui permettent d’augmenter les capacités des ateliers :

  • recours aux heures supplémentaires ;
  • organisation différente du travail : travail sur trois équipes au lieu de deux ;
  • réallocation des matériels (lorsque c’est possible) entre ateliers en sous-activité et ceux à qui ils manquent des capacités.

Dans les cas envisagés précédemment, c’est l’atelier A2 qui limitait la production et obligeait au sous-emploi des autres ateliers : on qualifie cette situation de goulot d’étranglement.

Exemple applicatif 1 (suite)

L’entreprise décide d’affecter des capacités supplémentaires pour obtenir le plein emploi de ces trois ateliers.

Dans cette perspective, elle choisit la combinaison productive représentée par le point M du graphique qui correspond à 450 R1 et 300 R2 (chiffres lus sur le graphique).

L’atelier A2 devrait disposer d’une capacité de : (450 R1 × 3) + (300 R2 × 3) = 2 250 heures

Si l’entreprise veut choisir cette solution, elle doit affecter une capacité supplémentaire de 150 heures (2 250 – 2 100) à l’atelier A2.

Recherche de la solution optimale en termes de rentabilité

Toutes ces possibilités ont été envisagées sans l’aspect pécuniaire. Mais les choix de l’entreprise ne peuvent s’effectuer sans référence aux coûts des ateliers ni à la rentabilité des différents produits.

Reprenons le cas de l’entreprise de construction mécanique.

Exemple applicatif 2

Supposons que les produits R1,R2 et R3 dégagent respectivement une marge sur coûts variables de 160, 140 et 50 euros.

La solution optimale est celle qui maximise la marge sur coût variable globale.

C’est-à-dire : MAX F = 160 R1 + 140 R2

La fonction ainsi définie est appelée Fonction économique du programme. Elle peut s’écrire aussi :

R2 = – 1,15 R1 + MAX F

Sous cette forme, la fonction économique est une fonction de la forme ax + b et MAX F est une constante qu’il faut maximiser tout en respectant les contraintes de l’entreprise. Cela revient à chercher la droite de pente égale à – 1,15 et dont l’ordonnée à l’origine est maximum. Il existe une méthode graphique pour choisir la solution optimale.

Reprenons le graphique précédent.

La programmation linéaire Exemple applicatif

La marge sur coût variable globale dégagée est de : (160 € × 500 R1) + (140 € × 200 R2) = 108 000 €.

Démarche générale

La fonction économique (F) doit être représentée au point 0. Il existe toute une famille de droites parallèles à la droite F et qui possèdent des ordonnées à l’origine de plus en plus élevées dès que l’on se déplace vers le haut du graphique.

Le déplacement sur le graphique d’une droite parallèle à la droite tracée permet de déterminer directement le point d’intersection entre le polygone des solutions acceptables et la fonction économique : ce point est celui de la solution optimale. Ici, il s’agit du point C représentant une combinaison de 500 R1 et de 200 R2.

Remarque : La solution graphique est praticable dans le cas de deux produits car elle conduit à des représentations géométriques simples. Dès que le nombre de produits s’accroît, il faut avoir recours aux techniques du simplexe pour résoudre ce type de problème.

Exercices corrigés sur la programmation linéaire en PDF

le document ci-dessous comprend des exercices avec leurs corrigés détaillés vont vous permettre de vous entraîner et d’acquérir la pratique de cette technique.

DocumentPage de téléchargement
Cours sur La programmation linéaireTélécharger
Article précédentLe marketing relationnel
Article suivantLe diagramme de GANTT

LAISSER UN COMMENTAIRE

S'il vous plaît entrez votre commentaire!
S'il vous plaît entrez votre nom ici