Chapter2:

Programmation linéaire

E. Ali1

1
LERSTAD
Université Gaston Berger de Saint-Louis, Sénégal
Cours de Recherche Opérationnelle

Ecole Superieur MIT, Août 2019

1 / 59
Outline
1 Introduction
2 Forme d’un programme linéaire
Forme générale
Forme standard ou forme canonique d’un programme linéaire
3 Résolution de programmes linéaires
Résolution graphique
La méthode du simplexe :
Rśolution par Tableaux de simplexe
4 Dualité
Exemple : Problème de production
Qu’est ce que la dualité ?
Comment trouver le dual ?
Conditions d’optimalité primal-dual
Exemple :

2 / 59
 Introduction

Sommaire
1 Introduction
2 Forme d’un programme linéaire
Forme générale
Forme standard ou forme canonique d’un programme linéaire
3 Résolution de programmes linéaires
Résolution graphique
La méthode du simplexe :
Rśolution par Tableaux de simplexe
4 Dualité
Exemple : Problème de production
Qu’est ce que la dualité ?
Comment trouver le dual ?
Conditions d’optimalité primal-dual
Exemple :

3 / 59
Introduction

En mathématiques, les problèmes de programmation linéaire (PL) sont

des problèmes d’optimisation où la fonction objective et les contraintes
sont toutes linéaires.

4 / 59
 Forme d’un programme linéaire

Sommaire
1 Introduction
2 Forme d’un programme linéaire
Forme générale
Forme standard ou forme canonique d’un programme linéaire
3 Résolution de programmes linéaires
Résolution graphique
La méthode du simplexe :
Rśolution par Tableaux de simplexe
4 Dualité
Exemple : Problème de production
Qu’est ce que la dualité ?
Comment trouver le dual ?
Conditions d’optimalité primal-dual
Exemple :

5 / 59
Forme d’un programme linéaire
Forme générale

La forme générale d’un problème d’optimisation est la suivante :

Maximiser f (x ) ou Minimiser f (x )
sous
gi (x ) = 0, i ∈ I 0 contrainte égalité
gi (x ) ≤ 0, i ∈ I − contrainte inégalité
gi (x ) ≥ 0, i ∈ I + contrainte inégalité
T
x = [x1 , · · · , xn ] ≥ 0
D’une manière plus détaillée, un programme linéaire (PL) est dit
sous forme générale s’il s’écrit de la façon suivante :
maxF = c1 x1 + c2 x2 + · · · + cn xn (1)

6 / 59
Forme d’un programme linéaire
Forme générale

La fonction (1) peut s’exprimer par une sommation de n terme (variable)

comme suit :
Xn
maxF = cj xj (2)
j=1

Sous les contraintes : Pn 

j=1 arj xj= br 

ou


Pn 
a x
j=1 ij j ≥ bi (3)
ou


Pn 

a x ≤ bk

j=1 kj j

7 / 59
Forme d’un programme linéaire
Forme standard ou forme canonique d’un programme linéaire

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 égalité, il
faut ajouter aux 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.
La forme standard peut être donné par la forme suivante :

maxZ = CX (4)

sous 
AX = b α
X ≥0 β

8 / 59
Forme d’un programme linéaire
Forme standard ou forme canonique d’un programme linéaire

Cette forme standard est obtenue en introduisant des variables d’écart

dans toutes les contraintes d’égalité (α) et que ces variables soient non
négatives (β)
La forme canonique d’un programme linéaire peut être exprimée par un
ensemble de vecteurs comme suit :

 X = (x1 , x2 , · · · , xn ) ∈ Rn
c = (c1 , c2 , · · · , cn ) ∈ Rn
b = (b1 , b2 , · · · , bn ) ∈ Rn


Et la matrice A de taille m × n
 
a11 a12 ··· a1n
A =  ... .. .. (5)
 
. . 
am1 am2 ··· amn

9 / 59
Forme d’un programme linéaire
Forme standard ou forme canonique d’un programme linéaire

