[PDF] Université Pierre et Marie Curie Année 2011-2012 Licence 3`eme

View - Download Université Pierre et Marie Curie Année 2011-2012 Licence 3`eme

Previous PDF

Next PDF

Universite Pierre et Marie CurieAnnee 2011-2012

Licence 3

emeannee : LM339 Examen du 30 mai 2012Le sujet est prevu pour 2h. Tout document est interdit. Veillez a la clarte de votre redaction

ainsi qu'a justier soigneusement chacune de vos armations.Exercice 1Questions de cours (5 points).

1. Denir l'enveloppe convexe, notee conv(S), d'un sous-ensemble quelconqueSdeRn:

2. SoitCun sous-ensemble convexe ferme non vide deRnetx2Rn:On notepC(x) la

projection orthogonale dexsurC, et on rappelle quepC(x) est l'unique element deC qui verie kxpC(x)k= miny2Ckxyk: Enoncer une caracterisation equivalente depC(x) en termes de signe de certains produits scalaires, et faire un dessin explicatif.

3. SoitCun convexe ferme deRnetFC:Sous quelle condition dit-on queFest une face

deC? Corrige 11. L'enveloppe convexe deSest l'ensemble de toutes les combinaisons convexes de points deS, c'est aussi le plus petit ensemble convexe deRncontenantS, ou encore l'intersection de tous les ensembles convexes deRncontenantS:

2. La caracterisation equivalente est quepC(x)2Cet que

hxpC(x);ypC(x)i608y2C; condition qui se traduit sur un dessin par le fait que l'angle entre les vecteurs reliant respecti- vementpC(x)ax(pour l'un) etpC(x)ay(pour l'autre,yetant quelconque dansC) est obtus.

3. On dit queFest une face deCsi le fait quex1+(1)x22Favecx1;x22Cet0< <1

implique necessairement quex12Fetx22F: Exercice 2Application de la methode du simplexe (10 points).

Pour le probleme d'optimisation (P) suivant :

maxf:= 5x1+ 4x2+ 3x38>>< >:2x1+ 3x2+x365

4x1+x2+ 2x3611

3x1+ 4x2+ 2x368

x

1;x2;x3>0(P)

1. Decrire le probleme dual (D) correspondant. De quel type de probleme s'agit-il?

2. Mettre le probleme dual (D) sous forme standard (DS).

3. Decrire un probleme auxiliaire (A) utilise pour initialiser la methode du simplexe pour

(DS). On veillera a n'introduire qu'une seule nouvelle variable par rapport a (DS):

4. Resoudre le probleme auxiliaire (A) par la methode du simplexe, choix du critere naturel.

1

5. Resoudre le probleme dual sous forme standard (DS) par la methode du simplexe, choix

du critere naturel.

6. En deduire, en se basant sur les prix marginaux de la solution optimale de (DS) obtenue,

une solution optimale du probleme (P). Observer que les valeurs optimales du primal et du dual sont confondues comme il se doit.

7. Pourt1;t2;t3susamment petits en valeur absolue, donner la valeur de l'optimum pour le

probleme d'optimisation perturbe (P0) ci-dessous? (n.b. : on ne demande pas de calculer de solution optimale pour (P0), mais uniquement la valeur de l'optimum) maxf:= 5x1+ 4x2+ 3x38>>< >:2x1+ 3x2+x365 +t1

4x1+x2+ 2x3611 +t3

2x1+ 4x2+ 2x368 +t2

x

1;x2;x3>0(P0)

Corrige 21. Le probleme dual (D) s'ecrit

ming= 5y1+ 11y2+ 8y38>>< >:2y1+ 4y2+ 3y3>5

3y1+y2+ 4y3>4

y

1+ 2y2+ 2y3>3

y

1;y2;y3>0;

ou encore sous forme canonique equivalente maxg=5y111y28y38>>< >:2y14y23y365

3y1y24y364

y12y22y363 y

1;y2;y3>0(D):

