MTH8414
OUTILS ET LOGICIELS DE RECHERCHE
OPÉRATIONNELLE EN INGÉNIERIE
Programmation linéaire
- introduction
- un peu de théorie
- analyse de sensibilité
Louis-Martin Rousseau
Office: A520.21 Tel.: #4569 - difficultés
[Link]@[Link] - exercice
Motivation
La programmation linéaire fut développée au cours de la Seconde Guerre mondiale.
• L’objectif était d’allouer plus intelligemment les ressources de l’armé.
• Le terme « programmation » est employé avec le sens de « plan ».
La PL peut résoudre un VASTE nombre de problèmes (modèle de transport, allocation de ressources, théorie
des jeux, tarifications, etc.)
Le développement de la théorie et des algorithmes est une des avancées scientifiques importantes du 20e
siècle
• avec l’accélération des ordinateurs, la vitesse de résolution est améliorée par un facteur de 800 milliard
en 20 ans...
Impact majeur :
• économique : des centaines de millions de $ dans l’industrie aérienne
• santé : traitement en radiothérapie
Louis-Martin ROUSSEAU
Formulation d’un modèle PL
Variable de décisions
• Des variables mathématiques représentant des décisions
Fonction Objectif
• Une équation linéaire qui quantifie un objectif
• L’objectif le plus fréquent des entreprises est de maximiser les profits.
• Pour un département de service, on essaie souvent de minimiser les coûts d’opération.
Contrainte
• Des équations linéaires qui restreignent les variables de décisions.
Louis-Martin ROUSSEAU
Formulation d’un modèle PL
xj = variables de décision
bi = terme de droite
cj = coefficients de la fonction objectif
aij = coefficients des contraintes
Louis-Martin ROUSSEAU
Un exemple
Un menuisier assemble deux produits (chaises et tabourets)
Ses ressources sont limitées à:
• 3000 unités de bois.
• 40 heures de production par semaine.
Le profit est de
• 8$ pour une chaise.
• 5$ pour un tabouret.
Louis-Martin ROUSSEAU
Un exemple
Variable de décision:
• X1 = Production (mensuelle) de chaises
• X2 = Production (mensuelle) de tabourets
Fonction objectif:
• maximiser le profit mensuel
Contraintes
• Une chaise demande 5 unités de bois et 10 minutes d’assemblage.
• Un tabouret demande 3 unité de matière et 15 minutes d’assemblage.
• Pas plus de 800 produits au total par mois (stockage)
• Nombre de chaises ne doit pas dépasser de plus de 400 le nombre de tabourets.
Un exemple
Une stratégie de production intuitive… mais est-elle optimale ?
• Produire le plus possible de chaises (le plus profitable)
• Utiliser les ressources disponibles pour produire des tabourets, tout en respectant les règles.
Le plan consiste donc à produire :
• Chaises = 525 unités
• Tabouret = 125 unités
• Profit = 8×525 + 5×125 = 4825$
Modélisation en PL
Max 8𝑋1 + 5𝑋2 (profit mensuel)
Sujet à
5𝑋1 + 3𝑋2 ≤ 3000 (Bois dispo)
10𝑋1 + 15𝑋2 ≤ 9600 (Temps dispo)
𝑋1 + 𝑋2 ≤ 800 (Stockage)
𝑋1 − 𝑋2 ≤ 400 (Mélange)
𝑋𝑗 ≥ 0, 𝑗 = 1,2 (Non negativité)
Résolution graphique
X2
Contraintes de non-négativité
X1
Résolution graphique
X2
1000 Bois disponible
5X1+3X2 £ 3000
800 Stockage
640 X1+X2 £ 800 (redondante)
Non réalisable
Temps disponible
Réalisable
10X1+15X2 £ 9600
X1
600 800 960
Résolution graphique
X2
1000 Bois disponible
5X1+3X2 £ 3000
800 Stockage
640 X1+X2 £ 800 (redondante)
Non réalisable
mélange
X1-X2 £ 400
Temps disponible Réalisable
10X1+15X2 £ 9600
X1
Points intérieurs Points frontières Points extrêmes
Trois types de points réalisables
Trouver une solution optimale
Débuter avec un profit arbitraire, disons $2,000...
X2
Ensuite on augmente le profit si c’est possible
1000
… en continuant tant qu’on est réalisable
700 Profit $4880
500
X1
500
La solution optimale…
Chaises = 360 unités
Tabourets = 400 unités
Profit = 4880$
• Cette solution utilise tout le matériel et le temps disponible.
• La production est de 760 (non 800).
• La production de tabourets dépasse celle des chaises de 140 unités.
Le plan “intuitif” consistait à produire :
• Chaises = 525 unités
• Tabouret = 125 unités
• Profit = 8×525 + 5×125 = 4825$
MTH8414
OUTILS ET LOGICIELS DE RECHERCHE
OPÉRATIONNELLE EN INGÉNIERIE
Programmation linéaire
- introduction
- un peu de théorie
- analyse de sensibilité
Louis-Martin Rousseau
Office: A520.21 Tel.: #4569 - difficultés
[Link]@[Link] - exercice
Résolution par le simplex
Les inégalités représentent des plans (en 2D) ou des hyperplans.
Un ensemble d’inégalités permet de construire un espace réalisable borné que l’on appelle un polygone
convexe (2D) ou polyèdre convexe.
Un rappel sur la convexité :
• Soit a et b deux solutions réalisables d’un polyèdre convexe, alors (a+b)/2 est aussi une solution de ce
polyèdre
Encore un peu de géométrie…
La propriété des points extrêmes nous dit que si un polyèdre (P) contient une solution optimale, alors il existe
une solution optimale qui est située sur un point extrême.
La bonne nouvelle : on ne peut que considérer les points extrêmes !
La mauvaise nouvelle : le nombre de points extrêmes peut-être exponentiellement élevé par rapport au
nombre de variables de décision.
Le prix de consolation : la convexité garantit que les optimums locaux sont des optimaux globaux.
• C'est-à-dire qu’un point extrême est optimal si tous ses voisins sont pires que lui.
• Mais attention aux plateaux…
Le rôle des points extrêmes…
Si un programme linéaire possède une solution optimale,
alors au moins un point extrême est optimal.
Plusieurs solutions optimales
Si plusieurs solutions optimales existent alors la fonction objectif
doit être parallèle à au moins une des contraintes
Toute moyenne pondérée de
plusieurs solutions optimales est
aussi une solution optimale
L’algorithme du simplexe (Dantzig, 1947)
Développé juste après la Seconde Guerre mondiale
Utilisé pour planifier le pont aérien de Berlin en 1948.
Les grandes lignes de l’algorithme :
• La recherche démarre d’un point extrême
• Elle se déplace (pivot) vers un point extrême voisin
• On répète jusqu’à l’obtention de la solution optimale
D’autres algorithmes pour résoudre les PLs
Il existes d’autres algorithmes pour résoudre des
programmes linéaires, en particulier les méthodes de
points intérieurs
• En théorie ces méthodes converge dans un temps
polynomial (elles devrait donc bcp plus efficaces que
le simplex)
• En pratique elles fonctionnent mieux que l’espaces
est plus «lisse» alors que le simplexe semble plus
efficaces quand les arrêtes sont plus prononcées.
MTH8414
OUTILS ET LOGICIELS DE RECHERCHE
OPÉRATIONNELLE EN INGÉNIERIE
Programmation linéaire
- introduction
- un peu de théorie
- analyse de sensibilité
Louis-Martin Rousseau
Office: A520.21 Tel.: #4569 - difficultés
[Link]@[Link] - exercices
L’analyse de sensibilité
Est-ce que la solution optimale est sensible aux paramètres du problème ?
Pourquoi se poser cette question ?
• Les paramètres utilisés ne sont que des estimations
• Dans un environnement dynamique, ceux-ci peuvent changer régulièrement.
• Une analyse de scénarios (what-if) peut permettre de proposer des changements aux paramètres.
Analyse sensibilité (objectif)
Intervalle d’optimalité
La solution optimale demeurera inchangée tant que:
• Un coefficient de la fonction objectif demeure dans son intervalle d’optimalité;
• Rien d’autre ne change.
La valeur de cette solution changera si:
• Le coefficient qui a changé multiplie une variable dont la valeur optimale est non nulle.
Analyse sensibilité (objectif)
1000 X2
M
ax
Ma 4 X
x3 1 +
.33 5X
X
M
1 +5 2
ax
X
8X
2
1
+
Max
5X
2X
+ 5X
2
1
2
X1
500 800
Analyse sensibilité (objectif)
X2
1000
M
ax
8X
Intervalle d’optimalité pour X1: [3.33, 8.33]
1
Ma
+
Ma
5X
x3
x8
.33
2
.33
X
1 +5
X1
X
+5
2
X2
400 600 800 X1
Analyse sensibilité (objectif)
Coûts réduits
En assumant que rien d’autre ne change dans les paramètres, le coût réduit d’une variable qui vaut 0 dans
la solution optimale est:
• L’inverse de l’augmentation du coefficient de l’objectif de la variable Xj (Cj) nécessaire pour que la
variable devienne positive dans la solution optimale.
• OU, c’est le changement à la valeur de l’objectif pour chaque unité d’augmentation de Xj (nulle).
Écart complémentaire
Pour une solution optimale, soit la variable vaut 0, soit c’est son coût réduit qui vaut 0.
Analyse sensibilité (termes de droite)
L’analyse de sensibilité du terme de droite des contraintes est utile pour répondre aux questions suivantes:
• En conservant tous les paramètres inchangés, de combien l’objectif de la solution optimale changerait si
on modifiait le terme de droite d’une contrainte.
• Pour combien d’unité supplémentaire (ou de moins) est-ce que la solution optimale demeurerait la même ?
Analyse sensibilité (termes de droite)
Tout changement au terme de droite d’une contrainte active (qui touche la solution optimale) entraînera une
modification de la solution optimale.
Tout changement au terme de droite d’une contrainte inactive qui est plus petite que l’écart entre la solution
et cette contrainte n’entrainera pas de modification à la solution optimale.
Coûts marginaux
En assumant que rien d’autre ne change dans les paramètres, l’augmentation de la valeur de l’objectif pour
chaque augmentation d’une unité du terme de droite d’une contrainte est nommée le coût marginal de cette
contrainte.
Coût marginal (graphique)
Contrainte
matière X2
Si on dispose de plus de matière, le
terme de droite de cette contrainte
augmente
1000
5X 1
5X 1
Profit = $4880
+3
+3
x2
x2
£3 0 Profit = $ 4881.5
£3
640
00
00
1 Coût marginal =
4881.5 – 4880 = 1.5
Contrainte X1
temps
500
Intervalle de réalisabilité
En assumant que rien ne change dans les paramètres, l’intervalle de réalisabilité est défini comme:
• L’intervalle dans lequel le terme de droite d’une contrainte peut varier, sans que le coût
marginal n’en soit affecté.
• Dans cet intervalle, la fonction objective varie comme suite: Obj = Obj + CoutMarginal * Modif.
Intervalle de réalisabilité
Contrainte
matière X2 L’augmentation de la matière
n’est seulement utile jusqu’à
5X 1
ce qu’une nouvelle contrainte
+3
soit active
x2
£3 Nouvelle
Contrainte 00 contrainte
0
production active
X1 + X2 £ 800 Solution non réalisable
Contrainte
temps
X1
500
Intervalle de réalisabilité
Contrainte
matière X2
5X 1
Notez que le profit
augmente avec la quantité
+3 de matière
x2
£3
00
0
Contrainte
temps
X1
500
Intervalle de réalisabilité
X2
Si moins de matière est
1000
disponible…
Solution
Non réalisable
500 5X1 + 3X2 £ 2500
… le profit diminue
Nouvelle
contrainte
active X1
500
MTH8414
OUTILS ET LOGICIELS DE RECHERCHE
OPÉRATIONNELLE EN INGÉNIERIE
Programmation linéaire
- introduction
- un peu de théorie
- analyse de sensibilité
Louis-Martin Rousseau
Office: A520.21 Tel.: #4569 - difficultés
[Link]@[Link] - exercice
Problèmes rencontrés en PL.
La programmation linéaire est un outil de modélisation et de résolution très puissant.
Par contre, dans certaines situations, on peut rencontrer certaines difficultés…
• Solutions optimales multiples
• Phénomène de dégénérescence et cyclage
• Solution réalisable inexistante
• Solution non bornée
Solutions optimales multiples
Soit le problème linéaire suivant:
Max z = 3x1 + 4x2
sujet à:
3x1 + 4x2 ≤ 12
3x1 + 3x2 ≤ 10
4x1 + 2x2 ≤ 8
x1 ≥ 0
x2 ≥ 0
Solutions optimales multiples
So
op lutio
tim ns
ale
s
f
cti
bje
O
Solutions optimales multiples
•La fonction objectif tracée au niveau optimal coïncide avec la droite (contrainte) : 3𝑥! + 4𝑥" = 12
•Tous les points sur le segment de droite joignant (0,3) à (4/5, 12/5) représentent des solutions optimales i.e.:
3x1* + 4 x2* = 12
0 £ x1* £ 4 5
12 5 £ x2* £ 3
z * = 12
Solutions réalisables inexistantes
Soit le programme linéaire suivant:
Max x0 = 4x1 + 3x2
Sujet à:
3x1 + 4x2 ≤ 12 (2.11)
x1 + x2 ≥ 4 (2.19)
4x1 + 2x2 ≤ 8 (2.13)
x1 ≥ 0
x2 ≥ 0.
Solutions réalisables inexistantes
Il n’existe pas de point qui satisfasse toutes
les contraintes simultanément.
41
Problème de PL non borné
Soit le programme linéaire suivant:
Max z = x1 + x2 (2.21)
Sujet à:
−4x1 + x2 ≤ 2 (2.22)
x1 + x2 ≥ 3 (2.23)
x1 + 2x2 ≥ 4 (2.24)
x1 − x2 ≤ 2 (2.25)
x1 ≥ 0
x2 ≥ 0.
42
Problème de PL non borné
x2
+
x 1
Pas de solution optimale
43
MTH8414
OUTILS ET LOGICIELS DE RECHERCHE
OPÉRATIONNELLE EN INGÉNIERIE
Programmation linéaire
- introduction
- un peu de théorie
- analyse de sensibilité
Louis-Martin Rousseau - difficultés
Office: A520.21 Tel.: #4569 - exercice
Louis-
[Link]@[Link]
Exemple : le problème du brasseur
Une petite micro-brasserie produit 2 types de produit (une Ale et une Bière). Suite à une sécheresse, la
production doit être limitée par le manque de ressources en céréales (maïs, houblon, malte).
Le tableau suivant donne les recettes utilisées pour la production, ainsi que les ressources disponibles et le
profit associé à chaque produit.
Bière Mais (lb) Houblon(on) Malte(lb) Profit($)
Ale 5 4 35 10
Bière 15 4 20 23
Quantité 480 160 1190
Comment le brasseur peut-il maximiser son profit ?
• Ne faire que de l’Ale ?
• Ne faire que de la Bière ?
• 7,5 barils d’Ale et 29,5 barils de Bière ?
• 12 barils d’Ale et 28 barils de Bière ?
Exemple : le problème du brasseur
Trouver le mélange optimal
De combien peuvent varier les prix sans qu’il ne faille changer le plan de production.
De quelle matière première devrait négocier davantage de volume.
De quelle matière première pourrait-on réduire le volume (et de combien).
Que se passe-t-il si le prix de la bière monte à 30 $ ?