Outils de Recherche
Opérationnelle
La programmation linéaire: Introduction
Motivation
La programmation linéaire fut développée au cours de la
Seconde Guerre mondiale.
L’objectif était d’
d’allouer plus intelligemment les ressources de l’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, ...)
Le développement de la théorie et des algorithmes est une des
avancées scientifiques importantes du 20e siècle
avec l’l’accélération des ordinateurs, la vitesse de résolution est améliorée par
un facteur de 1 milliard en 15 ans...
Impact majeur :
économique : des centaines de millions de $ dans l’l’industrie aérienne
santé : traitement en radiothérapie
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 service, on essaie souvent de minimiser les coûts
d’opération.
Contrainte
Des équations linéaires qui restreignent les variables de
décisions.
Formulation d’un modèle PL
Max/min z = c1x1 + c2x2 + ... + cnxn
subject to:
a11x1 + a12x2 + ... + a1nxn (≤, =, ≥) b1
a21x1 + a22x2 + ... + a2nxn (≤, =, ≥) b2
:
am1x1 + am2x2 + ... + amnxn (≤, =, ≥) bm
xj = variables de décision
cj = coefficients de la fonction objectif
aij = coefficients des contraintes
bi = terme de droite
Un exemple
Un fabricant assemble 2 produits (A et B)
Ses ressources sont limitées à:
1000 unités de matériel.
matériel.
40 heures de production par semaine
semaine..
Le profit est de
8$ pour une unité de A.
5$ pour une unité de B.
Un exemple
Variable de décision:
X1 = Prodution (hebdo) de produit A
X2 = Prodution (hebdo) de produit B
Fonction objectif:
maximiser le profit hebdomadaire
Contraintes
Produit A consomme 2 unités de matière et 3 minutes de temps.
Produit B consomme 1 unité de matière et 4 unités de temps.
Pas plus de 700 produits au total par semaine (stockage)
Nombre de A ne doit pas dépasser de plus de 350 le nombre de B.
Un exemple
Le plan de production actuel prévoit:
Produire le plus possible de A (le plus profitable)
Utiliser les ressources disponibles pour produire du B,
tout en respectant les règles.
Le plan consiste donc à produire:
Produit A = 450 unités
Produit B = 100 unités
Profit = 4100$ hebdo
8(450) + 5(100)
Modélisation en PL
Max 8X1 + 5X2 (profit hebdo
hebdo))
sujet à
2X1 + 1X2 ≤ 1000 (Matière dispo)
dispo)
3X1 + 4X2 ≤ 2400 (Temps dispo)
dispo)
X1 + X2 ≤ 700 (Stockage
Stockage))
X1 - X2 ≤350 (Mélange)
Xj >= 0, j = 1,2 (Non negativité
negativité))
Résolution graphique
X2
Contraintes de non-négativité
X1
Résolution graphique
X2
1000 Matière dispo
2X1+X2 ≤ 1000
700 stockage
X1+X2 ≤ 700 (redondante)
500
non réalisable
Temps dispo
3X1+4X2 ≤ 2400 Réalisable
X1
500 700
Résolution graphique
X2
1000 Matière dispo
2X1+X2 ≤ 1000
700 Stockage:
X1+X2 ≤ 700 (redondante)
500
non réalisable
mélange
Réalisable X1-X2 ≤ 350
Temps dispo
3X1+4X2≤ 2400
X1
Points intérieurs Points frontières Points extrêmes
• Trois types de points réalisables
Trouver une solution optimale
Trouver une solution optimale
Débuter avec un profit arbitraire, disons $2,000...
Ensuite on augmente le profit si c’est possible
X2
1000 … en continuant tant qu’on est réalisable
700 Profit $4360
500
X1
500
La solution optimale…
Produit A = 320 unités
Produit B = 360 unités
Profit = 4360$
Cette solution utilise tout le matériel et le
temps disponible
La production est de 680 (non 700).
Produit B dépasse A par 40 unités.
Le rôle des points extrêmes…
Si un programme linéaire a une solution
optimale, alors au moins un point extrême est
optimal.
