Chapitre 1

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 14

Université IBN Tofail

Faculté des Sciences


Département Informatique

Recherche Opérationnelle :
Programmation liniéaire
Chapitre 1

Author: Filière:
Pr. Khalil IBRAHIMI Licence SMI, S5

September 30, 2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

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:

• Formulation du problème à résoudre: Les objectifs, les contraintes et


les variables de décision;

• Modélisation du problème (modèle mathématique);

• Solution au problème c’est de trouver la valeur optimale de l’objectif;

• 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

• La recherche opérationnelle est née pendant la Seconde Guerre mon-


diale des efforts conjugués d’éminents mathématiciens (dont von Neu-
mann, Dantzig, Blackett) à qui il avait été demandé de fournir des
techniques d’optimisation des ressources militaires;

• En 1940 par le Prix Nobel de physique Patrick Blackett qui résolut un


problème d’implantation optimale de radars de surveillance;

• A partir des années 50, la recherche opérationnelle fait son entrée dans
les entreprises;

• Au milieu des années 70, à cause d’un excès d’enthousiasme au départ et


à l’inadéquation des moyens informatiques à l’application des méthodes
de la RO, la discipline s’essoulle;

• A partir du milieu des années 90, on assiste à un retour en force la RO,


les outils informatiques étant maintenant à la hauteur des méthodes
proposées par la recherche opérationnelle (exemple IBM CPLEX Opti-
mizer);

Pr. Khalil IBRAHIMI 1 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

Exemples des domaine d’applications de la RO:

• Production : maximiser le profit selon la disponibilité de la main


d‘oeuvre, demande du marché, capacité de production, prix de revient
du matériau brut;

• Réseaux de transports : minimiser la distance totale parcourue selon


les quantités de matériaux à transporter, capacité des transporteurs;

• Réseaux de communication, systèmes d’information: conception, con-


figuration;

• Télécomuncations : optimisation de déploillement de stations de base


du réseau mobile;

• Finance;

• Economie;

• Santé;

Exemple du problème de production :


Une usine fabrique 2 produits P1 et P2 nécessitant des ressources d’équipement,
de main d’oeuvre et de matières premières disponibles en quantité limitée.
Les deux produits P1 et P2 rapportent respectivement à la vente 6 dh et 4
dh par unité.

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

Type de question: Quelles quantités de produits P1 et P2 doit produire


l’usine pour maximiser le bénéfice total venant de la vente des 2 produits?
Problème de transport
Deux usines à Casa et à Tanger fabriquent des produits pour une distribution
aux clients qui se trouvent à Casa, Rabat, Fès selon leurs demandent dj . La

Pr. Khalil IBRAHIMI 2 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

capacité de production est Ci . Le coût cij de distribution est en fonction de la


quantité transportée entre la source et la destination. La capacité maximale
de production.
U sine Casa T anger
P roduction 60 50
La demande
clients Casa Rabat F es
Demande 20 50 30
Le prix unitaire
P rix/unité Casa Rabat F es
Casa 0 100 300
T anger 500 200 400
Quel est le plan optimal de distribution à coût minimal. La réponse est de
suivre les méthodes qui vont être exposées dans les sections suivantes.

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

Pr. Khalil IBRAHIMI 3 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire


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.

2.2 Formes d’un programme linéaire (PL)


Définition : On a des problèmes qui peuvent être formulés en tant que max-
imisation où minimisation d’un objectif, en fonction des ressources limitées
et de contraintes. Si on arrive à expimer l’objectif sous forme d’une fonction
linéaire en fonction des contraintes sous la forme d’égalités ou d’inégalités
sur ces variables, alors on a un problème de programmation linéaire (PL).
Fonction linéaire : On définit une fonction linéaire f pour tout variable xi
et nombre réel ai par: f (x1 , x2 , ..., xn ) = a1 x1 + a2 x2 + ... + an xn = nj=1 aj xj
P
Si b est un nombre réel et f est une fonction linéaire, alors l’équation f (x1 , x2 , ..., xn ) =
b est une égalité linéaire et les inégalités linéaires: f (x1 , x2 , ..., xn ) ≥ b et
f (x1 , x2 , ..., xn ) ≤ b.
Définition : Un problème de programmation linéaire consiste à min-
imiser ou maximiser une fonction liniéaire soumise à des contraintes liniéaires
(fini).

Type du programme : Si l’objectif du problème est de minimiser, le


programme linéaire porte le nom de programme linéaire de minimisation.
Si l’objectif du problème est de maximiser, le programme linéaire porte le
nom de programme linéaire de maximisation.
La formulation et la résolution du programme linéaire nécessite de mettre le
problème sous forme algébrique, canonique ou standard.
Forme canonique : Nous considérons n nombres réels c1 , c2 , ..., cn ;
m nombres réels b1 , b2 , ..., bm ; et m*n nombres réels aij pour j = 1, ..., n
et i = 1, ..., m. On cherche à P trouver n nombres réels x1 , x2 , ..., xn qui
maximisent la fonction objectif nj=1 cj xj
Sous les contraintes de positivités xj ≥ 0 pour j = 1, ..., n

