Chapitre 1 :Programmation linéaire

Modélisation d’un programme linéaire (PL)

Introduction : La programmation linéaire est un problème d’optimisation mathématique qui

consiste à trouver l’optimum (maximum ou minimum) d’une fonction à n variables x1 , x2 , , xn ,
liées tous par m contraintes g i ( X )  0 ou g i ( X )  0 . Notons qu’un programme linéaire peut être
ramené à un problème d’optimisation combinatoire.

I. Etapes de modélisation d’un programme linéaire (PL)

La formalisation mathématique d’un problème concret est une tâche délicate mais essentielle car elle
conditionne la découverte ultérieure de la bonne solution. Elle comporte les mêmes phases quelles
que soient les techniques requises ultérieurement pour le traitement (programmation linéaire ou
programmation non linéaire) : Généralement il y a trois étapes à suivre pour pouvoir construire le
modèle d'un programme linéaire :

1. Identifier les variables du problème à valeur non connues (variable de décision) et les
représenter sous forme symbolique (exp. x1 , y1 ).
2. Identifier les restrictions (les contraintes) du problème qui s’expriment en général par des
relations entre les variables et qui se représentent sous forme d’un système d’équations ou
d’inéquations linéaires.
3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction
des variables de décision. Spécifier si le critère de sélection est à maximiser ou à minimiser.

II. Présentation théorique

Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite
fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En langage
mathématique, on décrira de tels modèles de la manière suivante :

Soient n variables de décision x1 , x2 , , xn l’hypothèse que les variables de décision sont positives
implique que x1  0, x2  0, , xn  0 .
La fonction objectif est une forme linéaire en fonction des variables de décision de type
Z  c1 x1  c2 x2    cn xn où les coefficients c1,…,cn doivent avoir une valeur bien déterminée
(avec certitude) et peuvent être positifs, négatifs ou nuls. Par exemple le coefficient ci peut
représenter un profit unitaire lié à la production d’une unité supplémentaire du bien xi, ainsi la valeur
de Z est le profit total lié à la production des différents biens en quantités égales à x1 , x2 , , xn .

Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis
par m inégalités :

1
Chapitre 1 :Programmation linéaire

a11 x1  a12 x2    a1n xn  b1

a x  a x    a x  b
 21 1 22 2 2n n 2

 
am1 x1  am 2 x2    amn xn  bm

où les coefficients am1 , , amn et b1 , , bm doivent avoir une valeur bien déterminée (avec
certitude) et peuvent être positifs, négatifs ou nuls. Le paramètre bi représente la quantité de matière
première disponible dont le bien xi utilise une quantité égale à aij xi .

En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :

max c1 x1  c2 x2    cn xn
 a x  a x  a x  b
 11 1 12 2 1n n 1


 a21x1  a22 x2    a2 n xn  b2

 
 am1 x1  am 2 x2    amn xn  bm


 x1  0, x2  0, , xn  0

III. Exemples de modélisations

Plusieurs problèmes de divers domaines sont représentés ou approximés par des modèles de PL.
L’utilisation de ces techniques de modélisation s’est renforcée encore après avoir construit des
algorithmes et des logiciels capables de résoudre de plus larges problèmes avec autant de variables
de décision que de contraintes.

La tâche de formulation demande généralement une certaine expertise et connaissance du problème

pour pouvoir relever facilement les différentes composantes du problème et ainsi donner un
programme qui modélise au mieux la situation réelle. Dans ce qui suit, on présentera quelques
exemples de formulation en programme linéaire liés à différents problèmes de décision.

Exemple 1: Problème de médecine :

Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir les sujets atteints
d’un rhume. Ces pilules sont fabriquées selon deux formats :

 Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1 grain de codéine.
 Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6 grains de codéine.
Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate et 24
grains de codéine. Déterminer le nombre de pilules minimales à prescrire au sujet pour qu’il soit
guérit.

2
Chapitre 1 :Programmation linéaire

Modélisation du problème en un PL

Le problème de médecine présente certaines ressemblances avec le problème de l’agriculture, dans

les deux cas c’est un problème d’allocation de ressources.
 Les variables de décision qui représentent des valeurs inconnues par le décideur qui est dans ce
cas le spécialiste en médecine sont :
- x1 : le nombre de pilules de petite taille à prescrire.
- x2 : le nombre de pilules de grande taille à prescrire.

On vérifie bien que les variables de décision x1 et x2 sont positives : x1  0, x2  0 .

 Les contraintes imposées par le problème sur les valeurs possibles de x1 et x2 sont :
