Chapitre 4 Dualité PDF A chaque problème d'

Exercice 2. Dans le cas d'un problème de programmation linéaire (minimisation) possédant une solution optimale finie l'algorithme primal du simplexe permet

OPTI1- Dualité en PL - Algorithme dual du simplexe

Modéliser son problème par un programme linéaire P2. Quelle est la nature de P2 relativement à P1 ? Exercice 2. Ecarts complémentaires. On considère le

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux

TD 7 : Exercice corrigé. Algorithme du simplexe. Méthode des deux phases. Exercice. Résoudre par la méthode des deux phases le modèle de programmation linéaire

SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

PPL : Le problème de programmation linéaire sous forme canonique est de maximiser Cela provient du fait que. Excel dans son algorithme du simplexe utilise une ...

FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière

PROGRAMMATION LINEAIRE - Complément –. - Partie III : Algorithme du simplexe EXERCICE : N° 10 - Résolution graphique – résolution simplexe - dualité. Une ...

Recherche opérationnelle dualité exercices corrigés pdf

programmation lineaire methode simplexe pdf.td programmation lineaire corrige pdf.primal dual exercice dualite exercices corriges pdf.recherche ...

174 EXERCICES SUPPLÉMENTAIRES — PARTIE II

lité de la programmation linéaire l'algorithme du simplexe révisé

Dualité en Programmation Linéaire Algorithmes primal et dual du

Exercice. Exercice. Page 20. 20. Le résultat suivant est très important ;. - Si l Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe. Que ...

- Exercices de TD - 1 Modélisation.

Traduire par un programme linéaire en forme canonique. b. Résoudre le probl`eme par une méthode graphique. c. Maximiser le gain de l'année par la méthode du

1. Le tableau du simplexe (version perso)

Donc l'application de la méthode du simplexe à un programme linéaire associé Exercice 1. Résoudre en utilisant le tableau du simplexe. Maximiser f:(x1 x2 ...

1 Programmation linéaire

Master d'économie. Cours de M. Desgraupes. Méthodes Numériques. Document 4 : Corrigé des exercices d'optimisation linéaire. 1 Programmation linéaire.

TD 5 Programmation linéaire et optimisation Dualité Exercice 1

Exercice 2. Dans le cas d'un problème de programmation linéaire (minimisation) possédant une solution optimale finie l'algorithme primal du simplexe permet

Dualité en Programmation Linéaire Algorithmes primal et dual du

Ecrire le dual de ce problème. A-t-il une solution réalisable ? Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe. Que se

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux

Algorithme du simplexe. Méthode des deux phases. Exercice. Résoudre par la méthode des deux phases le modèle de programmation linéaire suivant :.

Cahier dexercices corrigés Eric LALLET Jean-Luc RAFFY

Correction page 42. 1.6 Programmation linéaire : le simplexe. Exercice 1.6.1 (Une histoire de fromage). Une laiterie s'

SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

PPL : Le problème de programmation linéaire sous forme canonique est de maximiser Excel dans son algorithme du simplexe utilise une construction du dual ...

- Exercices de TD - 1 Modélisation.

Maximiser le gain de l'année par la méthode du simplexe. Modéliser le probl`eme sous forme d'un programme linéaire en nombres entiers.

Programmation linéaire

Théorème de dualité. 4. L'algorithme du simplexe Résoudre le problème linéaire défini par A b

(Microsoft PowerPoint - 5_dualite [Mode de compatibilité])

Problème de programmation linéaire sous forme standard L'algorithme dual du simplexe est une méthode itérative pour résoudre un.

Chapitre 4 Dualité

A chaque problème d'optimisation linéaire nous allons définir un nouveau problème d'écart x4

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. 1

2CHAPITRE 4. DUALITÉ

Par exemple, considérons le problème

suivant minz=x1x2 sous les contraintes 8< :x13x2 3;

2x1x2 2;

1;x20:

qui admet la solution (x1;x2) = (3=5;4=5)etz=7=5.x 1x 21312

Le problème dual s"écrit sous la forme :

maxz=3y12y2 sous les contraintes 8< :y12y2 1;

3y1y2 1;

1;y20:

qui admet la solution (y1;y2) = (1=5;2=5)etz=7=5.x 1x

211=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 plantes

A;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 et

2 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+ 1500x3

Contrainte 1 :

dimension du terrain x

1+x2+x3340

Contrainte 2 :

temps de tra vail

2x1+ 3x2+x32400

Contrainte 2 :

temps de mac hine x

1+ 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

50 031 111500

20 1 21 0 1220

