Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Importer

Bienvenue sur Scribd !

  • 7 vues

    enonce5

    Transféré par

    bdrsmsng

    Droits d'auteur :

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

    enonce5

    Transféré par

    bdrsmsng
    7 vues2 pages

    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é ?

    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
    7 vues2 pages

    enonce5

    Transféré par

    bdrsmsng

    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 2

    EPFL RECHERCHE OPÉRATIONNELLE

    Institut de Mathématiques IN/MA


    J.-F. Hêche HIVER 2002/2003

    SÉRIE D’EXERCICES 5

    Les énoncés des séries et leurs corrigés ainsi que les copies des présentations sont disponibles
    sur le site du cours : roso.epfl.ch/cours/ro/2002-2003.

    Problème 1
    Donner le problème dual de chacun des programmes linéaires suivants.
    a)
    Max z = 7x2 + 2x3
    s.c. x1 + x2 + 2x3 = −1
    −2x1 + x2 + x3 ≤ 7
    x1 ∈ R
    x2 ≤ 0
    x3 ≥ 0
    b)
    Min z = 4x1 + 2x2
    s.c. −x1 + 2x2 ≥ −5
    x1 + x 2 ≥ 0
    x1 ≥ 0
    x2 ∈ R
    c)
    Max z = 3x1 − 5x2
    s.c. x 1 − x2 + x3 ≤ 4
    2x2 + x3 = 2
    x2 , x 3 ≥ 0
    d)
    Min z = 3x1 − x3
    s.c. 2x1 − x2 + 2x3 ≥ 5
    3x2 + 4x3 = 12
    x1 ≤ 6
    x2 , x3 ≥ 0
    e)
    Max z = 5x2 + x3
    s.c. −x1 + 4x2 + 2x3 ≤ 8
    2x1 + x3 = 6
    x1 , x2 ≥ 0
    x3 ≥ −3

    Problème 2
    On considère la paire de programmes linéaires :
    A : max z = cx B : min w = cx
    s.c. Ax = b s.c. Ax = b
    x ≥ 0 x ≥ 0

    1
    Décider si l’affirmation suivante est vraie ou fausse (justifier votre réponse) :
    Si le programme linéaire A n’a pas d’optimum fini, alors le programme
    linéaire B possède un optimum fini.

    Problème 3
    Une fabrique de feux d’artifice produit trois types de fusées, des rosaces, des étoiles et des
    fontaines. Les prix de vente, les quantités requises de poudre et de carton ainsi que le nombre
    d’heures de construction sont différents pour chaque type de fusées et sont résumés dans le
    tableau suivant :
    fusées de fusées de fusées de
    type rosace type étoile type fontaine
    Temps de construction [min] 4 2 12
    Quantité de poudre [g] 100 150 100
    Quantité de carton [g] 20 10 40
    Prix de vente [Frs] 48 36 90

    Pour la semaine à venir, la fabrique dispose de 3000 minutes pour la construction, de 100 kg de
    poudre et de 12 kg de carton.

    a) Formuler un programme linéaire aidant la fabrique à déterminer une production maximi-


    sant son chiffre d’affaires.
    b) Donner le programme linéaire dual du problème précédent.
    c) Résoudre le programme primal.
    d) Donner la solution optimale du programme dual.
    e) Si la fabrique pouvait augmenter la quantité de ressources en poudre ou en carton, dans
    laquelle de ces deux ressources serait-il conseillé d’investir en premier?

    Problème 4 (MA)
    On considère le domaine P suivant : P = {x ∈ Rn
    | ai x ≤ bi , i = 1 . . . ,m}. La boule B(y,r) de
    centre y et de rayon r est définie par B(y,r) = {x ∈ R n | kx − yk ≤ r} où k · k est la norme
    euclidienne. On cherche à déterminer la boule de rayon maximal contenue dans P . Formuler ce
    problème comme un programme linéaire.

    Problème 5 (MA)
    Soit A ∈ Mm×n . Montrer que les affirmations suivantes sont équivalentes :

    (1) Ax ≤ 0 n’a que la solution triviale ;


    (2) yA = c, y ≥ 0 a des solutions ∀ c ∈ Rn .

    21 novembre 2002 – JFH/ro

    Vous aimerez peut-être aussi