Exercices de révision: Méthode du Simplexe

Recherche Opérationnelle 1 / 41
 Résolution d’un programme linéaire canonique

Exemple 1 : Résolution d’un programme linéaire par la

méthode du simplexe

Maximiser z = 1200x1 + 1000x2

Sous contraintes 3x1 + 4x2 ≤ 160
6x1 + 3x2 ≤ 180
x1 ≥ 0, x2 ≥ 0

Recherche Opérationnelle 2 / 41
 Résolution d’un programme linéaire canonique Ecriture du programme sous forme standards

Ecriture du programme sous forme standards

Maximiser z = 1200x1 + 1000x2 + 0.t1 + 0.t2

Sous contraintes 3x1 + 4x2 + t1 = 160
6x1 + 3x2 + t2 = 180
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0

Recherche Opérationnelle 3 / 41
 Résolution d’un programme linéaire canonique Initialisation

Initialisation

Maximiser z = 1200x1 + 1000x2 + 0.t1 + 0.t2

Sous contraintes 3x1 + 4x2 + t1 = 160
6x1 + 3x2 + t2 = 180
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0

Recherche Opérationnelle 4 / 41
 Résolution d’un programme linéaire canonique Initialisation

Initialisation

Maximiser z = 1200x1 + 1000x2 + 0.t1 + 0.t2

Sous contraintes 3x1 + 4x2 + t1 = 160
6x1 + 3x2 + t2 = 180
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0
la solution de base réalisable initiale est

Recherche Opérationnelle 4 / 41
 Résolution d’un programme linéaire canonique Initialisation

Initialisation

Maximiser z = 1200x1 + 1000x2 + 0.t1 + 0.t2

Sous contraintes 3x1 + 4x2 + t1 = 160
6x1 + 3x2 + t2 = 180
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0
la solution de base réalisable initiale est
 
0
 0 
 
 160 
180

Recherche Opérationnelle 4 / 41
 Résolution d’un programme linéaire canonique Initialisation

Initialisation

Maximiser z = 1200x1 + 1000x2 + 0.t1 + 0.t2

Sous contraintes 3x1 + 4x2 + t1 = 160
6x1 + 3x2 + t2 = 180
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0
la solution de base réalisable initiale est
 
0
 0 
 
 160 
180

Et la fonction objectif initiale est alors

Recherche Opérationnelle 4 / 41
 Résolution d’un programme linéaire canonique Initialisation

Initialisation

Maximiser z = 1200x1 + 1000x2 + 0.t1 + 0.t2

Sous contraintes 3x1 + 4x2 + t1 = 160
6x1 + 3x2 + t2 = 180
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0
la solution de base réalisable initiale est
 
0
 0 
 
 160 
180

Et la fonction objectif initiale est alors z0 = 1200 × 0 + 1000 × 0 = 0

Recherche Opérationnelle 4 / 41
 Résolution d’un programme linéaire canonique Tableau 0

Tableau 0

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 -z=0

Recherche Opérationnelle 5 / 41
 Résolution d’un programme linéaire canonique L’algorithme du simplexe

L’algorithme du simplexe

Recherche Opérationnelle 6 / 41
 Résolution d’un programme linéaire canonique L’algorithme du simplexe

L’algorithme du simplexe

Former le premier tableau du simplexe.

Recherche Opérationnelle 6 / 41
 Résolution d’un programme linéaire canonique L’algorithme du simplexe

L’algorithme du simplexe

Former le premier tableau du simplexe.

Vérifier si le test d’arrêt est vérifié.

Recherche Opérationnelle 6 / 41
 Résolution d’un programme linéaire canonique L’algorithme du simplexe

L’algorithme du simplexe

Former le premier tableau du simplexe.

Vérifier si le test d’arrêt est vérifié.
Sinon, faire le tableau suivant et changer de base.

Recherche Opérationnelle 6 / 41
 Conditions du tableau du simplexe

Conditions du tableau du simplexe

A chaque itération les conditions suivantes doivent être vérifiées :

Recherche Opérationnelle 7 / 41
 Conditions du tableau du simplexe

Conditions du tableau du simplexe

A chaque itération les conditions suivantes doivent être vérifiées :

