PROGRAMMATION LINEAIRE

Modélisation linéaire

Comme toute méthode quantitative, la programmation linéaire repose sur un

modèle mathématique qui est supposé représenter au mieux le système réel. Plus
concrètement, le gestionnaire a besoin de connaître tous les éléments utiles à la résolution de
son problème, de déterminer les différentes interactions et relations qui les régissent, et les
formuler mathématiquement, avant de procéder à la résolution du problème sous sa forme
mathématique.

Dans la pratique, cette étape de formulation (modélisation) est souvent délicate et cruciale et
devrait être menée avec beaucoup de vigilance en intégrant le maximum d’informations
disponibles.

Modéliser un problème sous forme linéaire consiste à :

- Préciser les variables de décisions (les inconnues du problème) : les variables sont
souvent notées x1, . . ., xn

- Formuler en fonction des variables de décision l’objectif à atteindre (appelé aussi la

fonction économique ou fonction objectif). En termes économiques, il s’agit en
général de minimiser les coûts, maximiser les profits, …

- Déterminer les contraintes qui pèsent sur les variables et qui limitent la portée des
actions (disponibilité de ressources, capacité de production, limite du marché, …). Les
contraintes prennent la forme d’équations et d’inéquations linéaires. Des contraintes
de non-négativité (positivité) xi ≥ 0 sont souvent utilisées pour rappeler que les
variables de décision peuvent-être toujours ramenées à des quantités positives.
 Le terme ‘linéaire’ rappelle que la modélisation se fait exclusivement par des expressions
mathématiques du type α1x1 +…+ αpxp qui supposent les hypothèses de proportionnalité
et d’additivité :

- La proportionnalité : Le profit (ou le coût) provenant d’un produit rattaché à une variable
de décision est proportionnel à la valeur de cette variable (si le lavage d’une voiture
coûte 30DH, pour en laver 10 il faut 300 DH …)
- L’additivité : Le profit (ou le coût) total est la somme des profits (ou coûts) provenant
des différents produits.

En résumé :

Un problème linéaire (ou programme linéaire) (PL) est un problème d’optimisation

consistant à maximiser (ou minimiser) une fonction économique linéaire à n variables de
décision, soumises à un ensemble de contraintes exprimées sous forme d’équations ou
d’inéquations linéaires.

A l’origine, le terme programme a le sens de planification opérationnelle mais il est aujourd’hui

employé comme synonyme de problème (d’optimisation). Le programme linéaire obtenu après
modélisation est dit sous forme canonique : les contraintes peuvent être des égalités ou
inégalités (supérieures ou inférieures). Les inégalités sont toujours au sens large.
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 un programme annuel de fabrication qui donne 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 objectif :

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

Exemple 3 : Programme de Distribution

La société TRANS est chargée de livrer un produit à partir de deux usines U1 et U2 vers trois
clients C1, C2 et C3. Le coût unitaire (en DH / tonne) de transport varie selon la destination
usine-client :

C1 C2 C3

U1 5 4 6

U2 5 5 4

(Par exemple, pour transporter une tonne du produit de l’usine U1 vers le client C3 le coût de
transport est de 6 DH).
Les stocks disponibles en produit sont de 250 tonnes pour U1 et 300 tonnes pour U2.

D’autre part, les demandes formulées par les clients sont 150 tonnes pour C1, 200 tonnes
pour C2 et 150 tonnes pour C3.

La société souhaite planifier son programme de livraison pour minimiser le coût global du
transport.

Modélisation :

Variables de décision : Il s’agit de déterminer la quantité à livrer à partir de chaque usine vers
chaque client. Bien entendu, la société peut satisfaire la commande d’un client à partir de
plusieurs livraisons partielles provenant des différentes usines, ceci dans le but de minimiser
les coûts de transport et de respecter les contraintes de disponibilité du produit dans les
usines.

Notons par xij la quantité à livrer de l’usine Ui vers le client Cj. (1≤ i ≤2 et 1≤j≤3). Il y a donc
6 inconnues dans ce problème : x11 , x12 , x21 , x22 , x31 , x32 .

L’objectif à atteindre par la société est de minimiser le coût global de l’opération : la fonction
économique s’écrit dans ces conditions comme suit :

Minimiser Z = (5x11 + 5x21) + (4x12+ 5x22) + (6x13+ 4x23)

Entre parenthèses, le coût de transport relatif à chaque client.

Les contraintes dans ce genre de problème sont de deux types : contraintes liées aux stocks
disponibles et les contraintes liées à la demande :

- Contraintes de stock : La somme des quantités livrées à partir d’une usine ne peut dépasser
le stock disponible à cette usine :

Pour l’usine U1 : x11 + x12 + x13 ≤ 250

 Pour l’usine U2 : x21 + x22 + x23 ≤ 300

- Contraintes de la demande : La somme des quantités reçues par un client doit correspondre
à sa commande :

Pour le client C1 : x11 + x21 = 150

Pour le client C1 : x12+ x22 = 200

Pour le client C1 : x13+ x23 = 150

- Contraintes de positivité : xij  0 (1 ≤ i ≤ 2 et 1 ≤ j ≤ 3)

Le programme de livraison qui minimise le coût global de transport dans ces conditions est le
suivant :

Minimiser Z = 5x11 + 5x21 + 4x12+ 5x22 + 6x13+ 4x23

Sachant que :

x11 + x12 + x13 ≤ 250

x21 + x22 + x23 ≤ 300

x11 + x21 = 150

x12+ x22 = 200

x13+ x23 = 150

xij  0 (1 ≤ i ≤ 2 et 1 ≤ j ≤ 3)