Video RO1

Recherche opérationnelle
Filière Sciences Économiques et Gestion

Semestre 5
Mohamed HACHIMI
UNIVERSITÉ IBNOU ZOHR

FACULTÉ DES SCIENCES JURIDIQUES ECONOMIQUES
ET SOCIALES D’AGADIR
http://hachimicours.uiz.ac.ma
1
M. Hachimi Recherche opérationnelle Semestre 5 1 / 28
1
Modélisation

Maximisation
Sommaire
1 Maximisation
2 Minimisation

Maximisation
É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.

Maximisation

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.

Maximisation

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.

Maximisation
On dispose chaque jour de :

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

Maximisation

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.

Maximisation

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 ?

Maximisation
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

Maximisation
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 ?

Maximisation

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

tidiennement, n’est-ce pas ?

Maximisation


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

Maximisation


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.

Maximisation
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.

Maximisation
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.

Maximisation
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

Maximisation
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.

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

Maximisation
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.

Maximisation
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

Maximisation
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)

Maximisation
Les contraintes
Contraintes relatives aux matières premières
En s’inspirant de la contrainte relative à la machine, ces

contraintes s’écrivent tout naturellement :
2x1 + 2x2 6 10 (p)

9x1 + 4x2 6 36 (q)

Maximisation
Les contraintes
Contraintes de positivité
Elles assurent que la solution ne comporte pas des valeurs né-

gatives (inacceptables).
x1 , x2 > 0,

Maximisation
Le modèle
Le modèle se résume ainsi :

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

Maximisation
Le modèle

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

Maximisation
Variables d’écart
Afin de ramener les contraintes à des égalités (qui sont plus fa-
ciles à 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é dispo-

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

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

contraintes (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

Maximisation
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’uti-
lisation 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


Minimisation
Sommaire
1 Maximisation
2 Minimisation

Minimisation
Un agriculteur souhaite que son troupeau consomme la plus

faible ration quotidienne de trois éléments nutritifs A, B et C.

Minimisation

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.

Minimisation

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.

Minimisation
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

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 to-

tal 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

Minimisation
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.

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

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.

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


Video RO1

Transféré par

Droits d'auteur :

Formats disponibles

Video RO1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Video RO1

Transféré par

Droits d'auteur :

Formats disponibles

Recherche opérationnelle

Filière Sciences Économiques et Gestion

UNIVERSITÉ IBNOU ZOHR

M. Hachimi Recherche opérationnelle Semestre 5 2 / 28

M. Hachimi Recherche opérationnelle Semestre 5 3 / 28

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

M. Hachimi Recherche opérationnelle Semestre 5 4 / 28

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

M. Hachimi Recherche opérationnelle Semestre 5 4 / 28

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

M. Hachimi Recherche opérationnelle Semestre 5 4 / 28

On dispose chaque jour de :

M. Hachimi Recherche opérationnelle Semestre 5 5 / 28

On dispose chaque jour de :

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

M. Hachimi Recherche opérationnelle Semestre 5 5 / 28

On dispose chaque jour de :

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

M. Hachimi Recherche opérationnelle Semestre 5 5 / 28

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

M. Hachimi Recherche opérationnelle Semestre 5 6 / 28

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

M. Hachimi Recherche opérationnelle Semestre 5 7 / 28

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

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

M. Hachimi Recherche opérationnelle Semestre 5 7 / 28

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

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

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

x1 = la quantité du produit A à produire

M. Hachimi Recherche opérationnelle Semestre 5 7 / 28

Les variables de décision

Quelles sont les informations dont doit disposer le directeur de

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

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

x1 = la quantité du produit A à produire

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

M. Hachimi Recherche opérationnelle Semestre 5 7 / 28

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

M. Hachimi Recherche opérationnelle Semestre 5 8 / 28

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

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

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

M. Hachimi Recherche opérationnelle Semestre 5 9 / 28

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

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

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

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

M. Hachimi Recherche opérationnelle Semestre 5 10 / 28

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

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

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

M. Hachimi Recherche opérationnelle Semestre 5 11 / 28

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

M. Hachimi Recherche opérationnelle Semestre 5 12 / 28

Contrainte relative à la machine m