Mathématiques de Gestion

Recherche Opérationnelle

Mohamed HACHIMI

Audit et Contrôle de Gestion

Année universitaire 2009-10

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Chapitre I

Modélisation

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Une entreprise fabrique deux produits A et B, en utilisant une

machine m et deux matières premières p et q.
On suppose que :
— la production d’une unité de A nécessite 2 kg de p et 9 kg de
q, et utilise la machine m durant 1 heure ;
— la production d’une unité de B nécessite 2 kg de p et 4 kg de
q, et utilise la machine m durant 2 heure.
Les profits réalisés sont de :
50 dh par unité de A et 60 dh par unité de B.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Une entreprise fabrique deux produits A et B, en utilisant une

machine m et deux matières premières p et q.
On suppose que :
— la production d’une unité de A nécessite 2 kg de p et 9 kg de
q, et utilise la machine m durant 1 heure ;
— la production d’une unité de B nécessite 2 kg de p et 4 kg de
q, et utilise la machine m durant 2 heure.
Les profits réalisés sont de :
50 dh par unité de A et 60 dh par unité de B.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Une entreprise fabrique deux produits A et B, en utilisant une

machine m et deux matières premières p et q.
On suppose que :
— la production d’une unité de A nécessite 2 kg de p et 9 kg de
q, et utilise la machine m durant 1 heure ;
— la production d’une unité de B nécessite 2 kg de p et 4 kg de
q, et utilise la machine m durant 2 heure.
Les profits réalisés sont de :
50 dh par unité de A et 60 dh par unité de B.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

On dispose chaque jour de :

8 heures de m, de 10 kg de p et de 36 kg de q.

L’objectifque poursuit l’entreprise est de maximiser le profit

qu’elle pourra tirer, par jour, de ces 2 produits en utilisant au
mieux ses ressources.

Autrement dit :
Combien d’unités de A et de B doit-on produire afin d’obtenir
un profit maximal ?

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

On dispose chaque jour de :

8 heures de m, de 10 kg de p et de 36 kg de q.

L’objectifque poursuit l’entreprise est de maximiser le profit

qu’elle pourra tirer, par jour, de ces 2 produits en utilisant au
mieux ses ressources.

Autrement dit :
Combien d’unités de A et de B doit-on produire afin d’obtenir
un profit maximal ?

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

On dispose chaque jour de :

8 heures de m, de 10 kg de p et de 36 kg de q.

L’objectifque poursuit l’entreprise est de maximiser le profit

qu’elle pourra tirer, par jour, de ces 2 produits en utilisant au
mieux ses ressources.

Autrement dit :
Combien d’unités de A et de B doit-on produire afin d’obtenir
un profit maximal ?

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Le tableau suivant résume les données afférentes à ce problème

de production :

A B Disponible
m 1h 2h 8h
p 2 kg 2 kg 10 kg
q 9 kg 4 kg 36 kg
Profit unitaire 50 dh 60 dh

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

l’entreprise pour considérer que son problème est résolu ?

Il suffit de connaître la quantité de A et celle de B à fabriquer quo-

tidiennement, n’est-ce pas ?

Agissons comme si ces quantités nous étaient connues et

dénotons-les par :

x1 = la quantité du produit A à produire

x2 = la quantité du produit B à produire

Les variables x1 et x2 sont dites variables de décision.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

l’entreprise pour considérer que son problème est résolu ?

Il suffit de connaître la quantité de A et celle de B à fabriquer quo-

tidiennement, n’est-ce pas ?

Agissons comme si ces quantités nous étaient connues et

dénotons-les par :

x1 = la quantité du produit A à produire

x2 = la quantité du produit B à produire

Les variables x1 et x2 sont dites variables de décision.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

l’entreprise pour considérer que son problème est résolu ?

Il suffit de connaître la quantité de A et celle de B à fabriquer quo-

tidiennement, n’est-ce pas ?

Agissons comme si ces quantités nous étaient connues et

dénotons-les par :

x1 = la quantité du produit A à produire

x2 = la quantité du produit B à produire

Les variables x1 et x2 sont dites variables de décision.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

l’entreprise pour considérer que son problème est résolu ?

Il suffit de connaître la quantité de A et celle de B à fabriquer quo-

tidiennement, n’est-ce pas ?

Agissons comme si ces quantités nous étaient connues et

dénotons-les par :

x1 = la quantité du produit A à produire

x2 = la quantité du produit B à produire

Les variables x1 et x2 sont dites variables de décision.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

La fonction objectif

Quel profit retirera l’entreprise de la vente de ces deux produits ?

