FSJES AGDAL- L.

RECHERCHE
OPERATIONNELLE
Pr. HABACHI MOHAMED1
1 Faculté des sciences juridiques, économique et sociales Agdal

Département Sciences de Gestion

Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Plan du chapitre préliminaire

Introduction
1. Étapes du développement de la recherche
opérationnelle.
2. Relation entre le gestionnaire et le spécialiste de la
RO
3. Outils et techniques de la RO
4. Applications de la recherche opérationnelle

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
La recherche opérationnelle est une discipline
relativement nouvelle. Les contenus et les frontières
de la RO ne sont pas encore fixés. Par conséquent, il
est difficile de donner une définition formelle du
terme "recherche opérationnelle".
La RO commence lorsque des techniques
mathématiques et quantitatives sont utilisées pour
justifier la décision à prendre.
L'activité principale d'un manager est la prise de
décision..

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 Introduction
Par exemple,

• la planification d'un réseau de transport public dans une ville

ayant sa propre disposition d'usines, d'immeubles résidentiels
• la recherche d'une combinaison de produits appropriée lorsqu'il
existe un grand nombre de produits ayant des contributions aux
bénéfices et des exigences de production différentes, etc. de
production, etc.

Les outils de la recherche opérationnelle ne proviennent pas d'une

seule discipline. La recherche opérationnelle utilise des outils
provenant de différentes disciplines telles que les mathématiques,
les statistiques, l'économie, la psychologie, l'ingénierie, etc. et
combine ces outils pour créer un nouvel ensemble de connaissances
pour la prise de décision.
 FSJES AGDAL- L.E

Introduction
La R.O. est devenue une discipline professionnelle qui traite de
l'application de méthodes scientifiques pour la prise de décision, et
en particulier pour l'allocation de ressources rares. L'objectif
principal de la R.O. est de fournir une base rationnelle pour la prise
de décisions en l'absence d'informations complètes, car les systèmes
composés d'humains, de machines et de procédures peuvent ne pas
disposer d'informations complètes.
Les spécialistes de la R.O. sont impliqués dans trois aspects
classiques de la science, qui sont les suivants :
i)Déterminer le comportement des systèmes.
ii)Analyser le comportement des systèmes en développant des
modèles appropriés.
iii)Prédire le comportement futur à l'aide de ces modèles.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
L'accent mis sur l'analyse des opérations dans leur ensemble
distingue l'O.R. des autres activités de recherche et d'ingénierie.
L'O.R. est une discipline interdisciplinaire qui a fourni des solutions
aux problèmes des opérations militaires pendant la Seconde Guerre
mondiale, et qui a également connu le succès dans d'autres
opérations. Aujourd'hui, les applications commerciales sont
principalement concernées par l'analyse R.O. pour les actions
alternatives possibles. Le commerce et l'industrie ont bénéficié de
l'analyse des risques opérationnels dans les domaines de l'inventaire,
des politiques de réapprovisionnement, de la localisation et de la
taille optimales des entrepôts, politiques publicitaires, etc.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
Définir le R.O. est une tâche difficile. Les définitions soulignées par
les différents experts et sociétés sur le sujet nous permettent de
savoir ce qu'est la R.O. et ce qu'elle fait.
Elles sont les suivantes :
(1)La recherche opérationnelle est l'attaque de la science moderne
sur les problèmes complexes qui se posent 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, le gouvernement et la
défense. Son approche distinctive consiste à développer un modèle
scientifique du système, incorporant des mesures de facteurs tels que
le changement et le risque, avec lequel on peut prédire et comparer
les résultats de décisions, stratégies ou contrôles alternatifs.
L'objectif est d'aider la direction à déterminer scientifiquement sa
politique et ses actions.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
(2)Randy Robinson souligne que la recherche opérationnelle est
l'application de méthodes scientifiques pour améliorer l'efficacité des
opérations, des décisions et de la gestion. Par des moyens tels que
l'analyse de données, la création de modèles mathématiques et la
proposition d'approches innovantes, les professionnels de la
recherche opérationnelle développent des informations scientifiques
qui donnent un aperçu et guident la prise de décision. Ils
développent également des logiciels, des systèmes, des services et
des produits connexes.
(3)Morse et Kimball décrit l'O.R. comme "une méthode scientifique
permettant de fournir aux départements exécutifs une base
quantitative pour les décisions concernant les opérations sous leur
contrôle".

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
(4)Saaty considère que : "La R.O. est l'art de donner de bonnes
réponses à des problèmes qui, autrement, auraient de pires
réponses".
(5)Miller et Starr affirment que "l'O.R. est une théorie appliquée de
la décision, qui utilise tous les moyens scientifiques, mathématiques
ou logiques pour tenter de faire face aux problèmes auxquels est
confronté l'exécutif, lorsqu'il essaie d'atteindre une rationalité
complète dans le traitement de son problème de décision".
(6)Pocock souligne que l'O.R. est une science appliquée. Il affirme
que "la R.O. est une méthodologie scientifique (analytique,
mathématique et quantitative) qui, en évaluant l'implication globale
de diverses alternatives d'action dans un système de gestion, fournit
une meilleure base pour les décisions de gestion".

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

1.Étapes du développement de la recherche opérationnelle.

Les étapes du développement de la R.O. sont également connues
sous le nom de phases et processus de la R.O., qui comporte six
étapes importantes. Ces six étapes sont organisées dans l'ordre
suivant :

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

(1)Cette étape comprend différentes activités : conférences, visites

de sites, recherches, observations, etc. Ces activités fournissent des
informations suffisantes aux spécialistes des R.O. pour formuler le
problème.
(2)Cette Dans cette étape, en plus de la définition du problème, les
objectifs, les utilisations et les limites de l'étude de la R.O. du
problème sont également définis. Les résultats de cette étape sont
une compréhension claire du besoin d'une solution et de sa nature.
(3)Cette étape permet de développer un modèle ; un modèle est une
représentation d'une situation abstraite ou réelle. Les modèles sont
essentiellement des modèles mathématiques, qui décrivent des
systèmes, des processus sous forme d'équations, de formules ou de
relations. Les différentes activités de cette étape sont la définition
des variables, la formulation des équations, etc. Le modèle est testé
sur le terrain sous différentes contraintes environnementales et
modifié afin de fonctionner. Parfois, le modèle est modifié pour que
la direction soit satisfaite des résultats.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

(4)Un modèle fonctionne correctement lorsqu'il y a une entrée de données

appropriée. Par conséquent, la sélection des données d'entrée appropriées
est une étape importante de l'étape ou du processus de développement du
RO. Les activités de cette étape comprennent l'analyse des données
internes/externes, l'analyse des faits, la collecte d'opinions et l'utilisation de
banques de données informatiques. L'objectif de cette étape est de fournir
des données d'entrée suffisantes pour exploiter et tester le modèle
développé à l'étape III.
(5)Cette étape consiste à obtenir une solution à l'aide du modèle et des
données d'entrée. Cette solution n'est pas mise en œuvre immédiatement,
mais elle est utilisée pour tester le modèle et déterminer s'il y a des limites.
(6) À cette étape, la solution obtenue à l'étape précédente est mise en
œuvre.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

2. Relation entre le gestionnaire et le spécialiste de la RO

La principale responsabilité du manager est la prise de décision. Le
rôle du spécialiste en R.O. est d'aider le gestionnaire à prendre de
meilleures décisions. La figure 1-1 explique la relation entre le
spécialiste des relations publiques et le gestionnaire/décideur.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

LES ÉTAPES DE LA RECONNAISSANCE DES PROBLÈMES, PARTICIPATION : SPECIALISTE R.O. ou

FORMULATION ET SOLUTION MANAGER
Reconnaître à partir de symptômes organisationnels Manager
symptômes qu'un problème existe

Décider quelles sont les variables impliquées ; énoncer le SPECIALISTE R.O. ou Manager
problème des relations quantitatives entre les variables

Rechercher des méthodes pour résoudre les problèmes SPECIALISTE R.O.

énoncés ci-dessus ; déterminer les outils quantitatifs
appropriés à utiliser

Tenter de trouver des solutions aux problèmes ; trouver SPECIALISTE R.O.

diverses solutions ; énoncer les hypothèses sous-jacentes
à ces solutions ; tester solutions alternatives.

Déterminer quelle solution est la plus efficace en raison SPECIALISTE R.O. ou Manager
des contraintes pratiques au sein de l'organisation ;
décidez de ce que la solution signifie pour l'organisation.

Choisir la solution à utiliser Manager

Vendez" la décision aux responsables opérationnels ; SPECIALISTE R.O. ou Manager

obtenez leur compréhension et leur coopération.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

[Link] et techniques de la RO
La recherche opérationnelle utilise tous les outils ou techniques
appropriés disponibles. Les outils/techniques les plus fréquemment
utilisés sont les procédures mathématiques, l'analyse des coûts, le
calcul électronique. Cependant, les chercheurs en recherche
opérationnelle accordent une importance particulière au
développement et à l'utilisation de techniques telles que la
programmation linéaire, la théorie des jeux, la théorie de la décision,
la théorie des files d'attente, les modèles d'inventaire et la
simulation. Outre les techniques susmentionnées, d'autres outils
courants sont la programmation non linéaire, la programmation en
nombres entiers, la programmation dynamique, la théorie des
séquences, le processus de Markov, l'ordonnancement en réseau
(PERT/CPM), le modèle symbolique, la théorie de l'information et la
théorie de la valeur. Il existe également de nombreux autres
outils/techniques de recherche opérationnelle. Les explications
succinctes de certaines de ces techniques/outils sont les suivantes :
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Programmation linéaire :
Il s'agit d'une technique d'optimisation sous contrainte, qui permet
d'optimiser un certain critère dans le cadre de certaines contraintes.
Dans la programmation linéaire, la fonction objectif (profit, perte ou
retour sur investissement) et les contraintes sont linéaires. Il existe
différentes méthodes pour résoudre la programmation linéaire.
La théorie des jeux :
Elle est utilisée pour prendre des décisions dans des situations
conflictuelles où il y a un ou plusieurs joueurs/opposants. Dans ce
cas, les motivations des joueurs sont dichotomisées. Le succès d'un
joueur tend à se faire au détriment des autres joueurs, ce qui les met
en conflit.
La théorie de la décision :
La théorie de la décision s'intéresse à la prise de décisions dans des
conditions de certitude totale sur les résultats futurs et dans des
conditions telles que nous pouvons établir une certaine probabilité
sur ce qui se passera dans le futur.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Théorie des files d'attente :

Elle est utilisée dans les situations où une file d'attente est formée
(par exemple, des clients qui attendent d'être servis, des avions qui
attendent d'atterrir, des tâches qui attendent d'être traitées dans un
système informatique, etc.) L'objectif est ici de minimiser le coût de
l'attente sans augmenter le coût du service.
Modèles d'inventaire :
Le modèle d'inventaire prend des décisions qui minimisent le coût
total de l'inventaire. Ce modèle réduit avec succès le coût total de
l'achat, du transport et de la rupture de stock.
Simulation :
La simulation est une procédure qui étudie un problème en créant un
modèle du processus impliqué dans le problème, puis en essayant de
déterminer la meilleure solution par une série d'essais et d'erreurs
organisés. Parfois, cette procédure est difficile et prend du temps. La
simulation est utilisée lorsque l'expérimentation réelle n'est pas
réalisable ou la solution du modèle n'est pas possible.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Programmation non linéaire :

