[PDF] Searches related to les Étapes de l +algorithme du simplexe

View - Download Searches related to les Étapes de l +algorithme du simplexe

Previous PDF

Next PDF

Algorithme du simplexe

Brice Mayag

Cours RO

Brice MayagAlgorithme du simplexeCours RO 1 / 30

Exemple 1

Plan

1Exemple 1

2Exemple 2

3L"algorithme g´en´eral du simplexe:

Les ´etapes du simplexe

Retour `a l"exemple 1

Retour `a l"exemple 2

Brice MayagAlgorithme du simplexeCours RO 2 / 30

Exemple 1

Exemple

A l"approche des fˆetes de Pˆaques, un artisan chocolatier d´ecide de confectionner des oeufs en chocolat. En allant inspecter ses r´eserves, ilconstate qu"il lui reste 18 kg de cacao, 8 kg de noisettes et 14 kg de lait. Il a deux sp´ecialit´es : l"oeuf Extra et l"oeuf Sublime. Un oeuf Extra n´ecessite 1 kg de cacao, 1 kg de noisettes et 2 kg de lait. Un oeuf Sublime n´ecessite 3 kg de cacao, 1 kg de noisettes et 1 kg de lait. Il fera un profit de 20 euros en vendant un oeuf Extra, et de30 euros en vendant un oeuf Sublime. Combien d"oeufs Extra et Sublime doit-il fabriquer pour faire le plus grand b´en´efice possible ?

Oeuf Extra Oeuf SublimeStock

Cacao1 318

Noisette1 18

Lait2 114

B´en´efice20 30

Brice MayagAlgorithme du simplexeCours RO 3 / 30

Exemple 1

Exemple

Si on note x1le nombre d"oeufs extra et x2le nombre d"oeufs sublime alors le probl`eme admet la mod´elisation suivante:

Maxz= 20x1+ 30x2

x x x

1,x2≥0

La forme standard du probl`eme sera:

Maxz= 20x1+ 30x2

x

1+ 3x2+

x3= 18 x 1+x2+ x4= 8

2x1+x2+

x5= 14 x

1,x2,x3,x4,x5≥0

Brice MayagAlgorithme du simplexeCours RO 4 / 30

Exemple 1

A partir de la forme standard, on construit le tableau suivant:

Exemple (Dictionnaire 1)

x3= 18-x1-3x2 x4= 8-x1-x2 x5= 14-2x1-x2 z= 20x1+ 30x2

Ce tableau est appel´edictionnaire

Les variablesx3,x4,x5sont appel´eesvariables de base Les variablesx1,x2sont appel´eesvariables hors-base Lasolution basique (ou solution de base)associ´ee `a un dictionnaire est obtenue en donnant la valeur 0 `a toutes les variables hors-base.

On aura donc comme solution de base

x1= 0,x2= 0,x3= 18,x4= 8,x5= 14.

Le b´en´efice correspondant est

z= 0.

Brice MayagAlgorithme du simplexeCours RO 5 / 30

Exemple 1

En partant de cette solution basique,on va chercher `a am´eliorer le b´en´eficez.

Pour cela on va

choisir une variable hors-base dont le coefficient dans la derni`ere ligne (ligne dez) est positif . Par exemplex1. Il est ´evident que si on fait croˆıtrex1`a partir de 0, les autres variables hors-base restant nulles, la valeur de la fonction ´economiquezcroˆıt aussi. Mais jusqu"o`u peut-on "pousser"x1, tout en gardantx2`a z´ero? Il faut aussi que la solution reste admissible. Les contraintes sur l"augmentation dex1sont alors: x x x

Brice MayagAlgorithme du simplexeCours RO 6 / 30

Exemple 1

On fait un changement de dictionnaire en ´echangeant les rˆoles dex1etx5. Pour cela, on utilise la troisi`eme ´equation du Dictionnaire 1 (´equation contenantx5) pour exprimerx1 en fonction dex2etx5: x

1= 7-1

2x2-12x5

On remplace ensuitex1par cette expression dans les autres ´equations du dictionnaire:

Exemple (Dictionnaire 2)

x3= 11-52x2+12x5x4= 1-12x2+12x5x1= 7-12x2-12x5z= 140 + 20x2-10x5 La variablex5estsortie de la baseet la variablex1estentr´ee en base x3,x4,x1deviennent les variables de base x1etx5deviennent les variables hors-base On aura donc comme solution de base du Dictionnaire 2 x1= 7,x2= 0,x3= 11,x4= 1, x 5= 0 . Le b´en´efice correspondant estz= 140.

