La dualité dans les problèmes de programmation linéaire
La dualité dans les problèmes de programmation linéaire!
Pour chaque problème de programmation linéaire, il existe un problème unique correspondant impliquant les mêmes données et décrivant également le problème d'origine. Le problème initial est appelé programme primal et le problème unique correspondant est appelé programme double. Les deux programmes sont très étroitement liés et la solution optimale de dual donne des informations complètes sur la solution optimale de primal et vice versa.
Les différents aspects utiles de cette propriété sont:
(a) Si primal a un grand nombre de constantes et un petit nombre de variables, le calcul peut être considérablement réduit en convertissant le problème en Dual et en le résolvant.
(b) La dualité dans la programmation linéaire a certaines conséquences de grande portée, de nature économique. Cela peut aider les gestionnaires à répondre à des questions sur les plans d’action alternatifs et leurs valeurs relatives.
(c) Le calcul du double vérifie la précision de la solution primale.
(d) La dualité dans la programmation linéaire montre que chaque programme linéaire équivaut à un jeu à somme nulle pour deux personnes. Cela indique qu'il existe des relations assez étroites entre la programmation linéaire et la théorie des jeux.
1. Former le double lorsque Primal est sous forme canonique:
Parmi les deux programmes ci-dessus, les points suivants sont clairs:
(i) Le problème de la maximisation chez le primal devient le problème de la minimisation dans le dual et inversement.
(ii) Le problème de maximisation a () des contraintes.
(iii) Si la primale contient n variables et m contraintes, le dual contiendra m variables et n contraintes.
(iv) Les constantes b 1 b 2, b 3 ……… b m dans les contraintes du primal apparaissent dans la fonction objective du dual.
(v) Les constantes c 1, c 2, c 3 c n dans la fonction objectif du primal apparaissent dans les contraintes du dual.
(vi) Les variables des deux problèmes ne sont pas négatives.
Les relations de contrainte du primal et du dual sont représentées ci-dessous.
Exemple 1:
Construire le dual du problème primal
Solution:
Tout d'abord, la contrainte ≥ est convertie en contrainte ≤ en multipliant les deux côtés par -1.
Exemple 2:
Construire le dual du problème primal
Solution:
Soit Y 1, Y 2, V 3 et V 4 les variables duales correspondantes, alors le problème du double est donné par
Comme le problème dual a moins de contraintes que le primal (2 au lieu de 4), il nécessite moins de travail et d'effort pour le résoudre. Cela découle du fait que la difficulté de calcul du problème de la programmation linéaire est principalement associée au nombre de contraintes plutôt qu’au nombre de variables.
Exemple 3:
Construire le dual du problème
Solution:
Comme le problème donné est de minimisation, toutes les contraintes doivent être de type>. En multipliant la troisième contrainte par -1, nous obtenons des deux côtés.
-8x 1 + 2x 2 + 2x 3 ≥ -10
La dualité du problème posé sera
où y 1, y 2, y 3, y 4 et y 5 sont les variables duales associées aux première, deuxième, troisième, quatrième et cinquième contraintes, respectivement.
