Cours de Recherche Opérationnelle

Programmation linéaire

Mohamed Zeriab Essadek

ENSET - Rabat.
Plan de la présentation

1 Introduction
2 Formulation d’un programme linéaire
Problème de production
Problème de mélange
Problème de transport
Problème de découpe
3 Résolution graphique
4 Méthode du simplexe
5 Dualité
6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 2 / 55

 Introduction

Grandes lignes

1 Introduction

2 Formulation d’un programme linéaire

3 Résolution graphique

4 Méthode du simplexe

5 Dualité

6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 3 / 55

 Introduction

Introduction

En économie, économétrie et industrie, on est souvent confronté à

faire des choix pratiques. La recherche opérationnelle, appelée aussi
aide à la décision, est l’ensemble des méthodes qui nous permet de
faire le meilleur choix possible pour un problème donné.
Etant donné un problème réel quelconque on est amené à le
modéliser sous forme mathématique.
Dans ce cours, on s’intéresse aux problèmes de type maximisation ou
minimisation d’une fonction linéaire sous contraintes linéaires.

Essadek Recherche Opérationnelle 2019/2020 4 / 55

 Introduction

Introduction

En économie, économétrie et industrie, on est souvent confronté à

faire des choix pratiques. La recherche opérationnelle, appelée aussi
aide à la décision, est l’ensemble des méthodes qui nous permet de
faire le meilleur choix possible pour un problème donné.
Etant donné un problème réel quelconque on est amené à le
modéliser sous forme mathématique.
Dans ce cours, on s’intéresse aux problèmes de type maximisation ou
minimisation d’une fonction linéaire sous contraintes linéaires.

Essadek Recherche Opérationnelle 2019/2020 4 / 55

 Introduction

Introduction

En économie, économétrie et industrie, on est souvent confronté à

faire des choix pratiques. La recherche opérationnelle, appelée aussi
aide à la décision, est l’ensemble des méthodes qui nous permet de
faire le meilleur choix possible pour un problème donné.
Etant donné un problème réel quelconque on est amené à le
modéliser sous forme mathématique.
Dans ce cours, on s’intéresse aux problèmes de type maximisation ou
minimisation d’une fonction linéaire sous contraintes linéaires.

Essadek Recherche Opérationnelle 2019/2020 4 / 55

 Introduction

Introduction

Un problème de programmation linéaire s’écrit sous la forme :


maximiser f (x)
(1)
s.c. Ax = b

où :
f est une fonction linéaire c.à.d. qui s’écrit sous la forme :
f : IRn → IR
x → cx
avec c un vecteur ligne de taille n ; A une matrice de taille (m, n)

Essadek Recherche Opérationnelle 2019/2020 5 / 55

 Introduction

Introduction

Un problème de programmation linéaire s’écrit sous la forme :


maximiser f (x)
(1)
s.c. Ax = b

où :
f est une fonction linéaire c.à.d. qui s’écrit sous la forme :
f : IRn → IR
x → cx
avec c un vecteur ligne de taille n ; A une matrice de taille (m, n)

Essadek Recherche Opérationnelle 2019/2020 5 / 55

 Introduction

Introduction

Un problème de programmation linéaire s’écrit sous la forme :


maximiser f (x)
(1)
s.c. Ax = b

où :
f est une fonction linéaire c.à.d. qui s’écrit sous la forme :
f : IRn → IR
x → cx
avec c un vecteur ligne de taille n ; A une matrice de taille (m, n)

Essadek Recherche Opérationnelle 2019/2020 5 / 55

 Formulation d’un programme linéaire

Grandes lignes

1 Introduction

2 Formulation d’un programme linéaire

Problème de production
Problème de mélange
Problème de transport
Problème de découpe

3 Résolution graphique

4 Méthode du simplexe

5 Dualité

6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 6 / 55

 Formulation d’un programme linéaire

Formulation d’un programme linéaire

Dans ce chapitre, on va modéliser quelques problèmes classiques :

problème de production
problème de mélange
problème de transport
problème de découpe

Essadek Recherche Opérationnelle 2019/2020 7 / 55

 Formulation d’un programme linéaire

Formulation d’un programme linéaire

Dans ce chapitre, on va modéliser quelques problèmes classiques :

problème de production
problème de mélange
problème de transport
problème de découpe

Essadek Recherche Opérationnelle 2019/2020 7 / 55

 Formulation d’un programme linéaire Problème de production

Problème de production

Supposons une usine qui produit deux pièces M1 et M2 sur une

machine. Ces produits sont tellement demandés qu’ils sont tous
vendus.
Les prix de vente sont de 25 DHS pour M1 et 13 DHS pour M2 .
La production de ces produits demande 6 unités de matière première
pour M1 et 2.7 unités pour M2 , et aussi 10 min de temps de
fonctionnement de la machine pour M1 et 3 min pour M2 . On veut
calculer le nombre de pièces à produire pour que le chiffre d’affaires
soit maximale. Sachant que le stock de matières premières est de 350
unités et la disponibilité de la machine est de 8 heures(480 min)

Essadek Recherche Opérationnelle 2019/2020 8 / 55

 Formulation d’un programme linéaire Problème de production

Problème de production

Supposons une usine qui produit deux pièces M1 et M2 sur une

machine. Ces produits sont tellement demandés qu’ils sont tous
vendus.
Les prix de vente sont de 25 DHS pour M1 et 13 DHS pour M2 .
La production de ces produits demande 6 unités de matière première
pour M1 et 2.7 unités pour M2 , et aussi 10 min de temps de
fonctionnement de la machine pour M1 et 3 min pour M2 . On veut
calculer le nombre de pièces à produire pour que le chiffre d’affaires
soit maximale. Sachant que le stock de matières premières est de 350
unités et la disponibilité de la machine est de 8 heures(480 min)

Essadek Recherche Opérationnelle 2019/2020 8 / 55

 Formulation d’un programme linéaire Problème de production

Problème de production

Supposons une usine qui produit deux pièces M1 et M2 sur une

machine. Ces produits sont tellement demandés qu’ils sont tous
vendus.
Les prix de vente sont de 25 DHS pour M1 et 13 DHS pour M2 .
La production de ces produits demande 6 unités de matière première
pour M1 et 2.7 unités pour M2 , et aussi 10 min de temps de
fonctionnement de la machine pour M1 et 3 min pour M2 . On veut
calculer le nombre de pièces à produire pour que le chiffre d’affaires
soit maximale. Sachant que le stock de matières premières est de 350
unités et la disponibilité de la machine est de 8 heures(480 min)

Essadek Recherche Opérationnelle 2019/2020 8 / 55

 Formulation d’un programme linéaire Problème de production

Problème de production

Soit x le nombre de pièces M1 produites et y le nombre de M2 Le