Pr. Khalil IBRAHIMI 4 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

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.

Avec A = (aij ) est une matrice m x n, b = (bi ) est un vecteur de dimension


m et c = (cj ) est un vecteur de dimension n et x = (xj ) est un vecteur de
dimension n.

2.3 Solution réalisable


Définition : Une solution réalisable est toute configuration des variables x̄
qui satisfait à toutes les contraintes.
Une configuration de x̄ qui ne satisfait au moins une contrainte est dite
irréalisable.
Si un programme n’a aucune soltution réalisable, il est irréalisable; sinon, il
est réalisable.
Si le programme a des solutions réalisables sans avoir la valeur de l’objectif
optimale finie, alors il est non borné.
Valeur de l’objectif:
Nous dirons qu’une solution x̄ a la valeur objectif cT x̄.
Une solution x̄ dont la valeur objectif est suppérieure à toutes les solutions
réalisables est une solution optimale. Sa valeur est appelée valeur de l’objectif
optimale.

2.4 Interprétation géométrique


Si
K = {x|Ax ≤ b, x ≥ 0}
où A est une matrice carrée d’ordre m. Alors K est l’intersection de l’orthan
non négatif de
Rn+ = {x|x ≥ 0}

Pr. Khalil IBRAHIMI 5 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

et de m demi-espaces (Ax ≤ b), c’est un polyédre de R


Les points de K satisfaisant les contraintes avec le signe d’égalité (Ax = b)
sont situés sur des faces de K. Leur intersection définit un sommet de K
(point extrême)
La maximisation de la fonction objectif sur K, permet de trouver un x∗
dans K et une valeur z ∗ tels que l’hperplan cT x coupe le domaine K en un
point extrême du polyèdre. L’algorithme du Simplex qu’on va présenter
ultérieurement consistera à se déplacer entre les points extrêmes jusqu’à
lorsqu’on trouve un optimum.

2.5 Exemple d’une solution géométrique


