[PDF] [PDF] Algorithme du simplexe - LISIC

View - Download [PDF] Algorithme du simplexe - LISIC

Previous PDF

Next PDF

Algorithme du simplexe

Master 1

2014 / 2015

1 Applications

a - 8 >>>>>:maxz=32 x1+x2

2x1x24

x1+x21 x1+ 2x24

2x1+x212

x 1;x20 Mise sous forme de tableau : On ajoute les variables d'ecart pour obtenir la forme standard. A noter les coecients negatifs de la premiere lignezpuisquez32 x1x2= 0. Les variables de bases sont (e1;e2;e3;e4) puisquex1=x2= 0 est une solution admissible du systeme (les valeurs dee1,e2,e3ete4 sont bien positives lorsquex1=x2= 0).zx 1x 2e 1e 2e 3e

4z13=210

e

12-114

e

2-1111

e

3-1214

e

421112

Choix du pivot : colonnex1qui correspond au plus nombre negatif (3=2) sur la lignez; et lignee1

qui correspond au plus petit rapport entre les nombres de la colonne des constantes et les nombres de la

colonne pivot qui sont strictement positifs (4=2 est plus petit que 12=2).

Ensuite, technique du pivot de Gauss pour eliminer les nombres dans la colonne du pivot. Les coecients

sont indiques a droite du tableau. On obtient le tableau suivant. La variablex1devient une variable de

base a la place dee1. 1 zx 1x 2e 1e 2e 3e

4z1-7/43/43 Lz+32

:12 :Le1x

11-1/21/22

12 :Le1e

21/21/213 Le2+12

:Le1e

33/21/216 Le3+12

:Le1e

42-118 Le4Le1Choix du pivot : colonnex2qui correspond au plus nombre negatif (7=4) sur la lignez; et lignee4

qui correspond l'un des plus petits rapports entre les nombres de la colonne des constantes et les nombres

de la colonne pivot qui sont strictement positifs. En cas d'egalite, ici par exemple avec la lignee3, on peut

choisir l'une des lignes au choix.

Ensuite, technique du pivot de Gauss pour eliminer les nombres dans la colonne du pivot. Les coecients

sont indiques a droite du tableau. La lignee4est multipliee par 1=2 pour obtenir un coecient 1 dans la

colonnex2. On obtient donc le tableau suivant. On obtient donc le tableau suivant. La variablex2devient

une variable de base a la place dee4.zx 1x 2e 1e 2e 3e

4z1-1/87/810 Lz+74

:12 :Le4x

111/41/44 Lx1+12

:12 :Le4e

23/41-1/42 Le212

:12 :Le4e

35/41-3/40 Le332

:12 :Le4x

21-1/21/24

12 :Le4Choix du pivot : colonnee1qui correspond au plus nombre negatif (1=8) sur la lignez; et lignee3

qui correspond au plus petit rapport (0) entre les nombres de la colonne des constantes et les nombres de

la colonne pivot qui sont strictement positifs.

Ensuite, technique du pivot de Gauss pour eliminer les nombres dans la colonne du pivot. Les coecients

sont indiques a droite du tableau. La variablee1devient une variable de base a la place dee3.zx 1x 2e 1e 2e 3e

4z11/1032/4010 Lz+45

:18 :Le3x

11??4 Lx145

:14 :Le3e

21??2 Le245

:34 :Le3e

15/41-3/40

x

21??4 Lx2+45

:12

:Le3La premier lignezne contient que des nombres positifs.zne peut plus ^etre augmentee, l'algorithme

s'arr^ete. La valeur maximale dezest obtenue poure3=e4= 0, et l'on obtient un maximum de 10. On en deduit egalement les valeurs dex1= 4 etx2= 4. On remarque que les valeurs ? n'avaient pas besoin d'^etre calculees puisquee3ete4sont nuls. b - 2 8 >>>>>:maxz= 2x1+x2

2x1x24

x1+x21 x1+ 2x24

2x1+x212

x 1;x20

Les etapes de l'algorithme du simplexe :zx

1x 2e 1e 2e 3e

4z1-2-10

e

12-114

e

2-1111

e

3-1214

e

421112

zx 1x 2e 1e 2e 3e

4z1-214(z) + (e1)x

11-1/21/221

2 (e1)e

21/21/213(e2) +12

(e1)e

33/21/216(e3) +12

(e1)e

42-118(e4)(e1)zx

1x 2e 1e 2e 3e

4z10112(z) + (e4)x

11??4(x1) +14

(e4)e

2?1?5(e2)14

(e4)e

3?1?6(e3)32

12 (e4)x

21-1/21/241

2 (e4)Le maximum est 12, atteint lorsquee1=e4= 0. On obtient donc les valeursx1= 4 etx2= 4. 3 c - 8 >>>>>:maxz=x1+ 2x2

2x1x24

x1+x21 x1+ 2x24

2x1+x212

x 1;x20

Les etapes de l'algorithme du simplexe :zx

1x 2e 1e 2e 3e

4z11-20

e

12-114

e

2-1111

e

3-1214

e

421112

zx 1x 2e 1e 2e 3e

4z1-122(z) + 2:(e2)e

11115(e1) + (e2)x

2-1111

e

31-212(e3)2:(e2)e

43-1111(e4)(e2)zx

1x 2e 1e 2e 3e

4z1014(z) + (e3)e

11??3(e1)(e3)x

21??3(e2) + (e3)x

11-212

e

4??15(e4)3:(e3)Le maximum est 4, atteint lorsquee2=e3= 0. On obtient donc les valeursx1= 2 etx2= 3.

4quotesdbs_dbs29.pdfusesText_35

[PDF] Introduction aux méthodes numériques

[PDF] Analyse physico-chimique des sols Agricoles

[PDF] Résumé de méthodes quantitatives II 1 Introduction - Etudiant·e·s

[PDF] Plan du cours Méthodologie de la recherche 1 Introduction 11 Les

[PDF] Matière Métiers Sciences et Technologie 1 1er Licence Tronc

[PDF] lecture de plans et métré - ffc-Constructiv

[PDF] Métrologie - ganil

[PDF] LA MÉTROLOGIE

[PDF] fiche semestre - usthb

[PDF] En microbiologie et immunologie - Département de microbiologie

[PDF] Microbiologie industrielle et Biotechnologie - Groupe IMT

[PDF] Notes de cours de micro-économie en 2ème année du DEUG

[PDF] Microéconomie - fsegn

[PDF] LE MIND-MAPPING

[PDF] modems - cours Yves LESCOP