- La prescription doit contenir des pilules avec au moins 12 grains d’aspirine. Sachant qu’une
petite pilule contient 2 grains d’aspirine et qu’une grande pilule contient un seul grain d’aspirine,
on obtient la contrainte suivante : 2 x1  x2  12 .
- De la même façon que pour l’aspirine, la prescription du spécialiste en médecine doit contenir au
moins 74 grains de bicarbonate. Ainsi la contrainte suivante doit être satisfaite : 5x1  8x2  74 .
- Finalement la contrainte imposée par le fait que la prescription doit contenir au moins 24 grains
de codéine est : x1  6x2  24 .
 Identification de la fonction objectif. On remarque qu’il y a plusieurs couples de solutions
( x1 , x2 ) qui peuvent satisfaire les contraintes spécifiées à l’étape 2. La prescription doit
contenir le minimum possible de pilules. Donc le critère de sélection de la quantité de pilules à
prescrire est celle qui minimise le nombre total des pilules Z  x1  x2 .

Le programme linéaire qui modélise ce problème médical est donc le suivant :

min x1  x2
 2 x  x  12


1 2

 5 x1  8 x2  74
 x  6 x  24
 1 2


 x1  0, x 2  0

Exemple 2 : Problème de production

Exemple 2.1. Pour fabriquer deux produits P1 et P2 on doit effectuer des opérations sur trois
machines M1, M2 et M3, successivement mais dans un ordre quelconque. Les temps unitaires
d’exécution sont donnés par le tableau suivant :

M1 M2 M3
P1 11 mn 7 mn 6 mn
P2 9 mn 12 mn 16 mn

On supposera que les machines n’ont pas de temps d’inactivité.

La disponibilité pour chaque machine est :
3
Chapitre 1 :Programmation linéaire

 165 heures (9900 minutes) pour la machine M1 ;

 140 heures (8400 minutes) pour la machine M2 ;
 160 heures (9600 minutes) pour la machine M3 .
Le produit P1 donne un profit unitaire de 900 dinars et le produit P2 un profit unitaire de 1000 dinars.
Dans ces conditions, combien doit-on fabriquer mensuellement de produits P1 et P2 pour avoir un
profit total maximum ?

Modélisation en un PL :

 Les variables de décisions sont :

-x1 : le nombre d’unités du produit P1 à fabriquer
-x2 : le nombre d’unités du produit P2 à fabriquer
 Les contraintes outre les contraintes de non-négativité sont :
- 11x1  9x2  9900 pour la machine M1
- 7 x1  12 x2  8400 pour la machine M2
- 6 x1  16 x2  9600 pour la machine M3
 Le profit à maximiser est : Z  900x1  1000 x2
Le programme linéaire résultant est :

max 900x1  1000x2

 11x  9 x  9900


1 2

 7 x1  12 x 2  8400
 6 x  16 x  9600
 1 2


 x1  0, x2  0

Exemple [Link]ème de Production.

Un constructeur automobile a la possibilité de produire des voitures, des camionnettes et des
vélos. Chaque voiture, camionnette et vélo vendue, rapporte un profit de 3000 u.m, 2000 u.m et
500 u.m respectivement. L’usine est constituée de 3 ateliers : découpage des tôles, assemblage et
finition intérieure. Chaque atelier fonctionne 8 heures par jour. Le tableau suivant montre le temps
(en minutes) nécessaire dans chaque atelier à la production de chaque véhicule.

Découpage Assemblage Finition

Voiture 2 5 7
Camionnette 4 7 2
Vélo 0.5 1 0

Avant d’être livrés aux différents concessionnaires de la marque, les véhicules sont entreposés, en
fin de journée, dans un hangar pouvant recevoir l’équivalent de 200 voitures. Une camionnette
occupe 5 fois plus de place qu’un vélo et une voiture 3 fois plus de place qu’un vélo. Suite à des
commandes importantes provenant de différentes sociétés de transport, l’entreprise est dans
l’obligation de produire un minimum de 30 camionnettes par jour. Donner le programme linéaire
correspondant à ce problème.
4
Chapitre 1 :Programmation linéaire

Modélisation en un PL :

 Les variables de décision du problème sont :

- x1 : le nombre de voitures à produire par jour.
- x2 : le nombre de camionnettes à produire par jour.
- X3: le nombre de vélos à produire par jour.

 Les contraintes de non-négativité sont vérifiées.

 Les contraintes du problème sont :
- Temps de découpage par jour : 2 x1  4 x2  0.5x3  8  60
- Temps d’assemblage par jour : 5x1  7 x2  x3  8  60
- Temps de finition par jour : 7 x1  2 x2  8  60
- Contrainte sur l’espace dans l’hangar : 3x1  5x2  x3  3  200
- Le nombre minimum de camionnettes à produire par jour : x2  30
 La fonction objectif à maximiser est : Z  3000x1  2000 x2  500 x3 .

Le programme linéaire résultant est :

