RECHERCHE

OPERATIONNELLE
Table des matières

I Introduction à la recherche opérationnelle

Quelques exemples de modèles mathématiques
Tour d’horizon des techniques de recherche opérationnelle
II Applications de la programmation linéaire
Définition, exemples et méthode de résolution
Notions de bases
Exemples de modèles linéaires
Forme standard et forme canonique d’un programme
linéaire
 Résolution de programmes linéaires
Résolution graphique
La méthode du simplexe
Dualité et sensitivité: Le problème dual
Relations primal/dual
III File d’attente
Exemple de file d’attente
IV PERT ET Chemin critique
Exemple PERT et CPM
V Gestion de la qualité le Processus Statistique
Exemple Intervalle de confiance de la qualité
VI Programmation des stocks
Application: programmation des stocks
 Introduction à la recherche opérationnelle

La R.O., un outil pour l’aide à la décision

Un système de Fonctions économiques et de
contraintes
Le domaine combinatoire : chemin optimal,
ordonnancement, transport, affectation
Le domaine aléatoire : files d ’attente, gestion des
stocks
Le domaine concurrentiel
Quelques exemples de modèles
mathématiques

Max Profit Z: aX1 + bX2 + Cx3 + …

Min Couts C : a11 Y1 + a12 Y2 + … + a1n Yn

Les deux fonctions objectives sont chacune

sous Contraintes (temps, couts, facteurs…)
 La méthode PERT

• Qu ’est-ce qu’un ordonnancement ?

• Les méthodes : GANTT, MPM, PERT
• Construction du diagramme PERT
• Calendrier des étapes : arrivée au plus tôt/tard
• Calendrier des tâches et calcul des marges
La signification des marges
• Modification de contraintes

A.Faÿ 6
 Flots et réseaux de transport
• Définition et construction d’un réseau de transport. La
loi de Kirchoff
• Flot au jugé (exemple)
• Recherche d ’un flot complet

[4] 1
1 3 [4]
[4] 2
2
[1] 1 1
E S
3 [3]
[4]
[7]
2 4 4
[4] 4
6
[2]
1

A.Faÿ 7
 Problèmes de transport
• Définition
• Obtention d ’une solution de base :
- méthode du coin Nord-Ouest
- méthode de la différence maximale (Balas-Hammer)
• Calcul de la solution optimale - méthode du stepping-
stone
• Autre résolution à l ’aide d ’un réseau de transport

A.Faÿ 8
 Programmation linéaire
RESOLUTION PAR:
• La méthode graphique
• La méthode du simplexe (matrices)

A.Faÿ 9
 Phénomènes aléatoires
• Files d ’attente: Loi de Poisson
• Gestion de stocks : Programmation (BOM,
MRP)

A.Faÿ 10
EXEMPLES DE MODELES
MATHEMATIQUE
 -5-

Optimisation linéaire et non-

linéaire

2013-02-18
12
 Sujets abordés

 Introduction à la programmation
(optimisation) linéaire
 Concept, formulation
 Illustration à l’aide d’Excel
 Introduction à l’optimisation non-linéaire
 Concept, formulation
 Illustration à l’aide d’Excel

13
 Introduction
Qu’est-ce que la programmation linéaire?

« La programmation linéaire est une méthode

mathématique qui s'inscrit dans une recherche
d'optimisation »

 Il y a une fonction objective et des contraintes

 Nous tenterons de minimiser ou maximiser la fonction objective tout en
respectant les contraintes

 Les équations sont de premier degré

 Les variables sont élevées à la puissance 1
 Il s’agit donc de droites et non de courbe (d’où le terme linéaire)

14
 Introduction
Pourquoi étudier la programmation linéaire?

 Populaire en administration, surtout en gestion des

opérations
 Optimisation des flux de transport
 Planification de la production

 En finance, la programmation linéaire peut :

 Optimiser la prise de décisions (où, quand, combien ?)
 Décisions d’investissement
 Décisions d’emprunt
 Décisions de placement

 Optimiser l’encaisse (gestion de la liquidité)

15
 Introduction

Écriture d’un problème de programmation

linéaire
Bien définir la fonction objective
Bien définir les contraintes

Résoudre un problème simple d’optimisation

Méthode du simplexe avec le solveur
d’Excel

16
 Définir les équations
 Ecrire l’objectif et les contraintes sous la forme
d’équations mathématiques
1. Définir les variables de décisions (X1, X2, … Xn)
2. Définir la fonction objective à l’aide des variables de
décision
3. Définir les contraintes représentant les restrictions
 Les contraintes sont parfois explicites.
 Nous devons le plus souvent les déduire

17
 Définir les équations
 La forme usuelle des équations est la suivante :

Max : c1 X 1  c 2 X 2  ...  c n X n
Objectif :

(périodes 1 à m)
chaque période
Contraintes pour
a11 X 1  a12 X 2  ...  a1n X n  b1

a 21 X 1  a 22 X 2  ...  a 2n X n  b2
Contraintes : a X  a X  ...  a X  b
31 1 32 2 3n n 3
•
•
•

