Remerciez-le!

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

Chapitre 7 rop dualite Chapitre Introduction Dualité en programmation linéaire 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é pro

Chapitre Introduction Dualité en programmation linéaire 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 E fabricant n biens j j n et faisant intervenir m ressources i i 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 E 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 E et que le prix total d ? achat des ressources disponible soit minimum 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 E reste supérieur au profit que peut en tirer l ? entreprise E 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 y ?