Scribd Logo
Importer

Bienvenue sur Scribd !

  • 29 vues

    TD4 Dualité

    Transféré par

    hcrvhw8xrw
    Ce document contient plusieurs exercices de programmation linéaire portant sur la résolution par la méthode du simplexe, l'analyse de sensibilité, la dualité et l'introduction de nouvelles variables ou contraintes. Les exercices proposent de résoudre des programmes linéaires, compléter des tableaux de simplexe, déterminer des matrices inverses, étudier la stabilité des solutions et formuler des problèmes duaux.

    Droits d'auteur :

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

    TD4 Dualité

    Transféré par

    hcrvhw8xrw
    29 vues4 pages
    Ce document contient plusieurs exercices de programmation linéaire portant sur la résolution par la méthode du simplexe, l'analyse de sensibilité, la dualité et l'introduction de nouvelles variables ou contraintes. Les exercices proposent de résoudre des programmes linéaires, compléter des tableaux de simplexe, déterminer des matrices inverses, étudier la stabilité des solutions et formuler des problèmes duaux.

    Titre original

    TD4_Dualité

    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 contient plusieurs exercices de programmation linéaire portant sur la résolution par la méthode du simplexe, l'analyse de sensibilité, la dualité et l'introduction de nouvelles variables ou contraintes. Les exercices proposent de résoudre des programmes linéaires, compléter des tableaux de simplexe, déterminer des matrices inverses, étudier la stabilité des solutions et formuler des problèmes duaux.

    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
    29 vues4 pages

    TD4 Dualité

    Transféré par

    hcrvhw8xrw
    Ce document contient plusieurs exercices de programmation linéaire portant sur la résolution par la méthode du simplexe, l'analyse de sensibilité, la dualité et l'introduction de nouvelles variables ou contraintes. Les exercices proposent de résoudre des programmes linéaires, compléter des tableaux de simplexe, déterminer des matrices inverses, étudier la stabilité des solutions et formuler des problèmes duaux.

    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 4

    FACULTE DES SCIENCES 3 ème Année L.

    F
    ECONOMIQUES ET DE GESTION Ing. Eco. & Financière
    DE SOUSSE chargé du cours : Mr Mourad Belkahla
    Année Universitaire 2023/2024

    SERIE 4 RECHERCHE OPERATIONNELLE

    Dualité et analyse de sensibilité

    EXERCICE 1

    On considère le programme linéaire suivant :


    𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 4𝑥1 + 5𝑥2 − 3𝑥3
    𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 𝑥2 + 𝑥3 ≤5
    𝑥1 − 𝑥2 ≥1
    𝑥1 + 3𝑥2 + 𝑥3 ≤ 11
    𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 ≥0
    1) Résoudre le programme linéaire par la méthode du simplexe.
    2) Ecrire le dual de ce programme et déduire son dernier tableau à partir de celui du primal.

    EXERCICE 2

    On considère le dernier tableau (incomplet) d’un programme linéaire de maximisation où la


    première et la deuxième contrainte sont de type (≤) et la troisième contrainte est de type (≥).
    Cj 2 3 4 0 0 0 XB
    Variables x1 x2 x3 e1 e2 e3
    CB de base
    1 3 1 1 0 0 100
    1 -2 0 0 1 0 3
    -2 4 0 1 0 1 93
    Zj
    Zj-Cj
    1) a) Compléter le tableau de ce programme.
    b) Déterminer la solution optimale de ce programme.

    2) a) Déterminer la valeur de 𝑐2 (le coefficient de 𝑥2 dans 𝑍) pour que la solution


    optimale initiale soit multiple.
    b) Dans quel intervalle peut varier 𝑐3 (le coefficient de 𝑥3 dans 𝑍) sans affecter
    l’optimalité de la solution initiale ?
    3) a) Déterminer la matrice de base inverse.

    1
    b) les valeurs initiales de seconds membres des contraintes sont : 𝑏1 = 100, 𝑏2 = 3
    et 𝑏3 = 7. Dans quel intervalle peut varier 𝑏3 sans affecter la base optimale
    initiale trouvée. ?
    4) Si on introduit une nouvelle variable 𝑥4 ayant les caractéristiques suivantes :
    𝑐4 = 5 , 𝑎14 = 𝑎24 = 𝑎34 = 1. Déterminer la nouvelle solution le cas échéant.
    5) Si on introduit la nouvelle contrainte suivante : 𝑥1 + 𝑥2 + 𝑥3 ≤ 10. La solution
    reste t- elle optimale ? Justifier.
    6) Ajouter une contrainte telle que la solution optimale initiale soit dégénérée.

    EXERCICE 3 (Examen Juin 2012)

    Une entreprise fabrique 3 produits 𝑃1 , 𝑃2 et 𝑃3 en quantités 𝑥1 , 𝑥2 et 𝑥3 respectivement.


    Le problème de son coût est représenté sous forme d’un programme linéaire (PL)
    comme suit :

    𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝐶 = 7𝑥1 + 3𝑥2 + 4𝑥3


    𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 𝑥2 ≥ 10
    2𝑥1 + 2𝑥2 + 𝑥3 ≤ 40
    −2𝑥1 + 𝑥2 − 𝑥3 ≥ 12
    𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

    1) Résoudre ce PL par la méthode du simplexe. (utiliser la méthode des pénalités).


    2) Déterminer la matrice de base inverse à l’optimum.
    3) Dans quel intervalle peut varier le second membre de la troisième contrainte
    (𝑏3 = 12) sans affecter la solution optimale ?
    4) Déterminer le dual et déduire son dernier tableau de simplexe.
    5) Vérifier le théorème des écarts complémentaires.
    6) L’entreprise a-t- elle intérêt à introduire un nouveau produit 𝑃4 ayant les
    caractéristiques suivantes : 𝑐4 = 2 , 𝑎14 = 2, 𝑎24 = 1 𝑒𝑡 𝑎34 = 1. Si oui
    déterminer la nouvelle solution.
    7) Si on ajoute la contrainte 𝑥1 + 𝑥2 + 𝑥3 ≤ 10, au problème initial, la solution
    optimale trouvée à la question 1) va –t- elle changer ?

    EXERCICE 4 (Extrait Examen Mai 2015)

    Le tableau du simplexe ci-dessous est associé à un programme linéaire de type


    maximisation. (𝑒1 , 𝑒2 ) sont les variables d’écarts.

    2
    Cj 2 3 6 0 0 XB
    Variables x1 x2 x3 e1 e2
    CB de base
    2/7 1 0 3/7 -1/7
    3/7 0 1 1/7 2/7
    Zj
    Zj-Cj

    1) Donner la matrice de base inverse 𝐵 −1 du tableau ci-dessus.


    2) Compléter le tableau et donner la solution optimale sachant que les valeurs initiales de
    second membre des contraintes sont : 𝑏1 = 10 𝑒𝑡 𝑏2 = 6.
    3) Donner la formulation du programme linéaire relative à ce tableau du simplexe.
    4) a) Ecrire le programme dual correspondant et déduire son dernier tableau du simplexe.
    b) Donner la solution optimale du dual.
    c) Vérifier le théorème des écarts complémentaires.

    Exercice 5 (Extrait examen Juin 2017)

    Soit le programme linéaire suivant :

    𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 2𝑥1 + 3𝑥2 + 𝑥3

    𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 2𝑥1 + 𝑥2 + 4𝑥3 ≤ 12


    𝑥1 + 𝑥2 + 2𝑥3 ≤ 10
    2𝑥1 + 4𝑥2 + 𝑥3 ≥ 16

    𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

    1) Ecrire le problème sous forme standard.


    2) On vous donne le tableau courant incomplet de ce programme (𝑒1 , 𝑒2 , 𝑒3 ) sont
    les variables d’écarts :

    3
    Cj XB
    Variables x1 x2 x3 e1 e2 e3
    CB de base
    3/2 0 15/4 1 0 1/4 8
    1/2 0 7/4 0 1 1/4 6
    1/2 1 1/4 0 0 -1/4 4

    Zj
    Zj-Cj

    Compléter le tableau courant de ce programme.


    3) Est-il optimal ? Sinon continuer les itérations jusqu'au tableau optimal et donner
    la solution optimale.
    4) Quelles sont les contraintes saturées à l'optimum ? Justifier votre réponse.
    5) Si le coefficient 𝑐1 de 𝑥1 dans 𝑍 passe de 2 à 6, la solution reste-elle optimale ?
    si non donner l’intervalle de variation de 𝑐1 qui laisserait la base optimale
    inchangée.
    6) Dans quel intervalle peut varier 𝑐2 dans 𝑍 sans affecter la base optimale ?
    7) Dans quel intervalle peut varier le coefficient de second membre de la deuxième
    contrainte 𝑏2 sans affecter la base optimale ?
    8) Ecrire le dual et déduire son dernier tableau à partir de celui du primal.
    9) Vérifier le théorème des écarts complémentaires.
    10) Si on ajoute une nouvelle variable 𝑥4 dont son coefficient dans la fonction 𝑍
    𝑐4 = 6 , et ces coefficients dans le système des contraintes sont : 𝑎14 = 𝑎24 = 𝑎34 =
    1. Est-il profitable que cette variable soit dans la base ? Si oui donner la nouvelle
    solution.

    Vous aimerez peut-être aussi