chapitre_12_Exercices.pdf

7/24/2019 chapitre_12_Exercices.pdf

1/17

Chapitre 12 Optimisation statique

Testez vos connaissances

Quelle diffrence y a-t-il entre un extremum libre etcontraint ? Donner un exemple.

Pourquoi utilise-t-on les dterminants dans le cadre de larecherche dextrema ?

Pour les conomistes, quapporte le thorme de Kuhn etTucker la recherche dextrema ?

Rsoudre le programme du consommateur classique et

du producteur.

La diffrence entre un extremum libre et un extremumcontraint rside dans lexistence ou pas des contraintesfonctionnelles. Par exemple, pour trouver une quation dunedroite qui passe par un nuage de points, la mthode desmoindres carrs en minimisant la somme des erreurs au carre

est un extremum libre ; et, le programme de maximisationclassique du consommateur est un extremum contraint. Par le biais de la matrice des drives secondes, lutilisation

des dterminants sert traiter la nature des extrema. Pour des contraintes qui prennent la forme dingalit, le

thorme de Kuhn et Tucker apporte une mthode dersolution ; mais, il apporte surtout un critre dcisionnel quiassure directement lexistence dun maximum (ou dunminimum) la lecture du signe du multiplicateur.

1


2/17

Exercice dentranement

Rappel : pour optimiser une fonction on suppose que la

fonction admet au moins une drive premire pour appliquerles conditions de jugements.

1 Contraintes galitaires

1- ;2 2. . , , 2 1Opt x y s c x y x y++ = +

2- 2 22 4 2 . . 6 2Opt x y z s c x y z+ + = + +

1-.2 2Opt . . , 2 1x y s c x y x y ++ = +

La fonction objectif est de classe 2.

2 2 1x y+ = ( )2 2g x =La contrainte na pas de point stationnaire, alors la CQND estsatisfaite.

Remarque : la condition de qualification de la contrainte nestpas ncessaire vrifier dans le cas des contraintes galitaires.

Formons le lagrangien :2 2( , , ) ( 2 1)L x y x y x y = + + .

Dtermination des points candidats (CN)

22

12 2 0 2 (1 ) 02

1 01 2 02

12 1

2 1 0 2

Lx x x

x

Lx

y

x yL yx y

= = = = == = = + = = = + =

Le point candidat est1

(0, )2

M =

2


3/17

Nature de lextremum (CS)

2 2 0 2

0 0 22 2 0

B

x

Hx

=

1 0 0

( ) 0 0 20 2 0

BH M

=

( ) 4 0BH M =

La fonction admet un minimum li.

2-2 2Opt 2 4 2 . . 6x y z s c x y z + + = + + 2

2

La fonction objectif est de classe 2.

2 26 x y z= + + ( )2 2 2g x y z =La contrainte na pas de point stationnaire si , et

alors la CQND est satisfaite.

0x 0y

0z

Formons le lagrangien :

2 2 2( , , ) 2 4 2 ( 6+ )L x y x y z x y z = + + + +

Dtermination des points candidats (CN)

2 2 2

2 2 2

2 2 01 2 14 2 0

62 2 0

6 0

L

xxL

yy x y zL x y zzz

Lx y z

= = = = = = =

+ + == = = + =

2 2x z = = y

Les points candidats sont avec et

avec0 (1,2,1)M = 1 =

1 ( 1, 2, 1)M = 1 =

3


4/17

Nature des extrema

2 0 0 2

0 2 0 20 0 2 2

2 2 2 0

B

x

yHz

x y z

=

0

2 0 0 2

0 2 0 4( )

0 0 2 2

2 4 2 0

BH M

=

1

2 0 0 2

0 2 0 4( )

0 0 2 2

2 4 2 0

BH M

=

Mthode des mineurs

principauxMthode des pseudo-valeurs

propres

