Cours : Recherche Opérationnelle

Introduction
Programmation Mathématique
1. Problème de programmation mathématique
[Link]élisation d’un problème linéaire
3. Résolution graphique
4. Algorithme de Simplexe
5. Application aux problèmes de transport et de production
Dualité
1. Interprétation Économique
[Link] Primal & Dual
Théorie d’ordonnancement
1. Description
2. Méthodes de Résolution
Théorie des Graphes
1. Représentation d'un graphe
2. Connexité, Parcours eulériens et Hamiltoniens
3.Méthode de recherche de chemins
Heuristiques et Métaheuristiques
1. Heuristiques
2. Métaheuristiques : Algorithmes Génétiques, Colonies de Fourmies, PSO..

1
 Définition

v La Recherche Opérationnelle

• La recherche opérationnelle peut être définie comme l’ensemble des méthodes et

techniques rationnelles orientées vers la recherche du meilleur choix dans la façon
d’opérer en vue d’aboutir au résultat visé ou au meilleur résultat possible.

• Elle fait partie des "aides à la décision" dans la mesure où elle propose des modèles
conceptuels en vue d’analyser et de maitriser des situations complexes pour
permettre aux décideurs de comprendre, d’évaluer les enjeux et d’arbitrer ou de
faire les choix les plus efficaces.

• Ce domaine fait largement appel au raisonnement mathématique (logique, algèbre,

probabilités, analyse des données) et à la modélisation des processus. Il est
fortement lié à l’ingénierie des systèmes, ainsi qu’au management du système
d’information.

2
Applications

Production

Transport

Mobilité

3
Applications

4
Première Partie
Programmation Mathématique
 Préliminaires

Les problèmes de la programmation mathématique se posent lorsqu’on cherche à

optimiser (maximiser ou minimiser) une fonction à plusieurs variables, appelée
fonction objectif ou fonction économique. Ces variables sont soumises à des
relations sous forme d’inéquations ou d’équations, appelées contraintes.

6
Programme Mathématique

v Définition

Un programme mathématique (P) est un problème d’optimisation de la forme :

𝑴𝒊𝒏 𝒇 𝒙 (𝑟𝑒𝑠𝑝 𝑀𝑎𝑥 𝑓 𝑐 )

(P) 𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
𝒉𝒊 𝒙 ≤ 𝟎, 𝒊 = 𝟏, … . 𝒎
𝒙∈𝑪
• La fonction f est appelée la fonction objectif ou économique.
• L’ensemble C et les conditions ℎ" 𝑥 ≤ 0, 𝑖 = 1, … . 𝑚 sont appelées les
contraintes de (P).

7
Programme Mathématique

v Remarque

• Dans toute la suite nous ne considérons que le problème avec fonction objectif
égale à 𝑴𝒊𝒏 𝒇 𝒙 . En effet, 𝑴𝒂𝒙 𝒇 𝒙 = −𝑴𝒊𝒏 − 𝒇 𝒙 . Donc on peut
facilement ramener un problème de maximisation à un problème de
minimisation.

• Dans le problème (P) on a considéré que les contraintes d’inégalités, car une
contraintes d’égalité de type 𝒉 𝒙 = 𝟎 peut être remplacée par les deux
contraintes d’inégalités suivantes : 𝒉 𝒙 ≤ 𝟎 et 𝒉 𝒙 ≥ 𝟎.

8
 Solution Réalisable

v Définition

On appelle solution réalisable d’un programme mathématique (P), tout vecteur 𝒙 ∈

ℝ𝒏 vérifiant toutes les contraintes de (P) :

𝒉𝒊 𝒙 ≤ 𝟎, 𝒊 = 𝟏, … . 𝒎
O
𝒙∈𝑪

9
 Domaine Réalisable

On appelle domaine réalisable de (P), l’ensemble de toutes les solutions réalisables de

(P) .

Solution Optimale

• On appelle solution optimale ou optimum global de (P), la meilleure solution

réalisable de (P).

• Si (P) est un problème de minimisation, alors la solution optimale est la solution qui
minimise f(x) sur l’ensemble de toutes les solutions.

10
v Remarque

• Un problème (P) peut avoir plusieurs optimaux globaux.

• On dit que 𝒙 est un optimum local de (P) s’il existe un voisinage 𝑽𝒙 de 𝒙 tel
que 𝒙 soit un optimum global du problème (P1) suivant :

𝑴𝒊𝒏 𝒇 𝒙
𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
(P1)
𝒉𝒊 𝒙 ≤ 𝟎, 𝒊 = 𝟏, … . 𝒎
𝒙 ∈ 𝑪 ∩ 𝑽𝒙

11
v Remarque

• Un problème (P) peut avoir plusieurs optimaux globaux.

• On dit que 𝒙 est un optimum local de (P) s’il existe un voisinage 𝑽𝒙 de 𝒙 tel
que 𝒙 soit un optimum global du problème (P1) suivant :

𝑴𝒊𝒏 𝒇 𝒙
𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
(P1)
𝒉𝒊 𝒙 ≤ 𝟎, 𝒊 = 𝟏, … . 𝒎
𝒙 ∈ 𝑪 ∩ 𝑽𝒙

12
13
Classes de problèmes de programmation mathématique

v Classification selon l’espace de recherche

Problème Sans Contraintes Problème Avec Contraintes

𝑴𝒊𝒏 𝒇 𝒙 (𝑟𝑒𝑠𝑝 𝑀𝑎𝑥 𝑓 𝑐 ) 𝑴𝒊𝒏 𝒇 𝒙 (𝑟𝑒𝑠𝑝 𝑀𝑎𝑥 𝑓 𝑐 )

