View
4
Download
0
Category
Preview:
Citation preview
1
Chapitre 5 : Programmation Linéaire(Méthode du Simplexe)
2
Programmation Linéaire (Méthode du Simplexe)
Algorithme du simplexe Objectifs de la leçon :
-Comprendre la notion de base et solution de base.
-Savoir résoudre un problème de programmation linéaire à l’aide de la méthode du simplexe.
Dans cette leçon :
1- Introduction.
2- Problème canonique et solution de base.
3- Formule d’accroissement de la fonction objective.
4- Critère d’optimalité.
5- Itération de l’algorithme du simplexe.
6- Organigramme de l’algorithme du simplexe.
7- Tableau du simplexe.
3
Programmation Linéaire (Méthode du Simplexe)
1.Introduction Soit le problème canonique de programmation linéaire suivant :
max2211 →+++ nnxcxcxc (1)
=+++++
=+++++
=+++++=+++++
mnmnjmjmm
ininjijii
nnjj
nnjj
bxaxaxaxa
bxaxaxaxa
bxaxaxaxabxaxaxaxa
2211
2211
222222121
111212111
(2)
0,,0,0 21 ≥≥≥ nxxx (3) Ici on suppose nmrangAbbb m ≤=≥ ,0,,, 21 . Le problème (1)-(3) peut être écrit sous sa forme matricielle :
≥
=
→
;0
,
,max'
x
bAx
xc
(4)
4
Programmation Linéaire (Méthode du Simplexe)
où A=A(I,J) -est la matrice des conditions, ( )jIAaj ,= -les colonnes de A,( ) ( )JcJc t=' -le vecteur des coûts, b= b(I) -le vecteur des contraintes,
( ) ( )JjxJxx j ∈== , -le vecteur des paramètres, { } { }nJmI ,,2,1,,,2,1 == -les ensembles d’indices des lignes et des colonnes de la matrice A.
On sait que le nombre de points extrêmes d’un tel problème peut atteindre Cmn .
La méthode du simplexe est une méthode itérative. Elle démarre d’un point extrême ( sommet de départ ) et passe au sommet voisin , et ceci constitue une itération de l’algorithme du simplexe. Pour cela , on doit définir le point extrême de départ et le test d’arrêt. 2- Problème canonique et solution de base Définition 1 Tout vecteur x vérifiant les contraintes (2) et (3) est appelé solution réalisable (admissible ) du problème (1)-(3).
5
Programmation Linéaire (Méthode du Simplexe) Définition 2 Une solution réalisable 0x est optimale si )'max(' 0 xcxc = , pour toute solution réalisable x. Définition 3 Une solution réalisable x est dite de base si (n-m) de ses composantes sont nulles, et aux autres jmjj xxx ,,, 21 , correspondent m vecteurs jmjj aaa ,,, 21 de la matrice de condition A linéairement indépendants . L’ensemble JB={ }mjjj ,,, 21 est appelé ensemble des indices de base ; JH=J\JB ensemble des indices hors base. Autrement Une solution réalisable ( )Jxx= est solution de base si ( ) 0== HH Jxx ,
oùAB ,0det ≠ AB=A(I,JB) La matrice AB est appelée matrice de base , Bj Jjx ∈, -les composantes de base ;
Hj Jjx ∈, - les composantes hors base. Définition 4 Une solution de base x est dite non-dégénérée si jx >0, j∈JB.
6
Programmation Linéaire (Méthode du Simplexe)
Exemple 1 Soit le système :
=+−=+−+.972732
431
4321xxx
xxxx
La solution basique liée à la base AB=A (I,JB) =(a3,a4 )=
−−
1713 , avec JB={ 3, 4},
est de la forme : x=(0,0,x3 ,x4) et ⇒≠= 04det BA le système bxA BB = admet une solution unique de base qui sera :
( )211,2
1,0,0 −=x .
3-Formule d’accroissement de la fonction objective
Soit ( )nxxxx ,....,, 21= une solution réalisable de base avec la matrice de base ( ) BHBB JJJJIAA /,, == .
7
Programmation Linéaire (Méthode du Simplexe) Effectuons la partition suivante :
[ ] ( )
===
H
BHHHB x
xxJIAAAAA ,,, , ( ) ( )HHBBH
BHHBB JccJcccccJxxJxx ==
=== ,,),(),(
.
Considérons une autre solution réalisable quelconque xxx ∆+= .
L’accroissement de la fonction objective Z est donc égale à :
( ) ( ) xcxcxcxZxZZ ∆=−=−=∆ ''' . (5)
Comme x et x sont réalisables alors :
( ) 0=∆=−⇒== xAxxAbAxxA .
Comme
∆∆=∆
H
B
xxx , d’où 0=∆+∆=∆ HHBB xAxAxA ⇒ HHBB xAAx ∆−=∆ −1 et en
vertu de la relation (5) on obtient :
( ) HHHHBBHHBB xcxAAcxcxcZ ∆+∆−=∆+∆=∆ − '''' 1
⇒ ( ) HHHBB xcAAcZ ∆−−=∆ − '' 1 .
Construisons le m-vecteur y = y( I ) dit des potentiels : 1'' −= BB Acy ; (6)
et le vecteur ∆= ∆(J) = (∆j , j∈J ), dit des estimations :
∈−=∆−=∆
.,''''
JjcaycAy
jjj (7)
8
Programmation Linéaire (Méthode du Simplexe) Remarque 1
( ) 0'' =∆=∆ BB J par construction.
En utilisant (6) et (7), l’accroissement de la fonctionnelle prend la forme suivante :
jJj
jHH xxZH
∆∆−=∆∆−=∆ ∑∈
' (8)
Comme jx j ∀≥ ,0 et Hj Jjx ∈∀= ,0 , donc .,0 Hjjjj Jjxxxx ∈≥∆=∆+= En utilisant cette dernière inégalité et la relation (8) on déduit le critère d’optimalité.
4-Critère d’optimalité Théorème 1
Soit { }BAx, une solution réalisable de base de départ, l’inégalité vectorielle ( ) 0≥∆=∆ HH J est suffisante pour l’optimalité de la solution de base x . Elle est
aussi nécessaire lorsque x est non dégénérée.
9
Programmation Linéaire (Méthode du Simplexe) Preuve : -Condition suffisante :
Soit x une solution de base, telle que ( ) 0≥∆=∆ HH J , et considérons une autre
solution réalisable quelconque xxx ∆+= .
Comme xxx ∆+= ≥ 0 , donc 0≥∆+= HHH xxx et x est de base, c’est à dire,
0=Hx donc ( ) 0≥∆ HJx et en utilisant l’hypothèse ( ) 0≥∆ HH J on obtient l’inégalité suivante :
0''' ≤∆∆−=−=∆ HH xxcxcZ
⇒ xxcxc ∀≤ ,'' solution réalisable, et ceci montre que x est une solution optimale du problème. -Condition nécessaire :
Faisons la preuve par absurde.
Soit { }BAx, une solution optimale non dégénérée, et supposons que l’inégalité 0≥∆H n’est pas vérifié, c’est à dire, ,0 HJj ∈∃ tel que 0j∆ <0.
Construisons la solution réalisable xxx ∆+= , où x∆ est l’accroissement de x.
Pour cela posons :
=∈=∆
,,,/,0
0
0jjjJjx H
j θ
10
Programmation Linéaire (Méthode du Simplexe) avec θ ≥ 0, et de l’admissibilité de x ( )bxA = , on calcule :
( ) HHBBB xAAJxx ∆−=∆=∆ −1''
= 01
jB aA−−θ .
Vérifions l’admissibilité de x par rapport à la contrainte directe ( )0≥x :
HHH xxx ∆+= ,ici 0≥Hx car 0≥θ et 0=∆ Hx partout sauf pour 0jj= .
01
jBBB aAxx −−= θ , ici on sait que Bx >0( x non dégénérée).
Donc pour θ suffisamment petit 0≥Bx .De là x est une solution réalisable.
En utilisant l’accroissement de la fonctionnelle, on obtient :
( ) ( ) 0' jxcxZxZ ∆−=∆=− θ >0, ce qui implique xc' > xc' et ceci contredit l’optimalité de x .
Remarque 2
Si les composantes du vecteur 01
jB aA− sont non positives, alors le problème de départ possède une solution infinie.
En effet, en construisant x admissible, il faut avoir 01
jBBB aAxx −−= θ .
Comme Bx >0 et si 00
1 ≤−jB aA , alors Bx est positif ou nul pour toute valeur de
θ, ce qui implique que x est une solution admissible .
De là en tendant vers l’infini θ , on obtient : ( ) ∞→∆−=∆+= 0''' jxcxcxcxZ θ
11
Programmation Linéaire (Méthode du Simplexe)
5-Itération de l’algorithme du simplexe :
Soit { }BAx, une solution réalisable de base de départ et supposons que le critère d’optimalité n’est pas vérifié, c’est à dire l’inégalité ∆j ≥ 0 , j∈JH , n’est pas vérifiée .
Choisissons l’indice jJjjH
jJj ∆=∆∈
∈∆ ,00 min/ 0
.
Le but de l’itération est de faire rentrer cet indice j0 dans la base (autrement dit la colonne aj0 va rentrer dans la base).
Donc il faut trouver un indice j1∈JB, qui sortira de la base (à cet indice correspond la colonne Bj Aa ∈1 ).Et ceci constitue l’itération, qui procède au
passage de la solution de base ( point extrême ){ }BAx, à la solution { }BAx, (sommet voisin ) et tel que ( ) ( )xZxZ ≥ . La nouvelle solution de base x sera trouvé de la manière suivante :
12
Programmation Linéaire (Méthode du Simplexe)
θ+=xx ,où est la direction du changement et θ le pas le long de cette direction.
Construisons la direction de la manière suivante : Sur JH , posons :
=∈=
.0
0,1
,\,0jj
jJj Hj
Sur JB :
x doit être réalisable, donc elle doit vérifier bxA = et comme bAx= donc 0=Aθ , c’est à dire 0=A .
De cette dernière relation on obtient :
( ) HHBBB AAJ
1−−== .
De là 0≥=+= HHHH xx θθ et BBB xx θ+= ⇒ 01
jBjj aAxx −−= θ .
Si les composantes du vecteur 001 ≤−
jB aA , alors ,0,0 ≥∀≥ θjx donc on peut prendre θ = ∞ et on aura une solution infinie.
13
Programmation Linéaire (Méthode du Simplexe)
Si parmi les composantes du vecteur 01
jB aA− , ils existent celles qui sont
négatives, donc en augmentant θ certaines composantes de Bx seront négatives.
Pour avoir 0≥Bx , il faut prendre un pas maximal 0θ :
jJj B
θθ∈
=min0 = 10
0
,0/min jBjjjj
j Jjxxx θ=
∈ , jjB xoùJj0
,1∈ est la jème composante
de 01
jB aA− .
La nouvelle base sera :
( )1\ jJJ BB = 0j∪ et ( )j1a\BB AA = 0ja∪ .
14
Soit { }BAx, une solution réalisable.
Calculer 1'' −= BB Acy et Hjjj Jjcay ∈−=∆ ,' .
Stop, Le maximum de la fonction objective tend vers l’infini.
Hj Jj∈≥∆ ,0
0/ 00 jHJj ∆∈∃
et 001 ≤−
jB aA .
Stop, x est une solution optimale.
Déterminer HJj
jjj∈∆=∆ min/ 00 , et
10
1 / jj θθ = =
∈ Bjjjj
j Jjxxx ,0/min 0
0
.
Calculer ( ) ( ) ( )( )HB JxJxJxx ,== / ( ) ( ) 0
1jBBB aAJxJx −−= θ ,
0=jx , 0j\HJj∈ , 00 θ=jx .
Poser ( )1j\BB JJ = 0j∪ , ( )0j\HH JJ = 1j∪ , ( )BB JIAA ,= ,
d’où { }BAx, la nouvelle solution réalisable de base.
Oui
Non
Oui
Non
15
Programmation Linéaire (Méthode du Simplexe) 7-Tableau du simplexe :
Les différents calculs qu’on aura à effectuer dans les différentes étapes de résolution seront disposés dans le tableau suivant
c 1c 2c 3c …… mc 1+mc …..
jc …... nc
Bc Base b 1a 2a 3a …… ma 1+ma ….. ja …... na θj
1c 1a 11 xb = 1 0 0 …… 0 1,1 +mx …..
jx1 ….. nx1 θ1
2c 2a 22 xb = 0 1 0 …… 0 1,2 +mx …..
jx2 ….. nx2 θ2
3c 3a 33 xb = 0 0 1 …… 0 1,3 +mx …..
jx3 ….. nx3 θ3
mc ma mm xb =
0 0 0 …… 1 1, +mmx …..
mjx
….. mnx θm
BB xcZ '= ∆j ∆1=0 ∆2=0 ∆3=0 …… ∆m=0 ∆m+1 ….. ∆j ….. ∆m
16
Programmation Linéaire (Méthode du Simplexe)
Remarque 3 : Les m-vecteurs de la base ne sont pas forcement les premiers.
Exemple 2 : Nous allons résoudre le problème de programmation linéaire suivant, par la
méthode du simplexe :
=≥=+−=++−
=++→+=
.5,1,0632532
4max,2
521
421
321
21
jxxxxxxx
xxxxxZ
j
On a { }5,4,3,2,1=J et { }5,4,3=BJ , { }2,1=HJ avec 3IAB= , donc la solution réalisable de base est ( )6,5,4,0,0=x ,dressons alors le premier tableau du simplexe :
17
Programmation Linéaire (Méthode du Simplexe)
c 2 1 0 0 0
Bc Base b 1a 2a 3a 4a 5a θj
0 3a 4 1 1 1 0 0 4 L 11
0 4a 5 -2 3 0 1 0 / L 12
0 5a 6 2 -3 0 0 1 3 L 13→vecteur
sortant
Z=0 ∆j -2 -1 0 0 0
↑vecteur rentrant
On remarque que la relation Hj Jj∈∀≥∆ ,0 , n’est pas vérifiée , donc la solution réalisable de base initiale n’est pas optimale, on doit alors changer la base de la manière suivante :
18
Programmation Linéaire (Méthode du Simplexe)
,2min 1 −=∆=∆∈ jJj H
donc 10=j , de là le vecteur 1a va rentrer dans la nouvelle
base, et calculons jJj Bθθ
∈=min0 :
326,41
453 ==== θθ , d’où ,3min 5
01
====∈
θθθθ jJjj Bde là, le vecteur a5 va sortir de
la base, et la nouvelle base est { } { }2,5,1,4,3 == HB JJ , Pour déterminer la nouvelle solution x , dressons le 2ème tableau du simplexe :
19
Programmation Linéaire (Méthode du Simplexe) c 2 1 0 0 0
Bc Base b a1 a2 a3 a4 a5 θj
0 a3 1 0 2
5 1 0 2
1− 5
2 →L 21 = L 1
1 21− L 1
3
0 a4 11 0 0 0 1 1 / L 22 = L 1
2 + L 13
2 a1 3 1 2
3− 0 0 2
1 / L 23 = 2
1 L 13
6=Z ∆ j 0 -4 0 0 1
↑
La nouvelle solution de base est donc ( )0,11,1,0,3=x de plus elle n’est pas
optimale, car 042 −=∆ .
On doit alors changer la base une autre fois :
,4min 2 −=∆=∆∈
jJj H
donc le vecteur 2a va rentrer dans la base.
Comme 3min1 θθθ ==∈
jJjj
B, donc le vecteur a3 sortira de la base.
D’où, on obtient : { } { }3,5,1,4,2 == HB JJ , pour déterminer la nouvelle solution x , dressons le 3ème tableau du simplexe :
20
Programmation Linéaire (Méthode du Simplexe)
c 2 1 0 0 0
Bc Base b a1 a2 a3 a4 a5 jθ
1 2a 5
2 0 1 5
2 0 51−
→L 31 =
52
L 21
0 4a 11 0 0 0 1 1 L 32 = L 2
2
2 1a
518 1 0
53 0
51 L 3
3 = L 23 + 5
3 L 21
Z = 538 ∆ j
0 0 58 0
51
La nouvelle solution de base est donc x = ( )0,11,0,52,5
18 , comme ∆ j ≥ 0,
∀j∈ J H , l’algorithme s’arrête et la solution obtenue est optimale, avec Z = 538
Remarque 4 :
L 32 par exemple, désigne la 2ème ligne du 3ème tableau.
21
Chapitre 5 : Programmation Linéaire(Problème de Transport)
22
Programmation Linéaire(Problème de Transport)
Problèmes de transport Il s’agit de déterminer la façon optimale d’acheminer des biens à partir de m entrepôts et de les transporter vers n destinations et cela à moindre coût. Nous allons faire l’hypothèse que toute la marchandise de tous les entrepôts doit être acheminer vers les différentes destinations. Nous allons illustrer ce problème à partir de l’exemple suivant.
23
Programmation Linéaire(Problème de Transport)
24
Programmation Linéaire(Problème de Transport)
25
Programmation Linéaire(Problème de Transport)
26
Programmation Linéaire(Problème de Transport)
27
Programmation Linéaire(Problème de Transport)
28
Programmation Linéaire(Problème de Transport)
29
Programmation Linéaire(Problème de Transport)
30
Programmation Linéaire(Problème de Transport)
31
Programmation Linéaire(Problème de Transport)
32
Programmation Linéaire(Problème de Transport)
33
Programmation Linéaire(Problème de Transport)
34
Bibliographie
1) Cours Théorie des graphes ,Mme Djoudi Naïma . 2) La recherche opérationnelle et l'optimisation combinatoire:présentation,méthodes
secteurs d’application,Marie-Christine Costa ENSTA-CEDRIC-Paris avec la participation de Jean-Charles Billaut Polytech-Tours.
3) Recherche Opérationnelle:Programmation Linéaire.M.AIDENE,et B.OUKACHA. 4) Les Graphes par L’exemple, F.DROESBEKE, M.HALLIN, CL.LEFEVRE. 5) Précis de recherche opérationnelle.Nicole-Sylvie GUILLOT-LE GARFF,et Manuel BLOCH.
Recommended