Il s'agit d'un probleme de deuxieme espece puisque les composantes du vecteur des contraintes (5;4;3)Tne sont pas toutes positives.

2. Le probleme sous forme standard associe, (DS), s'ecrit

maxg=5y111y28y38>>< >:2y14y23y3+y4=5

3y1y24y3+y5=4

y12y22y3+y6=3 y

1;y2;y3;y4;y5;y6>0(DS):

3. Le probleme auxiliaire (A) est donne par

maxh=y78>>< >:2y14y23y3+y4y7=5

3y1y24y3+y5y7=4

y12y22y3+y6y7=3 y

1;y2;y3;y4;y5;y6;y7>0(A)

2

4. Le probleme (A) se met sous forme de tableau (on garde en derniere ligne la trace de la

fonctiong)

243 1 0 01j 5

314 0 1 01j 4

122 0 0 11j 30 0 0 0 0 01j05118 0 0 0 0j0

La composante la plus negative du vecteur des contraintes etant5, qui correspond a la variable d'ecarty4;on retient les variablesy5;y6;y7comme variables en base initiales et on applique donc la methode du pivot de Gauss avec l'element en premiere ligne et septieme colonne comme pivot.

Cela donne2 4 31 0 0 1j5

1311 1 0 0j1

1 2 11 0 1 0j22431 0 0 0j55118 0 0 0 0j0

et fournit la solution de base realisable(0;0;0;0;1;2;5):Le critere naturel implique alors de choisiry2comme variable entrante (4est le co^ut marginal le plus grand) et le critere de Dantzig implique de choisiry5comme variable sortante. On applique donc la methode du pivot de Gauss avec l'element en deuxieme ligne et deuxieme colonne comme pivot. Cela donne

10=3 0 13=3 1=34=3 0 1j11=3

1=3 11=31=3 1=3 0 0j1=3

5=3 05=31=32=3 1 0j4=310=3 013=31=34=3 0 0j11=326=3 035=311=3 11=3 0 0j11=3

Le critere naturel implique alors de choisiry3comme variable entrante (13=3est le co^ut marginal le plus grand) et le critere de Dantzig implique de choisiry6comme variable sortante. On applique donc la methode du pivot de Gauss avec l'element en troisieme ligne et troisieme colonne comme pivot. Cela donne

1 0 06=52=513=5 1j1=5

0 1 02=5 1=5 1=5 0j3=5

1 0 11=52=5 3=5 0j4=51 0 06=52=513=5 0j1=53 0 061 7 0j13

Le critere naturel implique alors de choisiry4comme variable entrante (6=5est le co^ut marginal le plus grand) et le critere de Dantzig implique de choisiry7comme variable sortante. On applique donc la methode du pivot de Gauss avec l'element en premiere ligne et quatrieme colonne comme pivot. Cela donne

5=6 0 0 1 1=313=6 5=6j1=6

1=3 1 0 0 1=32=3 1=3j2=3

5=6 0 1 01=3 1=6 1=6j5=60 0 0 0 0 01j02 0 0 0 16 5j14

3 et termine le probleme d'initialisation avec la solution de base realisable(0;2=3;5=6;1=3;0;0;0):

5. Pour resoudre (DS), on omet alors la variabley7de(A)ainsi que la ligne du tableau corres-

pondant ah, ce qui donne(0;2=3;5=6;1=3;0;0)comme solution de base realisable et le tableau

5=6 0 0 11=313=6j1=6

1=3 1 0 0 1=32=3j2=3

5=6 0 1 01=3 1=6j5=62 0 0 016j14

Le critere naturel implique alors de choisiry5comme variable entrante (1est le co^ut marginal le plus grand) et le critere de Dantzig implique de choisiry4comme variable sortante. On applique donc la methode du pivot de Gauss avec l'element en premiere ligne et cinquieme colonne comme pivot. Cela donne

5=2 0 0 3 113=2j1=21=21 01 0 3=2j1=2

