0% ont trouvé ce document utile (0 vote)
64 vues31 pages

Dualité: Motivation

Transféré par

Oussama oussama
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
0% ont trouvé ce document utile (0 vote)
64 vues31 pages

Dualité: Motivation

Transféré par

Oussama oussama
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
Vous êtes sur la page 1/ 31

Dualité

Motivation

•  La dualité est une notion essentielle en programmation linéaire

•  A un programme linéaire donné que nous appelons primal, l’opération de dualité


associe un autre programme linéaire dit son dual, qui ne sera défini qu’à l’aide des
données du primal

Programme linéaire Programme linéaire


Opération de dualité
primal dual

1 Pr. MESSAOUD
Dualité
Motivation

La dualité présente un double intérêt :

!  Les propriétés liant le programme primal et son dual permettront de résoudre le


problème dual s’il est plus simple que le problème primal. Ce sera le cas, en
particulier, lorsque le problème primal n’a pas de solution admissible évidente et
on peut la construire facilement pour le problème dual

2 Pr. MESSAOUD
Dualité
Motivation

La dualité présente un double intérêt :

!  Les propriétés liant le programme primal et son dual permettront de résoudre le


problème dual s’il est plus simple que le problème primal. Ce sera le cas, en
particulier, lorsque le problème primal n’a pas de solution admissible évidente et
on peut la construire facilement pour le problème dual

!  Le programme dual a une interprétation économique importante : il constitue une


autre vision du programme primal ( exemple)

3 Pr. MESSAOUD
Dualité
Exemple (interprétation économique de la dualité)
Une usine fabrique deux produits P1 et P2 en utilisant un certain nombre de ressources. Ces
besoins sont indiqués dans le tableau suivant. Par ailleurs, chaque ressource est disponible en
quantité limitée
P1 P2 Disponibilité
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 60 DH et 40 DH
par unité. Quelles quantités de produits P1 et P2 doit produire l’usine afin de maximiser le
bénéfice total venant de la vente des 2 produits?

4 Pr. MESSAOUD
Dualité
Exemple (interprétation économique de la dualité)
Une usine fabrique deux produits P1 et P2 en utilisant un certain nombre de ressources. Ces
besoins sont indiqués dans le tableau suivant. Par ailleurs, chaque ressource est disponible en
quantité limitée
P1 P2 Disponibilité
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 60 DH et 40 DH
par unité. Quelles quantités de produits P1 et P2 doit produire l’usine afin de maximiser le
bénéfice total venant de la vente des 2 produits?

Ce problème de production se modélise sous la forme:

5 Pr. MESSAOUD
Dualité
Exemple (interprétation économique de la dualité)
Supposons à présent qu’un acheteur se présente pour acheter toutes les ressources
de l’entreprise. Il propose à l’entreprise les prix unitaires u1, u2 et u3 pour chacune
des ressources.
!  L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle
obtient un profit au moins égal au profit obtenu en vendant ses produits
!  De son côté, l’acheteur cherche à minimiser ses dépenses
Quels prix unitaires u1, u2 et u3 l’acheteur doit-il proposer à l’entreprise en question
pour qu’elle accepte de vendre toutes ses ressources

P1 P2 Disponibilité
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Dualité
Exemple (interprétation économique de la dualité)
Supposons à présent qu’un acheteur se présente pour acheter toutes les ressources
de l’entreprise. Il propose à l’entreprise les prix unitaires u1, u2 et u3 pour chacune
des ressources.
!  L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle
obtient un profit au moins égal au profit obtenu en vendant ses produits
!  De son côté, l’acheteur cherche à minimiser ses dépenses
Quels prix unitaires u1, u2 et u3 l’acheteur doit-il proposer à l’entreprise en question
pour qu’elle accepte de vendre toutes ses ressources
Soient u1, u2 et u3 les prix unitaires respectifs des produits. L’acheteur cherche donc à
minimiser le coût

P1 P2 Disponibilité
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Dualité
Exemple (interprétation économique de la dualité)
Supposons à présent qu’un acheteur se présente pour acheter toutes les ressources
de l’entreprise. Il propose à l’entreprise les prix unitaires u1, u2 et u3 pour chacune
des ressources.
!  L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle
obtient un profit au moins égal au profit obtenu en vendant ses produits
!  De son côté, l’acheteur cherche à minimiser ses dépenses
Quels prix unitaires u1, u2 et u3 l’acheteur doit-il proposer à l’entreprise en question
pour qu’elle accepte de vendre toutes ses ressources
Soient u1, u2 et u3 les prix unitaires respectifs des produits. L’acheteur cherche donc à
minimiser le coût

P1 P2 Disponibilité
Le coût total d’achat
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Dualité
Exemple (interprétation économique de la dualité)
Supposons à présent qu’un acheteur se présente pour acheter toutes les ressources
de l’entreprise. Il propose à l’entreprise les prix unitaires u1, u2 et u3 pour chacune
des ressources.
!  L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle
obtient un profit au moins égal au profit obtenu en vendant ses produits
!  De son côté, l’acheteur cherche à minimiser ses dépenses
Quels prix unitaires u1, u2 et u3 l’acheteur doit-il proposer à l’entreprise en question
pour qu’elle accepte de vendre toutes ses ressources
Soient u1, u2 et u3 les prix unitaires respectifs des produits. L’acheteur cherche donc à
minimiser le coût

