Méthodes mathématiques

de gestion

La recherche opérationnelle

Master 1
Département de Gestion
Esp, Dakar

Juin 2017
Dr. O. Diop
La RO
 Plans du cours

1. Introduction
2. Modélisation d’un programme linéaire
3. Méthode graphique de résolution d’un problème linéaire
4. La méthode algébrique
5. La méthode du Simplex
6. Le solveur du logiciel Excel
 Introduction

La programmation linéaire est une technique mathématique permettant de

déterminer la meilleure solution d’un problème dont les données et les inconnues
satisfont à une série d’équations et d’inéquations linéaires

Il peut aussi se définir comme une technique mathématique permettant de résoudre des
problèmes de gestion et particulièrement ceux où le gestionnaire doit déterminer, face à
différentes possibilités, l’utilisation optimale des ressources de l’entreprise pour atteindre un
objectif spécifique comme la maximisation des bénéfices ou la minimisation des coûts.
 Domaine d’application de la RO
❖ Gestion stratégique d’investissements

❖ Réseaux de communication, systèmes d’information

❖ Gestion de la chaine logistique

Production : maximiser le profit selon la disponibilité de la main d’œuvre, la
demande du marché, la capacité de production, le prix de revient du matériau brut
…

Transport : minimiser la distance totale parcourue selon les quantités de

matériaux à transporter, la capacité des transporteurs, les points de ravitaillement
en carburant …
 Domaine d’application
Il existe d’autre domaines où la RO intervient:

❖ La finance

❖ L’informatique

❖ L’énergie

❖ Banque assurance

❖ File d’attente

❖ L’industrie manufacturière
Généralités sur la RO
 Approche de la RO

• Identifier les variables

Modélisation • Déterminer la fonction à optimiser

• Structurer les contraintes

• Méthode graphique
Analyse des modèles
• Méthode algébrique
et résolution
• Méthode du Simplex
 Chapitre 1

Modélisation d’un programme linéaire

Objectif: Dans ce chapitre, nous nous limiterons uniquement à la transcription d’un

problème en un système d’inéquations ainsi que repérer la fonction à optimiser.
 Exemple 1 : production de peinture
Une société produit de la peinture d’intérieur et d’extérieur à partir de deux
produits de base M1 et M2.

??? : système mathématique modélisant ce problème

 Variables, inconnues du problème

Définitions :
• On appelle fonction économique ou fonction objectif
la fonction qui doit être maximisée ou minimisée.
• On appelle programme de base
✔ l’identification des variables,
✔ la donnée de la fonction économique S.C
✔ le système d’inéquations correspondant aux
contraintes
.

• Solution admissible : Une solution admissible est un

ensemble de valeurs données aux variables qui satisfait
toutes les contraintes
 Forme standard d’un programme linéaire

Définition
Un programme linéaire est sous forme standard lorsque toutes ses contraintes sont des
égalités et toutes ses variables sont non-négatives.

Forme matricielle
 Forme canonique d’un programme linéaire

Définition : Un programme linéaire est sous forme canonique lorsque toutes ses contraintes sont
des inégalités et toutes ses variables sont non-négatives.

Forme matricielle
Théorème 1 (Equivalence des formes standard et canonique).
Tout programme linéaire peut s’écrire sous forme standard et sous forme canonique.

Preuve :
• Transformer les contraintes d’inégalité en contraintes d’
égalité en rajoutant une variable d’écart

• Une contrainte d’inégalité peut etre remplacée par deux inégalités

 Exemple 1
Exercice 3. L’administrateur d’une firme de comptables doit déterminer, chaque semaine, le
temps qu’il doit allouer à chacune des trois activités suivantes : la vérification, la comptabilité
de gestion et la planification fiscale.
Le but est de gérer, le mieux possible, les ressources humaines de la firme. Pour chaque heure
de vérification facturée, la firme doit faire 15 minutes de travail de comptabilité et 30 minutes
de travail de bureau. Pour chaque heure de comptabilité de gestion facturée, la firme doit
fournir 20 minutes de travail de comptabilité, 60 minutes de travail de bureau et elle doit, de
plus, utiliser 6 minutes de temps d’ordinateur. Pour chaque heure de planification fiscale
facturée, la firme doit prévoir 30 minutes de travail de comptabilité, 45 minutes de travail de
bureau et 3 minutes de temps d’ordinateur. Le profit net pour une heure de vérification est de 4
euro, tandis que les profits nets pour une heure de comptabilité de gestion et de planification
fiscale sont respectivement de 10 euro et de 6 euro. Le personnel de la firme peut fournir cette
semaine, 80 heures de comptabilité, 180 heures de travail de bureau et 30 heures de
traitement par ordinateur.

Formuler le programme de base de programmation linéaire dont la solution donnera la

répartition des heures de travail disponibles qui maximise le profit net de la firme.
Solution
 Exemple 2

On considère le cas d’un fabricant d’automobiles qui propose deux modèles à la

vente, des grosses voitures et des petites voitures. Les voitures de ce fabricant sont
tellement à la mode qu’il est certain de vendre tout ce qu’il parvient à produire, au
moins au prix catalogue actuel de 16000 euros pour les grosses voitures, et 10000
euros pour les petites voitures. Son problème vient de l’approvisionnement limité
en deux matières premières, le caoutchouc et l’acier. La construction d’une petite
voiture nécessite l’emploi d’une unité de caoutchouc et d’une unité d’acier, tandis
que celle d’une grosse voiture nécessite une unité de caoutchouc mais deux unités
d’acier. Sachant que son stock de caoutchouc est de 400 unités et son stock d’acier
de 600 unités,

