En programmation linéaire, la dualité est un concept fondamental qui établit
une relation entre deux problèmes linéaires associés, appelés le problème primal
et le problème dual, associés à un même ensemble de contraintes. Cette relation
permet de mieux comprendre la structure et l'interprétation des solutions aux
problèmes d'optimisation.
• Chaque programme linéaire peut être considéré comme un problème primal.
Considérons un problème d’optimisation de type Max, avec « n » variables
de décision et « m » contraintes
Max (z) = c1x1 + c2x2 + ………………………+ cnxn
S/C a11x1 + a12x2 + ………………………+ a1nxn ≤ b1
a21x1 + a22x2 + ………………………+ a2nxn ≤ b2
.
.
.
.
.
.
.
am1x1 + am2x2 +………………….……+amnxn ≤ bm
x1, x2 ……………… xn ≥ 0
• Il y a un autre programme linéaire associé avec le primal, uniquement défini
par celui-là, ce programme linéaire-ci est le problème dual.
- Ces deux programmes sont toujours symétriques, dans les sens suivants (entre
autres) :
- Si le problème primal vise à maximiser une fonction objectif sous
certaines contraintes linéaires, alors le problème dual vise à minimiser une
fonction objectif associée tout en respectant des contraintes spécifiques
dérivées des contraintes du problème primal.
- Il y a une contrainte duale pour chaque variable primale, et une variable
duale pour chaque contrainte primale.
- Les coefficients objectifs des variables primales deviennent les côtés
droits des contraintes duales, et les côtés droits des contraintes primales
deviennent les coefficients objectives des variables duales.
- “Le dual du dual, c’est le primal.”
- La matrice des coefficients techniques du programme dual est la
transposée de la matrice des coefficients techniques du programme
primal.
Donc le dual du programme primal précèdent est de type Min, avec « m »
variables de décision et « n » contraintes :
Min (w) = b1y1 + b2y2 + ………………………+ bmym
S/C a11y1 + a21y2 + ……………………+ am1ym ..... c1
a12y1 + a22y2 + ……………………+ am2ym ….. c2
.
.
.
.
.
.
.
a1ny1 + a2ny2 +……………………..+ amnym ….. cn
y1, y2 ……………… ym ….. 0
Maintenant on doit déterminer les signes des contraintes ….., puis les signes
des variables ….. :9
Les signes des contraintes duales (≥, ≤, =) sont déterminés par les restrictions
sur les variables primales, et les signes des variables duales (≥0, ≤0, libre) sont
déterminés par le type des contraintes primales. Cette double correspondance
reflète la structure réciproque entre le problème primal et son dual :
• Si une variable primale xi est restreinte à xi≥0 (représente souvent une quantité
ou une ressource), alors la contrainte duale associée est de type ≥ (impose une
limite minimale).
• Si une variable primale xi est restreinte à xi≤0 (peut représenter une perte ou
une réduction), alors la contrainte duale associée est de type ≤ (impose une
limite maximale).
• Si une variable primale xi est libre (sans restriction), la contrainte duale
associée est une égalité (indiquant une absence de limitation stricte).
• Si une contrainte dans le primal est de la forme : a1x1+a2x2+⋯+anxn ≤ b (ex :
ressource limitée), alors la variable duale associée est positive (y≥0 ;
représente un coût marginal positif).
• Si une contrainte dans le primal est de la forme : a1x1+a2x2+⋯+anxn ≥ b,
(ex : demande minimale) alors la variable duale associée est positive (y≤0, qui
indique une pénalité ou perte négative).
• Si une contrainte dans le primal est de la forme : a1x1+a2x2+⋯+anxn = b
(implique une flexibilité), alors la variable duale associée est libre (peut être
positive ou négative, sans restriction de signe).
Donc le dual du programme primal précèdent est de type Min, avec « m »
variables de décision et « n » contraintes :
Min (w) = b1y1 + b2y2 + ………………………+ bmym
S/C a11y1 + a21y2 + ……………………+ am1ym ≥ c1
a12y1 + a22y2 + ……………………+ am2ym ≥ c2
.
.
.
.
.
.
.
a1ny1 + a2ny2 +……………………..+ am nym ≥ cn
y1, y2 ……………… ym ≥ 0
Exemples :
Pour tout problème linéaire, les solutions optimales du problème primal et
du problème dual sont liées de manière spécifique :
- Le primal a une solution optimale est le dual a aussi une solution
optimale. (Une solution optimale primale aura la même valeur objective
qu’une solution optimale duale)
- Si le primal est non-borné, alors le dual est irréalisable.
- Si le dual est non-borné, alors le primal est irréalisable.
- Tous les deux problèmes sont irréalisables.
Le théorème des écarts complémentaires est un principe
fondamental en programmation linéaire qui relie le problème primal à son
problème dual, stipulant une condition nécessaire et suffisante pour l'optimalité
des solutions des deux problèmes. Il peut être vu comme un équilibre entre les
ressources (représentées par les contraintes dans le problème primal) et les coûts
ou bénéfices marginaux (représentés par les variables duales).
- Soit x* solution admissible de (Primal) et z* = cx* la valeur de l’objectif de
(Primal), et y* solution admissible de (Dual) et w* = y*b la valeur de l’objectif
de (Dual) :
• Si z* = w*, Alors x* et z* sont solutions optimales de (Primal) et (Dual)
respectivement.
• À une variable duale (primale) non nulle correspond une contrainte
primale (duale) saturée, et à une contrainte primale (duale) non saturée
correspond une variable duale (primale) nulle, C’est-à-dire :
✓ si yi > 0, alors la ième contrainte primale est saturée
(si xi > 0, alors la ième contrainte duale est saturée)
✓ si la ième contrainte primale est non saturée, alors yi = 0
(si la ième contrainte duale est non saturée, alors xi = 0)
Exemple :
L'entreprise Alpha travaille sur la production de 3 produits, P1, P2 et P3, en
combinant les ressources A, B et C de la manière suivante :
- La production d'une unité du produit P1 nécessite l'utilisation de 11 unités
de la ressource A, 14 unités de la ressource B et 19 unités de la ressource C.
- La production d'une unité du produit P2 nécessite l'utilisation de 11 unités
de la ressource A, 9 unités de la ressource B et 7 unités de la ressource C.
- La production d'une unité du produit P3 nécessite l'utilisation de 5 unités de
la ressource A, 7 unités de la ressource B et 15 unités de la ressource C.
Cette entreprise vise à générer des bénéfices nets de 50 $, 75 $ et 65 $ pour
ses trois produits respectifs. Elle est confrontée à des contraintes de ressources
avec des quantités limitées de A, B et C disponibles, soit 1400 unités, 1700 unités
et 1600 unités respectivement.
• Formulez le programme linéaire visant à maximiser le bénéfice total de
l'entreprise Alpha :
Max (z) = 50x1 + 75x2 + 65x3
11x1 + 11x2 + 5x3 ≤ 1400
14x1 + 9x2 + 7x3 ≤ 1700
19x1 + 7x2 + 15x3 ≤ 1600
x1, x2 et x3 ≥ 0
L'entreprise Beta opère dans le même secteur que l'entreprise Alpha et
envisage de soumettre une offre pour acquérir les ressources (A, B et C) détenues
par l'entreprise Alpha, tout en maintenant une situation concurrentielle avec elle.
• Formulez le programme linéaire permettant à l'entreprise Beta de proposer
une offre compétitive qui minimise le coût total, à condition que l'entreprise
Alpha accepte ladite offre :
Min (w) = 1400y1 + 1700y2 + 1600y3
11y1 + 14y2 + 19y3 ≥ 50
11y1 + 9y2 + 7y3 ≥ 75
5y1 + 7y2 + 15y3 ≥ 65
y1, y2 et y3 ≥ 0
Si l'on considère que le plan de production optimal de l'entreprise Alpha est
de produire 100 unités du produit 2 et 60 unités du produit 3, utilisez la méthode
des écarts complémentaires pour déterminer la meilleure offre que l'entreprise
Beta devrait soumettre pour acheter les ressources A, B et C disponibles chez
l'entreprise Alpha.
La solution optimale du programme Primal :
x* = {x1=0, x2=100, x3=60}
z* = 50*(0) + 75*(100) + 65*(60) = 11400 $
- x1=0 → la 1ère contrainte du programme dual est non saturée
→ 11y1 + 14y2 + 19y3 > 50
- (x2=100) > 0 → la 2eme contrainte du programme dual est saturée
→ 11y1 + 9y2 + 7y3 = 75
- (x3=60) > 0 → la 3eme contrainte du programme dual est saturée
→ 5y1 + 7y2 + 15y3 = 65
- 11x1 + 11x2 + 5x3 ≤ 1400 :
11(0) + 11(100) + 5(60) = 1400
→ la 1ère contrainte du programme primal est saturée
→ y1>0
- 14x1 + 9x2 + 7x3 ≤ 1700 :
14(0) + 9(100) + 7(60) = 1320
→ la 2eme contrainte du programme primal est non saturée
→ y2=0
- 19x1 + 7x2 + 15x3 ≤ 1600 :
19(0) + 7(100) + 15(60) = 1600
→ la 3eme contrainte du programme primal est saturée
→ y3>0
- On a : (y2=0) & (11y1 + 9y2 + 7y3 = 75) & (5y1 + 7y2 + 15y3 = 65)
→ 11y1 + 7y3 = 75 → 11y1 + 7y3 = 75
5y1 + 15y3 = 65
→ y1= 67/13 & y3 = 34/13
La meilleure offre que l'entreprise Beta devrait soumettre pour acheter les
ressources A, B et C disponibles chez l'entreprise Alpha est :
w*= 1400*(67/13) + 1700*(0) + 1600*(34/13) = 11 400 $
• L'interprétation des variables duales y1, y2 et y3 (Optimisation des
ressources) :
Ces variables représentent la valeur marginale ou prix ombre des
ressources pour l'entreprise Alpha, c'est-à-dire combien l'entreprise pourrait
augmenter son bénéfice en disposant d'une unité supplémentaire de chaque
ressource.
1. y1 (Variable duale associée à la ressource A) mesure l'importance
marginale de la ressource A dans la production. y1=67/13>0, cela signifie
que la ressource A est saturée : l'entreprise Alpha utilise toute la ressource
disponible pour produire ses produits et une augmentation de la quantité
de ressource A augmenterait directement le bénéfice de l'entreprise.
2. y2 (Variable duale associée à la ressource B) : indique la valeur marginale
de la ressource B dans le processus de production, y2=0, cela signifie que
la ressource A n'est pas saturée et qu'il y a encore des quantités
disponibles qui ne sont pas utilisées dans la production, donc une
augmentation de la ressource A n'aurait pas d'impact sur le bénéfice.
3. y3 (Variable duale associée à la ressource C) : représente la valeur
marginale de la ressource C dans la production. y3=34/13 > 0, cela signifie
que la ressource C est saturée et qu'une augmentation de la quantité de
ressource C permettrait à l'entreprise Alpha d'augmenter son bénéfice de
34/13 $.
Questions supplémentaires
• Augmentation du bénéfice à 14 348 $
Pour des raisons commerciales, l'entreprise Alpha souhaite augmenter son
bénéfice total à 14 348 $. Elle a la possibilité d’élargir son plan de production en
augmentant les quantités disponibles des ressources A et B.
Combien d’unités supplémentaires de chaque ressource (A et B) doit-elle acquérir
pour atteindre cet objectif ?
• Vente d’une partie de la ressource C
Le directeur de l’entreprise Alpha considère que le prix de 34/13 $ par unité pour
la ressource C est satisfaisant. Il envisage de vendre une partie de cette ressource,
à condition que le bénéfice total ne diminue pas en dessous de 9 700$.
Combien d’unités de la ressource A peut-il vendre tout en respectant cette
condition ?
