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

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

Previous PDF

Next PDF

Chapitre 3

Méthode du simplexe

Comme toujours, on suppose queAune matrice de formatmnetb2Rm. On notera les colonnes deApar[a1;a2;:::;an]. Aussi, on fera l"hypothèse que le rang de la matriceAest

égal à m.

Selon le chapitre précédent, nous savons que la solution optimale du problème d"optimisation

linéairemaxz=ctx; Ax=b; x0:(3.1) se trouve en un sommet de l"ensemble convexe des solutions admissiblesK=fx0jAx= bg. De plus, nous savons que les sommets sont étroitement reliés aux solutions de base admis- sibles. Concrètement, cela signifie que si on choisit une liste de m variables dites de base B=fxj1;xj2;:::;xjmgassociées à des colonnesfaj1;aj2;:::;ajmgqui forment une base de l"espace-colonne, on peut calculer l"unique solution de bases du système Ax B=b en imposant que les variables hors-basexi= 0pour tous lesi6=j1;j2;:::;jm. SixB0, la

solution est admissible et sera appellée solution de base admissible ou réalisable. D"après le

chapitre précédent, la solution de basexBcorrespond à un sommet deK. Par conséquent, il suffit de calculer tous les sommets deKpour trouver la solution optimale.

Mais le nombre de sommets est de l"ordre

n!m!(nm)!ce qui est beaucoup trop pour desnetm relativement grands. Le principe de la méthode du simplexe est d"éviter de calculer tous les sommets. A partir d"un sommet donné, la méthode calculera une suite de sommets adjacents l"un par rapport au précédent et qui améliore la fonction objective.

3.1 Solutions de base adjacentes

Définition

3.1.1 Deux sommetsxetysont dits adjacents si les variables de base ne

diffèrent que d"un seul élément. 1

2CHAPITRE 3. MÉTHODE DU SIMPLEXE

Reprenons le problème modèle du premier chapitre écrit sous la forme canonique maxz= 5x1+ 4x2 x

1+x3= 6

x

1=4 +x2+x4= 6

3x1+ 2x2+x5= 22

x

1;x2;x3;x4;x50

Le sommetx= (4;5;2;0;0)correspond aux variables de basefx1;x2;x3g. De même, le sommety= (6;2;0;2:5;0)est associé aux variables de basefx1;x2;x4g. Les deux sommets sont adjacents ce qui est conforme au graphique de l"ensembleKprojeté dansR2.

Le système s"écrit

2 6

641 0 1 0 0

1=4 1 0 1 0

3 2 0 0 13

7 752
6 6664x
1 x 2 x 3 x 4 x 53
7

7775=2

6 646
6 223
7 75
Pour calculer la solution de base(4;5;2;0;0), il suffit d"extraire les 3 colonnes de la matriceA

et de résoudre le système carré par la méthode d"élimination de Gauss. Toutefois, lorsque que

l"on voudra calculer la nouvelle solution de base(6;2;0;2:5;0), il faudra recommencer l"éli- mination de Gauss avec les nouvelles colonnes de base. Il est plus avantageux de poursuivre élimination de Gauss à partir du premier calcul.

Voici un exemple de calcul.

a)

En premier, on forme la matrice augmen tée

2 6

641 0 1 0 0 6

1=4 1 0 1 0 6

3 2 0 0 1 223

7 75
b) On applique l"élimination de Gauss-Jordan p ourles v ariablesde base fx1;x2;x3g. 2 6

641 0 04=5 2=5 4

0 1 0 6=51=10 5

0 0 1 4=52=5 23

7 75
Donc x

1= 4 + 4=5x42=5x5

x

2= 56=5x4+ 1=10x5

x

3= 24=5x4+ 2=5x5

En posant les variables hors-basesx4=x5= 0, on obtient bien la solution de base x= (4;5;2;0;0).

3.2. MÉTHODE DU SIMPLEXE : PHASE II3

c) Main tenant,on désire calculer la solution de base adjacen tel iéesaux v ariablesd ebase fx1;x2;x4g. Pour cela, on poursuit l"élimination de Gauss-Jordan à partir du pivot a 3;42 6

641 0 1 0 0 6

0 13=2 0 1=2 2

0 0 5=4 11=2 5=23

7 75:
Donc x

1= 6x3

x

2= 2 + 3=2x31=2x5

x

4= 5=25=4x3+ 1=2x5

En posant les variables hors-basesx3=x5= 0, on obtient bien la solution de base y= (6;2;0;2:5;0). d) P oursuivonsà u nautre sommet adjacen tz= (6;0;0;4:5;4)dont les variables de base sontfx1;x4;x5g. Ce sommet est adjacent àymais pas àx. Poursuivons l"élimination de Gauss-Jordan à partir du pivota2;5 2 6

641 0 1 0 0 6

0 23 0 1 4

0 11=4 1 0 9=23

7 75:

On obtient les relations

x

1= 6x3

x

5= 42x2+ 3x3

x

4= 9=2x2+ 1=4x3

En posant les variables hors-basesx2=x3= 0, on obtient bien la solution de base z= (6;0;0;4:5;4). L"opération décrite ci-dessus est aussi connue sous le nom de pivotement. Cette stratégie sera à la base de la méthode du simplexe.

3.2 Méthode du simplexe : Phase II

Dans cette section, nous allons présenter la Phase II de la méthode du simplexe. La Phase

I qui sert plus à initialiser la Phase II, sera aborder plus tard. Cette phase s"applique à des

problèmes du type maxz=ptx; Cxb; x0:ouminz=ptx; Cxb; x0:(3.2)

4CHAPITRE 3. MÉTHODE DU SIMPLEXE

oùCest une matrice de formatmn. On fera l"hypothèse queb0. Cette supposition est cruciale pour la Phase II. Ceci garantie que02K=fx0jCxbg. De plus, nous savons que le point0est un sommet. Ce point servira de point de départ de l"algorithme du simplexe. En gros, l"algorithme va pivoter autour de ce point pour trouver un meilleur sommet. On poursuit l"algorithme jusqu"à l"obtention de la solution optimale.

La méthode débute avec la forme canonique du problème (3.2) que l"on écrira sous la forme

maxz=ctx; Ax=b; x0:(3.3) Attention, nous avons inclus les variables d"écart dans la liste des variables, i.e.x2Rm+n.

La matriceAetcsont données par

A= [C I]c=p

0

L"idée de base de la méthode du simplexe consiste à appliquer l"élimination de Gauss-Jordan

à partir du système augmenté obtenu en ajoutant au systèmeAx=bla relation linéaire z=ctxAx=b; c txz= 0 Ce système peut s"écrire sous la forme matriciellequotesdbs_dbs2.pdfusesText_3

[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