Université Hassan II Année universitaire 2023/2024

FSJES Mohammedia Prof : Mustapha BASSOUR

Master : Développement Economique et Ingénierie des Programmes

Module : Recherche Opérationnelle et aide à la décision

Chapitre 2 : Méthode du simplexe et Dualité

1 Introduction
Nous avons résolu des cas de programmes linéaires simples : deux variables et trois ou quatre
contraintes. Au fur et à mesure que le nombre des contraintes s’accroı̂t, la méthode graphique
s’avère de plus en plus difficile à mettre en oeuvre. En présence de trois variables, nous devons faire
appel à une représentation graphique dans l’espace, exercice très délicat..., Or, dans la pratique,
les programmes linéaires comportent plusieurs dizaines de variables et de contraintes.
Ainsi, le recours à une méthode générale devient indispensable.

L’algorithme du simplexe est la plus utilisée des méthodes de résolution des programmes
linéaires. Il a été mis au point en 1948 par B. Dantzig.

2 Formes canonique et standard d’un programme linéaire :

2.1 Notion de formes canoniques :
Lorsque l’ensemble de contraintes se présente sous forme d’inégalités ( ≥ ou ≤ ) on parle de
forme canonique.
Toutefois, il convient de distinguer un programme canonique de type I d’un programme canonique
de type II.
ˆ Un programme canonique de type I est un programme dans lequel les contraintes inégalités
sont tournées dans le sens inférieur ou égal, l’objectif recherché étant la maximisation de
la fonction économique.

ˆ Un programme canonique de type II a des contraintes inégalités tournées dans le sens

supérieur ou égal, l’objectif recherché étant la minimisation de la fonction économique.

Exemple 2.1
max
 z = 1000x1 + 1500x2 min z = 10x1 + 6x2 + 8x3

 8x1 + 4x2 ≤ 160 
 4x1 + 6x2 ≤ 120  x1 + x2 + 2x3 ≥ 2


x1 ≤ 34 5x1 + 3x2 + 2x3 ≥ 1
x 2 ≤ 14 x1 , x2 , x3 ≥ 0

 


x1 , x2 ≥ 0


Forme canonique de type I Forme canonique de type II

2.2 Formes standard :

Un problème linéaire est sous forme standard si toutes les contraintes sont des contraintes
égalité. Pour transformer une contrainte d’inégalité en contrainte d’égalité, il faut ajouter aux

1
 Chapitre 2: Méthode du simplexe et Dualité

membres de gauche d’une contrainte, une quantité (une mesure) appelée variable d’écart qui sert
à absorber l’écart entre le membre gauche et le membre droit d’une contrainte si l’écart existe,
bien sûr, sinon cette variable vaut zéro.

tout programme se présentant sous forme canonique, doit être ramené sous la forme standard
avec introduction de variables d’écart selon le cas et selon les règles bien précises.

Exemple 2.2
Forme canonique d’un programme linéaire de maximisation :
max z = 50x1 + 60x2

 x1 + 2x2 ≤ 8

2x1 + 2x2 ≤ 10


 9x 1 + 4x2 ≤ 36
x1 , x2 ≥ 0


Forme standard correspondante :

max
 z = 50x1 + 60x2
 x1 + 2x2 + x3 = 8

2x1 + 2x2 + x4 = 10

 9x1 + 4x2 + x5 = 36

xi ≥ 0, i = 1, · · · , 5


La variable d’écart d’une contrainte représente la quantité disponible non utilisée. C’est l’écart
entre la disponibilité et le besoin.

2.3 Algorithme du simplexe : Méthode des tableaux

Principe : problème de maximisation

1. Dresser la forme canonique du problème posé ;

2. Passer de la forme canonique à la forme standard en transformant les inéquations en équations
et en introduisant les variables d’écart ;
3. Tableau initial : recherche de la solution extrême de base,
les variables d’écart sont considérées au départ comme variables principales ou variables dans
la base.
Les variables réelles sont non principales et se trouvent dans le hors base.
La fonction objectif est alors nulle.

