Chapitre 3 - Programmation Linéaire, Dualité [PDF]

Zitiervorschau

Chapitre 3: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

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: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

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: Programmation Linéaire, Dualité

Résolution par passage au dual Considérons le problème linéaire suivant : Min Z = 90u1 + 8u2 + 50u3

Abdelaziz CHETOUANI

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: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

Sommaire

Passage du primal au dual Pour déterminer le dual du primal, on eectue les changements suivants :

• Le nombre de variables du dual est égal au nombre de contraintes du primal (autres que les contraintes de positivité). Elles doivent être diérenciées de celles du primal. • Le nombre de contraintes du dual est égal au nombre de variables du primal. • Les coecients des colonnes (respectivement lignes) de la matrice des Contraintes du primal sont les coecients 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 coecients de la fonction économique du primal sont les coecients de second membre des contraintes du dual. • Les coecients du second membre du contraintes du primal sont les coecients 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: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

Passage du primal au dual En appliquant ces règles de transformations on obtient :

Sommaire

Donc pour résoudre notre primal, il sut de résoudre son dual puis appliquer les théorèmes suivants

6/9

Sommaire

Chapitre 3: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

Sommaire

Théorème 1 Si le primal admet une solution, le dual en admet une également et le maximum 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: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

Sommaire

Résolution

• On a le dual P.L.2 admet une solution optimale et max Z = 580. Donc d'après le théorème 1 on peut armer que le primal en admet une également et min Z = 580. • 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 :  (S)

2u1 + u2 + u3 = 12 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: Programmation Linéaire, Dualité Abdelaziz CHETOUANI

Sommaire

Résolution Donc (S) devient :

 (S)

2u1 + u3 = 12 u1 + u3 = 10

Solution optimale du primal pour laquelle min Z = 580

9/9