Recherche

opérationnelle
Professeur: BAKRIM FADWA
Docteur et ingénieur d’Etat en mathématiques appliquées
Année universitaire: 2022/2023
Chapitre 1: Programmation linéaire (PL)
• Définition
• Forme générale d’un programme
• Terminologie
• Exemples d’application
Chapitre 2: Résolution graphique d’un programme linéaire
Chapitre 3: Méthode du simplexe
Chapitre 4: Dualité
• Début de la recherche opérationnelle: XXe siècle en 1939 en
GrandBretagne (l’étude de la gestion de stock avec la formule du lot
économique (dite formule de Wilson))
• Elle a commence avec la seconde guerre mondiale. L’état major
anglais a convoque une équipe d’experts de divers domaines
(scientifiques, mathématiciens, ingénieurs, économistes, etc.) pour
étudier les problèmes d’optimisation militaire (l’implantation de radars de
surveillance, la gestion de transport, la protection de convois maritimes contre les sous-
marins ..etc)
• Pour résoudre ces problèmes: programmation linéaire

Pr. Bakrim 2023/2024

• La recherche opérationnelle est un outil puissant pour la résolution des
problèmes d’optimisation linéaire, et on peut l’appliquer dans différents
domaines : économie, finance, ingénierie, etc...

Exemple:
En se basant sur le principe du comportement optimal du producteur, on sait
qu’en général, l’objectif de l’entreprise est de maximiser le profit, ce qui donne
en contre partie de minimiser les couts. Ainsi, pour réaliser un tel objectif
l’entreprise doit assurer une allocation optimale de ces ressources rares (sans
gaspillage), mise en disposition de l’entreprise pour effectuer sa production.
Facteurs de Produit
ESe fini
production
Pr. Bakrim 2023/2024
La R.O est l’application de méthodes, techniques et outils scientifiques à des problèmes liés à l’exploitation de systèmes
afin de leur permettre de maîtriser les opérations avec des solutions optimales au problème.. - Churchman, Acoff,
Arnoff
V

La R.O consiste en l’application de méthodes scientifiques pour résoudre les problèmes complexes rencontres dans la
direction et la gestion de grands systèmes d’hommes, de machines, de matériaux, et d’argent dans l’industrie, le
Commerce, l’administration et la défense. La caractéristique de l’approche est le développement d’un modelé
scientifique (incluant la mesure de facteurs tels que le hasard et le risque) avec lequel on tente de prévoir et de
comparer les résultats de diverses décisions ou stratégies. Le but est d’aider la direction à déterminer sa politique de
manière scientifique. - La Société de R.O de Grande Bretagne.

La R.O est l’ensemble des méthodes et techniques rationnelles d’analyse et de synthèse des phénomènes d’organisation
utilisables pour élaborer de meilleures décisions. - R. Faure, B. Lemaire et C. Picouleau

La R.O est l’étude quantitative des opérations d’une organisation complexe et la prévision des effets des changements
dans les conditions de ces opérations de façons à permettre aux responsables de la direction d’obtenir un rendement
optimum des ressources disponibles. - R.G. Brown Pr. Bakrim 2023/2024
CHAPITRE 1: Programmation
Linéaire
• Un programme linéaire (PL) est un outil d’optimisation utilisé pour
résoudre un problème de maximisation (ou minimisation) d’une
fonction objectif linéaire de n variables, tout en tenant compte à un
ensemble de contraintes exprimées sous forme d’équations ou
d’inéquations linéaires.

Pr. Bakrim 2023/2024

• La programmation linéaire est un outil puissant de la recherche
opérationnelle. Il permet de modéliser et de résoudre un grand
nombre de problème d’optimisation.
• On peut distinguer entre la programmation linéaire en nombre réelle
et celle en nombre entiers.
• La résolution d’un problème de programmation linéaire en nombres
entiers est plus compliquée qu’un problème en nombre réels.
• Il existe de nombreuses méthodes permettant de résoudre un
problème d’optimisation linéaire ( méthode graphique, simplex,...)

Pr. Bakrim 2023/2024

• La programmation linéaire est appliquée dans divers domaines :
• L’industrie
• L’agriculture
• Le domaine militaire
• Les banques
• Les chaînes commerciales
• Le transport,....

Pr. Bakrim 2023/2024

 Le principe de la résolution d’un
problème en recherche opérationnelle

Prise de décision
Pr. Bakrim 2023/2024
 Introduction- formulation du PL
• Les hypothèses de la programmation linéaire sont :

1 - Proportionnalité et additivité (linéarité) : la contribution des

variables de décision à la fonction objectif et aux contraintes est
proportionnelle à leur valeur, ainsi, la contribution de chaque variable
est indépendante de la valeur des autres variables.