chiffre d’affaire est exprimé par : f (x, y ) = 25x + 13y
Et le problème se traduit sous la forme :

 maximiser f (x, y )
s.c. 6x + 2.7y ≤ 350
10x + 3y ≤ 480


Essadek Recherche Opérationnelle 2019/2020 9 / 55

 Formulation d’un programme linéaire Problème de production

Problème de production

Soit x le nombre de pièces M1 produites et y le nombre de M2 Le

chiffre d’affaire est exprimé par : f (x, y ) = 25x + 13y
Et le problème se traduit sous la forme :

 maximiser f (x, y )
s.c. 6x + 2.7y ≤ 350
10x + 3y ≤ 480


Essadek Recherche Opérationnelle 2019/2020 9 / 55

 Formulation d’un programme linéaire Problème de mélange

Problème de mélange

Une unité de production de jus désire fabriquer un jus composé

d’orange et de mangue.
On veut déterminer la composition à coût minimal d’un jus, tout en
sachant que
la quantité par bouteille est de 1000 gramme.
le jus doit comporter au moins 10% de vitamine C et au maximum
15% de glucides.
L’apport en vitamine C en 1 g d’orange est de 0.0053 g et en 1 g
de mangue est de 0.0044 g.
L’apport en glucides en 1 g d’orange est de 0.086 g et
en 1 g de mangue est de 0.143 g.
Le coût d’orange est de 3 DHS/kg et celui de la mangue est de 10
DHS/kg.

Essadek Recherche Opérationnelle 2019/2020 10 / 55

 Formulation d’un programme linéaire Problème de mélange

Problème de mélange

Une unité de production de jus désire fabriquer un jus composé

d’orange et de mangue.
On veut déterminer la composition à coût minimal d’un jus, tout en
sachant que
la quantité par bouteille est de 1000 gramme.
le jus doit comporter au moins 10% de vitamine C et au maximum
15% de glucides.
L’apport en vitamine C en 1 g d’orange est de 0.0053 g et en 1 g
de mangue est de 0.0044 g.
L’apport en glucides en 1 g d’orange est de 0.086 g et
en 1 g de mangue est de 0.143 g.
Le coût d’orange est de 3 DHS/kg et celui de la mangue est de 10
DHS/kg.

Essadek Recherche Opérationnelle 2019/2020 10 / 55

 Formulation d’un programme linéaire Problème de mélange

Problème de mélange

Soit x le nombre de grammes d’oranges par bouteille, et y le nombre

de grammes de mangue.
On veut minimiser le coût donc min f (x, y ) = 0.003x + 0.01y
Les contraintes sont :
x + y = 1000
0.0053x + 0.0044y ≥ 0.1(x + y )
0.086x + 0.143y ≤ 0.15(x + y )

Essadek Recherche Opérationnelle 2019/2020 11 / 55

 Formulation d’un programme linéaire Problème de mélange

Problème de mélange

Soit x le nombre de grammes d’oranges par bouteille, et y le nombre

de grammes de mangue.
On veut minimiser le coût donc min f (x, y ) = 0.003x + 0.01y
Les contraintes sont :
x + y = 1000
0.0053x + 0.0044y ≥ 0.1(x + y )
0.086x + 0.143y ≤ 0.15(x + y )

Essadek Recherche Opérationnelle 2019/2020 11 / 55

 Formulation d’un programme linéaire Problème de mélange

Problème de mélange

Soit x le nombre de grammes d’oranges par bouteille, et y le nombre

de grammes de mangue.
On veut minimiser le coût donc min f (x, y ) = 0.003x + 0.01y
Les contraintes sont :
x + y = 1000
0.0053x + 0.0044y ≥ 0.1(x + y )
0.086x + 0.143y ≤ 0.15(x + y )

Essadek Recherche Opérationnelle 2019/2020 11 / 55

 Formulation d’un programme linéaire Problème de transport

Formulation du problème

Un industriel désire transporter, à moindre coût, un certain bien depuis

m entrepôts vers n clients.
La disponibilité de l’entrepôt i, (1 ≤ i ≤ m) est ai et la demande du
client j, (1 ≤ j ≤ n) est bj . Nous supposons que ai , bj > 0.
Le coût unitaire de transport de l’entrepôt i vers le client j est Cij .

Essadek Recherche Opérationnelle 2019/2020 12 / 55

 Formulation d’un programme linéaire Problème de transport

Formulation du problème

Un industriel désire transporter, à moindre coût, un certain bien depuis

m entrepôts vers n clients.
La disponibilité de l’entrepôt i, (1 ≤ i ≤ m) est ai et la demande du
client j, (1 ≤ j ≤ n) est bj . Nous supposons que ai , bj > 0.
Le coût unitaire de transport de l’entrepôt i vers le client j est Cij .

Essadek Recherche Opérationnelle 2019/2020 12 / 55

 Formulation d’un programme linéaire Problème de transport

Formulation du problème

Un industriel désire transporter, à moindre coût, un certain bien depuis

m entrepôts vers n clients.
La disponibilité de l’entrepôt i, (1 ≤ i ≤ m) est ai et la demande du
client j, (1 ≤ j ≤ n) est bj . Nous supposons que ai , bj > 0.
Le coût unitaire de transport de l’entrepôt i vers le client j est Cij .

Essadek Recherche Opérationnelle 2019/2020 12 / 55

 Formulation d’un programme linéaire Problème de transport

Formulation du problème

Le problème de l’industriel est de déterminer la quantité xij à envoyer

de chaque entrepôt vers chaque client de telle manière que le coût
total de transport soit le plus faible possible tout en satisfaisant la
demande de tous les clients sans dépasser la disponibilité des
entrepôts.

Essadek Recherche Opérationnelle 2019/2020 13 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j ≥ bj j = 1, . . . , n (demande)
i=1
n
X
xi,j ≤ ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 14 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j ≥ bj j = 1, . . . , n (demande)
i=1
n
X
xi,j ≤ ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 14 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j ≥ bj j = 1, . . . , n (demande)
i=1
n
X
xi,j ≤ ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 14 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j ≥ bj j = 1, . . . , n (demande)
i=1
n
X
xi,j ≤ ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 14 / 55

 Formulation d’un programme linéaire Problème de transport

Hypothèse

On suppose le système balancé c.à.d.

m
X n
X
ai = bj
i=1 j=1

où ai , bj > 0

Essadek Recherche Opérationnelle 2019/2020 15 / 55

 Formulation d’un programme linéaire Problème de transport

Hypothèse

On suppose le système balancé c.à.d.

m
X n
X
ai = bj
i=1 j=1

où ai , bj > 0