(P) (P) 𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
𝒉𝒊 𝒙 ≤ 𝟎, 𝒊 = 𝟏, … . 𝒎
𝒙 ∈ ℝ𝒏 𝒙∈𝑪

• Aucune contrainte n’est imposée • Des contraintes sont imposées

14
 Classes de problèmes de programmation mathématique

v Classification selon la nature de fonction objectif et les contraintes

Problème Linéaire (PL) Problème Non Linéaire (PNL)

𝑴𝒊𝒏 𝒇 𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 = ∑𝒏𝒊'𝟏 𝒄𝒊 𝒙𝒊 𝑴𝒊𝒏 𝒇 𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 = ∑𝒏𝒊'𝟏 𝒄𝒊 𝒙𝟐𝒊

𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶ 𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
(PL) (PNL) 𝒏
∑𝒏𝒊'𝟏 𝒂𝒋𝒊 𝒙𝒊 ≤ 𝒃𝒋 , 𝒋 = 𝟏, … . 𝒎 ∑𝒊'𝟏 𝒂𝒋𝒊 𝒙𝟐𝒊 ≤ 𝒃𝒋 , 𝒋 = 𝟏, … . 𝒎
𝒙𝒊 ≥ 𝟎 𝒙𝒊 ≥ 𝟎

• La fonction objectif et les contraintes • La fonction objectif et/ou une des

doivent être linéaires contraintes n’est pas linéaire

15
Avant de résoudre un problème industriel, il faut bien commencer par sa
modélisation. Cette dernière passe par la traduction du problème en
relations mathématiques.

16
 Formulation mathématique

La modélisation mathématique d’un problème passe par trois étapes :

Déterminer les variables (Actions) du problème à valeur non connues

Identifier les
actions (Variables) (variable de décision) qui s’offrent au décideur et les représenter sous
forme symbolique (x1, x2, y1, y2, . . .)

Identifier les
restrictions
Identifier les restrictions (les contraintes) définissant la nature du
(Contraintes) système étudié et les exprimer par un système d’équations linéaires

Identifier l’objectif ou le critère de sélection et le représenter sous une

Identifier l’objectif forme linéaire en fonction des variables de décision, puis spécifier si le
critère de sélection est à maximiser ou à minimiser.

17
 Problème 1 : Fabricant de Yaourts

Un fabricant produit 2 types de yaourts à la fraise A et B ; à partir de Fraise, de

Lait et de Sucre. Chaque yaourt doit respecter les proportions suivantes de
matières premières.

On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de Sucre.

La vente de 1 Kg de yaourts A et B rapporte respectivement 40dh et 50dh.
Le fabricant cherche à maximiser son profit.
• Proposer une formulation mathématique du problème en suivant les 3 étapes de
modélisation
18
 Problème 1 : Fabricant de Yaourts

• Étape 1 : Identification des variables de décision

Q : Quelles sont les décisions (actions) à prendre ?

R : Déterminer les quantités à fabriquer du yaourt A et du yaourt B

Alors, Soient :

𝑥! : La quantité à fabriquer du yaourt A

Et

𝑥" : La quantité à fabriquer du yaourt B

19
 Problème 1 : Fabricant de Yaourts

• Étape 2 : Identification des contraintes

Q : Quelles sont les restrictions imposées ?
R : On ne peut pas dépasser les quantités de fraises, lait et sucre dont-on dispose.
Les contraintes du problème sont :
• Contrainte sur la quantité maximale de fraises à ne pas dépasser
2𝑥! + 𝑥" ≤ 800
• Contrainte sur la quantité maximale de lait à ne pas dépasser
𝑥! + 2𝑥" ≤ 700

• Contrainte sur la quantité maximale de sucre à ne pas dépasser

𝑥" ≤ 300
• Contrainte de positivité des quantités :
𝑥! , 𝑥" ≥0
20
 Problème 1 : Fabricant de Yaourts

• Étape 3 : Identification de la fonction objectif

Q : Que cherche-t-on à optimiser?
R : On cherche à maximiser le profit
Alors, la fonction objectif est :

Maximiser f(𝑥! , 𝑥" ) ∶ 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 40 𝑥! +50 𝑥"

21
Problème 1 : Fabricant de Yaourts

Donc on obtient le programme linéaire suivant :

22
 Problème 2 : Fleuriste

Un fleuriste dispose de 45 roses, 36 tulipes et 27 marguerites. Il veut préparer à

ses clients deux offres de bouquets :

v Offre 1 : bouquet à 80 Dh composé de 10 roses, 4 tulipes et 2 marguerites.

v Offre 2 : bouquet à 60 Dh composé de 6 roses, 6 tulipes et 6 marguerites.

Le fleuriste cherche à maximiser son revenu.

• Proposer une formulation mathématique du problème en suivant les 3 étapes de

modélisation

23
 Problème 2 : Fleuriste

• Étape 1 : Identification des variables de décision

Q : Quelles sont les décisions (actions) à prendre ? (Informations essentielles pour

résoudre le problème)
R : Déterminer le nombre de bouquets à préparer de chaque type (offre)

Alors, Soient :

𝑥# : le nombre de bouquets à préparer de type 1

Et

𝑥$ : le nombre de bouquets à préparer de type 2

24
 Problème 2 : Fleuriste

• Étape 2 : Identification des contraintes

Q : Quelles sont les restrictions imposées ?
R : • On ne peut pas dépasser le nombre total de roses, tulipes et marguerites dont-on
dispose.
• les variables 𝑥) et 𝑥* doivent être des entiers positives
Alors, les contraintes du problème sont :
• Contrainte sur le nombre maximum de roses à ne pas dépasser
10𝑥# + 6𝑥$ ≤ 45
• Contrainte sur le nombre maximum de roses à ne pas dépasser
4𝑥# + 6𝑥$ ≤ 36