2 - Divisibilité : les variables prennent des valeurs fractionnaires.

3 - Certitude : chaque paramètre est connu précisément.

Pr. Bakrim 2023/2024

Introduction- formulation du PL

Fonction objectif

Les variables
de décision
Contraintes de
positivité

Contraintes
m contraintes linèaires

équations/inéquations

Contraintes de
positivité

Pr. Bakrim 2023/2024

 Introduction- formulation du PL

• Les étapes à suivre pour pouvoir construire le modèle d’un

programme linéaire :
1-Comprendre le problème ;

2-Identifier les variables de décision ;

3-Formuler les contraintes du problème et les exprimer par un système

d’équations ou d’inéquations linéaires ;

4-Identifier l’objectif (à maximiser ou à minimiser)

Pr. Bakrim 2023/2024
 UNE PROBLEMATIQEU ( SOUS FORME D’UN TEXTE)

Etape 1:A lire attentivement

L’objectif
(la fonction objective) Les contraintes
MAX / MIN
Etape 2: Traduction /
modélisation

Contraintes:
Obj: equation
inégalités

Un système d’équations: PL à
résoudre

Outils de la
R.O
Pr. Bakrim 2023/2024
 Introduction- formulation du PL
• Exemple1: Considérons l’entreprise « XX » ayant les données
suivantes, modéliser la problématique de l’entreprise sous
forme d’un PL, sachant que:
• Le cout total des charges < 200.000 DH

Gamme des produits P1 P2 P3 P4

Quantité produite Y1 9500 Y3 Y4
Prix de vente (unitaire) 100 DH 85 DH 110 DH 180 DH

Facteurs de production Matières premières Travail Energie

Quantité utilisée X1 X2 X3
Cout unitaire 65 DH 70 DH 50 DH
Pr. Bakrim 2023/2024
 Introduction- formulation du PL
• Choix de variables de décision :
Y1 est la quantité du produit P1 fabriqué.
Y2 est la quantité du produit P2 fabriqué.
Y3 est la quantité du produit P3 fabriqué.
Y4 est la quantité du produit P4 fabriqué.
Gamme des produits P1 P2 P3 P4
Quantité produite Y1 9500 Y3 Y4
Prix de vente (unitaire) 100 DH 85 DH 110 DH 180 DH

• Choix de la fonction objectif à maximiser :

• l’objectif est de maximiser le profit de l’entreprise lors de la vente des produits.
• Donc, de maximiser la fonction suivante :
z = 100 Y1 + 85 Y2 + 110 Y3 + 180 Y4
Pr. Bakrim 2023/2024
 Introduction- formulation du PL

• Détermination des contraintes :

65 X1 + 70 X2 + 50 X3 < 200.000,
Y2=9500,
X1>0, X2>0, X3>0,
Y1>0, Y2>0, Y3>0, Y4>0,

Facteurs de production Matières premières Travail Energie

Quantité utilisée X1 X2 X3
Cout unitaire 65 DH 70 DH 50 DH

Pr. Bakrim 2023/2024

 Introduction- formulation du PL
• Exemple 2: dépenses et budget quotidien de l’étudiant

Pr. Bakrim 2023/2024

• Exemple 3: Mr X se demande comment gérer
au mieux ses dépenses alimentaires tout en
respectant ses besoins quotidiens en Energie
(2000 kcal), protéines (55g) et calcium (800
mg). Il sélectionne six produits qui semblent
être des sources nutritionnelles. Maintenant,
Mr X se demande comment composer ses
menus? Il décide donc d’imposer les limites
suivantes sur le nombre de services par jour
pour chacun des aliments:
• Céréales: au plus 4 services par jour,
• Poulet : au plus 3 services par jour,
• Œufs : au plus 2 services par jour,
• Lait entier : au plus 8 services par jour,
• Tarte aux pommes : au plus 2 services par jour,
• Poissons et haricots : au plus 2 services par
jour.
Pr. Bakrim 2023/2024
 Forme canonique d’un programme
linéaire
• Définition: Un programme linéaire est sous forme canonique
lorsque toutes ses contraintes sont des inégalités et toutes
ses variables sont positives.
• On appelle problème d’optimisation linéaire sous forme
canonique un problème de la forme :

Pr. Bakrim 2023/2024

 Forme standard d’un programme
linéaire
• Définition: Un programme linéaire est sous forme
standard lorsque toutes ses contraintes sont des
égalités et toutes ses variables sont positives.
• On appelle problème d’optimisation linéaire sous
forme standard un problème de la forme :

Pr. Bakrim 2023/2024

REMARQUE

• La forme canonique avec des contraintes d’inégalités s’utilise dans