0 0 1 1 02j11=20 03 0 1=2j27=2

Le critere naturel implique alors de choisiry1comme variable entrante (1=2est le co^ut marginal le plus grand) et le critere de Dantzig implique de choisiry2comme variable sortante. On applique donc la methode du pivot de Gauss avec l'element en deuxieme ligne et premiere colonne comme pivot. Cela donne

0 5 02 1 1j3

1 2 02 0 3j1

0 0 1 1 02j101 02 01j13

Ici tous les coecients du vecteurs des co^uts marginaux sont negatifs et par consequent ont est a l'optimum. La solution de base realisable est(y1;;y6) = (1;0;1;0;3;0)et correspond a g=13, soitg= 13:On conclut que le maximum pour le probleme primal (egal au minimum pour le probleme dual) est egal a13:

6. Une solution du primale est obtenue en considerant les (ici 3) dernieres composantes du

vecteur des prix marginaux en la solution optimale du dual, soit(1;0;1), et en prenant leur oppose. On obtient ainsi la solution optimale du primal (P) :(1;0;1):On a bienf((1;0;1)) = 13:

7. En vertu du Theoreme 10.6 du polycopie, la valeur optimale du probleme perturbe, sous

contrainte de petitesse pour les perturbations, est donnee par

13 + 1t1+ 0t2+ 1t3;

puisque(1;0;1)est la solution optimale du probleme dual(D): Exercice 3Capacite de raisonnement sur une base theorique (5 points). SoientC1etC2deux convexes fermes disjoints et non vides deRn:On suppose de plus que C

1est borne. Pour chaquex2C1, on notepC2(x) la projection orthogonale dexsurC2(cfr.

Exercice 1).

1. Montrer que l'application :C1!R+,x7! kxpC2(x)kest continue. (On pourra

bien s^ur faire reference a des resultats enonces dans le polycopie, ou a defaut faire une demonstration directe) 4

2. Montrer que atteint sa valeur minimale en au moins un point deC1;et que cette valeur

est strictement positive.

3. Montrer, en choisissant un exemple particulier, que peut parfois atteindre sa valeur

minimale en plusieurs points distincts deC1:

4. Soitxun point de minimum pour :Montrer que necessairementx=pC1pC2(x);ou

p C1designe l'application de projection orthogonale surC1:Autrement dit, montrer que x est confondu avec la projection orthogonale depC2(x) surC1:

5. Deduire que

sup y2C1hy;pC2(x)xi2. Toute fonction continue sur un ferme borne deRnatteint ses bornes. Cela s'applique a. La borne inferieure est strictement positive puisqu'elle est atteinte et queC1etC2sont supposes disjoints.

3. On peut par exemple choisir les deux segments paralleles deR2:C1:=f(0;y);06y61g

etC2:=f(d;y);06y61g;oudest un nombre reel quelconque mais non nul. Dans ce cas, la fonctionest constante surC1, egale ad:

4. Supposons par l'absurde quex6=pC1(pC2(x)):Alors, par denition depC1, il existey2C1

tel quekpC2(x)yk5. Par les caracterisations depC2(x)et depC1(pC2(x))en termes de produits scalaires (cfr.

Exercice 1.2) on a

hypC1(pC2(x));pC2(x)pC1(pC2(x))i608y2C1 et hzpC2(x);xpC2(x)i608z2C2: RemplacantpC1(pC2(x))par son expression equivalentexdans la premiere inegalite, on obtient alors apres rearrangement sup ou on a utilise le fait quehx;pC2(x)xi hpC2(x);pC2(x)xi=kpC2(x)xk2<0: 5quotesdbs_dbs35.pdfusesText_40

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomie

[PDF] fonction de cobb douglas pdf

[PDF] revenu d'équilibre et revenu de plein emploi

[PDF] fonction cobb douglas ses

[PDF] multiplicateur de depense publique(definition)

[PDF] revenu d'équilibre en économie fermée