Avec le tableau initial, on prépare le tableau N o 1 en choisissant respectivement la variable

entrante, sortante et le pivot :
ˆ La variable entrante correspondante au coefficient le plus élevé dans la fonction économique.
La colonne de la variable entrante prend alors le nom de colonne pivot.

ˆ La variable sortante correspondra au plus petit rapport positif issu de la division de la

colonne second-membre par la colonne variable-entrante. Cette variable sortante se lira dans
la base et sur la même ligne que le plus petit rapport positif.
Dans le cas ou le coefficient dans la colonne entrante est négatif, on ne le compte pas dans
le calcul du minimum.
La ligne de la variable sortante prend le nom de ligne pivot.
ˆ Le pivot se trouvera à l’intersection de la ligne pivot et de la colonne pivot.

2 Pr. Bassour
 Chapitre 2: Méthode du simplexe et Dualité

ä Il s’agira ensuite de rendre la colonne pivot unitaire, c-à-d, d’arriver à un pivot égal
à 1 et tous les autres éléments de la même colonne pivot égaux à zéro jusqu’à la fonction
économique(dernière ligne).
Chaque itération s’arrête dès que la colonne pivot est devenue unitaire.
ä Transformation de la ligne pivot : pour obtenir la ligne du pivot transformée, il suffit de diviser
tous ses éléments par le pivot.
ä On construit les différents tableaux jusqu’à ce que la fonction économique ne contienne plus
que des nombres négatifs ou nuls. Le pivot ne peut jamais être égal à zéro. Pour transformer les
autres éléments des autres lignes ou colonnes, on utilise la règle du rectangle.

Exemple 2.3
Une entreprise fabrique des vêtements pour femmes.
Les profits réalisés sont de 300 DH par robe et de 200 DH par chemise vendue.
En respectant les conditions suivantes :
3 On ne peut fabriquer plus de 80 items de vêtements par mois.
3 Il faut deux heures pour coudre une robe et une heure pour coudre une chemise, or la machine
à coudre n’est disponible que pendant cent heures par mois.
- Combien de robes et de chemises doit-elle vendre pour réaliser un profit maximum ?
Travail à faire :
1. formuler mathématiquement le problème.

2. Résoudre le programme linéaire par la méthode du simplexe.

Exemple 2.4
Une usine fabrique quatre produits P1, P2, P3 et P4.
La fabrication de chaque produit nécessite une certaine quantité de ressources. Les ressources
consommées, les stocks des ressources et les profits des produits sont récapitulés dans le tableau
suivant :
P1 P2 P3 P4 stock
ressource A 2 4 5 7 42
ressource B 1 1 2 2 17
ressource C 1 2 3 3 24
Profit par unité 7 9 18 17
On souhaite établir un plan de production de façon à maximiser le profit.

1. Formuler mathématiquement le problème.

2. Donner la forme standard du programme. Quelle est l’interprétation économique des
variables d’écart ?
3. Résoudre le programme linéaire par la méthode du simplexe.

4. Laquelle des contraintes est saturée par la solution trouvée et pourquoi ?

Exemple 2.5
Une société de jouets produit des trains, des camions et des voitures, en utilisant 3 machines M1,
M2 et M3.
Les disponibilités quotidiennes des 3 machines sont respectivement 430, 460 et 420 minutes.
Les bénéfices réalisés sont 30 Dh par train vendu, 20 Dh par camion vendu et 50 Dh par une
voiture vendue.
Les temps nécessaires sur chaque machine sont donnés dans le tableau suivant :

3 Pr. Bassour
 Chapitre 2: Méthode du simplexe et Dualité

Machine Train Camion Voiture

M1 1 2 1
M2 3 0 2
M3 1 4 0

La société souhaite établir un plan de production de façon à maximiser le profit.

1. Formuler mathématiquement le problème.

2. Donner la forme standard du programme. Quelle est l’interprétation économique des
variables d’écart ?
3. Résoudre le programme linéaire par la méthode du simplexe.

4. Laquelle des contraintes est saturée par la solution trouvée et pourquoi ?