la représentation graphique, et la forme standard avec des
contraintes d’égalité s’utilise dans la résolution algébrique.

• Passer d’une forme canonique à une forme standard !!!!!!!

Pr. Bakrim 2023/2024

 Les règles de transformation
• La fonction objectif:
Pour minimiser z, il suffit de maximiser −z et de changer
le signe de la fonction. Ainsi: min z = - max -z
• Les contraintes:

• Les contraintes de positivité: Tout nombre réel peut

être écrit comme la différence de deux nombres non
négatifs. Pr. Bakrim 2023/2024
 Les règles de transformation
• Pour passer d’une forme canonique à une forme standard, on ajoute les
variables d’écart dans chaque contrainte d’inégalité.
• Les écarts sont considérés par la suite dans l’ensemble des variables du PL
comme étant des inconnus, qu’il faut déterminer lors de la résolution du
système.
• NB: il faut obligatoirement ajouter ces variables-écarts dans la fonction objectif,
en leurs associant des coefficients nuls. (surtout lors de l’application des
méthodes de résolution)

Pr. Bakrim 2023/2024

Les règles de transformation

Pr. Bakrim 2023/2024

 Exemples d’application

Donnez le PL équivalent:

Pr. Bakrim 2023/2024

 Exemples d’application

Donnez le PL équivalent

Pr. Bakrim 2023/2024

EXERCICE D’APPLICATION
• Un patient consulte son médecin. Ce dernier
l’examine et l’informe qu’il souffre d’une carence en
deux vitamines, la vitamine A et la vitamine D. Le
médecin lui conseille de consommer régulièrement les
deux vitamines pendant un certain temps.
• Il lui prescrit le tonique X et le tonique Y, qui
contiennent de la vitamine A et D dans certaines
proportions. Il lui conseille également de consommer
au moins 40 unités de vitamine A et 50 unités de
vitamine D par jour.
• Le cout des toniques X et Y et la proportion de
vitamines A et D présentes dans X et Y sont indiqués
dans le tableau ci-dessous.

Pr. Bakrim 2023/2024

CHAPITRE 2: La résolution
graphique

Pr. Bakrim 2023/2024

 Introduction

• La résolution graphique d’un Programme Linéaire consiste à:

- Retrouver la solution du programme graphiquement.
- Tracer sur le plan cartésien (x,y) toutes les contraintes graphiquement,
ce qui donne ,dans le cas d’un PL, des droites d’équation: y=ax+b, puis
de déterminer la solution optimale du problème

• Cette méthode est généralement utilisée seulement dans le cas ou on a

que deux variables de décisions (x1, x2) ( pour plus que deux
dimensions la représentation graphique sur un repère de trois axes
devient compliquée).
Pr. Bakrim 2023/2024
 Détermination des solutions
réalisable
• La solution réalisable= la solution vérifiée par toutes les contraintes
• Le domaine réalisable= l’ensemble de toutes les solutions réalisables
• La solution optimale= la solution réalisable et qui vérifie la fonction
objectif aussi (max ou min)

• Les étapes:
• 1. Représentation des Droites des Contraintes.
• 2. Détermination du domaine réalisable.

Pr. Bakrim 2023/2024

 Détermination de la solution
optimale
• Représentation des Droites des Contraintes.
• Détermination du domaine réalisable.
• Représentation de la Droite de la Fonction Economique.
• Détermination de la solution optimale.

• Il existe deux méthodes pour déterminer la solution optimale à

savoir:
• La méthode des droites parallèles
• La méthode d’énumération des sommets

Pr. Bakrim 2023/2024

 Détermination de la solution
optimale
• Exemple 1:

Pr. Bakrim 2023/2024

 Détermination de la solution
optimale
• Exemple 2:

Pr. Bakrim 2023/2024

 La méthode des droites paralléles

• Tracer la droite (M) de la fonction objectif. Elle passe par l’origine.

• Déterminer la droite parallèle à (M) la plus éloignée de l’origine du
repère et qui coupe le domaine réalisable en un point au moins. En ce
point la fonction objectif atteint son maximum.
• Déterminer la droite parallèle à (M) la plus voisine de l’origine du
repère et qui coupe le domaine réalisable en un point au moins. En ce
point la fonction objectif atteint son minimum.

Pr. Bakrim 2023/2024

 La méthode d’énumération des sommets

• Déterminer tous les sommets du domaine réalisable.

• Calculer la valeur de z en chacun de ces sommets.
• Comparer les valeurs obtenues pour obtenir la combinaison optimale
(minimum ou maximum).

Pr. Bakrim 2023/2024

Exemples

Pr. Bakrim 2023/2024

Exemples

