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

Bienvenue sur Scribd !

  • 5 vues

    INF-L3-PLin-22

    Transféré par

    Hajar

    Droits d'auteur :

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

    INF-L3-PLin-22

    Transféré par

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

    INF-L3-PLin-22

    Transféré par

    Hajar

    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

    Corrigé EMD Programmation linéaire 3ième Année LMD Informatique Février 2022

    Exercice 1 (7 pts)

    Rappel : L’exercice 1 est considéré en plus comme micro interrogation

    1/Modélisation : (5pts) 2/ Forme canonique du programme linéaire :(2pts)

    Définition des variables de décision du PL Fonction objective Max sous contraintes de signe ≤ .

    X1 : Qté de produits gamme 1 il suffit de multiplier les deux premières


    1pt
    X2 : Qté de produits gamme 2 contraintes du PL par – 1 pour avoir le signe ≤

    -x1 ≤ - 80
    0.5pt
    Max Z = 100x1 + 80x2 -x2 ≤ - 10 2pts

    0.5pt
    Sc x1 ≥ 80

    x2 ≥ 10 05pt

    x2 ≤ 50 0.5pt
    x1 + x2 ≤ 200 0.5pt
    x1 ≥ 0 , x2 ≥ 0 0.5pt

    Modélisation correcte
    1pt

    Exercice 2 (13pts)

    Résolution graphique :

    Calcul des coordonnées de 2 points pour chaque droite représentant chaque contrainte en équation
    ainsi que la droite Dz représentant la fonction objective à l’origine des axes.
    D1 : x1 + x2 = 5 (0,5) et (5,0)
    1.5pts
    D2 : x1+ 2x2 = 2 (0,1) et (2,0)
    D3 : x1 - 3x2 = 3 (0,-1) et (3,0)

    Dz : Z = x1 + 2x2 = 0 x2 = (-1/2) * x1 (0,0) et (1,-1/2) 0.5pt


    s
    X2
    D1

    2pts polyèdre juste

    D3

    E C
    POLYEDRE
    A
    2pts
    B
    1 2 3 4 5 6 ……..… X1 sur chaque droite bien tracée
    Solution optimale : Dz D2 sur la selection zone admissible ou non
    En déplaçant la droite Dz // à elle-même jusqu’au dernier point de contact avec le polyèdre nous donne
    le sommet optimum, sur le schéma c’est le sommet D résultat de l’intersection des 2 droites D1 et l’axe
    des ordonnées, ici on peut lire directement les coordonnées de ce point sur le schéma.
    Soit x1 = 0 et x2 = 5.
    Soit la solution optimale de ce programme linéaire : 1pt

    X*1 = 0 X*2 = 5 avec Z* max = x1 + 2*x2 = 0 + 2 * 5 = 10.

    Confirmation du résultat obtenu par la méthode du simplexe tableaux :


    Tableau initial (du programme linéaire sous la forme standard)
    1pt 2pts
    Tableau initial Tableau n° 1

    Cj 1 2 0 0 0 -M b cj 1 2 0 0 0 -M b
    Xj X1 X2 X3 X4 X5 X6 Xj X1 X2 X3 X4 X5 X6
    CB XB CB XB
    0 x3 1 1 1 0 0 0 5 0 x3 1/2 0 1 1/2 0 4
    -M x6 1 2 0 -1 0 1 2 2 x2 1/2 1 0 -1/2 0 1
    0 x5 1 -3 0 0 1 0 3 0 x5 5/2 0 0 -3/2 1 6
    Zj - Cj -M-1 -2M- 0 M 0 0 Z=- Zj - Cj 0 0 0 -1 0 Z =2
    2 2M
    X2 entre en base x6 sort de la base x4 entre en base x3 sort de la base
    L2=L2/2 L1=L1 – 1*L2 L3=L3 + 3*L2 L1=L1/1/2 L2=L2 + 1/2 *L1 L3=L3 + 3/2*L1

    Tableau n°2 2pts Tableau n°….

    Cj 1 2 0 0 0 -M b cj 1 2 0 0 0 -M b
    Xj X1 X2 X3 X4 X5 X6 Xj X1 X2 X3 X4 X5 X6
    CB XB CB XB
    0 x4 1 0 2 1 0 8
    2 x2 1 1 1 0 0 5
    0 x5 4 0 3 0 1 18
    Zj - Cj 1 0 2 0 0 Z Zj - Cj Z=
    =10
    Solution optimale : x2*=5 x4*=8 x5*=18 x1*=x3*=0 Z*=10 résultat confirmé

    1pt

    Vous aimerez peut-être aussi