Essadek Recherche Opérationnelle 2019/2020 15 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j = bj j = 1, . . . , n (demande)
i=1
n
X
xi,j = ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 16 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j = bj j = 1, . . . , n (demande)
i=1
n
X
xi,j = ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 16 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j = bj j = 1, . . . , n (demande)
i=1
n
X
xi,j = ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 16 / 55

 Formulation d’un programme linéaire Problème de transport

Modèle mathématique

m X
X n
Min cij xij
i=1 j=1

m
X
xi,j = bj j = 1, . . . , n (demande)
i=1
n
X
xi,j = ai i = 1, . . . , m (disponibilité)
j=1

xij ≥ 0 j = 1, . . . , n; i = 1, . . . , m (positivité)

Essadek Recherche Opérationnelle 2019/2020 16 / 55

 Formulation d’un programme linéaire Problème de transport

Exemple

Un fabricant de marmites géantes à gaz veut livrer 4 hôtels, qui lui

achètent respectivement 10,8,5 et 7 marmites, qui sont réparties sur 3
entrepôts : 6 dans le premier, 9 dans le deuxième et 15 dans le
troisième.
Les coûts de transport entre chaque entrepôt Ri et chaque hôtel Lj
sont donnés dans le tableau suivant

Essadek Recherche Opérationnelle 2019/2020 17 / 55

 Formulation d’un programme linéaire Problème de transport

Exemple

Un fabricant de marmites géantes à gaz veut livrer 4 hôtels, qui lui

achètent respectivement 10,8,5 et 7 marmites, qui sont réparties sur 3
entrepôts : 6 dans le premier, 9 dans le deuxième et 15 dans le
troisième.
Les coûts de transport entre chaque entrepôt Ri et chaque hôtel Lj
sont donnés dans le tableau suivant

Essadek Recherche Opérationnelle 2019/2020 17 / 55

 Formulation d’un programme linéaire Problème de transport

Exemple

L1 L2 L3 L4
R1 4 3 7 2
R2 3 4 5 2
R3 5 6 9 7

Essadek Recherche Opérationnelle 2019/2020 18 / 55

 Formulation d’un programme linéaire Problème de transport

Min 4x11 + 3x12 + 7x13 + 2x14 + 3x21 + 4x22 + 5x23 +







 2x24 + 5x31 + 6x32 + 9x33 + 7x34



 s.c. x11 + x12 + x13 + x14 = 6



 x21 + x22 + x23 + x24 = 9
x31 + x32 + x33 + x34 = 15


 x11 + x21 + x31 = 10
x12 + x22 + x32 = 8




x13 + x23 + x33 = 5







 x14 + x24 + x34 = 7

xij >= 0 ∀(i, j)

Essadek Recherche Opérationnelle 2019/2020 19 / 55

 Formulation d’un programme linéaire Problème de découpe

Formulation du problème

En industrie du papier, de l’acier, du bois,..., on a besoin de découper

de la matière première pour produire des sous entités.
On appelle problème de découpe à une dimension, le problème de
découpage d’une barre en des barres de dimension inférieure.
On appelle problème de découpe à deux dimension, le problème de
découpage d’un rectangle en des sous rectangles de dimension
inférieure.

Essadek Recherche Opérationnelle 2019/2020 20 / 55

 Formulation d’un programme linéaire Problème de découpe

Formulation du problème

En industrie du papier, de l’acier, du bois,..., on a besoin de découper

de la matière première pour produire des sous entités.
On appelle problème de découpe à une dimension, le problème de
découpage d’une barre en des barres de dimension inférieure.
On appelle problème de découpe à deux dimension, le problème de
découpage d’un rectangle en des sous rectangles de dimension
inférieure.

Essadek Recherche Opérationnelle 2019/2020 20 / 55

 Formulation d’un programme linéaire Problème de découpe

Formulation du problème

En industrie du papier, de l’acier, du bois,..., on a besoin de découper

de la matière première pour produire des sous entités.
On appelle problème de découpe à une dimension, le problème de
découpage d’une barre en des barres de dimension inférieure.
On appelle problème de découpe à deux dimension, le problème de
découpage d’un rectangle en des sous rectangles de dimension
inférieure.

Essadek Recherche Opérationnelle 2019/2020 20 / 55

 Formulation d’un programme linéaire Problème de découpe

Exemple

Une unité de production de papier a une commande de 3 clients, pour

répondre à ces commandes, elle doit découper des bobines d’une
largeur standard de 5000 mm, en des bobines moins large, sachant
que la longueur est standard.
Soit la commande suivante :
client 1 : 280 bobines de largeur 900 mm
client 2 : 130 bobines de largeur 800 mm
client 3 : 150 bobines de largeur 750 mm

Essadek Recherche Opérationnelle 2019/2020 21 / 55

 Formulation d’un programme linéaire Problème de découpe

Exemple

Une unité de production de papier a une commande de 3 clients, pour

répondre à ces commandes, elle doit découper des bobines d’une
largeur standard de 5000 mm, en des bobines moins large, sachant
que la longueur est standard.
Soit la commande suivante :
client 1 : 280 bobines de largeur 900 mm
client 2 : 130 bobines de largeur 800 mm
client 3 : 150 bobines de largeur 750 mm

Essadek Recherche Opérationnelle 2019/2020 21 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

On construit l’ensemble des combinaisons possibles appelé activités.

Num 1 2 3 4 5 6 7 8 9
900 5 4 4 3 3 3 2 2 2
800 0 1 0 2 1 0 4 3 2
750 0 0 1 0 2 3 0 1 2
Perte 500 600 650 700 0 50 0 50 100

Essadek Recherche Opérationnelle 2019/2020 22 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

On construit l’ensemble des combinaisons possibles appelé activités.

Num 1 2 3 4 5 6 7 8 9
900 5 4 4 3 3 3 2 2 2
800 0 1 0 2 1 0 4 3 2
750 0 0 1 0 2 3 0 1 2
Perte 500 600 650 700 0 50 0 50 100

Essadek Recherche Opérationnelle 2019/2020 22 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

Num 10 11 12 13 14 15 16 17 18
900 2 2 1 1 1 1 1 1 0
800 1 0 5 4 3 2 1 0 6
750 3 4 0 1 2 3 4 5 0
Perte 150 200 100 150 200 250 300 350 200
Num 19 20 21 22 23 24
900 0 0 0 0 0 0
800 5 4 3 2 1 0
750 1 2 3 4 5 6
Perte 250 300 350 400 450 500

Essadek Recherche Opérationnelle 2019/2020 23 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

Num 10 11 12 13 14 15 16 17 18
900 2 2 1 1 1 1 1 1 0
800 1 0 5 4 3 2 1 0 6
750 3 4 0 1 2 3 4 5 0
Perte 150 200 100 150 200 250 300 350 200
Num 19 20 21 22 23 24
900 0 0 0 0 0 0
800 5 4 3 2 1 0
750 1 2 3 4 5 6
Perte 250 300 350 400 450 500

