0 évaluation0% ont trouvé ce document utile (0 vote)
5 vues11 pages
Cours 2 PL
La méthode du simplexe est une procédure algébrique pour résoudre des programmes linéaires avec plus de deux variables, développée par George Dantzig en 1947. Elle consiste à passer d'une solution de base admissible à une autre en améliorant la valeur de la fonction objectif jusqu'à atteindre l'optimum. Le document détaille les étapes de l'algorithme du simplexe, les transformations nécessaires pour formuler un programme linéaire, ainsi que des exemples d'application.
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
0 évaluation0% ont trouvé ce document utile (0 vote)
5 vues11 pages
Cours 2 PL
La méthode du simplexe est une procédure algébrique pour résoudre des programmes linéaires avec plus de deux variables, développée par George Dantzig en 1947. Elle consiste à passer d'une solution de base admissible à une autre en améliorant la valeur de la fonction objectif jusqu'à atteindre l'optimum. Le document détaille les étapes de l'algorithme du simplexe, les transformations nécessaires pour formuler un programme linéaire, ainsi que des exemples d'application.
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
3. La Méthode du Simplexe
3.1. Introduction
On a présenté dans le chapitre précédent une procédure graphique pour résoudre un
programme linéaire 4 deux variables. Par contre, dans la plupart des problémes réels,
ona plus que deux variables a déterminer. Une procédure algébrique pour résoudre les
programmes linéaires avec plus que deux variables fera l’objet de ce chapitre. C'est la
méthode de simplexe.
3.2. Les différentes forme d’un PL
3.2.1. Formulation algébrique
(fonction objective)
n
Minimiser (ou maximiser)z= Gx,
it
ax 2 dy T=
} n
Se ag = By L=ptipt2,..m
Presid
y = 6
at+tat2...
| x, quelconque.
oit les constantes ¢;, a et b, sont des nombres réels.
3.2.2. Forme canonique
a
Minimiser 2= Ex;
JFL
n
Sujeta: = Sax, 2 by
j=l
xy 2 2.
23 n
maximiser 7 = = eX,
i=
Sujet A:
TMs
#
a- Variables d’éeart et d’exeédent
Avant que l’algorithme du simplexe puisse étre utilisé pour résoudre un programme
linéaire, ce programme linéaire doit étre converti en un programme équivalent od
toutes les contraintes sont des équations et toutes les variables sont non négatives.
a. Contraintes de type (<) : Pour chaque contrainte i de ce type, on rajoute une
variable d'écart ¢,, tel que e, est une variable positive ou nulle.
Exemple : 3X, + 2X2 < 2 se transforme en 3x4 + 2x2 + e1 = 2e12 0
b. Contraintes de type (2) : Pour chaque contrainte i de ce type, on retranche
une variable d/exeédent o;, tel que e, est une variable positive ou nulle.
Exemple: 3x, + 2%, 2 2 se transforme en 3X, + 2Xy~ &p = 2,e,2 0
b- Opérations a effectuer pour passer d’une forme a autre
Opération A
En utilisant la relation
minimum f(s) = Maximum [-f()]
dans laquelle f(x) représente la fonction linéaire A optimiser, on peut toujours se
ramener un probléme de minimi
ion (ou de maximisation).
24 Une variable de signe quelconque, x, peut toujours étre remplacée par deux variables
non négatives x, et Xp. Il suffit de poser x = x, + Xp. Ollx, > Oet x, 20.
Opération C
Toute équation de la forme
”_, aijx; = b; peut sre remplacée par les deux
inéquations
yn
aijxj SD, et
Opération D
- Toute inéquation, par exemple Y7, a;jxj = bj peut étre remplacée par les
relations
Dhar ayxy ec =b; ee, 20
- Toute inéquation, par exemple D}_, aijxj 0 appelée variable
d’écart et affectée d'un coefficient nul dans la forme a optimiser.
Exemple
1.
Min (24 — 31)
—2an, +322 <6
a etr2>0
On transforme le probléme en une maximisation en changeant le signe de ta fone-
tion objectif :
Max (—2, +322)
25, 2. Si une variable x: est négative, on la remplace par une variable positive xi’ = -x1. Par
exemple :
max: = 3x, - 2x, - Sx,"
X,) +5, 20etx,<0
3. Si une variable n’a pas de contrainte de signe, on la remplace par deux variables positives
x1’ et xi” telles que xi= x1" - x1’”. Par exemple
max: z= 3x, - 2x, + 8x, max: 2= 3x, - 2x, + 8x,’ = 8x,”
sous:
5x, - 2x, +4x, <8
x, + 3x, + 8x, $25
9x, + 6x,- 3x, 517
4, Si le programme linéaire a une contrainte de supériorité, on la remplace par une contrainte
@infériorité en inversant le signe des constantes. Par exemple:
max: 2= 3x, - max: z= 3x,
sous
5x, - 2x, +4x,<8 =
x, +3x, + 8x, $25
9x, + 6x, -3x,217 x, - 6x, +3
js 5,20 20
Rom,
5, Si le programme linéaire a une contrainte d’égalité, on la remplace par deux contraintes
équivalentes, l'une d’infériorité, Pautre de supériorité, Les variables du programme doivent
satisfaire ces deux contraintes, ce qui revient alors a l’égalité de départ, Par exemple :
26 6. Soit le probléme de programmation linéaire suivant :
Max C = 6x; - 3x) +X > Min -C =-6x, + 3x, - x5
sous les contraintes sous les contraintes:
0.x, <0,
Les variables doivent toutes étre positives ou nulles :
x2 $0 et x3 libre > nous devons poser: x/ = yl, x2 =-p2,x3 =y3-y4,
ot les variables yi, i = /,2,3,4 sont toutes positives ou nulles.
Toutes les contraintes doivent étre du type (2) ie.
4yl - 2y2 + y3 -y4 $65 devient : -4y1 + 2y2 - y3+y42-65
yl -y2 = 10 devient : yl -y2 > 10 et-yl + y2 >-10
La forme canonique de notre probléme est finalement :
Min -C =- 6y, - 3y,
sous les contraintes:
Yaz
+Y¥s ~65
+¥4 5
10
> +10
Le simplexe
Dévloppée en 1947 par George Dantzig, la méthode du simplexe reste d’actualité pour
résoudre des problaémes de grande taille. Il s’agit d’une méthode algébrique basée sur
la résolution de systémes d’équations linéaires ;
L’algorithme du simplexe a été congu pour explorer uniquement ’ensemble des points
extrémes du Domaine de Solutions Admissibles du probléme.. Il passe d’un point
7 extréme A un autre en améliorant la valeur de la fonction-objectif 4 chaque étape
jusqu’a ce que l’optimum soit atteint.
3.3.1, Base et solution de base
Considérons un systéme d’équations an variables et m équations ot n > m. Une
solution de base pour ce systéme est obtenue de la maniére suivante :
max f(z) =c"x.
se.
Ax=b (1)
x20 (2)
Definition 1
D= {x ER" Ax=b,x> 0} est dit ensemble des solutions réalisables,
‘Tout vecteur vérifiant es contraintes (1) et (2) est appelé "solution réalisable” (admissible) du probleme
().
Une solution réatisable x* est dite optimal si maxclx, x € D}.
‘Une solution de base x est dite dégénéré six; >0,j Ja.
Leensemble des points extrémes du poly gone convexe X = {x € R"/Ax =b,x> 0}, estégale aV’ensemble
des solutions de bases réatisables.
28 Théoréme fondamental I
i) Sid une solution admissible alors J une solution de base admissible
ii) Si 3 une solution optimale alors 3 une solution de base optimale
Théoréme fondamental II
Les solutions de base admissibles sont les sommets de l'ensemble admissible
S'il existe une solution optimale, celle-ci est un des sommets de l'ensemble admissible
3.3.2. Principe de algorithme du Simplexe
Aller d’une solution de base admissible 4 une autre solution de base admissible jusqu’a
ce que la solution optimale soit trouvée
3.3.3. Critére d’ optimalité
tant donné que lobjectif s’exprime uniquement en fonction des variables hors-base
de la solution de base réalisable courante, si les coefficients de ces variables dans
Pobjectif sont tous négatifs ou nuls, alors la solution de base réalisable courante est
optimale.
3.3.4, Tableau de simplexe initial
Toutes les variables
A= (ai); by
Matrice des coefficients vecteur des
4 4 valeurs du
jes contraintes du programme seconds
standard membre
g coefficient de la fonction objectif
correspond aux variables
29 3.3.5. Algorithme du simplexe :
1. Obtenir une solution de base réalisable.
2, Verifier le critére d’optimalité: si les cofits réduits de toutes les variables
hors-base sont négatifs ou nuls, stop.
Sinon
2. Choisir la variable xj, celle qui a le coat réduit le plus élevé.
4, Déterminer la variable de sortie:
nin { = a >0}
aj
5. Effectuer un pivot et déterminer une nouvelle solution de base réalisable.
Retour a I’étape 2.
3.3.6. Diagramme de l’algorithme :
‘Tableau initial
‘Choix de la variable entrante
Choix de la variable sortante
30 Résoudre le PL suivant a l’aide de la méthode du simplexe :
Max 10x, +200x,
se. mtx) S150 (1)
4x,+2x, $440 (2)
x +4x, $480 (3)
x <90 (4)
x, 20,x, 20
Sous forme standard :
Max 100x, + 200x,
xtx+ ey = 150
4x, t2x, + & 440
SC{ x +4x%, +03 24
x +e, = 24
X41 Xz 1 Cn, 03,04 20
Premier tableau :
Variables hors base Variables de base
Vv Vv
% x & e es es i
1 1 1 0 0 0 150
4 2 0 1 0 0 440
1 4 0 0 1 0 480
1 0 0 0 0 1 90
Zz 100 _|200 _‘|o [o 0 0 0
Solution de base initiale (x, x2,¢;,€2,¢3,¢4) = (0,0,150,440,480,90)
Itération 1:
* Max Ci; = Max{100,200} = 200
Donc la variable entant dans la base est la variable x, (colonne pivot)
31 x ey &2 &3 es bi
Lt 1 1 0 0 0 150
12 4 0 1 0 0 440
L3 1 0 0 1 0 480
4 1 0 0 0 1 90
Z 100 0 [o 0 0 0
“ming = (22 } = (150,220,120) = 120
Donc la ligne pivot est la 3¢ ligne et élément pivot est le 4.
Alors la variable sortante est la variable e;
x1 e e es es bi
L1-1/4.13 [4 1 0 0 0 150
12-1/213 [4 0 1 0 0 440
%13
14
Z(L5-50.L3) | 100 o |o 0 0 0
x1 & e
i 3/4 [0 —— 0 1/4 [0
12 7/2 [0 0 1 1/2 [0
13 1/4 Dio 0 % 0
4 1 [0 0 0 0
Z 50 [0 0 0 -50 0
Les variables de base sont (x2,e1,€2,€4)
Solution de base en cours ( x;, X2,¢1,€2,€3,€4) = (0,120,30,200,0,90)
Itération 2:
* Max Cyj = max{50} = 50
Donc la variable entant dans la base est la variable x, (colonne pivot)
% x2 e e es es bi
L1 3/4 0 1 0 1 0 30
12 7/72__|0 0 1 1/72_[0 200
L3 1/4 1 0 0 a 0 120
L4 1 0 0 0 0 1 90
Zz 50 0 0 0 -50 0 -24000
32 smnin 2 = (2%, 208 220 go) =
Bap ay Ge 772’ 4/4" 90} {40,57,480,90} = 40
Donc la ligne pivot est la 1°* ligne et I’élément pivot est 3/4.
Alors la variable sortante est la variable e,
| % @ | @& | bi
4/311 [34 [oe 1 [0 1 [0 30
12-(7.2/3)1L1_ [7/2 [0 1 1/2 [0 200
L3-1/3.L1 1/4 1 0 Vs 0 120
L4-4/3L1 1 0 0 0 1 90
Z(L5- 50 0 0 -50 0 -24000
50.4/3.L1)
ae és |e by
4/311 1 0 1/3 0 40
L2-(7.2/3).L1_ | 0 0 2/3 |0
1L3-1/3.L1 0 1 1/3 |0
14-4/3L1 0 0 1/34
Z(L
50.4/3.L1)
Stop
La solution optimale est :
xj =40 , etx}=110 etZ* = 26000
Interprétation géométrique
- Une solution de base réalisable correspond a un point extreme du domaine
réalisable.
- Un pivot correspond a un déplacement d’un point extréme a un autre qui lui est
adjacente, i.e. toutes les variables hors-base sauf une sont les mémes.
La méthode du simplexe peut se résumer comme suit.
1. Nous débutons avec une solution de base réalisable initiale (un point extréme).
2. A chaque itération, nous effectuons un pivot, passant ainsi a une solution de base
réalisable adjacente (un point extréme adjacent).
3. L’algorithme s’arréte lorsqu’il identifie une solution de base réalisable optimale (un
point extréme correspondant & une solution optimale).
33