Brice MayagAlgorithme du simplexeCours RO 7 / 30

Exemple 1

En partant de cette solution basique,on va chercher `a am´eliorer le b´en´eficez.

Pour cela on va

choisir une variable hors-base dont le coefficient dans la derni`ere ligne (ligne dez) est positif . Seulex2a un coefficient positif.

On fait donc entrerx2dans la base.

Mais jusqu"o`u peut-on "pousser"x2, tout en gardantx5`a z´ero? Il faut aussi que la solution reste admissible. Les contraintes sur l"augmentation dex2sont alors: x 5x x

Brice MayagAlgorithme du simplexeCours RO 8 / 30

Exemple 1

On fait un changement de dictionnaire en ´echangeant les rˆoles dex2etx4. On fait sortirx4de la base et on fait rentrerx2`a sa place en faisant les mˆemes manipulations que pr´ec´edemment. On obtient le dictionnaire suivant:

Exemple (Dictionnaire 3)

x3= 6 + 5x4-2x5 x2= 2-2x4+x5 x1= 6 +x4-x5 z= 180-40x4+ 10x5 x3,x1,x2deviennent les variables de base x4etx5deviennent les variables hors-base On aura donc comme solution de base du Dictionnaire 3 x1= 6,x2= 1,x3= 6, x

4= 0,x5= 0

. Le b´en´efice correspondant estz= 180.

Brice MayagAlgorithme du simplexeCours RO 9 / 30

Exemple 1

En partant de cette solution basique,on va chercher `a am´eliorer le b´en´eficez.

Pour cela on va

choisir une variable hors-base dont le coefficient dans la derni`ere ligne (ligne dez) est positif . Seulex5a un coefficient positif.

On fait donc entrerx5dans la base.

Mais jusqu"o`u peut-on "pousser"x5, tout en gardantx4`a z´ero? Il faut aussi que la solution reste admissible. Les contraintes sur l"augmentation dex5sont alors: x x

2≥0?x5≥ -1

x

Brice MayagAlgorithme du simplexeCours RO 10 / 30

Exemple 1

On fait un changement de dictionnaire en ´echangeant les rˆoles dex3etx5. On fait sortirx3de la base et on fait rentrerx5`a sa place en faisant les mˆemes manipulations que pr´ec´edemment. On obtient alors le dictionnaire suivant:

Exemple (Dictionnaire 4)

x5= 3-12x3+52x4x2= 5-12x3+12x4x1= 3 +12x3-32x4z= 210-5x3-15x4 x5,x1,x2deviennent les variables de base x3etx4deviennent les variables hors-base On aura donc comme solution de base du Dictionnaire 3 x1= 3,x2= 5,x5= 3, x

3= 0,x4= 0

. Le b´en´efice correspondant estz= 210. Tous les coefficients de la derni`ere ligne ´etant n´egatifs,nous avons trouv´e la solution du probl`eme: 3 oeufs Extra, 5 oeufs Sublime avec unreste de 0 kg de cacao, 0 kg de Noisette et 3 kgs de lait, le tout pour un b´en´efice de 210 euros.

Brice MayagAlgorithme du simplexeCours RO 11 / 30

Exemple 2

Plan

1Exemple 1

2Exemple 2

3L"algorithme g´en´eral du simplexe:

Les ´etapes du simplexe

Retour `a l"exemple 1

Retour `a l"exemple 2

Brice MayagAlgorithme du simplexeCours RO 12 / 30

Exemple 2

Exemple

Une entreprise fabrique quatre produits. La fabrication dechaque produit n´ecessite une certaine quantit´e de ressources. Les ressources consomm´ees, les stocks des ressources et les b´en´efices des produits sont r´ecapitul´es dans le tableau suivant:

Produit 1 Produit 2 Produit 3 Produit 4Stock

Ressource A2 4 5 742

Ressource B1 1 2 217

Ressource C1 2 3 324

B´en´efice7 9 18 17

´Ecrire le programme lin´eaire permettant d"´etablir un plan de production de fa¸con `a maximiser le chiffre d"affaires.

Brice MayagAlgorithme du simplexeCours RO 13 / 30

Exemple 2

Exemple

Si on note x1; x2; x3; x4les quantit´es respectives de produits 1, 2, 3, 4, alors le probl`eme admet la mod´elisation suivante:

Maxz= 7x1+ 9x2+ 18x3+ 17x4

x x x

1,x2,x3,x4≥0

Remarque

Ce probl`eme est mis ici sous sa forme canonique (avec la recherche du Maximum)