La base est réalisable (les éléments de la dernière colonne sont positifs
ou nuls).

Recherche Opérationnelle 7 / 41
 Conditions du tableau du simplexe

Conditions du tableau du simplexe

A chaque itération les conditions suivantes doivent être vérifiées :

La base est réalisable (les éléments de la dernière colonne sont positifs
ou nuls).
Les variables de base sont listées sur la première colonne.

Recherche Opérationnelle 7 / 41
 Conditions du tableau du simplexe

Conditions du tableau du simplexe

A chaque itération les conditions suivantes doivent être vérifiées :

La base est réalisable (les éléments de la dernière colonne sont positifs
ou nuls).
Les variables de base sont listées sur la première colonne.
La case en bas à droite vaut −z

Recherche Opérationnelle 7 / 41
 Conditions du tableau du simplexe

Conditions du tableau du simplexe

A chaque itération les conditions suivantes doivent être vérifiées :

La base est réalisable (les éléments de la dernière colonne sont positifs
ou nuls).
Les variables de base sont listées sur la première colonne.
La case en bas à droite vaut −z
Les coûts des variables de base sont nuls.

Recherche Opérationnelle 7 / 41
 Conditions du tableau du simplexe Critère de sélection de la variable entrant dans la base :

Critère de sélection de la variable entrant dans la base

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Recherche Opérationnelle 8 / 41
 Conditions du tableau du simplexe Critère de sélection de la variable sortante de la base :

Critère de sélection de la variable sortante de la base

vb x1 x2 t1 t2 C R
160
t1 3 4 1 0 160 3
t2 6 3 0 1 180 30
4 1200 1000 0 0 −z0 = 0

Recherche Opérationnelle 9 / 41
 Conditions du tableau du simplexe Critère de sélection de la variable sortante de la base :

Critère de sélection de la variable sortante de la base

vb x1 x2 t1 t2 C R
160
t1 3 4 1 0 160 3
t2 6 3 0 1 180 30
4 1200 1000 0 0 −z0 = 0

vb x1 x2 t1 t2 C R
160
t1 3 4 1 0 160 3
t2 6 3 0 1 180 30
4 1200 1000 0 0 −z0 = 0

Recherche Opérationnelle 9 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Recherche Opérationnelle 10 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

vb x1 x2 t1 t2 C
t1 0
1 1
x1 1 2 0 6 30
4 0

Recherche Opérationnelle 10 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Pour les autres valeurs du tableau procéder comme suit à partir du tableau
précédent :
CCP ∗ CLP
NV = AV −
P
Avec :

Recherche Opérationnelle 11 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Pour les autres valeurs du tableau procéder comme suit à partir du tableau
précédent :
CCP ∗ CLP
NV = AV −
P
Avec :
NV : Nouvelle Valeur de la case considérée du tableau

Recherche Opérationnelle 11 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Pour les autres valeurs du tableau procéder comme suit à partir du tableau
précédent :
CCP ∗ CLP
NV = AV −
P
Avec :
NV : Nouvelle Valeur de la case considérée du tableau
AV : Ancienne Valeur de la case considérée du tableau

Recherche Opérationnelle 11 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Pour les autres valeurs du tableau procéder comme suit à partir du tableau
précédent :
CCP ∗ CLP
NV = AV −
P
Avec :
NV : Nouvelle Valeur de la case considérée du tableau
AV : Ancienne Valeur de la case considérée du tableau
CCP : Coefficient précédent de la colonne pivot situé sur la même
ligne que AV

Recherche Opérationnelle 11 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Pour les autres valeurs du tableau procéder comme suit à partir du tableau
précédent :
CCP ∗ CLP
NV = AV −
P
Avec :
NV : Nouvelle Valeur de la case considérée du tableau
AV : Ancienne Valeur de la case considérée du tableau
CCP : Coefficient précédent de la colonne pivot situé sur la même
ligne que AV
CLP : Coefficient précédent de la ligne pivot situé sur la même
Colonne que AV

Recherche Opérationnelle 11 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Pour les autres valeurs du tableau procéder comme suit à partir du tableau
précédent :
CCP ∗ CLP
NV = AV −
P
Avec :
NV : Nouvelle Valeur de la case considérée du tableau
AV : Ancienne Valeur de la case considérée du tableau
CCP : Coefficient précédent de la colonne pivot situé sur la même
ligne que AV
CLP : Coefficient précédent de la ligne pivot situé sur la même
Colonne que AV
P : Valeur précédente du pivot.