Pour le point 0MPour le point puisquil y a 3 variables (n) etune contrainte (p), n p =2 nous donne le nombrede dterminants calculer

0M

1 0( ) 40BH M =

2 0( ) 96BH M =

2 0 0

0 2 0 4( )0 0 2 2

2 4 2

P

2

0

=

le point candidat avec

est un maximumcontraint.

0M

1 = ( ) 0 2P = =

Pour le point1

M

Pour le point puisquil y a 3 variables (n) etune contrainte (p),

1M

2 0 0

0 2 0 4( )

0 0 2

2 4 2

P

2

2

0

=

( ) 0 2P = =

n p = 2 nous donne lenombre de dterminants calculer

1 1( ) 40BH M =

2 1( ) 96BH M =

le point candidat avecest un minimum

contraint.

1M1 =

4


5/17

2 Contraintes ingalitaires2 2( , ) . . 2 2, 0, 0f x y x y s c x y x y= + +

2 2 2( , ) 2 . . 2 2 2, 0, 0g x y x y s c x y x y= + +

2 2

2 2

0, 0 1 2 0( , ) 2 . .

1 0 1 2

x y x yh x y x y s c

x y x y

+ = +

0 +

Remarque : la condition de qualification des contraintes prendtout son sens lorsquil y a plusieurs contraintes. Cette conditionnous informe dabord sur lindpendance des vecteurs-colonnes

des contraintes et enfin sur le nombre de contraintes saturesdans la rsolution du systme de Lagrange.

1-Soit 2 2( , ) . . 2 2, 0, 0f x y x y s c x y x y= + +

1f C sur et sur2 1ig C 2Choisissant le programme de maximisation

2 2

. . 2 2

x y

s c x y

+ +

avec 0, 0x y

2 2 x y+ ( )2 1g =Remarque : on peut raliser cette condition pour lensemble des

contraintes respecter ( )2 11 0

0 1

g

=

Le seul point stationnaire de la contrainte est lepoint (0,0), nimporte quel point candidat sera une solution dans ledomaine convexe (ensemble des contraintes). Formons le lagrangien :

1 2g x y + 2

2 2

1( , , ) ( 2 2)L x y x y x y = + + + .

5


6/17

Point conseil : le thorme de Kuhn et Tucker exige dans sonapplication 2 conditions :

1- 1f C et (de classe 1.)1ig C2- que les contraintes soient convexes.

En consquence, la lecture des multiplicateurs deLagrange-Kuhn et Tucker indiquent directement lanature de lextremum. On peut aussi dans cetterecherche vrifier si la fonction objective et lescontraintes sont concaves ou convexes.

CNS

2 2 0

2 0

( 2 2) 0 ; 0

Lx

xL

yy

x y

= = = = + =

Si , ce qui sous-entend que . Ceci est unecontrainte sature, alors le systme rsoudre est :

0 1 2g x y + =2

2 2 0

2 0

2 2

x

y

x y

= = + =

42

5x y = = =

Ce systme a pour solution un point candidat acceptable

23

x y = = = .

( )4 2,5 5M = avec4

5 = Ce point est un maximum li.

2

Soit

2 2 2( , ) 2 . . 2 2 2, 0, 0g x y x y s c x y x y = + + 1g C sur et sur2 1ih C

2

6


7/17

2

2 2

2

. .

x y

s c x y

+ +

avec 0, 0x y

2 22 2x y+ 2 y( )2 2h x =Remarque : on peut raliser cette condition pour lensemble des

conditions respecter ( )

22

1 0

0 1

yx

g

=

Le seul point stationnaire de la contrainte est lepoint (0,0), nimporte quel point candidat est solution dans ledomaine convexe. Formons le lagrangien :

2 21 1h x y +

2 2 2( , , ) 2 ( 1)L x y x y x y = + + + .

CNS

2 2

1 2 0

4 2 0

( 1) 0 ;

Lxx

Ly y

y

x y

