Programmation Linéaire
Cours 1 : programmes linéaires, modélisation et
résolution graphique
Problème de production
Un fabricant produit 2 types de yaourts à la fraise A et B à partir
de Fraise, de Lait et de Sucre. Chaque yaourt doit respecter les
proportions suivantes de matières premières.
A B
Fraise 2 1
Lait 1 2
Sucre 0 1
On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de
sucre.
La vente de 1 Kg de yaourts A et B rapporte respectivement 4e et
5e.
Le fabricant cherche à maximiser son profit.
Modélisation
• Sur quelles quantités peut-on travailler ?
• Que cherche-t-on à optimiser ?
• Quelles sont les contraintes du problème ?
Modélisation
• Sur quelles quantités peut-on travailler ?
• Seules valeurs non constantes : les quantités de yaourts A et B
produites
• On parle de variables
• On les notera xA et xB
• Que cherche-t-on à optimiser ?
• Quelles sont les contraintes du problème ?
Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• Le profit z
• Calculé à partir de xA et xB
• On parle de fonction objectif
• z = 4xA + 5xB
• Quelles sont les contraintes du problème ?
Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• max z = 4xA + 5xB
• Quelles sont les contraintes du problème ?
• Première contrainte : 800 Kg de fraises disponibles
• la quantité utilisée dépend de la production : 2xA + xB
• 2xA + xB ≤ 800
Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• max z = 4xA + 5xB
• Quelles sont les contraintes du problème ?
2xA + xB ≤ 800 (fraises)
xA + 2xB ≤ 700 (lait)
xB ≤ 300 (sucre)
Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• max z = 4xA + 5xB
• Quelles sont les contraintes du problème ?
2xA + xB ≤ 800 (fraises)
xA + 2xB ≤ 700 (lait)
xB ≤ 300 (sucre)
xA , xB ≥0 positivité !
Mon premier programme linéaire
max 4xA + 5xB
2xA + xB ≤ 800
xA + 2xB ≤ 700
xB ≤ 300
xA , xB ≥0
Sommaire
Introduction par l’exemple
Programme linéaire
Résolution graphique
Points extrêmes
Forme standard, bases
Bilan
Règles de réécriture (1)
Toute contrainte d’égalité peut s’écrire comme deux inégalités :
n
(P
n
X a i xi ≤ b
ai xi = b ≡ Pin=1
i =1 i =1 ai xi ≥ b
Toute contrainte ≥ peut s’écrire comme une contrainte ≤ :
n
X n
X
a i xi ≥ b ≡ −ai xi ≤ −b
i =1 i =1
Tout problème de minimisation peut s’écrire comme un problème
de maximisation :
n
X n
X
max ci xi ≡ min −ci xi
i =1 i =1
Ecriture générale d’un programmation linéaire
On peut écrire ainsi un programme linéaire avec n variables
x1 , . . . , xn et m contraintes.
Pn
max i =1 ci xi
Pn
sous les contraintes i =1 aij xi ≤ bj , (j = 1, . . . , m)
xi ∈ R, (i = 1, . . . , n)
• Linéarité : Objectif et contraintes sont des fonctions linéaires
des variables de décision (les coefficients ci et aij des variables
sont constants)
• Continuité : Les variables peuvent prendre n’importe quelle
valeur réelle respectant les contraintes linaires
Exemples simples de programmes non linéaires (1)
Pn
min i =1 xi xi
Pn
sous les contraintes i =1 aij xi ≤ bj , (j = 1, . . . , m)
xi ∈ R, (i = 1, . . . , n)
Pn
min i =1 xi
Pn
sous les contraintes i =1 aij xi ≤ bj , (j = 1, . . . , m)
xi ∈ N, (i = 1, . . . , n)
Exemples simples de programmes non linéaires (2)
Pn
min i =1 ci xi
Pn
sous les contraintes i =1 aij xi ≤ bj , (j = 1, . . . , m)
xi ∈ R ∩ [l1 , u1 ] ∩ [l2 , u2 ], (i = 1, . . . , n)
Pn
min i =1 ci xi
Pn
sous les contraintes i =1 aij xi ≤ bj , (j = 1, . . . , m)
x1 = x2 ou x1 = x3
xi ∈ R, (i = 1, . . . , n)
Forme normale d’un programme linéaire
Tout programme linéaire peut s’écrire sous forme normale.
Pn
max i =1 ci xi
Pn
sous les contraintes i =1 aij xi ≤ bj , (j = 1, . . . , m)
xi ≥ 0, xi ∈ R, (i = 1, . . . , n)
Si on a une variable xi ∈ R, on introduit xi+ ≥ 0 et xi− ≥ 0 et on
pose xi = xi+ + xi− .
Sommaire
Introduction par l’exemple
Programme linéaire
Résolution graphique
Représentation graphique d’un PL
Résolution graphique
Points extrêmes
Forme standard, bases
Bilan
Résolution graphique
• On dispose d’un outil (la PL) pour modéliser des problèmes
• Comment résoudre les problèmes à l’aide de la PL ?
• Plusieurs algorithmes existent, dont le simplexe (prochain
cours)
• Pour des problèmes avec deux variables, on peut résoudre
graphiquement (aide à comprendre la structure du problème)
Représentation graphique
xB
2xA + xB ≤ 800
max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800
xA + 2xB ≤ 700
xB ≤ 300 xA + 2xB ≤ 700
xA , xB ≥0
xA
Représentation graphique
xB
2xA + xB ≤ 800
max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800
xA + 2xB ≤ 700
xB ≤ 300 xA + 2xB ≤ 700
xA , xB ≥0
xA
Représentation graphique
xB
2xA + xB ≤ 800
max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800
xA + 2xB ≤ 700
xB ≤ 300 xA + 2xB ≤ 700
xA , xB ≥0
xA
Représentation graphique
xB
2xA + xB ≤ 800
max 4xA + 5xB
2xA + xB ≤ 800 xB ≤ 300
xA + 2xB ≤ 700
xB ≤ 300 xA + 2xB ≤ 700
xA , xB ≥0
xA
Terminologie
xB
• Solution : 2xA + xB ≤ 800
affectation de valeurs aux
variables
xB ≤ 300
• Solution réalisable :
solution réalisable si les valeurs
satisfont l’ensemble des x = (80, 150) xA + 2xB ≤ 700
contraintes
• Région réalisable :
ensemble des solutions xA
réalisables.
Terminologie
xB
• Solution : 2xA + xB ≤ 800
affectation de valeurs aux
variables
• Solution réalisable : xB ≤ 300
solution réalisable si les valeurs
satisfont l’ensemble des
xA + 2xB ≤ 700
contraintes
• Région réalisable :
ensemble des solutions
réalisables. xA
Résolution graphique
xB
2xA + xB ≤ 800
Max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800
xA + 2xB ≤ 700
xB ≤ 300 xA + 2xB ≤ 700
xA , xB ≥0
xA
Résolution graphique
xB
2xA + xB ≤ 800
Max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800 4xA + 5xB = 2900
xA + 2xB ≤ 700
xA + 2xB ≤ 700
xB ≤ 300
xA , xB ≥0 4xA + 5xB = 2200
4xA + 5xB = 1000 xA
4xA + 5xB = 0
Résolution graphique
xB
2xA + xB ≤ 800
Max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800 4xA + 5xB = 2900
xA + 2xB ≤ 700
xA + 2xB ≤ 700
xB ≤ 300
xA , xB ≥0 4xA + 5xB = 2200
4xA + 5xB = 1000 xA
4xA + 5xB = 0
Résolution graphique
xB
2xA + xB ≤ 800
Max 4xA + 5xB xB ≤ 300
2xA + xB ≤ 800 4xA + 5xB = 2900
xA + 2xB ≤ 700
xA + 2xB ≤ 700
xB ≤ 300
xA , xB ≥0 4xA + 5xB = 2200
4xA + 5xB = 1000 xA
4xA + 5xB = 0
Résolution graphique
xB
2xA + xB ≤ 800
Max 4xA + 5xB
xB ≤ 300
2xA + xB ≤ 800
xA + 2xB ≤ 700 4xA + 5xB = 2900
xB ≤ 300 xA + 2xB ≤ 700
xA , xB ≥0
4xA + 5xB = 2200
4xA + 5xB = 1000 xA
4xA + 5xB = 0
Existence d’une solution (optimale)
Quatre possibilités
y
✻
min x + 2y
s.t. x ≤ 5
x +y ≥3
x, y ≥ 0
✲ x
Une solution optimale unique.
Existence d’une solution (optimale)
Quatre possibilités
y
✻
max x + 2y
s.t. x ≤ 5
x +y ≥3
x, y ≥ 0
✲ x
Solution non bornée.
Existence d’une solution (optimale)
Quatre possibilités
y
max x + 2y ✻
s.t. x ≤ 5
x +y ≥3
x + y ≤ −1
x, y ≥ 0
✲ x
Pas de solution.
Existence d’une solution (optimale)
Quatre possibilités
y
✻
max x
s.t. x ≤ 5
x +y ≥3
x, y ≥ 0
✲ x
Infinité de solutions.
Sommaire
Introduction par l’exemple
Programme linéaire
Résolution graphique
Points extrêmes
Points extrêmes et convexité
Algorithme géomètrique
Forme standard, bases
Bilan
Notion de point extrême
xB
Proposition 2xA + xB ≤ 800
S’il en existe, il y a toujours
une solution optimale sur un
sommet (point extrême) de la xB ≤ 300
région réalisable 4xA + 5xB = 2900
Corollaire xA + 2xB ≤ 700
Pour trouver l’optimum, il 4xA + 5xB = 2200
”suffit” d’examiner les points
extrêmes de la région 4xA + 5xB = 1000 xA
réalisable 4xA + 5xB = 0
Polyèdres et points extrêmes (1)
Définition
Un polyèdre convexe est l’ensemble des solutions d’un système
fini d’inégalités linéaires.
L’ensemble des solutions admissibles d’un PL est donc un polyèdre
convexe.
On s’intéressera dans un premier temps aux polyèdres bornés.
Rappel : S est convexe si
∀x, y ∈ S, ∀λ ∈ [0, 1], λx + (1 − λ)y ∈ S.
Polyèdres et points extrêmes (2)
Définition
Un point x0 d’un ensemble convexe S est un point extrême de S
s’il n’existe pas deux points x1 , x2 ∈ S t.q. x = λx1 + (1 − λx2 ).
Théorème
Soit S un ensemble convexe borné de Rn et S e l’ensemble de ses
points extrêmes. Si x ∈ S alors x peut s’écrire comme une
combinaison convexe de n + 1 éléments de S e .
Rappel : soit x, y, z ∈ Rn . Si x = λy + (1 − λ)z alors pour tout
a ∈ Rn , ax ≤ max{ay, az}.
Théorème
Si le polyèdre formé par l’ensemble des solutions d’un PL est
borné, alors il existe au moins une solution optimale et l’une d’elles
est obtenue sur un point extrême.
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
1
0
xA
4xA + 5xB = 0
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est
optimal, STOP
1
0
xA
4xA + 5xB = 0
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est
optimal, STOP
3. Se déplacer le long de l’arête
jusqu’au point extrême y
suivant.
S’il n’existe pas, le problème est 1
0
xA
non borné, STOP
Sinon, poser x ← y et revenir 4xA + 5xB = 0
en 2
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est
optimal, STOP
3. Se déplacer le long de l’arête
jusqu’au point extrême y
suivant.
S’il n’existe pas, le problème est 1
0
xA
non borné, STOP
Sinon, poser x ← y et revenir 4xA + 5xB = 0
en 2
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est 1
0
optimal, STOP 0
1
3. Se déplacer le long de l’arête
jusqu’au point extrême y
suivant.
S’il n’existe pas, le problème est
non borné, STOP xA
4xA + 5xB = 1500
Sinon, poser x ← y et revenir
en 2
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est 1
0
optimal, STOP 0
1
3. Se déplacer le long de l’arête
jusqu’au point extrême y
suivant.
S’il n’existe pas, le problème est
non borné, STOP xA
4xA + 5xB = 1500
Sinon, poser x ← y et revenir
en 2
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est 11
00
optimal, STOP 00
11
3. Se déplacer le long de l’arête
jusqu’au point extrême y 4xA + 5xB = 1900
suivant.
S’il n’existe pas, le problème est
non borné, STOP xA
Sinon, poser x ← y et revenir
en 2
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est 11
00
optimal, STOP 00
11
3. Se déplacer le long de l’arête
jusqu’au point extrême y 4xA + 5xB = 1900
suivant.
S’il n’existe pas, le problème est
non borné, STOP xA
Sinon, poser x ← y et revenir
en 2
Algorithme géométrique
1. Partir d’un point extrême x de xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est
optimal, STOP
3. Se déplacer le long de l’arête 11
00
004xA + 5xB
11 = 2200
jusqu’au point extrême y
suivant.
S’il n’existe pas, le problème est
non borné, STOP xA
Sinon, poser x ← y et revenir
en 2
Algorithme géométrique
1. Partir d’un point extrême x de
xB
la région réalisable
2. Déterminer une arête le long de
laquelle l’objectif augmente.
S’il n’en existe pas, x est
optimal, STOP
3. Se déplacer le long de l’arête 11
00
004xA + 5xB
11 = 2200
jusqu’au point extrême y
suivant.
S’il n’existe pas, le problème est
non borné, STOP xA
Sinon, poser x ← y et revenir
en 2
Sommaire
Introduction par l’exemple
Programme linéaire
Résolution graphique
Points extrêmes
Forme standard, bases
Bilan
Forme standard
Jusqu’à présent on a utilisé la forme normale pour représenter un
programme linéaire.
On introduit la forme standard qui va être utilisée dans
l’algorithme du simplex.
max z = 4x1 + 5y1 max z = 4x1 + 5x2 +0s1 + 0s2 +0s3
2x1 + x2 ≤4 2x1 + x2 +s1 =4
x1 + 2x2 ≤ 10 x1 + 2x2 + s2 = 10
− x2 ≤ −2 − x2 +s3 = −2
x1 ,x2 ≥0 x1 ,x2 , s1 ,s2 , s3 ≥ 0
Forme standard
À partir de tout PL sous forme normale, on peut construire un PL
sous forme standard
n
n
X
X max z = ci xi
max z = ci xi i =1
i =1 n
n
X
X aij xi + sj = bj (j = 1, . . . , m)
aij xi ≤ bj (j = 1, . . . , m) i =1
i =1
xi ≥ 0(i = 1, . . . , n)
xi ≥ 0(i = 1, . . . , n)
sj ≥ 0(i = 1, . . . , m)
Interprétation de la forme standard
Les variables supplémentaires si sont appelées variables d’écart.
Chaque variable d’écart est associée à une contrainte.
max 5x + y max 5x + y
x + y ≤ 10 x +y +s1 = 10
x −y ≤1 x −y + s2 =1
x ≤3 x +s3 = 3
x, y ≥ 0 x,y , s1 ,s2 , s3 ≥ 0
Quand s1 = 0, la contrainte x + x ≤ 10 est vérifiée à l’égalité.
Forme standard et points extrêmes
y
✻
E
max 5x + y
D
x + y + s1 = 10
x − y + s2 = 1
x + s3 = 3 C
x, y , s1 , s2 , s3 ≥ 0 ✲ x
A B
x = 0, y = 0 : A
x = 0, s2 = 0 : B
Points extrêmes : intersection s2 = 0, s3 = 0 : C
d’hyperplans (contraintes) s1 = 0, s3 = 0 : D
y = 0, s1 = 0 : E
Interprétation de la forme standard
y
✻
E
max 5x + y
D
x + y + s1 = 10
x − y + s2 = 1
x + s3 = 3 C
x, y , s1 , s2 , s3 ≥ 0 ✲ x
A B
Si on annule s2 et s3 ,
x + y + s1 = 10
il reste ce système qui
a pour solution x −y =0
x = 3, y = 3, s1 = 4 x =3
(x, y , s1 ≥ 0)
Sommets = bases
• On dispose d’un PL à n + m variables et m contraintes.
• Si on annule n variables, on obtient un système de m
équations à m inconnues
• Si la matrice associée est de rang m (base), le système admet
une solution unique
• Une base = une solution
• Pour résoudre le problème obtenu : pivot de Gauss !
• Attention : si la solution n’a pas des valeurs positives, elle
n’est pas valide !
Base non réalisable
y
✻
E
max 5x + y
D
x + y + s1 = 10
x − y + s2 = 1
x + s3 = 3 C
x, y , s1 , s2 , s3 ≥ 0 ✲ x
A B
y = 0, s1 = 0 x = 10
Solution x = 10, s2 = −9, x + s2 = 1
s3 = −3, non valide !
x + s3 = 3
(x, s2 , s3 ≥ 0)
Idée de résolution
• Si on a une base réalisable, on a un point extrême = une
solution dominante
• Pour calculer les valeurs des variables pour ces points : pivot
de Gauss
Il reste à voir
• comment trouver une première base réalisable
• comment passer d’une base réalisable à une autre