Recherche Opérationnelle 11 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6 30
4

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6 30
4 0

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6 30
4 0 400

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Calcul du tableau suivant

Tableau 1

vb x1 x2 t1 t2 C
t1 3 4 1 0 160
t2 6 3 0 1 180
4 1200 1000 0 0 −z0 = 0

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 − 1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000

Recherche Opérationnelle 12 / 41
 Conditions du tableau du simplexe Test d’arrêt

condition suffisante d’optimalité

Théorème (condition suffisante d’optimalité)

Considérons un programme linéaire sous forme canonique par rapport à

une base réalisable I. Si les coûts sur la ligne 4 correspondant aux
variables hors base sont négatifs ou nuls alors la solution de base I est la
solution optimale et l’objectif à l’optimum est z0 .

Recherche Opérationnelle 13 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000

Recherche Opérationnelle 14 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000

vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000

Recherche Opérationnelle 14 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000

Recherche Opérationnelle 15 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000

vb x1 x2 t1 t2 C R
t1 0 5/2 1 −1/2 70 28
x1 1 1/2 0 1/6 30 60
4 0 400 0 -200 −36000

Recherche Opérationnelle 15 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2

Recherche Opérationnelle 16 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 1

Recherche Opérationnelle 16 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Tableau 2

Tableau 1
vb x1 x2 t1 t2 C
t1 0 5/2 1 −1/2 70
x1 1 1/2 0 1/6 30
4 0 400 0 -200 −36000
Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200

Recherche Opérationnelle 17 / 41
Conditions du tableau du simplexe Solution optimale

Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200

Recherche Opérationnelle 18 / 41
Conditions du tableau du simplexe Solution optimale

Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200
x1 = 16,

Recherche Opérationnelle 18 / 41
Conditions du tableau du simplexe Solution optimale

Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200
x1 = 16, x2 = 28,

Recherche Opérationnelle 18 / 41
Conditions du tableau du simplexe Solution optimale

Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200
x1 = 16, x2 = 28, t1 = 0,

Recherche Opérationnelle 18 / 41
Conditions du tableau du simplexe Solution optimale

Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200
x1 = 16, x2 = 28, t1 = 0, t2 = 0

Recherche Opérationnelle 18 / 41
Conditions du tableau du simplexe Solution optimale

Tableau2
VB x1 x2 t1 t2 C
x2 0 1 2/5 −1/5 28
x1 1 0 −1/5 4/15 16
4 0 0 -160 -120 −47200
x1 = 16, x2 = 28, t1 = 0, t2 = 0

z0p = 47200

Recherche Opérationnelle 18 / 41
 Infinité de solution

Exemple 2 : Résolution d’un programme linéaire admettant

une infinité de solution

Maximiser z = x1 + 2x2
Sous contraintes −3x1 + 2x2 ≤ 2
x1 + 2x2 ≤ 4
−x1 + x2 ≤ 5
x1 ≥ 0, x2 ≥ 0,

Recherche Opérationnelle 19 / 41
 Infinité de solution

Exemple 2 : Résolution d’un programme linéaire admettant

une infinité de solution

Maximiser z = x1 + 2x2
Sous contraintes −3x1 + 2x2 ≤ 2
x1 + 2x2 ≤ 4
−x1 + x2 ≤ 5
x1 ≥ 0, x2 ≥ 0,
Écriture sous forme standard :

Maximiser z = x1 + 2x2 + 0t1 + 0t2 + 0t3

Sous contraintes −3x1 + 2x2 + t1 = 2
x1 + 2x2 + t2 = 4
−x1 + x2 + t3 = 5
x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0, t3 ≥ 0

Recherche Opérationnelle 19 / 41
 Infinité de solution

Maximiser z = x1 + 2x2 + 0t1 + ot2

Sous contraintes −3x1 + 2x2 + t1 = 2
x1 + 2x2 + t2 = 4
−x1 + x2 + t3 = 5
x1 ≥ 0, x2 ≥ 0,

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2
t2 1 2 0 1 0 4
t3 -1 1 0 0 1 5
4 1 2 0 0 0 -z0=0