Pr. Bakrim 2023/2024

Exemples

Pr. Bakrim 2023/2024

 Exemples
• On considère le programme suivant:

Comme les variables de décision sont positives, le programme sera

résolut dans le quart du plan. (La surface grise)

Pr. Bakrim 2023/2024

 Exemples
• Etape 1: tracer la première contrainte

• On trace la droite de l’équation:

• X1 + 4X2= 2

• Puis, on prend un point quelconque du plan et on vérifie si ses

coordonnées vérifient l’inéquation. Si c’est le cas, le point se situe alors
dans le bon demi-plan. (par exemple, on prend le point d’origine O(0,0))

Pr. Bakrim 2023/2024

 Exemples
• Etape 2: tracer la contrainte suivante

• On trace la droite de l’équation:

• -X1 - X2= -1

Pr. Bakrim 2023/2024

 Exemples
• Etape 3:

• On trace la droite D3 d’équation 6x1 + x2 = 2. Considérons le point

origine, 6x1 + x2 = 6 × 0 + 0 = 0 < 2
• donc l’origine est solution de l’inéquation. On sélectionne le demi-plan
qui convient et on observe finalement
• que le systéme n’admet pas de solution (la partie grise est inexistante).
Pr. Bakrim 2023/2024
CHAPITRE 3: La méthode du Simplexe
 La méthode du simplexe

• La méthode graphique est utilisée pour résoudre des problèmes de

programmation linéaire avec deux variables.
• La méthode simplexe est développée par George Dantzig en 1947. Elle
permet de déterminer la solution optimale, si elle existe, d’un problème de
programmation linéaire à n variables.
• Le principe de la méthode est de transformer les contraintes qui sont des
inéquations en équations en ajoutant des variables d’écart. Ensuite on
transforme ce système d’équations linéaires jusqu’à trouver la solution
optimale.
• C’est une méthode itérative algébrique où l’on circule sur les sommets à
l’intérieur de la zone de solution jusqu’à l’obtention de la solution
optimale.

Pr. Bakrim 2023/2024

 Etapes de la méthode du simplexe

• Mise sous forme standard du problème.

• A partir de la forme standard du problème, on utilise :

- soit la résolution algébrique (méthode 1: la méthode des bases)

- soit la présentation en tableau. (méthode 2: la méthode tabulaire)

• Déterminer le domaine réalisable.

• Vérifier si cette solution est optimale.

Pr. Bakrim 2023/2024

Méthode du simplexe 1: la
méthode des bases
 L’ALGORITHME DU SIMPLEXE- SOLUTION
DE BASE
a) Ecrire la forme matricielle du PL.
b) Calculer n-m: Pour déterminer le nombre de variables hors base.
c) Déterminer les variables à mettre dans la base et les variables hors
base pour chaque itération.
d) Calculer l’inverse de chaque base (si elle existe).
e) Calculer la solution de base Xb.
f) Si alors la base concernée représente une
solution réalisable, et on dit une solution de base réalisable.
g) Calculer .
h) Si alors la solution de base réalisable est optimale.
Pr. Bakrim 2023/2024
Forme standard générale

Pr. Bakrim 2023/2024

Forme standard générale

Pr. Bakrim 2023/2024

PL sous forme matricielle

Pr. Bakrim 2023/2024

 Le principe: simplexe des bases

• Une solution de base est obtenue en posant n − m

variables égales à 0, et en résolvant pour les m variables
restantes, qui sont les variables de base (VB).
• Les n−m variables à 0 sont les variables hors base (VHB).
• Des choix différents de VHB donnent lieu à des différentes
solutions de base.

• Donc , le système devient de la forme suivante:

Pr. Bakrim 2023/2024

 PL sous forme matricielle

X N

C N

A N

Pr. Bakrim 2023/2024

 Le principe: simplexe des bases

❑A = [BN] , X= XB , C= CB cN
XN
❑Ce qui donne :
Z= C’ X= CB XB + CN XN
❑ AX= b B XB + NXN= b
XN= 0 alors: B XB = b
❑Une solution de base est tel que:
-1
❑ donc: XB= B b ( si B n’est pas inversible alors le
choix de cette
-1 base est inapproprié)
Pr. Bakrim 2023/2024
Règle

Pr. Bakrim 2023/2024