• Contrainte sur le nombre maximum de roses à ne pas dépasser

2𝑥# + 6𝑥$ ≤ 27
• Contrainte qui exprime que les variables de décision sont des entiers positives:
𝑥# , 𝑥$ ∈ ℕ 25
 Problème 2 : Fleuriste

• Étape 3 : Identification de la fonction objectif

Q : Que cherche-t-on à optimiser?
R : On cherche à maximiser le revenu du fleuriste
Alors, la fonction objectif est :

Maximiser f(𝑥! , 𝑥" ) ∶ 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 80 𝑥# + 60 𝑥$

26
 Problème 2 : Fleuriste

Donc on obtient le programme linéaire suivant :

𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 80 𝑥U+ 60 𝑥V
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
10𝑥U + 6𝑥V ≤ 45
4𝑥U + 6𝑥V ≤ 36
2𝑥U + 6𝑥V ≤ 27
𝑥U, 𝑥V ∈ ℕ

Ce type de programme est appelé : Programme Linéaire en Nombres Entiers (PLNE)

27
 Problème 3 : fabrique artisanale

Une fabrique artisanale produit des articles de poterie et des articles d’émaux sur
cuivre, sachant que :

• Il faut 1 heure de temps de fabrication pour une poterie et 4 heures pour un

émail, la charge de travail pour les émaux ne doit pas dépasser celle de la
poterie de plus de 160 heures.

• La production d’articles de poterie ne doit pas excéder de plus de 30 unités la

production d’émaux.

• Le nombre total d’articles fabriqués ne doit pas être supérieur à 80 unités par
jour.

• Le bénéfice est de 20 DH pour une poterie et de 60 DH pour les émaux sur

cuivre.
Proposer une formulation mathématique du problème qui permettra à la fabrique
artisanale de maximiser son profit
28
 Forme Canonique

Un programme linéaire est dit sous sa forme canonique si il est :

• Un problème de Maximisation, sous contraintes Inférieure ou égale, dont toutes les
variables sont positives.
• Un problème de Minimisation, sous contraintes Supérieure ou égale, dont toutes les
variables sont positives.

𝑴𝒊𝒏 (𝑜𝑢 𝑀𝑎𝑥) 𝒇 𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 = ∑𝒏𝒊'𝟏 𝒄𝒊 𝒙𝒊

𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
(PL) ∑𝒏𝒊'𝟏 𝒂𝒋𝒊 𝒙𝒊 ≤ 𝒃𝒋 , 𝒋 = 𝟏, … . 𝒎
𝒙𝒊 ≥ 𝟎

Forme Canonique d’un Programme linéaire

29
Forme Canonique

30
 Forme Canonique

Si le programme linéaire ne correspond pas aux critères de l’écriture

canonique, il faut transformer les contraintes ou la fonction objectif selon les
opérations suivantes :
• max f(x) = – min –f(x)
• x + y ≥ b est équivalent à – x – y ≤ – b
• x + y = b est équivalent à x + y ≥ b, x + y ≤ b

31
 Forme Standard

Un programme linéaire est dit mis sous sa forme standard si :

• Toutes les contraintes (en dehors des contraintes de non négativité des variables de
décision) sont des contraintes d’égalités.

𝑴𝒊𝒏 (𝑜𝑢 𝑀𝑎𝑥) 𝒇 𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 = ∑𝒏𝒊'𝟏 𝒄𝒊 𝒙𝒊

𝑺𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 ∶
(PL) ∑𝒏𝒊'𝟏 𝒂𝒋𝒊 𝒙𝒊 = 𝒃𝒋 , 𝒋 = 𝟏, … . 𝒎
𝒙𝒊 ≥ 𝟎

Forme standard d’un Programme linéaire

32
Forme Standard

33
 Forme Standard

On peut toujours passer de la forme canonique d’un PL à sa forme standard en

introduisant des variables supplémentaires appelées variables d’écart ou
variables de surplus.

34
 Exemple 1 : variables d’écart

Considérons la forme canonique du programme linéaire (P) suivant :

𝑀𝑖𝑛 𝑐7 𝑥7 + 𝑐8 𝑥8 + ⋯ + 𝑐9 𝑥9
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑎77 𝑥: + 𝑎78 𝑥: + ⋯ + 𝑎79 𝑥: ≤ 𝑏7
(P) 𝑎87 𝑥: + 𝑎88 𝑥: + ⋯ + 𝑎89 𝑥: ≤ 𝑏8
⋮
𝑎;7 𝑥7 + 𝑎;8 𝑥8 + ⋯ + 𝑎;9 𝑥9 ≤ 𝑏;
𝑥7 , 𝑥8 , … , 𝑥9 ≥ 0

35
 Exemple 1 : variables d’écart

Le problème (P) peut être écrit sous la forme standard en ajoutant une variable
d ’écart à chaque contrainte.

Ainsi la contrainte :

𝑎+) 𝑥) + 𝑎+* 𝑥* + ⋯ + 𝑎+, 𝑥, ≤ 𝑏+

Sera remplacée par :

𝑎+) 𝑥) + 𝑎+* 𝑥* + ⋯ + 𝑎+, 𝑥, + 𝑦+ = 𝑏+

