Programmation linéaire : Etude d’un exemple

RCP101 – Recherche opérationnelle et aide à la décision

Voici un cas pratique illustrant la mise en œuvre de la méthode du simplexe dans le cadre de la recherche
d'un maximum.

Une entreprise fabrique deux articles A et B à partir de trois facteurs de production P, Q et R (on peut
penser par exemple à, respectivement, des heures-machines, des heures-salariés et à des kilos de
matière première).

Le tableau ci-dessous indique le nombre d'unités de P, Q et R nécessaires pour fabriquer un article A ou

B, la marge unitaire en euros réalisée après la vente de chaque article, et les capacités journalières
maximales disponibles concernant les facteurs de production P, Q et R.

Facteur Facteur Facteur Marge

P Q R unitaire (€)
Pour un A 2 7 4 740
Pour un B 3 15 1 1 200
Capacités
46 215 52
journalières

Ainsi pour fabriquer un article A, il faut deux unités du facteur P, sept unités du facteur Q et quatre unités
du facteur R. Une fois commercialisé, cet article permettra de dégager une marge de 740 €.

On ne peut toutefois fabriquer par jour n'importe quel nombre d'articles A ou B car l'entreprise est limitée
par ses capacités de production : elle dispose au maximum, et par jour de 46 unités de P, 215 unités de Q
et de 52 unités de R.

L'objectif est le suivant :

Combien d'articles A et B faut-il fabriquer chaque jour pour rendre maximale la marge totale
journalière de l'entreprise, tout en respectant ses contraintes de production ?

Il faut bien se rendre compte que ce problème en est bien un : l’entreprise voudrait commercialiser
un nombre maximal d’objets, pourtant elle en est empêchée par des capacités de production
limitées. Il s’agira de trouver le meilleur compromis entre ces contraintes et l’objectif.

La méthode qui permet d'apporter une réponse à ce type de question se décompose comme suit :

1 - Détermination du programme linéaire associé au problème, avec en particulier la mise en évidence :

- des variables du problème

- des contraintes associées
- de la fonction économique à maximiser

2 - Résolution du programme linéaire à l'aide de la méthode du simplexe, présentée sous forme de

tableaux.

3 - Mise en forme concrète de la solution trouvée avec ses conséquences pour l'entreprise.
Dans ce qui suit, certaines explications concernant en particulier la détermination des tableaux successifs
n'ont qu'un caractère justificatif et doivent être omises lors de la réalisation d'un exercice ; il suffira, pour
l'examen en particulier, de produire :

- le programme linéaire,
- le système d'équations linéaires associé qu’on appellera le programme standard
- les tableaux menant à la solution,
- la solution et ses conséquences.

1 - Le programme linéaire

1.1 Les variables

Comme la question porte sur le nombre d'articles A et B à fabriquer, les variables associées au problème
sont :
x1 : le nombre d'articles A à fabriquer par jour.
x2 : le nombre d'articles B à fabriquer par jour.

Remarquons que ces quantités sont par définition positives ou nulles, donc non négatives.

Si, à la fin, la solution comporte une variable nulle, cela signifiera simplement qu'il faut déconseiller à
l'entreprise la fabrication de l'article qui correspond à la variable en question.
D'autres variables, elles aussi positives ou nulles, apparaîtront lors de la mise en œuvre de la méthode du
simplexe. Elles seront notées, comme les précédentes par la lettre x pourvue d'indices entiers non
encore utilisés. Il faut donc systématiquement noter les variables de départ par x1 , x2 , ... (et non pas par
x, y, ... ou a, b, ...) afin d'homogénéiser les notations.

Finalement nous avons : x1 ≥ 0 ; x2 ≥ 0 .

1.2 Les contraintes

Il s'agit maintenant de traduire, avec les variables précédentes, le fait que l'entreprise est limitée dans ses
capacités quotidiennes de fabrication.

Ici les contraintes sont au nombre de trois : on ne peut pas dépasser par jour la mobilisation de :

46 unités de P
215 unités de Q
52 unités de R

Considérons par exemple le facteur P. Un article A nécessite 2 unités de P, donc x1 articles A

nécessiteront 2x1 unités de P.
De même un article B nécessite 3 unités de P, donc x2 articles B nécessiteront 3x2 unités de P.

En tout, il faudra donc mobiliser, pour la fabrication des A et des B, 2 x1 + 3 x2 unités de P. C'est cette
quantité qui ne doit pas dépasser 46 unités.

