Chapitre 4 Dualité
Dans cet exemple on observe que la valeur minimale du primal est égale à la dual à l'aide du tableau final du simplexe appliqué au problème primal.
IFT 2505 Programmation Linéaire
Exemple sur le simplexe dual et primal-dual. On consid`ere le probl`eme min x. 3x1 + 4x2 + 6x3 + 7x4 + x5 s.`a. 2x1 ? x2 + x3 + 6x4 ? 5x5 ? 6.
SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual
Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual Excel dans son algorithme du simplexe utilise une construction du dual directe ...
Dualité en Programmation Linéaire Algorithmes primal et dual du
Algorithmes primal et dual du simplexe. Alain Faye. Option 3A Définition du dual d'un programme linéaire ... Exemple : écrire le dual de ce PL.
MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 1. Introduction La
Cette méthode s'applique en ayant déjà déterminer une solution de base réalisable pour le problème dual. C'est par exemple le cas si c ? 01 dans (2). La
IFT 2505 Programmation Linéaire
Dualité : relations `a la procédure du simplexe. Résoudre le primal par le simplexe donne la solution duale. Supposons que le programme Exemple : dual.
Algorithme primal-dual
Simplexe primal-dual. L'idée est de travailler simultanément Algorithme primal-dual : exemple ... du simplexe avec la solution du dual `a l'optimalité.
Sujet 4: Dualité --- la formule pour définir le dual dun programme
Mar 11 2010 “Le dual du dual
Sujet 5: Dualité --- faible et forte
Mar 24 2010 Si le primal est non-borné
Programmation linéaire (dualité et analyse de sensibilité) Dualité
Dualité : exemple Wyndor Glass Voici le modèle pour Dual Glass appelé modèle dual : ... du simplexe : ce sont les coefficients dans la ligne.
[PDF] méthode du simplexe dual (revisitée)
Cette méthode s'applique en ayant déjà déterminer une solution de base réalisable pour le problème dual C'est par exemple le cas si c ? 01 dans (2) La
[PDF] Exemple sur le simplexe dual et primal-dual
Exemple sur le simplexe dual et primal-dual On consid`ere le probl`eme min x 3x1 + 4x2 + 6x3 + 7x4 + x5 s `a 2x1 ? x2 + x3 + 6x4 ? 5x5 ? 6
[PDF] Chapitre 4 Dualité
Dans cet exemple on observe que la valeur minimale du primal est égale à la valeur maximale du dual Essayons de dualiser d'autres types de problèmes
[PDF] Dualité en Programmation Linéaire Algorithmes primal et dual du
Programmation linéaire et dualité – Définition du dual d'un programme linéaire – Théorème de dualité forte • Algorithmes primal et dual du simplexe
[PDF] OPTI1- Dualité en PL - Algorithme dual du simplexe - ENSIIE
2-Résoudre PL en appliquant l'algorithme dual du simplexe en partant de la base constituée par les 2 variables d'écart 3-Vérifier les calculs en faisant une
[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual
Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual Excel dans son algorithme du simplexe utilise une construction du dual directe
[PDF] Dualité --- la formule pour définir le dual dun programme linéaire
11 mar 2010 · “Le dual du dual c'est le primal ” Page 7 Dualité : introduction La formule Un exemple
[PDF] Sujet 5: Dualité --- faible et forte
L'utilisation du théor`eme dans la méthode du simplexe Rappel : un exemple maximisation et ¯y une solution réalisable de son dual
[PDF] Cours 8 Dualité
En effet à tout modèle de programmation linéaire primal correspond résolution comme l'algorithme du dual simplexe que nous traitons dans ce chapitre
[PDF] FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière
La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale Donc on présente la méthode à l'aide d'un exemple illustratif
Comment calculer la dualité ?
Le dual est max z = bty, Aty ? c, y ? 0. min z = ctx, (At)tx ? b, x ? 0. ?? min z = ctx, Ax ? b, x ? 0. Donc, le dual du dual est le primal.Comment faire le tableau de simplexe ?
Le tableau initial de la méthode du Simplexe est composé par tous les coefficients des variables de décision du problème original et les variables d'écart, excès et artificielles ajutées dans la deuxième étape (dans les colonnes, étant P0 0 le terme indépendant et le reste de variables Pi sont les mêmes que Xi), et lesC'est quoi un programme dual ?
Par définition, le programme dual est un programme linéaire consistant à minimiser une fonction économique dans un domaine défini par des contraintes sous forme d'inéquations de type inférieures ou égales (?).- La dualité, c'est la théorie qui nous permet de trouver avec confiance une solution optimale d'un programme linéaire. Si on a une solution réalisable qui n'est pas optimale, la dualité nous donne la capacité de savoir pourquoi cela n'est pas optimale.11 mar. 2010
Chapitre 4
Dualité
4.1 Problème dual
On suppose queAest une matrice de formatmnetb2Rm.
A chaque problème d"optimisation linéaire, nous allons définir un nouveau problème appellé
le dual. Le problème original est le primal.Soit le problème d"optimisation linéaire
minz=ctx; Axb; x0:(4.1)Définition
4.1.1 Le dual du problème (4.1) est
maxz=bty; A tyc; y0:(4.2) On notera que, pour le problème primal, on ax2Rntandis quey2Rmpour le dual. 12CHAPITRE 4. DUALITÉ
Par exemple, considérons le problème
suivant minz=x1x2 sous les contraintes 8< :x13x2 3;2x1x2 2;
x1;x20:
qui admet la solution (x1;x2) = (3=5;4=5)etz=7=5.x 1x 21312Le problème dual s"écrit sous la forme :
maxz=3y12y2 sous les contraintes 8< :y12y2 1;3y1y2 1;
y1;y20:
qui admet la solution (y1;y2) = (1=5;2=5)etz=7=5.x 1x211=31=21
Dans cet exemple, on observe que la valeur minimale du primal est égale à la valeur maximale du dual. Essayons de dualiser d"autres types de problèmes.4.2. INTERPRÉTATION ÉCONOMIQUE3
(a)Ev aluonsle dual du problème
maxz=ctx; Axb; x0: Pour cela il suffit de le réécrire sous la forme d"un problème demin: maxctx; Axb; x0:()minctx; Ax b; x0:Le dual sera
maxbty;Aty c;
y0:()minbty; A tyc; y0: (b) Ev aluonsmain tenantle dual du dual. Soit le problème minz=ctx; Axb; x0:Le dual est
maxz=bty; A tyc; y0:On applique le résultat ci-dessus pour obtenir
minz=ctx; (At)txb; x0:()minz=ctx; Axb; x0:Donc, le dual du dual est le primal.
4.2 Interprétation économique
Considérons le problème d"une entreprise agricole qui désire ensemencer avec 3 variétés de
planteA;BetC. Il s"agit de déterminer les superficiesxi(en hectare) des terres ensemencées par les plantesA;BetCpour avoir un bénéfice maximal. Voici le tableau qui résume la situationTerrain (ha)Travail (h)Machine (h)Rendement
A211100
B321400
C131500
3402400560
4CHAPITRE 4. DUALITÉ
Par exemple, il faudra 3 heures de travail par hectare pour ensemencer avec la plante B et2 heures de machinerie. La dimension totale du terrain est de 340 ha et nous disposons de
2400 heures de temps de travail et de 560 heures en temps de machinerie. 1 hectare de la
plante A donne un profit de 1100$.La fonction objective est
maxz= 1100x1+ 1400x2+ 1500x3Contrainte 1 :
dimension du terrain x1+x2+x3340
Contrainte 2 :
temps de tra vail2x1+ 3x2+x32400
Contrainte 2 :
temps de mac hine x1+ 2x2+ 3x3560
On ajoute les variables d"écartx4;x5;x6à ce problème et on applique la méthode du simplexe.
Le tableau final est donné parBx
1x2x3x4x5x6x
11 01 2 0 1120
x50 031 111500
x20 1 21 0 1220
0 0200800 0300440;000La solution est
x1= 120;x2= 220;x3= 0;x4= 0;x5= 1500;x6= 0
et le profit estz= 440;000$. On observ eque les ressources de te rrainet de ma chinerieson tpleinemen tutilisées carx4=x6= 0. P arcon tre,la ressource en temps de tra vailn"est pas pleinemen tutilisée car x56= 0. Si on disposait d"un hectare ou d"une heure de travail ou de machinerie de plus, quel serait le profit de plus? C"est le concept de coût marginal. Introduisons les variables y1=coût marginal de 1 ha de terrain
y2=coût marginal de 1 h de tra vail
4.2. INTERPRÉTATION ÉCONOMIQUE5
y3=coût marginal de 1 h de mac hine
On devrait avoiry2= 0car la ressource en temps de travail n"est pas pleinement utilisée. Maintenant, regardons le point de vue d"un acheteur des activités de l"entreprise. Les coûts marginaux sont mieux interprétés de la manière suivante : y1=prix à offrir p ourac heterun h ade terrain
y2=prix à offrir p ourac heterune h de tra vail
y3=prix à offrir p ourac heterune h de mac hine
Quel sera le problème à résoudre pour déterminer ces variables? La fonction objective correspond au coût à payer pour acheter l"entreprise z= 340y1+ 2400y2+ 560y3=b1y1+b2y2+b3y3=bty: Il s"agit de minimiser le prix à payer :minz=bty. Pour cela, son offre sera accepté s"il offre au moins autant que le bénéfice de chacune des activités.Activité A :
le b énéficelié à l"ensemencemen tde la plan teA est y1+ 2y2+y31100:
Activité B :
le b énéficelié à l "ensemencementde la plan teB est y1+ 3y2+ 2y31400:
Activité C :
le b énéficelié à l" ensemencementde la plan teC est y1+y2+ 3y31500:
En résumé, le problème s"écrit
8>>>><
>>>:minz= 340y1+ 2400y2+ 560y3 y1+ 2y2+y31100;
y1+ 3y2+ 2y31400;
y1+y2+ 3y31500;
y1;y2;y30:
Le principe de la dualité peut s"énoncer de la manière suivante : le plus bas prix total à payer
pour l"acheteur doit être égal au bénéfice maximal pour le producteur.6CHAPITRE 4. DUALITÉ
4.3 Théorie de la dualité
4.3.1 Lagrangien et point de selle
SoientARnetBRmdeux ensembles non vide et
L:AB!R
une fonction appellée Lagrangien.Définition
4.3.1 Un point(x;y)2ABest un point de selle du LagrangienLsi
L(x;y)L(x;y)L(x;y)8x2A;8y2B:
Exemple
4.3.1 Le point(0;0)est un point de selle de la fonctionL(x;y) =x2y2avec
A=B=Rcar
L(0;y) =y20 =L(0;0)x2=L(x;0)8x;y2R:
Théorème
4.3.1 Si(x;y)est un point de selle deL, alors
max y2Bminx2AL(x;y) = minx2Amaxy2BL(x;y) =L(x;y) Autrement dit, on peut inverser l"ordre duminet dumax.Démonstration:Montrons en premier que
max y2Bminx2AL(x;y)minx2Amaxy2BL(x;y):En effet, on a que
minx2AL(x;y)L(x;y)maxy2BL(x;y) Le membre de gauche est une fonction de y seulement. De même, pour le membre de droite qui est une fonction de x uniquement. Ceci implique max y2Bminx2AL(x;y)maxy2BL(x;y);8x2A et, en prenant le minimum par rapport àx, max y2Bminx2AL(x;y)minx2Amaxy2BL(x;y); d"où le résultat.4.3. THÉORIE DE LA DUALITÉ7
En deuxième, montrons que
minx2Amaxy2BL(x;y)L(x;y): En effet, selon la définition du point de selle, on a max y2BL(x;y) =L(x;y) =)L(x;y)minx2Amaxy2BL(x;y):De même, on a
min x2AL(x;y) =L(x;y) =)L(x;y)maxy2Bminx2AL(x;y):En recollant les morceaux, on obtient
d"où le résultat final.4.3.2 Fonction indicatriceSoitKRnun sous-ensemble quelconque et non vide.
Définition
4.3.2 La fonction indicatrice de l"ensembleKest définie par
IK(x) =0six2K,
1sinon.
La fonction indicatrice sert à enlever les contraintes. Pour un problème de minimisation, on a évidemment la relation minx2Kf(x) = minxf(x) +IK(x) Pour un problème de maximisation, on a plutôt max x2Kf(x) = maxxf(x)IK(x)Dans notre contexte de l"optimisation linéaire, on préfère ne pas enlever les contraintes de
positivitéx0. Ainsi les relations ci-dessus vont s"écrire min x2K x0f(x) = minx0f(x) +IK(x) de même pour un problème de maximisation.8CHAPITRE 4. DUALITÉ
Appliquons cette technique au cas de l"optimisation linéaire : minz=ctx; Axb; x0:Nous allons introduire la fonction Lagrangienne
L(x;y) =ctx+yt(bAx)8x2Rn;8y2Rm:
Le rôle de la fonctionLest de transformer le problème d"optimisation linéaire sous la forme min Axb; x0:c tx()minx0maxy0L(x;y) = minx0maxy0ctx+yt(bAx) Cela est possible grâce au résultat suivant. Lemme4.3.1 La fonction indicatrice deK=fx2RnjAxbgest donnée par
IK(x) = maxy0yt(bAx)
Démonstration:En effet, six2K,Axb)bAx0. Ory0, ce qui signifie que l"expressionyt(bAx)est toujours négative. Donc le maximum sera0. Au contraire, s"il existe un indiceitel que(Ax)i< bi)bi(Ax)i>0. Prenons desyde laforme(0;0;:::;0;yi;0;:::;0)avecyi>0. Il est clair quemaxy0yt(bAx) =1.De manière analogue, on a le résultat suivant pour un problème de maximum.
Lemme4.3.2 La fonction indicatrice deK0=fy2RmjAtycgest donnée par
IK0(y) =minx0xt(cAty)
Démonstration:La démonstration est tout à fait semblable.Théorème4.3.2 Théorème de la dualité (version faible)
SiAxb,x0etAtyc,y0, on a
b tyctx8x;y: Autrement dit, la fonction objective du primal est toujours bornée inférieurement parbtyet cela pour tous lesyvérifiantAtycety0. De même, la fonction objective du dual est toujours bornée supérieurement parctxpour tous lesxvérifiantAxbetx0.4.3. THÉORIE DE LA DUALITÉ9
Démonstration:On a
c tx=xtcxtAty= (Ax)ty =ytAx ytb=btyDans l"exemple du début du chapitre, le pointy= (y1;y2)avecy1= 1=2ety2= 1=2vérifie les contraintes. On a bien b ty=3y12y2=5=2 7=5 =ctx pour le sommetx= (3=5;4=5)satisfaisantAxbetx0. Le théorème faible de la dualité implique b tyctx=)btyminxctx=)maxybtyminxctxEn fait, on a même égalité.
Théorème
4.3.3 Théorème de la dualité (version forte)
On a l"égalité
min Axb; x0:c tx= max Atyc; y0:b tyDe plus une des alternatives suivantes a lieu :
a) Si un des problèmes primal ou dual admet u nesolution, alors l"autre problème admet aussi une solution. b) Si un des problèmes primal ou dual n"admet pas un esolution, alors l"autre problème n"admet pas de solution. Démonstration:On va prouver seulement l"égalité ci-dessus. De plus, on supposera que le LagrangienL(x;y) =ctx+yt(bAx)possède un point de selle.10CHAPITRE 4. DUALITÉ
min Axb; x0:c tx= minx0ctx+IK(x)avecK=fAxbg, = min x0ctx+ maxy0yt(bAx)grâce au Lemme 4.3.1, = min x0maxy0ctx+yt(bAx)carctxne dépend pas dey, = max y0minx0ctx+yt(bAx)grâce au Théorème 4.3.1, = max y0minx0bty+xt(cAty) = max y0bty+ minx0xt(cAty)carbtyne dépend pas dex, = max y0btyIK0grâce au Lemme 4.3.2 etK0=fAtycg = max Atyc; y0:b ty4.3.3 Conditions d"optimalité Donnons une caractérisation d"un point de selle(x;y)du LagrangienL(x;y) =ctx+yt(bAx)8x;y0
(1) On a que L(x;y)L(x;y)pour tous lesx0. Ceci s"écrit c tx+ yt(bAx)ctx+ yt(bAx) =)ctxytAxctxytAx =)ct(xx)ytA(xx)08x0 Maintenant, si au lieu de prendre le pointx0, on prend plutôt le pointx+x0.Donc on changex!x+x
=)ctxytAx08x0 =)xt(cAty)08x0 =)cAty04.3. THÉORIE DE LA DUALITÉ11
Donc, on obtient les conditions :
y0etAtyc: De plus, si on posex= 0dans l"expressionct(xx)ytA(xx)0ci-dessus, on obtient c t(x)ytA(x)0:On fait de même avecx= 2x, on obtient
c t(x)ytA(x)0:Par conséquent, on a l"égalité
c t(x)ytA(x) = 0()xt(cAty) = 0: (2) On a que L(x;y)L(x;y)pour tous lesy0. Ceci s"écrit c tx+yt(bAx)ctx+ yt(bAx); =)(yy)t(bAx)0; =)(yy)t(Axb)08y0: Maintenant, si au lieu de prendre le pointy0, on prend plutôt le pointy+y0.Donc on changey!y+y
y t(Axb)08y0 =)Axb0:Donc, on obtient les conditions :
x0etAxb: Si on posey= 0dans l"expression(yy)t(Axb)0ci-dessus, on obtient (y)t(Axb)0:Avecy= 2y, on a
(y)t(Axb)0:Par conséquent, on a l"égalité
yt(Axb) = 0: En conclusion on obtient les conditions d"optimalité aussi connues sous le nom de Karush,Kuhn et Tucker (KKT).
12CHAPITRE 4. DUALITÉ
Théorème
4.3.4 Conditions KKT
Le point(x;y)est un point de selle du Lagrangien
L(x;y) =ctx+yt(bAx)
si et seulement si les conditions suivantes sont vérifiées x0; Axb;y0; Atyc; et les relations de complémentarité xt(cAty) = 0etyt(Axb) = 0: Quel est le lien entre le point de selle(x;y)du LagrangienL(x;y) =ctx+yt(bAx)8x;y0
et les solutions des problèmes primal et dual?On a vu que
min Axb; x0:c tx= minx0maxy0L(x;y) =L(x;y) =ctx+ yt(bAx) =ctxcaryt(bAx) = 0. Donc,xest la solution optimale du problème primal.De même, pour le dual, on a que
max Atyc; y0:b ty= maxy0minx0L(x;y) =L(x;y) =ctx+ yt(bAx) =bty+ xt(cAty) =btycarxt(cAty) = 0. Donc,yest la solution optimale du problème dual.4.3.4 Relations de complémentarité
Interprétons les conditions KKT de la section précédente. Parmi ces relations, on a les deux
relations d"égalités xt(cAty) = 0etyt(bAx) = 0(4.3)4.3. THÉORIE DE LA DUALITÉ13
Etudions la première relation de gauche. Nous savons déjà quex0etcAtygrâce aux conditions KKT. Ceci implique que0 = xt(cAty)0 =)xici(Aty)i= 08i= 1;2;:::;n
D"autre part, la quantitéci(Aty)in"est rien d"autre que la valeur de la variable d"écart ym+i. Donc on obtient la relation dite de complémentarité xiym+i= 0;8i= 1;2;:::;n:Ceci s"interprète de la manière suivante :
xi= 0ouym+i= 0;8i= 1;2;:::;n: De manière équivalente, on peut aussi dire :Si xi>0, on doit avoirym+i= 0.
Si ym+i>0, on doit avoirxi= 0.
De même, pour la seconde relation de droite de (4.3). Nous avons quey0etAxb. Ceciquotesdbs_dbs35.pdfusesText_40[PDF] dualité onde particule formule
[PDF] dualité synonyme
[PDF] dualité exemple
[PDF] dualité définition
[PDF] dualité adjectif
[PDF] dualité de l'homme définition
[PDF] dualité humaine
[PDF] dualité entre deux personnes
[PDF] dualité définition philosophique
[PDF] duane hanson oeuvre
[PDF] duane hanson biography
[PDF] duane hanson supermarket lady
[PDF] tourists ii
[PDF] duane hanson tourists