Upload
others
View
10
Download
0
Embed Size (px)
Citation preview
Programmation Linéaire
OptimisationAlain Faye
Programmation linéaireRésolution
1
Contenu
• Définition d’un programme linéaire
• Résolution graphique
• Algorithme du simplexe
• Méthode des tableaux
• Méthode des 2 phases
• Utilisation du « solveur » Excel
• Conclusion
• Annexes
2
Forme générale d’un PL
3
min / max 𝑧 = 𝑓 𝑥 = 𝑗=1
𝑛
𝑐𝑗𝑥𝑗
s.c.
𝑗=1
𝑛
𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 𝑖 ∈ 𝑀≤
𝑗=1
𝑛
𝑎𝑖𝑗𝑥𝑗 ≥ 𝑏𝑖 𝑖 ∈ 𝑀≥
𝑗=1
𝑛
𝑎𝑖𝑗𝑥𝑗 = 𝑏𝑖 𝑖 ∈ 𝑀=
𝑥𝑗 ≥ 0 𝑗 = 1, … , 𝑛
On peut soit minimiser soit maximiser l’objectif zM≤ indices des contraintes d’inégalités de type ≤M≥ indices des contraintes d’inégalités de type ≥M= indices des contraintes d’égalitéChacun de ces ensembles peut être videOn peut toujours se ramener si besoin à des variables sans signeen posant xj = xj
+ - xj- avec xj
+ ≥ et xj- ≥0
Résolution d’un PL
• 2 variables : résolution graphique
• n2 variables : algorithme du simplexe
4
Un peu d’analyse
développement d’une fonction f autour d’un point x(0)
𝑓 𝑥 = 𝑓 𝑥(0) + 𝛻𝑓 𝑥(0) 𝑥 − 𝑥(0) + ⋯
𝛻𝑓 𝑥 =
𝑓
𝑥1
⋮𝑓
𝑥𝑛
gradient de f
Cas f linéaire: 𝑓 𝑥 = 𝑐𝑥 = 𝑐1𝑥1 + ⋯ + 𝑐𝑛𝑥𝑛
𝛻𝑓 𝑥 =
𝑐1
⋮𝑐𝑛
𝑐𝑥 = 𝑐𝑥(0) + 𝑐 𝑥 − 𝑥(0)
5
Direction de déplacement
On considère f linéaire : 𝑓 𝑥 = 𝑐𝑥
A partir de x(0) on se déplace dans une direction d : x=x(0)+d
𝑐 𝑥(0) + 𝛼𝑑 = 𝑐𝑥(0) + 𝛼𝑐𝑑
• Si d = c= gradient de f
𝑐 𝑥(0) + 𝛼𝑐 = 𝑐𝑥(0) + 𝛼𝑐𝑐 = 𝑐𝑥(0) + 𝛼 𝑐 2
La valeur de la fonction augmente quand on s’éloigne de x(0)
• Si d = c = opposé du gradient de f
𝑐 𝑥(0) − 𝛼𝑐 = 𝑐𝑥(0) − 𝛼𝑐𝑐 = 𝑐𝑥 0 − 𝛼 𝑐 2
La valeur de la fonction diminue quand on s’éloigne de x(0)
6
Exemple
Soit 𝑓 𝑥 = 𝑥1 + 2𝑥2
Le point 𝑥(0) =00
• Déplacement dans le sens du gradient 𝑑 = 𝛻𝑓 =12
𝑥(0) + 𝛼𝑑 = 𝛼12
𝑓 𝑥(0) + 𝛼𝑑 = 𝛼 + 2 2𝛼 = 5α
• Déplacement dans le sens opposé au gradient 𝑑 = −𝛻𝑓 = −12
𝑥(0) + 𝛼𝑑 = −𝛼12
𝑓 𝑥(0) + 𝛼𝑑 = −𝛼 + 2 −2𝛼 = −5α
7
Résolution graphique d’un PL
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
𝑥1 + 𝑥2 ≤ 3𝑥1 ≤ 2−𝑥1 + 𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
8
On trace l’ensemble des solutions réalisables
32
3
2
x1
x2
0
9
1
1
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
𝑥1 + 𝑥2 ≤ 3𝑥1 ≤ 2−𝑥1 + 𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
On minimise l’objectif z sur le domaine tracé
z = 0L’opposé du gradient de z est une direction de descente Pour minimiser pousser la droite z=0dans la direction opposée au gradient de z
10
32
3
2
x1
x2
0
1
1
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
𝑥1 + 𝑥2 ≤ 3𝑥1 ≤ 2−𝑥1 + 𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
−𝛻𝑧 =12
Déplacement maximum en restant dans le domaine
z = -5
pousser au maximum en restant dans le domaineLe dernier point = (1 , 2) D’où z = -5
11
32
3
2
x1
x2
0
1
1
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
𝑥1 + 𝑥2 ≤ 3𝑥1 ≤ 2−𝑥1 + 𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
Bilan de la résolution graphique
• On se déplace selon une direction de descente
(si on minimise)
• Direction de montée si on maximise
• L’optimum est atteint en un point extrême du domaine (l’ensemble des solutions réalisables)
• Pratique pour n=2 variables
• Pour n=3 faire des dessins en 3 dimensions
• et n4 ?
12
Résultats généraux
• Représentation paramétrique des polyèdres
• Résultats sur la minimisation d’une forme linéaire
13
14
Représentation paramétrique des polyèdres
Polyèdre : ensemble des solutions d’un système d’inégalités linéaires
P = {x : Ax≤b}
Point extrême de P = point de P qui ne peut pas s’exprimer commecombinaison convexe de 2 points distincts de P
Polyèdre borné (i.e. ne contient pas de points infiniment « grands »)
xP xConv(Ext P) (l’enveloppe convexe des points extrêmes de P)
x = σ𝑥𝑖∈𝐸𝑥𝑡 𝑃 𝑖𝑥𝑖 avec 𝑖 ≥ 0 𝑖 , σ𝑖 𝑖 = 1
15
Polyèdre non borné
Rayons de P = Q = {d: Ad ≤0}Q un cône convexe c’est-à-dire si d1 , d2 Q alors α1d1+ α2d2 Q α1, α2 ≥ 0
Rayon extrême est un rayon qui ne peut pas s’exprimer comme combinaison positive de 2 rayons distincts de P
Représentation paramétrique de P
xP xConv(Ext P) + Cône(Ray P) l’enveloppe convexe des points extrêmes de P + l’enveloppe conique des rayons extrêmes de P
x = σ𝑥𝑖∈𝐸𝑥𝑡 𝑃 𝑖𝑥𝑖 + σ
𝑑𝑗∈𝑅𝑎𝑦 𝑃 𝛼𝑗𝑑𝑗 avec 𝑖 ≥ 0 𝑖 , σ𝑖 𝑖 = 1 , α𝑗 ≥ 0 𝑗
Représentation paramétrique des polyèdres
Représentation paramétrique: un exemple
16
32
3
2
x1
x2
0
1
1
𝑃 =
2𝑥1 ≥ 𝑥2
𝑥1 − 𝑥2 ≤ 1𝑥1 + 𝑥2 ≥ 1
𝑥1 ≥ 12
𝑄 =
2𝑥1 ≥ 𝑥2
𝑥1 − 𝑥2 ≤ 0𝑥1 + 𝑥2 ≥ 0
𝑥1 ≥ 0
Points extrêmes de P=1
2
1,
1
21
2
,10
Rayons extrêmes de Q=12
,11
. Ce sont des vecteurs
P
17
Soit le problème min z=cx sous contrainte xP={x : Ax≤b}
Cas P borné L’optimum est atteint en un point extrêmeDémonstration:
Soit 𝑥∗ = 𝑎𝑟𝑔𝑚𝑖𝑛 𝑐𝑥𝑖 ∶ 𝑥𝑖 ∈ 𝐸𝑥𝑡 𝑃
xP x = σ𝑥𝑖∈𝐸𝑥𝑡 𝑃 𝑖𝑥𝑖 avec 𝑖 ≥ 0 𝑖 , σ𝑖 𝑖 = 1
cx = σ𝑥𝑖∈𝐸𝑥𝑡 𝑃 𝑖𝑐𝑥𝑖 ≥ σ
𝑥𝑖∈𝐸𝑥𝑡 𝑃 𝑖𝑐𝑥∗ = 𝑐𝑥∗
x* est bien un minimiseur de la forme linéaire cx
Cas P non borné• Soit l’optimum est non borné (-)• Soit l’optimum est atteint en 1 point extrêmeDémonstration:Si dQ tel que cd<0 alors soit xP alors x+αdP α>0 et c(x+αd)=cx +αcd - quand α + Sinon (d Q cd≥0) on peut ne considérer que les points de P dans Conv(Ext P) et on est ramené au cas précédent (P borné).
Minimisation d’une forme linéaire sur un polyèdre
Algorithme du simplexe
• Mise sous forme standard
• Base , solution de base
• Critère d’optimalité d’une solution de base
• Déplacement d’une solution de base à une autre
• Validité de l’algorithme
• Méthode des tableaux : disposition pratique des calculs
• Recherche d’une base initiale: méthode des 2 phases
18
Forme standard
19
min 𝑧 = 𝑐𝑥 s.c. 𝐴𝑥 = 𝑏 , 𝑥 ≥ 0
On se ramène à la forme standard en rajoutant des variables d’écart
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
𝑥1 + 𝑥2 + 𝑥3 = 3𝑥1 + 𝑥4 = 2−𝑥1 + 𝑥2 + 𝑥5 = 1
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
𝑥1 + 𝑥2 ≤ 3𝑥1 ≤ 2−𝑥1 + 𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
20
P = {x≥0 : Ax=b }
A matrice m lignes et n colonnes (n>m) de rang m On peut toujours partitionner les colonnes de A de sorte que A=(B N) où B matrice carrée (m×m) inversible
Théorème
xExt P x=𝑥𝐵
𝑥𝑁avec xB=B-1b≥0 et xN=0 et B matrice carrée (m×m) inversible
extraite de A
Il y a donc au plus autant de points extrêmes que de façons de partitionner A en (B N) avec B inversible
Caractérisation des points extrêmes du polyèdre sous forme standard
21
Base, solution de base
m contraintes , n variables m<nB matrice carrée (m lignes m colonnes) formée de colonnes de AB inversibleQuitte à permuter des colonnes, A se décompose en 2 matrice B et N A=[B N]xB variables de base , xN variable hors-base Ax = b BxB + NxN = b
𝐴 =1 1 1 0 01 0 0 1 0
−1 1 0 0 1
Variables de base x3 , x4 , x5 , hors-base x1 , x2
𝐵 =1 0 00 1 00 0 1
, 𝑁 =1 11 0
−1 1
Il y a de nombreuses bases possibles
𝑥1 + 𝑥2 + 𝑥3 = 3𝑥1 + 𝑥4 = 2−𝑥1 + 𝑥2 + 𝑥5 = 1
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0x3 x4 x5 x1 x2
Solution de base
22
xB variables de base , xN variable hors_baseAx = b BxB + NxN = b xB + B-1NxN = B-1 b
Solution de base:on fixe xN= 0 , alors xB = B-1 b
x1 = x2 = 0 alors solution unique x3 = 3, x4 = 2, x5 = 1
𝑥1 + 𝑥2 + 𝑥3 = 3𝑥1 + 𝑥4 = 2−𝑥1 + 𝑥2 + 𝑥5 = 1
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
Coûts réduits
23
xB variables de base , xN variable hors_baseAx = b BxB + NxN = b xB + B-1NxN = B-1 b
fonction z s’écrit : z = cx z = cBxB + cNxN
On exprime z en fonction de xN uniquement en éliminant xB :
z = cB (B-1 b - B-1 NxN) +cN xN = cB (B-1 b) + (cN - cB B-1 N) xN
Coûts réduits = coefficients des variables hors-base = cN - cB B-1 N
𝑧 = −𝑥1 − 2𝑥2
Variables de base x3 , x4 , x5 , hors-base x1 , x2
c3 = 0 c4 = 0 c5 = 0, hors-base c1 = -1 c2 = -2coûts réduits = cN - cB B-1 N = [-1 -2]
Sol. de base n°1 : var. en base x3, x4, x5
Optimum atteint ?
24
On est sur la solution de base x1 = x2 = 0 x3 = 3, x4 = 2, x5 = 1et z = – x1 – 2x2 = 0On voit que si on augmente x2 (de coefficient -2) la valeur de z va diminuer.De combien peut-on l’augmenter ? Il faut que les variables restent 0
On voit sur le système que la valeur max est 1(par la 3è contrainte)Et quand x2=1 nécessairement x5=0, x3=2 x4=2
Ce point est une autre solution de base:variables de base x2=1, x3=2, x4 =2, hors base x1 =0, x5=0Et z = -2
𝑥1 + 𝑥2 + 𝑥3 = 3𝑥1 + 𝑥4 = 2−𝑥1 + 𝑥2 + 𝑥5 = 1
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
Sol. de base n°2 : var. en base x2, x3, x4
Optimum atteint ?
25
Calculons les coûts réduits pour la nouvelle base: variables en base x2, x3, x4
c’est-à-dire exprimons z en fonction des variables hors-base x1 , x5
Pour cela exprimons d’abord les variables de base en fonction des hors-base
𝐵 =1 0 10 1 00 0 1
, 𝑁 =1 01 0
−1 1, 𝐵−1 =
1 0 −10 1 00 0 1
, 𝐵−1𝑁 =2 −11 0
−1 1,𝐵−1𝑏 =
221
Ce qui donne le système: ൞
2𝑥1 + 𝑥3 −𝑥5 = 2
𝑥1 + 𝑥4 = 2
−𝑥1 𝑥2 + 𝑥5 = 1
Ensuite on exprime z en fonction des variables hors-base donc on remplace x2=1-x5 +x1(dernière ligne) et z = -x1-2(1-x5 +x1) = -2 -3x1 + 2x5
z = -2 sur la sol. de base x2=1, x3=2, x4 =2, x1 =0, x5=0
x3 x4 x2 x1 x5 x1 x5
Sol. de base n°2 : var. en base x2, x3, x4
Optimum non atteint
26
On a le système: ൞
2𝑥1 + 𝑥3 −𝑥5 = 2
𝑥1 + 𝑥4 = 2
−𝑥1 𝑥2 + 𝑥5 = 1
z en fonction des variables hors-base z = -2 -3x1 + 2x5
On voit que si on augmente x1 (de coefficient -3) la valeur de z va diminuer.De combien peut-on l’augmenter ? Les variables doivent rester 0
On voit sur le système que la valeur max est 1 (première équation)Et quand x1=1 nécessairement x3=0, x4=1, x2=2
Ce point est une autre solution de base:variables de base x1=1 x2=2, x4 =1, hors base x3 =0, x5=0 Et z = -5
Sol. de base n°3 : var. en base x1, x2, x4
Optimum atteint ?
27
Calculons les coûts réduits pour la nouvelle base: variables en base x1, x2, x4
c’est-à-dire exprimons z en fonction des variables hors-base x3 , x5
Pour cela exprimons d’abord les variables de base en fonction des hors-base
𝐵 =1 0 11 1 0
−1 0 1, 𝑁 =
1 00 00 1
, 𝐵−1 =
1
20
−1
2−1
21
1
21
20
1
2
, 𝐵−1𝑁 =
1
2
−1
2−1
2
1
21
2
1
2
,𝐵−1𝑏 =112
Ce qui donne le système:
𝑥1 +𝑥32
−𝑥52
= 1
−𝑥32
+𝑥4 +𝑥52
= 1
𝑥2 +𝑥32
+𝑥52
= 2
Ensuite on exprime z en fonction des variables hors-base donc on remplace x1=1-½x3+ ½ x5 (première ligne) x2=2-½x3-½ x5 (dernière ligne) et z = -(1-½x3+ ½ x5)-2(2-½x3-½ x5 ) = -5 +3/2x3 + ½ x5
z = -5 sur la sol. de base x1=1, x2=2, x4 =1, x3 =0, x5=0
x1 x4 x2 x3 , x5
Sol. de base n°3 : var. en base x1, x2, x4
Optimum atteint
28
z = -5 + 3/2x3 + ½ x5
z = -5 sur la sol. de base x1=1, x2=2, x4 =1, x3 =0, x5=0
Les coefficients des variables x3 , x5 sont 0Donc on ne peut plus diminuer la valeur de z.
La solution est optimale.
Validité de l’algorithme du simplexe
29
ThéorèmeSoit une base B telle que B-1b>0.
Alors la solution de base 𝑥∗ =𝑥𝐵
∗
𝑥𝑁∗ = 𝐵−1𝑏
0est optimale ssi les coûts réduits
𝑐𝑁 − 𝑐𝐵𝐵−1𝑁 sont ≥ 0
DémonstrationSens suffisant Soit x0 t.q. Ax=b (x est une solution quelconque réalisable). cx=cx*+c(x-x*). Montrons que c(x-x*)≥0𝑐 𝑥 − 𝑥∗ = 𝑐 − 𝑐𝐵𝐵−1𝐴 + 𝑐𝐵𝐵−1𝐴 𝑥 − 𝑥∗ = 𝑐 − 𝑐𝐵𝐵−1𝐴 𝑥 − 𝑥∗ + 𝑐𝐵𝐵−1𝐴 𝑥 − 𝑥∗
Le dernier terme 𝑐𝐵𝐵−1𝐴 𝑥 − 𝑥∗ = 𝑐𝐵𝐵−1 𝑏 − 𝑏 = 0Le premier terme 𝑐 − 𝑐𝐵𝐵−1𝐴 𝑥 − 𝑥∗ = 𝑐 − 𝑐𝐵𝐵−1𝐴 𝑥 − 𝑐 − 𝑐𝐵𝐵−1𝐴 𝑥∗
𝑐 − 𝑐𝐵𝐵−1𝐴 𝑥 ≥ 0 car 𝑐 − 𝑐𝐵𝐵−1𝐴 ≥ 0 et 𝑥 ≥ 0
𝑐 − 𝑐𝐵𝐵−1𝐴 𝑥∗ = 𝑐𝐵 − 𝑐𝐵𝐵−1𝐵 ; 𝑐𝑁 − 𝑐𝐵𝐵−1𝑁𝑥𝐵
∗
𝑥𝑁∗ = 0 ; 𝑐𝑁 − 𝑐𝐵𝐵−1𝑁
𝑥𝐵∗
0= 0
Note : la démonstration reste valide si B-1b a des coordonnées nulles
Optimalité du simplexe
30
DémonstrationSens nécessaire Supposons j t.q. 𝑐𝑗 − 𝑐𝐵𝐵−1𝐴𝑗 < 0
Alors on peut faire décroître l’objectif. Considérons
𝑥𝜃 = 𝑥∗ + −𝐵−1𝐴𝑗
𝑒𝑗= 𝐵−1𝑏
0+
−𝐵−1𝐴𝑗
𝑒𝑗
𝑐𝑥𝜃 = 𝑐𝑥∗ + 𝜃 −𝑐𝐵𝐵−1𝐴𝑗 + 𝑐𝑗
Donc si >0 alors 𝑐𝑥𝜃 < 𝑐𝑥∗ et x* pas optimalIl faut que x satisfasse les contraintes• Ax=b est vérifié • x 0 ? La partie contraignante est la partie haute de x
𝐵−1𝑏 − 𝜃𝐵−1𝐴𝑗 ≥ 0 (1)
Si B-1b>0, on peut toujours trouver >0 t.q. l’inégalité (1) est vérifiée
𝜃 = min𝐵−1𝑏 𝑖
𝐵−1𝐴𝑗 𝑖
: 𝑖 𝑡. 𝑞. 𝐵−1𝐴𝑗 𝑖> 0
31
Base dégénérée: base B réalisable telle que B-1b≥0 a au moins une coordonnée nulle
Quand on est sur une base dégénérée on peut passer à une autre base (adjacente) sans que pour autant l’objectif z ne change de valeur. En fait, dans ce cas on reste sur le même point.
On peut alors cycler c’est-à-dire revenir sur une base déjà parcourue. En pratique, ceci est très rare. Cependant, il existe des méthodes pour s’en prévenir (règle de Bland).
Quand on est sur une base dégénérée on peut avoir des coûts réduits < 0 et pourtant être en présence d’une solution optimale. Voir l’exemple suivant.
Exemple dégénérescence
32
Soit le problème min 𝑧 = −𝑥1 −1
2𝑥2
s.c.
𝑥1 + 𝑒1 = 1𝑥2 + 𝑒2 = 1
𝑥1 +𝑥2 +𝑒3 = 2𝑥1, 𝑥2, 𝑒1, 𝑒2, 𝑒3 ≥ 0
Base x1 , x2 , e1 – Hors base e2 , e3 . On est sur le point
𝑥1
𝑥2
𝑒1𝑒2
𝑒3
=
11000
z = -3/2 + e3 – e2/2
On fait rentrer e2 de coût réduit <0 et e1=0 sort de la base
Base x1 , x2 , e2 – Hors base e1 , e3
z = -3/2 + e1/2 + e3/2Cette fois les coûts réduits ≥0 indiquent qu’on est à l’optimum et on est toujours sur le même point.
Bilan
• Une solution de base correspond à un point extrême de l’ensemble des solutions réalisables
• On passe de solution de base en solution de base voisines (une seule var. de base change)
• On s’arrête en consultant les coûts réduits:
– Minimisation: coûts réduits0 on stoppe
– Maximisation: coûts réduits0 on stoppe
33
Algorithme du simplexeMéthode des tableaux
34
Méthodes des tableaux
• On met les coefficients du problème dans un tableau
• Chaque tableau correspond à une solution de base
• Chaque ligne du tableau correspond à une contrainte
• La dernière ligne représente la fonction objectif z• Le passage d’un tableau au suivant c’est-à-dire
d’une solution de base à une solution de base voisine se fait simplement (sans calculer B-1)
35
Rappel : vocabulaire, notation
36
Soit le problème: min 𝑧 = 𝑐𝑥 s.c. 𝐴𝑥 = 𝑏 , 𝑥 ≥ 0
• B est une matrice carrée extraite de A par sélection de colonnes de A(nombre de lignes de B = nombre de lignes de A)
• B est inversible
• Sélectionner une colonne de A revient à sélectionner une variable.Les variables sélectionnées pour construire B sont dites en base.
Une colonne j de A sera notée Aj
Base voisine
37
B et B ne diffèrent que par une colonne. s variable (col.) sortante , r variable (col.) entrante
B=
𝑎1𝑠
⋮𝑎𝑟𝑠
⋮𝑎𝑚𝑠
, B=
𝑎1𝑟
⋮𝑎𝑟𝑟
⋮𝑎𝑚𝑟
On a alors:
B-1B=
1 0 𝑦1 0 00 ⋱ ⋮ 00 0 𝑝 0
0 ⋮ ⋱ 00 0 𝑦𝑚 0 1
où B-1
𝑎1𝑟
⋮𝑎𝑟𝑟
⋮𝑎𝑚𝑟
=
𝑦1
⋮𝑝⋮
𝑦𝑚
Base voisine
38
Inversons B-1B
(B-1B)-1=
1 𝑦1 00 ⋱ 00 𝑝 0
0 ⋱ 00 𝑦𝑚 1
−1
=
1 −𝑦1𝑝
0
0 ⋱ 0
01
𝑝0
0 ⋱ 00 −
𝑦𝑚𝑝
1
Alors B-1= (B-1B)-1 B-1 se calcule simplement par pré-multiplication de B-1
par la matrice P=(B-1B)-1
P est simple à obtenir dès que l’on connait le produit de B-1 par la colonne r de la matrice A
Exemples
39
B avec var. de base ={x3 , x4 , x5} , B avec var. de base ={x3 , x4 , x2}
B=1 0 00 1 00 0 1
, B=1 0 10 1 00 0 1
, B-1A2=101
, p=1, P=
1 0 −1
1
0 1 00 0 1
1
, B-1= P B-1 =1 0 −10 1 00 0 1
B avec var. de base ={x3 , x4 , x2} , B avec var. de base ={x1 , x4 , x2}
B=1 0 10 1 00 0 1
, B=1 0 11 1 0
−1 0 1, B-1A1=
21
−1, p=2, P=
1
20 0
−1
21 0
1
20 1
, B-1= P B-1
=
1
20 −1
2
−1
21 1
21
20 1
2
ቐ
𝑥1 + 𝑥2 + 𝑥3 = 3𝑥1 + 𝑥4 = 2−𝑥1 + 𝑥2 + 𝑥5 = 1
Passer d’un tableau à l’autre: pivotage
40
• Itération i, on a B-1Ax = B-1b
• Itération i+1 , on veut B-1Ax = B-1b
Or B-1 = PB-1 et donc on veut PB-1Ax = PB-1b
Donc il suffit de pré-multiplier le tableau précédent par P
Passer d’un tableau à l’autre : pivotage
41
P=
1 −𝑦1𝑝
0
0 ⋱ 0
01
𝑝0
0 ⋱ 00 −
𝑦𝑚𝑝
1
Le tableau courant est pré-multiplié par PLa ligne du pivot est divisée par le pivot p
=
𝑦1
⋮
𝑝
⋮𝑦𝑚
col. r
Passer d’un tableau à l’autre : pivotage
42
P=
1 −𝑦1𝑝
0
0 ⋱ 0
01
𝑝0
0 ⋱ 00 −
𝑦𝑚𝑝
1
Le tableau courant est pré-multiplié par P
La ligne 1 du tableau devient la ligne 1 – la ligne du pivot multipliée par y1/p
=
𝑦1
⋮
𝑝
⋮𝑦𝑚
col. r
Passer d’un tableau à l’autre : pivotage
43
P=
1 −𝑦1𝑝
0
0 ⋱ 0
01
𝑝0
0 ⋱ 00 −
𝑦𝑚𝑝
1
Le tableau courant est pré-multiplié par P
La ligne m du tableau devient la ligne m – la ligne du pivot multipliée par ym/p
=
𝑦1
⋮
𝑝
⋮𝑦𝑚
col. r
Passer d’un tableau à l’autre : pivotage
44
On peut vérifier que après avoir pré-multiplié le tableau courant par Pil apparaît une colonne de la matrice identité dans la colonne r du tableau
=
0⋮
1
⋮0
col. r
Tableau initial : base initiale x3, x4, x5
45
Base x1 x2 x3 x4 x5
x3 1 1 1 0 0 = 3
x4 1 0 0 1 0 = 2
x5 -1 1 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
Zone bleu = contraintesZone verte = fonction objectif z
Variable entrant en base
46
Base x1 x2 x3 x4 x5
x3 1 1 1 0 0 = 3
x4 1 0 0 1 0 = 2
x5 -1 1 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
Coût réduit le plus petit = -2 x2 rentre en base
Variable sortant de base
47
Base x1 x2 x3 x4 x5
x3 1 1 1 0 0 = 3
x4 1 0 0 1 0 = 2
x5 -1 1 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
Coût réduit le plus petit = -2 x2 rentre en base
Qui sort ? Min { 3/1, ….}
Variable sortant de base
48
Base x1 x2 x3 x4 x5
x3 1 1 1 0 0 = 3
x4 1 0 0 1 0 = 2
x5 -1 1 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
Coût réduit le plus petit = -2 x2 rentre en base
Qui sort ? Min { 3/1, 1/1 }
Variable sortant de base
49
Ratios du second membre sur les coefficients>0 de la col. x2 (en zone bleue)
min 3
1,
1
1= 1 qui correspond à x5
Base x1 x2 x3 x4 x5
x3 1 1 1 0 0 = 3
x4 1 0 0 1 0 = 2
x5 -1 1 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
Coût réduit le plus petit = -2 x2 rentre en base
Qui sort ? Min { 3/1, 1/1 } = 1 qui correspond à x5
Changement de base : pivotage
50
Base x1 x2 x3 x4 x5
x3 1 1 1 0 0 = 3
x4 1 0 0 1 0 = 2
x5 -1 1 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
• Ligne du pivot = ligne de la variable qui sort ici x5 (ligne rose)On la divise par le pivot entouré en rouge
• Une ligne i (autre que ligne du pivot) Soit air le coef. à l’intersection de la ligne i et col. rentrante ici x2On la remplace par ligne i – air nouvelle ligne du pivot
Nouveau tableau : base x3, x4, x2
51
Base x1 x2 x3 x4 x5
x3 2 0 1 0 -1 = 2
x4 1 0 0 1 0 = 2
x2 -1 1 0 0 1 = 1
-3 0 0 0 2 = 2 + z
On voit qu’il apparait une colonne de la matrice identitésous la variable x2
Variable entrant en base
52
Base x1 x2 x3 x4 x5
x3 2 0 1 0 -1 = 2
x4 1 0 0 1 0 = 2
x2 -1 1 0 0 1 = 1
-3 0 0 0 2 = 2 + z
Coût réduit le plus petit = -3 x1 rentre en base
Variable sortant de base
53
Base x1 x2 x3 x4 x5
x3 2 0 1 0 -1 = 2
x4 1 0 0 1 0 = 2
x2 -1 1 0 0 1 = 1
-3 0 0 0 2 = 2 + z
Coût réduit le plus petit = -3 x1 rentre en base
Variable de base qui va s’annuler et sortir de base ?Ratios du second membre sur les coefficients>0 de la col. x1 (en zone bleue)
min 2
2,
2
1= 1 qui correspond à x3
Changement de base : pivotage
54
Base x1 x2 x3 x4 x5
x3 2 0 1 0 -1 = 2
x4 1 0 0 1 0 = 2
x2 -1 1 0 0 1 = 1
-3 0 0 0 2 = 2 + z
• Ligne du pivot = ligne de la variable qui sort ici x3 (ligne rose)On la divise par le pivot entouré en rouge
• Une ligne i (autre que ligne du pivot) Soit air le coef. à l’intersection de la ligne i et col. rentrante ici x1On la remplace par ligne i – air nouvelle ligne du pivot
Nouveau tableau : base x1, x4, x2
55
Base x1 x2 x3 x4 x5
x1 1 0 ½ 0 -½ = 1
x4 0 0 -½ 1 ½ = 1
x2 0 1 ½ 0 ½ = 2
0 0 3/2 0 ½ = 5 + z
Tous les coûts réduits 0 (ligne verte)STOP
La solution se lit dans le second membre pour les var. de baseLes var. hors-base sont nulles
La solution est x1=1, x4=1, x2=2, x3=x5=0
Un autre exemple
56
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
−𝑥1 + 𝑥2 ≤ 1−𝑥1 + 2𝑥2 ≤ 3
𝑥1 − 2𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
On trace l’ensemble des solutions réalisables
57
32
3
2
x1
x2
0
1
1
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
−𝑥1 + 𝑥2 ≤ 1−𝑥1 + 2𝑥2 ≤ 3
𝑥1 − 2𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
On minimise l’objectif z sur le domaine tracé
58
L’opposé du gradient de z est une direction de descente Pour minimiser pousser la droite z=0dans la direction opposée au gradient de z
32
3
2
x1
x2
0
1
1
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
−𝑥1 + 𝑥2 ≤ 1−𝑥1 + 2𝑥2 ≤ 3
𝑥1 − 2𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
−𝛻𝑧 =12
Déplacement maximum en restant dans le domaine
59
On peut pousser la droite tant que l’on veutsans quitter l’ensemble des solutions réalisablesOptimum non borné = -
32
3
2
x1
x2
0
1
1
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
−𝑥1 + 𝑥2 ≤ 1−𝑥1 + 2𝑥2 ≤ 3
𝑥1 − 2𝑥2 ≤ 1𝑥10 , 𝑥2 ≥ 0
Appliquons l’algorithme du simplexe
60
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
−𝑥1 + 𝑥2 + 𝑥3 = 1−𝑥1 + 2𝑥2 + 𝑥4 = 3𝑥1 − 2𝑥2 + 𝑥5 = 1
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
Mise sous forme standard: variables d’écart x3, x4, x5 et =
Tableau initial : base x3, x4, x5
61
Base x1 x2 x3 x4 x5
x3 -1 1 1 0 0 = 1
x4 -1 2 0 1 0 = 3
x5 1 -2 0 0 1 = 1
-1 -2 0 0 0 = 0 + z
x2 va rentrer en base Ratios du second membre sur les coefficients>0 de la col. x2 (en zone bleue)
min 1
1,
3
2= 1 correspond à x3
x3 va sortir de base
Tableau suivant : base x2, x4, x5
62
Base x1 x2 x3 x4 x5
x2 -1 1 1 0 0 = 1
x4 1 0 -2 1 0 = 1
x5 -1 0 2 0 1 = 3
-3 0 2 0 0 = 2 + z
x1 va rentrer en base Ratios du second membre sur les coefficients>0 de la col. x1 (en zone bleue)
min 1
1= 1 correspond à x4
x4 va sortir de base
Tableau suivant : base x2, x1, x5
63
Base x1 x2 x3 x4 x5
x2 0 1 -1 1 0 = 2
x1 1 0 -2 1 0 = 1
x5 0 0 0 1 1 = 4
0 0 -4 3 0 = 5 + z
x3 va rentrer en base Dans la colonne x3 (zone bleue) tous les coefficients 0 : -1 , -2 , 0 x3 peut augmenter indéfinimentOptimum non borné
Les deux conditions d’arrêt de l’algorithme du simplexe
• Problème de minimisation1. Coûts réduits 0 STOP optimum trouvé
2. Une variable xi de coût réduit <0 et telle que les coefficients dans la colonne xi sont 0 STOP optimum non borné -
• Problème de maximisation1. Coûts réduits 0 STOP optimum trouvé
2. Une variable xi de coût réduit >0 et telle que les coefficients dans la colonne xi sont 0 STOP optimum non borné +
64
Méthodes des 2 phases Trouver une base initiale et résoudre le problème
65
Base initiale
66
Jusqu’à maintenant, la base initiale était donnée par les variables d’écart.Pas toujours possible.
min 𝑧 = −𝑥1 − 2𝑥2
s.c.
2𝑥1 + 𝑥2 ≥ 2𝑥1 + 2𝑥2 ≥ 2𝑥1 + 𝑥2 ≤ 3𝑥1, 𝑥2 ≥ 0
Ajout variables d’écart
2𝑥1 + 𝑥2 − 𝑥3 = 2𝑥1 + 2𝑥2 − 𝑥4 = 2𝑥1 + 𝑥2 + 𝑥5 = 3
𝑥1, 𝑥2 , 𝑥3, 𝑥4, 𝑥5 ≥ 0
Base x3 , x4 , x5 . Sol. de base pas réalisable : x3=-2, x4=-2, x5=3, x1=x2=0car 2 variables <0
Recherche d’une base réalisable: résolution du problème auxiliaire
67
- On ajoute des variables artificielles sur les contraintes où c’est nécessaire c’est-à-dire sur les contraintes où les var. d’écart sont précédées du signe –- On minimise ensuite la somme des variables artificielles afin de les rendre nulles
min 𝑧′ = 𝑎1 + 𝑎2
s.c.
2𝑥1 + 𝑥2 − 𝑥3 + 𝑎1 = 2𝑥1 + 2𝑥2 − 𝑥4 + 𝑎2 = 2𝑥1 + 𝑥2 + 𝑥5 = 3
𝑥1, 𝑥2 , 𝑥3, 𝑥4, 𝑥5, 𝑎1, 𝑎2 ≥ 0
On a la base a1, a2, x5. Sol. de base réalisable a1=2, a2=2, x5=3, x1=x2=x3=x4=0
On résout le problème avec cette base de départ. Si on trouve a1=a2=0 (hors-base) alors on a une base réalisable formée par 3 variables du problème de départ.
Méthode des 2 phases
• Phase 1– Résolution du problème auxiliaire
– Si les variables artificielles se sont annulées
Alors on a une base de départ pour le problème initial, aller en phase 2
Sinon le problème initial n’a pas de solution réalisable (domaine vide) STOP
• Phase 2– Résoudre le problème initial en partant de la base
trouvée en phase 1
68
Phase 1: tableau initial
69
Base x1 x2 x3 x4 x5 a1 a2
a1 2 1 -1 0 0 1 0 = 2
a2 1 2 0 -1 0 0 1 = 2
x5 1 1 0 0 1 0 0 = 3
-3 -3 1 1 0 0 0 = -4 + z’
Il faut exprimer 𝑧′ = 𝑎1 + 𝑎2 en fonction des variables hors-baseOn remplace a1 et a2 par leur expression en fonction des variables x1, x2, x3, x4donnée dans les deux premières ligneOn obtient la ligne verte
Phase 1-Tableau initial : base a1, a2, x5
70
Base x1 x2 x3 x4 x5 a1 a2
a1 2 1 -1 0 0 1 0 = 2
a2 1 2 0 -1 0 0 1 = 2
x5 1 1 0 0 1 0 0 = 3
-3 -3 1 1 0 0 0 = -4 + z’
x1 va rentrer en base Ratios du second membre sur les coefficients>0 de la col. x1 (en zone bleue)
min 2
2,
2
1,
3
1= 1 correspond à a1
a1 va sortir de base
Phase 1-Tableau suivant : base x1, a2, x5
71
Base x1 x2 x3 x4 x5 a2
x1 1 ½ -½ 0 0 0 = 1
a2 0 3/2 ½ -1 0 1 = 1
x5 0 ½ ½ 0 1 0 = 2
0 -3/2 -½ 1 0 0 = -1 + z’
x2 va rentrer en base Ratios du second membre sur les coefficients>0 de la col. x2 (en zone bleue)
min 1
1/2,
1
3/2,
2
1/2=
2
3correspond à a2
a2 va sortir de base
Phase 1-Tableau final : base x1, x2, x5
72
Base x1 x2 x3 x4 x5
x1 1 0 -2/31/3 0 = 2/3
x2 0 1 1/3 -2/3 0 = 2/3
x5 0 0 1/31/3 1 = 5/3
0 0 0 0 0 = 0 + z’
Les variables artificielles sont hors-base On a maintenant une base pour le problème initial
Phase 2: tableau initial
73
Base x1 x2 x3 x4 x5
x1 1 0 -2/31/3 0 = 2/3
x2 0 1 1/3 -2/3 0 = 2/3
x5 0 0 1/31/3 1 = 5/3
0 0 0 -1 0 = 2 + z
Il faut exprimer 𝑧 = −𝑥1 − 2𝑥2 en fonction des variables hors-base x3, x4 On remplace x1 et x2 par leurs expressions en fonction de x3, x4qui sont données en ligne 1 et 2 du tableauOn obtient la ligne verte
Phase 2-Tableau initial : base x1, x2, x5
74
Base x1 x2 x3 x4 x5
x1 1 0 -2/31/3 0 = 2/3
x2 0 1 1/3 -2/3 0 = 2/3
x5 0 0 1/31/3 1 = 5/3
0 0 0 -1 0 = 2 + z
x4 va rentrer en base Ratios du second membre sur les coefficients>0 de la col. x4 (en zone bleue)
min 2/3
1/3,
5/3
1/3= 2 correspond à x1
x1 va sortir de base
Phase 2-Tableau suivant : base x4, x2, x5
75
Base x1 x2 x3 x4 x5
x4 3 0 -2 1 0 = 2
x2 2 1 -1 0 0 = 2
x5 -1 0 1 0 1 = 1
3 0 -2 0 0 = 4 + z
x3 va rentrer en base Ratios du second membre sur les coefficients>0 de la col. x3 (en zone bleue)
min 1
1= 1 correspond à x5
x5 va sortir de base
Phase 2-Tableau final : base x4, x2, x3
76
Base x1 x2 x3 x4 x5
x4 1 0 0 1 2 = 4
x2 1 1 0 0 1 = 3
x3 -1 0 1 0 1 = 1
1 0 0 0 2 = 6 + z
Tous les coûts réduits 0 (ligne verte)STOPLa solution se lit dans le second membre pour les var. de baseLes var. hors-base sont nulles
La solution est x4=4, x2=3, x3=1, x1=x5=0
Utilisation du « solveur » Excel
77
Installation du solveur
• Cliquer sur l’onglet Fichier
• Cliquer sur Options (une fenêtre va s’ouvrir)
• Cliquer sur Compléments
• Cliquer sur Complément Solveur à droite (il va devenir bleu)
• Cliquer sur OK en bas à droite
78
Définition d’un programme linéaire
• On définit dans une feuille Excel
– Une case par variable
– Une case pour l’objectif z
– Une case pour le membre gauche de chaque contrainte
– Une case pour le membre droit de chaque contrainte
79
80
Ici on voit la définition de l’objectif z
81
Ici on voit la définition du membre gauche de la contrainte 3
Accéder au solveur
• Cliquer sur l’onglet Données
• Il apparait en haut à droite Solveur
• Cliquer sur Solveur
• Un menu s’ouvre pour lui indiquer où se trouve dans la feuille Excel
– L’objectif, si on le maximise ou minimise
– Les variables
– Les contraintes , le sens des contraintes
82
83
On clique sur solveur et on renseigne où sont l’objectif, les variables, membres gauche et droit des contraintes , le sens des contraintes, si on maximise ou minimise
Choix variables >=0 ou pas et choix méthode Simplex PLOn appuie sur résoudre
Conclusion
• PL modèle de nombreux problèmes: économie, production, …
• Résolution efficace par l’algorithme du simplexe et la méthode des tableaux
• D’autres algorithmes existent : points intérieurs, méthodes des ellipsoïdes
• Il existe des « solveurs » libres ou payants• PLNE (nombres entiers) problème discret résolu
par procédures arborescentes (B&B) mais la PL est utilisée, et donc le simplexe, dans ces procédures
84
Annexes
• Démonstration de la validité de l’algorithme du simplexe en utilisant les conditions KKT
85
Conditions de Karush-Kuhn-Tucker
86
Soit le programme mathématique suivantmin 𝑓(𝑥)
s.c. ൝𝑔𝑖 𝑥 ≤ 0 𝑖 ∈ 𝐼
ℎ𝑗 𝑥 = 0 𝑗 ∈ 𝐽
Avec 𝐼 ensemble (fini) d’indices des contraintes d’inégalitéAvec 𝐽 ensemble (fini) d’indices des contraintes d’égalité
𝑓, 𝑔𝑖 𝑖 ∈ 𝐼, ℎ𝑗 𝑗 ∈ 𝐽 , fonctions de classe C1
Conditions nécessaires d’optimalité (Karush-Khun-Tucker)Si x* « qualifié » est un minimiseur local alors il existe 𝑖 ≥ 0 𝑖 ∈ 𝐼 tels que
𝛻𝑓 𝑥∗ +
𝑖∈𝐼
𝑖𝛻𝑔𝑖 𝑥∗ +
𝑗∈𝐽
𝜇𝑗𝛻ℎ𝑗 𝑥∗ = 0 (𝑐1)
𝑖𝑔𝑖 𝑥∗ = 0 𝑖 ∈ 𝐼 (𝑐2)
(c1) est la généralisation de f(x)=0 (f désigne le gradient de f)(c2) sont les conditions de complémentarité : une contrainte non saturée gi(x)<0 i=0i iI j jJ sont appelés « multiplicateurs de Lagrange »
Conditions nécessairesqualification des solutions de base réalisables non-dégénérées
87
Soit une solution de base 𝑥∗ =𝑥𝐵
∗
𝑥𝑁∗ = 𝐵−1𝑏
0t.q. B-1b>0 (non-dégénérée)
Alors x* est qualifié : il vérifie la qualification de l’indépendance linéaire.
DémonstrationConsidérons les contraintes saturées.Parmi les contraintes d’inégalité x0 seules celles relatives aux variables hors-base sont saturées x*N=0 car x*B>0 .Ecrivons la matrice des contraintes saturées en mettant à gauche les colonnes relativesaux variables de base et à gauche les colonnes relatives aux variables hors-base
𝐵 𝑁0 𝐼
Cette matrice est de rang m car B et l’identité I sont inversibles.Et les lignes sont linéairement indépendantes.
Conditions nécessaires
88
Théorème 1Soit une base B telle que B-1b>0 (non dégénérée).
Si la solution de base 𝑥∗ =𝑥𝐵
∗
𝑥𝑁∗ = 𝐵−1𝑏
0est optimale alors les coûts réduits
𝑐𝑁 − 𝑐𝐵𝐵−1𝑁 sont ≥ 0
Démonstrationx* est qualifié (cf page précédente) donc les conditions KKT sont nécessaires.Elles s’écrivent dans le cas de notre PL:il existe ≥0 associé aux contraintes -x≤0 et associé aux contraintes b-Ax=0 tels quec-A+=0 (cPL1)x*=0 (cPL2)B associé aux contraintes -xB ≤ 0 est nécessairement nul car x*B= B-1b > 0Les conditions (cPL1) sur les indices de variables en base donne:cB - B - B = 0 cB = B = cBB-1
Les conditions (cPL1) sur les indices de variables en hors-base donne:cN -N - N = 0 cN - cBB-1 N - N = 0 cN - cBB-1 N = N ≥ 0
Conditions de Karush-Kuhn-Tucker
89
Conditions suffisantes d’optimalité
Les conditions de KKT (c1) et (c2) sont des conditions suffisantes d’optimalité globaledans le cas de programme convexe où f, gi iI sont convexes et hj jJ affines
C’est-à-dire qu’un point x* qui vérifie (c1) et (c2) est optimum global dans le cas convexe
Vérifier (c1) et (c2) c’est savoir exhiber les multiplicateurs , qui satisfont (c1) et (c2) avec x*
La programmation linéaire est un programme mathématique convexe
90
Théorème 2Soit une base B réalisable (B-1 b≥0) avec coûts réduits cN - cB B-1 N ≥0Alors le point défini par xB=B-1 b et xN=0 est optimum.
DémonstrationOn utilise les conditions de Kuhn-Tucker-Tucker.c-A-=0 (1)x=0 (2)
Avec ≷0 associé aux contraintes b-Ax=0 et ≥0 associé aux contraintes -x≤0
En prenant =cBB-1 et = c-A = c - cBB-1A, (1) est vérifié et on a • Pour les colonnes hors-base : N = cN - cBB-1N ≥0• Pour les colonnes en base : B = cB - cBB-1B = 0Donc les signes de sont respectés (≥0)
De plus 𝑥 = 𝐵 𝑁𝑥𝐵
𝑥𝑁= 0 𝑁
𝑥𝐵
0= 0
Donc les conditions de complémentarité (2) sont satisfaites
Donc x satisfait les conditions de KKT. Comme on a un problème linéaire donc convexe, les conditions de KKT sont des conditions suffisantes d’optimalité globale.
Conditions suffisantes