= = = = + =

0

Si , ce qui sous-entend que est une contrainte

sature, alors le systme rsoudre est :

0 2 2 1x y+ =

2 2

1 2 0

2 (2 ) 0

1

x

y

x y

= = + =

2 2

12

21

xx y

= = + =

et

0

1

21

y

xx

= = =

1 15; ; 2

4 4

x y = = = 1

1; 0;

2

= = = x y

Ce systme a pour solution les points candidats acceptables

7


8/17

01 15;

4 4M

=

avec et2 = ( )1 1;0M = avec

1

2 = qui sont des

points maxima lis.

3-

2 2( , ) 2h x y x y = +

2 21 0

. . 1 2 0

1 2 0

2 2

2 2

2

1

. . 2 1

2 1

x y

x y

s c x y

x y

+ + + +

x y

s c x y

x y

+

=

)2 1

Condition de qualification des contraintes

Lensemble des contraintes forment bien un ensemble convexe.Vrifions que les quations indpendantes.

2 2

1 2( ) 2

1 2

i

x y

J g Rg J

=

( ) ( ) (2 2 2 21 2 32 1 2 1L x y x y x y x y = + + + + + + +

CNS

1 2 3

1 2 3

2 21 1

2 2

3 3

2 2 0

4 2 2 2 0

( 1) 0 ; 0 (

( 2 1) 0 ; 0 ( 0)

( 2 1) 0 ; 0 ( 0

Lx x

xL

y yy

x y

x y

x y

= + = = =

+ = + = + =

1

2

3

0)

)

1

1- Si , ce qui sous-entend que

et sont des contraintes satures, alors lesystme rsoudre devient :

1 2 30, 0, 0 = > >

2 1x y + = 2x y+ =

8


9/17

2 3

2 3

2 0

4 2 2 0

2 1

2 1

x

y

x y

x y

+ = = + = + =

2 31 1

0, ,2 2

x y = = = =

et doit tre vrifie par les rsultats obtenus2 2 1x y+ > 2 2 1x y+ =

2x y+ = 1

4 2 2

1

2 1

x x

y y

x y

x y

= =

+ = + =

1 31, 0, 1, 0x y = = = =

1 3

1 3

2 2

2 2 0

0

et doit tre vrifie par les rsultats obtenus2x y + < 1

Le point ( )1 1;0M = avec est non acceptable (la

contrainte n3 sannule en mme temps que ).1 31, 0 = =

3 0 =

3- Si , ce qui sous-entend que

et sont des contraintes satures, alors le systme

rsoudre devient :

3 1 20, 0, 0 = > > 2 2 1x y+ =

2x y + = 1

0

1 2

1 2

2 2

2 2 0

4 2 2

1

2 1

x x

y y

x y

x y

+ = = + = + =

9


10/17

1 21, 0, 1 et 0x y = = = =

1 23 4 7, , et5 5 5x y = = = =1225

et doit tre vrifie par les rsultats obtenus2x y+ < 1

Le point ( )2 1;0M = avec est non

acceptable (la contrainte n2 sannule en mme tempsque ).

1 21 et 0 = =

2 0 =

Le point ( )3 3 4;5 5M = avec 1 27 1

et5 2

= = 2

5 est non

acceptable (la contrainte n 3 nest pas satisfaite).

3 Programmation linaire

Trouver les solutions des programmes suivants optimiser.

1-

( , ) 2 4

0, 0

2 14. .

12

3 18

Min C x y x y

x y

x ys c

x y

x y

= +

+

+ +

2-

( , , ) 14 12 18

4 0

. . 2 2 0

, , 0

Max x y z x y z

x y z

s c x y z

x y z

= + +

Solutions

1-

min ( , ) 2 4

0, 0

2 14s.c. 12

3 18

C x y x y

x y

x y

x y

x y

= +

+

+ +

10


11/17

Passons la forme duale du programme pour une rsolution simple.

max 14 12 18

0, 0, 0

s.c. 2 2

3 4

P u w

u w z

u w z

u w z

= + +

+ + + +

z

u w z 1e 2e B TMS

1e 2 1 1 1 0 2 2

2e

1 1 3 0 1 4 4/3P 14 12 18 0 0 0

Solution de base et0 0 0P u w z = = = =0 1 22, 4e e= =

u w z 1e 2e B TMS

u 5/3 2/3 0 1 -1/3 2/3 2/5z 1/3 1/3 1 0 1/3 4/3 4

P 8 6 0 0 -6 -24

Solution et24 2/ 3 0 4/ 3P u w z = = = = 1 20, 0e e= =

u w z 1e 2e B TMS

u 1 2/5 0 3/5 -1/5 2/5 1z 0 1/5 1 -1/5 2/5 6/5 6P 0 14/5 0 24

5

22

5

136

5

Solution136 2 6

05 5 5

P u w z = = = = 1 20, 0e= =et e

u w z 1e 2e Bw 5/2 1 0 3/2 -1/2 1z -1/2 0 1 -1/2 1/5 1

P -7 0 0 -9 -3 -30

Solution finale et30 0 1P u w z = = = = 1 29, 3e e= =

Solution finale 30, 9, 3C x y= = =

11


12/17

2-max 14 12 18

4 0

s.c. 2 2 0

, , 0

x y z

x y z

x y z

x y z

= + +

min 2 4

0, 02 1

s.c.12

18

C u w

u wu w

u w

u w

= +

+ + +

4

x y z 1e 2e B TMS

1e 2 1 1 1 0 2 2

2e 1 1 1 0 1 4 4

14 12 18 0 0

Solution de base et0 0 0P x y z = = = =0 1 22, 4e e= =

x y z 1e 2e B

z 2 1 1 1 0 2

2

e -1 0 0 -1 1 2 -22 -6 0 -18 0 -36

Solution finale 36 0 0 2P x y z = = = = et 1 20, 2e e= =

La contraintes n 2 est pleinement utiliss, il reste 18 de disponiblepour la contrainte n1.

Solution finale 36, 18, 0C u w= = =

Exercices appliqus lconomie

1 Programmation linaire

Une entreprise dsire fabriquer trois produits x, y et z quidgageront des marges sur cot variable respectivement gales 60 , 75 et 93 . Le temps demploi des machines est de 42heures pour chacune. Le temps de passage dans les ateliers dechaque article exprim en centime dheure est rsum par :

12


13/17

chaque produit x ncessite 3 heures pour lassemblage (A), 5heures le polissage (P) et 3 heures pour la mise en caisse(C).Chaque y exige 6 heures pour lassemblage (A), 2 heures lepolissage (P) et 4 heures pour la mise en caisse(C). Chaqueproduit z exige 9 heures pour lassemblage (A), 3 heures lepolissage (P) et 6 heures pour la mise en caisse(C). Lentreprisedispose de 4 machines pour latelier A, 2 pour latelier B et C.Prsenter et donner la solution du programme de productionvisant maximiser la marge sur cot variable.

Solutions

Lentreprise maximise ses marges.

Tableau des valeursLe temps de passage est donn en centime dheure, il faut multiplierles capacits par 100 pour lhomognit du tableau.

x y z capacitsA 3 6 9 16 800P 5 2 3 8 400C 3 4 6 8 400

Marge 60 75 93

Programme

max 60 75 93

3 6 9 16800

5 2 3 8400s.c.

3 4 6 8400

, , 0

x y

x y z

x y z

x y z

x y z

= + +

+ +

+ + + +

z

13


14/17

x y z 1e 2e 3e B TMS

1e 3 6 9 1 0 0 16800 1866,67

2e 5 2 3 0 1 0 8400 2800

3e 3 4 6 0 0 1 8400 1400

60 75 93 0 0 0 0

Solution de base et0 0 0x y z = = = =0

1 2 316800, 8400, 8400e e e= = =

x y z 1e 2e 3e B TMS1e -3/2 0 0 1 0 -3/2 4200 -2800

2e 7/2 0 0 0 1 -1/2 4200 1200z 1/2 2/3 1 0 0 1/6 1400 2800

27/2 13 0 0 0 -31/2 -130200

Solution et130200 0 0 1400x y z = = = =

1 2 34200, 4200, 0e e e= = =

x y z 1e 2e 3e B TMS

1e 0 0 0 1 3/7 -12/7 6000 x 1 0 0 0 2/7 -1/7 1200 z 0 2/3 1 0 -1/7 5/21 800 1200

0 13 0 0 -27/7 -95/7 -146400

Solution et146400 1200 0 800x y z = = = =

1 2 36000, 0, 0e e e= = =

x y z 1e 2e 3e B1e 0 0 0 1 3/7 -12/7 6000x 1 0 0 0 2/7 -1/7 1200y 0 1 3/2 0 -3/14 5/14 1200

0 0 -39/2 0 -15/14 -255/14 -162000

La solution finale de lalgorithme du simplexe est :

162000, 1200, 0x y z = = = = et 1 2 36000, 0e e a= = = .

14


15/17

Lentreprise produira 1200 units de biens x , 1200 units debiens y, aucune unit du produit z, pour une marge de 162 000

. Les ateliers B et C sont pleinement utiliss, il reste 60 heuresdatelier A disponibles.

2 Extremum contraint

Les prfrences envers les quantits de biens x et y dunconsommateur sont traduites par la fonction dutilit

0,3 0,7( , )u x y x y= . Le revenu du consommateur slve 50 et les

prix des biens sont 2xp = et 5yp = 1. Trouver le panier qui maximise lutilit.2. Soit une transformation monotone croissante de

( , )u x y suivante : ( ) ln ( , )v u u x y= . Montrer que lon retrouve le

mme rsultat que dans la premire question.

Solutions

1-

Point conseil : Dans le programme traditionnel duconsommateur les conditions du premier ordre sont ncessaireset suffisantes. Ce rsultat permet de rduire ltude delextremum aux seules conditions ncessaires qui deviennentaussi suffisantes.

Formons le lagrangien0,3 0,7( , , ) ( 2 5 50)L x y x y x y = + +

CNS' 0,7 0,7

' 0,3 0,3

'

0,3 2 0

0,7 5 0

2 5 50 0

x

x

L x y

L x y

L x y

= = = + =

=

=

0,3 0,3 0,7 0,70,7 0, 3

5 22 5 50

x y x y

x y

= = + =

0,7 0,7

0,3 0,3

2 0, 7

5 0, 3

2 5 50

x y

x y

x y

= + =

15


16/17

14

152 5 50

y

xx y

= + =

7,5x = et 7y = .

Le point (7,5;7M ) avec 0,143 = est un maximum li.

2-

( ) ln ( , )v u u x y = 0,3 0,7ln 0,3 ln 0,7 lnx y x y = = + alors

( , , ) 0, 3 ln 0,7 ln ( 2 5 50)L x y x y x y

= + + +

CN

0,32 0

0,75 0

2 5 50

L

x xL

y y

L

x y

= = = = = + = 0

0, 3 0, 7

2 5

2 5 50

x y

x y

= = + =

15

14

2 5 5

x

y

x y

= + =

0

0,02

7,5

7

x

y

= = =

Le point candidat est (7,5;7)M =

CS

16


17/17

2

2

0,30 2

0,7

0 5

2 5 0

B

x

H y

=

et

2

2

0,30 2

7,5

0,7

( ) 0 57

2 5 0

BH M

=

( ) 0,19 0BH M = > cqfd

17

Documents

chapitre_12_Exercices.pdf