La première contrainte s'écrit dons sous la forme de l'inéquation : 2 x1 + 3 x2 ≤ 46

2
On a de même, pour le facteur Q : 7 x1 + 15 x2 ≤ 215

Et enfin pour le facteur R : 4 x1 + x2 ≤ 52

1.3 La fonction économique

L'objectif est de rendre maximale la marge totale dégagée par la fabrication

et la vente de x1 articles A et de x2 articles B.

Comme un article A rapporte 740 €, x1 articles A rapporteront 740x1 € ; de même, un article B rapportant
1 200 €, ce sont 1200x2 € que rapporteront x2 articles B.

La marge totale quotidienne dégagée par x1 articles A et x2 articles B, notée z , s'écrit donc :

z = 740 x1 + 1200 x2

Il s'agira dès lors de rechercher la valeur maximale de cette fonction de deux variables, ce que nous
noterons :

Max(740 x1 + 1200 x2 )

En résumé, le programme linéaire associé au problème posé est :

x1 ≥ 0 ; x2 ≥ 0
2 x1 + 3x2 ≤ 46
7 x1 + 15 x2 ≤ 215
4 x1 + x2 ≤ 52
Max ( 740 x1 + 1200 x2 )

2 - La méthode du simplexe

2.1 Les variables d'écart

Comme il est difficile, mathématiquement, de traiter des inéquations, nous allons dans un premier temps
les transformer en équations.

Considérons, par exemple, la première contrainte : 2 x1 + 3 x2 ≤ 46

La quantité 2 x1 + 3 x2 qui représente le premier membre de cette inéquation peut atteindre la valeur 46,
qui représente son second membre, à condition de lui ajouter une quantité inconnue (pour l’instant), et
que nous noterons x3 .
Cette nouvelle quantité représente alors l'écart qui existe entre 2 x1 + 3 x2 et 46 . De ce fait x3 est positive
ou nulle.

3
Cette variablex3 a une signification concrète : c'est le nombre d'unités du facteur P qui resteront
disponibles à la fin de la journée une fois fabriquées x1 unités de A et x2 unités de B.

A la première contrainte, nous associons donc l'équation : 2 x1 + 3x2 + x3 = 46

De même, aux deux autres contraintes, nous associons les équations suivantes :

7 x1 + 15 x2 + x4 = 215

4 x1 + x2 + x5 = 52

Les variables d'écart x3 , x4 et x5 n'ayant à priori aucune raison d'être égales sont bien entendu notées
de manière différente.

Ces nouvelles variables peuvent également figurer dans l'expression de la fonction économique, avec
évidemment des facteurs nuls, puisqu'elles ne participent pas au calcul de la valeur de la marge totale.
On écrira ainsi, également sous la forme d’une équation du même type que les précédentes

740 x1 + 1200 x2 + 0 x3 + 0 x4 + 0 x5 = z :

Finalement, le programme linéaire initial est remplacé par le programme suivant, appelé programme
standard :

x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0 ; x4 ≥ 0 ; x5 ≥ 0
2 x1 + 3x2 + x3 = 46
7 x1 + 15 x2 + x4 = 215
4 x1 + x2 + x5 = 52
740 x1 + 1200 x2 + 0 x3 + 0 x4 + 0 x5 = z
Max ( z )

Notons qu'en plus des équations figurent les contraintes de positivité (ou de nullité) de chacune des
variables, sur lesquelles, on le verra, repose la méthode, ainsi que le rappel de l'objectif : la maximisation
de la valeur de la fonction économique.

4
2.2 Le premier tableau

Pour la commodité et l'automaticité des calculs, nous allons remplacer le système d'équations précédent
par un tableau où ne figureront que les coefficients des variables :

1 2 3 4 5 C
2 3 1 0 0 46
7 15 0 1 0 215
4 1 0 0 1 52
Max 740 1200 0 0 0 z

En faisant dans un premier temps abstraction de la première colonne et de la dernière colonne, nous
reconnaissons les quatre équations du programme standard par l'intermédiaire des coefficients des
variables qui y figurent et par leurs seconds membres repérés par C (comme "constant").

Ainsi, à la première ligne, les nombres 2, 3, 1, 0, 0 et 46 aux colonnes 1, 2, 3, 4, 5 et C représentent

l'équation :

2 x1 + 3x2 + x3 = 46

