Recherche Opérationnelle et

Informatique de Gestion
3ème année de Licence: Sciences de Gestion
FEG-Settat
Prof. Khabouze & Prof. Drissi

2024-2025
Objectifs du cours

➢ Comprendre les techniques d'optimisation dans

le cas de la programmation linéaire.

➢ Appliquer ces concepts à des problèmes

économiques et de gestion.
Plan du cours
I. Introduction à l'optimisation
➢ Concept d'optimisation en économie
➢ Exemples : Maximisation de fonctions d'utilité, profit et production.
➢ Notion de contrainte : contrainte de budget, de production, etc.

II. Introduction à la programmation linéaire

➢ Définition et structure d’un problème de programmation linéaire : fonction
objectif, contraintes et variables de décision.

➢ Exemples économiques classiques (production, allocation des

ressources).
➢ Représentation géométrique des solutions
Plan du cours (2)
III- Méthode du Simplexe

➢ Principe de la méthode du Simplexe.

➢ Résolution graphique des petits problèmes linéaires (cas à deux

variables).

➢ Résolution algorithmique par Simplexe.

IV- Dualité en programmation linéaire
➢ Interprétation économique du problème dual.
➢ Utilité du théorème de dualité pour la théorie des prix et des ressources
rares
Plan du cours (3)
V- Résolution de problèmes économiques avec la programmation

linéaire

➢ Modèles d'allocation de ressources.

➢ Optimisation de portefeuilles d’investissement.

➢ Cas d'étude : programmation linéaire appliquée à la production.

I-Introduction
I- Le concept d'optimisation en économie

Exemples d'optimisation en économie :

➢ Consommateur : Un consommateur cherche à maximiser son utilité

(satisfaction) en fonction de son revenu et des prix des biens.

➢ Entreprise : Une entreprise cherche à minimiser ses coûts pour une

production donnée ou à maximiser ses profits en fonction des prix de
vente et des coûts de production.

➢ Marché du travail : Un employeur peut chercher à minimiser les coûts

de main-d'œuvre tout en répondant à la demande de production.
I-Introduction

I- Le concept d'optimisation en économie

➢ Se réfère à l'analyse et à la prise de décisions visant à maximiser ou

minimiser une fonction économique: le profit, l'utilité ou les coûts,
sous certaines contraintes: budget, les ressources ou la technologie

Voici les points clés pour comprendre ce concept :

I-Introduction

I- Le concept d'optimisation en économie

Maximisation
➢ Il s'agit de trouver la solution qui maximise une fonction économique

➢ Ex. maximiser le profit d'une entreprise, l'utilité d'un consommateur, ou

la production d'une usine.

Minimisation:

➢ Trouver la solution qui minimise une certaine fonction

➢ Ex. minimiser les coûts de production ou les pertes économiques

I-Introduction

I- Le concept d'optimisation en économie

Formulation et modélisation
Définir :

➢ Les alternatives de décision (Variables de décision)

➢ L’objectif qui nous permet d'évaluer les différentes alternatives

(Fonction objectif)

➢ Les restrictions ou limitations auxquelles nous sommes confrontés

(Contraintes)
I-Introduction
I- Le concept d'optimisation en économie

Fonction Objectif:

➢ est la fonction mathématique que l'on cherche à maximiser ou

minimiser. Elle représente l'objectif de l'agent économique (entreprise,
consommateur, gouvernement, etc.).

➢ Ex.1 Entreprise :Maximiser le profit, défini par Profit=Revenu - Coûts.

➢ Ex.2 Consommateur : Maximiser l'utilité, définie par une fonction

d'utilité représentant les préférences du consommateur.
I-Introduction
I- Le concept d'optimisation en économie

Contraintes:

➢ En économie, les agents ne peuvent pas agir sans limites.

Les décisions sont souvent limitées par des contraintes :

➢ Contraintes budgétaires : Un consommateur ne peut pas dépenser plus

que son revenu.

➢ Contraintes de production : Une entreprise ne peut pas produire plus que

ce que permettent ses ressources disponibles.

➢ Contraintes technologiques : Les limites imposées par la technologie

disponible dans le processus de production.
I-Introduction
I- Le concept d'optimisation en économie

Optimisation sous contraintes :