avec :
n = nombre de variables,
m = nombre de contraintes,
X = vecteur des variables de décision
A = matrice réelle m × n ( matrice des contraintes )
c = [c1 , · · · , cn ] = vecteur- ligne des couts,
>
b = [b1 , · · · , bm ] = vecteur-colonne des seconds membres
Z=CX est la fonction objective, ou critère à minimiser.

10 / 59
Forme d’un programme linéaire
Forme standard ou forme canonique d’un programme linéaire

Exemple : Reprenons l’exemple du problème de production de

l’introduction. sous forme standard ( en introduisant des variables
d’écart), le PL s’écrit :

maxF = 600x1 + 400x2

Sous 

 3x1 + 9x2 + x3 = 81
4x1 + 5x2 + x4 = 55


 2x 1 + x2 + x5 = 20
x1 , x2 , x3 , x4 , x5 ≥ 0


11 / 59
Forme d’un programme linéaire
Forme standard ou forme canonique d’un programme linéaire

Pour cet exemple

Le vecteur de variables dans le systm̀es est : X = (x1 , x2 , x3 , x4 , x5 )
Le vecteur de coefficients C est donnée par C (600, 400, 0, 0, 0)
puisque max F peut s’écrire comme suit

maxF = 600x1 + 400x2 + 0x3 + 0x4 + 0x5

Le vecteur de coefficients b est donné par b = (81, 55, 20)

La matrice A  
3 9 1 0 0
A = 4 5 0 1 0 (6)
2 1 0 0 1

12 / 59
 Résolution de programmes linéaires

Sommaire
1 Introduction
2 Forme d’un programme linéaire
Forme générale
Forme standard ou forme canonique d’un programme linéaire
3 Résolution de programmes linéaires
Résolution graphique
La méthode du simplexe :
Rśolution par Tableaux de simplexe
4 Dualité
Exemple : Problème de production
Qu’est ce que la dualité ?
Comment trouver le dual ?
Conditions d’optimalité primal-dual
Exemple :

13 / 59
Résolution de programmes linéaires

Il existe plusieurs techniques de résolution pour les programmes lináires.

Cela dit nous présenterons dans cette section :
la résolution graphique et la résolution analytique en détaillant deux
procédures : méthodes Simplexe et tableaux Simplexe

14 / 59
Résolution de programmes linéaires
Résolution graphique

La résolution graphique d’un problème linéaire consiste à tracer la

droite qui sépare les demi-plans pour chaque contrainte tout en
conservant le demi-plan acceptable, c’est-à dire le demi-plan des
solutions réalisables pour la contrainte.
L’intersection des différents demi-plans de toutes les contraintes sans
oublier les contraintes de positivité forme le polygone des solutions,
appelé aussi "région des solutions admissibles".
Exemples : soit le problème suivant :

max Z = 600x1 + 400x2 (7)

Sous les contraintes 

 4x1 + 5x2 ≤ 55

x + 3x ≤ 27
1 2
(8)


 2x 1 + x 2 ≤ 20
x1 , x2 ≥ 0


15 / 59
Résolution de programmes linéaires
Résolution graphique

Le problème possède trois contraintes plus la contrainte de

positivité. On commence à tracer chaque contrainte séparément.

4x1 + 5x2 ≤ 55

On prend la première contrainte du système et on remplace

l’inégalité par une égalité sans l’ajout de variable d’écart, (cette
façon de faire est applicable seulement pour la résolution graphique).
L’équation résultante correspond à une droite.
Pour tracer une droite, il faudrait déterminer deux points, ce qui
donne pour la première contrainte notre exemple :

4x1 + 5x2 = 55

16 / 59
Résolution de programmes linéaires
Résolution graphique

Si x1 = 0 ⇒ x2 = 11 le premier point est (x1 , x2 ) = (0, 11)

Si x2 = 0 ⇒ x1 = 55 4 = 13.75 le deuxième point est
(x1 , x2 ) = (13.75, 0)
à partir de ces points on trace la première droite et on conserve ce qui est
en dessus de la droite. On élimine ensuite la partie supérieure puisque la
contrainte est une contrainte d’infériorité.