Les repères verticaux 1, 2, 3, 4 et 5 des colonnes servent donc à marquer implicitement la présence des
variables x1 , x2 , x3 , x4 et x5 dans une équation.

La dernière ligne du tableau, séparée des précédentes, car de nature différente, n'est autre que l'équation
qui correspond à la fonction économique :

740 x1 + 1200 x2 + 0 x3 + 0 x4 + 0 x5 = z

Venons-en maintenant à la première colonne, tout à fait à gauche, du tableau. Elle sert à indiquer une
solution évidente du système d'équations, dite solution de base.

En effet, si l'on se reporte au programme standard, il est facile de voir que :

 x1 = 0
x = 0
 2
 x3 = 46
 x = 215
 4
 x5 = 52

constitue une solution particulièrement simple de ce système, solution qui respecte les contraintes de
positivité imposées aux variables.

On va donc associer les numéros des variables 3, 4 et 5 aux nombres 46, 215 et 52 de la colonne repérée
par C, en faisant figurer ces numéros dans la première colonne du tableau.

5
Les indices (variables) qui figurent dans cette première colonne sont les variables de base ; elles
sont égales aux seconds membres de la colonne C lorsque les variables qui ne sont pas de base
sont égales à 0.

Bien entendu, cette solution n'est pas économiquement satisfaisante car avec ces valeurs on a z=0 :

740 × 0 + 1200 × 0 + 0 × 46 + 0 × 215 + 0 × 52 = 0

Le premier tableau complété de sa première colonne est alors :

1 2 3 4 5 C
3 2 3 1 0 0 46
4 7 15 0 1 0 215
5 4 1 0 0 1 52
Max 740 1200 0 0 0 z

La méthode va consister maintenant à rechercher une autre solution qui augmente la valeur de z (qui
fasse passer z de la valeur 0 à une valeur strictement positive).

On s'arrêtera dès qu'il ne sera plus possible d'augmenter z qui aura alors atteint sa valeur maximale.

2.3 Choix d'une nouvelle variable de base

On l'a vu, la solution initiale, dite de base, comportait, entre autres, les valeurs x1 = 0 et x2 = 0 , ce qui
donnait z = 0.

Pour obtenir une nouvelle valeur de z strictement positive, donc en augmentation, il faut que l'une des
deux variables x1 ou x2 devienne non nulle, c'est à dire devienne une variable de base, ce qui fait que
l'une des trois variables x3 , x4 ou x5 , initialement de base, sortira de la base pour être nulle à son tour.

Comment alors choisir entre x1 et x2 celle qui entrera dans la base (car malheureusement nous ne
connaissons pas de méthode permettant d’augmenter simultanément ces deux variables) ?

Comment déterminer ensuite laquelle parmi x3 , x4 et x5 deviendra nulle en sortant de la base ?

La réponse à la première question est simple : on considère dans le tableau initial le plus fort coefficient
positif figurant dans la ligne de la fonction économique (la dernière ligne donc). C'est ici 1 200, valeur qui
est le coefficient de la variable x2 dans l'expression de z. On espère ainsi parvenir plus vite à la valeur
maximum de z en rendant cette variable strictement positive.

Pratiquement, cette opération se fait en soulignant dans le tableau initial le coefficient le plus élevé
qui figure à la dernière ligne.

Nous savons désormais que c'est x2 qui va devenir non nulle, donc nouvelle variable de base, tandis
qu'évidemment x1 reste une variable hors base donc nulle.

6
Le premier tableau est maintenant :

1 2 3 4 5 C
3 2 3 1 0 0 46
4 7 15 0 1 0 215
5 4 1 0 0 1 52
Max 740 1200 0 0 0 z

Notre but étant d'augmenter z le plus fortement, nous voulons attribuer à x2 la plus forte valeur strictement
positive. Mais cela doit se faire en respectant les contraintes de positivité des autres variables.

Si l'on reprend le système initial de la page 4 avec x1 = 0 , on a :

3x2 + x3 = 46

15 x2 + x4 = 215
 x + x = 52
 2 5

Vouloir conserver x3 ≥ 0 ; x4 ≥ 0 ; x5 ≥ 0 , c'est donc chercher x2 telle que :

46 − 3x2 ≥ 0

215 − 15 x2 ≥ 0
52 − x ≥ 0
 2