Elle est utilisée lorsque la fonction objectif et les contraintes ne sont pas
de nature linéaire.
Programmation dynamique :
La programmation dynamique est une méthode d'analyse des processus
de décision à plusieurs étapes. Dans cette méthode, chaque décision
élémentaire dépend des décisions précédentes ainsi que de facteurs
externes.
Programmation en nombres entiers :
Si une ou plusieurs variables du problème ne prennent que des valeurs
entières, la méthode de programmation dynamique est utilisée. Par
exemple, le nombre de moteurs dans une organisation, le nombre de
passagers dans un avion, le nombre de générateurs dans une centrale
électrique, etc.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Processus de Markov :
Le processus de Markov permet de prédire les changements dans le
temps ; les informations sur le comportement d'un système sont
connues. Il est utilisé dans la prise de décision dans des situations où les
différents états sont définis. La probabilité de passer d'un état à un autre
est connue et dépend de l'état actuel et est indépendante de la façon
dont nous sommes arrivés à cet état particulier.
Ordonnancement du réseau :
Cette technique est largement utilisée pour planifier, programmer et
surveiller de grands projets (par exemple, l'installation de systèmes
informatiques, la conception de la R & D, la construction, la
maintenance, etc.). Son objectif est de minimiser les problèmes (tels
que les retards, les interruptions, les goulots d'étranglement de la
production, etc, en identifiant les facteurs critiques.
Les différentes activités et leurs relations dans le projet sont
représentées de manière schématique à l'aide de réseaux et de flèches,
ce qui permet d'identifier les activités et les chemins critiques.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Il existe deux principaux types de techniques dans l'ordonnancement en

réseau :
La technique d'évaluation et d'examen des programmes (PERT) - est
utilisée lorsque le temps des activités n'est pas connu avec
précision/seulement une estimation probabiliste du temps est
disponible.
La méthode du chemin critique (CPM) - est utilisée lorsque le temps
des activités est connu avec précision.
La théorie de l'information :
Ce processus analytique est transféré du domaine des communications
électriques au domaine de l'informatique. L'objectif de cette théorie est
d'évaluer l'efficacité de la circulation de l'information dans un système
donné. Elle est utilisée principalement dans les réseaux de
communication mais a également une influence indirecte dans la
simulation de l'examen de la structure organisationnelle des entreprises
en vue d'améliorer le flux d'informations.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

[Link] applications de la recherche opérationnelle.

Aujourd'hui, presque tous les domaines de l'entreprise et du
gouvernement utilisent les avantages de la recherche opérationnelle. Il
existe une multitude d'applications de la recherche opérationnelle. Bien
qu'il ne soit pas possible de couvrir toutes les applications de la R.O. en
bref. Voici un ensemble abrégé d'applications typiques de la recherche
opérationnelle pour montrer à quel point ces techniques sont utilisées
aujourd'hui :
(1)Comptabilité :
•Affectation efficace des équipes d'audit
•Analyse de la politique de crédit
•Planification des flux de trésorerie
•Élaboration de coûts standards
•Établissement des coûts des sous-produits
•Planification de la stratégie des comptes en souffrance

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

(2)Construction :
• Programmation, suivi et contrôle du projet
• Détermination de la main-d'œuvre appropriée
• Déploiement de la main-d'œuvre
• Affectation des ressources aux projets
(3)Planification des installations :
• Décision concernant l'emplacement et la taille de l'usine.
• Estimation du nombre d'installations nécessaires.
• Planification des hôpitaux.
• Conception de systèmes logistiques internationaux.
• Chargement et déchargement des transports.
• Décision concernant l'emplacement de l'entrepôt.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

(4) Finance :
• Construire des modèles de gestion de trésorerie
• Affectation du capital entre diverses alternatives
• Construction de modèles de planification financière
• Analyse des investissements
• Analyse de portefeuille
• Élaboration de la politique de dividendes
(5) Fabrication :
• Contrôle des stocks
• Projection du bilan marketing
• Ordonnancement de la production
• Lissage de la production

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

(6)Marketing:
• Allocation du budget publicitaire
• Calendrier de lancement du produit
• Sélection de la gamme de produits
• Choix de l'emballage le plus efficace
(7)Comportement organisationnel / Ressources humaines :
• Planification du personnel
• Recrutement des employés
• Équilibrage des compétences
• Programmation des programmes de formation
• Conception d'une structure organisationnelle plus efficace

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

(8)Achats :
• Achat optimal
• Réapprovisionnement optimal
• Transfert de matériel
(9)Recherche et développement :
• Contrôle des projets de R & D
• Allocation du budget de R & D
• Planification de l'introduction du produit

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Plan du cours

1. Chapitre préliminaire
2. Chapitre 1: La programmation linéaire.
3. Chapitre 2: La modélisation en gestion.
4. Chapitre 4: Théorie des graphes et l’
ordonnancement .

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Chapitre 1
La programmation linéaire

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Objectifs

- Résoudre graphiquement un problème.

- Comprendre les bases de la méthode du simplexe.
- Expliquer les calculs du simplexe.
- Décrire les différentes solutions de la méthode du simplexe.
- Comprendre le dual du Problème en programmation linéaire.
- Formuler le dual du problème.
- Résoudre le dual du problème.
- Comprendre les propriétés d'un dual du problème.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La programmation linéaire
résolution graphique

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

plan
- Introduction à la programmation linéaire.
- Formulation du problème de programmation linéaire.
- Formulation avec différents types de contraintes.
- Analyse graphique de la programmation linéaire.
- Solution graphique de la programmation linéaire.
- Solutions optimales multiples.
- Solution non bornée.
- Solution infaisable.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
La programmation linéaire est une technique qui peut être appliquée à
une variété de problèmes de gestion, à savoir la publicité, la
distribution, l'investissement, la production, les opérations de raffinage
et l'analyse du transport. La méthode de programmation linéaire est
applicable aux problèmes caractérisés par la présence de variables de
décision.
La fonction objectif et les contraintes peuvent être exprimées comme
des fonctions linéaires des variables de décision. Les variables de
décision représentent des quantités qui sont, dans un certain sens, des
entrées contrôlables du système modélisé. Une fonction objectif
représente un critère objectif principal ou un but qui mesure
l'efficacité du système, comme la maximisation des profits ou de la
productivité, ou la minimisation des coûts ou de la consommation.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
La disponibilité des ressources (hommes, matériaux, machines ou
temps) est limitée pour un système ou une activité donnée. Cela
représente des contraintes de gestion. En programmation linéaire, ces
contraintes sont exprimées sous forme d'équations linéaires impliquant
les variables de décision.
Résoudre un problème de programmation linéaire signifie déterminer
les valeurs réelles des variables de décision qui optimisent la
fonction objectif sous réserve de la limitation imposée par les
contraintes.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction
La principale caractéristique importante du modèle de programmation
linéaire est la présence de la linéarité dans le problème. L'utilisation
du modèle de programmation linéaire apparaît dans une grande variété
d'applications. Certains modèles peuvent ne pas être strictement
linéaires, mais peuvent être rendus linéaires en appliquant des
transformations mathématiques appropriées.

D'autres applications ne sont pas du tout linéaires, mais peuvent être

efficacement approchées par des modèles linéaires.

La facilité avec laquelle les modèles de programmation linéaire peuvent

généralement être résolus en fait un moyen attrayant de traiter des
modèles non linéaires autrement difficiles à résoudre.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Formulation du problème de programmation linéaire.

La formulation du problème de programmation linéaire est illustrée par

un problème de gamme de produits.
Le problème de la gamme de produits se pose dans une industrie où il
est possible de fabriquer une variété de produits.
Chaque produit a une certaine marge de profit par unité, et utilise un
une source commune dont la disponibilité est limitée.
Dans ce cas, la technique de programmation linéaire identifie la
combinaison de produits qui maximisera les profits, sous réserve de la
disponibilité de ressources limitées.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Formulation du problème de programmation linéaire.

Exemple 1:
Supposons qu'une entreprise fabrique deux types de produits, 𝑃1 et 𝑃2 .
Les bénéfices par unité de ces deux produits sont respectivement de 30
et 40 dhs. Ces deux produits doivent être traités dans trois types de
machines. Le tableau suivant indique les heures de machine disponibles
par jour et le temps nécessaire à chaque machine pour produire une
unité de P1 et P2. Formulez le problème sous la forme d'un modèle de
programmation linéaire..
Profit par 𝑃1 𝑃2 Disponibilité totale de la
unité (30dhs) (40dhs) machine heures/jour
Machine 1 3 2 600
Machine 2 3 5 800
Machine 3 5 6 1100
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Formulation du problème de programmation linéaire.

Solution:
La procédure de formulation du problème de programmation linéaire
est la suivante :
Introduire la variable de décision comme suit :
- La fonction objectif:
Soit 𝑥1 et 𝑥2 respectivement les quantités des produits 𝑃1 et 𝑃2 . Afin de
maximiser les profits, nous définissant la fonction objectif comme suit:
𝑓 𝑥1 ,𝑥2 = 30𝑥1 + 40𝑥2
- Les contraintes
Puisqu'une unité de 𝑃1 nécessite 3 heures de traitement dans la machine
1 alors qu’une unité de 𝑃2 nécessite 2 heures et le nombre maximale
d’heure de travail de la machine 1 est 600h/j Ainsi, la première
contrainte peut être exprimée comme suit:
3𝑥1 + 2𝑥2 ≤ 600

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Formulation du problème de programmation linéaire.

Solution:
Même raisonnement pour les deux machines (2 et 3). De ce fait, les
contraintes dictées par les deux machine peuvent être exprimées comme
suit:
Machine (2) : 3𝑥1 + 5𝑥2 ≤ 800
Machine (2) : 5𝑥1 + 6𝑥2 ≤ 1100
En plus de ce qui précède, il n'y a pas de production négative, ce qui
peut être représenté algébriquement de la manière suivante:
0 ≤ 𝑥1 et 0 ≤ 𝑥2
Ainsi, la formulation mathématique du problème du mix produit dans le
modèle de programmation linéaire est le suivant :

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Formulation du problème de programmation linéaire.

Maximiser 𝑓 𝑥1 ,𝑥2 = 30𝑥1 + 40𝑥2

Sous réserve
3𝑥1 + 2𝑥2 ≤ 600
3𝑥1 + 5𝑥2 ≤ 800
5𝑥1 + 6𝑥2 ≤ 1100
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Formulation avec différents types de contraintes

Les contraintes de l'exemple précédent 1 sont du type "inférieur ou égal
à". Dans cette section, nous allons examiner le problème de
programmation linéaire avec des contraintes différentes, qui est illustré
dans l'exemple 2 suivant:
Une entreprise possède deux minoteries, A et B, dont les capacités de
production de farine de haute, moyenne et basse qualité sont différentes.
L'entreprise a conclu un contrat pour fournir chaque mois à une
entreprise de la farine d'au moins 8, 12 et 24 quintaux de qualité
supérieure, moyenne et inférieure respectivement. Le fonctionnement
des moulins A et B coûte à l'entreprise respectivement 2000 et 1500 dhs
par jour.
En un jour, le moulin A produit 6, 2 et 4 quintaux de farine de haute,
moyenne et basse qualité, le moulin B produit 2, 4 et 12 quintaux de
farine de haute, moyenne et basse qualité respectivement. Combien de
jours par mois faut-il faire fonctionner chaque moulin pour satisfaire la
commande contractuelle de la manière la plus économique possible ?
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Formulation avec différents types de contraintes

Définissons 𝑥1 et 𝑥2 comme étant les jours de travail respectivement
des moulins A et B. Ici, l'objectif est de minimiser le coût des
production et de satisfaire la commande du contrat. Le problème de
programmation linéaire est donné par:

Minimiser 𝑓 𝑥1 ,𝑥2 = 2000𝑥1 + 1500𝑥2

Sous réserve
6𝑥1 + 2𝑥2 ≥ 8
2𝑥1 + 4𝑥2 ≥ 12
4𝑥1 + 12𝑥2 ≥ 24
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Analyse graphique de la programmation linéaire

Cette section montre comment un problème de programmation linéaire
à deux variables est résolu graphiquement.
Soit le problème de programmation linaire définit par l’exemple 1:

Maximiser 𝑓 𝑥1 ,𝑥2 = 30𝑥1 + 40𝑥2

Sous réserve
3𝑥1 + 2𝑥2 ≤ 600
3𝑥1 + 5𝑥2 ≤ 800
5𝑥1 + 6𝑥2 ≤ 1100
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Analyse graphique de la programmation linéaire

La résolution de ce problème consiste à définir dans une première étape
la zone faisables déterminer par les contraintes. De ce fait, il faut:
(1) A partir de la première contrainte 3𝑥1 + 2𝑥2 ≤ 600, tracer la droite
3𝑥1 + 2𝑥2 = 600 qui passe par les points (200, 0) et (0, 300). Cette
droite est représentée sur le graphique suivant par la ligne 1.
(2) A partir de la deuxième contrainte 3𝑥1 + 5𝑥2 ≤ 800 , tracer la
800
droite 3𝑥1 + 5𝑥2 = 800qui passe par les points ( , 0) et (0, 160).
3
Cette droite est représentée sur le graphique suivant par la ligne 2.
(3) A partir des premières contraintes 5𝑥1 + 6𝑥2 ≤ 1100 , tracer la
550
droite 5𝑥1 + 6𝑥2 = 1100qui passe par les points (220, 0) et (0, ).
3
Cette droite est représentée sur le graphique suivant par la ligne 3.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Analyse graphique de la programmation linéaire

Pour la première contrainte, il faut trouver le demi plan qui vérifier la
contrainte. Pour ce faire, on peut procéder de deux façons:
La première, prendre un point du demi plan pour décider de quel côté
de la ligne 3𝑥1 + 2𝑥2 = 600 se trouve le demi-plan représentant la
contrainte. La méthode la plus simple pour résoudre l'inégalité pour x2
est la suivante:
3𝑥1 ≤ 600-2𝑥2
pour le point fixe (0,0), la contrainte est vérifiée de ce fait les points des
demi-plan qui contient (0,0) vérifient la contrainte 1.
De même pour les deux autres contraintes, en utilise les relations
suivantes :
3𝑥1 ≤ 800 − 5𝑥2 , 5𝑥1 ≤ 1100 − 6𝑥2
Et en détermine, les demi-plan par un point fixe tel que (0,0), (1,1) ..etc.
La zone faisable est limité par les axes d’abscisses et des ordonnées
pour satisfaire la condition des 0 ≤ 𝑥1 et 0 ≤ 𝑥2 . L’analyse des
contraintes permet de déterminer la zone faisable grafiquement:
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Zone réalisable
350

300

250

200

150

100

50

0
-50 0 50 100 150 200 250
-50

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Analyse graphique de la programmation linéaire

Définitions:
Solution réalisable :
Toute valeur non négative de 𝑥1 , 𝑥2 qui est 0 ≤ 𝑥1 et 0 ≤ 𝑥2 est connue
comme solution réalisable du problème de programmation linéaire si
elle satisfait toutes les contraintes existantes.
Région Réalisable :
La collection de toutes les solutions réalisables est appelée la région ou
zone réalisable.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Analyse graphique de la programmation linéaire

Exemple 2:
Minimiser 𝑓 𝑥1 ,𝑥2 = 2000𝑥1 + 1500𝑥2
Sous réserve
6𝑥1 + 2𝑥2 ≥ 8
2𝑥1 + 4𝑥2 ≥ 12
4𝑥1 + 12𝑥2 ≥ 24
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

15

10

0
-4 -2 0 2 4 6 8

-5

-10

-15

-20

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

Un problème de programmation linéaire à deux variables peut être
facilement résolu graphiquement. La méthode est simple mais le
principe de la solution dépend de certains concepts analytiques :
Région convexe :
Une région R est convexe si et seulement si, pour deux points
quelconques de la région R, la ligne reliant ces points est entièrement
située dans la région R
Point extrême :
Le point extrême E d'une région convexe R est un point tel qu'il n'est
pas possible de localiser deux points distincts dans R, de sorte que la
ligne qui les joint inclue E. Les points extrêmes sont également appelés
points d'angle ou sommets
Ainsi, le résultat suivant fournit la solution au modèle de
programmation linéaire :

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

"Si la valeur minimale ou

maximale d'une fonction linéaire
définie sur une région convexe
existe, alors elle doit se trouver
sur l'un des points extrêmes".

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

Dans cette section, nous allons décrire une solution graphique de
programmation linéaire pour les problèmes de maximisation et de
minimisation, discutés dans les exemples 1 et 2.
Pour l’exemple 1, la zone réalisable est définie par les points A,B,C, D
et E
350
300
250
200
150 B
100 C
50 D
0 A E
-50 -50 0 50 100 150 200 250

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

Dans ce problème, la fonction objectif est
𝑓 𝑥1 ,𝑥2 = 30𝑥1 + 40𝑥2
Soit 𝑚 un paramètre, le graphe 30𝑥1 + 40𝑥2 = 𝑚 est un groupe de
lignes parallèles de pente - 30/40.
Certaines de ces lignes coupent la région réalisable et contiennent de
nombreuses solutions réalisables, tandis que les autres lignes manquent
et ne contiennent aucune solution réalisable.
Afin de maximiser la fonction objectif, nous trouvons la ligne de cette
famille qui coupe la région réalisable et qui est la plus éloignée de
l'origine. Notez que plus la ligne est éloignée de l'origine, plus la valeur
de M sera grande.
Observez que la droite 30𝑥1 + 40𝑥2 = 𝑚 passe par le point C, qui est
l'intersection des droites 3𝑥1 + 5𝑥2 = 800 et 5𝑥1 + 6𝑥2 = 1100 et dont
les coordonnées sont 𝑥1 = 175 et 𝑥2 = 34,5. Puisque C est la seule
solution réalisable sur cette ligne, la solution est unique.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

La valeur de 𝑚 est 7000, qui est la valeur maximale de la fonction
objectif. Les variables de la valeur optimale des variables sont 𝑥1 = 175
et 𝑥2 = 34,5
Le tableau 1 suivant montre le calcul de la valeur maximale de la
fonction objectif.
Point extrême 𝑥1 𝑥2 𝒎 = 𝑓 𝑥1 ,𝑥2
A 0 0 0
B 0 160 6400
C 100 100 7000
D 175 34,5 6620
E 200 0 6000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

Les cordonnées des points A,B,C,D et E sont déterminées par la
résolution du système d’équations composé des équations dont le point
en question est l’intersection des droites y afférentes:

Point Équation 1 Équation 2 𝑥1 ,𝑥2

extrême
A 𝑥1 =0 𝑥2 =0 (0,0)
B 𝑥1 =0 3𝑥1 + 5𝑥2 = 800 (0,160)
C 3𝑥1 + 5𝑥2 = 800 5𝑥1 + 6𝑥2 = 1100 (100,100)
D 5𝑥1 + 6𝑥2 = 1100 3𝑥1 + 2𝑥2 = 600 (175,75/2)
E 3𝑥1 + 2𝑥2 = 600 𝑥2 =0 (200,0)

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

Pour l’exemple 2, La région réalisable pour ce problème est illustrée
dans le graphique suivant. Ici, chacun des demi-plans se trouve au-
dessus de sa limite. Dans ce cas, la région réalisable est infinie. Dans ce
cas, on se préoccupe de la minimisation ; aussi il n'est pas possible de
déterminer la valeur maximale
Comme dans l'exemple précédent, introduisons un paramètre 𝑚 dans la
fonction objectif, c'est-à-dire 2000𝑥1 + 1500𝑥2 = m, et traçons
les lignes pour différentes valeurs de M, comme le montre le tableau 2
ci-dessous.
Les cordonnées des points A,B et C sont déterminées par la résolution
du système d’équations composé des équations dont le point en
question est l’intersection des droites y afférentes

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

15

10

5A

B
C
0
-4 -2 0 2 4 6 8

-5

-10

-15

-20

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

Les cordonnées des points A,B,C,D et E sont déterminées par la
résolution du système d’équations composé des équations dont le point
en question est l’intersection des droites y afférentes:

Point Équation 1 Équation 2 𝑥1 ,𝑥2

extrême
A 𝑥1 =0 6𝑥1 + 2𝑥2 = 8 (0,4)
B 6𝑥1 + 2𝑥2 = 8 2𝑥1 + 4𝑥2 = 12 (4/10,28/10)
C 2𝑥1 + 4𝑥2 = 12 𝑥2 = 0 (6,0)

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution graphique de la programmation linéaire

La valeur de 𝑚 est 5000, qui est la valeur minimale de la fonction
objectif. Les variables de la valeur optimale des variables sont 𝑥1 = 0,4
et 𝑥2 = 2,8
Le tableau 1 suivant montre le calcul de la valeur maximale de la
fonction objectif.
Point extrême 𝑥1 𝑥2 𝒎 = 𝑓 𝑥1 ,𝑥2
A 0 4 6000
B 0,4 2,8 5000
C 6 0 12000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions optimales multiples

Lorsque la fonction objectif ne passe que par le point extrême
situé à l'intersection de deux demi-plans, alors le problème de
programmation linéaire possède des solutions uniques. Les
exemples précédents, c'est-à-dire l'exemple sont de ce type
(qui possèdent des solutions uniques).
Lorsque la fonction objectif coïncide avec l'un des demi-plans
générés par les contraintes du problème, il y aura plusieurs
solutions optimales. Dans cette section, nous allons discuter
des solutions optimales multiples d'un problème de
programmation linéaire à l'aide de l'exemple 3 suivant.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions optimales multiples

Exemple 3:
Une entreprise qui achète des matériaux de rebut dispose de deux types
de matériaux de rebut. Le premier type contient 30 % de matériau X, 20
% de matériau Y et 50 % de matériau Z en poids. Le second type
contient 40 % de du matériau X, 10 % du matériau Y et 30 % du
matériau Z.
Les coûts des deux déchets sont respectivement de 120 et 160 dhs par
kg. L'entreprise a besoin d'au moins 240 kg de matériau X, 100 kg de
matériau Y et 290 kg de matériau Z. Trouvez les quantités optimales des
deux déchets à acheter pour satisfaire les besoins de l'entreprise en trois
matières à un coût minimal.
Solution
Nous devons d'abord formuler le modèle de programmation linéaire.
Introduisons les variables de décision 𝑥1 et 𝑥2 qui indiquent la quantité
de matériel de rebut à acheter. L'objectif est ici de minimiser le coût
d'achat. La fonction objectif est donc la suivante:
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solutions optimales multiples

Exemple 3:
Minimiser 𝑓 𝑥1 ,𝑥2 = 120𝑥1 + 160𝑥2
Sous réserve
0.3𝑥1 + 0.4𝑥2 ≥ 240
0.2𝑥1 + 0.1𝑥2 ≥ 100
0.5𝑥1 + 0.3𝑥2 ≥ 290
0 ≤ 𝑥1 et 0 ≤ 𝑥2
Multipliez par 10 les deux côtés de l'inégalité, et le problème devient:
Minimiser 𝑓 𝑥1 ,𝑥2 = 120𝑥1 + 160𝑥2
Sous réserve
3𝑥1 + 4𝑥2 ≥ 2400
2𝑥1 + 𝑥2 ≥ 1000
5𝑥1 + 3𝑥2 ≥ 2900
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions optimales multiples

Exemple 3: Les points extrêmes de ce problème sont:
2000

1500

1000

500

0
-400 -200 0 200 400 600 800 1000 1200 1400
-500

-1000

-1500

-2000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions optimales multiples

Exemple 3:
Les points extrêmes de ce problème sont:

Point Équation 1 Équation 2 𝑥1 ,𝑥2

extrême
A 𝑥1 =0 2𝑥1 + 𝑥2 = 1000 (0,1000)
B 2𝑥1 + 𝑥2 = 1000 5𝑥1 + 3𝑥2 = 2900 (100,800)
C 5𝑥1 + 3𝑥2 = 2900 3𝑥1 + 4𝑥2 = 2400 (400,300)
D 3𝑥1 + 4𝑥2 = 2400 𝑥2 = 0 (800,0)

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions optimales multiples

La valeur de 𝑚 est 96000, qui est la valeur minimale de la fonction
objectif. Plusieurs solution réalise cette minimum comme précisé dans
le tableau suivant qui montre le calcul de la valeur maximale de la
fonction objectif.

Point extrême 𝑥1 𝑥2 𝒎 = 𝑓 𝑥1 ,𝑥2

A 0 1000 160000
B 100 800 140000
C 400 300 96000
D 800 0 96000
Ainsi, chaque point de la ligne CD minimise la valeur de la fonction-
objectif et le problème contient plusieurs solutions optimales
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solution non bornée

Lorsque la région réalisable n'est pas limitée, un problème de
maximisation peut ne pas avoir de solution optimale, car les valeurs des
variables de décision peuvent être augmentées arbitrairement. Ceci est
illustré à l'aide du problème suivant.
Exemple 4:
Maximiser 𝑓 𝑥1 ,𝑥2 = 3𝑥1 + 𝑥2
Sous réserve
𝑥1 + 𝑥2 ≥ 6
−𝑥1 + 𝑥2 ≤ 6
−𝑥1 + 2𝑥2 ≥ −6
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

20

15

10
A
5

B
0
-10 -5 0 5 10 15
-5

-10

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non bornée

Le graphique montre la région réalisable non bornée et démontre que la
fonction objectif peut être rendue arbitrairement grande en augmentant
les valeurs de 𝑥1 et 𝑥2 dans la région réalisable non bornée. Dans ce cas,
aucun point (𝑥1 , 𝑥2 ) n'est optimal car il existe toujours d'autres points
réalisables pour lesquels la fonction objectif est plus grande. Notez que
ce n'est pas la région réalisable non bornée seule qui empêche une
solution optimale. La minimisation des fonctions soumises aux
contraintes indiquées dans le graphique 6 serait résolue à l'un des points
extrêmes (A ou B).
Les solutions non bornées sont généralement dues au fait que certaines
contraintes réelles, qui représentent une limitation pratique des
ressources, n'ont pas été prises en compte dans la formulation de la
programmation linéaire. Dans une telle situation, le problème doit être
reformulé et résolu à nouveau.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non réalisable

On dit d'un problème de programmation linéaire qu'il non réalisable s'il
n'existe pas de solution réalisable du problème. Cette section décrit la
solution non réalisable du problème de programmation linéaire à l'aide
de l'exemple 5 suivant.
Exemple 5:
Minimiser 𝑓 𝑥1 ,𝑥2 = 200𝑥1 + 3000𝑥2
Sous réserve
4𝑥1 + 6𝑥2 ≥ 2400
2𝑥1 + 2𝑥2 ≤ 800
4𝑥1 + 3𝑥2 ≥ 1800
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

700

600 A

500

400 B

300

200 F

100

C E
0
0 100 200 300 400 500 600 700

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non réalisable

La région à droite de la limite AFE comprend toutes les solutions qui
satisfont la première (4𝑥1 + 6𝑥2 ≥ 2400 ) et la troisième (4𝑥1 + 3𝑥2 ≥
1800) contraintes. La région à gauche de la BC contient toutes les
solutions qui satisfont la deuxième contrainte (2𝑥1 + 2𝑥2 ≤ 800 ).

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La programmation linéaire
Méthode de simplexe

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

plan
- Introduction
- Principes de base de la méthode du simplexe.
- Calcul de la méthode du simplexe.
- Méthode du simplexe avec plus de deux variables.
- Méthode en deux phase.
- Méthode M.
- Solutions multiples.
- Solution non bornée.
- Solution non réalisable.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Objectifs

- Comprendre les bases de la méthode du simplexe.

- Expliquer les calculs du simplexe.
- Décrire les différentes solutions de la méthode du simplexe.
- Comprendre la méthode biphasée et la méthode M.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction

La programmation linéaire à deux variables peut être résolue

graphiquement. La méthode graphique de résolution des
problèmes de programmation linéaire a une application
limitée dans les problèmes commerciaux, car le nombre de
variables est très élevé.
Si le problème de programmation linéaire comporte un plus
grand nombre de variables, la méthode la plus appropriée
pour le résoudre est la méthode du simplexe.
La méthode du simplexe est un processus itératif qui permet
d'atteindre finalement la valeur minimale ou maximale de la
fonction objectif.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Introduction

La méthode du simplexe aide également le

décideur/gestionnaire à identifier les éléments suivants :
1. Les contraintes.
2. Solutions multiples.
3. Solution non bornée.
4. Problème non réalisable.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Les bases de la méthode du simplexe

Nous allons expliquer les fondements de la méthode du

simplexe à l'aide du problème de programmation linéaire
suivant.

Exemple 5:
Maximiser 𝑓 𝑥1 ,𝑥2 = 60𝑥1 + 70𝑥2
Sous réserve
2𝑥1 + 𝑥2 ≤ 300
3𝑥1 + 4𝑥2 ≤ 509
4𝑥1 + 7𝑥2 ≤ 812
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Les bases de la méthode du simplexe

Solution
On introduit d'abord les variables, 𝑠3 , 𝑠4 , 𝑠5 ≥ 0
De sorte que les contraintes deviennent des équations, donc
2𝑥1 + 𝑥2 + 𝑠3 = 300
3𝑥1 + 4𝑥2 + 𝑠4 = 509
4𝑥1 + 7𝑥2 + 𝑠5 = 812

Le système d’équation précédent correspond aux trois

contraintes. Il est a trois équations et cinq variables.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Les bases de la méthode du simplexe

Il existe deux types de solutions pour ce système qui sont les
solutions de base et les solutions de base réalisables:
1- Solution de base.
Nous pouvons mettre n'importe quelles deux variables à zéro
dans le système d'équations ci-dessus, et le système aura
alors a trois variables. Ainsi, si ce système de trois équations
avec trois variables est soluble, une telle solution est appelée
solution de base.
Par exemple, supposons que nous prenons 𝑥1 =0 et 𝑥2 =0, la
solution du système avec les trois variables restantes est
𝑠3 =300, 𝑠4 =509 et 𝑠5 =812, il s'agit d'une solution de base et
les variables 𝑠3 , 𝑠4 et 𝑠4 sont connues comme des variables
de base alors que les variables 𝑥1 , 𝑥2 sont connues comme
des variables hors-base.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Les bases de la méthode du simplexe

2- Solution de base réalisable.
Une solution de base d'un problème de programmation
linéaire est appelée solution de base réalisable si elle est
réalisable, c'est-à-dire si toutes les variables sont non
négatives. La solution 𝑠3 =300, 𝑠4 =509 et 𝑠5 =812 est une
solution de base réalisable.
Chaque solution de base réalisable est un point extrême de
l'ensemble convexe des solutions réalisables et chaque point
extrême est une solution réalisable de base de l'ensemble des
contraintes données. Il est impossible d'identifier les points
extrêmes géométriquement si le problème a plusieurs
variables, mais les points extrêmes peuvent être identifiés en
utilisant les solutions réalisables de base.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Les bases de la méthode du simplexe

Puisque l'une des solutions de base réalisables maximisera ou

minimisera la fonction objectif, la recherche des points
extrêmes peut être effectuée en partant d'une solution de base
réalisable à une autre.
La méthode simplexe fournit une recherche systématique de
sorte que la fonction objectif augmente progressivement dans
les cas de maximisation jusqu'à ce que la solution de base
réalisable est identifiée où la fonction objectif est maximisée.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

Cette section décrit l'aspect calcul de la méthode simplexe.
Considérons le problème de programmation précédent:

Maximiser 𝑓 𝑥1 ,𝑥2 = 60𝑥1 + 70𝑥2

Sous réserve

2𝑥1 + 𝑥2 + 𝑠3 = 300
3𝑥1 + 4𝑥2 + 𝑠4 = 509
4𝑥1 + 7𝑥2 + 𝑠5 = 812
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑠3 , 0 ≤ 𝑠4 𝑒𝑡 0 ≤ 𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

La forme matricielle de ce problème est :
Maximiser 𝑓 𝑥1 ,𝑥2 = 60𝑥1 + 70𝑥2
Sous réserve

𝐴𝑋 = 𝐵
avec

𝑥1
2 1 1 0 0 𝑥2 𝑏1 = 300
𝐴= 3 4 0 1 0 ,𝑋 = 𝑠3 et 𝐵 = 𝑏2 = 509
4 7 0 0 1 𝑠4 𝑏3 = 812
𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

Maximiser 𝑓 𝑥1 ,𝑥2 = Z implique la Maximisation 60𝑥1 +
70𝑥2 , la forme matricielle peut être présentée sous forme d'un
tableau. Dans ce problème, les variables pivots 𝑠3 , 𝑠4 et 𝑠5
fournissent une solution de base réalisable à partir de laquelle
commence le calcul. C'est-à-dire 𝑠3 =300, 𝑠4 =509 et 𝑠5 =812 et.
La ligne supérieure du tableau 1 indique le coefficient des
variables 𝒙𝟏 , 𝒙𝟐 , 𝒔𝟑 , 𝒔𝟒 , 𝒔𝟓 de la fonction objectif que nous
notons 𝐶𝑖 . respectivement. La colonne sous 𝒙𝟏 , 𝒙𝟐 , 𝒔𝟑 , 𝒔𝟒 , 𝒔𝟓
indiquent les coefficients de 𝒙𝟏 , 𝒙𝟐 , 𝒔𝟑 , 𝒔𝟒 , 𝒔𝟓 dans les trois
équations respectivement.
La dernière colonne représente les valeurs de 𝐵 et la dernière
ligne représente la fonction objectif 𝑍𝑖 − 𝐶𝑖 avec :
𝑍𝑖 = 3𝑗=1 𝐶𝑉𝐵𝑗 ∗ 𝑎𝑖𝑗

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

VB 𝑪𝒊 60 70 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 2 1 1 0 0 300
𝒔𝟒 0 3 4 0 1 0 509
𝒔𝟓 0 4 7 0 0 1 812
𝒁𝒊 − 𝑪𝒊 -60 -70 0 0 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

En voyant l'équation Z = 60𝑥1 + 70𝑥2 , nous pouvons observer que
si 𝑥1 ou 𝑥2 , qui n'est actuellement pas une variable de base, est
inclus comme variable de base, le bénéfice augmentera. Comme le
coefficient de 𝑥2 est plus élevé, nous choisissons d'inclure 𝑥2
comme variable de base dans la prochaine itération.
(Un critère équivalent de choix d'une nouvelle variable de base
peut être obtenu à la dernière ligne du tableau, c'est-à-dire celle
correspondant à Z, Puisque l'entrée correspondant à 𝑥2 est plus
petite entre les deux valeurs négatives, 𝑥2 sera incluse comme
variable de base dans l'itération suivante).
Cependant, avec les trois contraintes, il ne peut y avoir que trois
variables de base. Ainsi, en introduisant une variable de base 𝑥2 ,
une des variables de base existantes devient hors-base. La
question est la suivante : comment identifier cette variable ?
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

Les énoncés suivants donnent la solution à cette question:
Considérons la première équation: 2𝒙𝟏 + 𝒙𝟐 + 𝒔𝟑 = 300
A partir de cette équation: 2𝒙𝟏 + 𝒔𝟑 = 300-𝒙𝟐 , Mais 𝒙𝟏 = 0.
Donc, pour que 𝒔𝟑 ≥0 on a 300 − 𝒙𝟐 ≥ 0, c-à-d que 𝒙𝟐 ≤300
De même, la deuxième équation: 3𝒙𝟏 + 4𝒙𝟐 + 𝒔𝟒 = 509.
A partir de cette équation : 3𝒙𝟏 +𝒔𝟒 =509-4𝒙𝟐 , Mais, 𝒙𝟏 = 0.
donc, afin que 𝒔𝟑 ≥0 on a 509-4𝒙𝟐 ≥ 0, c-à-d que 𝒙𝟐 ≤509/4
De même, la troisième équation : 4𝒙𝟏 + 7𝒙𝟐 + 𝒔𝟓 = 812.
A partir de cette équation : 4𝒙𝟏 +𝒔𝟓 =812-7𝒙𝟐 , Mais 𝒙𝟏 = 0.
donc, afin que 𝒔𝟓 ≥0 implique 812 − 7𝒙𝟐 ≥ 0, c-à-d que
𝒙𝟐 ≤ 812/7
Par conséquent, les trois équations conduisent à:
𝒙𝟐 =min(300/1, 509/4, 812/7)=116

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

Donc 𝒙𝟐 =116, si 𝒙𝟐 =116, vous pouvez noter à partir de la
troisième équation: 7𝒙𝟐 +𝒔𝟓 =812 c'est-à-dire que 𝒔𝟓 =0
Ainsi, la variable 𝒔𝟓 devient une variable hors-base dans
l'itération suivante.
De sorte que les valeurs révisées des deux autres variables de base
sont les suivantes
𝒔𝟑 = 300-𝒙𝟐 =184 et 𝒔𝟒 =509-4𝒙𝟐 =45

En se référant au tableau 1, on obtient les éléments du tableau suivant,

c'est-à-dire le tableau 2, en utilisant les règles suivantes :

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

1. On répartit les quantités qui sont négatives dans la
rangée 𝒁𝒊 − 𝑪𝒊
2. Supposons que toutes les quantités soient positives,
l'inclusion de toute variable hors-base n'augmentera pas la
valeur de la fonction objectif. Par conséquent, la présente
solution maximise la fonction objectif. S'il y a plus d'une
valeur négative, nous choisissons comme variable de base
celle dont la valeur Z est la plus faible, car elle est susceptible
d'augmenter le bénéfice.
3. Soit 𝑥𝑗 la variable de base entrante et les éléments
correspondants de la colonne de la jème ligne soient
désignées respectivement par a1j , a2j et a3j . Si les valeurs
actuelles des variables de base sont 𝑏1 , 𝑏2 et 𝑏3
respectivement, alors nous pouvons calculer.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

𝑏 𝑏 𝑏
Min [ 1, 2, 3] pour a1j , a2j , a3j > 0.
a1j a2j a3j
Notez que si un quelconque aij ≤ 0, il n'est pas nécessaire de
l'inclure dans la comparaison. Si le minimum se produit
𝑏
correspondant à a 𝑟 alors la rième variable de base deviendra hors
rj
base dans l'itération suivante.
3. En utilisant les règles suivantes, le tableau 2 est calculé à
partir du tableau 1.
 Les variables de base révisées sont 𝒔𝟑 , 𝒔𝟒 et 𝒙𝟐 . En conséquence,
nous faisons 𝐶𝑉𝐵1 =0, 𝐶𝑉𝐵2 =0, et 𝐶𝑉𝐵3 =70.
 Comme 𝒙𝟐 est la variable de base entrante, nous faisons en sorte que
le coefficient de 𝒙𝟐 soit égal à 1 en divisant chaque élément de la
ligne 3 par 7. Ainsi, la valeur numérique de l'élément correspondant
à 𝒙𝟏 est 4/7, celle correspondant à 𝒔𝟓 est 1/7 dans le tableau 2.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

 La variable de base entrante ne doit apparaître que dans la troisième
ligne c-à-d que la colone 2 doit avoir des valeurs nulles à l’exception
de la troisième valeur qui doit être égale à 1. de ce fait:
 La première𝐿1 ligne doit être remplacée par 𝐿1 − 𝑎12 𝐿3 , dans cette
exemple, 𝐿1 ligne doit être remplacée par 𝐿1 − 𝐿3 .
 La deuxiéme 𝐿2 ligne doit être remplacée par 𝐿2 − 𝑎22 𝐿3 , dans
cette exemple, 𝐿1 ligne doit être remplacée par 𝐿1 − 4𝐿3 .
 La dérniére ligne est calculer par 𝒁𝒊 − 𝑪𝒊 donc:
𝑍1 − 𝐶1 = 10/7∗0+5/7∗0+70∗4/7−60 = − 20
𝑍2 − 𝐶2 = 70 ∗ 1 − 70 = 0
𝑍3 − 𝐶3 = 0
𝑍4 − 𝐶4 = 0
𝑍5 − 𝐶5 = −1/7∗0−4/7∗0+1/7∗70−0 = 10

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

VB 𝑪𝒊 60 70 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 10/7 0 1 0 -1/7 184

𝒔𝟒 0 5/7 0 0 1 -4/7 45
𝒙𝟐 70 4/7 1 0 0 1/7 116
𝒁𝒊 − 𝑪𝒊 -20 0 0 0 10

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

1- Maintenant, nous appliquons la règle (1) au tableau 2. Ici, le
seul 𝒁𝒊 − 𝑪𝒊 négatif est 𝒁𝟏 − 𝑪𝟏 = -20.
Par conséquent, 𝒙𝟏 doit devenir une variable de base à la
prochaine itération.
2- Nous calculons le minimum du rapport:
𝑏 𝑏 𝑏
Min [ 1 , 2 , 3 ] pour a11 , a21 , a31 > 0 donc
a11a 21a 31
𝑏 𝑏 𝑏 184 45 116 644
Min [ 1 , 2 , 3 ]= Min [ , , ]= Min [ , 63, 203]=63
a11 a21 a31 10/7 5/7 4/7 5
Ce minimum se produit en correspondance avec 𝒔𝟒 , il devient une
variable hors base dans l'itération suivante.
3. Comme le tableau 2, le tableau 3 est calculé par les règles (i),
(ii), (iii) décrites ci-dessus.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

VB 𝑪𝒊 60 70 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 0 0 1 -2 1 94
𝒙𝟏 60 1 0 0 7/5 -4/5 63
𝒙𝟐 70 0 1 0 -4/5 3/5 80
𝒁𝒊 − 𝑪𝒊 0 0 0 28 -6

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

1- 𝒁𝟓 − 𝑪𝟓 = -6< 0, 𝒔𝟓 doit devenir une variable de base dans
l'itération suivante.
2. Calculer maintenant les rapports minimaux
Nous calculons le minimum du rapport:
94 80 400
Min [ , ]= Min [94, ]=94
1 3/5 3
Ce minimum se produit en correspondance avec 𝒔𝟑 , il devient une
variable hors base dans l'itération suivante.
3. Comme le tableau 3, le tableau 4 est calculé par les règles (i),
(ii), (iii) décrites ci-dessus.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

VB 𝑪𝒊 60 70 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟓 0 0 0 1 -2 1 94
𝒙𝟏 60 1 0 4/5 -1/5 0 691/5
𝒙𝟐 70 0 1 -3/5 2/5 0 118/5
𝒁𝒊 − 𝑪𝒊 0 0 6 16 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Calcul de la méthode du simplexe

Notez que 𝒁𝒊 − 𝑪𝒊 ≥ 0 pour tout 𝑗, de sorte que la fonction objectif
ne peut pas être améliorée davantage.
691 118
Ainsi, la fonction objectif est maximisée pour 𝒙𝟏 = et 𝒙𝟐 =
5 5
et la valeur maximale de la fonction objectif est de 9944.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

Dans la section précédente, nous avons discuté de la méthode du
simplexe pour les problèmes de programmation linéaire avec deux
variables de décision. La procédure de calcul de la méthode du
simplexe peut être facilement étendue aux problèmes de
programmation linéaire avec plus de deux variables. Ceci est illustré
dans cette section à l'aide du problème suivant.
Une entreprise possède trois ateliers d'usinage, à savoir A, B et C, et
fabrique trois produits, à savoir X, Y et Z, en utilisant ces trois ateliers.
Chaque produit implique le fonctionnement des ateliers d'usinage. Le
temps disponible dans les ateliers d'usinage A, B et C est
respectivement de 100, 72 et 80 heures. Le bénéfice par unité de
produit X, Y et Z est respectivement de 22 dhs, 6 dhs et 2 dhs.
Le tableau suivant indique le temps nécessaire à chaque opération pour
une quantité unitaire de chaque produit. Déterminez une combinaison
appropriée de produits afin de maximiser le bénéfice.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

Présentation de l’exemple en tableau

Machine Ateliers
Productions Profit par Unité A B C
X 22 10 7 2
Y 6 2 3 4
Z 2 1 2 1
Heures disponibles 100 72 80

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

Solution
La formulation de problème linéaire.

Maximiser 𝑓 𝑥1 ,𝑥2 = 22𝑥1 + 6𝑥2 + 2𝑥3

Sous réserve
10𝑥1 + 2𝑥2 + 𝑥3 ≤ 100
7𝑥1 + 3𝑥2 + 2𝑥3 ≤ 72
2𝑥1 + 4𝑥2 + 𝑥3 ≤ 80
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3

Nous introduisons des variables muettes 𝑠4 , 𝑠5 et 𝑠6 pour rendre

l'équation des inégalités. Ainsi, le problème peut être énoncé
comme suit:

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

Maximiser 𝑓 𝑥1 ,𝑥2 = 22𝑥1 + 6𝑥2 + 2𝑥3

Sous réserve

10𝑥1 + 2𝑥2 + 𝑥3 + 𝑠4 = 100

7𝑥1 + 3𝑥2 + 2𝑥3 + 𝑠5 = 72
2𝑥1 + 4𝑥2 + 𝑥3 + 𝑠6 = 80
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3 ,0 ≤ 𝑠4 ,0 ≤ 𝑠5 et 0 ≤ 𝑠6

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

A partir de l'équation ci-dessus, on peut obtenir le tableau
simplexe 1 de manière directe. Ici, les variables de base sont 𝑠4 ,
𝑠5 et 𝑠6 . Par conséquent, 𝐶𝑉𝐵1 = 𝐶𝑉𝐵2 = 𝐶𝑉𝐵3 = 0
VB 𝑪𝒊 22 6 2 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟒 𝒔𝟓 𝒔𝟔

𝒔𝟒 0 10 2 1 1 0 0 100

𝒔𝟓 0 7 3 2 0 1 0 72

𝒔𝟔 0 2 4 1 0 0 1 80

𝒁𝒊 − 𝑪𝒊 -22 -6 -2 0 0 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

1. 𝒁𝟏 − 𝑪𝟏 = -22 est la plus petite valeur négative. Par
conséquent, 𝒙𝟏 devrait être pris comme variable de base dans la
prochaine itération.
2. Calculer le minimum des rapports
100 72 80
Min ( 10 , 7 , 2 )=10 donc la variable qui devient Hors base est 𝒔𝟒
A partir du tableau 1, le tableau 2 est calculé en utilisant les règles
suivantes :
i. Les variables de base révisées sont 𝑥1 , 𝑠5 et 𝑠6 . En conséquence, nous
faisons 𝐶𝑉𝐵1 = 22 et 𝐶𝑉𝐵2 = 𝐶𝑉𝐵3 = 0.
ii. Puisque 𝑥1 est la variable entrante, nous donnons à 𝑥1 le coefficient 1
en divisant chaque élément de la ligne 1 par 10. Ainsi, la valeur
numérique de l'élément correspondant à 𝑥2 est 2/10, celle
correspondant à 𝑥3 est 1/10, celle correspondant à 𝑠4 est 1/10, celle
correspondant à 𝑠5 est 0/10 et celle correspondant à 𝑠6 est 0/10 dans le
tableau 2.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

iii- La variable de base entrante ne doit apparaître que dans la
première ligne. Nous multiplions donc la première ligne du
Tableau 2 par 7 et nous la soustrayons de la deuxième ligne du
Tableau 1 élément par élément.
Ainsi , l'élément correspondant à 𝑥1 dans la deuxième ligne du
Tableau 2 est zéro.
16
L'élément correspondant à 𝑥2 est 3-7*2/10=10
En utilisant cette méthode, nous obtenons les éléments de la deuxième
et de la troisième ligne du tableau 2.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

VB 𝑪𝒊 22 6 2 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟒 𝒔𝟓 𝒔𝟔

𝒙𝟏 22 1 1/5 1/10 1/10 0 0 10

𝒔𝟓 0 0 8/5 13/10 -7/10 1 0 2

𝒔𝟔 0 0 18/5 4/5 -1/5 0 1 60

𝒁𝒊 − 𝑪𝒊 0 -8/5 1/5 11/5 0 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

1. 𝒁𝟐 − 𝑪𝟐 = -8/5. Donc 𝒙𝟐 devient une variable de base dans
l'itération suivante.
2. Calculez le minimum des rapports
10 2 60 20 100 20
Min ( 1 , 8 , 18 )= Min (50, 8 , 3 )= 8 donc la variable qui devient
5 5 5
hors base est 𝒔𝟓
A partir du tableau 1, le tableau 2 est calculé en utilisant les règles
suivantes :
i. Les variables de base révisées sont 𝑥1 , 𝑠5 et 𝑠6 . En conséquence, nous
faisons 𝐶𝑉𝐵1 = 22 et 𝐶𝑉𝐵2 =6 et 𝐶𝑉𝐵3 = 0.
ii. Puisque 𝑥2 est la variable entrante, nous donnons à 𝑥2 le coefficient 1
8
en divisant chaque élément de la ligne 1 par 5 . Ainsi, la valeur
numérique de l'élément correspondant à 𝑥1 est 0, celle correspondant à
𝑥3 est 13/16, celle correspondant à 𝑠4 est -7/16, celle correspondant à
𝑠5 est 5/8 et celle correspondant à 𝑠6 est 0 dans le tableau 3.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

iii- La variable de base entrante ne doit apparaître que dans la
deuxième ligne. Nous multiplions donc la deuxième ligne du
Tableau 3 par 1/5 et nous la soustrayons de la premiére ligne du
Tableau 1 élément par élément.
Ainsi , l'élément correspondant à 𝑥2 dans la première ligne du
Tableau 3 est zéro.
−1
L'élément correspondant à 𝑥3 est 1/10-1/5*13/16= 16
En utilisant cette méthode, nous obtenons les éléments de la deuxième
et de la troisième ligne du tableau 2.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode simplexe avec plus de deux variables

VB 𝑪𝒊 22 6 2 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒔𝟒 𝒔𝟓 𝒔𝟔

𝒙𝟏 22 1 0 -1/16 3/16 -1/8 0 39/4

𝒙𝟐 6 0 1 13/16 -7/16 5/8 0 10/8

𝒔𝟔 0 0 0 -17/8 11/8 -9/4 1 111/2

𝒁𝒊 − 𝑪𝒊 0 0 7/8 3/2 1 0

Notez que tous les 𝑍𝑖 − 𝐶𝑖 ≥0, de sorte que la solution est 𝑥1 = 39/4,
𝑥2 = 10/8 et 𝑠5 = 111/2 maximise la fonction objectif.
Le profit maximum est : 22* 39/4 + 6* 10/8 = 858/4 + 60/8 = 888/4 =
222
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases et méthode M

Dans les deux dernières sections, nous avons vu que la méthode
du simplexe était appliquée aux problèmes de programmation
linéaire avec des contraintes de type inférieur ou égal à (≤). Ainsi,
nous avons pu y introduire des variables de type souples ( qui
fournissent une solution initiale de base réalisable du problème.
Généralement, le problème de programmation linéaire peut également
être caractérisé par la présence de contraintes de type 'inférieur ou égal
à' ou 'supérieur ou égal à (≥)'. Dans ce cas, il n'est pas toujours possible
d'obtenir une solution initiale de base réalisable à l'aide de variables
relâchées.
Le problème de programmation linéaire de type supérieur ou égal peut
être résolu en utilisant les méthodes suivantes :
1. Méthode à deux phases
2. Méthode M
Dans cette section, nous allons discuter de ces deux méthodes

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Nous discutons de la méthode des deux phases à l'aide de
l'exemple suivant:
Minimiser 𝑓 𝑥1 ,𝑥2 = 12.5𝑥1 + 14.5𝑥2

Sous réserve

𝑥1 + 𝑥2 ≥ 2000
0.4𝑥1 + 0.75𝑥2 ≥ 1000
0.075𝑥1 + 0.1𝑥2 ≤ 200
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Solution
Ici, la fonction objectif doit être minimisée ; les valeurs de 𝑥1 et 𝑥2 qui
ont minimisé cette fonction objectif sont également les valeurs qui
maximisent la fonction objectif révisée, c'est-à-dire:
Maximiser 𝑓 𝑥1 ,𝑥2 = −12.5𝑥1 − 14.5𝑥2
Nous pouvons multiplier la deuxième et la troisième contrainte par 100
et 1000 respectivement pour la commodité de calcul.
Ainsi, le problème de programmation linéaire révisé est

Maximiser 𝑓 𝑥1 ,𝑥2 = −12.5𝑥1 − 14.5𝑥2

Sous réserve
𝑥1 + 𝑥2 ≥ 2000
40𝑥1 + 75𝑥2 ≥ 100000
75𝑥1 + 100𝑥2 ≤ 200000
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Nous convertissons maintenant les deux inégalités en
introduisant des variables exedentaire 𝑠3 et 𝑠4
respectivement.
La troisième contrainte est transformée en une équation en
introduisant une variable de déficitaire 𝑠5 .
Ainsi, le problème de programmation linéaire devient
25 29
Maximiser 𝑓 𝑥1 ,𝑥2 = − 𝑥1 − 𝑥2
2 2
Sous réserve

𝑥1 + 𝑥2 − 𝑠3 = 2000
40𝑥1 + 75𝑥2 − 𝑠4 = 100000
75𝑥1 + 100𝑥2 + 𝑠5 = 200000
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3 ,0 ≤ 𝑠4 ,0 ≤ 𝑠5 et 0 ≤ 𝑠6
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Bien que les variables d’écarts 𝑠3 , 𝑠4 et 𝑠5 puissent convertir
les contraintes de type supérieur ou égal en équations, elles
sont incapables de fournir des variables de base initiale pour
lancer le calcul par la méthode du simplexe. Ainsi, nous
devons introduire deux autres variables supplémentaires 𝑎6 et
𝑎7 appelées variables artificielles pour faciliter le calcul d'une
solution initiale de base réalisable.
Dans cette méthode, le calcul est effectué en deux phases.
Nous allons expliquer cette méthode par deux exemple.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Exemple 1
Maximiser 𝑧 = −𝑎6 − 𝑎7
Sous réserve

𝑥1 + 𝑥2 − 𝑠3 + 𝑎6 = 2000
40𝑥1 + 75𝑥2 − 𝑠4 + 𝑎7 = 100000
75𝑥1 + 100𝑥2 + 𝑠5 = 200000
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3 ,0 ≤ 𝑠4 ,0 ≤ 𝑠5 , 0 ≤ 𝑠6 , 0 ≤ 𝑎6
𝑒𝑡0 ≤ 𝑎7

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Phase I:
La solution initiale de base réalisable du problème sont : 𝑎6
= 2000, 𝑎7 =100000 et 𝑠5 = 200000.
𝑥1
𝑥2
1 1 −1 0 0 1 0 𝑠3
𝐴 = 40 75 0 −1 0 0 1 , 𝑋 = 𝑠4 et
75 100 0 0 1 0 0 𝑠5
𝑎6
𝑎7
𝑏1 = 2000
𝐵 = 𝑏2 = 100000
𝑏3 = 200000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Comme la valeur minimale de la fonction objective de la
phase 1 est nulle à la fin de la phase 1, 𝑎6 et 𝑎7 deviennent
tous deux nuls.
VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝑎6 -1 1 1 -1 0 0 1 0 2000
𝑎7 -1 40 75 0 -1 0 0 1 100000
𝒔𝟓 0 75 100 0 0 1 0 0 200000

𝒁𝒊 − 𝑪𝒊 −41 −76 1 1 0 0 0

𝟑
𝒁𝒊 − 𝑪𝒊 = 𝒋=𝟏 𝐶𝑉𝐵𝑗 𝒂𝒋𝒊 − 𝑪𝒊

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Ici, 𝒙𝟐 devient une variable de base et 𝑎7 devient une
variable non basique dans l'itération suivante. Elle n'est plus
considérée pour être réintroduite dans le tableau..
VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝑎6 -1 7/15 0 -1 1/75 0 1 -1/75 2000/3

𝒙𝟐 0 8/15 1 0 -1/75 0 0 1/75 4000/3

𝒔𝟓 0 65/3 0 0 4/3 1 0 -4/3 200000/3

𝒁𝒊 − 𝑪𝒊 −7/15 0 1 -1/75 0 0 0

𝟑
𝒁𝒊 − 𝑪𝒊 = 𝒋=𝟏 𝐶𝑉𝐵𝑗 𝒂𝒋𝒊 − 𝑪𝒊

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Alors 𝒙𝟏 devient une variable de base et 𝑎6 devient une
variable non basique dans l'itération suivante.
Min((2000/3)/7/15; (4000/3)/8/15; (200000/3)/65/3)=(2000/3)/7/15=10000/7

VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝑎6 -1 7/15 0 -1 1/75 0 1 -1/75 2000/3

𝒙𝟐 0 8/15 1 0 -1/75 0 0 1/75 4000/3

𝒔𝟓 0 65/3 0 0 4/3 1 0 -4/3 200000/3

𝒁𝒊 − 𝑪𝒊 −7/15 0 1 -1/75 0 0 0

𝟑
𝒁𝒊 − 𝑪𝒊 = 𝒋=𝟏 𝐶𝑉𝐵𝑗 𝒂𝒋𝒊 − 𝑪𝒊

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝑥1 0 1 0 -15/7 1/35 0 15/7 -1/75 10000/7

𝒙𝟐 0 0 1 8/7 -1/35 0 -8/15 1/75 4000/7

𝒔𝟓 0 0 0 325/7 5/7 1 -325/7 -4/3 250000/7

𝒁𝒊 − 𝑪𝒊 0 0 0 0 0 0 0

Le calcul de la phase I se termine à ce stade. Notez que les deux

variables artificielles ont été supprimées et qu'une solution de base
réalisable a été trouvée pour le problème.
La solution de base réalisable est :
𝑥1 = 10000/7, 𝒙𝟐 = 4000/7, 𝒔𝟓 = 250000/7.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Phase II
La solution initiale de base réalisable obtenue à la fin de la phase I du
calcul est utilisée comme solution initiale de base réalisable du
problème. Dans ce calcul de la phase II, la fonction objective originale
est introduite et la procédure habituelle du simplexe est appliquée pour
résoudre le problème de programmation linéaire.
VB 𝑪𝒊 -25/2 -29/2 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝑥1 -25/2 1 0 -15/7 1/35 0 10000/7

𝒙𝟐 -29/2 0 1 8/7 -1/35 0 4000/7

𝒔𝟓 0 0 0 325/7 5/7 1 250000/7

𝒁𝒊 − 𝑪𝒊 0 0 143/14 2/35 0

Dans ce tableau 1 tous les 𝒁𝒊 − 𝑪𝒊 ≥ 0 la solution actuelle maximise la

fonction objectif révisée. Ainsi, la solution du problème est :
𝑥1 = 10000/7 = 1428,57 et 𝒙𝟐 = 4000/7 = 571,42 et
La valeur minimale de la fonction objectif est : 26142,85
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Un dirigeant d’entreprise qui produit deux produits 𝑃1 et 𝑃2 en train de
planifier une période 𝑇 de production dans deux ateliers A et B.
L’atelier A utilise 2 heures de travail pour produire 𝑃1 et l’atelier B
travail 3 heures 𝑃2 . sachant que :
- Les prix unitaires des deux produits 𝑃1 et 𝑃2 sont respectivement 1000
et 1200 dhs et
- Les couts unitaires sont respectivement 10 et 5 dhs et que le coût
global de la production durant la période T ne doit pas dépasser
200dhs
- Le dirigeant veut faire travailler les deux atelier exactement 60 heures
durant la période 𝑇 et il croit que le marché pourrait absorber jusqu’à
12 unité de sa production du produit 𝑃1 .
- Enfin, il s'est engagé à livrer 6 unité de 𝑃2 à un client régulier et il
tient à respecter son engagement.
Qu’elles sont les quantités 𝑥1 et 𝑥2 qu’il faut produire pour maximiser
le chiffre d’affaire de cette entreprise dans la période T.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Le problème de programmation linéaire peut être formalisé
comme suit
Maximiser 𝑓 𝑥1 ,𝑥2 = 1000𝑥1 + 1200𝑥2
Sous réserve

10𝑥1 + 5𝑥2 ≤ 200

2𝑥1 + 3𝑥2 = 60
𝑥1 ≤ 12
𝑥2 ≥ 6
0 ≤ 𝑥1 , 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

L’ajout de variables d’écart ou d’excédent transforme le modèle
précédent au modèle suivant :

Maximiser 𝑧 = 1000𝑥1 + 1200𝑥2

Sous réserve
10𝑥1 + 5𝑥2 + 𝑠3 = 200
2𝑥1 + 3𝑥2 = 60
𝑥1 + 𝑠4 = 12
𝑥2 − 𝑠5 =6
0 ≤ 𝑥1 , 0 ≤ 𝑥2 ,0 ≤ 𝑠3 ,0 ≤ 𝑠4 𝑒𝑡 0 ≤ 𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Phase 1:
Cette phase consiste à ajouter deux variables artificielles au niveau de
la contrainte 2 et la contrainte 4 et résoudre le problème suivant
Maximiser 𝑧 = −𝑎6 − 𝑎7
Sous réserve

10𝑥1 + 5𝑥2 + 𝑠3 = 200

2𝑥1 + 3𝑥2 + 𝑎6 = 60
𝑥1 + 𝑠4 = 12
𝑥2 − 𝑠5 + 𝑎7 =6
0 ≤ 𝑥1 , 0 ≤ 𝑥2 ,0 ≤ 𝑠3 ,0 ≤ 𝑠4 𝑒𝑡 0 ≤ 𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Phase I:
La solution initiale de base réalisable du problème sont 𝑠3 =
200 , 𝑎6 = 60, 𝑎7 =6, et 𝑠4 = 12.
𝑥1
𝑥2
10 5 1 0 0 0 0
𝑠3
2 3 0 0 0 1 0
𝐴= , 𝑋 = 𝑠4 et
1 0 0 1 0 0 0 𝑠5
0 1 0 0 −1 0 1 𝑎6
𝑎7
𝑏1 = 200
𝑏2 = 60
𝐵=
𝑏3 = 12
𝑏4 = 6
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Comme la valeur minimale de la fonction objective de la
phase 1 est nulle à la fin de la phase 1, 𝑎6 et 𝑎7 deviennent
tous deux nuls.
VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝒔𝟑 0 10 5 1 0 0 0 0 200
𝑎6 -1 2 3 0 0 0 1 0 60
𝒔𝟒 0 1 0 0 1 0 0 1 12

𝑎7 -1 0 1 0 0 -1 0 0 6

𝒁𝒊 − 𝑪𝒊 −2 −4 0 0 1 0 0

𝟒
𝒁𝒊 − 𝑪𝒊 = 𝒋=𝟏 𝐶𝑉𝐵𝑗 𝒂𝒋𝒊 − 𝑪𝒊
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Ici, 𝒙𝟐 devient une variable de base et 𝑎7 devient une variable hors base
200 60 6
dans l'itération suivante (min( 5 , 3 , 1) = 6). Elle n'est plus considérée
pour être réintroduite dans le tableau.

VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝒔𝟑 0 10 0 1 0 5 0 0 170
𝑎6 -1 2 0 0 0 3 1 0 42
𝒔𝟒 0 1 0 0 1 0 0 1 12

𝒙𝟐 0 0 1 0 0 -1 0 0 6

𝒁𝒊 − 𝑪𝒊 −2 0 0 0 -3 0 0

𝟒
𝒁𝒊 − 𝑪𝒊 = 𝒋=𝟏 𝐶𝑉𝐵𝑗 𝒂𝒋𝒊 − 𝑪𝒊
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Le tableau précédent montre que , 𝒔𝟓 devient une variable de base et 𝑎6
170 42
devient une variable hors base dans l'itération suivante (min( 5 , 3 ) =
14) Elle n'est plus considérée pour être réintroduite dans le tableau.

VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝒔𝟑 0 20/3 0 1 0 0 -5 0 100
𝑠5 0 2/3 0 0 0 1 1/3 0 14
𝒔𝟒 0 1 0 0 1 0 0 1 12
𝒙𝟐 0 2/3 1 0 0 0 1 0 20
𝒁𝒊 − 𝑪𝒊 0 0 0 0 0 0 0

𝟒
𝒁𝒊 − 𝑪𝒊 = 𝒋=𝟏 𝐶𝑉𝐵𝑗 𝒂𝒋𝒊 − 𝑪𝒊
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝒔𝟑 0 20/3 0 1 0 0 -5 0 100
𝑠5 0 2/3 0 0 0 1 1 0 14
𝒔𝟒 0 1 0 0 1 0 0 1 12
𝒙𝟐 0 2/3 1 0 0 0 1 0 20
𝒁𝒊 − 𝑪𝒊 0 0 0 0 0 0 0

Le calcul de la phase I se termine à ce stade. Notez que les deux

variables artificielles ont été supprimées et qu'une solution de base
réalisable a été trouvée pour le problème.
La solution de base réalisable est :
𝑥2 = 20, 𝒔𝟑 = 100, 𝒔𝟒 = 12, 𝒔𝟓 = 14.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

La phase II
Dans cette phase le tableau de la premiére phase est maintenant en effectuant
les opération suivantes:
• Suppression des colonnes de 𝑎6 et 𝑎7
• Remplir la ligne 𝑪𝒊 par les coefficient de la fonction objectif 1000𝑥1 +
1200𝑥2
• Changer les coefficients des 𝒙𝒊 dans la colonne 𝐶𝑉𝐵𝑖 (𝒙𝟐 reçoit 1200)
• Changer les valeurs de 𝒁𝒊 − 𝑪𝒊
VB 𝑪𝒊 1000 1200 0 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 20/3 0 1 0 0 100

𝑠5 0 2/3 0 0 0 1 14

𝒔𝟒 0 1 0 0 1 0 12

𝒙𝟐 1200 2/3 1 0 0 0 20

𝒁𝒊 − 𝑪𝒊 −200 0 0 0 0
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Le tableau montre que 𝑍1 − 𝐶1 = −200 ≤ 0, donc 𝑥1 est une variable entrante
100 14 12 20
et 𝑠4 est une variable hors base (min( 20 , 2 , , 2 )=12).
1
3 3 3

VB 𝑪𝒊 1000 1200 0 0 0 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 0 0 1 -20/3 0 20

𝑠5 0 0 0 0 -2/3 1 6

𝒙𝟏 1000 1 0 0 1 0 12

𝒙𝟐 1200 0 1 0 -2/3 0 12

𝒁𝒊 − 𝑪𝒊 0 0 0 200 0

Le calcul de la phase II se termine à ce stade (𝒁𝒊 − 𝑪𝒊 ≥ 𝟎).

La solution de base réalisable qui maximise la fonction objectif est:𝑥1 =
12, 𝑥2 =12 , 𝒔𝟑 = 100, 𝒔𝟓 = 20, 𝒔𝟓 = 6 et le maximum de la fonction
objectif est 26400dhs
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode M
Dans cette méthode, nous avons également besoin de variables
artificielles pour déterminer la solution initiale de base réalisable. La
méthode M est expliquée dans les exemples suivants.
Exemple 1:
25 29
Maximiser 𝑓 𝑥1 ,𝑥2 = − 𝑥1 − 𝑥2
2 2
Sous réserve

𝑥1 + 𝑥2 − 𝑠3 = 2000
40𝑥1 + 75𝑥2 − 𝑠4 = 100000
75𝑥1 + 100𝑥2 + 𝑠5 = 200000
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3 ,0 ≤ 𝑠4 ,0 ≤ 𝑠5 et 0 ≤ 𝑠6

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
Introduire les variables artificielles 𝑎6 et 𝑎7 afin de fournir une solution
de base réalisable dans la première et deuxième contrainte. La fonction
objectif est révisée en utilisant un grand nombre positif, par exemple
M. Ainsi, au lieu du problème original, on considère le problème
suivant:
25 29
Maximiser 𝑧 = − 𝑥1 − 𝑥2 − 𝑀(𝑎6 + 𝑎7 )
2 2
Sous réserve
𝑥1 + 𝑥2 − 𝑠3 + 𝑎6 = 2000
40𝑥1 + 75𝑥2 − 𝑠4 + 𝑎7 = 100000
75𝑥1 + 100𝑥2 + 𝑠5 = 200000
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑥3 ,0 ≤ 𝑠4 ,0 ≤ 𝑠5 , 0 ≤ 𝑠6 , 0 ≤ 𝑎6
𝑒𝑡0 ≤ 𝑎7

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
Les coefficients de 𝑎6 et 𝑎7 sont un grand nombre négatif (-M) dans la
fonction objectif. Puisque la fonction objectif doit être maximisée par
la solution optimale, les variables artificielles seront nulles. Par
conséquent, les variables de base de la solution optimale sont des
variables autres que les variables artificielles et donc une solution de
base faisable du problème original.
The successive calculation of simplex tables is as follows:
VB 𝑪𝒊 -12,5 -14,5 0 0 0 -M -M 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝑎6 -M 1 1 -1 0 0 1 0 2000
𝑎7 -M 40 75 0 -1 0 0 1 100000
𝒔𝟓 0 75 100 0 0 1 0 0 200000

𝒁𝒊 − 𝑪𝒊 −41𝑀 −76M M M 0 0 0
+ 12,5 +14,5
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode M
Comme M est un grand nombre positif, le coefficient de M dans la
ligne 𝒁𝒊 − 𝑪𝒊 décidera de la variable de base entrante. Comme
− 76𝑀 < −41𝑀, 𝒙𝟐 devient une variable de base dans l'itération
suivante en remplaçant 𝑎7 .
La variable artificielle 𝑎7 ne peut pas être réintroduite comme variable
de base.:
VB 𝑪𝒊 -12,5 -14,5 0 0 0 -M -M 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝑎6 -M 1 1 -1 0 0 1 0 2000
𝑎7 -M 40 75 0 -1 0 0 1 100000
𝒔𝟓 0 75 100 0 0 1 0 0 200000

𝒁𝒊 − 𝑪𝒊 −41𝑀 −76M M M 0 0 0
+ 12,5 +14,5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
V 𝑪𝒊 -12,5 -14,5 0 0 0 -M -M 𝑩
B
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝑎6 -M 7/15 0 - 1/75 0 1 0 2000/3

1
𝒙𝟐 -14,5 8/15 1 0 -1 0 0 1 4000/3
𝒔𝟓 0 65/3 0 0 0 1 0 0 200000/3
𝒁𝒊 − 𝑪𝒊 −7/15𝑀 0 M -M/75+ 0 0 0
+ 143/30 29/150

Ensuite 𝒙𝟏 devient une variable de base remplaçant 𝑎6 , la colonne

relative à 𝑎7 sera ignorée dans les calculs suivants. Comme 𝑎7 , la
variable 𝑎6 est aussi une variable artificielle, elle ne peut donc pas être
𝑀 29
réintroduite dans le tableau. Donc on ignore le signe de -75+ 150

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
V 𝑪𝒊 -12,5 -14,5 0 0 0 -M -M 𝑩
B
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝑥1 -12,5 1 0 -15/7 1/35 0 1 0 10000/7

𝒙𝟐 -14,5 0 1 8/7 -1/35 0 0 1 4000/7
𝒔𝟓 0 0 0 325/7 16/21 1 0 0 250000/7
𝒁𝒊 − 𝑪𝒊 0 0 143/14 2/35 0 0 0

Dans ce tableau 1 tous les 𝒁𝒊 − 𝑪𝒊 ≥ 0 . Ainsi, la solution du problème

est :
𝑥1 = 10000/7 = 1428,57 et 𝒙𝟐 = 4000/7 = 571,42 et
La valeur minimale de la fonction objectif est : 26142,85

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
Exemple 2

Maximiser 𝑓 𝑥1 ,𝑥2 = 1000𝑥1 + 1200𝑥2

Sous réserve

10𝑥1 + 5𝑥2 ≤ 200

2𝑥1 + 3𝑥2 = 60
𝑥1 ≤ 12
𝑥2 ≥ 6
0 ≤ 𝑥1 , 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
L’ajout de variables d’écart ou d’excédent transforme le modèle
précédent au modèle suivant :

Maximiser 𝑧 = 1000𝑥1 + 1200𝑥2

Sous réserve
10𝑥1 + 5𝑥2 + 𝑠3 = 200
2𝑥1 + 3𝑥2 = 60
𝑥1 + 𝑠4 = 12
𝑥2 − 𝑠5 =6
0 ≤ 𝑥1 , 0 ≤ 𝑥2 ,0 ≤ 𝑠3 ,0 ≤ 𝑠4 𝑒𝑡 0 ≤ 𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
Le problème initial sera transformé lors de l’utilisation de la méthode
M du fait que la fonction objectif va intégrer les variables 𝑎6 et 𝑎7
multipliés par un coefficient M et sera définie comme suit:
Maximiser 𝑧 = 1000𝑥1 + 1200𝑥2 − 𝑀(𝑎6 + 𝑎7 )

Les contraintes se présentent comme suit:

10𝑥1 + 5𝑥2 + 𝑠3 = 200
2𝑥1 + 3𝑥2 + 𝑎6 = 60
𝑥1 + 𝑠4 = 12
𝑥2 − 𝑠5 + 𝑎7 =6
0 ≤ 𝑥1 , 0 ≤ 𝑥2 ,0 ≤ 𝑠3 ,0 ≤ 𝑠4 𝑒𝑡 0 ≤ 𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
La présentation sous forme de tableau est comme suit:
VB 𝐶𝑖 1000 1200 0 0 0 -M -M 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝒔𝟑 0 10 5 1 0 0 0 0 200
𝑎6 -M 2 3 0 0 0 1 0 60
𝒔𝟒 0 1 0 0 1 0 0 0 12

𝑎7 -M 0 1 0 0 -1 0 1 6

𝒁𝒊 − 𝑪𝒊 −2M −4M 0 0 M 0 0
-1000 -1200

Et comme −4M -1200≤ −2M −1000, 𝒙𝟐 est la premiére variable de

base (variable d’entrée).

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
𝒙𝟐 devient une variable de base et 𝑎7 devient une variable
200 60 6
hors base dans l'itération suivante puisque (min( , , ) =
5 3 1
6). D’autres part, la variable 𝑎7 ne sera plus utilisée pour les
prochaine itération et sera supprimée du tableau.
VB 𝑪𝒊 1000 1200 0 0 0 -M -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝒔𝟑 0 10 0 1 0 5 0 0 170
𝑎6 -M 2 0 0 0 3 1 0 42
𝒔𝟒 0 1 0 0 1 0 0 1 12

𝒙𝟐 1200 0 1 0 0 -1 0 0 6

𝒁𝒊 − 𝑪𝒊 −2𝑀 0 0 0 -3M- 0 0
− 1000 1200
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode M
Le tableau précédent montre que 𝒔𝟓 devient une variable de base et 𝑎6
devient une variable hors base dans l'itération suivante, puisque
170 42
(min( 5 , 3 ) = 14). la variable 𝑎6 ne sera plus utilisée pour les
prochaine itération et sera supprimée du tableau

VB 𝑪𝒊 1000 1200 0 0 0 -M -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7

𝒔𝟑 0 20/3 0 1 0 0 -5 0 100
𝑠5 0 2/3 0 0 0 1 1/3 0 14
𝒔𝟒 0 1 0 0 1 0 0 1 12
𝒙𝟐 1200 2/3 1 0 0 0 1 0 20
𝒁𝒊 − 𝑪𝒊 -200 0 0 0 0 0 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode M
Le tableau précédent montre que 𝑍1 − 𝐶1 = −200 ≤ 0, donc 𝑥1 est une
100 14 12 20
variable entrante et 𝑠4 est une variable hors base (min( 20 , 2 , 1 , 2 )=12).
3 3 3
Donc 𝒔𝟒 est la nouvelle variable hors base
VB 𝑪𝒊 1000 1200 0 0 0 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 0 0 1 -20/3 0 20

𝑠5 0 0 0 0 -2/3 1 6
𝒙𝟏 1000 1 0 0 1 0 12
𝒙𝟐 1200 0 1 0 -2/3 0 12

𝒁𝒊 − 𝑪𝒊 0 0 0 200 0

Le calcul se termine à ce stade puisque (𝒁𝒊 − 𝑪𝒊 ≥ 𝟎). La solution de

base qui maximise la fonction objectif est: 𝑥1 = 12, 𝑥2 =12, 𝒔𝟑 = 20,
𝒔𝟓 = 6 et le maximum de la fonction objectif est 26400dhs
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solutions multiples
La méthode du simplexe permet également d'identifier les solutions
multiples d'un problème de programmation linéaire. Cette méthode est
expliqué à l'aide de l'exemple suivant.
Maximiser 𝑧 = 2000𝑥1 + 3000𝑥2
Sous réserve
6𝑥1 + 9𝑥2 ≤ 100
2𝑥1 + 𝑥2 ≤ 20
0 ≤ 𝑥1 , 0 ≤ 𝑥2
Solution
Introduisez les variables muettes 𝑠3 et 𝑠4 , de sorte que les inégalités
puissent être converties en équations comme suit:
6𝑥1 + 9𝑥2 + 𝑠3 = 100
2𝑥1 + 𝑥2 + 𝑠4 = 20
0 ≤ 𝑥1 , 0 ≤ 𝑥2 0 ≤ 𝑠3 , 0 ≤ 𝑠4
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solutions multiples
Le calcul de la procédure simple et les tableaux sont les suivants :

VB 𝑪𝒊 2000 3000 0 0 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒

𝒔𝟑 0 6 9 1 0 100

𝑠4 0 2 1 0 1 20
𝒁𝒊 − 𝑪𝒊 −2000 −3000 0 0

En entrant 𝒙𝟐 et en sortant 𝒔𝟑 en obtient le tableau suivant:

VB 𝑪𝒊 2000 3000 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒

𝑥2 3000 2/3 1 1/9 0 100/9

𝑠4 0 4/3 0 -1/9 1 80/9

𝒁𝒊 − 𝑪𝒊 0 0 1000/ 3 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions multiples
Ici, 𝒁𝒊 − 𝑪𝒊 ≥ 0 pour toutes les variables de sorte que nous ne pouvons
plus améliorer le tableau simplex. Par conséquent, il est optimale.
La solution optimale est 𝒙𝟏 = 0, 𝒙𝟐 = 100/9 et la valeur maximale de la
fonction objectif est : 3000*100/9=100000/3 = 33333,33.
Cependant, la valeur 𝒁𝟏 − 𝑪𝟏 correspondant à la variable hors base 𝒙𝟏
est également nulle. Cela indique qu'il existe plus d'une solution
optimale pour le problème.
Afin de calculer la valeur de la solution optimale alternative, nous
devons introduire 𝒙𝟏 comme variable de base en remplaçant 𝑠4 . Le
tableau 3 suivant montre le calcul de cette valeur.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions multiples

VB 𝑪𝒊 2000 3000 0 0 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒
𝑥2 3000 0 1 1/6 0 20/3
𝒙𝟏 2000 1 0 -1/12 3/4 20/3
𝒁𝒊 − 𝑪𝒊
Solutions
0
multiples
0 1000/ 3 0

Ainsi, 𝒙𝟏 = 20/3, 𝒙𝟐 = 20/3 maximisent également la fonction objectif

et la valeur maximale de la fonction objectif est : 100000/3 = 33333.33.
Ainsi, le problème a plusieurs solutions.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions optimales multiples

Exemple 3:
maximiser 𝑓 𝑥1 ,𝑥2 = 120𝑥1 + 160𝑥2
Sous réserve
3𝑥1 + 4𝑥2 ≤ 2400
2𝑥1 + 𝑥2 ≤ 2000
5𝑥1 + 3𝑥2 ≤ 2900
0 ≤ 𝑥1 et 0 ≤ 𝑥2
Solution
Introduisez les variables muettes 𝑠3 et 𝑠4 , de sorte que les inégalités
puissent être converties en équations comme suit:
3𝑥1 + 4𝑥2 + 𝑠3 = 2400
2𝑥1 + 𝑥2 + 𝑠4 = 2000
5𝑥1 + 3𝑥2 + 𝑠5 = 2900
0 ≤ 𝑥1 , 0 ≤ 𝑥2 0 ≤ 𝑠3 , 0 ≤ 𝑠4
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solutions multiples
Le calcul de la procédure simple et les tableaux sont les suivants :
VB 𝑪𝒊 120 160 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒔𝟑 0 3 4 1 0 0 2400
𝑠4 0 2 1 0 1 0 2000

𝑠5 0 5 3 0 0 1 2900

𝒁𝒊 − 𝑪𝒊 −120 −160 0 0 0

VB 𝑪𝒊 120 160 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓

𝒙𝟐 160 3/4 1 1/4 0 0 600

𝑠4 0 5/4 0 -1/4 1 0 1400

𝑠5 0 11/4 0 -3/4 0 1 1100

𝒁𝒊 − 𝑪𝒊 0 0 0 0 0
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solutions multiples
Ici, 𝒁𝒊 − 𝑪𝒊 ≥ 0 pour toutes les variables de sorte que nous ne pouvons
plus améliorer le tableau simplex. Par conséquent, il est optimale.
La solution optimale est 𝒙𝟏 = 0, 𝒙𝟐 = 600 et la valeur maximale de la
fonction objectif est : 160*600=96000.
Cependant, la valeur 𝒁𝟏 − 𝑪𝟏 correspondant à la variable hors base 𝒙𝟏
est également nulle. Cela indique qu'il existe plus d'une solution
optimale pour le problème.
Afin de calculer la valeur de la solution optimale alternative, nous
devons introduire 𝒙𝟏 comme variable de base en remplaçant
1400 1100
𝑠5 (min( 5 , 11 )=400)
4 4
Le tableau 3 suivant montre le calcul de cette valeur.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solutions multiples
Le calcul de la procédure simple et les tableaux sont les suivants :
VB 𝑪𝒊 120 160 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓
𝒙𝟐 160 0 1 5/11 0 -3/11 300

𝑠4 0 0 0 1/11 1 -5/11 900

𝒙𝟏 120 1 0 -3/11 0 4/11 400

𝒁𝒊 − 𝑪𝒊 0 0 0 0 0

Ainsi, 𝒙𝟏 = 400, 𝒙𝟐 = 300 maximisent également la fonction objectif et

la valeur maximale de la fonction objectif est : 120*400+160*300 =
960000. Ainsi, le problème a plusieurs solutions.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non bornée

Dans cette section, nous allons voir comment la méthode du simplexe
est utilisée pour identifier la solution non bornée. Cette méthode est
expliqué à l'aide de l'exemple suivant.
Exemple 3:
maximiser 𝑓 𝑥1 ,𝑥2 = 5𝑥1 + 4𝑥2
Sous réserve
𝑥1 − 𝑥2 ≤ 8
𝑥1 ≤ 7
0 ≤ 𝑥1 et 0 ≤ 𝑥2
Solution :
Introduire les variables molles 𝒔𝟑 et 𝑠4 , de sorte que les inégalités
deviennent des équations comme suit :
𝑥1 − 𝑥2 + 𝑠3 = 8
𝑥1 + 𝑠4 = 7
0 ≤ 𝑥1 , 0 ≤ 𝑥2 , 0 ≤ 𝑠3 , 0 ≤ 𝑠4
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Solution non bornée

Les procédures et les tables de calcul du simplex sont les suivantes :
VB 𝑪𝒊 5 4 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒
𝒔𝟑 0 1 -1 1 0 8

𝑠4 0 1 0 0 1 7

𝒁𝒊 − 𝑪𝒊 −5 −4 0 0

VB 𝑪𝒊 5 4 0 0 𝑩

𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒

𝒔𝟑 0 0 -1 1 -1 1

𝑥1 5 1 0 0 1 7
𝒁𝒊 − 𝑪𝒊 0 −4 0 5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non bornée

Notez que 𝒁𝟐 − 𝑪𝟐 < 0 ce qui indique que 𝒙𝟐 doit être introduit comme
variable de base dans la prochaine itération. Cependant, les deux 𝒂𝟏𝟐 =
− 1≤0, 𝒂𝟐𝟐 = 0≤0.
Ainsi, il n'est pas possible de poursuivre plus avant la méthode de
calcul du simplexe car nous ne pouvons pas décider quelle variable sera
hors base à la prochaine itération. C'est le critère de la solution non
bornée.
NOTE : Si au cours du calcul du simplexe, 𝒁𝒋 − 𝑪𝒋 < 0 mais 𝒂𝒊𝒋 ≤ 0
pour tous les 𝑖, alors le problème n'a pas de solution finie.
Mais dans ce cas, nous pouvons observer que la variable 𝒙𝟐 est sans
contrainte et peut être augmentée arbitrairement.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non réalisable

Cette section illustre comment identifier la solution infaisable à l'aide
de la méthode du simplexe. Ceci est expliqué à l'aide de l'exemple
suivant.

Exemple 5:
Minimiser 𝑓 𝑥1 ,𝑥2 = 200𝑥1 + 300𝑥2
Sous réserve
2𝑥1 + 3𝑥2 ≥ 1200
𝑥1 + 𝑥2 ≤ 400
2𝑥1 + 3/2𝑥2 ≥ 1800
0 ≤ 𝑥1 et 0 ≤ 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non réalisable

Solution
Comme il s'agit d'un problème de minimisation, nous devons le
convertir en un problème de maximisation et introduire les variables
d’écart, de surplus et les variables artificielles. Après avoir effectué
toutes ces opérations, le problème se présente de la manière suivante:
Maximiser 𝑓 𝑥1 ,𝑥2 = −200𝑥1 − 300𝑥2
Sous réserve
2𝑥1 + 3𝑥2 − 𝑠3 + 𝑎6 = 1200
𝑥1 + 𝑥2 + 𝑠4 = 400
2𝑥1 + 3/2𝑥2 − 𝑠5 + 𝑎7 = 900
𝑥1 , 𝑥2 , 𝑠3 , 𝑠4 , 𝑠5 , 𝑎6, 𝑎7 ≥ 0

Ici, les variables 𝑎6 et 𝑎7 sont des variables artificielles. Nous utilisons

une méthode à deux phases pour résoudre ce problème

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Solution non réalisable

Phase I
Maximiser 𝑓 𝑥1 ,𝑥2 = −𝑎6 − 𝑎7
Sous réserve
2𝑥1 + 3𝑥2 − 𝑠3 + 𝑎6 = 1200
𝑥1 + 𝑥2 + 𝑠4 = 400
2𝑥1 + 3/2𝑥2 − 𝑠5 + 𝑎7 = 900
𝑥1 , 𝑥2 , 𝑠3 , 𝑠4 , 𝑠5 , 𝑎6, 𝑎7 ≥ 0

VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝑎6 -1 2 3 -1 0 0 1 0 1200
𝒔𝟒 0 1 1 0 1 0 0 0 400
𝑎7 -1 2 3/2 0 0 -1 0 1 900
𝒁𝒊 − 𝑪𝒊 −4 −9/2 1 0 1 0 0
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Méthode à deux phases

Comme la valeur minimale de la fonction objective de la
phase 1 est nulle à la fin de la phase 1, 𝑎6 et 𝑎7 deviennent
tous deux nuls.
VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝒙𝟐 0 2/3 1 -1/3 0 0 1/3 0 400
𝒔𝟒 0 1/3 0 1/3 1 0 -1/3 0 0
𝑎7 -1 1 0 1/2 0 -1 -1/2 1 300
𝒁𝒊 − 𝑪𝒊 −1 0 -1/2 0 1 3/2 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthode à deux phases

Ici, 𝒙𝟏 devient une variable de base et 𝑠4 devient une variable hors base
0 300
dans l'itération suivante (min( 1 , 1 ) = 0).
3
VB 𝑪𝒊 0 0 0 0 0 -1 -1 𝑩
𝐶𝑉𝐵𝑖 𝒙𝟏 𝒙𝟐 𝒔𝟑 𝒔𝟒 𝒔𝟓 𝑎6 𝑎7
𝒙𝟐 0 0 1 -1 -2 0 1/3 0 400
𝒙𝟏 0 1 0 1 3 0 -1/3 0 0
𝑎7 -1 0 0 -1/2 -3 -1 -1/2 1 300
𝒁𝒊 − 𝑪𝒊 0 0 1/2 3 1 3/2 0

Notez que 𝒁𝒊 − 𝑪𝒊 ≥ 0 pour toutes les variables mais la variable

artificielle 𝑎7 est toujours une variable de base. Cette situation indique
que le problème n'a pas de solution réalisable.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La programmation linéaire
Problème Dual

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Définition
Deux problèmes d’optimisation sont dits en dualité si l’un est
un problème de maximisation, l’autre un problème de
minimisation et si résoudre l’un équivaut à résoudre l’autre,
dans le sens où la solution optimale de l’un se déduit de la
solution optimale de l’autre.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Définition
La notion de dualité permet de montrer qu’un problème d’allocation
optimale de ressources rares:
Maximiser 𝑓 𝑥1 ,𝑥2 = 60𝑥1 + 70𝑥2
Sous réserve
2𝑥1 + 𝑥2 ≤ 300
3𝑥1 + 4𝑥2 ≤ 509
4𝑥1 + 7𝑥2 ≤ 812
0 ≤ 𝑥1 et 0 ≤ 𝑥2
Est associé à un problème de tarification optimale de ressources:
Minimiser 𝑓 𝑦1 ,𝑦2 , 𝑦3 = 300𝑦1 + 509 𝑦2 +812𝑦3
Sous réserve
2𝑦1 + 3 𝑦2 +4𝑦3 ≥ 60
𝑦1 + 4 𝑦2 +7𝑦3 ≥ 70
0 ≤ 𝑦1 ,𝑦2 , 𝑦3

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Définition
La notion de dualité permet de montrer qu’un problème d’allocation
optimale de ressources rares:
Maximiser 𝑓 𝑥1 ,𝑥2 = 60𝑥1 + 70𝑥2
Sous réserve
2𝑥1 + 𝑥2 ≤ 300
3𝑥1 + 4𝑥2 ≤ 509
4𝑥1 + 7𝑥2 ≤ 812
0 ≤ 𝑥1 et 0 ≤ 𝑥2
Est associé à un problème de tarification optimale de ressources:
Minimiser 𝑓 𝑦1 ,𝑦2 , 𝑦3 = 300𝑦1 + 509 𝑦2 +812𝑦3
Sous réserve
2𝑦1 + 3 𝑦2 +4𝑦3 ≥ 60
𝑦1 + 4 𝑦2 +7𝑦3 ≥ 70
0 ≤ 𝑦1 ,𝑦2 , 𝑦3

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Construction du dual d’un programme linéaire

La dualité des problème linaire est la traduction

mathématique de la dualité quantité-prix qui permet de
considérer un problème d’allocation des ressources de deux
façons équivalentes:
- Soit comme une détermination des niveaux optimaux des
activités en optimisant les quantités
- Soit comme la valorisation optimale des ressources en
déterminants les prix optimaux.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

forme matricielle d’un problème linéaire

Forme primale Forme dual

Fonction objectif Max Z= 𝐶 𝑡 X Min W= 𝐵𝑡 Y

contraintes 𝐴𝑋 ≤ 𝐵 𝐴𝑇 𝑌 ≥ 𝐶
𝑋≥0 𝑌≥0

𝐴𝑇 est le transposé de la matrice A

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Correspondance Dual/Primal
Le tableau suivant fixe les règles de passage d’un problème
linéaire à son Dual:
Forme primale Forme dual
Fonction Max Z= 𝐶 𝑡 X Min W= 𝐵 𝑡 Y
objectif 𝐶=𝑐𝑖 , 𝑖 = 1, … , 𝑛 𝐵=𝑏𝑗 , 𝑗 = 1, … , 𝑝
variables Variable 𝑥𝑖 ≥ 0 Contrainte i ≥ 𝑐𝑖
Variable 𝑥𝑖 ≤ 0 Contrainte i ≤ 𝑐𝑖
Variable 𝑥𝑖 sans Contrainte i = 𝑐𝑖
restriction de signe
Contraintes Contrainte 𝑗 ≤ 𝑐𝑖 Variable 𝑦𝑖 ≥ 0
Contrainte i ≥ 𝑐𝑖 Variable 𝑦𝑖 ≤ 0
Contrainte i = 𝑐𝑖 Variable 𝑦𝑖 sans restriction
de signe
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Construction du dual d’un programme linéaire

Remarque :
La résolution d’un problème de minimisation par la méthode
de simplexe n’est pas toujours simple dans la mesure où la
plupart des contraintes sont de type supérieur ou égal (≥). Ce
qui signifié l’absence d’une solution de base réalisable de
départ évidente.
En effet, il faut introduire des variables artificielles ce qui
complique le processus de résolution.
De ce fait, l’utilisation du problème dual permet de dépasser
ce problème.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Fondement théorique de la relation primaire/dual

A tout programme linéaire, on peut faire correspondre un autre

programme linéaire, dual du premier (celui–ci étant appelé primal).
Cette transformation associe à chaque variable du primal une contrainte
du dual et donc une variable d’écart (si le problème ne contient pas de
contrainte d’égalité). Elle associe à chaque contrainte du primal
une variable du dual.

Proposition :

Le dual d’un dual est un programme linéaire équivalent au primal

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Construction du dual d’un programme linéaire

Exemple 1:
Deux usines A et B produisent des produits 𝑃1 , 𝑃2 ,𝑃3 de trois qualités
différentes. Elles ont des commandes pour chaque type de produis : la
compagnie qui gère les usines a des contrats pour fournir 16 tonnes de
𝑃1 , 5 tonnes de 𝑃2 et 20 tonnes de 𝑃3 . Il coûte 1000 euros par jour pour
faire fonctionner l’usine A et 2000 euros par jour pour l’usine B.
L’usine A produit 8 tonnes de 𝑃1 , 1 tonne de 𝑃2 et 2 tonnes de 𝑃3 par
jour. L’usine B produit 2 tonnes de 𝑃1 , 1 tonne de 𝑃2 et 7 tonnes de 𝑃3
par jour. On cherche combien de jours chaque usine doit fonctionner
afin de satisfaire la demande de la façon la plus économique.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Construction du dual d’un programme linéaire

Le programme linéaire est un exemple de programme de satisfaction de
demande. Les variables 𝑥1 et 𝑥2 représentent les nombres de jours de
fonctionnement des usines A et B.

Minimiser 𝑓 𝑥1 ,𝑥2 = 1000𝑥1 + 2000𝑥2

Sous réserve
8𝑥1 + 2𝑥2 ≥ 16
𝑥1 + 𝑥2 ≥ 5
2𝑥1 + 7𝑥2 ≥ 20
0 ≤ 𝑥1 , 𝑥2

La contrainte 1 concerne la qualité inférieure, la deuxième contrainte

concerne la qualité moyenne et la troisième concerne la qualité
supérieure
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Construction du dual d’un programme linéaire

Pour former le programme Pour former le programme dual, la matrice
linéaire dual on commence par A est remplacer par le transposer de A, le
former la matrice des vecteur de la fonction objectif est remplace
coefficients des contraintes et par son transposer est prend la position du
de l’objectif avec seconds vecteur B et le vecteur B est remplacé par
membres. On place la ligne de son transposé et prend la place de la
l’objectif en bas. fonction objectif.

Fonction objectif Transposé de B Transposé

Vecteur (nouvelle fonction objectif) fonction
1000 2000 B
objectif
16 5 20
8 2 16
8 1 2 1000
1 1 5
2 1 7 2000
2 7 20
Transposé matrice A Nouvelle
Matrice A
vecteur B

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Construction du dual d’un programme linéaire

Le dual est obtenu en utilisant les règles de transformation définies en
haut concernant le signe de variable et le sens des inégalités des
contraintes, comme suit:

Maximiser 𝑊 = 16𝑦1 + 5𝑦2 + 20𝑦3

Sous réserve
8𝑦1 + 𝑦2 + 2𝑦3 ≤ 1000
2𝑦1 + 𝑦2 + 7𝑦3 ≤ 2000
0 ≤ 𝑦1 , 𝑦2 , 𝑦3

La contrainte 1 concerne l’usine A et la deuxième contrainte concerne

l’usine B.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Proposition :
A chaque variable du primal 𝑥𝑖 correspond une variable d’écart du dual
𝑠𝑗 . La valeur de 𝑥𝑖 dans la solution optimale du primal est égale à 𝑧𝑗 −
𝑐𝑗 qui correspond à 𝑠𝑗 dans le tableau de simplexe final du dual.
Théorème 7 (théorème des écarts complémentaires) :
On considère un programme linéaire comportant 𝑛 variables 𝑥1 , . . . , 𝑥𝑛
et 𝑚 contraintes. Son dual comporte 𝑚 variables 𝑦1 , . . . , 𝑦𝑚 et 𝑛
contraintes.
A chaque variable 𝑥𝑖 correspond une variable d’écart 𝑦𝑚+𝑖 . A chaque
variable 𝑦𝑖 correspond une variable d’écart 𝑥𝑛+𝑖 . Soient 𝑋(𝑥1 ,…..𝑛) une
solution réalisable du premier et 𝑌(𝑦1 ,…..𝑦𝑚 )une solution réalisable du
second. Les solutions réalisables 𝑋 et 𝑌 sont optimales si et seulement
si :
𝑥𝑖 𝑦𝑚+𝑖 = 𝑦𝑗 𝑥𝑛+𝑗 = 0 pour tous 1 ≤ i ≤ n et 1 ≤ j ≤ m.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Pour ce problème, à la variable 𝑥1 du primal correspond la contrainte ‘
usine A ‘ du dual et donc la variable d’écart 𝑠4 et à la variable 𝑥2 du
primal correspond la contrainte « usine B » du dual et donc la variable
d’écart 𝑠5 :

Maximiser 𝑊 = 16𝑦1 + 5𝑦2 + 20𝑦3

Sous réserve
8𝑦1 + 𝑦2 + 2𝑦3 + 𝑠4 = 1000
2𝑦1 + 𝑦2 + 7𝑦3 + 𝑠5 = 2000
0 ≤ 𝑦1 , 𝑦2 , 𝑦3

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
La solution du problème dual

𝑐𝑖 16 5 20 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑦3 𝑠4 𝑠5

𝑠4 0 8 1 2 1 0 1000

𝑠5 0 2 1 7 0 1 2000

𝑧𝑖 -𝑐𝑖 -16 -5 -20 0 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Min(𝑧𝑖 -𝑐𝑖 < 0)=-20 et min (1000/2, 2000/7)= 2000/7 donc 𝑦3 est la
variable d’entrée et 𝑠5 est la variable de sortie.
𝑐𝑖 16 5 20 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑦3 𝑠4 𝑠5

𝑠4 0 52/7 5/7 0 1 -2/7 3000/7

𝑦3 20 2/7 1/7 1 0 1/7 2000/7

𝑧𝑖 -𝑐𝑖 -72/7 -15/7 0 0 20/7

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Min(𝑧𝑖 -𝑐𝑖 < 0)= -72/7et min (3000/52,1500 )=3000/52 donc 𝑦1 est la
variable d’entrée et 𝑠4 est la variable de sortie.

𝑐𝑖 16 5 20 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑦3 𝑠4 𝑠5

𝑦1 16 1 5/52 0 7/52 -2/52 3000/52

𝑦3 20 0 6/52 1 -2/52 8/52 14000/52

𝑧𝑖 -𝑐𝑖 0 -60/52 0 2/52 128/52

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Min(𝑧𝑖 -𝑐𝑖 < 0)= -60/52 et min (3000/5,14000/6 )=3000/5 donc 𝑦2 est la
variable d’entrée et 𝑦1 est la variable de sortie.

𝑐𝑖 16 5 20 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑦3 𝑠4 𝑠5

𝑦2 5 52/5 1 0 7/5 -2/5 600

𝑦3 20 -6/52 6/52 1 -1/5 1/5 200

𝑧𝑖 -𝑐𝑖 438/13 120/52 0 3 2
La solution optimale du problème dual est (𝑦1 =0, 𝑦2 =600, 𝑦3 =200).
Donc max 16𝑦1 + 5𝑦2 + 20𝑦3 = 7000
La solution optimale du problème primaire est (𝑥1 = 𝑧4 -𝑐4 𝑠4 =3,
𝑥2 = 𝑧5 -𝑐5 𝑠5 =2). Donc min 1000𝑥1 + 2000𝑥2 = 7000
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Relations primal/dual
En utilisant la théorème des écarts complémentaires on a:
Maximiser 𝑊 = 16𝑦1 + 5𝑦2 + 20𝑦3
Sous réserve
8𝑦1 + 𝑦2 + 2𝑦3 + 𝑦4 = 1000
2𝑦1 + 𝑦2 + 7𝑦3 + 𝑦5 = 2000
0 ≤ 𝑦1 , 𝑦2 , 𝑦3
Minimiser 𝑓 𝑥1 ,𝑥2 = 1000𝑥1 + 2000𝑥2
Sous réserve
8𝑥1 + 2𝑥2 − 𝑥3 =16
𝑥1 + 𝑥2 −𝑥4 = 5
2𝑥1 + 7𝑥2 −𝑥5 20
0 ≤ 𝑥1 , 𝑥2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
D’où:
𝑥1 𝑦4 = 0
𝑥2 𝑦5 = 0
𝑥3 𝑦1 = 0
𝑥4 𝑦2 = 0
𝑥5 𝑦3 = 0
La solution du problème dual est (𝑦1 =0, 𝑦2 =600, 𝑦3 =200) donc 𝑥4 =
𝑥5 =0
D’où
𝑥1 + 𝑥2 = 5
2𝑥1 + 7𝑥2 = 20
D’où
2(5 − 𝑥2 ) + 7𝑥2 = 20 donc 𝑥2 =2 et en conséquence 𝑥1 =3 et 𝑥2 =2 d’où
Minimiser 𝑓 𝑥1 ,𝑥2 = 1000𝑥1 + 2000𝑥2 =7000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Exemple 2:
Soit le problème primaire suivant:
min 𝑍 = 8𝑥1 + 7𝑥2 + 3𝑥3
Sous réserve
2𝑥1 + 𝑥2 ≥ 4000
𝑥1 + 2𝑥2 + 𝑥3 ≥ 5000
0 ≤ 𝑥1 , 𝑥2 , 𝑥3
Le problème dual s’écrit
max 𝑊 = 4000𝑦1 + 5000𝑦2
Sous réserve
2𝑦1 + 𝑦2 ≤ 8
𝑦1 + 2𝑦2 ≤ 7
𝑦2 ≤ 3
0 ≤ 𝑦1 , 𝑦2

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Soit 𝑠4 , 𝑠5 , 𝑠6 les variables d’écarts relatives au trois contraintes:

max 𝑊 = 4000𝑦1 + 5000𝑦2
Sous réserve
2𝑦1 + 𝑦2 + 𝑠3 = 8
𝑦1 + 2𝑦2 + 𝑠4 = 7
𝑦2 + 𝑠5 = 3
0 ≤ 𝑦1 , 𝑦2 , 𝑦3
Donc
- 𝑥1 est associé à la variable d’écart 𝑠3
- 𝑥2 est associé à la variable d’écart 𝑠4
- 𝑥3 est associé à la variable d’écart 𝑠5

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Min(𝑧𝑖 -𝑐𝑖 < 0)=𝑧2 -𝑐2 =-5000 et min (8/1,7/2, 3/1 )=3 donc 𝑦2 est la
variable d’entrée et 𝑠5 est la variable de sortie.

𝑐𝑖 4000 5000 0 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑠3 𝑠4 𝑠5

𝑠3 0 2 1 1 0 0 8

𝑠4 0 1 2 0 1 0 7
𝑠5 0 0 1 0 0 1 3

𝑧𝑖 -𝑐𝑖 -4000 -5000 0 0 0

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual

𝑐𝑖 4000 5000 0 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑠3 𝑠4 𝑠5

𝑠3 0 2 0 1 0 -1 5

𝑠4 0 1 0 0 1 -2 1
𝑦2 5000 0 1 0 0 1 3

𝑧𝑖 -𝑐𝑖 -1500 0 0 0 5000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Min(𝑧𝑖 -𝑐𝑖 < 0)= 𝑧1 -𝑐1 =-4000 et min (5/2,1/1 )=1 donc 𝑦1 est la
variable d’entrée et 𝑠4 est la variable de sortie.

𝑐𝑖 4000 5000 0 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑠3 𝑠4 𝑠5
𝑠3 0 0 0 1 -2 3 3
𝑦1 4000 1 0 0 1 -2 1
𝑦2 5000 0 1 0 0 1 3
𝑧𝑖 -𝑐𝑖 -1500 0 0 4000 -3000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
Min(𝑧𝑖 -𝑐𝑖 < 0)= 𝑧5 -𝑐5 =-3000 et min (3/3,3/1 )=1 donc 𝑠5 est la
variable d’entrée et 𝑠3 est la variable de sortie.

𝑐𝑖 4000 5000 0 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑠3 𝑠4 𝑠5
𝑠3 0 0 0 1 -2 3 3
𝑦1 4000 1 0 0 1 -2 1
𝑦2 5000 0 1 0 0 1 3
𝑧𝑖 -𝑐𝑖 0 0 0 4000 -3000

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
𝑐𝑖 4000 5000 0 0 0
VB 𝑏𝑖
𝐶𝑉𝐵𝑖 𝑦1 𝑦2 𝑠3 𝑠4 𝑠5
𝑠5 0 0 0 1/3 -2/3 1 1
𝑦1 4000 1 0 2/3 -1/ 3 0 3
𝑦2 5000 0 1 -1/3 2/3 0 2
𝑧𝑖 -𝑐𝑖 0 0 1000 2000 0

La solution optimale est (𝑦1 =3, 𝑦2 =2). Donc :

max 4000𝑦1 + 5000𝑦2 = 22000
La solution optimale du problème primaire est (𝑥1 = 𝑧3 -𝑐3 𝑠3 = 1000,
𝑥2 = 𝑧4 -𝑐4 𝑠4 =2000, 𝑥3 = 𝑧5 -𝑐5 𝑠5 = 0 ). Donc :
Min 8𝑥1 + 7𝑥2 + 3𝑥3 = 22000.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
En utilisant la théorème des écarts complémentaires on a:
max 𝑊 = 4000𝑦1 + 5000𝑦2
Sous réserve
2𝑦1 + 𝑦2 + 𝑠3 = 8
𝑦1 + 2𝑦2 + 𝑠4 = 7
𝑦2 + 𝑠5 = 3
0 ≤ 𝑦1 , 𝑦2

min 𝑍 = 8𝑥1 + 7𝑥2 + 3𝑥3

Sous réserve
2𝑥1 + 𝑥2 − 𝑔4 = 4000
𝑥1 + 2𝑥2 + 𝑥3 − 𝑔5 = 5000
0 ≤ 𝑥1 , 𝑥2 , 𝑥3

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Relations primal/dual
D’où:
𝑥1 𝑠3 = 0
𝑥2 𝑠4 = 0
𝑥3 𝑠5 = 0
𝑔4 𝑦1 = 0
𝑔5 𝑦2 = 0
La solution du problème dual est (𝑦1 =3, 𝑦2 =2) et 𝑠5 =1 donc
𝑔4 = 𝑔5 = 𝑥3 =0
D’où
2𝑥1 + 𝑥2 = 4000
𝑥1 + 2𝑥2 = 5000
D’où
2(5000 − 2𝑥2 ) + 𝑥2 = 4000 donc 𝑥2 =2000 et en conséquence
𝑥1 =1000 et 𝑥2 =2000 d’où
min 𝑍 = 8𝑥1 + 7𝑥2 + 3𝑥3 = 22000
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

Approches probabilistes

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Description du problème
Soit, X un indicateur de gestion mesurable (consommation,
profit, perte, commande,….).
Déterminer la valeur maximale de 𝑋 (𝑉𝑀𝑎𝑥 (𝑋))sur une
période 𝑇 telle que :
𝑃 𝑋 ≤ 𝑉𝑀𝑎𝑥 𝑋 =1−𝛼
Avec
1 − 𝛼 est la seuil de confiance.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

Méthodologie
La résolution de ce problème, se fera selon les étapes suivants:
- Considérer l’indicateur de gestion comme une variables aléatoire
𝑋.
- Déterminer la loi de distribution le plus approprié qui s’ajuste
avec 𝑋(la loi normale, lognormale, poisson, weibull, …etc).
- Estimer les paramètres de la loi de 𝑋
- Déterminer la valeur maximal en procédant par l’une des
méthode suivante:
• La méthode analytique en utilisant directement les
caractéristiques de la loi de 𝑋
• La méthode historiques en reproduisant le même
comportement historique.
• La méthode de simulation en simulant les valeurs possibles
en se basant sur les paramètres et la distribution de la loi de 𝑋
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

Définition:
Valeur attendue (EV)et valeur inattendue (UV) avec un seuil (1-𝛼)

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

1- Calcul de la valeur inattendue (𝑽𝑨):
Soit 𝑉𝑀𝑎𝑥 𝑋 définit par:
𝑃 𝑋 ≤ 𝑉𝑀𝑎𝑥 𝑋 = 1 − 𝛼
La valeur maximal au seuil 1 − 𝛼 est égale à:
𝑉𝑀𝑎𝑥(1−𝛼) = 𝐸𝑉 + 𝑈𝑉 1−𝛼
D’où 𝑃 𝑋 ≤ 𝐸𝑉 + 𝑈𝑉 (1−𝛼) = 1 − 𝛼
𝑃 𝑋 − 𝐸𝑉 ≤ 𝑈𝑉 (1−𝛼) = 1 − 𝛼
𝑋 − 𝐸𝑉 𝑈𝑉 (1−𝛼)
𝑃 ≤ =1−𝛼
𝜎𝑋 𝜎𝑋
𝑋−𝐸𝑉 𝑋−𝐸(𝑋)
On a 𝜎𝑋
= 𝜎𝑋
~𝑁 0,1
𝑈𝑉 (1−𝛼)
d’où =𝑍𝛼 donc
𝜎𝑋
𝑈𝑉 (1−𝛼) = 𝜎𝑋 𝑍𝛼
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

2- Approximation de Cornish –Fisher:
La normalité des indicateurs de gestion est
hypothèses forte et ce compte tenu des études
statistiques menées par les statisticiens ayant
montrées que :
- Les séries chronologiques ne sont pas
centrées
- Les queues de distribution sont plus
épaisses.
De ce fait, les événement rares sont sous
estimés par la loi normale. S 5 – 2022-2023
Pr. Mohamed Habachi Recherche opérationnelle 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

Pour résoudre ce problème on introduit l’approximation de
Cornish –Fisher:
2 𝑆 3 𝐾 3 𝑆2
Z=𝑧𝑐 +(𝑧𝑐 -1) +(𝑧𝑐 -3𝑧𝑐 ) -(2𝑧𝑐 -5𝑧𝑐 )
6 24 36
Avec :
𝑆: le coefficient d’asymétrie et
𝒏
(𝒙𝒊 − 𝑿)𝟑
𝑺=
(𝒏 − 𝟏)𝒔𝟑
𝒊=𝟏
𝐾: le coefficient d’aplatissement
𝒏
(𝒙𝒊 − 𝑿)𝟒
𝐾=
(𝒏 − 𝟏)𝒔𝟒
𝒊=𝟏
𝑧𝑐 : le quantile de la loi normale
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

3- La valeur inattendue sur une période 𝑇:
La valeur inattendue sur une période T n’est pas
proportionnelle à la valeur attendue d’une unité
de temps (heure, jours, mois, année) mais
définie en fonction du temps T écoulé comme
suit:
𝑈𝑉 𝑇,(1−𝛼) = 𝑈𝑉 (1−𝛼) ∗ 𝑇
𝑈𝑉 𝑇,(1−𝛼) = 𝜎𝑋 𝑍𝛼 ∗ 𝑇
Ou
𝑈𝑉 𝑇,(1−𝛼) = 𝜎𝑋 𝑍 ∗ 𝑇 (Cornish-Fisher)
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

4- Méthode historique:
Il s’agit d’exécuter un processus en trois étapes:
Étape 1: On stocke un historique des valeurs des indicateurs
de gestion ( commande, consommation, valeur portefeuille,
pertes, profits…).
Étapes 2: On considère les évolutions passées de ces
variables et on applique chacune de ces évolutions sur les
indicateurs à étudier.
Étapes 3: On obtient une série de valeurs possibles pour
l’indicateur et on détermine le percentile (1-𝛼) souhaité.
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

5- Méthode de simulation:
Pour la simulation nous allons présenter la simulation moyennant
Excel:
Etape 1: Simulation des valeurs de la fonction de la fonction de
répartition de la loi normale par la fonction Alea()
Etape 2: Simulation un nombre important des valeurs de la loi normale
par la fonction inverse de la loi normale. Sur Excel il faut exécuté la
fonction : [Link](I7;𝜇;𝜎)
Etape 3: déterminer le percentile 1-𝛼 en utilisant la fonction centile
(valeaurs, 1-𝛼 ), le résultat est la valeur recherchée.
alea() [Link](I7;2;3)
0,94203604 6,716292773
0,51084111 2,081533925
0,08108457 -2,193439799
CENTILE(J7:J11; 0,95)

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

6- exemple Valeur en risque(Value At Risk, VaR):
Définition du problème:
Supposons que nous avons un portefeuille , et que nous
voulons savoir quelle sera notre perte maximale pendant les
10 prochains jours avec une probabilité de 95%.
La quantité qui représente cette information est définie
comme la Valeur en risque (𝑉𝑎𝑅) à 95% pour un horizon de
10 jours.

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

5- exemple Valeur en risque:

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

5- exemple Valeur en risque :
Remarque :
la var est une mesure de la perte et elle est normalement
positif
La traduction mathématique de la VAR est donnée par la
formule suivante:

𝑉𝑎𝑅 𝛼 = inf{R/ P(perte ≤ −R) ≥ 𝛼}

Exemple:
Au bout d’un jour, il y a 100 évolutions possibles pour la
valeur du portefeuille = -50, -49, -48,……-2, -1, 1, 2,3…..48,
49, 50
Quelle est la var à 90% sur une journée
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

5- exemple Valeur en risque :
Approche analytique:
Dans l’approche analytique en suppose que variable
aléatoire perte et profit du porte feuille notée 𝑋 suit
la loi normale de moyenne 𝜇 et d’écart type 𝜎

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

5- exemple Valeur en risque :
Approche analytique:
Pour calculer la 𝑉𝑎𝑅, il faut déterminer 𝑍𝛼 à partir de la table
de la loi normale. En conséquence:
𝑋−μ −𝑉𝑎𝑅 − μ
𝑃 ≤ =𝛼
𝜎𝑋 𝜎𝑋
−𝑉𝑎𝑅 − μ
= 𝑍𝛼
𝜎𝑋
𝑉𝑎𝑅 = −𝑍𝛼 𝜎𝑋 – μ =𝑍1−𝛼 𝜎𝑋 – μ (𝑍𝛼 =-𝑍1−𝛼 )
𝑉𝑎𝑅𝑇 = 𝑉𝑎𝑅1 𝑇
Exemple: 𝜇=10000, 𝜎=25000 calculer la 𝑉𝑎𝑅 95%
90% 1.282 95% 1.645
99% 2.326 99.99% 3.62
Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1
 FSJES AGDAL- L.E

La modélisation par la loi normale

Exemple numérique: les pertes et les profits
journalières sont donnés par le tableau suivant
jour 1 2 3 4 5 6 7 8 9 10

Perte et
-100 60 -70 50 -40 80 -70 100 -80 90
profit
jour 11 12 13 14 15 16 17 18 19 20

Perte et
-60 110 120 -100 130 110 90 -150 -80 90
profit
jour 21 22 23 24 25 26 27 28 29 30

Perte et
50 -60 70 80 -50 100 110 - 30 0 60
profit

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

• Calculer la moyenne et l’écart-type.

• Le risque accepté par l’entreprise est 𝛼=1%
• Calculer la 𝑉𝑎𝑅 à10 jours.
Réponse:
𝑛 (𝑋 −𝑋)2 𝑛
𝑖=1 𝑖 𝑖=1 𝑋𝑖
𝜎𝑋 = 𝑛−1
= 85,37 et 𝑋= 𝑛
=22,06
𝑉𝑎𝑅 = 𝑍1−𝛼 𝜎𝑋 – μ=2,326* 85,37-22,06 = 176,51
𝑉𝑎𝑅10 = 𝑉𝑎𝑅1 10
VaR10 =558,17

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1

 FSJES AGDAL- L.E

La modélisation par la loi normale

Calculer la 𝑉𝑎𝑅 en utilisant Cornish-Fisher.
Réponse:
𝑆 = −0,45 𝑒𝑡 𝐾 = −1,35 et 𝑧𝑐 =2,326
−0,45 −1,35 (−0,45)2
Z=𝑧𝑐 +(𝑧𝑐 2-1) +(𝑧𝑐 3-3𝑧𝑐 ) -(2𝑧𝑐 3 -5𝑧𝑐 )
6 24 36
−0,45 -1,35
Z= 2,326 +( 2,3262 -1) +( 2,3263 -3* 2,326 ) -
6 24
(−0,45)2
(2 ∗ 2,3263 -5∗ 2,326) = 1,603
36
𝑉𝑎𝑅 = 𝑍1−𝛼 𝜎𝑋 – μ= =1,603* 85,37-22,06 = 114,84
VaR10 =363,18

Pr. Mohamed Habachi Recherche opérationnelle S 5 – 2022-2023 1