17 / 59
Résolution de programmes linéaires
Résolution graphique

Figure 1: Représentation de la première contrainte.

18 / 59
Résolution de programmes linéaires
Résolution graphique

Ainsi, on applique le même principe pour toutes les contraintes du

système :
x1 + 3x2 = 27

Si x1 = 0 ⇒ x2 = 9 le premier point est (x1 , x2 ) = (0, 9)

Si x2 = 0 ⇒ x1 = 27 le deuxième point est (x1 , x2 ) = (27, 0)
2x1 + x2 = 20

Si x1 = 0 ⇒ x2 = 20 le premier point est (x1 , x2 ) = (0, 20)

Si x2 = 0 ⇒ x1 = 10 le deuxième point est (x1 , x2 ) = (10, 0)
Bien évidemment, il faut tracer aussi les contraintes de positivité.
L’intersection de toutes les contraintes forme le polygone de solutions tel
qu’il est donné par la figure2

19 / 59
Résolution de programmes linéaires
Résolution graphique

Figure 2: Représentation des différentes contraintes.

20 / 59
Résolution de programmes linéaires
Résolution graphique

La question qui se pose maintenant est :quel est le point qui donne
la valeur optimale pour ce problème ?

21 / 59
Résolution de programmes linéaires
Résolution graphique

La question qui se pose maintenant est :quel est le point qui donne
la valeur optimale pour ce problème ?
Pour répondre à cette question nous expliquerons la procédure à
suivre pour déterminer la valeur maximale pour ce problème qui
consiste à tracer la droite qui correspond à la fonction objective.

21 / 59
Résolution de programmes linéaires
Résolution graphique

La question qui se pose maintenant est :quel est le point qui donne
la valeur optimale pour ce problème ?
Pour répondre à cette question nous expliquerons la procédure à
suivre pour déterminer la valeur maximale pour ce problème qui
consiste à tracer la droite qui correspond à la fonction objective.
Tout d’abord, on prend l’équation de la fonction objective et on lui
attribue la valeur zéro puisque c’est la plus petite valeur pour la
fonction objective. Ce qui donne pour cet exemple :

400x1 + 600x2 = 0

⇒ 4x1 = −6x2 ⇒ x1 = −1.5x2

21 / 59
Résolution de programmes linéaires
Résolution graphique

La question qui se pose maintenant est :quel est le point qui donne
la valeur optimale pour ce problème ?
Pour répondre à cette question nous expliquerons la procédure à
suivre pour déterminer la valeur maximale pour ce problème qui
consiste à tracer la droite qui correspond à la fonction objective.
Tout d’abord, on prend l’équation de la fonction objective et on lui
attribue la valeur zéro puisque c’est la plus petite valeur pour la
fonction objective. Ce qui donne pour cet exemple :

400x1 + 600x2 = 0

⇒ 4x1 = −6x2 ⇒ x1 = −1.5x2

Le coefficient directeur de cette fonction est (-1, 1.5). Il passe par
l’origine (0, 0).

21 / 59
Résolution de programmes linéaires
Résolution graphique

Une fois la droite tracée on effectue une translation parallèle à la

direction de la droite du bas vers le haut jusqu’à rencontrer le dernier
point du polygone satisfaisant les contraintes.

Figure 3: Résolution graphique du problème de production

22 / 59
Résolution de programmes linéaires
Résolution graphique

Le maximum de Z sur cet ensemble de contraintes est alors atteint.

On obtient ainsi le point qui correspond à la solution optimale.

23 / 59
Résolution de programmes linéaires
Résolution graphique

Le maximum de Z sur cet ensemble de contraintes est alors atteint.