36
 Exemple 1 : variables d’écart

Le problème (P) peut être écrit sous la forme standard en ajoutant une variable
d ’écart à chaque contrainte.

𝑀𝑖𝑛 𝑐U𝑥U + 𝑐V𝑥V + ⋯ + 𝑐] 𝑥]

𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑎UU𝑥^ + 𝑎UV𝑥^ + ⋯ + 𝑎U] 𝑥^ + 𝑦U ≤ 𝑏U
𝑎VU𝑥^ + 𝑎VV𝑥^ + ⋯ + 𝑎V] 𝑥^ + 𝑦V ≤ 𝑏V
(PS)
⋮
𝑎_U𝑥U + 𝑎_V𝑥V + ⋯ + 𝑎_] 𝑥] + 𝑦_ ≤ 𝑏_
𝑥U, 𝑥V, … , 𝑥] ≥ 0
𝑦U, 𝑦V, … , 𝑦_ ≥ 0

Les programmes (P) et (PS) sont équivalents et admettront la même solution

37
 Exemple 2 : variables de surplus

Considérons la forme canonique du programme linéaire (P) suivant :

𝑀𝑖𝑛 𝑐7 𝑥7 + 𝑐8 𝑥8 + ⋯ + 𝑐9 𝑥9
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑎77 𝑥: + 𝑎78 𝑥: + ⋯ + 𝑎79 𝑥: ≥ 𝑏7
(P) 𝑎87 𝑥: + 𝑎88 𝑥: + ⋯ + 𝑎89 𝑥: ≥ 𝑏8
⋮
𝑎;7 𝑥7 + 𝑎;8 𝑥8 + ⋯ + 𝑎;9 𝑥9 ≥ 𝑏;
𝑥7 , 𝑥8 , … , 𝑥9 ≥ 0

38
 Exemple 2 : variables de surplus

Le problème (P) peut être écrit sous la forme standard en ajoutant une variable de
surplus −𝑦% à chaque contrainte.

𝑀𝑖𝑛 𝑐U𝑥U + 𝑐V𝑥V + ⋯ + 𝑐] 𝑥]

𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑎UU𝑥^ + 𝑎UV𝑥^ + ⋯ + 𝑎U] 𝑥^ − 𝑦U ≤ 𝑏U
𝑎VU𝑥^ + 𝑎VV𝑥^ + ⋯ + 𝑎V] 𝑥^ − 𝑦V ≤ 𝑏V
(PS)
⋮
𝑎_U𝑥U + 𝑎_V𝑥V + ⋯ + 𝑎_] 𝑥] − 𝑦_ ≤ 𝑏_
𝑥U, 𝑥V, … , 𝑥] ≥ 0
𝑦U, 𝑦V, … , 𝑦_ ≥ 0

Les programmes (P) et (PS) sont équivalents et admettront la même solution

39
 Forme Standard

On peut toujours passer de la forme canonique d’un PL à sa forme standard en

introduisant des variables supplémentaires appelées variables d’écart ou
variables de surplus.

40
 Incompatibilité des contraintes

Soit le problème (P) suivant :

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 5 𝑥# + 2 𝑥$ + 𝑥& 𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 5 𝑥# + 2 𝑥$ + 𝑥&

𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶ 𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑥# + 𝑥$ +2𝑥& = 1 𝑥# + 𝑥$ +2𝑥& = 1
(P)
𝑥# + 2𝑥$ +3𝑥& = 1 ⇔ 𝑥# + 2𝑥$ +3𝑥& = 1
2𝑥# + 4𝑥$ + 6𝑥& = 1 𝑥# + 2𝑥$ + 3𝑥& = 1/2
𝑥# , 𝑥$ , 𝑥& ≥ 0 𝑥# , 𝑥$ , 𝑥& ≥ 0

Nous remarquons que la deuxième et la troisième contrainte sont incompatibles,

donc la problème n’admet pas de solution

41
 Redondance des contraintes

Soit le problème (P) suivant :

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 5 𝑥# + 2 𝑥$ + 𝑥& 𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 5 𝑥# + 2 𝑥$ + 𝑥&

𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶ 𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑥# + 𝑥$ +2𝑥& = 1 𝑥# + 𝑥$ +2𝑥& = 1
(P)
𝑥# + 2𝑥$ +3𝑥& = 2 ⇔ 𝑥# + 2𝑥$ +3𝑥& = 2
2𝑥# + 4𝑥$ + 6𝑥& = 4
𝑥# , 𝑥$ , 𝑥& ≥ 0 𝑥# , 𝑥$ , 𝑥& ≥ 0

Nous remarquons que la deuxième et la troisième contrainte sont redondantes,

donc on peut éliminer l’une des contrainte 2 ou 3 sans changer le domaine
réalisable et la solution du problème (P)

42
 Problème 4 : Problème de localisation

Dans son prochain programme d’investissement, une société désire construire 1 ou 2

usines et peut être un entrepôt, sachant que ce dernier ne peut se trouver que là où il y
a un usine. La compagnie dispose d’un budget d’investissement de 15 millions de
dirhams et a le choix entre 3 villes pour installer ses nouvelles unités. On dispose
également des estimations du coût de construction et de la valeur nette actualisée
(VNA) de chaque usine et entrepôt. Pour des raisons socio-économiques la compagnie
ne peut pas installer plus d’une usine dans la même ville.
Usine Entrepôt
Villes Coût (en VNA (en Coût (en VNA (en millions)
millions) millions) millions)
Fès 6 9 1 3
Tanger 3 5 2 4
Rabat 5 6 3 5

