Chapitre 3:
Programma-
tion Linéaire,
Dualité
Abdelaziz
CHE-
TOUANI
Sommaire
Chapitre 3: Programmation Linéaire, Dualité
Abdelaziz CHETOUANI
École Nationale de Commerce et de Gestion - Oujda
Département de commerce
Recherche opérationnelle
1er décembre 2020
1/9
Sommaire
Chapitre 3:
Programma-
tion Linéaire,
Dualité
Abdelaziz
CHE-
TOUANI
Sommaire
• Il s'agit de résoudre un problème de minimisation.
• Dans le cas de deux variables, la méthode graphique peut être
utilisée.
• Mais dans le cas de plus de deux variables, la méthode du
simplexe devient "lourde" à appliquer.
3/9
Sommaire
Chapitre 3: Résolution par passage au dual
Programma-
tion Linéaire,
Dualité
Considérons le problème linéaire suivant :
Abdelaziz
CHE- Min Z = 90u1 + 8u2 + 50u3
TOUANI
Sommaire
sous les contraines :
2u1 + u2 + u3 ≥ 12
u1 + 2u2 + u3 ≥ 10
u1 , u2 , u3 ≥ 0
Pour résoudre ce P.L., on peut utiliser la dualité qui consiste à :
• Trouver le dual de ce P. L. qui est un problème de maximisation ;
• Résoudre le dual.
• Appliquer des théorèmes pour trouver la solution optimale du
P.L. initial.
Dé nition
Le P.L. initial s'appelle :le primal
4/9
Sommaire
Chapitre 3:
Programma-
tion Linéaire,
Passage du primal au dual
Dualité
Pour déterminer le dual du primal, on eectue les changements suivants :
Abdelaziz
CHE- • Le nombre de variables du dual est égal au nombre de contraintes du primal
TOUANI (autres que les contraintes de positivité). Elles doivent être diérenciées de
celles du primal.
Sommaire
• Le nombre de contraintes du dual est égal au nombre de variables du primal.
• Les coe cients des colonnes (respectivement lignes) de la matrice des
Contraintes du primal sont les coe cients des lignes (respectivement
colonnes ) de la matrice du contraintes du dual.
• Les inégalités du dual sont de sens opposé à celles du primal.
• Les coe cients de la fonction économique du primal sont les coe cients de
second membre des contraintes du dual.
• Les coe cients du second membre du contraintes du primal sont les
coe cients de la fonction économique du dual.
• Si le primal est une minimisation, le dual est une maximisation et
inversement.
• Les variables des deux problèmes sont positives ou nulles.
5/9
Sommaire
Chapitre 3:
Programma-
tion Linéaire,
Dualité
Abdelaziz
CHE- Passage du primal au dual
TOUANI
En appliquant ces règles de transformations on obtient :
Sommaire
Donc pour résoudre notre primal, il su t de résoudre son dual puis appliquer les
théorèmes suivants
6/9
Sommaire
Chapitre 3:
Programma-
tion Linéaire,
Dualité
Abdelaziz
CHE-
TOUANI
Théorème 1
Si le primal admet une solution, le dual en admet une également et le maximum
Sommaire de l'un est égal au minimum de l'autre.
Théorème 2
Si la ième variable (variable réelle) est non nulle à l'optimum du primal, alors la
ième contrainte du dual est saturée à l'optimum.
Théorème 3
Si la ième contrainte du primal est non saturée à l'optimum, alors la ième variable
est nulle à l'optimum du dual .
7/9
Sommaire
Chapitre 3:
Programma-
tion Linéaire,
Dualité
Résolution
Abdelaziz • On a le dual P.L.2 admet une solution optimale et max Z = 580. Donc
CHE-
TOUANI
d'après le théorème 1 on peut a rmer que le primal en admet une
également et min Z = 580.
Sommaire
• A l'optimum du dual, on a trouvé que la solution optimale est donnée par
(x1∗ = 40, x2∗ = 10)
• x1∗ 6= 0 et x2∗ 6= 0
• Par application du théorème 2, on en déduit que la 1ère et la 2ème
contraintes du primal sont saturées à l'optimum.
• C-à-d à l'optimum du primal, on a :
2u1 + u2 + u3 = 12
(S)
u1 + 2u2 + u3 = 10
• A l'optimum du dual, on a la 2ème contrainte est non saturée
(e2 = 20 6= 0). Par application du théorème 3, on en déduit qu' à
l'optimum du primal, la 2ème variable u2 = 0.
8/9
Sommaire
Chapitre 3:
Programma-
tion Linéaire,
Dualité
Abdelaziz
CHE-
TOUANI
Sommaire
Résolution
Donc (S) devient :
2u1 + u3 = 12
(S)
u1 + u3 = 10
Solution optimale du primal pour laquelle min Z = 580
9/9