On obtient ainsi le point qui correspond à la solution optimale.
Par la projection de ce point sur les axes x1 et x2 on obtient :
x1 = 7.5 et x2 = 5, ce qui donne une valeur maximale Z = 6500.
La méthode graphique pour la résolution d’un problème linéaire à
deux variables est très facile à appliquer. Sa difficulté augmente par
l’augmentation des variables dans le système.
Elle devient difficile pour trois variables et, voire impossible, au delà
de trois inconnus dans le système étudié.
Afin d’ôter cette difficulté, une méthode appelée méthode du
simplexe a été proposée et développée par Dantzig afin de résoudre
des problèmes de programmation linéaire avec plusieurs variables.

23 / 59
Résolution de programmes linéaires
La méthode du simplexe :

La méthodologie proposée pour cette technique consiste à visiter

tous les états possibles dans un système en partant d’un sommet
vers un sommet adjacent de manière à réviser et améliorer la
fonction objective. Pour ce faire, nous procédons à l’exploration des
différentes démarches selon l’ordre de priorité donné ci dessous :

24 / 59
Résolution de programmes linéaires
La méthode du simplexe :

La méthodologie proposée pour cette technique consiste à visiter

tous les états possibles dans un système en partant d’un sommet
vers un sommet adjacent de manière à réviser et améliorer la
fonction objective. Pour ce faire, nous procédons à l’exploration des
différentes démarches selon l’ordre de priorité donné ci dessous :
Démarche 1 : On démarre l’application de l’approche (méthode du
simplexe) par la transformation des contraintes d’inégalité en
contraintes d’égalité en ajoutant les variables d’écart.

24 / 59
Résolution de programmes linéaires
La méthode du simplexe :

La méthodologie proposée pour cette technique consiste à visiter

tous les états possibles dans un système en partant d’un sommet
vers un sommet adjacent de manière à réviser et améliorer la
fonction objective. Pour ce faire, nous procédons à l’exploration des
différentes démarches selon l’ordre de priorité donné ci dessous :
Démarche 1 : On démarre l’application de l’approche (méthode du
simplexe) par la transformation des contraintes d’inégalité en
contraintes d’égalité en ajoutant les variables d’écart.
Démarche 2 : Dans un second temps nous sélectionnons les
variables originales comme variables hors-base et les variables
d’écarts comme variable basique. puis nous effectuerons une
permutation entre une variable hors-base de notre choix qui sera
remplacée par une variable de base (entrante). Le choix de la
variable entrante repose sur la variable dont le coefficient est le plus
élevé dans la fonction objective.

24 / 59
Résolution de programmes linéaires
La méthode du simplexe :

Démarche 3 : La variable sortante est la première à s’annuler. On

répète le processus jusqu’à ce que tous les coefficients de fonction
objective soient négatifs ou nuls. Dans ce cas, on arrê ete et la
solution optimale est trouvée.
Exemple : Considérons le problème suivant :
MaxF = 40y1 + 60y2
Sous les contraintes
2y1 + y2 ≤ 70 (9)
y1 + y2 ≤ 40 (10)
y1 + 3y2 ≤ 90 (11)
y1 ≥ 0
y2 ≥ 0

25 / 59
Résolution de programmes linéaires
La méthode du simplexe :

Solution
Soit y3 , y4 et y5 , les variables d’écart relatif respectivement aux
contraintes 9,10 et 11, qui permettent de transformer les contraintes
d’inégalité pour obtenir les égalités suivantes :

2y1 + y2 + y3 = 70 (12)

y1 + y2 + y4 = 40 (13)
y1 + 3y2 + y5 = 90 (14)
On commence à partir du point y1 = 0, y2 = 0 et on vérifie s’il est
possible d’augmenter la fonction objective sachant que notre système est
un système de trois équations avec cinq inconnues.
Pour trouver la solution on impose deux des variables à zéro et on déduit
les valeurs des trois variables restantes.

26 / 59
Résolution de programmes linéaires
La méthode du simplexe :

Ce qui donne :
y1 = 0,
y2 = 0
Pour les variables de base et :

y3 = 70

y4 = 40
y5 = 90
Pour les variables hors base.
Et la valeur de la fonction objective F = 40y1 + 60y2 = 0,
La question qui se pose est :Est-il possible d’augmenter F