• Proposer une formulation mathématique du problème qui permettra à la

compagnie de satisfaire ses exigences tout en maximisant la valeur nette
actualisée. 43
Après avoir modélisé un problème sous forme d’un programme mathématique
linéaire, il faut maintenant trouver des méthodes appropriées pour le résoudre.
Parmi les méthodes les plus utilisées nous trouvons :
• La méthode graphique (pour les problèmes simples à deux variables)
• La méthode du Simplexe
• La méthode du point intérieur

44
Après avoir modélisé un problème sous forme d’un programme mathématique
linéaire, il faut maintenant trouver des méthodes appropriées pour le résoudre.
Parmi les méthodes les plus utilisées nous trouvons :
• La méthode graphique (pour les problèmes simples à deux variables)
• La méthode du Simplexe
• La méthode du point intérieur

45
 3.1 Résolution Graphique

Comme annoncé dans le slide précédent, dans le cas de deux variables de

décision, un problème linéaire peut être résolu de manière purement
graphique en suivant le processus en trois étapes qui suit :
1. Représenter graphiquement la région réalisable.
2. Représenter graphiquement des lignes d’isovaleur de la fonction objectif
3. Optimum sera déterminé graphiquement comme le plan de production
situé sur la droite d’isoprofit la plus élevée, c’est-à-dire celle qui donne le
profit le plus élevé.

46
 3.1 Résolution Graphique

Comme annoncé dans le slide précédent, dans le cas de deux variables de

décision, un problème linéaire peut être résolu de manière purement
graphique en suivant le processus en trois étapes qui suit :
1. Représenter graphiquement la région réalisable.
2. Représenter graphiquement des lignes d’isovaleur de la fonction objectif
3. Optimum sera déterminé graphiquement comme le point situé sur la
droite d’isoprofit la plus élevée, c’est-à-dire celle qui donne le profit le plus
élevé.

47
 3.1 Résolution Graphique

Soit le problème linéaire suivant :

48
 3.1 Résolution Graphique

• Étape 1 : Représentation du domaine réalisable

On rappelle que le domaine réalisable est l’ensemble des points (x1, x2) satisfaisant
les inégalités

49
 3.1 Résolution Graphique

• Étape 1 : Représentation du domaine réalisable

• On rappelle que le domaine réalisable est l’ensemble des points (x1, x2) satisfaisant
les contraintes (1),(2),(3), (4) et (5).

• Graphiquement une inégalité telle que 3x1 + 2x2 ≤ 18 correspond à un demi-plan

limité par la droite obtenue en prenant l’inéquation à l’égalité (3x1 + 2x2 = 18).

• Lorsque l’on fait l’intersection des cinq demi-plans correspondant aux cinq
contraintes, on obtient le polygone hachuré suivant :

50
 3.1 Résolution Graphique

• Étape 1 : Représentation du domaine réalisable

Domaine réalisable du problème (P)

51
 3.1 Résolution Graphique

• Étape 2 : Représentation des lignes d’isovaleur de la fonction objectif

• On va devoir choisir entre ces différents plans de production.

• Pour ce faire on va représenter graphiquement des lignes d’isovaleur de la fonction objectif :

• En effet, on remarquera que l’expression de la fonction objectif fait intervenir trois variables
et ne peut donc être représentée que dans l’espace. Pour se ramener dans le plan, on va
considérer des valeurs successives de l’objectif :

52
 3.1 Résolution Graphique

• Étape 2 : Représentation des lignes d’isovaleur de la fonction objectif

• Ce qui correspond graphiquement à des droites parallèles

• Les points d’une de ces droites sont donc le lieu de tous les points donnant la même valeur
du profit (d’où le nom de droite d’isovaleur de la fonction objectif). Ceci est fait à la figure
où l’on a représenté z = 10, 20 et 36.
53
 3.1 Résolution Graphique

• Étape 3 : Solution optimale

• L’optimum sera déterminé graphiquement comme le point situé sur la droite d’isoprofit la
plus élevée, c’est-à-dire celle qui donne le profit le plus élevé

• On voit à la figure qu’il s’agit du point x∗ =(2,6).

54
3.1 Résolution Graphique

55
3.1 Résolution Graphique

56
Problème 1 : Fabricant de Yaourts

En se basant sur la méthode graphique déterminer une solution optimale

du problème de fabriquant de yaourts suivant :

57
 Problème : fabrique de bonbons

Vous avez décider d’ouvrir une fabrique de bonbons. Vous envisagez

de produire deux types de bonbons :A et B, les deux composés
uniquement de sucre, de noix et de chocolat. A l’heure actuelle,
vous avez en stock 100 kg de sucre, 20 kg de noix, et 30 kg de
chocolat. Le mélange utilisé pour faire le bonbon B doit contenir au
moins 20% de noix. Le mélange utilisée pour préparer le bonbon A
doit contenir au moins 10% de noix et 10% de chocolat. Chaque kilo
de B peut être vendu pour 25e, et chaque kilo de A pour 20e.

1) Formuler un PL qui vous permettra de maximiser vos revenus de vente.

2) Déterminer une solution optimale du problème

57
 3.2 Algorithme de simplexe

v Objectif

L’objectif de l’algorithme de simplexe est de déterminer une solution optimale à

un problème linéaire deux méthodes de calcul peuvent être utilisées dans cette
algorithme :
• La méthode Algébrique
• La méthode en Tableaux

58
 3.2 Algorithme de simplexe

Soit le problème linéaire suivant :

59
 3.2 Algorithme de simplexe