0 0200800 0300440;000La solution est

1= 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 y

1=coût marginal de 1 ha de terrain

2=coût marginal de 1 h de tra vail

4.2. INTERPRÉTATION ÉCONOMIQUE5

3=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 : y

1=prix à offrir p ourac heterun h ade terrain

2=prix à offrir p ourac heterune h de tra vail

3=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 y

1+ 2y2+y31100:

Activité B :

le b énéficelié à l "ensemencementde la plan teB est y

1+ 3y2+ 2y31400:

Activité C :

le b énéficelié à l" ensemencementde la plan teC est y

1+y2+ 3y31500:

En résumé, le problème s"écrit

8>>>><

>>>:minz= 340y1+ 2400y2+ 560y3 y

1+ 2y2+y31100;

1+ 3y2+ 2y31400;

1+y2+ 3y31500;

1;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 indicatrice

SoitKRnun sous-ensemble quelconque et non vide.

Définition

4.3.2 La fonction indicatrice de l"ensembleKest définie par

K(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. Lemme

4.3.1 La fonction indicatrice deK=fx2RnjAxbgest donnée par

K(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 la

forme(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.

Lemme

4.3.2 La fonction indicatrice deK0=fy2RmjAtycgest donnée par

K0(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=)maxybtyminxctx

En 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 ty

De 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 Lagrangien

L(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 =)cAty0

4.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 Lagrangien

L(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 que

0 = 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. Ceci implique que

0 = yt(Axb)0 =)yi[Ax)ibi] = 08i= 1;2;:::;m

D"autre part, la quantité(Ax)ibin"est rien d"autre que la valeur de la variable d"écart xn+i. Donc on obtient une autre relation de complémentarité yixn+i= 08i= 1;2;:::;m:

Ceci s"interprète de la manière suivante :

yi= 0ouxn+i= 0;8i= 1;2;:::;m: ou, de manière équivalente,

Si yi>0, on doit avoirxn+i= 0.

Si xn+i>0, on doit avoiryi= 0.

Exemple

4.3.2 Prenons le problème

minz= 340x1+ 2400x2+ 560x38>>< >:x

1+ 2x2+x31100;

1+ 3x2+ 2x31400;

1+x2+ 3x31500;

1;x2;x30:

14CHAPITRE 4. DUALITÉ

qui est de la formemin Axb; x0:c tx:

Les données sont

A=0 @1 2 1 1 3 2

1 1 31

A ; c=0quotesdbs_dbs1.pdfusesText_1

[PDF] Chapitre 4 Dualité A chaque problème d'

Chapitre 4

Dualité

4.1 Problème dual

On suppose queAest une matrice de formatmnetb2Rm.

Soit le problème d"optimisation linéaire

Définition

4.1.1 Le dual du problème (4.1) est

2CHAPITRE 4. DUALITÉ

Par exemple, considérons le problème

2x1x2 2;

1;x20:

Le problème dual s"écrit sous la forme :

3y1y2 1;

1;y20:

211=31=21

4.2. INTERPRÉTATION ÉCONOMIQUE3

Ev aluonsle dual du problème

Le dual sera

Aty c;

Le dual est

On applique le résultat ci-dessus pour obtenir

Donc, le dual du dual est le primal.

4.2 Interprétation économique

A211100

B321400

C131500

3402400560

4CHAPITRE 4. DUALITÉ

2 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

La fonction objective est

Contrainte 1 :

1+x2+x3340

Contrainte 2 :

2x1+ 3x2+x32400

Contrainte 2 :

1+ 2x2+ 3x3560

Le tableau final est donné parBx

1x2x3x4x5x6x

11 01 2 0 1120

50 031 111500

20 1 21 0 1220

0 0200800 0300440;000La solution est

1= 120;x2= 220;x3= 0;x4= 0;x5= 1500;x6= 0

1=coût marginal de 1 ha de terrain

2=coût marginal de 1 h de tra vail

4.2. INTERPRÉTATION ÉCONOMIQUE5

3=coût marginal de 1 h de mac hine

1=prix à offrir p ourac heterun h ade terrain

2=prix à offrir p ourac heterune h de tra vail

3=prix à offrir p ourac heterune h de mac hine

Activité A :

1+ 2y2+y31100:

Activité B :

1+ 3y2+ 2y31400:

Activité C :

1+y2+ 3y31500:

En résumé, le problème s"écrit

8>>>><

1+ 2y2+y31100;

1+ 3y2+ 2y31400;

1+y2+ 3y31500;

1;y2;y30:

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

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

Démonstration:Montrons en premier que

En effet, on a que