C'est à dire telle que, à la fois :

 46
 x2 ≤ 3
  x2 ≤ 15,3
 215 
 x2 ≤ c’est-à-dire  x2 ≤ 14,3
 15  x ≤ 52
 52  2
 x2 ≤ 1


215
Il suffit donc de considérer x2 = , la plus petite des trois divisions, pour satisfaire à la fois ces trois
15
inégalités et pour attribuer à x2 la plus forte valeur possible.

215
Cela entraîne x4 = 0 : 15 × + x4 = 215 implique x4 = 0
15

C'est cette dernière variable qui va donc sortir de la base pour laisser la place à x2 .

7
Pratiquement, on procède à partir du tableau initial, de la manière suivante :

- On fait figurer dans la dernière colonne repérée R (comme "Rapport") les quantités "second
membre divisé par coefficient de la variable qui entre dans la base".

- On choisit, en le soulignant, le plus petit des rapports positifs de la colonne R.

Le tableau ci-dessous, qui est encore le tableau initial, comporte les manipulations décrites plus haut :

1 2 3 4 5 C R
3 2 3 1 0 0 46 46/3
4 7 15 0 1 0 215 215/15
5 4 1 0 0 1 52 52/1
Max 740 1200 0 0 0 z

Avant de continuer, fixons une terminologie qui sera utile pour la suite :

- La colonne 2 est ici la colonne de la variable entrante (à cause du plus fort coefficient positif
1200). On dit aussi que c'est la colonne du pivot.

- La deuxième ligne du tableau, repérée par la variable de base 4 est la ligne de la variable
sortante (à cause du plus petit rapport positif 215/15). On dit aussi que c'est la ligne du pivot.

- La quantité située à l'intersection de la colonne du pivot et de la ligne du pivot est le pivot. Ici
c'est le nombre 15, qu'on souligne également.

2.4 Le deuxième tableau

Il se présente, avant tout calcul, comme ci-dessous, puisque la variable 2 a remplacé la variable 4 dans la
liste des variables de base :

1 2 3 4 5 C R
3
2
5
Max

Les calculs qui vont suivre ont pour but de tirer les conséquences du fait que 3, 2 et 5 sont nos nouvelles
variables de base.

8
On peut constater, en observant le tableau initial qu'une variable de base a pour particularité de n'être
présente que dans l'équation où elle figure et avec un coefficient égal à 1.

Il faut donc, avec des manipulations d'équations telles que des combinaisons linéaires, de manière à
ne pas modifier l'ensemble des solutions du système, obtenir un second tableau de type suivant :

1 2 3 4 5 C R
3 0
2 1
5 0
Max 0

Puisque la variable 2 est la nouvelle variable de base, les formules de transformation des lignes du
tableau initial sont les suivantes :

1. Pour faire apparaître un coefficient 1 en bonne place à la place du pivot, la ligne du pivot L pivot est
divisée par le pivot. Ce qui se traduit par la transformation suivante :

1
L pivot → × L pivot
pivot

La flèche → voulant dire « se transforme en … ».

2 – Pour obtenir des 0 ailleurs sur la précédente colonne du pivot chaque ligne Li , autre que la ligne
du pivot (donc L1 , L3 et L4 , la première, troisième et quatrième ligne du tableau précédent) est
transformée, pour figurer dans le nouveau tableau de la manière suivante :

a
Li → Li − × L pivot
pivot

où a est le coefficient situé sur la ligne à transformer et sur la colonne du pivot

On doit donc à partir du tableau initial effectuer les transformations suivantes, en rappelant qu’ici L2 est la
ligne du pivot :

3
L1 → L1 − × L2
15
1
L2 → × L2
15
1
L3 → L3 − × L2
15
1200
L4 → L4 − × L2
15

9
Examinons par exemple le détail des calculs qui mène à la nouvelle première ligne L1 . Ici le nombre a
présent sur cette ligne et sur la colonne du pivot est 3 :

3 9 3
2 devient 2 − ×7 = =
15 15 5

3
3 devient 3 − × 15 = 0
15

3
1 devient 1 − ×0 =1
15

3 1
0 devient 0 − ×1 = −
15 5

3
0 devient 0 − ×0 = 0
15

3
46 devient 46 − × 215 = 3
15

La colonne R qui ne concerne que la recherche de la variable sortante n'est pas touchée par ces calculs et
devient à nouveau vide.

Le lecteur pourra vérifier que le nouveau tableau est :

