Chapitre 2 : Programmation linéaire

Plan du Chapitre 2
2.1 Exemple introductif

2.2 Formalisation du programme

2.3 Méthode graphique

2.4 Algorithme du simplexe

2.5 Analyse de sensibilité

2.6 Compléments
3

Chap. 2 - Programmation linéaire

2.1 Exemple introductif

Gestion de la production
 4
Cas Production
1 lingot Acier LQ (300€) 1 lingot Acier HQ (800€)

2kg 1kg

4kWh 5kWh

3h 10h

Production par lot de 1000 lingots.

2.1 Exemple introductif

Les contraintes de l’entreprise sont sur les ressources :

8 000kg 20 000kWh 30 000h

Pb : Combien de lots de lingots de chaque type faut-il produire

pour maximiser le chiffre d’affaires ?
5

Chap. 2 - Programmation linéaire

2.2 Formalisation du programme

• Variable de décisions
• Contraintes
• Fonction-objectif
 6
Formalisation du problème (1/3)
1) Variables de décision
2.2 Formalisation
 7
Formalisation du problème (2/3)
2) Contraintes

Il y a aussi des contraintes logiques : on produit des quantités

2.2 Formalisation

positives !
 8
Solutions
Solutions admissibles
2.2 Formalisation

L’ensemble des solutions admissibles est, en général, infini :

c’est un polygone convexe = un « simplexe »
 9
2.2 Formalisation
Représentation graphique

1)Matière premières 2)Energie 3)Laminage 4)Logique

10
Formalisation du problème (3/3)
3) Critère d’optimisation – Fonction-objectif

La fonction-objectif étant linéaire, et les contraintes étant des

2.2 Formalisation

inéquations linéaires, on parle d’une programmation linéaire.

11
Solutions
Solution optimale

Théorème
S’il existe une solution optimale, alors elle est égale à un
2.2 Formalisation

sommet du simplexe de l’ensemble des solutions admissibles.

12

Chap. 2 - Programmation linéaire

2.3 Méthode graphique

• Sommets du simplexe
• Droite isoprofit
• Fonction-objectif
13
Méthode graphique
Point O :
2.3 Méthode graphique
14
Méthode graphique
Point D, solution de :

Toute la Matière Première est utilisée :

la contrainte est « saturée »
càd la ressource est épuisée
2.3 Méthode graphique

Z=1200k€
15
Méthode graphique
Point C, solution de :

Les contraintes Matière Première et Energie

sont saturées
2.3 Méthode graphique

Z=2067k€
16
Méthode graphique
Point A, solution de :

La contrainte Laminage est saturée

2.3 Méthode graphique

Z=2400k€
17
Méthode graphique
Point B, solution de :

Les contraintes Laminage et Energie

sont saturées

Z=2520k€
2.3 Méthode graphique
 18
2.3 Méthode graphique
Méthode graphique
19

Chap. 2 - Programmation linéaire

2.4 Algorithme du simplexe

• Forme canonique
• Forme standard
• Solution initiale
• Tableau initial
• Variable entrant dans la base
• Variable sortant de la base
• Arrêt de l’algorithme
20
Algorithme du simplexe
• Pour 2 variables, l’ensemble des solutions admissibles est
un polygone convexe. On peut utiliser la méthode graphique.

• Au-delà, la méthode graphique n’est plus utilisable.

On utilise alors « l’algorithme du simplexe »
2.4 Algorithme du simplexe
21
Algorithme du simplexe
Algorithme du simplexe
2.4 Algorithme du simplexe
22
Forme canonique

Maximiser
2.4 Algorithme du simplexe
23
Forme canonique
Pour écrire le programme sous forme canonique,
il faut éventuellement effectuer les transformations :
2.4 Algorithme du simplexe
24
Variables d’écart

Exemple :
2.4 Algorithme du simplexe

quantité de Matière Première restante

quantité d’Energie restante
quantité de Laminage restant
25
Forme standard
Forme canonique Forme standard

Exemple :
2.4 Algorithme du simplexe
26
Solution initiale admissible
1) Soit il y a une solution initiale admissible évidente :
2.4 Algorithme du simplexe

2) Soit il n’y a pas de solution initiale admissible évidente :

Ce cas sera traité en TD.

27
Etape 0 : tableau initial

Base Résultat
2 1 1 0 0 8
2.4 Algorithme du simplexe

4 5 0 1 0 20
3 10 0 0 1 30