est la recherche de la solution optimale en tenant compte des limites

imposées (budget, ressources, etc.).
I-Introduction
I- Le concept d'optimisation en économie

Outils d'optimisation:

➢ Calcul différentiel : En économie, on utilise les dérivées pour analyser

comment les changements dans les variables économiques affectent la
fonction objectif (par exemple, le profit ou l'utilité).

➢ Programmation linéaire : Utilisée pour optimiser une fonction linéaire

sous contraintes linéaires, particulièrement dans des problèmes
d’allocation de ressources.

➢ Modèles économétriques : Ceux-ci peuvent être utilisés pour

optimiser des décisions économiques basées sur des données réelles.
I-Introduction (15)
I- 3 Méthode de résolution

➢ Dans notre cours nous allons utiliser la méthode dite méthode du

simplexe : C'est l'une des méthodes les plus courantes pour résoudre les
problèmes de programmation linéaire.

➢ Il consiste à explorer les sommets du polyèdre défini par les contraintes

jusqu'à trouver la solution optimale
 Problème de production
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.
A B

Fraise (kg) 2 1

Lait (kg) 1 2

Sucre (kg) 0 1

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

[Link] vente de 1 unité de yaourts A et B rapporte
respectivement 4$ et 5$.
Le fabricant cherche à maximiser son profit
 Problème de production-2
Trois questions clés :

Sur quelles quantités peut-on travailler?

Que cherche-t-on à optimiser?
Quelles sont les contraintes du problème ?
Modélisation
Modélisation-2
Modélisation-3
Modélisation-4

A B
Fraise (kg) 2 1

Lait (kg) 1 2
Sucre (kg) 0 1
 Problème II
➢ 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 fabriquant 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, combien doit-il produire de petites et de grosses voitures au moyen de
ces stocks afin de maximiser son chiffre d’affaire ?
 Modélisation

Nous appellerons x le nombre de grosses voitures produites, y le

nombre de petites voitures produites, et z le chiffre d’affaire résultant.
Le problème se traduit alors sous la forme:

GV PV
Caoutchouc 1 1

Acier 2 1
 Rappels de géométrie
Une inégalité linéaire à deux variables peut s'exprimer de la manière suivante :
𝑎. 𝒙𝟏 + 𝑏.𝒙𝟐 +𝑐 ≤ 0 , 𝑎.𝒙𝟏+ 𝑏.𝒙𝟐 +𝑐 ≥0

Exemple : 4.𝒙𝟐 + 2.𝒙𝟏 +8 ≤ 0

On représente la droite 4.𝒙𝟐 + 2.𝒙𝟏 + 8 = 0

Elle passe par les points (𝒙𝟏 , 𝒙𝟐) :

A (0 , -2) et B (-4 , 0)

La droite découpe le plan en deux parties

dont l'une est la solution de l'inégalité.
 Rappels de géométrie
Une inégalité linéaire à deux variables peut s'exprimer de la manière suivante :
𝑎. 𝒙𝟏 + 𝑏.𝒙𝟐 +𝑐 ≤ 0 , 𝑎.𝒙𝟏+ 𝑏.𝒙𝟐 +𝑐 ≥0

Exemple : 4.𝒙𝟐 + 2.𝒙𝟏 +8 ≤ 0

On représente la droite 4.𝒙𝟐 + 2.𝒙𝟏 + 8 = 0

Elle passe par les points (𝒙𝟏 , 𝒙𝟐) :

A (0 , -2) et B (-4 , 0)

La solution de l'inégalité est la partie

située en dessous de la droite.
 Rappels de géométrie

Exemples :

Résoudre graphiquement l’inégalité :

𝟐.𝒙𝟏 − 𝟑.𝒙𝟐 + 𝟓 ≤ 𝟎
 Rappels de géométrie
Exemples : 𝟐.𝒙𝟏 − 𝟑.𝒙𝟐 + 𝟓 ≤ 𝟎

La droite passe par les points (𝒙𝟏 , 𝒙𝟐) :

A (0 , 5/3) et B (-5/2 , 0)

La solution de l'inégalité est la partie

située au dessus de la droite.
 Rappels de géométrie

Exemples :

Résoudre graphiquement l’inégalité :

𝟓.𝒙𝟏 + 𝟒.𝒙𝟐 ≥ 0
 Rappels de géométrie
Exemples : 𝟓.𝒙𝟏 + 𝟒.𝒙𝟐 ≥ 0

La droite passe par les points (𝒙𝟏 , 𝒙𝟐) :

A (0 , 0) et B (4 , -5)

La solution de l'inégalité est la partie

située au dessus de la droite.
 Rappels de géométrie

Exemples :

Résoudre graphiquement l’inégalité :

𝒙𝟐 ≥ 𝟐
 Rappels de géométrie
Exemples : 𝒙𝟐 ≥ 𝟐

La droite passe par les points (𝒙𝟏 , 𝒙𝟐) :

A (0 , 2) et est parallèle à l’axe des x1

La solution de l'inégalité est la partie

située au dessus de la droite.
 Résolution graphique
Exemple :
 Résolution graphique
Exemple :
 Résolution graphique

Sommets du polygone

B (0 , 6) C (2 , 6) Exemple de calcul d’un sommet du polygone (le point C) :

Intersection entre les droites :

x2 = 6 et 3 x1 + 2 x2 = 18

D (4 , 3) Solution :
x1 = 2 et x2 = 6

A (0 , 0) E (4 , 0)
 Résolution graphique
Exemple :

Famille de droites parallèles représentant différentes valeurs

de Z et passant par la région réalisable.

Direction améliorant la valeur de Z

Résolution graphique

Point optimal :
Point optimal (2 , 6)

Valeur maximale :
Z
=3x2+5x6
= 36
 Résolution algébrique

S’il en existe, il y a toujours une solution optimale sur au moins un sommet (point extrême)
de la région réalisable.

Pour trouver l’optimum, il ”suffit” d’examiner les points extrêmes de la région réalisable.
 Résolution graphique
Autre exemple :

2 x1 + x2 = 10

4 x1 + 5 x2 = 40
Résolution graphique

Sommets

2 x1 + x2 = 10

B (0 , 8)
C (1,66 , 6,66)

4 x1 + 5 x2 = 40

A (0 , 0) D (5, 0)
 Résolution graphique
On peut tracer les droites parallèles représentant Z

B (0 , 8)
C (1,66 , 6,66)
Direction améliorant
la valeur de Z
Z=2

Z = 1,6

Point optimal A (0 , 0) D (5, 0)

 Résolution algébrique
On peut tracer les droites parallèles représentant Z

Z = 0,4.X1 + 0,8.X2
A (0 , 0) Z=0
B (0 , 8) Z = 6,4
C (1,66 , 6,66) Z=6
D (5 , 0) Z=2
 Types de solutions
Les exemples traités pour l’instant ont une solution unique. Ceci n’est pas toujours le cas.
 Types de solutions
Solution optimale multiple avec zone réalisable bornée
 Types de solutions
Solution optimale multiple avec zone réalisable bornée

Tous les points de ce

segment sont des
solutions optimales
 Autres cas
Solution optimale multiple avec zone réalisable non bornée

Tous les points de ce

segment sont des
solutions optimales
 Autres cas
Aucune solution optimale finie

Direction améliorant la valeur de Z

 Autres cas
Zone réalisable vide :
aucune solution

Aucune intersection
entre les zones
délimitées par les
contraintes
2 x1 + 4 x2 = 8

x1 + 2 x2 = 2
Exercice
 Modélisation

Nous appellerons X1 le nombre de modèles produits de type A, X2 le

nombre de modèles produits de type B et Z le bénéfice résultant.
Le problème se traduit alors sous la forme:

Maximiser Z = 100 X1 + 120 X2

Sous les contraintes 3 X1 + 4 X2 ≤ 4200

X1 + 3 X2 ≤ 2400
2 X1 + 2 X2 ≤ 2600
X1 , X2 ≥ 0
 Maximiser Z = 100 X1 + 120 X2

Sous les contraintes 3 X1 + 4 X2 ≤ 4200

X1 + 3 X2 ≤ 2400
2 X1 + 2 X2 ≤ 2600
2X1 + 2X2=2600

3X1 + 4X2=4200

X1 + 3X2=2400
 Maximiser Z = 100 X1 + 120 X2

Sous les contraintes 3 X1 + 4 X2 ≤ 4200

2X1 + 2X2=2600
X1 + 3 X2 ≤ 2400
2 X1 + 2 X2 ≤ 2600
3X1 + 4X2=4200

X1 + 3X2=2400
.
.
Zone réalisable .
. .
 Maximiser Z = 100 X1 + 120 X2

Sous les contraintes 3 X1 + 4 X2 ≤ 4200

2X1 + 2X2=2600
X1 + 3 X2 ≤ 2400
2 X1 + 2 X2 ≤ 2600
3X1 + 4X2=4200

X1 + 3X2=2400
.
B(0 , 800)
.C(600 , 600)

Zone réalisable . D(1000 , 300)

A(0 , 0)
. .E(1300 , 0)
 Maximiser Z = 100 X1 + 120 X2

Sous les contraintes 3 X1 + 4 X2 ≤ 4200

2X1 + 2X2=2600
X1 + 3 X2 ≤ 2400
2 X1 + 2 X2 ≤ 2600
3X1 + 4X2=4200

X1 + 3X2=2400
.
B(0 , 800)
.
C(600 , 600)
Point optimal

. D(1000 , 300)

A(0 , 0)
. .E(1300 , 0)

Z = 100.000

Z = 50.000
 Résolution algébrique

Les points d'intersection Z = 100 X1 + 120 X2

A(0 , 0) 0
B(0 , 800) 96000
C(600 , 600) 132000
D(1000 , 300) 136000
E(1300 , 0) 130000
 Exercice

Dans une exploitation agricole, on doit choisir entre deux types d’engrais A et B
pour fertiliser les terres. Celles-ci requièrent au moins 60 kg de potassium, 120 kg
de calcium et 90 kg de sodium par hectare. Dans un paquet d’engrais A, il y a 1 kg
de potassium, 3 kg de calcium et 3 kg de sodium. Un paquet d’engrais A coûte 150
dhs. Dans un paquet d’engrais B, il y a 2 kg de potassium, 2 kg de calcium et 1 kg
de sodium. Un paquet d’engrais B coûte 150 dhs.
a. On veut minimiser le coût de la fertilisation. Modéliser mathématiquement
(Programme linéaire PL.) ce problème économique.
b. Résoudre le problème linéaire graphiquement.
 Exercice

A B
Quantité
Composition minimale
requise
Potassium 1 2 60
Calcium 3 2 120
Sodium 3 1 90
Coût 150 150
 Modélisation

Nous appellerons X1 le nombre de paquets de type A, X2 le nombre de

paquets de type B et Z le coût de la fertilisation.
Le problème se traduit alors sous la forme:

Minimiser Z = 150 X1 + 150 X2

Sous les contraintes X1 + 2 X2 ≥ 60

3 X1 + 2 X2 ≥ 120
3 X1 + X2 ≥ 90
X1 , X2 ≥ 0
 3X1 + X2= 90

Minimiser Z = 150 X1 + 150 X2

3X1 + 2X2 = 120
. A(0 , 90) Sous les contraintes X1 + 2 X2 ≥ 60
3 X1 + 2 X2 ≥ 120
3 X1 + X2 ≥ 90
X1 , X2 ≥ 0

X1 + 2X2= 60
. B(20 , 30)

.
C(30 , 15)

.
D(60 , 0)
 3X1 + X2= 90 Minimiser Z = 150 X1 + 150 X2

Sous les contraintes X1 + 2 X2 ≥ 60

3 X1 + 2 X2 ≥ 120
3X1 + 2X2 = 120
. A(0 , 90)
3 X1 + X2 ≥ 90
X1 , X2 ≥ 0

Zone réalisable

X1 + 2X2= 60
. B(20 , 30)

.
C(30 , 15)

.
D(60 , 0)
 3X1 + X2= 90

3X1 + 2X2 = 120

. A(0 , 90)

Point optimal

X1 + 2X2= 60
. B(20 , 30)

.
C(30 , 15)

.
D(60 , 0)
Z = 18.000

Z = 15.000
 Résolution algébrique

Les points d'intersection Z = 150 X1 + 150 X2

A(0 , 90) 13500
B(20 , 30) 7500
C(30 , 15) 6750
D(60 , 0) 9000