Recherche Opérationnelle 20 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2
t2 1 2 0 1 0 4
t3 -1 1 0 0 1 5
4 1 2 0 0 0 -z0=0

Recherche Opérationnelle 21 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2
t2 1 2 0 1 0 4
t3 -1 1 0 0 1 5
4 1 2 0 0 0 -z0=0

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Recherche Opérationnelle 21 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
t3

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4 4

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4 4 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4 4 0 -1

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4 4 0 -1 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4 4 0 -1 0 0

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau0
x1 x2 t1 t2 t3 C R
t1 -3 2 1 0 0 2 1
t2 1 2 0 1 0 4 2
t3 -1 1 0 0 1 5 5
4 1 2 0 0 0 -z0=0

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1
t2 4 0 -1 1 0 2
1
t3 2 0 − 12 0 1 4
4 4 0 -1 0 0 -z0=-2

Recherche Opérationnelle 22 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
x2

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
x2 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
x2 0 1

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1
x2 0 1 8

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3
x2 0 1 8 8

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3
x2 0 1 8 8 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4 0 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4 0 0 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4 0 0 0 -1

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4 0 0 0 -1 0

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4
x1 1 0 − 14 1
4 0 1
2
t3 0 0 − 38 - 18 1 15
4
4 0 0 0 -1 0 -z0=-4

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 1 7
x1 1 0 − 14 1
4 0 1
2 ⇒ M1 = ( , )
2 4
t3 0 0 − 38 - 18 1 15
4
4 0 0 0 -1 0 -z0=-4

Recherche Opérationnelle 23 / 41
 Infinité de solution

Tableau1
x1 x2 t1 t2 t3 C R
x2 − 32 1 1
2 0 0 1 − 23
1
t2 4 0 -1 1 0 2 2
1
t3 2 0 − 21 0 1 4 8
4 4 0 -1 0 0 -z0=-2

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 1 7
x1 1 0 − 14 1
4 0 1
2 ⇒ M1 = ( , ) Z0 = 4
2 4
t3 0 0 − 38 - 18 1 15
4
4 0 0 0 -1 0 -z0=-4

Recherche Opérationnelle 23 / 41
 Infinité de solution

Théorème (Infinité de solutions)

Si, à la fin des itérations, une variable est HB avec un coefficient nul dans
la ligne 4, alors on a une arête (plan,...) optimale. Les autres sommets
solutions sont obtenus en faisant rentrer cette variable dans la base.

Recherche Opérationnelle 24 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1 9
4

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1 9
4 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1 9
4 0 -4

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1 9
4 0 -4 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1 9
4 0 -4 0 -1

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4
t3 0 3 0 1 1 9
4 0 -4 0 -1 0

Recherche Opérationnelle 25 / 41
 Infinité de solution

Tableau2
x1 x2 t1 t2 t3 C R
1 3 7
x2 0 1 8 8 0 4 14
x1 1 0 − 14 1
4 0 1
2 -2
t3 0 0 − 38 - 81 1 15
4 -10
4 0 0 0 -1 0 -z0=-4

Tableau3
x1 x2 t1 t2 t3 C R
t1 0 8 1 3 0 14
x1 1 2 0 1 0 4 ⇒ M2 = (4, 0)
t3 0 3 0 1 1 9
4 0 -4 0 -1 0 -z0=-4

Recherche Opérationnelle 25 / 41
 Résolution d’un programme linéaire quelconque Principe

Exemple 3 : Résolution d’un programme linéaire

quelconque

Maximiser z = 2x1 + 5x2

Sous contraintes 8x1 + 4x2 ≥ 40
x1 + 5x2 ≥ 10
x1 ≥ 0, x2 ≥ 0

Recherche Opérationnelle 26 / 41
 Résolution d’un programme linéaire quelconque Principe

Exemple 3 : Résolution d’un programme linéaire

quelconque

Maximiser z = 2x1 + 5x2

Sous contraintes 8x1 + 4x2 ≥ 40
x1 + 5x2 ≥ 10
x1 ≥ 0, x2 ≥ 0

Maximiser z = 2x1 + 5x2