Brice MayagAlgorithme du simplexeCours RO 14 / 30

Exemple 2

Ce probl`eme mis sous forme standard s"´ecrit:

Exemple

Maxz= 7x1+ 9x2+ 18x3+ 17x4

2x1+ 4x2+ 5x3+ 7x4+

x5= 42 x

1+x2+ 2x3+ 2x4+

x6= 17 x

1+ 2x2+ 3x3+ 3x4+

x7= 24 x

1,x2,x3,x4,x5,x6,x7≥0

Les variablesx5,x6,x7sont des variables d"´ecart qui mesurent pour chaque ressource l"´ecart entre la quantit´e initialement disponible et la quantit´e consomm´ee par le plan de fabrication donn´e par les variablesx1,x2,x3etx4.

Brice MayagAlgorithme du simplexeCours RO 15 / 30

Exemple 2

A partir de la forme standard, on construit le tableau suivant:

Exemple (Dictionnaire 1)

x5= 42-2x1-4x2-5x3-7x4 x6= 17-x1-x2-2x3-2x4 x7= 24-x1-2x2-3x3-3x4 z= 7x1+ 9x2+ 18x3+ 17x4

Ce tableau est appel´edictionnaire

Les variablesx5,x6,x7sont appel´eesvariables de base Les variablesx1,x2,x3etx4sont appel´eesvariables hors-base Lasolution basique (ou solution de base)associ´ee `a un dictionnaire est obtenue en donnant la valeur 0 `a toutes les variables hors-base.

On aura donc comme solution de base

x1= 0,x2= 0,x3= 0,x4= 0,x5= 42, x

6= 17 etx7= 24

. Le b´en´efice correspondant estz= 0.

Brice MayagAlgorithme du simplexeCours RO 16 / 30

Exemple 2

En partant de cette solution basique,on va chercher `a am´eliorer le b´en´eficez.

Pour cela on va

choisir une variable hors-base dont le coefficient dans la derni`ere ligne (ligne dez) est positif . Par exemplex3. Il est ´evident que si on fait croˆıtrex3`a partir de 0, les autres variables hors-base restant nulles, la valeur de la fonction ´economiquezcroˆıt aussi. Mais jusqu"o`u peut-on "pousser"x3, tout en gardantx1,x2etx4`a z´ero? Il faut aussi que la solution reste admissible. Les contraintes sur l"augmentation dex3sont alors: x x x

Brice MayagAlgorithme du simplexeCours RO 17 / 30

Exemple 2

On fait un changement de dictionnaire en ´echangeant les rˆoles dex3etx7. Pour cela, on utilise la troisi`eme ´equation du Dictionnaire 1 (´equation contenantx7) pour exprimerx3 en fonction dex1,x2,x4etx7: x

3= 8-1

3x1-23x2-x4-13x7

On remplace ensuitex3par cette expression dans les autres ´equations du dictionnaire:

Exemple (Dictionnaire 2)

x5= 2-13x1-23x2+53x7-2x4x6= 1-13x1+13x2+23x7x3= 8-13x1-23x2-13x7-x4z= 144 +x1-3x2-6x7-x4 La variablex7estsortie de la baseet la variablex3estentr´ee en base x5,x6,x3deviennent les variables de base x1,x2,x4etx7deviennent les variables hors-base On aura donc comme solution de base du Dictionnaire 2 est x1= 0,x2= 0,x3= 8, x

4= 0,x5= 2,x6= 1 etx7= 0

. Le b´en´efice correspondant estz= 144.

Brice MayagAlgorithme du simplexeCours RO 18 / 30

Exemple 2

En partant de cette solution basique,on va chercher `a am´eliorer le b´en´eficez.

Pour cela on va

choisir une variable hors-base dont le coefficient dans la derni`ere ligne (ligne dez) est positif . Seulex1a un coefficient positif.

On fait donc entrerx1dans la base.

Mais jusqu"o`u peut-on "pousser"x1, tout en gardantx2,x4etx7`a z´ero? Il faut aussi que la solution reste admissible. Les contraintes sur l"augmentation dex1sont alors: x x x

Brice MayagAlgorithme du simplexeCours RO 19 / 30

Exemple 2

On fait un changement de dictionnaire en ´echangeant les rˆoles dex1etx6. On fait sortirx6de la base et on fait rentrerx1`a sa place en fait les mˆemes manipulations que pr´ec´edemment. On obtient le dictionnaire suivant:

