Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  1  

Bureau  d’Études  d’Optimisation                                Non  Linéaire  

 

RAPPORT  

 

Introduction  

Ce  Bureau  d’Études  a  pour  objectif  d’appliquer  les  méthodes  vues  en  cours.  Nous  avons  été  confronté   auparavant   à   un   problème   d’optimisation   linéaire,   abordons   maintenant   des  problèmes  d’optimisation  non  linéaires.  Ce  travail  a  été  divisé  en  deux  parties,   la  première  comprenant  2  exercices  –  le  premier  exercice  centré  sur  la  commande  d’un  système  discret,  le   second  s’intéressant  aux  méthodes  permettant  de   rechercher  un  minimum   local  –  et   la  seconde   partie   focalisée   sur   le   problème   du   berger.   L’optimisation   et   les   techniques  associées  vont  permettre  de  répondre  à  ces  divers  problèmes  en  trouvant  la  ou  les  solutions  optimales.  

 I.  Partie  1  

Exercice  1    

On  souhaite  commander  le  système  discret  suivant  :  

𝑥 𝑘 + 1 =   0 1    −0,25 1   𝑥 𝑘 +    1 0  

 0 1   𝑢(𝑘)  

Tout  en  minimisant  l’énergie  dépensée  pour  la  commande,  soit  le  critère    

𝐽 = 𝑢! 𝑘 𝑢(𝑘)!

!!!

.  

L’état   initial   du   système  est   connu  𝑥 0 =    1    2    et   l’état   final   désiré  est  𝑥 4 =    6    4   .   Les  

limitations  sur  la  commande  sont  :  𝑢! 𝑘 ≥ 0  ∀𝑘,  (pas  de  limitation  sur  𝑢!).  

Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  2  

(1) Écrire  les  conditions  du  premier  ordre  de  ce  problème  d’optimisation.  Montrer  que  ce  problème  peut  être  considéré  de  deux  façons  différentes  suivant   l’écriture  des  contraintes.  

Le  problème  énoncé  peut   s’écrire   sous  deux   formes,   la  première  ayant  4  contraintes  et   la  seconde  en  n’en  ayant  qu’une.  

1ère  forme  :  sous  contraintes  

𝑥 1 =  𝐴𝑥 0 +  𝐵𝑢(0)  

𝑥 2 =  𝐴𝑥 1 +  𝐵𝑢(1)  

𝑥 3 =  𝐴𝑥 2 +  𝐵𝑢(2)  

𝑥 4 =  𝐴𝑥 3 +  𝐵𝑢(3)  

 

 

ℎ 1 = 𝐴𝑥 0 +  𝐵𝑢 0 −  𝑥 1  

ℎ 2 = 𝐴𝑥 1 +  𝐵𝑢 1 −  𝑥 2  

ℎ 3 = 𝐴𝑥 2 +  𝐵𝑢 2 −  𝑥 3  

ℎ 4 = 𝐴𝑥 3 +  𝐵𝑢 3 −  𝑥 4  

 

2ème  forme  :  sous  contrainte  

𝑥 4 = 𝐴!𝑥 0 +  𝐴!𝐵𝑢 0 + 𝐴!𝐵𝑢 1 +  𝐴𝐵𝑢 2 +  𝐵𝑢(3)  

 

 

ℎ = 𝐴!𝑥 0 +  𝐴!𝐵𝑢 0 + 𝐴!𝐵𝑢 1 +  𝐴𝐵𝑢 2 +  𝐵𝑢 3 −  𝑥(4)  

 

(2) Comment  peut-­‐on  résoudre  ces  conditions  du  premier  ordre  ?  

Il  est  possible  de  résoudre  ces  conditions  du  premier  ordre  en  utilisant  le  Lagrangien  :  

ℒ 𝑢, 𝜆 =  𝐽 𝑢 +  𝜆!ℎ 𝑢  

 

Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  3  

(3) Résoudre  ces  conditions  (vous  pouvez  vous  aider  de  Matlab)  

