Chapitre 1
Chapitre 1
Chapitre 1
Recherche Opérationnelle :
Programmation liniéaire
Chapitre 1
Author: Filière:
Pr. Khalil IBRAHIMI Licence SMI, S5
1 Introduction
Définition La recherche opérationnelle est la discipline des mathématiques
appliquées qui traite des questions d’utilisation optimale des ressources dans
l’industrie, les réseaux, la logistique et les transports. L’objectif du cours
est de donner aux étudiants qui souhaitent occuper un poste d’ingénieur
technique les bases de la recherche operationnelle. La méthodologie de la
recherche opérationnelle (RO) suit le schéma suivant:
• Implémentation de la solution.
L’étudiant au final doit proposer une meilleure utilisation des ressources (util-
isation optimale) face à un problème de recherhce opérationnelle.
Histoire
• A partir des années 50, la recherche opérationnelle fait son entrée dans
les entreprises;
• Finance;
• Economie;
• Santé;
P 1 P 2 Disponibilité(contraintes)
Équipement 3 9 81
0
M aind oeuvre 4 5 55
M atière première 2 1 20
P rof it unitaire 6 4 z = 10
2 Programmation Linéaire
2.1 Rappel sur le calcul matriciel
Matrice
Une matrice estun tableau
rectangualire. Exemple
a11 a12 a13 1 2 3
A= =
a21 a22 a23 4 5 6
A = (aij ) est une matrice de taille 2*3; i=1,2; j=1,2,3. Une matrice carrée
de dimension n*n. Le transposé d’une matrice est obtenu en échangeant les
lignes
et les colonnes.
1 4
AT = 2 5
3 6
L’inverse d’une matrice A de taille nxn est noté A−1 telque A ∗ A−1 = I. Une
matrice A inversible est dite non sigulière. Si la matrice n’a pas d’inverse
A−1 est dite singulière (det(A) =0) ou non inversible.
Vecteur (colonne) Un vecteur est un tableau à une dimension. Exemple
1
x = 2
3
Vecteur ligne est le transposé de x teq: xT = 1 2 3
Le vecteur unité ei le vecteur dont le iéme élément est égale à 1 et tous les
autres égaux à 0. Vecteurs linéairement dépendants Les vecteurs x1 , x2 , ..., xn
est linéairement dépendants s’il existe des cofficients c1 , c2 , ..., cn non nuls tels
que c1 x1 + c2 x2 + ... + cn xn = 0. Sinon ils sont dits linéarement indépendants
T T
(cas de colonnes d’une matrice I). Exemple. x1 = 1 2 3 , x2 = 2 6 4 , x3 =
T
4 11 9 , sont liniéarement dépendants car,2x1 + 3x2 − 2x3 = 0 Rang
d’une matrice Le rang d’une matrice est un entier compris entre 0 et min(m,
n). Le nombre de colonnes ou de lignes de A linéairement indépendants.
Pn
Et contraintes d’inégalité inférieur ou égale à j=1 aij xj ≤ bi pour i =
1, ..., m
Forme canonique matriciel tuple (A, b, c) :
Soit le programme suivant:
maximiser
cT x
T est le transposé.
Sous les contraintes
Ax ≤ b et x ≥ 0.
P 1 P 2 Disponibilité(contraintes)
Équipement 3 9 81
0
M aind oeuvre 4 5 55
M atière première 2 1 20
M ax z = 6x1 + 4x2
3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20
2.9.1 Exemple
Conversion d’un PL de minimisation à un PL de maximisation
Soit le programme linéaire suivant:
minimiser
−2x1 + 3x2
sous les contraintes
x1 + x2 = 7
x1 − 2x2 ≤ 4
0 ≤ x1
On inverse les coefficeints de la fonction objectif.
maximiser
2x1 − 3x2
sous les mêmes contraintes.
Conversion d’un PL au forme canonique On a pas le signe de la
variable x2 . Dans ce cas, on remplace x2 par x02 − x002 avec les contraintes de
x1 + x02 − x002 ≥ 7
et
x1 + x02 − x002 ≤ 7
maximiser
2x1 − 3(x02 − x002 )
sous les contraintes
x1 + x02 − x002 ≥ 7
x1 + x02 − x002 ≤ 7
x1 − 2(x02 − x002 ) ≤ 4
x1 , x02 , x002 ≥ 0
En fin, nous prenons l’opposé de la contrainte x1 + x02 − x002 ≥ 7 qui est
x5 = 7 − x1 − x2 + x3
x6 = 4 − x1 + 2x2 − 3x3
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
pour i ∈ B.
La forme standard
B = {4, 5, 6}, N = {1, 2, 3} b = (−7, 7, 4)T , c = (2, −3, 3)T et v = 0.
−1 −1 1
A= 1 1 −1
1 −2 3