27 / 59
Résolution de programmes linéaires
La méthode du simplexe :

Pour répondre à cette question, on vérifie la fonction objective. Si

les coefficients sont positifs, ce qui est le cas, on a donc la possibilité
d’augmenter F.
On favorise l’augmentation de la variable qui a le plus grand
coefficient dans la fonction objective.
Donc on choisit y2 en maintenant y1 = 0.
On remplace y1 = 0 dans les équation 12,13 et 14

2y1 + y2 + y3 = 70 ⇒ y2 + y3 = 70 (15)
y1 + y2 + y4 = 40 ⇒ y2 + y4 = 40 (16)
y1 + 3y2 + y5 = 90 ⇒ 3y2 + y5 = 90 (17)
On réécrit les variables restantes en fonction de y2 pour chaque
équation. Ce qui nous donne :

28 / 59
Résolution de programmes linéaires
La méthode du simplexe :

y3 = 70 − y2 ≥ 0 ⇒ y2 ≤ 70 (18)
y4 = 40 − y 2 ≥ 0 ⇒ y 2 ≤ 40 (19)
y 5 = 90 − 3y 2 ≥ 0 ⇒ y 2 ≤ 30 (20)

On peut augmenter la valeur de y2 au maximum à 30 puisque c’est

la valeur qui permet de satisfaire les équations 18, 19 et 20.
Nouvelle solution admissible
y1 = 0;
y2 = 30;
y3 = 40;
y4 = 10;
y5 = 0

29 / 59
Résolution de programmes linéaires
La méthode du simplexe :

On remarque bien que y1 = 0 est toujours maintenu à zéro. Par

ailleurs, y5 est passé de 90 a 0 et y2 est passé de 0 a 30 .Donc on
déduit que pour cette étape la variable sortante de la base est y2 et
la variable entrante à la base est y5 .
La nouvelle valeur de la fonction objective est :
F = 40y1 + 60y2 = 1800,
Les coefficients de la fonction objective sont positifs. Ce qui permet
d’améliorer d’avantage la solution obtenue.
Dans ce cas on s’arrange pour exprimer toutes les équations en
fonction de y1 et y5 .
Pour ce faire on retire la valeur de y2 de la troisième équation et on
remplace son expression dans les deux premières. Il en est de même
pour F, ce qui nous donne dans cette étape les équations 21,22 et 23

30 / 59
Résolution de programmes linéaires
La méthode du simplexe :

5/3y1 + y3 − 1/3y5 = 40 (21)

2/3y1 + y4 − 1/3y5 = 10 (22)
1/3y1 + y2 + 1/3y5 = 30 (23)

Nouvelle expression de la fonction objective F = 1800 + 20y1 − 20y5 ,

D’après l’expression de la fonction objective de l’étape précédente on
choisit d’augmenter y1 en gardant y5 = 0
5/3y1 + y3 − 1/3y5 = 40 y 3 = 40 − 5/3y1 ≥ 0 ⇒ y1 ≤ 24 (24)
2/3y1 + y4 − 1/3y5 = 10 y4 = 10 − 2/3y1 ≥ 0 ⇒ y1 ≤ 15 (25)
1/3y1 + y2 + 1/3y5 = 30 y5 = 30 − 1/3y1 ≥ 0 ⇒ y1 ≤ 90 (26)

31 / 59
Résolution de programmes linéaires
La méthode du simplexe :

La valeur maximale admissible pour y1 = 15.

Nouvelle solution admissible :

y1 = 15;

y2 = 25;
y3 = 15;
y4 = 0;
y5 = 0

32 / 59
Résolution de programmes linéaires
La méthode du simplexe :

Pour cette étape, la variable sortante de la base est y2 et la variable

entrante à la base est y4 .
L’expression de la nouvelle valeur du critère est :
F = 2100 − 30y4 − 10y5 , Les coefficients de y4 et y5 dans la fonction
objective de la dernière étape sont négatifs, quelle que soient la
valeur de y4 et y5 qui implique une diminution de la valeur du critère
F.
Il n’existe donc plus d’augmentation et d’amélioration possible et la
dernière solution obtenue représente la solution optimale qui est
égale à 2100.