Remarque 2.1
Lorsque plusieurs variables sont susceptibles d’entrer ou de sortir de la base, on choisit toujours
celle qui a l’indice le plus petit.

Remarque 2.2
pour résoudre un problème de minimisation, on utilise la dualité.

3 Dualité
La dualité est un concept important en recherche opérationnelle. Tout programme linéaire ad-
met un programme dual. Autrement dit, à tout problème de maximisation peut être associé un
problème de minimisation et à tout problème de minimisation peut être associé un problème de
maximisation. Le premier est appelé : primal, le second étant son dual.

Programme linéaire primal Programme linéaire dual

T
max
 z=c x min w = bT y
AT y ≥ c

Ax ≤ b
⇐⇒
x≥0 y≥0
Le fait d’avoir un problème vu selon deux angles différents (primal - dual) liés d’une certaine
manière, met en évidence la dépendance des solutions entre primal - dual. D’ailleurs on peut fa-
cilement trouver une solution de l’un à partir de la solution de l’autre.

Dualité forte : Si x et y sont solutions optimales du primal et dual alors les valeurs des
fonctions objectifs sont égales : cT x = bT y

3.1 Comment trouver le dual ?

Pour passer du primal au dual, certaines transformations doivent être considérées qui sont
définies comme suit :
1. Les termes du second membre des contraintes dans le problème primal deviennent
les coefficients de la nouvelle fonction économique du dual et les coefficients de la fonction
économique primal deviennent le second membre des contraintes du dual.

2. Les variables de décisions du problème primal deviennent des variables d’écarts dans le
problème dual et les variables d’écarts deviennent les variables de décisions.
3. Le problème de maximisation devient un problème de minimisation et le problème de
minimisation devient un problème de maximisation.

4 Pr. Bassour
 Chapitre 2: Méthode du simplexe et Dualité

4. Les inégalités d’infériorité deviennent des inégalités de supériorité et inversement.

5. La matrice A se transforme en sa transposée AT .( l’écriture en ligne devient l’écriture en
colonne).

3.2 Théorème des écarts complémentaires

Comment retrouver une solution d’un problème avec la solution de l’autre ?
Notons x∗ la solution optimale du primal et y ∗ la solution optimale du dual.
ˆ Si x∗j > 0, alors la j-ième contrainte du dual est saturée.
ˆ Si la j-ième contrainte du dual n’est pas saturée, alors x∗j = 0.
ˆ Si yi∗ > 0, alors la i-ième contrainte du primal est saturée.
ˆ Si la i-ième contrainte du primal n’est pas saturée, alors yi∗ = 0.

Exemple 3.1
Deux produits P1 et P2 fabriqués en quantité x1 et x2 , nécessitant trois ressources disponibles en
quantités données.(cf. tableau)
P1 P2 stock
ressource 1 3 9 270
ressource 2 4 5 360
ressource 3 2 1 20
bénéfice 60 40
L’entreprise cherche à maximiser le bénéfice total provenant de la vente des 2 produits.
Un acheteur se présente pour acheter toutes les ressources de l’entreprise. Il propose à l’entreprise
les prix unitaires y1 , y2 et y3 pour chacune des ressources. L’entreprise acceptera de lui vendre
toutes ses ressources uniquement si elle obtient pour chaque produit un prix de vente au moins
égal au profit qu’elle ferait en vendant ses produits.
De son côté, l’acheteur cherche à minimiser ses dépenses.
On note y1 , y2 et y3 les prix unitaires que l’acheteur doit proposer à l’entreprise pour qu’elle
accepte de vendre toutes ses ressources.

1. formuler mathématiquement le problème (programme primal).

2. Résoudre le programme linéaire par la méthode du simplexe.
3. Écrire le dual du programme primal.
4. Donner la solution optimale du programme dual.

Exercice 3.1
Résoudre les programmes linéaires suivants par la méthode du simplexe :
max z = 50x1 + 60x2

 x1 + 2x2 ≤ 8

2x1 + 2x2 ≤ 10


 9x 1 + 4x2 ≤ 36