-Z 300 800 0 0 0 0
28
Etape 0 : tableau initial
Base Résultat
2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
-Z 300 800 0 0 0 0
2.4 Algorithme du simplexe

• La fonction-objectif s’écrit en fonction des variables hors-

base : coefficients non nuls pour les variables hors-base.
• On lit la valeur de –Z dans Résultat.
29
2.4 Algorithme du simplexe Etape 1 : choix du pivot, variable entrante

300 800 0 0 0 0
30
Interprétation géométrique
Base Résultat
2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
-Z 300 800 0 0 0 0
2.4 Algorithme du simplexe
31
Etape 1 : choix du pivot, variable sortante
Base Résultat
2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
2.4 Algorithme du simplexe
32
Interprétation géométrique
Base Résultat Rapport
2 1 1 0 0 8 8/1=8
4 5 0 1 0 20 20/5=4
3 10 0 0 1 30 30/10=3
-Z 300 800 0 0 0 0
2.4 Algorithme du simplexe

On choisit le plus petit rapport :

33
Etape 1 : choix du pivot

Base Résultat Rapport

2 1 1 0 0 8 8/1=8
4 5 0 1 0 20 20/5=4
3 10 0 0 1 30 30/10=3
-Z
-z 300 800 0 0 0 0
2.4 Algorithme du simplexe

1) Variable entrant : plus grand coefficient de la fonction objective

2) Variable sortant : plus petit rapport

On obtient ainsi le coefficient qui va servir de pivot

34
Etape 2 : mise à jour du tableau
Base Résultat

2 1 1 0 0 8
4 5 0 1 0 20
3 10 0 0 1 30
-Z 300 800 0 0 0 0
2.4 Algorithme du simplexe

Base Résultat

1,7 0 1 0 -0,1 5

2,5 0 0 1 -0,5 5

0,3 1 0 0 0,1 3

-Z 60 0 0 -80 0 -2 400
35
Interprétation géométrique
Base Résultat
1,7 0 1 0 -0,1 5
2,5 0 0 1 -0,5 5
0,3 1 0 0 0,1 3
-Z 60 0 0 -80 0 -2 400
2.4 Algorithme du simplexe
36
Itération étape 1
Et on recommence à l’étape 1, si l’on peut améliorer la fonction-objectif.

Base Résultat Rapport

1,7 0 1 0 -0,1 5
2.4 Algorithme du simplexe

2,5 0 0 1 -0,5 5 5/2,5=2

0,3 1 0 0 0,1 3 3/0,3=10
-Z 60 0 0 -80 0 -2 400 -2 400
37
Itération étape 2
Base Résultat

1,7 0 1 0 -0,1 5
2,5 0 0 1 -0,5 5
0,3 1 0 0 0,1 3
-z 60 0 0 -80 0 -2 400
2.4 Algorithme du simplexe

Base Résultat

0 0 1 -0,68 0,24 1,6

1 0 0 0,4 -0,2 2

0 1 0 -0,12 0,16 2,4

-Z 0 0 0 -24 -68 -2 520

Et on recommence à l’étape 1, si l’on peut améliorer la fonction-objectif.

38
Interprétation géométrique
Base Résultat
0 0 1 -0,68 0,24 1,6
1 0 0 0,4 -0,2 2
0 1 0 -0,12 0,16 2,4
-Z 0 0 0 -24 -68 -2 520
2.4 Algorithme du simplexe
39
Arrêt de l’algorithme

Base Résultat

0 0 1 -0,68 0,24 1,6

1 0 0 0,4 -0,2 2

0 1 0 -0,12 0,16 2,4

-Z 0 0 0 -24 -68 -2 520

2.4 Algorithme du simplexe

Le programme est donc optimum : on lit dans Résultat :

39
Méthode des deux phases
La méthode du simplexe impose une solution de base réalisable de départ.
Lorsque nous l’avons pas, nous utilisons la méthode des deux phases (variante
de la méthode du simplexe).
Considérons le programme linéaire mis sous la forme standard
Max Z= c x
(PLS) A x = b x désigne le vecteur variable du PLS ainsi
x0 que les variables d’écart
Associons à ce programme (PLS) la programme auxiliaire suivant:
2.4 Algorithme du simplexe

(PLA) Ax+y=b y désigne le vecteur variable artificielle