Cf.  annexe  1  

(4) A-­‐t-­‐on  bien  la  valeur  minimale  du  critère  ?  

Cf.  annexe  2  

 

Exercice  2    

On  cherche  à  optimiser  la  fonction  non  linéaire  

min 𝑓 𝑥 = 𝑥! − 2 ! + 𝑥! 𝑥! − 1 + 3 𝑥! + 1 +  𝑒!!!  !!!"  

L’objectif   est   ici   d’implémenter   une   ou   plusieurs   méthodes   de   recherche   d’un   optimum  local.  

(1) Énoncer  les  conditions  d’optimalité  du  premier  ordre  pour  la  fonction  f  

Cf.  annexe  3  

             Questions  suivantes  :  annexes  

Cf.  scripts  

(2) Observation  

 

Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  4  

 

(4)  Observation  

 

             (5)  Observation  

 

Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  5  

 II.  Partie  2  

Le  problème  du  berger  Un  berger  souhaite  mettre  en  place  une  clôture  dans  son  champ  pour  y  installer  son  cheptel  de  moutons.  Un  mangeoir  est  déjà  placée  sur  le  terrain  et  les  moutons  ne  doivent  jamais  se  trouver  à  plus  de  100m  du  mangeoir.  De  plus,  les  limites  du  champ  sont  telles  que  la  clôture  ne   peut   pas   être   située   plus   de   90m   au   dessus   du  mangeoir   et   plus   de   80m   à   droite   du  mangeoir.  Le  berger  ne  dispose  que  de  450m  de  grillage  et  d  e  3  poteaux.  Son  objectif  est  de  concevoir  un  enclos  le  plus  vaste  possible  pour  ces  moutons.  

 

 

 

(1) Quelles  sont  les  variables  du  problème  ?  

Les  variables  du  problème  sont  les  coordonnées  des  3  poteaux  :  

  Poteaun  :  𝑥!𝑦! ,𝑛 ∈ {1,2,3}  

Schéma  du  problème  

Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  6  

                 Questions  suivantes    

Cf.  scripts  

                 Observations  :  

 

 

 

 

 

 

 

 

 

 

Timothée  QUERE  –  Mohammed  DJABRI    Master  1  SMI  –  SIR   22/03/14  

  7  

Conclusion  

En   définitive,   ce   Bureau   d’Études   nous   aura   permis   de   faire   face   à   différents    problèmes,  et,  grâce  aux  outils  d’optimisation,  des  solutions  optimales  ont  été  trouvées.  La  première  partie  nous  a  montré  comment  aborder  un  problème  de  commande  de  système  discret,  par  différents  moyens,  et  comment  le  résoudre  par  le  calcul  en  s’aidant  de  Matlab.  Différentes   techniques,   la   méthode   du   gradient   et   la   méthode   de   Newton,   ont   été  implémentées  et  des  résultats  positifs  se  sont  révélés.    

La  seconde  partie  de  ce  Bureau  d’Études  aura  été,  grâce  à  la  toolbox  Optimization  de  Matlab,   de   résoudre   le   problème   du   berger.   Cette   toolbox   contenant   des   fonctions  pertinentes,  et  après  caractérisation  du  problème  de  long  en  large  –  fonctions  à  minimiser,  contraintes  d’égalité/  d’inégalités,  nous  avons  pu   trouver  une  solution  optimale,  parmi   les  nombreuses  existantes.  

Ce   Bureau   d’Études   a   été   utile   de   part   l’application   des   concepts   généraux   vu   en  cours,  mais  aussi  de   la   logique  à  adopter   face  à  un  problème.  En  effet,  quitte  à  avoir  une  solution   répondant   à   un   problème,   autant   optimiser   celle-­‐ci   afin   d’obtenir   la   meilleure  réponse   possible,   et   de   ce   fait   gagner   soit   en   temps,   en   coût   ou   en   espace  mémoire   par  exemple.