Modélisation Programme

  • Published on
    15-Oct-2015

  • View
    12

  • Download
    0

Embed Size (px)

Transcript

  • 1

  • 2

  • 3

  • 4

    Pour rsoudre numriquement un programme

    linaire, il faut quil ait une certaine forme que lon appelle " forme standard ".

  • 5

    Il faut utiliser de nouvelles variables (variables

    dcart ou variables artificielles) afin de transformer les contraintes ingalits en

    contraintes galits. Pour cela, nous devons

    appliquer les rgles de transformation suivantes :

    Donc pour obtenir le programme standard dun programme linaire, on doit appliquer

    lalgorithme suivant :

  • 6

  • 7

    On dit quune contrainte est sature

    pour une solution optimale, si son membre de

    gauche gal son membre adroite.

    En utilisant la forme standard du programme

    linaire, le modle gnral pour chaque itration,

    de la mthode des tableaux de simplexe est :

    Cj

    Toutes les variables

    Ci VB Qi A = (aij)ij

    Z zj

    cj - zj

    Aprs initialisation de toutes les variables, dans la colonne VB on note les variables qui sont

    dans la base (variables non nulles) ;

    Dans la colonne Qi, on note les valeurs des variables qui sont dans la base ;

    Dans la ligne Cj, on note les coefficients des variables qui figurent dans lexpression de la fonction conomique ;

  • 8

    zj est la somme des termes obtenus en multipliant les coefficients de la colonne Ci par

    les coefficients de xj ;

    Dans la colonne Ci, on note les coefficients de la fonction conomique des variables qui sont

    dans la base.

    : Un tableau du

    simplexe est optimal lorsque tous les coefficients de

    la ligne cj zj sont ngatifs ou nuls.

    La

    variable entrante est la variable associe

    Max{cj-zj} pour les variables hors base. Toutefois,

    si la valeur la plus leve nest pas unique, on slectionne alors lune ou lautre des variables correspondantes.

    1. On divise chacune des valeurs dans la colonne

    quantit Qj par les lments correspondants

  • 9

    qui apparaissent dans la colonne de la variable

    entrante. Nous ne divisons toutefois que par les

    lments strictement positifs pour assurer que le

    prochain programme soit ralisable.

    2. Nous choisissons parmi les valeurs obtenues en 1, celle qui a la plus petite valeur strictement

    positive.

    3. La variable en ligne avec cette plus petite valeur strictement positive devient alors la variable

    sortante

    Une solution est unique, dans le cas

    dune maximisation, si tous les coefficients de la ligne cj-zj pour les variables hors base sont < 0.

    Un tableau du

    simplexe est optimal lorsque tous les coefficients de

    la ligne cj zj sont ngatifs ou nuls.

    La

    variable entrante est la variable associe

    Min{cjzj} pour les variables hors base. Toutefois,

  • 10

    si la valeur la plus petite nest pas unique, on slectionne alors lune ou lautre des variables correspondantes

    Le mme que

    celui du problme de maximisation.

    Une solution est unique, dans le cas

    dune minimisation, si tous les coefficients de la ligne cj-zj pour les variables hors base sont > 0.

    Le tableau suivant rsume les tapes de la

    mthode de simplexe :

    1. Formuler le programme linaire ; 2. Vrifier que le second membre du PL est

    positif, sinon multiplier toutes contraintes

    dont le second membre est ngatif par -1 ;

    3. Ecrire le programme linaire sous la forme standard ;

    4. Construire tableau initial du simplexe ; 5. Choisir la variable entrante ; 6. Choisir la variable sortante et changer la

    variable sortante par la variable entrante sans

    oublier de changer aussi ci associ ;

  • 11

    7. Identifier le pivot (intersection de la colonne de la variable entrante et de la ligne de la

    variable sortante). Ramener llment pivot 1 et tous les lments de la colonne du pivot

    0 par soustraction de lignes ;

    8. Calculer Z en multipliant les coefficients de la colonne Ci par les coefficients de Qi et den faire la somme ;

    9. Calculer les zj en faisant la somme des termes obtenus en multipliant les coefficients de la

    colonne Ci par les coefficients de xj ;

    10. Calculer les cj - zj ; 11. Faire le test doptimalit. Si le test est valid, alors

    la solution obtenue est optimale. Sinon retourner

    ltape 5.

  • 12

  • 13

  • 14

    Le problme est impossible si une ou plusieurs

    variables artificielles sont prsentes dans la base

    du tableau de simplexe optimal, ce qui signifie

    que la solution donne par ce tableau nest pas rellement ralisable.

    Un programme de maximisation ou

    de minimisation avec seulement des contraintes

    de type ne peut pas tre impossible (sous lhypothse que le second membre est positif). Ceci est d au fait que lors de la rsolution de ce

  • 15

    genre de programme par la mthode de simplexe

    on n'utilise pas des variables artificielles.

    Le problme est solutions multiples (la solution

    nest pas unique) lorsquun des effets nets (cj-zj) relatif une variable hors base est nul.

  • 16

    Le problme est solution infinie ou non borne

    si la variable entrante nadmet aucune limite sur sa valeur dentre, cest dire que tous les ratios Qi /aij sont ngatifs ou nuls.

    Un programme linaire est dit dgnr si une ou

    plusieurs variables dans la base optimale sont

    nulles.

  • 17

    La solution optimale de ce problme

    est : x1 = 1, x2 = 0, x3 = 2 avec Z = 5

    La forme standard du programme linaire est

    Max (2x1 + 0 x2 + (3/2)x3 + 0S1 + 0S2 + 0S3)

    S.C x1 - x2 + S1 = 2

    2x1 + x3 + S2 = 4

    x1 + x2 + x3 + S3 = 3

    x1, x2, x3, S1, S2, S3 0

    Le tableau de simplexe initial est :

    2 0 3/2 0 0 0

    x1 x2 x3 S1 S2 S3

    0 S1 2 1 -1 0 1 0 0

    0 S2 4 2 0 1 0 1 0

    0 S3 3 1 1 1 0 0 1

    Z = 0 0 0 0 0 0 0

    2 0 3/2 0 0 0

  • 18

    La variable entrante est x1, mais les deux

    premires contraintes donnent la mme valeur

    minimale du ratio (2/1 ; 4/2 ; 3/1). Ceci indique

    que lorsque x1 passe 2, les variables dcart S1 et S2 vont sannuler malgr que lun des deux demeure encore dans la base.

    Choisissons arbitrairement de faire sortir de la

    base la variable dcart S1.

    2 0 3/2 0 0 0

    x1 x2 x3 S1 S2 S3

    2 x1 2 1 -1 0 1 0 0

    0 S2 0 0 2 1 -2 1 0

    0 S3 1 0 2 1 -1 0 1

    Z = 4 2 -2 0 2 0 0

    0 2 3/2 -2 0 0 La nouvelle solution ralisable de base est :

    x1 = 2, x2 = 0, x3 = 0, S1 = 0, S2 = 0, S3 = 1 et Z = 4.

    Cette solution de base est dite dgnre.

    Continuons les itrations relatives la mthode

    de simplexe. La variable entrante est x2.

    Le problme est quun des ratios est nul ce qui indique quon ne peut pas augmenter la valeur de

  • 19

    x2 puisque la valeur de la fonction objectif ne va

    pas augmenter et reste gale 4.

    Si on ritre une autre fois, on obtient :

    2 0 3/2 0 0 0

    x1 x2 x3 S1 S2 S3

    2 x1 5/2 1 0 1/2 1/2 0 3/2

    0 S2 -1 0 0 0 -1 1 -1

    0 x2 1/2 0 1 1/2 -1/2 0 1/2

    Z = 5/2 2 0 1 1 0 3

    0 0 1/2 0 0 -3

    Ce tableau nest pas optimal, la variable entrante est x3 et la variable sortante est x2. On remarque

    aussi que ce passage dune solution une autre ne saccompagne pas dune augmentation de la valeur de la fonction conomique.

    On peut facilement vrifier que nous sommes en

    train de cycler sans atteindre la solution

    optimale. Ce genre de cyclage dans la mthode de

    simplexe est dangereux et on doit lidentifier avant de commencer rsoudre le problme,

    sinon on passera un temps norme sans atteindre

    la solution optimale.

  • 20

  • 21

  • 22

  • 23

    Dans la plupart des problmes que nous traitons,

    les variables considres x1, x2, , xn sont supposs valeurs relles. Or, dans certaines

    applications, on peut se trouver dans les trois

    situations suivantes :

    Les variables (x1, x2, ..., xn) ne peuvent prendre que des valeurs entires (par exemple lorsque

    ces variables reprsentent un nombre dunit non fractionnables telles que nombre de

    machines, units produites, nombre de

    personnes). Les programmes correspondants

    sont dits PROGRAMME LINAIRE EN

    NOMBRES ENTIERS (PLNE).

    Certaines des variables x1, x2, , xn ne peuvent prendre que des valeurs entires, les autres

    tant valeurs relles. Les programmes

    correspondants sont dits PROGRAMME

    LINAIRE EN NOMBRES MIXTES.

  • 24

    Un cas particulier de la premire situation est celle o toutes les variables entires doivent

    prendre les valeurs 0 ou 1. Les programmes

    correspondants sont dits PROGRAMME

    LINAIRE A VARIABLES BINAIRES.

    Pour ces divers cas, on pourrait penser quil s'agit simplement de rsoudre ces problmes par

    la mthode de simplexe dans laquelle les variables

    sont supposes valeurs relles et arrondir les

    rsultats obtenus aux valeurs entires les plus

    proches.

    Avec un tel raisonnement, il nest pas possible daffirmer que la solution arrondie soit une solution ralisable du programme linaire ou

    encore quil nexiste pas une meilleure solution entire.

  • 25

    La rsolution des modles suivants permet

    dillustrer les consquences darrondir les solutions valeurs relle