Exemple (Dictionnaire 3)

x5= 1 +x6-x2+x7-2x4 x1= 3-3x6+x2+ 2x7 x3= 7 +x6-x2-x7-x4 z= 147-3x6-2x2-4x7-x4 x5,x1,x3deviennent les variables de base x6,x2,x4etx7deviennent les variables hors-base On aura donc comme solution de base du Dictionnaire 3 x1= 3,x2= 0,x3= 7, x

4= 0,x5= 1,x6= 0 etx7= 0

. Le b´en´efice correspondant estz= 147. Tous les coefficients de la derni`ere ligne ´etant n´egatifs,nous avons trouv´e la solution du probl`eme: (3,0,7,0)

Brice MayagAlgorithme du simplexeCours RO 20 / 30

L"algorithme g´en´eral du simplexe:

Plan

1Exemple 1

2Exemple 2

3L"algorithme g´en´eral du simplexe:

Les ´etapes du simplexe

Retour `a l"exemple 1

Retour `a l"exemple 2

Brice MayagAlgorithme du simplexeCours RO 21 / 30

L"algorithme g´en´eral du simplexe:

Dans l"algorithme du simplexe, chaque dictionnaire est mat´erialis´e par un tableau appel´e tableau du simplexequi apr`es la mise sous forme standard du probl`eme lin´eaire se pr´esente comme suit:

Bbx1...xn+m

xB1b1α11... α1,n+m .xBmbmαm1... αm,n+m

¯cz¯c1...¯cn+m

Brice MayagAlgorithme du simplexeCours RO 22 / 30

L"algorithme g´en´eral du simplexe:Les ´etapes du simplexe On consid`ere le probl`eme et saforme standard(apr`es ajout desmvariables d"´ecart): Max n? j=1c jxj n j=1a x j≥0,j= 1,...,n

Maxn+m?

j=1c jxj n+m? j=1a ijxj=bi,i= 1,...,m x j≥0,j= 1,...,n+m Les ´etapes de l"algorithme du simplexe sont:´Etape 1:Initialisation du tableau du simplexe: bi=bi,cj=cj, αij=aij,z=0

Bbx1...xn+m

xB1b1α11... α1,n+m xBmbmαm1... αm,n+m

¯cz¯c1...¯cn+m

Bbx1...xn+m

xB1b1a11...a1,n+m xBmbmam1...am,n+m

¯c0c1...cn+m

Brice MayagAlgorithme du simplexeCours RO 23 / 30

L"algorithme g´en´eral du simplexe:Les ´etapes du simplexe

Bbx1...xn+m

xB1b1α11... α1,n+m .xBmbmαm1... αm,n+m

¯cz¯c1...¯cn+m

´Etape 2:Choix de la colonne du pivot(variable `a entrer dans la base):

2Sinon, choisir une colonnestelle quecs>0

´Etape 3:Choix de la ligne du pivot(variable `a sortir de la base):

2Sinon, choisir une lignertelle que

br

αrs= min{bi

αis:i= 1,...,m, αis>0}

Brice MayagAlgorithme du simplexeCours RO 24 / 30

L"algorithme g´en´eral du simplexe:Les ´etapes du simplexe

Bbx1...xs...xn+m

xB1b1α11...α1s... α1,n+m xBrbrαr1...αrs...αr,n+m xBmbmαm1...αms... αm,n+mquotesdbs_dbs23.pdfusesText_29

[PDF] Chapitre 3 Méthode du simplexe - Cours

[PDF] Algorithmique au lycée

[PDF] le programme d 'algorithmique sans ordinateur - Mathématiques

[PDF] Algorithmique programmation en langage C - vol1 - Hal

[PDF] Algorithmes et structures de données : TD 4 Corrigé - LaBRI

[PDF] ALGO 11 #339 Correction TD N°5

[PDF] Exemples de fonctions en Python - Lirmm

[PDF] Récursivité (1/3)

[PDF] Corrigé Série d exercices n°4 : Les fonctions et procédures

[PDF] Bases d 'algorithmique

[PDF] COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE

[PDF] FICHE n°6 : PROGRAMMER DES BOUCLES - Maths-et-tiques

[PDF] fiche maternelle algorithme imprimer- pdf documents

[PDF] Fiche enseignant ALGORITHMES NIVEAU : GRANDE SECTION

[PDF] Algorithme et numération - Académie de Nancy-Metz