max( 3000x1  2000 x 2  500 x3 )

 2 x  4 x  0.5 x  480
 1 2 3

 5 x1  7 x 2  x3  480

 7 x1  2 x 2  480
 3 x1  5 x 2  x3  600

 x 2  30

 x1  0, x 2  0, x3  0

Exemple 3: Problème d’alimentation

On se propose de réaliser une alimentation économique pour des bestiaux, qui contient
obligatoirement 4 sortes de composants nutritifs, A, B, C et D. L’industrie alimentaire produit
précisément deux aliments M et N qui contiennent ces composants : 1 Kg d’aliment M contient 100
g de A, 100 g de C, 200 g de D ; 1 Kg d’aliment N contient 100 g de B, 200 g de C, 100 g de D. Un
animal doit consommer par jour au moins : 0.4 Kg de A, 0.6 Kg de B, 2 Kg de C et 1.7 Kg de D.
L’aliment M coûte 10 u.m le Kg et N coûte 4 u.m le Kg. Quelles quantités d’aliments M et N doit-
on utiliser par jour et par animal pour réaliser l’alimentation la moins coûteuse ?

Modélisation en un PL :

On peut résumer toutes les données du problème dans le tableau suivant :

M N Quantités prescrites
A 0.1 0 0.4
5
Chapitre 1 :Programmation linéaire

B 0 0.1 0.6
C 0.1 0.2 2
D 0.2 0.1 1.7
Coût 10 4
Ce genre de tableau peut aider à mieux analyser le problème et ainsi formuler le programme linéaire
correspondant.

Les variables de décision sont :

- x1 : la quantité d’aliments M à utiliser pour l’alimentation des deux bestiaux
- x2 : la quantité d’aliments N à utiliser pour l’alimentation des deux bestiaux
Les contraintes de non-négativité sont x1  0, x2  0.

 Le choix de cette quantité est contraint à la présence dans l’alimentation du composant

- A : 0.1 x1  0.4  x1  4
- B : 0.1 x2  0.6  x2  6
- C : 0.1 x1  0.2 x2  2  x1  2 x2  20
- D : 0.2 x1  0.1 x2  1.7  2 x1  x2  17

 La fonction objectif est une fonction coût : Z  10x1  4 x2 .

Le programme linéaire est un programme de minimisation :

min 10 x1  4 x2
 x 4
 1

 x2  6

 x1  2 x2  20
 2 x1  x2  17


 x1  0, x2  0

Exemple 4 : Sélection de Médias

Une entreprise désire effectuer une campagne publicitaire dans la télévision, la radio et les journaux
pour un produit lancé récemment sur le marché. Le but de la campagne est d’attirer le maximum
possible de clients. Les résultats d’une étude de marché sont donnés par le tableau suivant :

Télévision Radio Journaux

Locale Par satellite
Coût d’une publicité 40 u.m 75 u.m 30 u.m 15 u.m
Nombre de client potentiel par publicité 400 900 500 200
Nombre de client potentiel femme par publicité 300 400 200 100

Pour la campagne, on prévoit de ne pas payer plus que 800 u.m pour toute la campagne et on
demande que ces objectifs soient atteints :

6
Chapitre 1 :Programmation linéaire

1. Au minimum 2000 femmes regardent, entendent ou lisent la publicité ;

2. La campagne publicitaire dans la télévision ne doit pas dépasser 500 u.m;
3. Au moins 3 spots publicitaires seront assurés par la télévision locale et au moins de deux spots
par la télévision par satellite.
4. Le nombre des publicités dans la radio ou dans les journaux sont pour chacun entre 5 et 10.

Modélisation en un PL :

 Les variables de décision du problème sont :

- x1 : le nombre de spots publicitaires dans la télévision locale
- x2 : le nombre de spots publicitaires dans la télévision par satellite
- x3 : le nombre de spots publicitaires dans la radio
- x4 : le nombre d’affiches publicitaires dans les journaux
 Les contraintes de non-négativité sont vérifiées.

 Les contraintes du problème sont :

- Coût total de la compagne publicitaire : 40 x1  75x2  30 x3  15x4  800
- Nombre de clients femmes potentiels par publicité : 300 x1  400 x2  200 x3  100 x4  2000

 Contraintes de la télévision : 40x1  75x2  500 , x1  3 et x2  2

 Contraintes sur le nombre de publicités dans la radio et dans les journaux :
5  x3  10 et 5  x4  10 .

 La fonction objectif à maximiser représente le nombre de clients potentiels par publicité

Z  400 x1  900 x2  500 x3  200 x4 .

Le programme linéaire résultant est :

max 400x1  900x2  500x3  200x4

 40 x  75 x  30 x  15x  800
 1 2 3 4

 30 x1  40 x2  20 x3  10 x4  2000

 40 x1  75 x2  500
 x1  3


 x2  2
 x3  5

 x3  10

 x4  5
 x4  10


 x1 , x2 , x3 , x4  0
