I- Programmation linéaire
1) Exemples de modélisation
Pour se familiariser avec la modélisation mathématique, prenons quelques exemples très simples :
Exemple 1 : Programme de fabrication
Une entreprise fabrique des fauteuils sous deux modèles, le Luxe (L) et le standard (S). Des études
de marché ont montré que pour l’année à venir, les possibilités de ventes s’élèvent à 300 unités L
et 400 unités S. L’approvisionnement en cuir est suffisant pour pouvoir fabriquer annuellement
500 fauteuils quel que soit le type. Le temps de fabrication d’un fauteuil L est le double d’un
fauteuil S. Si tous les fauteuils étaient de type S, on pourrait en fabriquer annuellement 700 au
maximum. La vente donne un bénéfice (« marge unitaire sur coût variable ») de 7 DH pour un L et
de 5 DH pour un S.
Déterminer le programme linéaire qui modélise le programme annuel de fabrication qui procure
à l’entreprise un profit maximum.
Modélisation :
Si on appelle x1 le nombre de fauteuils L fabriqués et x2 le nombre de fauteuils S, on a donc :
Contraintes de positivité :
x1 0
x2 0
Contraintes du marché :
x1 300
x2 400
Contrainte d’approvisionnement :
x1 + x2 500
Contrainte du temps :
2x1 + x2 700
Fonction objective :
L’objectif du problème est de maximiser la fonction économique Z = 7x1 + 5x2.
En résumé, le programme de fabrication s’écrit :
Maximiser Z = 7x1 + 5x2
Sachant que :
x1 300
x2 400
x1 + x2 500
2x1 + x2 700
x1 0
x2 0
Exemple 2 : Planification des opérations et répartition des ressources
Une entreprise produit deux types de jouets L1 et L2. Chaque jouet L1 rapporte un profit de 20 DH
et chaque jouet L2 un profit de 40 DH.
L’entreprise utilise trois machines : A, B et C. Les capacités de travail hebdomadaire sont de 120 h pour
A, 72 h pour B et 10 h pour C. La fabrication de chaque jouet L1 nécessite 4h de travail sur la machine
A et 2h sur B alors qu’un jouet L2 nécessite 6h sur A, 6h sur B et 1h sur C. Pour simplifier, assumons
que les coûts d’achat des ressources et de production ont été comptabilités dans les profits unitaires
et que l’entreprise peut vendre toute sa production.
Combien de jouets de chaque type l’entreprise doit-elle produire pour optimiser ses profits ?
Modélisation :
Les variables de décision sont le nombre de jouets de chaque type à produire. Notons :
- x1 : Le nombre de jouet L1 à fabriquer.
- x2 : Le nombre de jouet L1 à fabriquer.
L’objectif à atteindre ici est la maximisation du profit global de l’entreprise :
Il s’agit donc de maximiser la fonction économique Z = 20 x1 + 40 x2
Les contraintes de fabrication et disponibilité s’écrivent :
4 x1 + 6 x2 ≤ 120 (machine A)
2 x1 + 6 x2 ≤ 72 (machine B)
1 x2 ≤ 10 (machine C)
Les contraintes de positivité des variables de décision sont :
x1 0
x2 0
Le programme de fabrication qui assure à l’entreprise un profit maximal est donc :
Maximiser Z = 20 x1 + 40 x2
Sachant que :
4 x1 + 6 x2 ≤ 120
2 x1 + 6 x2 ≤ 72
x2 ≤ 10
x1 0
x2 0