Ils’agit, tout simplement, d’additionner les bénéfices à tirer de
chacun des 2 produits :
— pour A, elle retire 50 dh par unité et en fabrique x1 unités ;
cette production lui rapporte donc un profit de (50 x1 ) dh ;
— de même, la quantité x2 de B lui permet de faire un profit de
(60 x2 ) dh.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

La fonction objectif

Le profit total à tirer des deux produits s’élève donc à :

(50 x1 + 60 x2 ) dh

On dénote ce profit total par z et laisse implicite l’unité monétaire :

z = 50 x1 + 60 x2

On cherche évidemment à rendre z aussi grand que possible en

donnant à x1 et x2 des valeurs appropriées.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

La fonction objectif

La grandeur z est une fonction qui, à chaque plan de production

(x1 , x2 ), associe le nombre de dirhams que l’entreprise retirerait
comme profit si elle adoptait ce plan.

Cette fonction z, qui traduit l’objectif de notre problème, s’appelle

fonction objectif ou fonction économique.

Comme on cherche à rendre z aussi grand que possible, on écrit :

Maximiser z où z = 50 x1 + 60 x2

Ce que généralement l’on convient d’abréger comme suit :

Max z = 50 x1 + 60 x2

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

S’il ne s’agissait pour l’entreprise que de maximizer z, il suffirait

de laisser augmenter x1 ou x2 pour que z prenne une valeur aussi
grande qu’elle le souhaite.

Mais s’attendre à de tels profits s’apparente plus au rêve qu’à la

situation de notre entreprise.

IIl y a bien sûr des empêchements naturels, appelés contraintes,

qui freinent le rêve d’un profit infini.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

Prenons en considération tour à tour chacune des contraintes.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

Contrainte relative à la machine m

Le temps d’utilisation de la machine m pour fabriquer les produits

A et B ne peut excéder les 8 heures disponibles :

Temps d’utilisation de m 6 8.

Ce temps utilisé est la somme des heures consacrées à chacun

des types de produits.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

Pour A, le temps nécessaire à la fabrication de la quantité x1 se

calcule ainsi :

1 heure/(unité de A) × x1 (unité de A) = x1 heures

pour B, on procède de façon analogue :

2 heure/(unité de B) × x2 (unité de B) = 2x2 heures

La contrainte relative à la machine m s’écrit donc :

x1 + 2x2 6 8 (m)

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

Pour A, le temps nécessaire à la fabrication de la quantité x1 se

calcule ainsi :

1 heure/(unité de A) × x1 (unité de A) = x1 heures

pour B, on procède de façon analogue :

2 heure/(unité de B) × x2 (unité de B) = 2x2 heures

La contrainte relative à la machine m s’écrit donc :

x1 + 2x2 6 8 (m)

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

Contraintes relatives aux matières premières

En s’inspirant de la contrainte relative à la machine, ces con-

traintes s’écrivent tout naturellement :

2x1 + 2x2 6 10 (p)

9x1 + 4x2 6 36 (q)

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Les contraintes

Contraintes de positivité

Elles assurent que la solution ne comporte pas des valeurs néga-

tives (inacceptables).
x1 , x2 > 0,

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Le modèle

Le modèle se résume ainsi :

Max z = 50x1 + 60x2




x1 + 2x2 6 8



(P) 2x1 + 2x2 6 10 soit : x1 + x2 6 5
9x1 + 4x2 6 36






x1 , x2 > 0

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Le modèle

Le modèle se résume ainsi :

Max z = 50x1 + 60x2




x1 + 2x2 6 8



(P) 2x1 + 2x2 6 10 soit : x1 + x2 6 5
9x1 + 4x2 6 36






x1 , x2 > 0

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Variables d’écart

Afin de ramener les contraintes à des égalités (qui sont plus

faciles à traiter que les inégalités), on introduit des variables
d’écart.

Ces variables seront toujours, comme les variables de décision

x1 et x2 , positives ou nulles.

La variable d’écart d’une contrainte représente la quantité

disponible non utilisée. C’est l’écart entre la disponibilité et le
besoin.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Variables d’écart

Après l’ajout des variables d’écart x3 , x4 et x5 relatives aux con-

traintes (m), (p) et (q), nous obtenons la formulation :

Max z = 50x1 + 60x2





x1 + 2x2 + x3 = 8



(P) 2x1 + 2x2 + x4 = 10
9x1 + 4x2 + x5 = 36






x1 , x2 , x3 , x4 , x5 > 0

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Généralisation : Problème de production

Soient m machines Mi (i=1, . . . , m) qui fabriquent en série n types
de produits Pj (j = 1, . . . , n). Mi a une capacité maximum de
bi unités de temps. La fabrication d’une unités de Pj nécessite
l’utilisation de Mi durant aij unités de temps.
Si cj représente le gain relatif à la production d’une unité du pro-
duit Pj , le problème s’écrit :

 Max z = c1 x1 + c2 x2 + · · · + cn xn