Sous contraintes 8x1 + 4x2 − t1 = 40
x1 + 5x2 − t2 = 10
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0

Recherche Opérationnelle 26 / 41
 Résolution d’un programme linéaire quelconque Principe

La matrice  
8 4 −1 0
A=
1 5 0 −1

Recherche Opérationnelle 27 / 41
 Résolution d’un programme linéaire quelconque Principe

Le programme artificielle associé est

Minimiser w = k1 + k2
Sous contraintes 8x1 + 4x2 − t1 + k1 = 40
x1 + 5x2 − t2 + k2 = 10
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 k1 ≥ 0, k2 ≥ 0

Recherche Opérationnelle 28 / 41
 Résolution d’un programme linéaire quelconque Principe

Le programme artificielle associé est

Minimiser w = k1 + k2
Sous contraintes 8x1 + 4x2 − t1 + k1 = 40
x1 + 5x2 − t2 + k2 = 10
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 k1 ≥ 0, k2 ≥ 0

m
k1 et k2 sont des variables artificielles

Maximiser (−w ) = −k1 − k2

Sous contraintes 8x1 + 4x2 − t1 + k1 = 40
x1 + 5x2 − t2 + k2 = 10
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 k1 ≥ 0, k2 ≥ 0

Recherche Opérationnelle 28 / 41
 Résolution d’un programme linéaire quelconque Principe

Maximiser (−$) = −k1 −k2 ⇔ Maximiser (−$) = 9x1 +9x2 −t1 −t2 −50

Recherche Opérationnelle 29 / 41
Résolution d’un programme linéaire quelconque Principe

   
8 4 −1 0 1 0 40
A= et b =
1 5 0 −1 0 1 10
Maximiser (−$) = 9x1 + 9x2 − t1 − t2 − 50

Recherche Opérationnelle 30 / 41
Résolution d’un programme linéaire quelconque Principe

   
8 4 −1 0 1 0 40
A= et b =
1 5 0 −1 0 1 10
Maximiser (−$) = 9x1 + 9x2 − t1 − t2 − 50

x1 x2 t1 t2 k1 k2 C
k1 8 4 −1 0 1 0 40
Tableau 0 :
k2 1 5 0 −1 0 1 10
4 9 9 -1 -1 0 0 50

Recherche Opérationnelle 30 / 41
Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50

Recherche Opérationnelle 31 / 41
Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50

Recherche Opérationnelle 31 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0 9/2

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0 9/2 1/8

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0 9/2 1/8 -1

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0 9/2 1/8 -1 −9/8

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0 9/2 1/8 -1 −9/8 0

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
k1 8 4 −1 0 1 0 40 5
Tableau 0 :
k2 1 5 0 −1 0 1 10 10
4 9 9 -1 -1 0 0 50
x1 x2 t1 t2 k1 k2 C
x1 1 1/2 −1/8 0 1/8 0 5
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5
4 0 9/2 1/8 -1 −9/8 0 5

Recherche Opérationnelle 32 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

Recherche Opérationnelle 33 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

Recherche Opérationnelle 33 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0 −1

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0 −1 -1

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C R
x1 1 1/2 −1/8 0 1/8 0 5 10
Tableau 1 :
k2 0 9/2 1/8 −1 −1/8 1 5 10/9
4 0 9/2 1/8 -1 −9/8 0 5

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0 −1 -1 0

Recherche Opérationnelle 34 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0 −1 -1 0

Recherche Opérationnelle 35 / 41
 Résolution d’un programme linéaire quelconque Principe

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0 −1 -1 0

Proposition
Supposons que l’objectif réalisé à l’optimum du programme artificiel soit
$0 = 0. La solution optimale du programme artificiel fournit une première
base réalisable au programme linéraire initial si et seulement si aucune
variable artificielle n’est en base.

Recherche Opérationnelle 35 / 41
 Résolution d’un programme linéaire quelconque Première solution de base

x1 x2 t1 t2 k1 k2 C
x1 1 0 −5/36 1/9 5/36 -1/9 40/9
Tableau 2 :
x2 0 1 1/36 −2/9 −1/36 2/9 10/9
4 0 0 0 0 −1 -1 0

Maximiser z = 2x1 + 5x2 (1)