Exemple illustratif- méthode du simplexe

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3
x2 x4
x1 x2
x3 x4
x1 x2
x4 x3
x2 x1
x3 x4
x2 x1
x4 x3
x3 x1
x4 x2

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3 1 0
x2 x4 0 1
x1 x2
x3 x4
x1 x2
x4 x3
x2 x1
x3 x4
x2 x1
x4 x3
x3 x1
x4 x2

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3 1 0
x2 x4 0 1
x1 x2 2 0
x3 x4 1 1
x1 x2
x4 x3
x2 x1
x3 x4
x2 x1
x4 x3
x3 x1
x4 x2

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3 1 0
x2 x4 0 1
x1 x2 2 0
x3 x4 1 1
x1 x2 2 1
x4 x3 1 0
x2 x1
x3 x4
x2 x1
x4 x3
x3 x1
x4 x2

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3 1 0
x2 x4 0 1
x1 x2 2 0
x3 x4 1 1
x1 x2 2 1
x4 x3 1 0
x2 x1 1 0
x3 x4 2 1
x2 x1
x4 x3
x3 x1
x4 x2

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3 1 0
x2 x4 0 1
x1 x2 2 0
x3 x4 1 1
x1 x2 2 1
x4 x3 1 0
x2 x1 1 0
x3 x4 2 1
x2 x1 1 1
x4 x3 2 0
x3 x1
x4 x2

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur Xb conclusion
Base VHB VB
x1 x3 1 0
x2 x4 0 1
x1 x2 2 0
x3 x4 1 1
x1 x2 2 1
x4 x3 1 0
x2 x1 1 0
x3 x4 2 1
x2 x1 1 1
x4 x3 2 0
x3 x1 1 2
x4 x2 2 1

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur X b conclusion
Base VHB VB
x1 x3 1 0 1 0
x2 x4 0 1 0 1
x1 x2 2 0 1/2 0
x3 x4 1 1 -1/2 1
x1 x2 2 1 0 1
x4 x3 1 0 1 -2
x2 x1 1 0 1 0
x3 x4 2 1 -2 1
x2 x1 1 1 0 1/2
x4 x3 2 0 1 -1/2
x3 x1 1 2 -1/3 2/3
x4 x2 2 1 2/3 -1/3

Pr. Bakrim 2023/2024

 Exemple illustratif- méthode du simplexe
1 2 1 0 4 x1
A= , b= 5
, X= X2 , le nombre de VHB= n-m= 4-2=2
2 1 0 1
X3
x4
-1
Variables de hors Variables de base La matrice B La matrice B Le vecteur X conclusion
b
Base VHB VB
x1 B1= x3 1 0 1 0 x3 = 4 B1 est une SBR
x2 x4 0 1 0 1 x4 5
x1 B2= x2 2 0 1/2 0 2 B2 est une SBR
x3 x4 1 1 -1/2 1 3
x1 B3= x2 2 1 0 1 5 ----------------------
x4 x3 1 0 1 -2 -6
x2 B4= x1 1 0 1 0 4 ---------------------
x3 x4 2 1 -2 1 -3
x2 B5= x1 1 1 0 1/2 5/2 B5 est une SBR
x4 x3 2 0 1 -1/2 3/2
x3 B6= x1 1 2 -1/3 2/3 2 B6 est une SBR
x4 x2 2 1 2/3 -1/3 1

Pr. Bakrim 2023/2024

 Donc les Solutions de base
réalisables de ce PL sont:

X1 0
X= X2 = 0
X3 4
X4 5

X1 0
X2 2
X= =
X3 0
X4 3

X1 5/2
X= X2 = 0
X3 3/2
X4 0
X1
2
X= X2 = 1
X3 0
X4 0Pr. Bakrim 2023/2024
 Exemple illustratif- méthode du simplexe

• Nous avons vérifié que B1, B2, B5 et B6 sont des bases réalisables,
cherchons maintenant la solution optimale.

• Rappel: Une solution SBR est dite optimale si et seulement si:

avec:

Pr. Bakrim 2023/2024

Exemple illustratif- méthode du simplexe
CN CB N CONCLUSION

B1 EST LA
-1 -2 0 0 1 2 -1 -2 SOLUTION
2 1 OPTIMALE

-1 0 -2 0 1 1 0 1
2 0
---------------
-1 0 -2 0 1 0
2 1

-1 0 2 1
-2 0 --------------
1 0
2 0 -3/2 1/2
-2 0 -1 0 1 1
1 0
1 0
0 0 -1 -2 0 1

Pr. Bakrim 2023/2024

• CONCLUSION:

• La solution optimale de ce programme linéaire est:

Pr. Bakrim 2023/2024

Exemple

Pr. Bakrim 2023/2024

Exemple

Pr. Bakrim 2023/2024

Pr. Bakrim 2023/2024
Pr. Bakrim 2023/2024
Exemple d’application

Pr. Bakrim 2023/2024

Exemples

Pr. Bakrim 2023/2024

Exemples

Pr. Bakrim 2023/2024