• Étape 1 : Représentation sous forme standard

Forme standard

𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 3 𝑥# + 5 𝑥$ 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 3 𝑥# + 5 𝑥$
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶ 𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑥# ≤ 4 𝑥# + 𝑒# = 4
2𝑥$ ≤ 12 ⇔ 2𝑥$ + 𝑒$ = 12
3𝑥# + 2𝑥$ ≤ 18 3𝑥# + 2𝑥$ + 𝑒& = 18
𝑥# , 𝑥$ ≥ 0 𝑥# , 𝑥$ , 𝑒# , 𝑒$ , 𝑒& ≥ 0

60
 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 3 𝑥# + 5 𝑥$
3.2 Algorithme de simplexe 𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑥# + 𝑒# = 4
• Étape 2 : Tableau de simplexe
2𝑥$ + 𝑒$ = 12
3𝑥# + 2𝑥$ + 𝑒& = 18
𝑥# , 𝑥$ , 𝑒# , 𝑒$ , 𝑒& ≥ 0
Variables hors bases

𝑥) 𝑥* 𝑒) 𝑒* 𝑒-

𝑒)

𝑒*

𝑒- Variables de bases

61
 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 3 𝑥# + 5 𝑥$
3.2 Algorithme de simplexe 𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑥# + 𝑒# = 4
• Étape 2 : Tableau de simplexe
2𝑥$ + 𝑒$ = 12
3𝑥# + 2𝑥$ + 𝑒& = 18
𝑥# , 𝑥$ , 𝑒# , 𝑒$ , 𝑒& ≥ 0

VB Valeurs 𝑥) 𝑥* 𝑒) 𝑒* 𝑒-
VB (b)
𝑒) 1 O 1 0 0

𝑒* 0 2 0 1 0

𝑒- 3 2 0 0 1

z 3 5 0 0 0

62
 𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 3 𝑥# + 5 𝑥$
3.2 Algorithme de simplexe 𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑥# + 𝑒# = 4
• Étape 2 : Tableau de simplexe
2𝑥$ + 𝑒$ = 12
3𝑥# + 2𝑥$ + 𝑒& = 18
𝑥# , 𝑥$ , 𝑒# , 𝑒$ , 𝑒& ≥ 0

VB Valeurs 𝑥) 𝑥* 𝑒) 𝑒* 𝑒-
VB (b)
𝑒) 4 1 O 1 0 0

𝑒* 12 0 2 0 1 0

𝑒- 18 3 2 0 0 1

z 0 3 5 0 0 0

Les coûts relatifs

63
 3.2 Algorithme de simplexe

• Étape 2 : Tableau de simplexe

VB Valeurs 𝑥) 𝑥* 𝑒) 𝑒* 𝑒-
VB (b)
𝑒) 4 1 O 1 0 0

𝑒* 12 0 2 0 1 0

𝑒- 18 3 2 0 0 1

z 0 3 5 0 0 0

• la solution est optimale si les coûts relatifs de toutes les variables hors-base sont
négatifs ou nuls.

64
 3.2 Algorithme de simplexe

• Étape 2 : Choix de la variable entrante (dans la base)

VB Valeurs 𝑥) 𝑥* 𝑒) 𝑒* 𝑒-
VB (b)
𝑒) 4 1 O 1 0 0

𝑒* 12 0 2 0 1 0

𝑒- 18 3 2 0 0 1

z 0 3 5 0 0 0

Ensuite, nous choisissons comme variable entrante dans la nouvelle base la

variable hors-base ayant le plus grand coût relatif (le plus petit pour un problème
de minimisation).
La variable entrante est donc 𝑥$
65
 3.2 Algorithme de simplexe

• Étape 2 : Choix de la variable sortante (de la base)

Colonne pivot
VB Valeurs 𝑥) 𝑥* 𝑒) 𝑒* 𝑒- b/ai
VB (b)
𝑒) 4 1 O 1 0 0 __

𝑒* 12 0 2 0 1 0 6

𝑒- 18 3 2 0 0 1 9

z 0 3 5 0 0 0

Nous appliquons la règle du plus petit rapport b/ai pour trouver la variable
sortante

66
 3.2 Algorithme de simplexe

• Étape 2 : Choix de la variable sortante (de la base)

Colonne pivot
VB Valeurs 𝑥) 𝑥* 𝑒) 𝑒* 𝑒- b/ai
VB (b)
𝑒) 4 1 O 1 0 0 __
Pivot
Ligne
pivot 𝑒* 12 0 2 0 1 0 6

𝑒- 18 3 2 0 0 1 9

z 0 3 5 0 0 0

Nous appliquons la règle du plus petit rapport b/ai pour trouver la variable
sortante
La variable sortante est donc 𝑒*

67
 3.2 Algorithme de simplexe

• Étape 3 : Pivotage
Le Pivotage s’effectue de la manière suivante :
- Nous commençons par diviser la ligne du pivot par le chiffre du pivot

VB Valeur 𝑥! 𝑥" 𝑒! 𝑒" 𝑒# b/ai

s VB
(b)
𝑒! 0

𝑥" 1

𝑒# 1

z 5/2

68
 3.2 Algorithme de simplexe

• Étape 3 : Pivotage
Le Pivotage s’effectue de la manière suivante :
- Nous commençons par diviser la colonne du pivot par le chiffre du pivot
- Ensuite nous divisons la ligne du pivot par le chiffre du pivot

VB Valeur 𝑥! 𝑥" 𝑒! 𝑒" 𝑒# b/ai

s VB
(b)
𝑒! 0

𝑥" 6 0 1 0 1/2 0