Essadek Recherche Opérationnelle 2019/2020 23 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

Le but est de minimiser le nombre de bobines à découper.

Soit (xi , i = {1, 2, . . . , 24}) le nombre de bobines à découper suivant la
combinaison i, (pi , i = {1, 2, . . . , 24}) la perte de la combinaison i,
(ai , i = {1, 2, . . . , 24}) le nombre de bobines de 900 mm résultant de
la combinaison i, (bi , i = {1, 2, . . . , 24}) le nombre de bobines de 800
mm résultant de la combinaison i et (ci , i = {1, 2, . . . , 24}) le nombre
de bobines de 750 mm résultant de la combinaison i.

Essadek Recherche Opérationnelle 2019/2020 24 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

La fonction objectif s’écrit :

24
X
Min z = pi xi
i=1

Essadek Recherche Opérationnelle 2019/2020 25 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

La fonction objectif s’écrit :

24
X
Min z = pi xi
i=1

Essadek Recherche Opérationnelle 2019/2020 25 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

Les contraintes sont :

24
X
ai xi ≥ 280
i=1
24
X
bi xi ≥ 130
i=1
24
X
ci xi ≥ 150
i=1

xi , i = 1, 2, . . . , 24 entier

Essadek Recherche Opérationnelle 2019/2020 26 / 55

 Formulation d’un programme linéaire Problème de découpe

Modèle mathématique

Les contraintes sont :

24
X
ai xi ≥ 280
i=1
24
X
bi xi ≥ 130
i=1
24
X
ci xi ≥ 150
i=1

xi , i = 1, 2, . . . , 24 entier

Essadek Recherche Opérationnelle 2019/2020 26 / 55

 Résolution graphique

Grandes lignes

1 Introduction

2 Formulation d’un programme linéaire

3 Résolution graphique

4 Méthode du simplexe

5 Dualité

6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 27 / 55

 Résolution graphique

Résolution graphique

Une fois le problème modélisé, il est donc normal d’avoir pour objectif
de résoudre le programme linéaire.
Une des méthodes qui peut s’avérer bonne dans ce cas est la
résolution graphique dans le cas où le problème est à deux variables.
Les contraintes de type inégalités sont des demi-plans. On peut
représenter géométriquement ces contraintes comme étant
l’intersection de tous les demi-plans.
on dessine une droite qui représente la fonction objectif, puis on la fait
glisser selon la direction adéquate.

Essadek Recherche Opérationnelle 2019/2020 28 / 55

 Résolution graphique

Résolution graphique

Une fois le problème modélisé, il est donc normal d’avoir pour objectif
de résoudre le programme linéaire.
Une des méthodes qui peut s’avérer bonne dans ce cas est la
résolution graphique dans le cas où le problème est à deux variables.
Les contraintes de type inégalités sont des demi-plans. On peut
représenter géométriquement ces contraintes comme étant
l’intersection de tous les demi-plans.
on dessine une droite qui représente la fonction objectif, puis on la fait
glisser selon la direction adéquate.

Essadek Recherche Opérationnelle 2019/2020 28 / 55

 Résolution graphique

Résolution graphique

Une fois le problème modélisé, il est donc normal d’avoir pour objectif
de résoudre le programme linéaire.
Une des méthodes qui peut s’avérer bonne dans ce cas est la
résolution graphique dans le cas où le problème est à deux variables.
Les contraintes de type inégalités sont des demi-plans. On peut
représenter géométriquement ces contraintes comme étant
l’intersection de tous les demi-plans.
on dessine une droite qui représente la fonction objectif, puis on la fait
glisser selon la direction adéquate.

Essadek Recherche Opérationnelle 2019/2020 28 / 55

 Résolution graphique

Résolution graphique

Une fois le problème modélisé, il est donc normal d’avoir pour objectif
de résoudre le programme linéaire.
Une des méthodes qui peut s’avérer bonne dans ce cas est la
résolution graphique dans le cas où le problème est à deux variables.
Les contraintes de type inégalités sont des demi-plans. On peut
représenter géométriquement ces contraintes comme étant
l’intersection de tous les demi-plans.
on dessine une droite qui représente la fonction objectif, puis on la fait
glisser selon la direction adéquate.

Essadek Recherche Opérationnelle 2019/2020 28 / 55

 Résolution graphique

Exemple

Exemple


 max 6x + 4y



 s.c
3x + 9y ≤ 81


 4x + 5y ≤ 55
2x + y ≤ 20




x, y ≥ 0


Essadek Recherche Opérationnelle 2019/2020 29 / 55

 Résolution graphique

Exemple

y



 max 6x + 4y
s.c





 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




0 x

Essadek Recherche Opérationnelle 2019/2020 30 / 55

 Résolution graphique

Exemple

y



 max 6x + 4y
s.c





 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




y = 9 − 13 x

0 x

Essadek Recherche Opérationnelle 2019/2020 30 / 55

 Résolution graphique

Exemple

y



 max 6x + 4y
s.c





 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




y = 9 − 13 x

0 x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Résolution graphique

Exemple

y



 max 6x + 4y
s.c




y = 20 − 2x 
 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




y = 9 − 13 x

0 x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Résolution graphique

Exemple

y



 max 6x + 4y
s.c




y = 20 − 2x 
 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




•
• y = 9 − 13 x

0• • x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Résolution graphique

Exemple

y



 max 6x + 4y
s.c




y = 20 − 2x 
 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




•
• y = 9 − 13 x

0• • x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Résolution graphique

Exemple

y



 max 6x + 4y
s.c




y = 20 − 2x 
 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




•
• y = 9 − 13 x

0• • x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Résolution graphique

Exemple

y



 max 6x + 4y
s.c




y = 20 − 2x 
 3x + 9y ≤ 81



 4x + 5y ≤ 55

2x + y ≤ 20





x, y ≥ 0




•
• y = 9 − 13 x

0• • x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Résolution graphique

Exemple

y



 max 6x + 4y
s.c




y = 20 − 2x 
 3x + 9y ≤ 81



 4x + 5y ≤ 55
Optimum

2x + y ≤ 20





x, y ≥ 0




•
• y = 9 − 13 x

0• • x
y = 11 − 45 x
Essadek Recherche Opérationnelle 2019/2020 30 / 55
 Méthode du simplexe

Grandes lignes

1 Introduction

2 Formulation d’un programme linéaire

3 Résolution graphique

4 Méthode du simplexe

5 Dualité

6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 31 / 55

 Méthode du simplexe

Définition

Considérons le problème linéaire suivant :

 min c t x


s.c
Ax = b


avec m < n et x, c ∈ IRn , b ∈ IRm , A ∈ IRm×n et rg(A) = m

rg(A) = m =⇒ toute sous matrice d’ordre m de A est inversible.

A = [B | N ]