Pr. Bakrim 2023/2024
La méthode du simplexe 2: La méthode du simplexe
tabulaire
 La méthode du tableau du pivot 1
L’algorithme du simplexe
Étape 3: calculer le tableau suivant:
Étape 1: Construction du tableau initial (chercher la limite de la valeur à
Toutes es Les donner à la variable entrante)
Étape 2:
variables constant Détermination de la
es Var Constantes
variable entrante: entrant /
Var de base Coef dans les C’est celle qui e coefficients
contraintes contribue mieux à
l’optimisation de la Var de
fonction objectif base
La fct objectif Coef du vecteur c

Étape 4: la variable sortante est celle qui donne le plus petit

rapport POSITIF
Étape 5: calculer le PIVOT: c’est
l’intersection de la colonne de Etape 6: construction du tableau pivot
la variable entrante et de la 1- on met la nouvelle variable entrante et sortante dans le tableau
ligne de la variable sortante initial
dans le tableau 1 2- on divise la ligne du pivot par le pivot
3- on met des 0 dans la colonne du pivot à l’aide du pivot de gauss
Pr. Bakrim 2023/2024
La méthode du tableau du pivot 1

Remarque:

Après l’étape 6 si les coefficients des

variables hors base dans la fonction
objectif sont tous positifs (resp.
négatifs) dans le cas de min z (resp max
z) on arrête l’algorithme , l’optimum est
atteint

Pr. Bakrim 2023/2024

La méthode du simplexe
tabulaire 2
 La méthode du simplexe tabulaire 2
• Le principe est de constituer le tableau de pivot comme dans la première méthode
mais selon la formule suivante:
Les nouvelles valeurs du tableau de pivot sont calculées par la formule suivante:

- pour les valeurs de la ligne de pivot on divise par le pivot.

- pour les autres cases:

la nouvelle valeur = l’ancienne valeur – Plv*Pcv/pivot

Avec: Plv= la projection sur la ligne de pivot.

Pcv= la projection sur la colonne de pivot.

Remarque:
- La VS est déterminée par la même règle.
- La VE correspond à la plus grande valeur de Cj-Zj ( c’est le profil marginal)Pr. Bakrim 2023/2024
 La méthode du simplexe tabulaire 2
Problème de
maximisation

• Le tableau de pivot est de la forme suivante:

Cj C1 C2 C3 C4
qtité X1 X2 e1 e2
Coef de VHB1 e1(VHB) b1 a11 a12 a13 a14

Coef de VHB2 e2(VHB) b2 a21 a22 a23 a24

Zj= coef a1j* coef de

VHB1 +coef a2j* coef de
VHB1

Ci - Zj Pr. Bakrim 2023/2024

 La méthode du simplexe tabulaire 2

• La méthode du simplexe tabulaire 2 est une méthode itérative, on

poursuit l’algorithme jusqu’à la réalisation de la condition d’arret
suivante:

• En cas de maximisation:

• En cas de minimisation:

( ici on change le signe car max Z est équivalent à –min(-Z))

Pr. Bakrim 2023/2024
La méthode du simplexe tabulaire 2

Pr. Bakrim 2023/2024

 La méthode du simplexe tabulaire 2

Exemple illustratif
• Soit le PL suivant:

• Itération 0:

Pr. Bakrim 2023/2024

 La méthode du simplexe tabulaire 2

• Itération 1: Exemple illustratif

Pr. Bakrim 2023/2024

 La méthode du simplexe tabulaire 2

Les variables artificielles

Cas des contraintes avec des inégalités d’inférieur:
• Dans ce cas, il faut introduire les variables artificielles Aj pour
respecter la contrainte de positivité des variables. (avec le
coefficient M dans la fonction objectif)
• M étant très grand qui tend vers plus l’infini

Pr. Bakrim 2023/2024

Le tableau final et la solution optimale: :

Pr. Bakrim 2023/2024

 Exercice d’application

• Exercice: Une entreprise fabrique deux biens X et Y, en utilisant trois

machines M1, M2 et M3. Les capacités de production de ces trois machines
sont respectivement de 20, 15 et 10 heures.
• Produire une unité de bien X nécessite une heure de la machine M2 et 2
heures de la machine M3. Alors que, produire une unité de bien Y nécessite
une heure de la machine M1, trois heures de la machine M2 et deux
heures de la machine M3. Le prix de vente unitaire est de 10 DH pour le
produit X et de 5 DH pour le produit Y.

• L’objectif du producteur est de maximiser son chiffre d’affaire.

• Donner le programme linéaire adéquat à cette problématique.

Pr. Bakrim 2023/2024

Chapitre 4: La dualité
 INTRODUCTION

• La dualité est un concept important en programmation linéaire.

