Scribd Logo
Importer

Bienvenue sur Scribd !

  • 18 vues

    Solution de Lexamen 20-21

    Transféré par

    Meryem Kachani
    Ce document présente deux exercices de programmation mathématique. Le premier exercice demande de montrer certaines propriétés d'un projet sur un convexe. Le second exercice consiste à résoudre un problème de programmation linéaire et son dual.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Solution de Lexamen 20-21

    Transféré par

    Meryem Kachani
    18 vues6 pages
    Ce document présente deux exercices de programmation mathématique. Le premier exercice demande de montrer certaines propriétés d'un projet sur un convexe. Le second exercice consiste à résoudre un problème de programmation linéaire et son dual.

    Titre original

    Solution de lexamen 20-21

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document présente deux exercices de programmation mathématique. Le premier exercice demande de montrer certaines propriétés d'un projet sur un convexe. Le second exercice consiste à résoudre un problème de programmation linéaire et son dual.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    18 vues6 pages

    Solution de Lexamen 20-21

    Transféré par

    Meryem Kachani
    Ce document présente deux exercices de programmation mathématique. Le premier exercice demande de montrer certaines propriétés d'un projet sur un convexe. Le second exercice consiste à résoudre un problème de programmation linéaire et son dual.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 6

    Université Cadi Ayyad Filière : SMA S5

    Faculté des Sciences Sémlalia Module : M4-Programmation Mathématique


    Département de mathématiques Session I 2020-21
    Le Lundi 08 Mars 2021 Durée 1 heure 30 mn
    Tou document, calculatrice ou téléphone non-autorisé
    Vos réponses doivent être justifiées (= démontrées ou bien validées par un contre-exemple)..

    Nom et Prénom : —————————————————————–

    Numéro d’Apogée : —————————————— Note sur 20

    Numéro de table : ——————————————–

    Exercice 1 :(5 points) Dans cet exercice, C désigne un convexe fermé non vide de Rn .
    La norme euclidienne de x est notée kxk.
    1. Montrer que pour tout z ∈ Rn , il existe un unique z ∗ ∈ C tel que kz − z ∗ k = min kz − xk.
    x∈C
    On notera cet élément z ∗ = ΠC (z).
    2. Montrer que pour tout z ∈ Rn , on a la propriété suivante

    ∀x ∈ C, (z − ΠC (z))T (x − ΠC (z)) ≤ 0.

    3. Montrer que pour tout z1 , z2 ∈ Rn ,

    kΠC (z1 ) − ΠC (z2 )k ≤ kz1 − z2 k.

    Solution : 1. (2 pst) Soit z ∈ Rn fixé, et considérons une suite minimisante


    (xk )k dans C telle que
    r0 := inf kz − xk = lim kz − xk k.
    x∈C k→+∞

    Alors (xk )k est bornée. En effet, puisque lim kz − xk k = r0 , alors il existe


    k→+∞
    N > 0 tel que ∀k ≥ N , kz − xk k < 1. Par suite ∀k ≥ N , kxk k ≤ kzk + 1.
    Ainsi, (xk )k est bornée dans Rn , donc admet une sous-suite (xkp )p qui converge
    vers un z ∗ qui est dans C, car (xk )k ⊂ C et C est fermé. D’où
    kz − z ∗ k = lim kz − xkp k = lim kz − xk k = min kz − xk.
    p→+∞ k→+∞ x∈C

    Pour l’unicité, on suppose qu’il existe z1∗ 6= z2∗ ∈ C qui réalisent ce minimum,
    alors z̄ = 21 z1∗ + 12 z2∗ ∈ C car C est supposé convexe et
    r02 = kz2∗ − zk2 ≤ kz̄ − zk2 = k 21 (z1∗ − z) + 21 (z ∗
    2 − z)k
    2

    = 12 kz1∗ − zk2 + kz2∗ − zk2 − 21 kz1∗ − z2∗ k2


    

    < 12 kz1∗ − zk2 + kz2∗ − zk2 = r02


    ce qui est absurde. Donc z ∗ ∈ C est l’unique point de C tel que kz − z ∗ k =
    min kz − xk.
    x∈C

    1
    2. (1,5pt) On fixe z ∈ Rn , et on prend x ∈ C. On a z ∗ = ΠC (z) et C convexe,
    donc pour tout t ∈]0, 1[, tx + (1 − t)z ∗ ∈ C, et par suite

    kz − z ∗ k2 ≤ kz − (tx + (1 − t)z ∗ )k2 = kt(z − x) + (1 − t)(z − z ∗ )k2


    = t2 kz − xk2 + (1 − t)2 kz − z ∗ k2 + 2t(1 − t)(z − x)T (z − z ∗ )
    t2 kz − xk2 + (1 − t)2 kz − z ∗ k2 + 2t(1 − t) kz − z ∗ k2 + (z ∗ − x)T (z − z ∗ )
     
    =
    = t2 kz − xk2 + (1 − t2 )kz − z ∗ k2 + 2t(1 − t)(z ∗ − x)T (z − z ∗ ).
    Donc
    (z − z ∗ )T (x − z ∗ ) ≤ 1
    t2 kz − xk2 + (1 − t2 )kz − z ∗ k2
    
    2t(1−t)
    t
    kz − xk2 − kz − z ∗ k2 .
    
    = 2(1−t)

    Ainsi, lorsque t → 0, on aura (z − z ∗ )T (x − z ∗ ) ≤ 0.

    3. (1,5pt) Soient z1 , z2 ∈ Rn et notons z1∗ = ΠC (z1 ) et z2∗ = ΠC (z2 ). D’après la


    question 2, on a

    (z1 − z1∗ )T (x − z1∗ ) ≤ 0 et (z2 − z2∗ )T (x − z2∗ ) ≤ 0.

    En prenant x = z2∗ dans la première inégalité et x = z1∗ dans la seconde et en


    sommant les deux inégalités, on obtient

    0 ≥ (z1 − z1∗ )T (z2∗ − z1∗ ) + (z2 − z2∗ )T (z1∗ − z2∗ ) = (z1 − z2 )T (z2∗ − z1∗ ) + kz2∗ − z1∗ k2 .

    D’où
    kz2∗ − z1∗ k2 ≤ (z2 − z1 )T (z2∗ − z1∗ ) ≤ kz2 − z1 kkz2∗ − z1∗ k
    ce qui donne kΠC (z1 ) − ΠC (z1 )k ≤ kz2 − z1 k.

    Exercice 2 : (9 points) × 1,5 ≡ 13,5


    On considère le problème de programmation linéaire suivant :

    Maximiser 5x
     1 + 6x2 + 3x3
     4x1 + 3x2 + x3 ≤ 2
    (P)
    Sous-cont x1 + 2x2 + 2x3 ≤ 3
    x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

    1. Écrire le programme duale (P)∗ associé au problème (P).


    2. En utilisant la méthode des tableaux résoudre le programme (P).
    3. Déduire du tableau final la solution de base optimale de (P ∗ ).
    4. En utilisant le Théorème de dualité forte vérifier la validité des solutions optimales de
    (P) et (P)∗ .
    5. Citer le Théorème de complémentarité, et l’utiliser pour retrouver la solution de base
    optimale de (P ∗ ) à partir de celle de (P).

    2
    Solution : 1. (1 pt) Puisque le programme linéaire (P) est déjà sous forme
    canonique, alors son problème dual est
    Minimiser 2y
     1 + 3y2
     4y1 + y2 ≥ 5
    ∗

    (P ) 3y1 + 2y2 ≥ 6

    Sous-cont
    y + 2y2 ≥ 3
     1


    y1 ≥ 0, y2 ≥ 0.

    2. (3,5 pts) En ajoutant des variables d’écart x4 , x5 , le problème (P) sous


    forme standard est :
    Maximiser 5x
     1 + 6x2 + 3x3
     4x1 + 3x2 + x3 + x4 = 2
    (P)
    Sous-cont x1 + 2x2 + 2x3 + x5 = 3
    x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.

    Pour résoudre le problème (P), on utilisera une seule phase :


    c 5 6 3 0 0
    x1 x2 x3 x4 x5 x0
    x4 4 3 1 1 0 2 `01
    x5 1 2 2 0 1 3 `02
    ∆0 5 6 3 0 0 −z0 = 0 `03
    Tableau 1
    c 5 6 3 0 0
    x1 x2 x3 x4 x5 x1
    x2 4/3 1 1/3 1/3 0 2/3 `11 = `01 /3
    x5 -5/3 0 4/3 -2/3 1 5/3 `12 = `02 − 2`11
    ∆1 -3 0 1 -2 0 −z1 = −4 `13 = `03 − 6`11
    Tableau 2
    c 5 6 3 0 0
    x1 x2 x3 x4 x5 x2
    x2 7/4 1 0 1/2 -1/4 1/4 `21 = `11 − 3`22
    x3 -5/4 0 1 -1/2 3/4 5/4 `22 = 34 `12
    ∆2 -7/4 0 0 -3/2 -3/4 −z2 = −21/4 `23 = `13 − `22
    Tableau 3
    Dans le tableau 3, toutes les composantes de ∆2 sont négatives, alors la solution
    T
    de base optimale est x̄ = x2 = 0, 41 , 45 , et la valeur optimale est z̄ = z2 = 21
    4.

    3
    3. (1 pt) Puisque le programme linéaire (P) est sous forme canonique, alors du
    tableau final de cette phase primale, on déduit que la solution de base optimale
    du programme linéaire dual (P ∗ ) se déduit des composantes de ∆2 en prenant :
    3 3
    ȳ1 = ∆42 = et ȳ2 = ∆52 = .
    2 4
    La valeur optimale de (P ∗ ) est w̄ = 2ȳ1 + 3ȳ2 = 21
    4.

    4. (1,5 pt) Du Théorème de dualité forte, si le problème primal (P) admet


    une solution optimale alors il en est de même pour le problème dual (P ∗ ) et les
    valeurs optimales sont identiques : z̄ = w̄. Or, on a z̄ = 21 21
    4 et w̄ = 4 , donc les
    solutions optimales z̄ et w̄ sont admissibles.

    5. (2 pt) Le théoreme de complémentarité nous dit que si x̄ et ȳ sont


    respectivement admissibles pour les problèmes (P) et (P)∗ , alors x̄ et ȳ sont
    optimaux si, et seulement si, (AT ȳ − c)T x̄ = 0 et ȳ T (b − Ax̄) = 0, c’est à dire :
     n
    !
     X
     bj − aji x̄i ȳj = 0, j = 1, · · · , m ,



    i=1
    Xm
    ! .




     aij ȳj − ci x̄i = 0, i = 1, · · · , n.
    j=1
    T
    Puisque la solution de base optimale de (P) est x̄ = 0, 41 , 54 , alors

     x̄1 (4ȳ1 + ȳ2 − 5) = 0
    x̄ (3ȳ1 + 2ȳ2 − 6) = 0
     2
    x̄3 (ȳ1 + 2ȳ2 − 3) = 0
    nous donne le système du premier ordre
    
    3ȳ1 + 2ȳ2 = 6
    ȳ1 + 2ȳ2 = 3
    3
    qui a pour solution ȳ1 = 2 et ȳ2 = 34 .

    4
    SMA S3 AModule : M4-Program Math Session 1 - 2020/21 Le 8 Mars 2021

    Nom et Prénom : —————————————————————–

    Numéro d’Apogée : ————————————— Numéro de table : ————————-

    Exercice 3 : (6 points)
    Soient f (x, y) = 12 (x2 + y 2 ) et
    1
    C = {(x, y) ∈ R2 : g(x, y) = (x + y)2 + (x − y)2 − 4 = 0}.
    2
    On considère le problème

    Minimiser f (x, y)
    Sous-contrainte : (x, y) ∈ C

    1. Montrer que f est convexe sur R2 .


    2. L’esnsemble C est-il convexe ? (Justifier)
    3. En utilisant les conditions d’optimalité, déterminer tous les candidats aux minimum
    locaux de f sur C.
    4. En déduire les minimaux globaux de f sur C.

    Solution : 1 (1,5 pt). Pour justifier la convexité de f , on peut utiliser directe-


    ment la définition, mais cela est plus coûteux en calcul. Puisque f est de classe
    C 2 sur R2 , on utilisera la méthode du hessien :
    On a le gradient de f et donc son hessien sont respectivement :
       
    x 2 1 0
    ∇f (x, y) = et ∇ f (x, y) = .
    y 0 1

    Toutes les valeurs propres de ∇2 f (x, y) valent +1 > 0, donc ∇2 f (x, y) est définie
    positive pour tout (x, y) ∈ R2 . On déduit que f est convexe.
    √ √ √ √
    2. (1 pt) L’ensemble C n’est pas convexe, car ( 2, 2) et −( 2, 2) sont
    dans C, alors que
    1 √ √ 1 √ √
    ( 2, 2) + (− 2, − 2) = (0, 0) ∈/ C.
    2 2

    3. (2,5 pts) On a à minimiser f sur C qui est un ensemble à une seule contrainte
    égalité. Donc d’après le théorème des conditions nécessaires du 1er ordre, si f et
    g sont de classe C 1 sur R2 , si (x, y) ∈ C un extremum local de f sur l’ensemble
    C, et ∇g(x, y) 6= 0, alrs il existence un unique λ ∈ R (multiplicateurs de
    Lagrange) tel que
    ∇f (x, y) = λ∇g(x, y).

    5
    En appliquant cette condition et la contrainte, on aura le système suivant :

      x = λ(3x − y) (1)
    ∇f (x, y) = λ∇g(x, y)
    ⇔ y = λ(−x + 3y) (2)
    g(x, y) = 0  1 2 2
    2 (x + y) + (x − y) = 4 (3)

    En faisant une différence entre (1) et (2), on aboutit au système équivalent



     (4λ − 1)(x − y) = 0 (1b)
    y = λ(−x + 3y) (2)
     1 2 2
    2 (x + y) + (x − y) = 4 (3)

    ? Si λ = 14 , alors (2) donne y = −x, et donc d’après (3)

    4 = (2x)2 = 4x2 =⇒ x = ±1.

    Ainsi, (x, y, λ) = (1, −1, 14 ) ou (x, y, λ) = (−1, 1, 14 ).

    ? Si λ 6= 14 , alors (1b) donne y = x, et donc d’après (3) et (2)


    1 √ 1
    4 = (2x)2 = 2x2 =⇒ x = ± 2 et λ = .
    2 2
    √ √ 1 √ √ 1
    Ainsi, (x, y, λ) = (− 2, − 2, 2 ) ou (x, y, λ) = ( 2, 2, 2 ).
    On déduit que tous les candidats aux minimum locaux de f sur C sont
    √ √
    ±(1, −1) et ± ( 2, 2).

    4. (1 pt) Pour conclure les minimaux√globals√ de f , il suffit de calculer les va-


    leurs de f aux points ±(1, −1) et √ ±√( 2, 2).
    On a f (±(1, −1)) = 1 et f ±( 2, 2) = 2, donc les deux points (−1, 1) et
    (1, −1) réalisent la valeur minimale globale de f sur C.

    =========================================== Fin d’épreuve

    Vous aimerez peut-être aussi