1 2 3 4 5 C R
3 3/5 0 1 − 1/5 0 3
2 7/15 1 0 1/15 0 43/3
5 53/15 0 0 − 1/15 1 113/3
Max 180 0 0 − 80 0 z − 17200

Remarquons que ces transformations conservent aux variables 3 et 5 leur statut de variable de base
puisqu’on a en définitive un tableau formé à partir de l’armature suivante :

1 2 3 4 5 C R
3 0 1 0
2 1 0 0
5 0 0 1
Max 0 0 0

Le deuxième tableau s'interprète, comme on l'a vu, de la manière suivante :

43 113
lorsque x1 = x4 = 0 (variables hors base) on x3 = 3 , x2 = et x5 = (variables de base)
3 3

10
Et avec ces valeurs :

43 113
180 × 0 + 0 × + 0 × 3 − 80 × 0 + 0 × = z − 17200
3 3
ce qui signifie z = 17200 .

On le voit, la nouvelle valeur de la fonction économique qui correspond à cette nouvelle solution se
lit après le signe moins qui suit la lettre z à la dernière ligne du deuxième tableau.

Il est très important lorsqu'on mène ces calculs de laisser les résultats sous forme fractionnaire et
donc de ne pas calculer une valeur approchée des nombres trouvés sous peine de fausser le
résultat final.

2.5 Le troisième tableau

On procède à partir du deuxième tableau de la même façon que précédemment :

- On souligne le plus fort coefficient positif de la dernière ligne.

- On calcule les rapports de la colonne R.
- On souligne le plus petit des rapports positifs.
- On souligne le pivot à l'intersection de la colonne de la variable entrante et de la ligne de la
variable sortante.

Tout ceci donne :

1 2 3 4 5 C R
3 3/5 0 1 − 1/5 0 3 5
2 7/15 1 0 1/15 0 43/3 215/7
5 53/15 0 0 − 1/15 1 113/3 565/53
Max 180 0 0 − 80 0 z − 17200

C'est la variable x1 qui va entrer dans la base et x3 qui va en sortir.

Les transformations des lignes menant au troisième tableau sont :

1 5
L1 → × L1 c’est-à-dire L1 → × L1 (ligne du pivot)
3 3
5

7
7
L2 → L2 − 15 × L1 c’est-à-dire L2 → L2 − × L1
3 9
5

11
 53
53
L3 → L3 − 15 × L1 c’est-à-dire L3 → L3 − × L1
3 9
5

180
L4 → L4 − × L1 c’est-à-dire L4 → L4 − 300 L1
3
5

En effectuant les calculs, le tableau obtenu est :

1 2 3 4 5 C R
1 1 0 5/3 − 1/3 0 5
2 0 1 − 7/9 2/9 0 12
5 0 0 − 53/9 10/9 1 20
Max 0 0 − 300 − 20 0 z − 18100

Ce tableau a pour particularité de ne plus comporter de coefficient strictement positif à la dernière ligne.
On ne peut donc plus augmenter la valeur de la fonction économique. Son maximum est atteint, et
avec lui la solution du problème.

Remarquons que désormais les coefficients des variables présents dans le corps du tableau sont inutiles
puisqu’on a obtenu le dernier tableau.

Dans la pratique on calcule d’abord pour chaque nouveau tableau la dernière ligne, celle de la
fonction économique ;

- si ses coefficients sont tous négatifs ou nuls, on a atteint le dernier tableau et il suffit pour
obtenir la solution de calculer uniquement les seconds membres de la colonne C,

- sinon on a obtenu un tableau intermédiaire qu’il faudra remplir intégralement.

2.5 Solution et conséquences

De manière maintenant habituelle, on lit pour ce dernier tableau la solution cherchée :

x1 = 5 objets A (variable de base)

x2 = 12 objets B (variable de base)
x3 = 0 unité de P disponible (variable hors base)
x4 = 0 unité de Q disponible (variable hors base)
x5 = 20 unités de R encore disponibles (variable de base)

La marge totale maximale obtenue en fabriquant 5 objets A et 12 objets B est dans ce cas z = 18100 €.

On le voit, la méthode permet d'une part de trouver les quantités inconnues x1 et x2 ainsi que la valeur
maximale de la fonction économique, et d'autre part, les nombres d'unités des facteurs de production
encore disponibles. Ce qui présente un certain intérêt pour l'entreprise (affectation de ces reliquats à
d'autres activités par exemple).

12