Scribd Logo
Importer

Bienvenue sur Scribd !

  • 57 vues

    TD 4

    Transféré par

    beckerrolandh
    Le document présente cinq exercices sur la programmation linéaire. Les exercices portent sur la transformation de problèmes généralisés en problèmes standards, la dualité généralisée et la résolution de problèmes par la méthode du simplexe.

    Droits d'auteur :

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

    TD 4

    Transféré par

    beckerrolandh
    57 vues1 page
    Le document présente cinq exercices sur la programmation linéaire. Les exercices portent sur la transformation de problèmes généralisés en problèmes standards, la dualité généralisée et la résolution de problèmes par la méthode du simplexe.

    Titre original

    td4

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

    Le document présente cinq exercices sur la programmation linéaire. Les exercices portent sur la transformation de problèmes généralisés en problèmes standards, la dualité généralisée et la résolution de problèmes par la méthode du simplexe.

    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
    57 vues1 page

    TD 4

    Transféré par

    beckerrolandh
    Le document présente cinq exercices sur la programmation linéaire. Les exercices portent sur la transformation de problèmes généralisés en problèmes standards, la dualité généralisée et la résolution de problèmes par la méthode du simplexe.

    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
    sur 1

    L1 Info/MIASHS/Math - 2014/2015 TD No.

    4 12 avril 2015
    Programmation linéaire
    R. Becker

    Exercice n◦ 1 D UAUX DES PROBL ÈMES G ÉN ÉRALIS ÉS

    1. Transformer le problème de maximisation généralisé on remplaçant les contraintes d’égalité par deux inégalités,
    n
    X n
    X n
    X
    aij xj = bi → aij xj ≤ bi et (−aij )xj ≤ −bi ,
    j=1 j=1 j=1

    et en remplaçant toute variables xj sans restriction de signe par deux variables positives x0j , x00j telles que xj =
    x0j − x0j . On obtient donc un problème de maximisation standard.
    2. Utiliser les même techniques pour transformer le problème de minimisation généralisé en un problème de mini-
    misation standard.
    3. Montrer que les deux problèmes trouvés précédemment sont duaux (l’un est le dual de l’autre et vice versa).

    Exercice n◦ 2 D UALIT É G ÉN ÉRALIS ÉE


    Soit x admissible pour le problème de maximisation généralisé et y ∗ admissible pour le problème de minimisation
    ∗

    généralisé. A l’aide du théorème de la dualité généralisé, montrer que x∗ et y ∗ sont optimaux si et seulement si
    n
    X
    yi∗ = 0 pour tout i tel que aij x∗j < bi , (1)
    j=1
    Xm
    x∗j = 0 pour tout j tel que yi∗ aij > cj . (2)
    i=1

    Exercice n◦ 3 S IMPLEXE POUR LE PROBL ÈME G ÉN ÉRALIS É

    1. Trouver le dual du problème généralisé donné comme exemple en cours.


    2. Résoudre ce problème dual.

    Exercice n◦ 4 S IMPLEXE
    On considère max x1 − 2x2 − 3x3 − x4 sous les contraintes xi ≥ 0 pour 1 ≤ i ≤ 4 et :

    x1 − x2 − 2x3 − x4 ≤ 12,
    2x1 + x3 − 4x4 ≤ 2,
    −2x1 + x2 + x4 ≤ 4.

    Résoudre par la méthode du simplexe et donner la valeur et les solutions primale et duale.

    Exercice n◦ 5 S IMPLEXE
    On considère max 3x1 − x2 + 5x3 sous les contraintes xi ≥ 0 pour 1 ≤ i ≤ 3 et :

    −x1 + 4x2 + 2x3 ≤ 0,


    −2x1 + x2 − 3x3 ≤ −2,
    7x2 + x3 ≤ 1.

    Résoudre par la méthode du simplexe et donner la valeur et les solutions primale et duale.

    Vous aimerez peut-être aussi