Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Chapitre 7 Dualité en programmation linéaire Introduction Dans ce chapitre no

1 Chapitre 7 Dualité en programmation linéaire Introduction Dans ce chapitre nous allons voir comment nous pouvons, à partir d'un programme linéaire donné (qui sera appelé programme primal), construire un autre programme linéaire appelé programme dual. Entre ces deux programmes il y a des liens très étroits : si un des deux a une solution optimale l'autre en possède également une et les valeurs optimales des deux programmes coïncident. Il arrive que la résolution du problème dual peut être plus simple que celle du problème primal (par exemple on connaît une solution de base admissible pour le dual et on peut démarrer directement le simplexe, tandis que pour le primal on est obligé d'utiliser la méthode des deux phases). En plus de l'intérêt mathématique ou numérique pour l'étude du problème dual, un aspect autre très important est l'interprétation économique des variables duales. Ces variables représentent des coûts marginaux et peuvent être considérées comme l'augmentation maximale du revenu, par rapport à la solution optimale, qui résulterait de l'utilisation d'une unité supplémentaire de l'un des biens. Etant donné le PL suivant écrit sous forme canonique, on peut considérer qu’il concerne une entreprise E1 fabricant n biens j, j {1, . . . , n} et faisant intervenir m ressources i, i {1, . . . , m}. Le problème que peut se poser l’entreprise est le suivant : Etant donnée la disponibilité bi pour chaque ressource i et le profit unitaire cj pour chacun des biens j, quel doit être le niveau de production de chaque bien j pour que la quantité de bien i consommée reste inférieure à la disponibilité bi et que le profit total soit maximal? Supposons qu’une autre entreprise E2, en rupture de stock, désire racheter les ressources de la première, le problème qu’elle va se poser et le suivant : Etant donné un prix unitaire cj pour chacun des n biens j et une disponibilité bi pour chacune des m ressources i, quel doit être le prix unitaire minimum d’achat yi de chaque ressource i pour que la valeur totale des ressources consommées par chaque bien j soit supérieure ou égale à cj (pour que cela rester intéressant pour l’entreprise E1 et que le prix total d’achat des ressources disponible soit minimum? 2 Ce deuxième problème constitue le problème dual du premier, il peut se mettre sous la forme : On voit aisément que les contraintes, impliquent que le prix d’achat des ressources par l’entreprise E2 reste supérieur au profit que peut en tirer l’entreprise E1, c’est à dire, ce qui est conforme aux lois de l’économie, on voit donc intuitivement que le minimum atteint par le deuxième problème doit être égal au maximum du premier problème. La théorie montre que c’est le cas quand le problème a des solutions. La construction du programme dual Considérons un programme linéaire sous la forme canonique appelée programme primal : Primal Le programme dual a m variables notées ¸y1,…., ym qui sont rangées sous la forme d'un vecteur ligne . A noter la différence par rapport aux variables primales qui sont données sous la forme d’un vecteur colonne . Alors le programme dual s’écrit sous la forme matricielle : Ou encore, Dual 3 Remarque : À toute variable d’écart primale (resp. duale) positive correspond une variable structurelle duale (resp. primale) nulle. À toute variable structurelle primale (resp. duale) positive correspond une variable d’écart duale (resp. primale) nulle. On note, xj (resp. yi) les variables structurelles du primal (resp. dual) et ti (resp. uj) les variables d’écart du primal (resp. dual). Le tableau suivant résume les correspondances entre les deux problèmes primal et dual: Problème primal Problème dual Maximisation Matrice des contraintes (m,n) n variables (vecteur colonne) m contraintes variable nº j ≥ 0 contrainte nº i ≤ contrainte nº i = variable nº j de signe qcq (ligne de) coefficients fonction objectif second membre minimisation transposée de la mat des contraintes (n,m) n contraintes m variables (vecteur ligne) contrainte nº j ≥ variable nº i ≥ 0 variable nº i de signe qcq contrainte nº j = second membre (colonne de) coefficients fonction objectif Nous remarquons facilement que la matrice des contraintes du problème dual est la transposée de celle du problème primal. Enfin, pouvons constater facilement que le dual du problème dual c'est le problème primal. Exemple Primal Dual Remarque : Le tableau précédent nous permet d’obtenir le dual d’un PL quelque soit sa forme, néanmoins, il est préférable de mettre le PL primal sous forme canonique avant de déterminer son dual. La forme canonique ici est un abus de langage puisque les ne sont pas tous positifs. Il s’agit d’avoir en plus des contraintes de positivité (variables toutes positives), toutes les contraintes sont de type pour un problème de minimisation et un problème de maximisation. Exemple : Soit le PL suivant Nous l’écrivons d’abord sous cette forme pour obtenir son dual facilement. 4 Primal Dual Propriétés de la dualité Théorème 1 : Soient x une solution admissible du primal et y une solution admissible du dual. Alors on a . Autrement dit chaque valeur admissible du dual est un majorant pour chaque valeur admissible du primal. Démonstration. Soit une solution réalisable de P, alors on a et soit y vérifiant : On a . □ Nous pouvons donc facilement déduire le résultat suivant Théorème faible de la dualité : Soient et deux solutions amissibles respectivement du primal et du dual. Si c = b, alors est une solution optimale de (P) et une solution optimale de (D). Démonstration. Soit une solution réalisable de P, alors on a d’après le théorème précédent puisque est une solution réalisable de D. Donc est une solution optimale de P. On montre de la même manière que st une solution optimale de D. □ A noter que la réciproque n'est pas aussi évidente à montrer, à savoir que si et sont deux solutions optimales respectivement du primal et du dual, alors les valeurs optimales coïncident. C'est l'objet du théorème suivant qui est un résultat central de la dualité en programmation linéaire. Théorème fort de la dualité: Si le problème primal (P) a une solution optimale , alors le problème dual (D) a une solution optimale et les valeurs optimales coïncident, c = b. Autrement dit z* = w*. Démonstration : Soient une solution optimale de P et B la base optimale correspondante. Posons Rappelons que est le vecteur des multiplicateurs du simplexe correspondant. On a les coûts réduits à l’optimum = et pour Par suite . D’où est une solution réalisable du dual. D’autre part on a , . D’après le théorème faible de la dualité, est une solution optimale de D. □ 5 Le théorème précédent donne le lien entre le primal (P) et le dual (D) dans le cas où P admet une solution optimale finie. Cependant, il ne donne pas le résultat dans les autres cas. Le théorème suivant englobe tous les cas possibles. Théorème 2 : Soient P un problème linéaire primal et D son dual. Un seul cas parmi les trois cas suivants est possible : 1. Les deux Problèmes P et D ont chacun une solution optimale finie et la valeur de leur fonction objectif à l’optimum sont égales. 2. Si P est non borné, alors son dual D est contradictoire. 3. Si P n’a pas de solution, alors D est soit non borné ou contradictoire. Démonstration : 1. Ceci est vrai d’après le théorème fort de la dualité. 2. Procédons par l’absurde. Supposons que P est non borné, alors il existe toujours une solution telle que pour aussi grand que l’on veut. Supposons maintenant que D est non contradictoire, alors il possède une solution réalisable y. D’après le théorème 1 on a, . Ce qui est une contradiction. 3. Supposons que P n’a pas de solution, alors il n’a pas de solution optimale finie. Par suite d’après le théorème fort de la dualité D ne possède pas de solution optimale finie. Il est donc soit contradictoire ou non borné. □ Remarque: Nous pouvons montrer le point 2 du théorème précédent en utilisant les tableaux du simplexe. En effet, si le primal que nous supposerons un problème de maximisation est non borné, alors il existe une colonne dans le tableau du simplexe correspondant à ce PL (à une itération donnée) dont tous les coefficients sont négatifs et les coûts réduits correspondant sont positifs. Ceci correspond à une contrainte (ligne) du dual dont tous les coefficients sont négatifs, avec un second membre positif. Ce qui est contradictoire bien sur. Théorème des écarts complémentaires : Soient et deux solutions respectivement du primal et du dual. et sont optimales si et seulement si Démonstration : Supposons que et sont deux solutions optimales de P et D respectivement. Alors on a, , ou encore Comme et la nullité du produit scalaire précédent implique . Inversement, si alors on et d’après le théorème faible de la dualité, et sont deux solutions respectivement du primal et du dual. □ Exemple : Soient le uploads/Voyage/ chapitre-7-rop-dualite.pdf