• Elle permet de visualiser un problème sous un autre angle.
• Elle conduit à des résultats de grande portée théorique et
pratique.
• En effet, Tout programme linéaire admet un programme dual.
• A tout problème de maximisation peut être associé un problème
de minimisation et vice-versa.
• L’OBJECTIF: Le principe de la dualité permet d’analyser le
problème linéaire de point de vue économique. En effet,
dans ce chapitre nous ne présentons pas une nouvelle
méthode de résolution puisque nous allons faire toujours
référence aux méthodes des chapitres précédents.
Pr. Bakrim 2023/2024
• Le principe: est de transformer un PL de sa forme Primal à
la forme Duale ou vice versa, comme dans l’exemple
suivant:

• Donc, le problème de maximisation devient un problème de

minimisation.
• Les coefficients de la fonction économique deviennent les
seconds membres des contraintes et vice versa.
• Les variables de décisions du problème primal deviennent
des variables d’écarts dans le problème dual et les
variables d’écarts deviennent les variables de décisions.
• Les inégalités d’infériorité deviennent des inégalités de
supériorité et vice versa.
• La matrice A se change en sa transposée.
Pr. Bakrim 2023/2024
Exemple d’application

Pr. Bakrim 2023/2024

 Exemple

Solution:

Min W = 10 Y1 + 8 Y2
Max Z= 5X1 + 12X2 + 4X3
X1 + 2X2 + X3 = 10 Y1 + 2Y2 >= 5

2X1 – X2 + 3X3 <= 8 2Y1 – Y2 = 12

X1>= 0, X2 et X3 quiconque Y1 + 3Y2 = 4

Y2>= 0 Y1 quiconque

Pr. Bakrim 2023/2024

 L’objectif de la dualité
Exemple illustratif

• Une entreprise de menuiserie produit des tables , des chaises et des

armoires , les ressources de cette entreprises étant limitées par trois
contraintes . Le responsable de la production formule le problème
de la manière suivante :
x1: est le nombre de produit
P1 fabriqués

x2: est le nombre de produit

P2 fabriqués

x3: est le nombre de produit P3

fabriqués

Pr. Bakrim 2023/2024

 L’objectif de la dualité

Exemple illustratif

1 2 3 0 0 0
Cj
qtité X1 X2 X3 e1 e2 e3
VB
0 e1 100 1 2 2 1 0 0

0 e2 50 2 1 1 0 1 0

0 e3 60 1 3 2 0 0 1

Zj 0 0 0 0 0 0

Cj - Zj 1 2 3 0 0 0

Pr. Bakrim 2023/2024

 L’objectif de la dualité
Exemple illustratif
1 2 3 0 0 0
Cj
qtité X1 X2 X3 e1 e2 e3
VB
0 e1 40 0 -1 0 1 0 -1
0 e2 20 3/2 -1/2 0 0 0 -1/2
3 X3 30 1/2 3/2 1 0 0 1/2

Zj 3/2 9/2 3 0 0 3/2

Cj - Z j -1/2 -5/2 0 0 0 -3/2

La solution optimale donnée par le tableau ce dessus est la suivante :

X1*= 0 X2*= 0 X3*= 30 e1*= 40 e2*= 20 e3*= 0

Pr. Bakrim 2023/2024
 L’objectif de la dualité
Exemple illustratif
1 2 3 0 0 0
Cj
qtité X1 X2 X3 e1 e2 e3
VB
0 e1 40 0 -1 0 1 0 -1
0 e2 20 3/2 -1/2 0 0 0 -1/2
3 X3 30 1/2 3/2 1 0 0 1/2
Zj 3/2 9/2 3 0 0 3/2

Cj - Z j -1/2 -5/2 0 0 0 -3/2

La solution optimale donnée par le tableau ce dessus est la suivante :

X1*= 0 X2*= 0 X3*= 30 e1*= 40 e2*= 20 e3*= 0
L’interprétation économique:
e1: est l’écart entre la quantité de la matière première utilisée et la quantité disponible,
après l’optimisation e1= 40, donc il restera encore 40 KG de MP dans le stock après avoir
maximisé le chiffre d’affaire.
e2: à l’optimum, le producteur économisera 20h de l’utilisation des machines.
e3: à l’optimum, la capacité de production des machines sera à sa limite. Pr. Bakrim 2023/2024
 L’objectif de la dualité
Exemple illustratif
1 2 3 0 0 0
Cj
qtité X1 X2 X3 e1 e2 e3
VB
0 e1 40 0 -1 0 1 0 -1
0 e2 20 3/2 -1/2 0 0 0 -1/2
3 X3 30 1/2 3/2 1 0 0 1/2
Zj 3/2 9/2 3 0 0 3/2