a11 x1 + a12 x2 + · · · + a1n xn 6 b1 (M1 )





a21 x1 + a22 x2 + · · · + a2n xn 6 b2 (M2 )


.. .. ..
. . .




a x + a x + + amn xn 6 bm (Mm )



 m1 1 m2 2 · · ·

x1 , x2 , . . . , xn > 0


Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Un agriculteur souhaite que son troupeau consomme la plus

faible ration quotidienne de trois éléments nutritifs A, B et C.
L’agriculteur achète deux types d’aliments P et Q :
— une unité de P comprend 2 unités de A, 1 unité de B et 1 unité
de C ; et elle coûte 20 dh
— une unité de Q comprend 1 unité de A, 1 unité de B et 3 unités
de C ; et elle coûte 40 dh.
Les exigences quotidiennes sont de :
16 pour A, 12 pour B et 18 pour C.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Un agriculteur souhaite que son troupeau consomme la plus

faible ration quotidienne de trois éléments nutritifs A, B et C.
L’agriculteur achète deux types d’aliments P et Q :
— une unité de P comprend 2 unités de A, 1 unité de B et 1 unité
de C ; et elle coûte 20 dh
— une unité de Q comprend 1 unité de A, 1 unité de B et 3 unités
de C ; et elle coûte 40 dh.
Les exigences quotidiennes sont de :
16 pour A, 12 pour B et 18 pour C.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

Un agriculteur souhaite que son troupeau consomme la plus

faible ration quotidienne de trois éléments nutritifs A, B et C.
L’agriculteur achète deux types d’aliments P et Q :
— une unité de P comprend 2 unités de A, 1 unité de B et 1 unité
de C ; et elle coûte 20 dh
— une unité de Q comprend 1 unité de A, 1 unité de B et 3 unités
de C ; et elle coûte 40 dh.
Les exigences quotidiennes sont de :
16 pour A, 12 pour B et 18 pour C.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Énonce du problème

L’agriculteur cherche la combinaison la moins coûteuse des

quantités de P et Q qui respectera l’exigence de consommation
minimale d’éléments nutritifs.

Le tableau suivant résume les données relatives ce problème :

P Q Besoins minimaux
A 2 1 16
B 1 1 12
C 1 3 18
Coût unitaire 20 dh 40 dh

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

La construction d’un modèle linéaire

Appelons x1 et x2 les quantités des aliments P et Q qu’il faut

acheter.

L’objectif de l’agriculteur est évidemment de minimiser le coût

total des aliments qu’il faut acheter. Mathématiquement cela
s’écrit :
Minimiser z = 20x1 + 40x2
ce que généralement l’on convient d’abréger comme suit :

Min z = 20x1 + 40x2

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

La construction d’un modèle linéaire

Chacun des 3 éléments nutritifs à considérer donne lieu à une

contrainte, qui vise à exiger que les aliments, dans leur ensemble,
satisfassent les besoins quotidiens du troupeau. On obtient :

2x1 + x2 > 16 (A)

x1 + x2 > 12 (B)
x1 + 3x2 > 18 (C)

Les contraintes ci-dessus emploie le signe « > » parce qu’il faut

respecter les exigences de consommation minimales, mais que
celles-ci peuvent être dépassées.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

La construction d’un modèle linéaire

Enfin, il faut pas oublier qu’on peut pas acheter des quantités
négatives de P ou Q :
x1 , x2 > 0
Le modèle se résume ainsi :
Min z = 20x1 + 40x2




2x1 + x2 > 16



x1 + x2 > 12
x1 + 3x2 > 18






x1 , x2 > 0

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Généralisation : Problème de mélange

Il s’agit de rechercher un régime alimentaire qui, tout en étant le

meilleur marché possible, garantisse un apport suffisant en élé-
ments nutritifs.

Soient n aliments de prix cj (j = 1, . . . , n) par unité ; m éléments

nutritifs ; aij la quantité du ième élément nutritif contenue dans une
unité du jème aliment ; bi (i = 1, . . . , m) les besoins respectifs en
les m éléments nutritifs.

Mohamed Hachimi Mathématiques de Gestion

 Maximisation
Minimisation

Généralisation : Problème de mélange

Si les variables xj (j = 1, . . . , n) représentent les quantités des

divers aliments du régime, on obtient le problème

Min z = c1 x1 + c2 x2 + · · · + cn xn




a11 x1 + a12 x2 + · · · + a1n xn > b1





a21 x1 + a22 x2 + · · · + a2n xn > b2


.. .. ..
. . .




a x + a x + + amn xn > bm



 m1 1 m2 2 · · ·

x1 , x2 , . . . , xn > 0


Mohamed Hachimi Mathématiques de Gestion