33 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

On commence par la transformation des contraintes d’inégalité en

contraintes d’égalité en introduisant des variables d’écart.
Étape 1
On construit un tableau à deux dimensions r × s où le nombre de
colonnes r est égal au nombre de variables (les variables de décision
plus les variables d’écart) dans le système plus une colonne de
solution. Le nombre de lignes est égal au nombre d’équation dans le
système sans considération des contraintes de positivité.
A la première itération, on sélectionne la variable qui a le coefficient
le plus élevé dans la ligne objective (fonction objective). On
encadrent la colonne de la variable entrante que l’on appelle "
colonne pivot".

34 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Étape 2
On calcule le minimum du rapport du coefficient du membre de
droite de chaque contrainte sur le coefficient correspondant à la
colonne. Dans le cas ou le coefficient dans la colonne entrante est
négatif ou infini, on ne le compte pas dans le calcul du minimum.
On encadre alors la ligne ou le minimum se produit. Cette ligne
reçoit le nom de "ligne pivot".
Le coefficient qui se trouve à l’intersection de la colonne pivot et de
la ligne pivot est appelé "élément pivot".

35 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Étape 2
On reconstruit le tableau du simplexe (il faut conserver la même
dimension du tableau). On commence, d’abord, par construire la
nouvelle ligne pivot qui se calcule de la manière suivante :
Ancienne ligne pivot
Nouvelle ligne pivot =
Element pivot
Puis, on calcule les autres lignes par la formule suivante :
Toutes les autres lignes y compris z= (Ligne actuelle)-(l’élément de sa
colonne pivot)* (nouvelle ligne pivot)

36 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Exemple : Une entreprise disposant de 10 000 m2 de planches de bois en

réserve fabrique et commercialise 2 types de boîtes en bois. La fabrication
d’une boîte en bois de type 1 et de type 2 requiert, respectivement, 1 et
2 m2 de bois ainsi que 2 et 3 minutes de temps d’assemblage.
Seules 200 heures de travail sont disponibles pendant la semaine à venir.
Les boites sont clouées et, il faut quatre fois plus de clou pour une boîte
du second type que pour une du premier.
Le stock de clous disponible permet d’assembler au maximum 15 000
boîtes du premier type. Les boites sont vendues, respectivement, 3 et 5
du chiffre d’affaires.

37 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Formulation du problème :
x1 : quantité de boîtes en bois de type 1
x2 : quantité de boîtes en bois de type 2

Maxz = 3x1 + 5x2

Sous les contraintes :

x1 + 2x2 ≤ 10000
2x1 + 3x2 ≤ 12000
x1 + 4x2 ≤ 15000
x1 ≥ 0 et x2 ≥ 0
Après avoir mis le programme linéaire sous sa forme standard

Maxz = 3x1 + 5x2

38 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

S.c. :
x1 + 2x2 + x3 = 10000
2x1 + 3x2 + x4 = 12000
x1 + 4x2 + x5 = 15000
x1 ≥ 0 et x2 ≥ 0
On peut réécrire le programme linéaire en fonction de toutes les variables
du système (variables de décision et variables d’écarts)

Maxz = 3x1 + 5x2 + 0x3 + 0x4 + 0x5

x1 + 2x2 + x3 + 0x4 + 0x5 = 10000

2x1 + 3x2 + 0x3 + x4 + 0x5 = 12000
x1 + 4x2 + 0x3 + 0x4 + x5 = 15000
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 et x5 ≥ 0
Puis, nous faisons juste une translation vers un tableau comme suit :