𝑒# 1

z 5/2

69
 3.2 Algorithme de simplexe

• Étape 3 : Pivotage
Le Pivotage s’effectue de la manière suivante :
- Nous commençons par diviser la colonne du pivot par le chiffre du pivot
- Ensuite nous divisons la ligne du pivot par le chiffre du pivot
- Pour le reste des valeurs nous appliquons la relation suivante :
' é$% ()*+,- +. /0*0..+ 1'(02×% é$% ()*+,- +. *'4.+ 1'(02
𝑎'% − ( )
1'(02

VB Valeur 𝑥! 𝑥" 𝑒! 𝑒" 𝑒# b/ai

s VB
(b)
𝑒! 0

𝑥" 6 0 1 0 1/2 0

𝑒# 1

z 5/2

70
 3.2 Algorithme de simplexe

• Étape 3 : Pivotage
Le Pivotage s’effectue de la manière suivante :
- Nous commençons par diviser la colonne du pivot par le chiffre du pivot
- Ensuite nous divisons la ligne du pivot par le chiffre du pivot
- Pour le reste des valeurs nous appliquons la relation suivante :
' é$% ()*+,- +. /0*0..+ 1'(02×% é$% ()*+,- +. *'4.+ 1'(02
𝑎'% − ( )
1'(02

VB Valeur 𝑥! 𝑥" 𝑒! 𝑒" 𝑒# b/ai

s VB
(b)
𝑒! 4 1 0 1 0 0

𝑥" 6 0 1 0 1/2 0

𝑒# 6 3 1 0 -1 1

z -30 3 5/2 0 -5/2 0

71
 Problème : Fabricant de Yaourts

En se basant sur la méthode de simplexe déterminer une solution optimale

du problème de fabriquant de yaourts suivant :

72
 Exercice

Un fabricant de pâtisseries souhaite maximiser son profit en produisant des

gâteaux et des biscuits. Pour chaque gâteau produit, il gagne 5 euros de profit et
pour chaque biscuit produit, il gagne 3 euros de profit. Le fabricant dispose de 10
heures de main-d'œuvre et de 20 kilogrammes de farine par jour. La production
d'un gâteau nécessite 2 heures de main-d'œuvre et 1 kilogramme de farine, tandis
que la production d'un biscuit nécessite 1 heure de main-d'œuvre et 0,5
kilogramme de farine. Le fabricant souhaite maximiser son profit quotidien en
déterminant combien de gâteaux et de biscuits il doit produire chaque jour.
1) Modéliser le problème sous forme d’un programme linéaire
2) Déterminer graphiquement la production optimale des chaises et des tables
3) Retrouver la production optimale via l’algorithme du Simplexe (avec relaxation des
contraintes d’intégrité)
72
Deuxième Partie
Dualité
Illustration par exemple Problème de production de huiles d’olives
Cultivar 1 Cultivar 2 Cultivar 3 Profit
Une coopérative produit deux qualités
d’huile d’olive à partir de trois variétés Huile A 30% 20% 50% 7 € /litre
(Cultivars). Huile B 50% 10% 40% 5 € /litre
• Quelles quantités de huiles doit-on
produire pour maximiser le profit ? Stock 500 kg 100 kg 400 kg

73
Illustration par exemple Problème de production de huiles d’olives
Cultivar 1 Cultivar 2 Cultivar 3 Profit
Une coopérative produit deux qualités
d’huile d’olive à partir de trois variétés Huile A 30% 20% 50% 7 € /litre
(Cultivars). Huile B 50% 10% 40% 5 € /litre
• Quelles quantités de huiles doit-on
produire pour maximiser le profit ? Stock 500 kg 100 kg 400 kg

𝑥& , 𝑥' : Quantités de huiles A et B produites

𝑀𝑎𝑥𝑖𝑚𝑖𝑒𝑟 7 𝑥. + 5 𝑥/

(Cultivar1) 0,3 𝑥. + 0,5 𝑥/ ≤ 500

(Cultivar2) 0,2 𝑥. + 0,1 𝑥/ ≤ 100

(Cultivar3) 0,5 𝑥. + 0,4 𝑥/ ≤ 400

𝑥. , 𝑥/ ≥ 0

73
Illustration par exemple Problème de production de huiles d’olives
Cultivar 1 Cultivar 2 Cultivar 3 Profit
Une coopérative produit deux qualités
d’huile d’olive à partir de trois variétés Huile A 30% 20% 50% 7 € /litre
(Cultivars). Huile B 50% 10% 40% 5 € /litre
• Quelles quantités de huiles doit-on
produire pour maximiser le profit ? Stock 500 kg 100 kg 400 kg

𝑥& , 𝑥' : Quantités de huiles A et B produites Un concurrent souhaite acheter tous les
stocks.
𝑀𝑎𝑥𝑖𝑚𝑖𝑒𝑟 7 𝑥. + 5 𝑥/ • À quels prix doit-il proposer les
cultivars afin de minimiser sa dépense ?
(Cultivar1) 0,3 𝑥. + 0,5 𝑥/ ≤ 500

(Cultivar2) 0,2 𝑥. + 0,1 𝑥/ ≤ 100

(Cultivar3) 0,5 𝑥. + 0,4 𝑥/ ≤ 400

𝑥. , 𝑥/ ≥ 0

73
Illustration par exemple Problème de production de huiles d’olives
Cultivar 1 Cultivar 2 Cultivar 3 Profit
Une coopérative produit deux qualités
d’huile d’olive à partir de trois variétés Huile A 30% 20% 50% 7 € /litre
(Cultivars). Huile B 50% 10% 40% 5 € /litre
• Quelles quantités de huiles doit-on
produire pour maximiser le profit ? Stock 500 kg 100 kg 400 kg

𝑥& , 𝑥' : Quantités de huiles A et B produites Un concurrent souhaite acheter tous les
stocks.
𝑀𝑎𝑥𝑖𝑚𝑖𝑒𝑟 7 𝑥. + 5 𝑥/ • À quels prix doit-il proposer les
cultivars afin de minimiser sa dépense ?
(Cultivar1) 0,3 𝑥. + 0,5 𝑥/ ≤ 500
y( , y), y* : Prix proposés pour chaque cultivar

(Cultivar2) 0,2 𝑥. + 0,1 𝑥/ ≤ 100

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 500 y) + 100 y* + 400 y-
(Cultivar3) 0,5 𝑥. + 0,4 𝑥/ ≤ 400
Profit de vente profit de vente
≥
𝑥. , 𝑥/ ≥ 0 des stocks des huiles