a m1 X 1  a m2 X 2  ...  a mn X n  bm

X 1 , X 2 ,..., X n  0 Contrainte de non

négativité

18
 ETAPES DE CONSTRUCTION DU MODELE LINEAIRE

ETAPE 1:
DEFINIR LES VARIABLES DE DECISION
ETAPE 2:
DEFINIR LA FONCTION OBJECTIVE
D’OPTIMISATION
ETAPE 3:
ECRIRE LES CONTRAINTES
ETAPE 4:
RAPPELER LA NON NEGATIVITE DE VARIABLES DE
DECISION
Exemple : Allocation de ressources
Produit A Produit B Disponibilité
Machine 1 10 5 2000
Machine 2 4 10 1500
Machine 3 1 2 500
Profit 10 20
Résolution graphique
 EXAMPLE
Trouver la meilleure combinaison de production des tables
et des chaises
La société Flair Furniture Company produit des
tables et des chaises.
La production nécessite un nombre d'heures de travail
de menuiserie, et, de peinture et vernissage
Chaque table nécessite 4 heures de menuiserie et 2
heures de peinture et de vernissage
Chaque chaise nécessite 3 heures de menuiseries et
1 heure de peinture et vernissage
Il y a 240 heures de menuiserie disponibles et 100
heures de peinture et de vernissage
Chaque table rapporte 70$ de profit et chaque chaise
rapporte 50$ de profit.
 T: nombre de tables
C: nombre de chaises

The complete problem stated mathematically

Maximize profit = $70T + $50C
subject to:
4T + 3C ≤ 240 (carpentry constraint)
2T + 1C ≤ 100 (painting and varnishing constraint)
T, C ≥ 0 (nonnegativity constraint)
 Holiday Meal Turkey Ranch
HMT envisage l'achat de deux marques différentes d'aliments de
dinde. Leur mélange peut fournir un bon régime à faible coût. Le
programme lineaire est le suivant.
Soit:
X1 = nombre de livres d'aliments de marque 1 achetés
X2 = nombre de livres d'aliments de marque 2 achetés

Minimiser les coûts: C = 2X1 + 3X2

sujet à:
5X1 + 10X2 ≥ 90 onces (contrainte d'ingrédient A)
4X1 + 3X2 ≥ 48 onces (contrainte d'ingrédient B)
0,5X1 ≥ 1,5 once (contrainte d'ingrédient C)

X1 ≥ 0 (contrainte de non-négativité)
X2 ≥ 0 (contrainte de non-négativité)
REPRESENTATION GRAPHIQUE
 EXAMPLE
Une entreprise fabrique des clés et des pinces en acier en utilisant
une machine de moulage et une machine d'assemblage.
Selon les informations suivantes sur les matières premières, les
heures-machine, et la demande, quelle est la quantité des clés
et/ou des pinces qui peut aider à maximiser le profit de
l’entreprise?
Chaque unité des clés nécessite: 1.5 livre d’acier une heure de
moulage, 0,40 heures d’assemblage. La demande actuelle est de
8000 clés,
Chaque unité des pinces nécessite: 1,0 livre d’acier, 1.0 hr de
moulage, 0,5 heures d’assemblage. La demande actuelle est de
10 000 pinces.
Les données disponibles:
Acier: 15000 livres. Heures moulage: 12000. heures assemblage:
5000
Profit espéré: $0.40 par clé, $0.30 par pince
 Formulation du problème LP

1. Comprendre le problème.

2. Identifier les variables décisionnelles.

w = nbre de clés
p = nbre de pinces

3. Définir la fonction objectif en une combinaison

linéaire de variables décisionnelles.
MAX: 0.40w + 0.30p
 Étapes pour la formulation du problème LP (Suite)

4. Définir les contraintes en une combinaison linéaire de variables

décisionnelles.
1.5w + 1.0p <= 15000 } Acier
1.0w + 1.0p <= 12000 } Moulinage.
0.4w + 0.5p <= 5000 } Assemblage
Demande des clés: w <= 8000
Demande des pinces: p <= 10000

5. Identifier limites supérieures ou inférieures des variables

décisionnelles.
w >= 0
p >= 0
 Étapes pour la formulation du problème LP (Suite)

4. Définir les contraintes en une combinaison linéaire de variables

décisionnelles.
1.5w + 1.0p <= 15000 } Acier
1.0w + 1.0p <= 12000 } Moulinage.
0.4w + 0.5p <= 5000 } Assemblage
Demande des clés: w <= 8000
Demande des pinces: p <= 10000

5. Identifier limites supérieures ou inférieures des variables

décisionnelles.
w >= 0
p >= 0
 Sommaire du modèle LP

Objective Function

max : profit  400  w  300  p

Subject to
– Steel: 1.5  w  1.0  p  15

– Moulding: 1.0  w  1.0  p  12

– Assembly: 0.4  w  0.5  p  5 p  10

– Wrench demand: w 8

– Pliers demand: p,w  0

 Résolution graphique d’un problème de LP

Then begin plotting the constraints, one

14

at a time:
12
10