Cj - Z j -1/2 -5/2 0 0 0 -3/2

La solution optimale donnée par le tableau ce dessus est la suivante :

X1*= 0 X2*= 0 X3*= 30 e1*= 40 e2*= 20 e3*= 0
L’interprétation économique:
C1-Z1 : une unité de production de plus de P1 impliquera une diminution de ½ du chiffre
d’affaire.
C4-Z4 : une unité supplémentaire de matière première utilisée dans la production
impliquera aucun n’impact sur la maximisation du CA.
C2-Z2 :une unité de production de plus de P2 impliquera une diminution de 5/2 du chiffre
Pr. Bakrim 2023/2024
d’affaire.
 L’objectif de la dualité
Exemple illustratif
• Le programme équivalent dual du problème est:

y1= est le cout d’une unité de MP

y2= est le cout d’une heure du travail
y3= est le cout de la capacité de production

Commentaire:

Maintenant dans cette version Duale, le producteur raisonne de point de vue

cout des ressources, en Primal, il cherchait à maximiser le chiffre d’affaires Z et
de trouver la combinaison optimale de la production des biens P1, P2 et P3 qui le
permettra.

En version Duale, le problème est traité d’un autre point de vue, le producteur
cherche la combinaison optimale de la production qui permet de minimiser les
couts de production Z’. Pr. Bakrim 2023/2024
 L’objectif de la dualité
Exemple illustratif
• La solution du Dual:

T.A.F: Résoudre cet exercice avec la méthode du simplexe et vérifier que la solution
optimale est: X1*= 1/2 X2*= 5/2 X3*= 0 e1*= 0
e2*= 0 e3*= 3/2-3/2
Pr. Bakrim 2023/2024
 Solution du primal et le dual

Relation entre les deux solutions :

• Si le primal et le dual ont deux solutions réalisables, alors ils

ont des solutions optimales et: z*= Max(P) = Min(D).

• Si l’un d’entre eux a une solution non bornée, l’autre n’a pas
de solution réalisable.

Pr. Bakrim 2023/2024

 L’objectif de la dualité
Analyse de sensibilité

• I- Dans une première partie , on présentera une

analyse de sensibilité de la solution optimale aux
variations des coefficients des variables de
décisions dans la fonction objectif .

• II- Dans une seconde partie, on effectuera une

analyse de la sensibilité de la solution optimale due
aux variations dans les seconds membres des
contraintes.

Pr. Bakrim 2023/2024

 L’objectif de la dualité
Analyse de sensibilité sur les coefficients dans la fonction objectif Z

Pr. Bakrim 2023/2024

 L’objectif de la dualité
Analyse de sensibilité sur les coefficients dans la fonction objectif Z
1 2 3 + Δ 0 0 0
Cj
qtité X1 X2 X3 e1 e2 e3
VB
0 e1 40 0 -1 0 1 0 -1
0 e2 20 3/2 -1/2 0 0 0 -1/2
3+Δ X3 30 1/2 3/2 1 0 0 1/2
Zj 3/2 + Δ/2 9/2 + 3Δ/2 3+Δ 0 0 3/2 + Δ/2

Cj - Z j -1/2- Δ/2 -5/2- 3Δ/2 0 0 0 -3/2 - Δ/2

La solution reste optimale suite à ce changement si et seulement si:

-1/2- Δ/2> 0, -5/2- 3Δ/2> 0, -3/2 - Δ/2>0
c.a.d: Δ <1 , Δ < 5/3, Δ <3 donc: la solution reste optimale pour tout
changement au niveau du prix unitaire de X3 tant que le changement ne
dépasse pas 1
Pr. Bakrim 2023/2024
 L’objectif de la dualité
Analyse de sensibilité sur les seconds membres des contraintes
1 2 3 0 0 0
Cj
qtité X1 X2 X3 e1 e2 e3
VB
0 e1 40 + 1*Δ 0 -1 0 1 0 -1
0 e2 20 + 0*Δ 3/2 -1/2 0 0 0 -1/2
3 X3 30 + 0*Δ 1/2 3/2 1 0 0 1/2
Zj 3/2 9/2 3 0 0 3/2

Cj - Z j -1/2 -5/2 0 0 0 -3/2

- Soit un changement de contrainte 1 de 100 à 100 + Δ. (c’est la constante de

la première contrainte dans le PL)
LA REGLE: Le changement au niveau des constantes, dans le tableau optimal,
est calculés en fonction des coefficients de e1 (la variable écart
correspondante à la première contrainte), comme c’est illustré sur le tableau.
Pr. Bakrim 2023/2024
Merci pour votre attention

Et

Bon courage
Exercices d’application