39 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Itération
z x1 x2 x3 x4 x5 sol
z -1 3 5 0 0 0 0
x3 0 1 2 1 0 0 10000
x4 0 2 3 0 1 0 12000
x5 0 1 4 0 0 1 15000
Dans ce tableau, nous allons définir la colonne pivot, la ligne pivot et
l’élément pivot. Nous commençons par la colonne pivot. Pour ce faire,
nous sélectionnerons la variable qui a le coefficient le plus élevé dans la
ligne de la fonction objective qui est le 5 de la variable x2 . Donc la
colonne pivot est la colonne du x2 .

40 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Ensuite, nous définirons la ligne pivot en divisant chaque solution par les
éléments correspondants dans la colonne pivot.

10000/2 = 5000

12000/3 = 4000
15000/4 = 3750
On choisit la plus petite valeur. Dans ce cas c’est la valeur de : 3750. Ce
qui correspond à la dernière ligne du tableau qui sera la ligne pivot.

41 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

L’intersection entre la colonne pivot et la ligne pivot, nous donne

l’élément pivot qui est égal à 4
42 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Itŕation 2 Une fois l’élément pivot déterminé, on calcule la nouvelle ligne

pivot en divisant l’ancienne ligne par l’élément pivot, ce qui donne :
0 1 4 0 0 1 15000
4 4 4 4 4 4 4
0 0.25 1 0 0 0.25 3750
On la place dans le nouveau tableau en conservant la même position que
dans le premier tableau sauf que la variable dans la colonne pivot prend
la place de la variable de la ligne pivot comme suit :
z x1 x2 x3 x4 x5 sol
z
x3
x4
x2 0 0.25 1 0 0 0.25 3750

43 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

Ensuite, on remplit toutes les autres lignes par la formule suivante :

(Ligne actuelle)-(l’élément de sa colonne pivot) * (nouvelle ligne pivot)
On applique le principe sur la ligne 3 (variable x4 )

Et de la même manière, on applique le même calcule pour les lignes de x3

et de z. On les place dans les zones appropriées dans le tableau de la
deuxième itération.

44 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

À la fin de cette itération, on vérifie tous les coefficients de ligne z. S’ils

sont négatifs ou nuls on s’arrête. On a trouvé la solution optimale. Ce
n’est pas le cas ici, la valeur de x1 est positive. On construit donc une
nouvelle itération et un nouveau tableau de la même manière que pour
l’itération 2.

45 / 59
Résolution de programmes linéaires
Rśolution par Tableaux de simplexe

z x1 x2 x3 x4 x5 sol
z -1 0 0 0 -1,4 -0,2 -19800
x3 0 0 0 1 -0,4 -0,2 2200
x1 0 1 0 0 0,8 -0,6 600
x2 0 0 1 0 -0,2 -0,4 3600

D’après le tableau de l’itération 3 on remarque que les coefficients de la

ligne z, sont négatifs ou nuls. Donc on s’arrête. On a trouvé la solution
optimale avec :
x1 = 600
x2 = 3600
z = 19800

46 / 59
 Dualité

Sommaire
1 Introduction
2 Forme d’un programme linéaire
Forme générale
Forme standard ou forme canonique d’un programme linéaire
3 Résolution de programmes linéaires
Résolution graphique
La méthode du simplexe :
Rśolution par Tableaux de simplexe
4 Dualité
Exemple : Problème de production
Qu’est ce que la dualité ?
Comment trouver le dual ?
Conditions d’optimalité primal-dual
Exemple :

47 / 59
Dualité
Exemple : Problème de production

Deux produits R1 et R2 sont fabriqués en quantité m1 et m2. La

fabrication des deux produits passe par trois machines afin de subir
différents traitements. Bien évidemment le but de l’entreprise est de
maximiser son bénéfice total provenant de la vente des 2 produits. Le
problème ainsi formulé est donné par le programme suivant :

MaxF (x1 , x2 ) = 6x1 + 4x2

Sous contraintes :

3x1 + 9x2 ≤ 81

4x1 + 5x2 ≤ 55

2x1 + x2 ≤ 20

x1 ; x2 ≥ 0
48 / 59
Dualité
Exemple : Problème de production

Pour certaines raisons, l’entreprise décide de vendre toutes ses ressources.

