La Methode Des Penalites ( Ou Du Grand m )

Embed Size (px)

Citation preview

La METHODE DES PENALITES ( ou du grand M)

Prsente par : AMRANI BADR ISSAM EL ALAOUI

Pourquoi la mthode du grand M ?

Pour deux raisons c est qu il ya des limites sur : Limites de la mthode graphique Limites de la mthode de simplexe

Limites de la mthode graphiqueCette mthode est limit deux variables la ralit reflte que des programmes linaires plusieurs variables

Limites de la mthode de simplexeNcessite que des contraintes soient infrieur ou gal dans le cas d un problme de maximisation or dans la ralit on a des contraintes de type suprieur ou gal et/ou de type gal, ainsi que des problme o on a minimiser au lieu de maximiser.

Dfinition :Cette mthode permet de tenir compte des variables artificielles. On les pnalise en leur affectant un coefficient de valeur trs leve dans la fonction conomique (- M pour un problme maximum, + M pour un problme minimum). Les pnalits ont pour objet de provoquer l'limination des variables artificielles au fil des itrations. Normalement, l'optimum (s'il existe) les variables artificielles sont hors base. Si celles-ci sont l'optimum dans la base, avec une valeur non nulle, le programme n'a pas de solution.

Les tapes de la mthode du grand MFormuler un programme linaire pour le problme rel. Dresser la forme canonique du problme Mettre le programme sous sa forme standard :introduction des variables d cart introduction des variables artificielles

Les tapes de la mthode du grand MLe choix des variables de base et les hors variables de base Elaboration des tableaux Le choix de la colonne pivot Le choix de la variable entrante et de la variable sortante.

Petit aperuSupposons la contrainte suivante : + 10 aprs l introduction du variable d cart on a + -e=10 Dans la solution de base ( =0 et =0) on aura donc e=10 qui contredit l hypothse de ngativit des variables

Petit aperuOn va transformer l galit et il devient a + -e +T=10 dans la solution de base on aurra e=0 T =10 T est appele variable artificielle cette variable ne doit pas intervenir dans la solution final d o la pnalisation avec M (M )

ApplicationSoit le programme linaire suivant : Min z = 3 x + 10 y 5 x + 6 y 10 2 x + 7 y 14 x 0; y 0 * Forme standard 5 x + 6 y - 1 e1 + 1 s1 = 10 2 x + 7 y - 1 e2 + 1 s2 = 14 Min z = 3 x + 10 y + M s1 + M s2 x 0 ; y 0 ; e1 0 ; e2 0; s1 0 ; s2 0