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

On choisit le plus petit rapport :

2.4 Algorithme du simplexe
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 :

40

Chap. 2 - Programmation linéaire

2.5 Analyse de sensibilité

• Fonction-objectif
• Contraintes
41
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 ➔
42
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é
43
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 :

44
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 ».

45
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.
46
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 !
47

Chap. 2 - Programmation linéaire

2.6 Compléments
• Cas transport optimal
• Cas mélange optimal
48
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 ?

49
Cas Transport
1) Variables de décision

2) Contraintes
2.6 Compléments

3) Fonction-objectif
On cherche à :
50
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 ?

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

2) Contraintes
2.6 Compléments

3) Fonction-objectif
On cherche à :