Exemple 5 : Problème du transport
Une entreprise stock un produit dans trois dépôts A1, A2 et A3. Les quantités stockées sont
respectivement a1, a2 et a3. Les dépôts doivent alimenter 4 magasins B1, B2, B3 et B4. La quantité du
7
Chapitre 1 :Programmation linéaire

produit nécessaire au point de vente Bj : j=1, …,4 est bj. Si cij est le coût unitaire de transport du
produit de dépôt Ai vers le point de vente Bj, comment l’entreprise doit-elle répartir les stocks du
produit entre les points de vente ?
Modélisation en un PL :

Une condition nécessaire pour que ce problème possède une solution est que l’offre soit au mois
égale à la demande d’où :  ai   bj .
i j

 Les variables de décision du problème sont :

xij : quantité du produit acheminée depuis le dépôt Ai au point de vente Bj.
 Les contraintes de non-négativité sont vérifiées.
 Les contraintes du problème sont :

- La quantité acheminée de dépôt Ai vers le point de vente Bj ne dépasse pas la quantité

4

disponible, d’où  xij  ai pour i=1,…,3.

j1
3

- La quantité acheminée doit satisfaire la demande d’où  xij  bj pour j=1,…,4.

i 1

3 4
 Fonction objectif : le coût de transport à minimiser, donc Z (min)   cij xij , d’où le
i 1 j 1

problème peut s’écrire sous la forme suivante :

 3 4

 min 
i 1 j 1
cij xij
 4

  xij  ai pour i  1,...,3
 j 1
 3
  xij  b j pour j  1,...,4
 i 1
 xij  0 pour i  1,...,3 et j  1,...,4


Exemple 6 : Problème du sac à dos

Considérons n objets, notés i=1,...,n, apportant chacun un bénéfice c i et possédant un poids ai. On
veut ranger ces objets dans un sac que l'on veut au maximum de poids b. Le problème de sac-à-dos
(knapsack) consiste à choisir les objets à prendre parmi les n objets de manière à avoir un bénéfice
maximal et respecter la contrainte du poids à ne pas dépasser. Chaque objet i, i∈ {1,...,n}, doit être
sélectionné au moins pi fois et au plus qi fois. Ce problème se rencontre bien entendu dès que l'on
part en randonnée en voulant emmener le plus possible d'objets utiles (nourriture, boissons,...). Ce
problème est plus fréquemment utilisé pour remplir les camions de transport, les avions ou bateaux
de fret et même pour gérer la mémoire d'un microprocesseur.

8
Chapitre 1 :Programmation linéaire

Modélisation en un PL :
La formulation en un problème linéaire en nombres entiers du problème de sac-à-dos est très simple.
On utilise pour chaque objet i 1,...,n, une variable entière xi correspondant au nombre de fois où
l'objet i est choisi. Le problème du sac-à-dos est donc équivalent au programme en nombres entiers
suivant.

 n

 max 
i 1
ci xi
 n

  ai xi  b, (1)
 i 1

 p i  xi q i , pour i  1,..., n
 x  N, pour i  1,..., n
 i

La contrainte (1) est dite contrainte de sac-à-dos. Elle est l'unique contrainte de ce programme
linéaire en nombres entiers qui est un problème difficile algorithmiquement à résoudre.

Exemple 7 : Problème du voyageur de commerce :

On considère un ensemble de n villes et les distances cij qui les séparent. Le problème du voyageur
de commerce consiste à déterminer le tour le plus court possible passant exactement une fois par
chaque ville et revenant au lieu de départ (cycle Hamiltonien).

Modélisation en un PL :

Il y a n villes et nous notons cij la distance entre la ville i et la ville j. Pour modéliser le problème du
voyageur de commerce, nous utilisons les variables suivantes :

1 si le voyageur va de i vers j
xij   ,
0 sinon

Alors le problème du voyageur de commerce peut être modélisé comme suit :

9
Chapitre 1 :Programmation linéaire

 n n

 min  
j 1 i 1
cij xij

 n x  1,
 i 1
ij j
 n

 xij  1, i
 j 1


   xij  S  1 S  1,..., n et 2  S  n  1
 iS jS

   xij  1 S  1,..., n et   S  1,..., n
 iS jS
 xij  0,1,  i,  j


La première contrainte dit qu’il entre exactement 1 fois dans chaque ville, tandis que la deuxième dit
qu’il sort exactement 1 fois de chaque ville. Ceci n’est pas suffisant, car on pourrait aboutir ainsi à
plusieurs petits tours, donc il reste à éliminer les sous-tours en mettant soit les troisièmes contraintes
(élimination de sous-tours) soit les quatrièmes contraintes (connexité).

10