1.5  w  1.0  p  15
8
6
4
2

w
2 4 6 8 10 12 14
 Résolution graphique d’un problème de LP

p
14
12
10

1.0  w  1.0  p  12
8
6
4
2

w
2 4 6 8 10 12 14
 Résolution graphique d’un problème de LP
p
14
12
10

0.4  w  0.5  p  5
8
6
4
2

w
2 4 6 8 10 12 14
 Solving an LP Graphically

p
14
12
10

p  10
8

w 8
6
4
2

w
2 4 6 8 10 12 14
 Solving an LP Graphically
p

This defines the LP problem’s

14

feasible region.
12

But how do we solve it?

10
8
6
4
2

w
2 4 6 8 10 12 14
 PROBLEME DUEL
En théorie d'optimisation, nous associons à
chaque problème principal de la
programmation linéaire son problème duel.
A chaque problème principal de maximisation
est associé son problème duel de
minimisation, et vice versa.
 Formulation du problème duel
Les variables décisionnels du problème duel:
S, M, et A représentent respectivement l’acier, le
moulinage, et l’assemblage
La fonction objective est donc: Min. Coût: 15S +
12M + 5A
s/c 1.5 S +1.0M +0.4 A ≥ 400
1.0 S + 1.0M + 0.5A ≥ 300
S, M, A ≥ 0
 Exemple de problème de minimisation –
Résolution graphique

Une entreprise fabrique deux produits chimiques, c1 et c2.

c1 nécessite un coût de fabrication de $2500 par tonne et
c2 nécessite $3000 par tonne. Selon les prévisions de
l’entreprise concernant la demande de ses produits, les
productions des deux produits doivent atteindre au moins
30 tonnes et 20 tonnes pour c1 et c2 respectivement. Du
fait que les matières premières des deux produits sont
sensibles et vite périssables, leur stock ne doit pas
dépasser 30 jours. Pour cela, l’entreprise table sur une
production d’au moins de 60 tonnes pour les deux
produits.
 Formulation du problème
Les variables décisionnels:
X1: tonnes of c1. X2: tonnes of c2
La fonction objective:
Min. Coût: 2500X1 + 3000X2
Sujet à:
X1 ≥ 30 tonnes de c1
X2 ≥ 20 tonnes de c2
X1 + X2 ≥ 60 tonnes en totalité
X1, X2 ≥ 0
 Résolution graphique d’un problème de LP

X
2

60
Region faisable
0
4

b
0
2

X
2 4 60
0 0
1
 Résolution graphique d’un problème de LP

Le graphe présente deux coins: le coin (a) et le

coin (b).
Le coût total au coin (a) est:
2500(40) + 3000(20) = $160000
Le coût total au coin (b) est:
2500(30) + 3000(30) = $165000
Le coût minimum est réalisé au coin a. Le
manager de production doit produire 40
tonnes de c1 et 20 tonnes de c2
 Example d’un probleme de production
Une entreprise fabrique deux produits necessitant des
ressources d’equipement, de main d’oeuvre et de
matieres premieres disponibles en quantite limitee.
Prd.1 Prd.2 Disponibilite

Produit1 et produit2 rapporte a la vente respectivement 6 euros et

4 euros par unite.
Quelle quantite des deux produits doit produire l’usine pour
maximiser la fonction objective?
QUELLE QUANTITE DU PRODUIT A ET DU
PRODUIT B FAUT-IL PRODUIRE POUR
MAXIMISER LE PROFIT ?
 Exemple
Exemple

Le gestionnaire d’une entreprise de fabrication de meubles doit

planifier la production du prochain mois. Il doit choisir le nombre
optimal de bureaux de travail, de tables d’ordinateur et de
classeurs à fabriquer.

- Le budget prévu pour la production est 100 000 $

- Les employés peuvent travailler un maximum de 1500 heures
- L’entrepôt peut contenir un maximum de 150 m3

51
 Définir les équations
Exemple (suite)

Objectif : Max : W  400$X1  700$ X 2  350$ X 3

300$ X 1  500$ X 2  250$ X 3  100 000$

20hrsX 1  32hrsX 2  16hrsX 3  1500hrs
Contraintes :
3m3 X 1  3m3 X 2  2m3 X 3  150m3

X1, X 2 , X 3  0 Puisqu’il est impossible de fabriquer

un nombre négatif de meubles…
PROBLEME PRIMAL ET PROBLEME DUAL
EXEMPLE
PROBLEME DUAL
Résolution du programme linéaire (PL)
METHODE DE SIMPLEXE
INTRODUCTION DES VARIABLES D’ECART. e1, e2,e3
 VARIABLES DE BASE ET VARIABLES HORS
BASE
On a n = 6 variables et m = 4 equations

n – m = 2 variables = 0

Si X1 = 0, et X2 = 0 alors
les Xi: variables hors base et les ei sont les variables de base

e1 = 200
e2 = 60
e3 = 34
e4 = 14
 Étape B :
Choix de la variable entrante (dans la base)
Étape C : choix de la variable sortante
Étape D : Pivotage
Le critère d’arrêt