Formuler le programme de base de programmation linéaire associé à ce problème

 Exercices d’application

Exercice 1 - Bucheron.
Un bucheron a 100 hectares de bois de feuillus. Couper un hectare de bois et laisser la
zone se regénérer naturellement coute 700 fcfa par hectare, et rapporte à terme 35000
fcfa. Alternativement, couper un hectare de bois, et replanter avec des pins coute
35000 fcfa par hectare, et rapporte à terme 84000 fcfa. Sachant que le bucheron n’a
que 2800000 cfa en caisse au début de l’opération, déterminer le programme linéaire
permettant d’avoir la meilleure stratégie à adopter.
 Exercices d’application
Exercice 2 - Taxi.
Une compagnie de taxi dispose de quatre véhicules libres et doit transporter
quatre clients. Le but de la compagnie est d’assigner un taxi par client en
minimisant la somme des distances parcourues. Les distances respectives (en
kilomètres) entre les taxis et les voyageurs sont données par le tableau suivant :

Modéliser le problème sous la forme d’un programme linéaire sous forme canonique
Capitre 2 : Résolution d’un programme linéaire
par la méthode graphique
 Exemple 1 : Programme linéaire à deux inconnues

Reprenons l’exemple du chapitre précédent, la production de peinture

On rappelle que le programme linéaire modélisant la production de peinture est donné par le système suivant

SC
 Exemple 2 : Programme linéaire à deux inconnues
Considèrons le programme linéaire suivant
Exemple 3 : Allocation de ressources
 Exercice 1

Résoudre le programme linéaire suivant

 Exercice 2
L’entreprise Simco fabrique différents modèles d’appareils électro- ménagers. Le programme
actuel de fabrication est de 500 unités du modèle Elec-100 et 400 unités du modèle Elec-200.
Le vice-président de la fabrication veut déterminer si les contributions aux bénéfices de
l’entreprise peuvent être augmentées en modifiant le programme actuel de fabrication. Il
possède l’information suivante sur le nombre d’heures requises pour fabriquer chaque
modèle, ainsi que le temps disponible à chaque atelier.

b) Faites la représentation graphique du

problème
c) Points-sommets,tla fonction économique et en déduire la solution du
problème
 Résolution

La solution de ce problème est les couple (1000,300)

Exemple : problème linéaire à trois variables
 Exemple 3 : Programme linéaire à trois inconnues
•

La fonction économique est donnée par Polyèdre des

contraintes

Et les contraintes
 Exercice d’application
1
 Exercice d’application
2
Chapitre 3 : Résolution par la méthode algébrique
 Variables d’écart

•
•

Ainsi les contraintes du modèle fil rouge (cf. page 36) exprimées sous forme
d’inéquations linéaires, peuvent se ramener à un système d’équations linéaires en
introduisant trois variables d’écart, x3, x4 et x5 :
Reprenons l’éxemple suivant
Coefficients des variables d’écart dans la fonction économique

Nous sommes alors en présence d’un système de trois équations à cinq inconnues.
Résolution complète
Critère d’entrée d’une variable dans le programme de base
Détermination de la valeur entrante
détermination de la nouvelle solution : programme de
base no 2
détermination du troisième programme de base
Détermination du quatrième programme de base
 Démarche à suivre
1) structurer le problème sous forme d’un système d’équations en introduisant les variables d’écart requises. Il
s’agira bien sûr d’avoir précisé préalablement les variables (principales et d’écart) ainsi que la fonction
économique.
2) Déterminer le programme de base qui servira de départ au cheminement vers la solution optimale (programme
optimal).
3) Expliciter la fonction économique et déterminer si elle peut être améliorée : recherche de l’éventuelle variable
(hors programme) admettant le plus grand coefficient positif. Dans la négative, le programme est optimal.

4) En introduisant cette variable dans le programme, on choisira la plus petite valeur positive obtenue à l’aide du
système d’équa- tions calculé lors de l’étape précédente. Celà induira la variable sortante.

5) Pour déterminer un nouveau programme de base, on doit trans- former le système d’équations ainsi que
l’expression de la fonc- tion économique en exprimant les variables dans le programme de base en fonction des
variables hors programme (par substi- tution).

6) Retourner à 3) jusqu’à l’obtention du programme de base optimal.

7) Donner le programme optimal en précisant la valeur de toutes les variables ainsi que la valeur optimisée de la fonction
écono- mique.
Exercice 1
Exercice 2
Chapitre 4 : La méthode du simplex
La méthode du simplex
Reprenons le problème discuté dans le chapitre précédent
On peut écrire le système précédent sous la forme suivante
On obtient le système suivant
Démarche à suivre pour la méthode du complex
Exemple: Reprenons l’exemple du controle

1. Matrice du programme de base no 1 :

2. Déterminer la ligne et la colonne du pivot no 1 :
3. Rendre le pivot no 1 unitaire :
4. Annuler tous les termes de la colonne du pivot no 1 :
5. La fonction économique est-elle optimisée ?
6. Déterminer la ligne et la colonne du pivot no 2 :
7. Rendre le pivot no 2 unitaire :
8. Annuler tous les termes de la colonne du pivot no 2 :
9. La fonction économique est-elle optimisée ?
10. Exprimer alors la situation optimale :
Chapitre 5 : Le solveur du logiciel Excel
Reprenons l’exemple du controle
Reprenons l’exemple du controle
Reprenons l’exemple du controle
Le programme correspondant s’écrit comme suit
Remarque
Remarque :
Exercice : Résoudre le problème suivant