73
Illustration par exemple Problème de production de huiles d’olives
Cultivar 1 Cultivar 2 Cultivar 3 Profit
Une coopérative produit deux qualités
d’huile d’olive à partir de trois variétés Huile A 30% 20% 50% 7 € /litre
(Cultivars). Huile B 50% 10% 40% 5 € /litre
• Quelles quantités de huiles doit-on
produire pour maximiser le profit ? Stock 500 kg 100 kg 400 kg

𝑥& , 𝑥' : Quantités de huiles A et B produites Un concurrent souhaite acheter tous les
stocks.
𝑀𝑎𝑥𝑖𝑚𝑖𝑒𝑟 7 𝑥. + 5 𝑥/ • À quels prix doit-il proposer les
cultivars afin de minimiser sa dépense ?
(Cultivar1) 0,3 𝑥. + 0,5 𝑥/ ≤ 500
y( , y), y* : Prix proposés pour chaque cultivar

(Cultivar2) 0,2 𝑥. + 0,1 𝑥/ ≤ 100

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 500 y) + 100 y* + 400 y-
(Cultivar3) 0,5 𝑥. + 0,4 𝑥/ ≤ 400 (Huile A) 0,3 y) + 0,2 y* + 0,5 y- ≥ 7

𝑥. , 𝑥/ ≥ 0 (Huile B) 0,5 y) + 0,1 y* + 0,4 y- ≥ 5

y) , y* , y- ≥ 0

Primal Dual 74
 L’ « Entreprise » Le « Concurrent »
c, : Profit d’une unité de produit i
b+ : Profit d’une unité de produit j Quels prix unitaires (𝑦+ ) compétitifs faut-
a,+ : Quantité de ressources j nécessaire pour il proposer pour racheter les ressources
une unité de produit i de l’entreprise à coût minimum
Quelles quantités (𝑥+ ) de produit j à y+ : Prix pour la ressource j
fabriquer avec les ressources
disponibles pour maximiser le profit 1
𝑀inimiser - b+ y+
/ +.(
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
𝑀aximiser - 𝑐- 𝑥- 2
-.( - 𝑎0- y+ ≥ 𝑏+ , 𝑗 = 1, … . n
𝑆𝑜𝑢𝑠 𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 ∶
/ -.(
𝑥- ≥ 0
- 𝑎0- 𝑥- ≤ 𝑏0 , 𝑗 = 1, … . 𝑚
-.(
𝑥- ≥ 0

Primal Dual 75
Le programme dual est une symétrie du programme primal, de façon général :
• À toute contrainte du primal correspond une variable du duale;
• À toute variable du primal correspond une contrainte du duale;
• les coefficients de la fonction objectif primale sont les deuxièmes
membres ( b) du dual et réciproquement.
• Il est à noter que le dual du dual est le primal.

76
Tableau des signes

77
Exemple

77
 Exemple

Déterminer le dual du programme suivant :

78
 Dualité faible

Pour toute solution du dual et pour toute solution du primal, la valeur objectif
du dual z=cx* est supérieur ou égal à celui du primal v=bw*.

Dualité forte

Si le primal a une solution optimale x* alors le dual a une solution optimale w*

et la valeur objectif du primal est égal à celle du dual.

79
 Théorème des écarts complémentaires

Soient les solutions réalisables x* du primal et u* du dual alors:

∀𝑗 ∈ [1 … . 𝑚]

𝑥g∗ > 0 ⟹ 𝑢∗ 𝑎.g = 𝑐g

B ∗
𝑢 𝑎.g > 𝑐g ⇒ 𝑥g∗ = 0

∀𝑖 ∈ [1 … . 𝑛]

𝑎^. 𝑥 ∗ < 𝑏^ ⟹ 𝑢^∗ = 0

B ∗
𝑢^ > 0 ⇒ 𝑎^. 𝑥 ∗ = 𝑏^

80
 Exemple

𝑀𝑎𝑥𝑖𝑚𝑖𝑒𝑟 200 𝑥. + 300 𝑥/

(C1) 3 𝑥. + 2 𝑥/ ≤ 600

(C2) 𝑥. + 2 𝑥/ ≤ 400

(C3) 𝑥. + 𝑥/ ≤ 225

𝑥. , 𝑥/ ≥ 0

𝒙𝑨 = 𝟓𝟎, 𝒙𝑩 = 𝟏𝟕𝟓

80
 Propriétés des écarts complémentaires

Déterminer en utilisant les écarts complémentaires une solution optimale du dual

du programme suivant :

81