Rappel sur la programmation linéaire
Méthode du simplexe
On a un programme sous forme standard
On a une base réalisable
On a une forme canonique par rapport à la base réalisable
19:02 19
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Méthode du simplexe
On a une base J 1, , m
m
x1
Max z c j x j 0 0 cm 1
Forme
cn Standard
j 1 x
n
1 0 a1,m 1 a1,n x1 b1 Forme
canonique
par rapport à
am , n xn bm
la base J.
0 1 a
m , m 1
x1 xn 0 0
La base J 1, , m est réalisable bi 0; i 1, , m
19:02 20
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Méthode du simplexe
Tableau du simplexe
x1 … xr … xm xm+1 … xk … xn
0 … 0 … 0 cm+1 … ck … cn -z0
x1 1 … 0 … 0 a1,m+1 … a1,k … a1,n b1
xr 0 … 1 … 0 ar,m+1 … ar,k … ar,n br
xm 0 … 0 … 1 am,m+1 … am,k … am,n bm
Forme canonique par rapport à la base J 1, , m
Variables de base x1 , , xm x j , j J
19:02 21
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Méthode du
Commencer par une solution
simplexe
de base réalisable
Trouver la colonne k telle que
ck Max c j
ck 0? aik 0?
Non Oui Non
La solution est Oui
Le problème n’est
optimale pas borné.
Stop Trouver la ligne r telle que
br bi Stop
Min
ark aik 0 a
ik
Trouver la forme canonique par rapport à la nouvelle
base en utilisant comme élément pivot: ark
19:02 22
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Méthode du simplexe
Calcul du nouveaux tableau
La variable qui se trouve à la ligne r sort de la base
La variable xk rentre dans la base
ar, j br
La ligne pivot ar, j j 1,, n
br
ark ark
ar, j br
La fonction
cj c j ck j 1,, n
z0 z0 ck
objectif ark ark
b ar, j
Les autres bi bi r ai,k ai, j ai, j ai,k i 1,, m
éléments ark i 1,, m ark j 1,, n
19:02 23
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Méthode du simplexe ar, j
Calcul du nouveaux tableau (suite) ai, j ai, j ai,k i 1,, m
ark j 1,, n
ar ,m 1 x
i=1 a1, m 1 a1,m 1 a1,k -
j = m+1 ark
x1 … xr … xm xm+1 … xk … xn
0 … 0 … 0 cm+1 … ck … cn -z0
x1 1 … 0 … 0 a1,m+1 … a1,k … a1,n b1
xr 0 … 1 … 0 ar,m+1 … ar,k … ar,n br
xm 0 … 0 … 1 am,m+1 … am,k … am,n bm
19:02 24
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Méthode du simplexe
br
Calcul du nouveaux tableau (suite) bi bi a i 1,, m
ark i,k
br x
i= 1 b1 b1
ark
a1,k -
x1 … xr … xm xm+1 … xk … xn
0 … 0 … 0 cm+1 … ck … cn -z0
x1 1 … 0 … 0 a1,m+1 … a1,k … a1,n b1
xr 0 … 1 … 0 ar,m+1 … ar,k … ar,n br
xm 0 … 0 … 1 am,m+1 … am,k … am,n bm
19:02 25
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Max z x1 2x2 x3
2x1 x2 x3 2
Forme
2x1 x2 5x3 6
canonique
4x1 x2 x3 6
x1, x2, x3 0
Max z x1 2x2 x3
2x1 x2 x3 x4 2 Forme standard
2x1 x2 5x3 x5 6
Forme canonique par
4x1 x2 x3 x6 6 rapport à J={4,5,6}
x1, x2, x3, x4, x5, x6 0
19:02 26
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
x1 x2 x3 x4 x5 x6
1 2 1 0 0 0 0
x4 2 1 -1 1 0 0 2 2/1
x5 2 -1 5 0 1 0 6
x6 4 1 1 0 0 1 6 6/1
19:02 27
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
x1 x2 x3 x4 x5 x6
-3 0 3 -2 0 0 -4
x2 2 1 -1 1 0 0 2
x5 4 0 4 1 1 0 8 8/4
x6 2 0 2 -1 0 1 4 4/2
19:02 28
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
x1 x2 x3 x4 x5 x6
-6 0 0 -11/4 -3/4 0 -10
x2 2 1 0 5/4 1/4 0 4
x3 4 0 1 1/4 1/4 0 2
x6 2 0 0 -3/2 -1/2 1 0
x1 = 0 x2 = 4 x3 = 2 z = 10
19:02 29
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Outils Geogebra
19:02 30
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Geogebra
19:02 31
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Outils LPSolve
19:02 32
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
19:02 33
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Si la solution de base initiale n'est pas réalisable
C'est-à-dire un des bi est négatif
On utilise la méthode duale du simplexe pour
retrouver une solution de base réalisable
19:02 34
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Commencer par une solution Méthode duale
de base duale réalisable: du simplexe
i / bi 0 j , c j 0
Trouver la ligne r telle que
br Min bi
br 0? arj 0?
Non Oui Non
La solution est Oui
Le problème n’a
optimale pas de solution.
Stop Trouver la colonne k telle que
ck cj Stop
Min
a rk a rj 0 a
rj
Trouver la forme canonique par rapport à la nouvelle
base en utilisant comme élément pivot: ark
19:02 35
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Max z x1 x2 Max z x1 x2
Forme
3 x1 x2 4 3x1 x2 4 canonique
x1 4 x2 5 x1 4 x2 5
x1 , x2 0 x1 , x2 0
Max z x1 x2
Forme standard
3 x1 x2 x3 4
x1 4 x2 x4 5 Forme canonique par
x1 , x2 , x3 , x4 0 rapport à J={3,4}
19:02 36
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
x1 x2 x3 x4
-1 -1 0 0 0
x3 -3 -1 1 0 -4
x4 -1 -4 0 1 -5 ←
1 1/4
↑
19:02 37
© Y. Ouinten, Université de Laghouat, 2009 – 2018
z
xc1j243 arj
x1 x2 x3 x4
-3/4 0 0 -1/4 5/4
x3 -11/4 0 1 -1/4 -11/4 ←
x2 1/4 1 0 -1/4 5/4
3/11 1
↑
19:02 38
© Y. Ouinten, Université de Laghouat, 2009 – 2018
x1 x2 x3 x4
0 0 -3/11 -2/11 2
x1 1 0 -4/11 1/11 1
x2 0 1 1/11 -3/11 1
19:02 39
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Remarques
Dans de très nombreux problèmes d'optimisation, quelques
variables ou toutes les variables de décision ne peuvent
prendre que des valeurs entières non négatives
Si toutes les variables de décision sont contraintes à
prendre des valeurs entières on dit que l’on a
un programme mathématique, en nombres entiers, pur
19:02 40
© Y. Ouinten, Université de Laghouat, 2009 – 2018
Rappel sur la programmation linéaire
Remarques
Si quelques variables seulement sont contraintes à prendre
des valeurs entières on dit que l’on a
un programme mathématique, en nombres entiers, mixte.
Si la fonction objectif et les contraintes sont linéaires on dit
que l’on a
un problème de programme linéaire en nombre entier.
19:02 41
© Y. Ouinten, Université de Laghouat, 2009 – 2018
