Dualité: Motivation
Dualité: Motivation
Motivation
1 Pr. MESSAOUD
Dualité
Motivation
2 Pr. MESSAOUD
Dualité
Motivation
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?
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
11 Pr. MESSAOUD
Dualité
Opération de dualité
12 Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:
Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:
Exemple:
Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:
Exemple:
Pr. MESSAOUD
Dualité
Définition:
Au programme linéaire primal suivant:
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
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
22 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité
1. Proposition:
Le dual du dual est le primal
Preuve
23 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité
1. Proposition:
Le dual du dual est le primal
Preuve
24 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité
25 Pr. MESSAOUD
Dualité
Propriétés-Théorèmes de dualité
! 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é
! 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é
29 Pr. MESSAOUD
Dualité
! 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