x, y  0 On rajoute à la contrainte n’ayant pas de
variable de base une variable artificielle
Principe:
- Phase 1: Résoudre le programme linéaire auxiliaire (PLA). Si ce problème
possède une solution optimale finie , alors cette solution est de base réalisable
de départ pour le programme linéaire (PLS).
- Phase 2: Résoudre (PLS) en utilisant comme solution de base réalisable celle
trouvée en phase 1.
 Recherche d’une solution de base
réalisable
Remarques:
1) Exprimer d’abord la fonction objectif en termes de variables hors
base uniquement avant de commencer la résolution de (PLA).
2) A la fin de la phase 1, s’il existe une solution optimale finie, elle doit
nécessairement être nulle ; yi=0 i  I(A).
3) Pour accroitre la rapidité de la résolution du problème, il est
2.4 Algorithme du simplexe

conseillé d’ajouter dans la tableau du simplex à la phase 1 la

fonction objectif de (PLS).
 Exemple
Soit le PL suivant:
Min Z= x1 + 2 x2 Max Z’= - x1 - 2 x2
2 x1+ x2  6 2 x1+ x2 + e1 = 6
x1 + x2 = 4 (PLS) x1 + x2 =4
x1 + 3 x2  8 x1 + 3 x2 - e2 = 8
x1 , x2  0 x1 , x2 , e1, e2  0
2.4 Algorithme du simplexe

Le problème auxiliaire s’obtient en ajoutant au PLS une variable

artificielle à la seconde et troisième contrainte
Min  = a1 + a2
2 x1+ x2 + e1 =6
(PLA) x1 + x2 + a1 = 4
x1 + 3 x2 - e2 + a2 = 8
x1 , x2 , e1, e2 , a1, a2  0
Min  = a1 + a2  Max ’=-12 + 2 x1+ 4x2 - e2
 Phase 1: Exemple
1ière itération

Base b Rap x1 x2 e1 e2 a1 a2
e1 6 6 2 1 1 0 0 0
a1 4 4 1 1 0 0 1 0
a2 8 8/3 1 3 0 -1 0 1
’ 12 2 4 0 -1 0 0
Z’ 0 -1 -2 0 0 0 0
2.4 Algorithme du simplexe

2ième itération

Base b Rap x1 x2 e1 e2 a1
e1 10/3 2 5/3 0 1 1/3 0
a1 4/3 2 2/3 0 0 1/3 1
x2 8/3 8 1/3 1 0 -1/3 0
’ 4/3 2/3 0 0 1/3 0
Z’ 16/3 -1/3 0 0 -2/3 0
 Exemple
Phase 1:
3ière itération
Base b x1 x2 e1 e2
e1 0 0 0 1 -1/2
x1 2 1 0 0 1/2
x2 2 0 1 0 -1/2
’ 0 0 0 0 0
Z’ 6 0 0 0 -1/2
.4 Algorithme du simplexe

Le test se termine et la solution de base réalisable de départ pour PLS

est : x1 = 2 x2 =2 e1 = e2= 0 Z=6
Phase 2
Base b x1 x2 e1 e2
e1 0 0 0 1 -1/2
x1 2 1 0 0 1/2
x2 2 0 1 0 -1/2
Z’ 6 0 0 0 -1/2
Nous avons: cj 0 j, il s’ensuit que la solution de base réalisable
trouvée en phase 1 est une solution optimale pour PL
45
Méthode du Grand M
Lorsque nous n’avons pas une solution de base réalisable de départ,
nous pouvons recourir à la méthode du Grand M (variante de la
méthode du simplexe).

Si l’objectif est un maximum, les variables artificielles doivent être

pénalisées dans la fonction économique par un coefficient très grand
précédé par un signe négatif , on le notera –M.
2.4 Algorithme du simplexe

Si l’objectif est un minimum, les variables artificielles doivent être

pénalisées dans la fonction économique par un coefficient très grand
précédé par un signe positif, on le notera +M. M étant suffisamment
grand pour que l’on soit sûr que les variables artificielles soient
exclues de la solution optimale,
46
Méthode du Grand M
le programme linéaire sera mis sous la forme standard pour un objectif
de type maximum::
Max Z= c x - M × y y désigne le vecteur variable artificielle
(PLS) A x = b x désigne le vecteur variable du PLS
ainsi
x0 que les variables d’écart
Mais pour un objectif de type minimum:
Min Z= c x + M × y y désigne le vecteur variable artificielle
2.4 Algorithme du simplexe