La méthode est connue sous le nome de la (méthode de droite de paralléle.
Maximiser
z = x1 + x2
Sous les contraintes
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
5x1 − 2x2 ≥ −2
x1 , x2 ≥ 0
L’ensemble d’intersections est le polyèdre OABCD. Première méthode est le
recensement des sommets. Calculer la valeur de l’objectif à chaque sommet,
puis de choisir la plus grande qui est l’omptimale.
Deuxième méthode est la méthodes des droites parallèles à la droite qui passe
par l’origine (bénéfice est nulle, x1 + x2 = 0). La solution optimale du PL est
tout point d’intersection du polyèdre avec la droite x1 + x2 = 8 en sommet
B (2, 6).

Pr. Khalil IBRAHIMI 6 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

La région de réalisation est bornée, il existe une valeur maximale de z dans


laquelle l’interesection de la droite z = x1 + x2 et la région est non vide.

2.6 Propriétés fondamentale de la programmation linéaire


Théorème. Soit A une matrice et b un vecteur.
1.Le système Ax = b a une solution non négative si et seulement si yb ≥ 0
pour tout vecteur y satisfaisant yA ≥ 0.
2.Le système Ax ≤ b a une solution x si et seuelement si yb ≥ 0 pour tout
vecteur y ≥ 0 satisfaisant yA = 0.
Propriété 1 Soit K = {x|Ax ≤ b, x ≥ 0}. Si K est non vide, alors K a
au moins un point extrême.
Propriété 2: Si une fonction linéaire atteint son maximum (ou son min-
imum) sur K, alors cet optimum a lieu en un point extrême de K.
Exemple de problème de production Une usine fabrique 2 produits
P1 et P2 nécessitant des ressources d’équipement, de main d’oeuvre et de
matières premières disponibles en quantité limitée. Les deux produits P1 et
P2 rapportent respectivement à la vente 6 dh et 4 dh par unité.

Pr. Khalil IBRAHIMI 7 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

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

Q1. Quelles quantités de produits P1 et P2 doit produire l’usine pour max-


imiser le bénéfice total venant de la vente des 2 produits? (méthode des
droites parallèles)

Q2. Utiliser la méthode du recensement des sommets du polygone pour


maximiser le bénéfice total.
Modélisation

• Choix des variables: Deux variables positives :


- quantité de P1 produite : x1 ≥ 0
- quantité de P2 produite : x2 ≥ 0

• Objectif = Une fonction économique

M ax z = 6x1 + 4x2

• Contraintes = des inégalités ( trois demi-espaces)

3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20

• Appel de la méthode des droites parallèle pour déterminer la production


optimale.

2.7 Difficulté de généralisation de la mèthode géométrique


1. Il est difficile de généraliser la representation géométrique dans un espace
plus de 3 dimensions.
2. Un autre problème lorsque le nombre contraintes augmente même pour
deux variables.

Pr. Khalil IBRAHIMI 8 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

Théoréme Si l’ensemble des contraintes d’un programme liniéaire forme


un polyèdre non vide, alors il existe une solution optimale qui est le sommet
de ce polyèdre.
La solution optimale du PL est alors trouvée en recensant tous les points du
polyèdre, puis calculer la valeur de la fonction objectif et de choisir la plus
grande valeur qui représente la solution optimale.
Une nouvelle méthode du Simplexe géométrique permet à partir d’une solu-
tion initiale (point de départ du polyèdre), lors de toute itération de passer
d’un sommet à un sommet voisin en lequel la valeur de la fonction objectif
est meilleure. L’algoritme s’arrête lorsqu’on ne trouve aucun sommet voisin
dont la valeur de la fonction objectif est meilleure.

2.8 Interprétation économique d’un programme liniéaire


Soit un P.L suivant:
maximiser n
X
z= cj x j
j=1

Sous les contraintes de positivités (xj ≥ 0)


n
X
aij xj ≤ bi pour i = 1, ..., m
j=1

Cette formulation signifie qu’une entreprise exerce un ensemble d’activités j.


Chaqu’une consomme une ressource aij de bi par unité et peut être exercée
avec une quantité xj . Si enfin le cj est le profit unitaire obtenu de l’activité j.
Alors déterminer les quantités xj de manière que: la valeur de z soit maximal
en respectant les contraintes de la disponbilité des ressources.

2.9 Conversion de programmes linéaires sous forme


canonique
Il existe des programmes linéaires qui ne peuvent pas être sous forme canon-
ique. Par exemple,

• La fonction objectif peut être une minimization au lieu de maximiza-


tion;

Pr. Khalil IBRAHIMI 9 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

• Il peut avoir des variables sans la contrainte de positivité;

• Il peut avoir des contraintes d’égalités aulieu d’inégalité;

• Il peut avoir des contraintes d’inégalités de signe différent (suppérieur


aulieu d’inférieur où égale).

Constat Lorsqu’on convertit un programme linéaire L en un programme


linéaire L’, on cherche que la solution optimale de L’ donne une solution
optimale au programme L.
Deux programmes linéaires de maximisation L et L’ sont des équivalent
si pour toute solution réalisable de L ayant pour valeur objectif z, il existe
une solution réalisable homologue de L’ ayant la même valeur objectif z et
l’inverse.
Un programme de maximisation L et un programme de minimisation L’ sont
équivalents si pour toute solution réalisable de L ayant pour valeur objectif
z, il existe une solution réalisable homologue de L’ ayant la valeur objectif -z
et l’inverse.

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

Pr. Khalil IBRAHIMI 10 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

positivités x02 ≥ 0 x002 ≥ 0


maximiser
2x1 − 3(x02 − x002 )
sous les contraintes
x1 + x02 − x002 = 7
x1 − 2(x02 − x002 ) ≤ 4
x1 , x02 , x002 ≥ 0
Ensuite, nous convertissons la contrainte dégalité x1 +x02 −x002 = 7 en inégalités

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

−x1 − x02 + x002 ≤ −7

On renome les variables pour la cohérence et on trouve la forme canonique.


maximiser
2x1 − 3x2 + 3x3
sous les contraintes
−x1 − x2 + x3 ≤ −7
x1 + x2 − x3 ≤ 7
x1 − 2x2 + 3x3 ≤ 4
x1 , x2 , x3 ≥ 0

Pr. Khalil IBRAHIMI 11 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

Forme canonique mariciel


Maximiser
z = cx
sous les contraintes
Ax ≤ b
x≥0
Exemple:
x = (x1 , x2 , x3 )T , b = (−7, 7, 4)T , c = (2, −3, 3)
 
−1 −1 1
A= 1 1 −1 
1 −2 3

2.10 Conversion d’un PL en forme standard


Un programme linéaire est sous forme standard si uniquement les contraintes
de positivités sont des contraintes d’inégalités, toutes les autres contraintes
étant des égalités.
La conversion de la i-éme i = 1, ..., m contrainte d’inégalité à égalite.
n
X
aij xj ≤ bi
j=1

La nouvelle variable d’écart est noté xn+i et la contrainte devient


n
X
xn+i = bi − aij xj
j=1

avec la contrainte de positivité xn+i ≥ 0.


Les variables de gauche xn+i sont des variables de base, alors les variables
de droite xj sont des variables hors-base qui figures seul dans la fonction
objectif.
Exemple
maximiser
2x1 − 3x2 + 3x3
Sous les contraintes
x4 = −7 + x1 + x2 − x3

Pr. Khalil IBRAHIMI 12 a.u: 2021-2022


FSK, SMI, S5 Chapitre 1 Programmation linéaire

x5 = 7 − x1 − x2 + x3
x6 = 4 − x1 + 2x2 − 3x3
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

On mettre les contraintes de positivité x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 et la forme


standard est:

z = 2x1 − 3x2 + 3x3


x4 = −7 + x1 + x2 − x3
x5 = 7 − x1 − x2 + x 3
x6 = 4 − x1 + 2x2 − 3x3
Soit N designe l’ensemble des indices des variables hors-base et B désigne
l’esemble des indices des variables de base. Une forme standard est un tuple
(N, B, A, b, c, v) telque: X
z=v+ cj x j
j∈N
X
xi = b i − aij xj
j∈N

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

Pr. Khalil IBRAHIMI 13 a.u: 2021-2022

Vous aimerez peut-être aussi