5 1 40
Sous contraintes x1 − t1 + t2 = (2)
36 9 9
1 2 10
x2 + t1 − t2 = (3)
36 9 9
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 (4)

Recherche Opérationnelle 36 / 41
Résolution d’un programme linéaire quelconque Première solution de base

Maximiser z = 2x1 + 5x2 (5)

5 1 40
Sous contraintes x1 − t1 + t2 = (6)
36 9 9
1 2 10
x2 + t1 − t2 = (7)
36 9 9
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 (8)

Recherche Opérationnelle 37 / 41
Résolution d’un programme linéaire quelconque Première solution de base

Maximiser z = 2x1 + 5x2 (5)

5 1 40
Sous contraintes x1 − t1 + t2 = (6)
36 9 9
1 2 10
x2 + t1 − t2 = (7)
36 9 9
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 (8)

5 1 40 5 1 40
x1 − t1 + t2 = ⇔ x1 = t1 − t2 +
36 9 9 36 9 9
1 2 10 1 2 10
x2 + t1 − t2 = ⇔ x2 = − t1 + t2 +
36 9 9 36 9 9

Recherche Opérationnelle 37 / 41
Résolution d’un programme linéaire quelconque Première solution de base

Maximiser z = 2x1 + 5x2 (5)

5 1 40
Sous contraintes x1 − t1 + t2 = (6)
36 9 9
1 2 10
x2 + t1 − t2 = (7)
36 9 9
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 (8)

5 1 40 5 1 40
x1 − t1 + t2 = ⇔ x1 = t1 − t2 +
36 9 9 36 9 9
1 2 10 1 2 10
x2 + t1 − t2 = ⇔ x2 = − t1 + t2 +
36 9 9 36 9 9
5 8 130
z= t1 + t2 +
36 9 9

Recherche Opérationnelle 37 / 41
Résolution d’un programme linéaire quelconque Première solution de base

5 8 130
Maximiser z= t1 + t2 + (9)
36 9 9
5 1 40
Sous contraintes x1 − t1 + t2 = (10)
36 9 9
1 2 10
x2 + t1 − t2 = (11)
36 9 9
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 (12)

Recherche Opérationnelle 38 / 41
Résolution d’un programme linéaire quelconque Première solution de base

5 8 130
Maximiser z= t1 + t2 + (9)
36 9 9
5 1 40
Sous contraintes x1 − t1 + t2 = (10)
36 9 9
1 2 10
x2 + t1 − t2 = (11)
36 9 9
x1 ≥ 0, x2 ≥ 0 t1 ≥ 0, t2 ≥ 0 (12)

x1 x2 t1 t2 C
x1 1 0 −5/36 1/9 40/9
Tableau 0 :
x2 0 1 1/36 −2/9 10/9
4 0 0 5/36 8/9 -130/9

Recherche Opérationnelle 38 / 41
Résolution d’un programme linéaire quelconque Première solution de base

x1 x2 t1 t2 C R
x1 1 0 −5/36 1/9 40/9 40
Tableau 0 :
x2 0 1 1/36 −2/9 10/9 -5
4 0 0 5/36 8/9 -130/9

Recherche Opérationnelle 39 / 41
Résolution d’un programme linéaire quelconque Première solution de base

x1 x2 t1 t2 C R
x1 1 0 −5/36 1/9 40/9 40
Tableau 0 :
x2 0 1 1/36 −2/9 10/9 -5
4 0 0 5/36 8/9 -130/9

x1 x2 t1 t2 C
t2 9 0 −5/4 1 40
Tableau 1 :
x2 2 1 −1/4 0 10
4 -8 0 5/4 0 -50

Recherche Opérationnelle 39 / 41
 Résolution d’un programme linéaire quelconque Première solution de base

x1 x2 t1 t2 C
t2 9 0 −5/4 1 40
Tableau 1 :
x2 2 1 −1/4 0 10
4 -8 0 5/4 0 -50

S’il existe une variable hors base dont le coût sur la ligne 4 est positif
et tous les autres coefficients de la colonne de cette variable sont
négatifs ou nuls alors le programme linéaire n’est pas borné, la
solution est donc l’infini.

Recherche Opérationnelle 40 / 41