(PLS) A x = b x désigne le vecteur variable du PLS ainsi

x0 que les variables d’écart

Associons à ce programme (PLS) la programme auxiliaire suivant:

(PLA) A x + y = b y désigne le vecteur variable artificielle
x, y  0 On rajoute à la contrainte n’ayant pas de
variable de base une variable artificielle et on applique l’algorithme du
simplexe en considérant la fonction économique qui inclut le grand M, et
on arrête l’algorithme quand tous les cj deviennent tous ≤0 pour un max
ou t ≥0 pour un min
47

Chap. 2 - Programmation linéaire

2.5 Analyse de sensibilité

• Fonction-objectif
• Contraintes
48
Analyse de sensibilité
On souhaite évaluer les conséquences d’un changement de stratégie.

Que ce passe-t-il si l’on fait varier

• la fonction-objectif : augmenter le prix de vente d’un des produits ?
• les contraintes : augmenter une des ressources ?
2.5 Analyses de sensibilité

Laminage 
49
Analyse de sensibilité de la fonction-objectif
La fonction-objectif est égale à :

Point B, solution de :

Donc le programme B reste optimal si :

2.5 Analyse de sensibilité
50
Analyse de sensibilité de la fonction-objectif
Le programme B :

• Le programme B reste optimal si le prix de HQ varie :

2.5 Analyse de sensibilité

• Le programme B reste optimal si le prix de LQ varie :

51
Analyse de sensibilité des ressources : prix caché
Le programme optimal
sature les contraintes Energie et Laminage.
2.5 Analyse de sensibilité

On dit alors que se sont des « ressources rares ».

52
Analyse de sensibilité des ressources : prix caché
Supposons que l’on dispose de 1000h de laminage en plus :

Laminage 

On refait tourner l’algorithme du simplexe : le nouveau

programme optimal est
2.5 Analyse de sensibilité

La fonction-objectif augmente de 2588 – 2520 = 68K€.

Cette valeur est appelée « shadow price » ou « prix caché ».

Si on achète 1000h de laminage, on gagne 68K€ :

•Prix d’achat maximum de 1000h de laminage ;
•Prix de vente minimum de 1000h de laminage.
53
Analyse de sensibilité : prix caché
On peut lire les prix cachés dans le tableau final du simplexe.
Ce sont les valeurs des variables d’écart respectives :
2.5 Analyse de sensibilité

Contrainte Variable d’écart Prix caché (K€)

Matière première 0
Energie 24
Laminage 68

Le programme optimal ne sature pas la contrainte matière

première, donc son prix caché est nul !
54

Chap. 2 - Programmation linéaire

2.6 Compléments
• Cas transport optimal
• Cas mélange optimal
55
Cas Transport
Demande
50 tonnes
Capacité de production
100 tonnes
Coût du transport U1->E1
4 000€

Demande
E1 E2 E3 70 tonnes

Capacité de production U1 4 3 6
100 tonnes U2 3 5 3

Demande
80 tonnes
2.6 Compléments

Le transport s’effectue par camions ayant une charge utile d’1 tonne

Pb : Quelles quantités transporter des usines vers les entrepôts ?

56
Cas Transport
1) Variables de décision

2) Contraintes
2.6 Compléments

3) Fonction-objectif
On cherche à :
57
Cas Mélange
La fonderie a reçu une commande de 5 tonnes d’acier.
Cet acier doit avoir les caractéristiques suivantes :
Elément chimique % min % max
Carbone ( C ) 2 3
Cuivre (Cu) 0,4 0,6
Manganèse (Mn) 1,2 1,65

Elle dispose pour cela des matières premières suivantes :

Elément chimique %C % Cu %Mn Stock (kg) Coût (€/kg)
Alliage de fer 1 2,5 0 1,3 4 000 1,2
Alliage de fer 1 3 0 0,8 3 000 1,5
2.6 Compléments

Alliage de cuivre 1 0 90 0 5 000 1,3

Alliage de cuivre 2 0 96 4 2 000 1,45
Alliage d’aluminium 1 0 0,4 1,2 3 000 1,2
Alliage d’aluminium 2 0 0,6 0 2 500 1

Pb : Quelle est la composition de l’acier qui minimise les coûts de production ?

58
Cas Mélange
1) Variable de décision

2) Contraintes
2.6 Compléments

3) Fonction-objectif
On cherche à :