LESTAPESDELALGORITHMEDUSIMPLEXE
Sommaire
1.
Introduction.............................................................................................................................1
2.
Variablesdcartetdexcdent...............................................................................................2
3.
Variablesdebaseetvariableshorsbase................................................................................2
4.
Solutionsadmissibles..............................................................................................................3
5.
Rsolutionduprogrammelinaire(PL)..................................................................................3
6.
Lecritredarrt......................................................................................................................8
1. Introduction
Unprogrammelinaire(PL)missouslaformeparticulireotouteslescontraintes
sont des quations et toutes les variables sont non ngatives est dit sous forme
[Link](PL=).
2. Variables dcart et dexcdent
Avantquelalgorithmedusimplexepuissetreutilispourrsoudreunprogramme
linaire, ce programme linaire doit tre converti en un programme quivalent o
toutes les contraintes technologiques sont des quations et toutes les variables sont
nonngatives.
a. Contraintesdetype( ):Pourchaquecontrainte decetype,onrajouteune
variabledcart ,telque estunevariablepositiveounulle.
Exemple:3
2setransformeen3
2,
b. Contraintesdetype( ):Pourchaquecontrainte decetype,onretranche
unevariabledexcdent ,telque estunevariablepositiveounulle.
Exemple:3
2setransformeen3
2,
Un programme linaire qui contient des contraintes (technologiques) de type est
not(PL).Unprogrammelinairequicontientdescontraintes(technologiques)detype
, , )estnot(PG).Unprogrammelinaire(PL)resp(PG)convertitelquetoutesles
contraintes technologiques sont des quations et toutes les variables sont non
ngativesestnot(PL=)resp(PG=).
3. Variables de base et variables hors base
Considrons un systme dquations variables et quations o
solutiondebasepourcesystmeestobtenuedelamaniresuivante:
. Une
a) Onpose
[Link]
base(V.H.B.).
b) On rsout le systme pour les variables restantes. Ces variables sont
appeleslesvariablesdebase(V.B.)
c) Le vecteur de variables obtenu est appel solution de base (il contient les
variablesdebaseetlesvariableshorsbase)
Une solution de base est admissible si toutes les variables de la solution de base
sont 0.
Ilestvraimentimportantdavoirlemmenombredevariablesquedquations.
Page2sur8
4. Solutions admissibles
Toute solution de base de (PL=) pour laquelle toutes les variables sont non ngatives,
[Link]
unpointextrme.
5. Rsolution du programme linaire (PL)
(PL)
(PL)
Ex:
. . 10
2
1000
1200
5
200
3
60
34
14
,
0
Ex:
. . 10
2
,
1000
5
3
1200
200
60
34
14
, _1, _2, _3, _4 0
6et
2variables
Variableshorsbase
si 1
Variablesdebase:
200
60
34
14
alors
Page3sur8
tapeA:tableauinitial
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
0
E4
zj
Cjzj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
bi
200
60
34
14
0
10
2
1
0
0
1000
5
3
0
1
0
1200
1
0
0
0
0
0
Letableauinitialseconstruitdelamaniresuivante:
Lencadrbleucorrespondauxcoefficientsdescontraintesdu(PL=).
Lencadrvertcorrespondaux :cestdirelescoefficientsdans
Exemplepourlacolonnede
nomme( ):
0
10
Les encadrs roses correspondent aux coefficients ( ) des variables dans la
fonctionobjectif( ).
Lencadrgriscorrespondlavaleurdesvariablesdebase.
Lencadr orange correspond la valeur de , donc la valeur de la fonction
objectifquisecalculedelafaonsuivante:
0
200
60
34
14
tapeB:choixdelavariableentrante(danslabase)
Maximumdes pourdesproblmesdemax.
Minimumdes
pourdesproblmesdemin.
Dansnotreexemple: aleplusgrand donc,ilentredanslabase.
Page4sur8
tapeC:choixdelavariablesortante
DansunproblmedeminOUdemax,lavariablesortanteseraleminimumdes
0
Dansnotreexemple,nousdevonsvaluer:
[Link]
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
0
E4
zj
Cjzj
1000
X1
1200
X2
0
E1
10
2
1
0
0
1000
5
3
0
1
0
1200
1
0
0
0
0
0
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
bi
200
60
34
14
0
200/5=40
60/3=20
14/1=14cestleminimum,donc estlavariablequisortdelabase.
tapeD:pivotage
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
0
E4
zj
Cjzj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
10
2
1
0
0
1000
5
3
0
1
0
1200
1
0
0
0
0
0
bi
200
60
34
14
0
La cellule bleue est nomme le pivot. Pour passer au tableau suivant et donc
effectuerlapremireitration,ilestessentieldutiliserlepivot.
Page5sur8
Lepivotageseffectuedelamaniresuivante:
Oncommencepardiviserlalignedupivotparlechiffredupivot.
Dansnotreexemple,ondivisepar1.
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
0
0
0
0
0
1
0
0
0
0
1000
1
0
1200
0
0
0
bi
14
0
Nouspoursuivonsaveclamatriceidentitpourlesvariablesdebase.Nousinscrivons1
lintersectiondechaquevariableet0ailleurs.
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1000
0
0
0
1
0
1200
1
0
0
0
0
0
bi
14
0
Nousdevonscalculerlesnouvellesvaleurspourlescasesrestantespartirdutableau
prcdent(tableauinitialpourlapremireitration).
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1000
0
0
0
1
0
1200
1
0
0
0
0
0
bi
14
0
Page6sur8
Tableauinitial:
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
0
E4
zj
Cjzj
1000
X1
1200
X2
0
E1
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
bi
200
60
34
14
0
10
2
1
0
0
1000
5
3
0
1
0
1200
1
0
0
0
0
0
Dans notre exemple, le 10 contenu dans lencadr rouge provient de la formule
suivante:
10
donc 10
05
1
10.
Faisonsunautreexempleavecl'encadrvert.Nousobtenons3delafaonsuivante:
0
[Link]
Base
Coef.Z [Link]
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj
1000
X1
1200
X2
31
1
0
E1
0
E2
0
E3
0
E4
0
1
0
0
0
0
0
0
1
0
0
0
5
3
0
1
0
0
10
2
1
0
0
1000
0
0
0
1
0
1200
1
0
0
0
0
0
bi
14
0
Les cases restantes se calculent de la mme faon. Lorsque le tableau est rempli
(commecidessus),ilestpossibledepasserladeuximeitrationquis'effectuedela
mmefaon.
Page7sur8
6. Le critre darrt
Nousarrtonslorsquenousobtenonslecritred'optimalit.L'algorithmedusimplexe
s'arrtelorsque:
0pourunproblmedemax
0pourunproblmedemin
Page8sur8