Un acheteur se présente et propose à l’entreprise les prix unitaires
k1 , k2 , k3 pour chacune des ressources. L’entreprise acceptera de lui
vendre toutes ses ressources uniquement si le prix de vente est au moins
égal au profit qu’elle ferait en vendant ses produits.
De son coté, l’acheteur cherche à minimiser ses dépenses.
Quels prix unitaires k1 , k2 , k3 l’acheteur doit-il proposer à l’entreprise
pour qu’elle accepte de vendre toutes ses ressources ?

48 / 59
Dualité
Qu’est ce que la dualité ?

La dualité est un programme linéaire qui refléte un programme

linéaire d’un probléme donné par sa premiére de description
(principale). Autrement dit, la dualité est une façon de visualiser un
problème donné sous un autre angle. La dualité d’un problème,
peut-être assimilé à l’effet miroir où on arrive à voir la même chose
sauf que les coordonnées de la base utilisée ne sont pas les mêmes.
La dualité est un concept important en recherche opérationnelle.
Tout programme linéaire admet 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.

49 / 59
Dualité
Qu’est ce que la dualité ?

Programme linéaire primal Programme linéaire dual

MaxZ = c > x minf = b > y

  >
Ax ≤ b A y ≥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 facilement trouver une solution de
l’un à partir de la solution de l’autre.

50 / 59
Dualité
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 "bi" dans le problème
primal deviennent les coefficients de la nouvelle fonction objective du
dual et les coefficients de la fonction objective 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 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 A> .( l’écriture en ligne
devient l’écriture en colonne).

51 / 59
Dualité
Comment trouver le dual ?

Exemple :

MaxF (x1 , x2 ) = 6x1 + 4x2

Sous contraintes
3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20
x1 ; x2 ≥ 0
A chaque contrainte, nous affecterons une variable appelée yi . La
transformation est donnée par le tableau A.

52 / 59
Dualité
Comment trouver le dual ?

Tableau A : Passage du primal vers le dual

53 / 59
Dualité
Conditions d’optimalité primal-dual

L’ensemble primal-dual possède un certain nombre de conditions et

de propriétés indissociables raccordées l’une à l’autre, précisées
comme suit :
si le problème primal est réalisable et possède une solution optimale
donc, forcement, il existe une solution optimale pour le dual qui est
la même.
Et si le problème primal est non réalisable, le primal l’est non borné.

54 / 59
Dualité
Exemple :

le programme primal est :

Maxz = 100x1 + 200x2

S.C
x1 + x2 ≤ 150
4x1 + 2x2 ≤ 440
x1 + 4x2 ≤ 480
x1 ≤ 90
x1 ≥ 0, x2 ≥ 0

55 / 59
Dualité
Exemple :

Donc le programme dual est :

Minw = 150y1 + 440y2 + 480y3 + 90y4

Sous contraintes
y1 + 4y2 + y3 + y4 ≥ 100
y1 + 2y2 + 4y3 ≥ 200
y1 ≥ 0, y2 ≥ 0
Nous proposons de résoudre ce système par les tableaux de simplexe.

56 / 59
Dualité
Exemple :

On remarque bien que le problème dual est un problème de minimisation.

Les tableaux de Simplexe s’appliquent de la même manière expliquée
dans la section précédente. La seule différence réside dans le choix de la
colonne pivot qui se fait, en sélectionnant la variable qui a le coefficient
le plus bas(le plus petit) dans la ligne de la fonction objective.
Itération 1 :

57 / 59
Dualité
Exemple :

Itération 2 :

Itération 3 :

58 / 59
Dualité
Exemple :

Itération 4 :

La solution optimale du dual peut être déduite du primal de la manière

suivante :

y1 = 0 ⇔ S1 = 0
y2 = −60 ⇔ S2 = 60
y3 = 0 ⇔ S3 = 0
y4 = −50 ⇔ S4 = 50
e1 = 0 ⇔ x1 = 40
e2 == 110 ⇔ x2 = 110
w = −26000 ⇔ z = 26000
59 / 59