où N est la sous matrice de A formée par les colonnes qui ne sont pas
dans la base.

Essadek Recherche Opérationnelle 2019/2020 32 / 55

 Méthode du simplexe

Définition

Considérons le problème linéaire suivant :

 min c t x


s.c
Ax = b


avec m < n et x, c ∈ IRn , b ∈ IRm , A ∈ IRm×n et rg(A) = m

rg(A) = m =⇒ toute sous matrice d’ordre m de A est inversible.

A = [B | N ]

où N est la sous matrice de A formée par les colonnes qui ne sont pas
dans la base.

Essadek Recherche Opérationnelle 2019/2020 32 / 55

 Méthode du simplexe

Variables de base

variables de bases variables hors bases

xB xN =z
cB cN
B N =b
(Base) (Colonnes hors base)
 
xB
[B | N ] = BxB + NxN = b
xN

Une solution de base du problème est donc

xN = 0 et xB = B −1 b

Si de plus xB ≥ 0 alors la solution est réalisable

Essadek Recherche Opérationnelle 2019/2020 33 / 55

 Méthode du simplexe

Variables de base

variables de bases variables hors bases

xB xN =z
cB cN
B N =b
(Base) (Colonnes hors base)
 
xB
[B | N ] = BxB + NxN = b
xN

Une solution de base du problème est donc

xN = 0 et xB = B −1 b

Si de plus xB ≥ 0 alors la solution est réalisable

Essadek Recherche Opérationnelle 2019/2020 33 / 55

 Méthode du simplexe

Caractérisation des solutions de base optimales

Les itérations du simplexe consistent à rechercher parmi les variables
hors base celle permettant d’augmenter le plus la fonction objectif.
Considérons le vecteur ligne de taille m, appelé vecteur des
multiplicateurs du simplexe , et défini par

π = cB B −1

Théorème
Une condition nécessaire et suffisante pour que B soit une base
optimale réalisable est :

c = cN − π.N ≥ 0

Les cj sont appelées coûts réduits des variables hors base.

Essadek Recherche Opérationnelle 2019/2020 34 / 55

 Méthode du simplexe

Caractérisation des solutions de base optimales

Corollaire
Soit B une base réalisable et x0 la solution de base correspondante.
S’il existe une variable hors base xs telle que cs < 0, alors on met en
0
évidence une autre base B tel que
0
f (x ) < f (x0 )

Essadek Recherche Opérationnelle 2019/2020 35 / 55

 Méthode du simplexe

Exemple
Soit le problème 

 max x1 + 2x2



 s.c
−3x1 + 2x2 ≤ 2

 −x1 + 2x2 ≤ 4

x + x2 ≤ 5


 1


x1 , x2 ≥ 0
On introduit des variables d’écarts, le problème devient sous la forme
standard : 

 min −x1 − 2x2



 s.c
−3x1 + 2x2 + x3 =2


 −x 1 + 2x 2 +x4 =4
x + x2 +x5 = 5


 1


x1 , x2 , x3 , x4 , x5 ≥ 0

Essadek Recherche Opérationnelle 2019/2020 36 / 55

 Méthode du simplexe

Exemple
Soit le problème 

 max x1 + 2x2



 s.c
−3x1 + 2x2 ≤ 2

 −x1 + 2x2 ≤ 4

x + x2 ≤ 5


 1


x1 , x2 ≥ 0
On introduit des variables d’écarts, le problème devient sous la forme
standard : 

 min −x1 − 2x2



 s.c
−3x1 + 2x2 + x3 =2


 −x 1 + 2x 2 +x4 =4
x + x2 +x5 = 5


 1


x1 , x2 , x3 , x4 , x5 ≥ 0

Essadek Recherche Opérationnelle 2019/2020 36 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x3 -3 2 1 0 0 2 L1
x4 -1 2 0 1 0 4 L2
x5 1 1 0 0 1 5 L3
-1 -2 0 0 0 0 L4

La dernière ligne est la ligne des coûts réduits.

Il y’a des coûts strictement négatifs donc l’optimum n’est pas atteint.
La solution de base correspondante :

x3 = 2, x4 = 4, x5 = 5, x1 = x2 = 0

Le coût est :
f =0

Essadek Recherche Opérationnelle 2019/2020 37 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x3 -3 2 1 0 0 2 L1
x4 -1 2 0 1 0 4 L2
x5 1 1 0 0 1 5 L3
-1 -2 0 0 0 0 L4
x2 entre dans la base

Essadek Recherche Opérationnelle 2019/2020 37 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x3 -3 2 1 0 0 2 L1
x4 -1 2 0 1 0 4 L2
x5 1 1 0 0 1 5 L3
-1 -2 0 0 0 0 L4

Essadek Recherche Opérationnelle 2019/2020 37 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x3 -3 2 1 0 0 2 L1
x4 -1 2 0 1 0 4 L2
x5 1 1 0 0 1 5 L3
-1 -2 0 0 0 0 L4
 
2 4 5
min , , =1
2 2 1

Essadek Recherche Opérationnelle 2019/2020 37 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x3 -3 2 1 0 0 2 L1
x4 -1 2 0 1 0 4 L2
x5 1 1 0 0 1 5 L3
-1 -2 0 0 0 0 L4
x3 sort de la base

0 1 0 0 1 0
L1 = L1 , L2 = L2 − L1 , L3 = L3 − L1 , L4 = L4 + L1
2 2

Essadek Recherche Opérationnelle 2019/2020 37 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 -3/2 1 1/2 0 0 1 L1
x4 2 0 -1 1 0 2 L2
x5 5/2 0 -1/2 0 1 4 L3
-4 0 1 0 0 2 L4

Il y’a un coût strictement négatif donc l’optimum n’est pas atteint.

La solution de base correspondante :

x2 = 1, x4 = 2, x5 = 4, x1 = x3 = 0

Le coût est :
f = −2

Essadek Recherche Opérationnelle 2019/2020 38 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 -3/2 1 1/2 0 0 1 L1
x4 2 0 -1 1 0 2 L2
x5 5/2 0 -1/2 0 1 4 L3
-4 0 1 0 0 2 L4
x1 entre dans la base

Essadek Recherche Opérationnelle 2019/2020 38 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 -3/2 1 1/2 0 0 1 L1
x4 2 0 -1 1 0 2 L2
x5 5/2 0 -1/2 0 1 4 L3
-4 0 1 0 0 2 L4

Essadek Recherche Opérationnelle 2019/2020 38 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 -3/2 1 1/2 0 0 1 L1
x4 2 0 -1 1 0 2 L2
x5 5/2 0 -1/2 0 1 4 L3
-4 0 1 0 0 2 L4
 
2 4
min , =1
2 5/2