x1 , x2 ≥ 0


max z = 1000x1 + 1500x2



 8x1 + 4x2 ≤ 160
 4x1 + 6x2 ≤ 120


x1 ≤ 34
x2 ≤ 14




x1 , x2 ≥ 0


5 Pr. Bassour
 Chapitre 2: Méthode du simplexe et Dualité

min z = 10x1 + 6x2 + 8x3

 x1 + x2 + 2x3 ≥ 2
5x1 + 3x2 + 2x3 ≥ 1
x1 , x2 , x3 ≥ 0


max z = 100x1 + 200x2 + 50x3


 5x1 + 5x2 + 10x3 ≤ 1000

10x1 + 8x2 + 5x3 ≤ 2000


 10x1 + 5x2 ≤ 500
x1 , x2 , x3 ≥ 0


Exercice 3.2
L’économe d’un établissement doit remplacer 300 chaises, 110 tables et 30 bureaux.
II s’adresse à deux entreprises qui proposent les lots suivants :
3 l’entreprise A propose des lots de 18 chaises, de 5 tables et 1 bureau pour un prix de 25000
DH par lot.
3 l’entreprise B propose des lots de 12 chaises, de 5 tables et 2 bureaux pour un prix de 30000
DH par lot.
Le but de l’exercice est de déterminer le nombre de lots que l’économe doit acheter à chaque entre-
prise pour réaliser une dépense minimale. On note x1 le nombre de lots achetés de l’entreprise
A et x2 le nombre de lots achetés de l’entreprise B.
1. formuler mathématiquement le problème (programme primal).
2. Écrire le dual du programme primal.

3. Résoudre le programme dual par la méthode du simplexe.

4. Déduire la solution optimale du programme primal.

Exercice 3.3
On peut acheter 4 types d’aliments, dont la teneur en glucides et lipides est donnée dans le tableau
suivant (par unité de poids et exprimé en unités convenables) :
type 1 type 2 type 3 type 4
glucides 2 1 0 1
lipides 3 4 3 0
prix (UM) 2 2 1 8
Le problème du consommateur consiste à obtenir la meilleure stratégie d’achat au moindre coût,
au moins 12 unités de glucides et 19 unités de lipides.

1. formuler mathématiquement le problème (programme primal).

2. Écrire le dual du programme primal.
3. Résoudre le programme dual par la méthode du simplexe.

4. Déduire la solution optimale du programme primal. interpréter les résultats.

Exercice 3.4
Un fabricant produit des chaises et des petites tables à partir d’un stock de 16 unités de bois, 10
unités de tissu et emploie un ouvrier qui fournit 40 heures de travail par semaine. Pour produire
une chaise il faut 1 heure de travail, une unité de bois et une unité de tissu ; tandis que pour une
table il faut 4 heures de travail et 1 unité de bois. Le prix d’une chaise est de 100 Unités-Monétaire
(UM) et celui d’une table de 200 UM. Le fabricant désire déterminer la production hebdomadaire
des chaises et des tables permettant de maximiser son chiffre d’affaires.
1. Donner la formulation mathématique, sous forme canonique, du programme primal.

6 Pr. Bassour
 Chapitre 2: Méthode du simplexe et Dualité

2. Donner la forme standard du programme. Quelle est la signification économique des variables
d’écart ?
3. Résoudre le programme primal par la méthode du simplexe. interpréter ces résultats.

Exercice 3.5
Soit (P ) le programme linéaire suivant :
min
 w = 50y1 + 20y2 + 30y3 + 80y4

 8y1 + 4y2 + 3y3 + 10y4 ≥ 10
 3y1 + 2y2 ≥ 6


y1 + y2 + 2y3 + 2y4 ≥ 5
2y1 + 4y2 + y3 + 5y4 ≥ 8




yi ≥ 0, i = 1, · · · , 4

¶ Donner (D) le dual du programme (P ).
· Résoudre (D) par l’algorithme du simplexe.
¸ Déduire la solution optimale du programme primal (P ).

7 Pr. Bassour