P1 P2 Disponibilité
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Dualité
Exemple (interprétation économique de la dualité)
Supposons à présent qu’un acheteur se présente pour acheter toutes les ressources
de l’entreprise. Il propose à l’entreprise les prix unitaires u1, u2 et u3 pour chacune
des ressources.
!  L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle
obtient un profit au moins égal au profit obtenu en vendant ses produits
!  De son côté, l’acheteur cherche à minimiser ses dépenses
Quels prix unitaires u1, u2 et u3 l’acheteur doit-il proposer à l’entreprise en question
pour qu’elle accepte de vendre toutes ses ressources
Soient u1, u2 et u3 les prix unitaires respectifs des produits. L’acheteur cherche donc à
minimiser le coût

P1 P2 Disponibilité
Ressource A 3 9 81
Ressource B 4 5 55
Ressource C 2 1 20
Dualité
Exemple (interprétation économique de la dualité)
!  L’entreprise acceptera de lui vendre toutes ses ressources uniquement si elle
obtient un profit au moins égal au profit obtenu en vendant ses produits

!  Et il est raisonnable de penser que:

!  L’acheteur devrait résoudre le programme linéaire suivant :

11 Pr. MESSAOUD
Dualité

Programme primal Programme dual

Opération de dualité

12 Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:

On associe le programme linéaire dual:

Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:

On associe le programme linéaire dual:

Exemple:

Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:

On associe le programme linéaire dual:

Exemple:

Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:

On associe le programme linéaire dual:

Exemple:

Pr. MESSAOUD
Dualité
Règles de dualisation
Le tableau suivant donne un ensemble de règles formelles permettant de passer d’un
problème de programmation linéaire général à son problème dual:
(Le tableau n’est pas symétrique)

17 Pr. MESSAOUD
Dualité
Règles de dualisation
Le tableau suivant donne un ensemble de règles formelles permettant de passer d’un
problème de programmation linéaire général à son problème dual:
(Le tableau n’est pas symétrique)

Exemples

⎧ Max 2x1 + 4x2 + 3x3



⎪⎪3x1 + 4x2 + 2x3 ≥ 20
(P1 ) : ⎨2x1 + x2 + 2x3 ≤ 40
⎪ x + 3x + 2x = 35
⎪ 1 2 3
⎪⎩ x1 , x2 , x3 ≥ 0

18 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

1. Proposition:
Le dual du dual est le primal

19 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

1. Proposition:
Le dual du dual est le primal
Preuve

20 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

1. Proposition:
Le dual du dual est le primal
Preuve

21 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

1. Proposition:
Le dual du dual est le primal
Preuve

On prend le dual du dual

22 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

1. Proposition:
Le dual du dual est le primal
Preuve

On prend le dual du dual

23 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

1. Proposition:
Le dual du dual est le primal
Preuve

On prend le dual du dual

24 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

2. Théorème faible de dualité


Soit x une solution réalisable d’un (PL) sous forme canonique et u une solution
réalisable du problème dual (PLD). Alors:
1.  cT x ≤ bT u

2.  Si cT x = bT u alors x et u sont des solutions optimales de (PL) et (PLD)


respectivement

25 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

3. Théorème forte de dualité

Considérons le programme linéaire (PL) et son dual (PLD)

!  Si l’un des problèmes duaux admet une solution optimale finie, alors il en est de

même pour l’autre et les valeurs des fonctions objectifs à l’optimum sont égales

!  Si l’un des problèmes duaux n’est pas borné, alors l’autre est impossible

26 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

3. Théorème forte de dualité

Considérons le programme linéaire (PL) et son dual (PLD)

!  Si l’un des problèmes duaux admet une solution optimale finie, alors il en est de

même pour l’autre et les valeurs des fonctions objectifs à l’optimum sont égales

!  Si l’un des problèmes duaux n’est pas borné, alors l’autre est impossible

Remarque
Si l’un des problèmes est impossible, on ne peut pas conclure que l’objectif de l’autre
problème est non borné

27 Pr. MESSAOUD
Dualité

Etant donnés un problème primal (PL) et son dual (PLD), on a une et une seule des
trois situations suivantes:

!  Les deux problèmes possèdent des solutions optimales (a l'optimum, les coûts
sont égaux)
!  Un des problèmes est non borné, l'autre est impossible
!  Aucun des deux problèmes ne possède de solution réalisable

28 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité

4. Théorème des écarts complémentaires


Soient x et y deux solutions réalisables respectivement du problème primal (PL) et du
problème dual (PLD). Alors x et y sont des solutions réalisables optimales si et
seulement si on a:

est la ième ligne de la matrice A


est la transposée de la jème colonne de la matrice A

29 Pr. MESSAOUD
Dualité

Utilisation pratique de théorème des écarts complémentaires

!  Il permet de vérifier si une solution réalisable d'un (PL) est optimale ou non
!  Il permet de déterminer la solution optimale d'un (PL), à partir de la connaissance
d'une solution optimale de son dual

30 Pr. MESSAOUD
Dualité

31 Pr. MESSAOUD

Vous aimerez peut-être aussi