Essadek Recherche Opérationnelle 2019/2020 38 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 -3/2 1 1/2 0 0 1 L1
x4 2 0 -1 1 0 2 L2
x5 5/2 0 -1/2 0 1 4 L3
-4 0 1 0 0 2 L4
x4 sort de la base

0 3 0 1 0 5 0
L1 = L1 + L2 , L2 = L2 , L3 = L3 − L2 , L4 = L4 + 2L2
4 2 4

Essadek Recherche Opérationnelle 2019/2020 38 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 0 1 -1/4 3/4 0 5/2 L1
x1 1 0 -1/2 1/2 0 1 L2
x5 0 0 3/4 -5/4 1 3/2 L3
0 0 -1 2 0 6 L4

Il y’a un coût strictement négatif donc l’optimum n’est pas atteint.

La solution de base correspondante :

x1 = 1, x2 = 5/2, x5 = 3/2, x3 = x4 = 0

Le coût est :
f = −6

Essadek Recherche Opérationnelle 2019/2020 39 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 0 1 -1/4 3/4 0 5/2 L1
x1 1 0 -1/2 1/2 0 1 L2
x5 0 0 3/4 -5/4 1 3/2 L3
0 0 -1 2 0 6 L4
x3 entre dans la base

Essadek Recherche Opérationnelle 2019/2020 39 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 0 1 -1/4 3/4 0 5/2 L1
x1 1 0 -1/2 1/2 0 1 L2
x5 0 0 3/4 -5/4 1 3/2 L3
0 0 -1 2 0 6 L4

Essadek Recherche Opérationnelle 2019/2020 39 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 0 1 -1/4 3/4 0 5/2 L1
x1 1 0 -1/2 1/2 0 1 L2
x5 0 0 3/4 -5/4 1 3/2 L3
0 0 -1 2 0 6 L4

Il y’a un seul composant positif dans la colonne de x3

Essadek Recherche Opérationnelle 2019/2020 39 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 0 1 -1/4 3/4 0 5/2 L1
x1 1 0 -1/2 1/2 0 1 L2
x5 0 0 3/4 -5/4 1 3/2 L3
0 0 -1 2 0 6 L4
x5 sort de la base

0 1 0 2 0 4 0 4
L1 = L1 + L3 , L2 = L2 + L3 , L3 = L3 , L4 = L4 + L3
3 3 3 3

Essadek Recherche Opérationnelle 2019/2020 39 / 55

 Méthode du simplexe

Exemple

x1 x2 x3 x4 x5
x2 0 1 0 1/3 1/3 3 L1
x1 1 0 0 -1/3 2/3 2 L2
x3 0 0 1 -5/3 4/3 2 L3
0 0 0 1/3 4/3 8 L4

Tous les coûts sont positifs ou nuls donc l’optimum est atteint
La solution de base correspondante :

x1 = 2, x2 = 3, x3 = 2, x4 = x5 = 0

Le coût est :
f ∗ = −8

Essadek Recherche Opérationnelle 2019/2020 40 / 55

 Méthode du simplexe

Remarques

Remarques
Pour un problème de maximisation, la même procédure est
appliquée, mais les éléments de la ligne des coûts doivent être
négatifs pour avoir un optimum.
Si tous les éléments de la colonne du pivot sont négatifs ou nuls
alors la solution est non bornée.
S’il y a un élément négatif dans la dernière colonne, alors le
problème est non réalisable.

Essadek Recherche Opérationnelle 2019/2020 41 / 55

 Dualité

Grandes lignes

1 Introduction

2 Formulation d’un programme linéaire

3 Résolution graphique

4 Méthode du simplexe

5 Dualité

6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 42 / 55

 Dualité

Définition

On appelle problème primal

min c t x



s.c.


 Ax ≤ b
x ≥0


On associe au problème primal un problème dual défini par

max y t b



s.c.


 At y ≥ c
y ≥0


Essadek Recherche Opérationnelle 2019/2020 43 / 55

 Dualité

Définition

On appelle problème primal

min c t x



s.c.


 Ax ≤ b
x ≥0


On associe au problème primal un problème dual défini par

max y t b



s.c.


 At y ≥ c
y ≥0


Essadek Recherche Opérationnelle 2019/2020 43 / 55

 Dualité

Propriétés

Le problème dual du problème dual est le problème primal.

Théorème fort de dualité
Si le problème primal (PL) admet une solution optimale x ∗ , alors le
problème dual (PLD) admet aussi une solution optimale y ∗ , et on a :

F (x ∗ ) = G(y ∗ )

Essadek Recherche Opérationnelle 2019/2020 44 / 55

 Dualité

Conditions d’optimalité primal-dual

Soient x et y des solutions réalisables respectivement du (PL) et du

(PLD), alors x et y sont des solutions réalisables optimales si et
seulement si :
Si une contrainte est satisfaite en tant qu’inégalité stricte dans
(PL) (respectivement dans (PLD)) alors la variable
correspondante dans (PLD) (respectivement dans (PL)) est nulle.
Si la valeur d’une variable dans (PL) ou (PLD) est strictement
positive alors la contrainte correspondante de l’autre programme
est une égalité.

Essadek Recherche Opérationnelle 2019/2020 45 / 55

 Analyse de sensibilité

Grandes lignes

1 Introduction

2 Formulation d’un programme linéaire

3 Résolution graphique

4 Méthode du simplexe

5 Dualité

6 Analyse de sensibilité

Essadek Recherche Opérationnelle 2019/2020 46 / 55

 Analyse de sensibilité

Définition
L’objectif de l’analyse post-optimale et de sensibilité est de faire une
étude sur l’impact de la variation d’une variable de la fonction objectif
ou du second membre des contraintes sur la solution optimale d’un
problème donné.

Essadek Recherche Opérationnelle 2019/2020 47 / 55

 Analyse de sensibilité

Illustration sur exemple

Soit le problème 

 max 6x1 + 4x2
3x1 + 9x2 ≤ 81


 4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20


Le problème devient sous forme standard



 max 6x1 + 4x2
3x1 + 9x2 + e1 = 81


 4x1 + 5x2 + e2 = 55
2x1 + x2 + e3 = 20


Essadek Recherche Opérationnelle 2019/2020 48 / 55

 Analyse de sensibilité

Illustration sur exemple

Soit le problème 

 max 6x1 + 4x2
3x1 + 9x2 ≤ 81


 4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20


Le problème devient sous forme standard



 max 6x1 + 4x2
3x1 + 9x2 + e1 = 81


 4x1 + 5x2 + e2 = 55
2x1 + x2 + e3 = 20


Essadek Recherche Opérationnelle 2019/2020 48 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 0 3 9 81
0 1 0 4 5 55
0 0 1 2 1 20
0 0 0 6 4 f
Variable entrante : maxj {(LH )j , (LH )j > 0} = 6 ⇒ x1 variable entrante
Variable sortante : min{( 81 55 20 20
3 , 4 , 2 )} = 2 ⇒ e3 variable sortante
L’inverse de la matrice de base est :

1 0 − 32
 

A−1B1 =
 0 1 −2 
0 0 12

Essadek Recherche Opérationnelle 2019/2020 49 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 0 3 9 81
0 1 0 4 5 55
0 0 1 2 1 20
0 0 0 6 4 f
Variable entrante : maxj {(LH )j , (LH )j > 0} = 6 ⇒ x1 variable entrante
Variable sortante : min{( 81 55 20 20
3 , 4 , 2 )} = 2 ⇒ e3 variable sortante
L’inverse de la matrice de base est :

1 0 − 32
 

A−1B1 =
 0 1 −2 
0 0 12

Essadek Recherche Opérationnelle 2019/2020 49 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 0 3 9 81
0 1 0 4 5 55
0 0 1 2 1 20
0 0 0 6 4 f
Variable entrante : maxj {(LH )j , (LH )j > 0} = 6 ⇒ x1 variable entrante
Variable sortante : min{( 81 55 20 20
3 , 4 , 2 )} = 2 ⇒ e3 variable sortante
L’inverse de la matrice de base est :

1 0 − 32
 

A−1B1 =
 0 1 −2 
0 0 12

Essadek Recherche Opérationnelle 2019/2020 49 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 0 3 9 81
0 1 0 4 5 55
0 0 1 2 1 20
0 0 0 6 4 f
Variable entrante : maxj {(LH )j , (LH )j > 0} = 6 ⇒ x1 variable entrante
Variable sortante : min{( 81 55 20 20
3 , 4 , 2 )} = 2 ⇒ e3 variable sortante
L’inverse de la matrice de base est :

1 0 − 32
 

A−1B1 =
 0 1 −2 
0 0 12

Essadek Recherche Opérationnelle 2019/2020 49 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 − 32 0 152 51
0 1 −2 0 3 15
1
0 0 2 1 12 10
0 0 −3 0 1 f − 60
Variable entrante : maxj {(LH )j , (LH )j > 0} = 1 ⇒ x2 variable entrante
51 15 10
Variable sortante : min{( 15/2 , 3 , 1/2 )} = 15
3 ⇒ e2 variable sortante
L’inverse de la matrice de base est :
1 − 52 0
 

A−1 =  0 1 0 
B2 3
0 − 61 1

Essadek Recherche Opérationnelle 2019/2020 50 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 − 32 0 152 51
0 1 −2 0 3 15
1
0 0 2 1 12 10
0 0 −3 0 1 f − 60
Variable entrante : maxj {(LH )j , (LH )j > 0} = 1 ⇒ x2 variable entrante
51 15 10
Variable sortante : min{( 15/2 , 3 , 1/2 )} = 15
3 ⇒ e2 variable sortante
L’inverse de la matrice de base est :
1 − 52 0
 

A−1 =  0 1 0 
B2 3
0 − 61 1

Essadek Recherche Opérationnelle 2019/2020 50 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 − 32 0 152 51
0 1 −2 0 3 15
1
0 0 2 1 12 10
0 0 −3 0 1 f − 60
Variable entrante : maxj {(LH )j , (LH )j > 0} = 1 ⇒ x2 variable entrante
51 15 10
Variable sortante : min{( 15/2 , 3 , 1/2 )} = 15
3 ⇒ e2 variable sortante
L’inverse de la matrice de base est :
1 − 52 0
 

A−1 =  0 1 0 
B2 3
0 − 61 1

Essadek Recherche Opérationnelle 2019/2020 50 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 0 − 32 0 152 51
0 1 −2 0 3 15
1
0 0 2 1 12 10
0 0 −3 0 1 f − 60
Variable entrante : maxj {(LH )j , (LH )j > 0} = 1 ⇒ x2 variable entrante
51 15 10
Variable sortante : min{( 15/2 , 3 , 1/2 )} = 15
3 ⇒ e2 variable sortante
L’inverse de la matrice de base est :
1 − 52 0
 

A−1 =  0 1 0 
B2 3
0 − 61 1

Essadek Recherche Opérationnelle 2019/2020 50 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 − 25 7
2 0 0 27
2
1
0 3 − 32 0 1 5
0 − 61 5
2 1 0 15
2
0 − 31 − 11
3 0 0 f − 65
L’optimum est :

27 15
(e1∗ = ; x2∗ = 5 ; x1∗ = ; e2∗ = e3∗ = 0)
2 2

Essadek Recherche Opérationnelle 2019/2020 51 / 55

 Analyse de sensibilité

Illustration sur exemple

e1 e2 e3 x1 x2
1 − 25 7
2 0 0 27
2
1
0 3 − 32 0 1 5
0 − 61 5
2 1 0 15
2
0 − 31 − 11
3 0 0 f − 65
L’optimum est :

27 15
(e1∗ = ; x2∗ = 5 ; x1∗ = ; e2∗ = e3∗ = 0)
2 2

Essadek Recherche Opérationnelle 2019/2020 51 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Supposons qu’on veut étudier la variation du coefficient du paramètre

x1 .
On remplace le coefficient 6 par un paramètre c1 dans f

cBT∗ = (0, 4, c1 ) cHT ∗ = (0, 0)

La solution optimale est xB∗ ∗ = (e1∗ , x2∗ , x1∗ ) xH∗ ∗ = (e3∗ , e2∗ )
7
− 52
 
2
A∗H ∗ =  − 32 1
3

5
6 − 16

Essadek Recherche Opérationnelle 2019/2020 52 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Supposons qu’on veut étudier la variation du coefficient du paramètre

x1 .
On remplace le coefficient 6 par un paramètre c1 dans f

cBT∗ = (0, 4, c1 ) cHT ∗ = (0, 0)

La solution optimale est xB∗ ∗ = (e1∗ , x2∗ , x1∗ ) xH∗ ∗ = (e3∗ , e2∗ )
7
− 52
 
2
A∗H ∗ =  − 32 1
3

5
6 − 16

Essadek Recherche Opérationnelle 2019/2020 52 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Supposons qu’on veut étudier la variation du coefficient du paramètre

x1 .
On remplace le coefficient 6 par un paramètre c1 dans f

cBT∗ = (0, 4, c1 ) cHT ∗ = (0, 0)

La solution optimale est xB∗ ∗ = (e1∗ , x2∗ , x1∗ ) xH∗ ∗ = (e3∗ , e2∗ )
7
− 52
 
2
A∗H ∗ =  − 32 1
3

5
6 − 16

Essadek Recherche Opérationnelle 2019/2020 52 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Supposons qu’on veut étudier la variation du coefficient du paramètre

x1 .
On remplace le coefficient 6 par un paramètre c1 dans f

cBT∗ = (0, 4, c1 ) cHT ∗ = (0, 0)

La solution optimale est xB∗ ∗ = (e1∗ , x2∗ , x1∗ ) xH∗ ∗ = (e3∗ , e2∗ )
7
− 52
 
2
A∗H ∗ =  − 32 1
3

5
6 − 16

Essadek Recherche Opérationnelle 2019/2020 52 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Supposons qu’on veut étudier la variation du coefficient du paramètre

x1 .
On remplace le coefficient 6 par un paramètre c1 dans f

cBT∗ = (0, 4, c1 ) cHT ∗ = (0, 0)

La solution optimale est xB∗ ∗ = (e1∗ , x2∗ , x1∗ ) xH∗ ∗ = (e3∗ , e2∗ )
7
− 52
 
2
A∗H ∗ =  − 32 1
3

5
6 − 16

Essadek Recherche Opérationnelle 2019/2020 52 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Les coûts réduits sont :

8 5 c1 4
LTH ∗ = cHT ∗ − cBT∗ A∗H ∗ = ( − c1 , − )
3 6 6 3
La condition d’optimalité LTH ∗ ≤ 0 donne

16
≤ c1 ≤ 8
5
16
Donc si on choisit 5 ≤ c1 ≤ 8, la solution optimale reste inchangée.

Essadek Recherche Opérationnelle 2019/2020 53 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Les coûts réduits sont :

8 5 c1 4
LTH ∗ = cHT ∗ − cBT∗ A∗H ∗ = ( − c1 , − )
3 6 6 3
La condition d’optimalité LTH ∗ ≤ 0 donne

16
≤ c1 ≤ 8
5
16
Donc si on choisit 5 ≤ c1 ≤ 8, la solution optimale reste inchangée.

Essadek Recherche Opérationnelle 2019/2020 53 / 55

 Analyse de sensibilité

Analyse post-optimale de l’objectif

Les coûts réduits sont :

8 5 c1 4
LTH ∗ = cHT ∗ − cBT∗ A∗H ∗ = ( − c1 , − )
3 6 6 3
La condition d’optimalité LTH ∗ ≤ 0 donne

16
≤ c1 ≤ 8
5
16
Donc si on choisit 5 ≤ c1 ≤ 8, la solution optimale reste inchangée.

Essadek Recherche Opérationnelle 2019/2020 53 / 55

 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

Condition de faisabilité
xB ∗ = A−1
B∗ b ≥ 0

Avec l’exemple précédent, on veut examiner la sensibilité de la

solution optimale par rapport à la deuxième contrainte. Pour cela, on
introduit le paramètre d2 ,
 
81
d =  d2 
20

Essadek Recherche Opérationnelle 2019/2020 54 / 55

 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

Condition de faisabilité
xB ∗ = A−1
B∗ b ≥ 0

Avec l’exemple précédent, on veut examiner la sensibilité de la

solution optimale par rapport à la deuxième contrainte. Pour cela, on
introduit le paramètre d2 ,
 
81
d =  d2 
20

Essadek Recherche Opérationnelle 2019/2020 54 / 55

 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

Condition de faisabilité
xB ∗ = A−1
B∗ b ≥ 0

Avec l’exemple précédent, on veut examiner la sensibilité de la

solution optimale par rapport à la deuxième contrainte. Pour cela, on
introduit le paramètre d2 ,
 
81
d =  d2 
20

Essadek Recherche Opérationnelle 2019/2020 54 / 55

 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

A−1 −1 −1
B ∗ = AB2 AB1
On a alors
1 − 25 7
  
2 81
xB ∗ = A−1
B∗ d =
 0 1
3 − 32   d2 
0 − 61 5
6
20
Donc
e1∗ 151 − 25 d2
   

xB ∗ =  x2∗  =  1
3 (d2 − 40)

x1∗ 1
6 (−d2 + 100)

xB ∗ ≥ 0 ⇒ 40 ≤ d2 ≤ 60, 4
Donc si on choisit d2 de cette manière alors la solution de base
réalisable xB ∗ est optimale.
Essadek Recherche Opérationnelle 2019/2020 55 / 55
 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

A−1 −1 −1
B ∗ = AB2 AB1
On a alors
1 − 25 7
  
2 81
xB ∗ = A−1
B∗ d =
 0 1
3 − 32   d2 
0 − 61 5
6
20
Donc
e1∗ 151 − 52 d2
   

xB ∗ =  x2∗  =  1
3 (d2 − 40)

x1∗ 1
6 (−d2 + 100)

xB ∗ ≥ 0 ⇒ 40 ≤ d2 ≤ 60, 4
Donc si on choisit d2 de cette manière alors la solution de base
réalisable xB ∗ est optimale.
Essadek Recherche Opérationnelle 2019/2020 55 / 55
 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

A−1 −1 −1
B ∗ = AB2 AB1
On a alors
1 − 25 7
  
2 81
xB ∗ = A−1
B∗ d =
 0 1
3 − 32   d2 
0 − 61 5
6
20
Donc
e1∗ 151 − 52 d2
   

xB ∗ =  x2∗  =  1
3 (d2 − 40)

x1∗ 1
6 (−d2 + 100)

xB ∗ ≥ 0 ⇒ 40 ≤ d2 ≤ 60, 4
Donc si on choisit d2 de cette manière alors la solution de base
réalisable xB ∗ est optimale.
Essadek Recherche Opérationnelle 2019/2020 55 / 55
 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

A−1 −1 −1
B ∗ = AB2 AB1
On a alors
1 − 25 7
  
2 81
xB ∗ = A−1
B∗ d =
 0 1
3 − 32   d2 
0 − 61 5
6
20
Donc
e1∗ 151 − 52 d2
   

xB ∗ =  x2∗  =  1
3 (d2 − 40)

x1∗ 1
6 (−d2 + 100)

xB ∗ ≥ 0 ⇒ 40 ≤ d2 ≤ 60, 4
Donc si on choisit d2 de cette manière alors la solution de base
réalisable xB ∗ est optimale.
Essadek Recherche Opérationnelle 2019/2020 55 / 55
 Analyse de sensibilité

Analyse post-optimale du second membre des

contraintes

A−1 −1 −1
B ∗ = AB2 AB1
On a alors
1 − 25 7
  
2 81
xB ∗ = A−1
B∗ d =
 0 1
3 − 32   d2 
0 − 61 5
6
20
Donc
e1∗ 151 − 52 d2
   

xB ∗ =  x2∗  =  1
3 (d2 − 40)

x1∗ 1
6 (−d2 + 100)

xB ∗ ≥ 0 ⇒ 40 ≤ d2 ≤ 60, 4
Donc si on choisit d2 de cette manière alors la solution de base
réalisable xB ∗ est optimale.
Essadek Recherche Opérationnelle 2019/2020 55 / 55