Hiver 2025

RECHERCHE OPÉRATIONNELLE

INTRODUCTION À LA R.O. et
MODÉLISATION
Prof Pelope Adzakpa
Hiver 2025
 RECHERCHE OPÉRATIONNELLE

Chapitre 1 INTRODUCTION – MODÉLISATION

1. Notions préliminaires
1.1 Qu'est-ce que la recherche opérationnelle?
• La recherche opérationnelle est une approche scientifique de prise de décision
impliquant les opérations des systèmes que l'on retrouve dans les organisations.
• Elle sert à résoudre une foule de problèmes pratiques nécessitant une approche
mathématique.
• Elle sert à résoudre une foule de problèmes pratiques nécessitant une approche
mathématique. Elle vise à trouver le meilleur pour chaque prise de décision.
• La recherche opérationnelle est utilisée dans plusieurs domaines: industries
(fabrication, ordonnancement de tâches, planification d’activités, transport,
logistique, manutention, etc.), gouvernements (prise de décision selon les
objectifs et selon les ressources), services (santé, éducation, assurances, …), etc.

1.2 Exemples d'applications

a) Un investisseur doit déterminer comment diversifier son portefeuille de placements

étant donné un budget limité et étant donné qu'il désire obtenir le meilleur
rendement possible.

b) Une compagnie aérienne doit planifier ses différents vols en fonction de sa flotte
d'avions, de la capacité de ses avions, de l'achalandage de certains itinéraires et de
la maintenance obligatoire des avions; le tout au moindre coût (Air Ivoire, Asky
airlines, Air Burkina, etc.)

c) Une compagnie manufacturière doit faire la planification de la production de ses

produits. Elle doit prendre en considération sa capacité de production, le nombre
d'employés, les règles de la convention collective, la possibilité ou non de faire
des heures supplémentaires, d'embaucher du personnel ou d'aller en sous-
traitance.

d) Un hôpital doit établir les horaires de travail de ses infirmières de façon à avoir
recours le moins possible à la liste de rappel et à satisfaire les requêtes des
infirmières. Il faut tenir compte des règles de la convention collective, des quarts
de travail, du besoin en infirmières, etc.

1.3 Techniques de résolution des problèmes de recherche opérationnelle

• Programmation linéaire
• Programmation en nombres entiers
• Programmation non-linéaire
• Programmation dynamique

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 1 sur 21

 • Procédure de séparation et évaluation (Branch and bond)
• Graphes et réseaux (par exemple les réseaux de Pétri)
• Heuristiques et méta-heuristiques
• Files d'attente
• Simulation
• Programmation stochastique

2. Modélisation
La modélisation est une étape clé de la recherche opérationnelle. Pour utiliser la
recherche opérationnelle, il est essentiel de définir le modèle mathématique qui décrit
adéquatement le problème à résoudre.
La modélisation se fait selon des règles bien définies (ce qui ne signifie pas que, pour un
problème donné, il n'existe qu'un seul modèle acceptable).
La formulation ou modélisation d'un problème pratique en modèle mathématique
représente souvent l'étape la plus difficile et délicate de la programmation linéaire et en
nombres entiers. C’est aussi une étape cruciale dans les autres méthodes de résolution.
Il n'existe pas de formules magiques pour le faire !

Exemple 2.1 : Fabrication de tableaux

La compagnie Table inc. fabrique trois types de tableaux (A, B et C) utilisés dans les
écoles. Afin d'obtenir un profit maximal, elle doit déterminer quelles quantités de chaque
tableau elle devrait fabriquer.
Pour cela, il ne suffit pas de produire le type de tableau rapportant le plus gros montant
lorsqu'il est vendu. En effet, on sait que chaque type de tableau utilise une quantité
donnée de matière première et nécessite un certain nombre d'heures de travail. De plus,
l'entrepôt a une capacité totale de 2500 tableaux.
Les informations concernant les quantités disponibles de matière première et du nombre
d'heures-personne par tableau sont données ci-contre.

Besoin de matière Besoin en personnel Profit unitaire

première par tableau par tableau
A 4 kg 2 heures 6000 FCFA
B 2 kg 30 minutes 2000 FCFA
A 1 kg 3 heures 4000 FCFA
Quantité hebdomadaire
6000 kg 4000 heures
disponible

La compagnie désire connaître quelle quantité de chaque type de tableaux elle doit
fabriquer pour obtenir le profit le plus élevé

2.1 Les variables de décision

Nous devons représenter les quantités à fabriquer à l'aide de variables

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 2 sur 21

Dans l’exemple 2.1, posons les variables de décision suivantes

• x1 le nombre de tableaux de type A fabriqués.

• x2 le nombre de tableaux de type B fabriqués.
• x3 le nombre de tableaux de type C fabriqués.
Les variables peuvent être représentées par des expressions comprenant des lettres telles
que x, y, z, xx, xy, xA, x1 etc.
Nous pouvons aussi utiliser une expression pour nous aider à retenir ce que la variable
représente.
Dans notre cas, nous pourrions choisir tab_A au lieu de x1 pour le nombre de tableaux de
type A fabriqués.

2.2 Les contraintes

Les contraintes sont des restrictions imposées par les caractéristiques du problème aux
valeurs que peuvent prendre les variables.
Le problème de l’exemple 2.1 comprend trois ressources limitant les valeurs des
variables : les matières premières, les heures-personne et la taille de l'entrepôt.

• Contrainte sur les matières premières

Le nombre total de kilogrammes de matière première est limité à 6000 kg.

Un tableau de type A utilise 4 kg de matière première.
Le nombre total de kg utilisés par l'ensemble des tableaux de type A est 4x1.
Pour les tableaux de type B et de type C, ces quantités sont respectivement de 2x2 kg et
x3 kg.
La contrainte associée à la matière première est
donc :
𝟒𝒙𝟏 + 𝟐𝒙𝟐 + 𝒙𝟑 ≤ 𝟔𝟎𝟎𝟎

• Contraintes sur les heures-personne

Le nombre d'heures-personne disponible chaque semaine est égal à 4000.

Pour fabriquer un tableau de type A, cela nécessite 2 heures-personne.
Pour en fabriquer x1, il faut 2x1 heures-personne.
Pour les tableaux de type B et C, cela représente respectivement 0,5x2 (30 minutes valent
0,5 heure) et 3x3 heures-personne.
La contrainte associée aux heures-personne est donc :

𝟐𝒙𝟏 + 𝟎, 𝟓𝒙𝟐 + 𝟑𝒙𝟑 ≤ 𝟒𝟎𝟎𝟎

• Contraintes sur la capacité de l'entrepôt

La capacité de l'entrepôt est de 2500 tableaux.

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 3 sur 21

Chaque tableau occupe le même espace.
La contrainte associée à la capacité de l'entrepôt
est donc :
𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 ≤ 𝟐𝟓𝟎𝟎

• Contraintes de non-négativité

Le nombre de tableaux de chaque type fabriqué doit être non-négatif

𝒙𝟏 ≥ 𝟎, 𝒙𝟐 ≥ 𝟎, 𝒙𝟑 ≥ 𝟎

• Contraintes d’intégrité

Les contraintes d'intégralité (ou d'intégrité) ne sont pas présentes dans tous les modèles.
Seuls les problèmes, dont les variables de décision doivent être représentées par des
valeurs entières (non fractionnaires), auront de telles contraintes.
Puisqu'il est farfelu de considérer un nombre fractionnaire de tableaux, il faut ajouter des
contraintes d'intégralité à notre modèle.
Ainsi, dans l’exemple 2.1, 𝒙𝟏 , 𝒙𝟐 et 𝒙𝟑 sont entières.

2.3 La fonction objectif ou fonction économique

La fonction objectif ou fonction économique est une fonction qui permet d'évaluer et
comparer plusieurs solutions. Elle représente le but à atteindre.
Il faut noter que le mot objectif ne s'accorde pas avec le mot fonction dans la fonction-
objectif; le mot objectif n'est pas considéré comme un adjectif du mot fonction. Le mot
objectif indique simplement l’objectif à atteindre et la fonction fait office de cet objectif.

Dans l’exemple 2.1, la question posée est la suivante :

Quel profit la compagnie retirera-t-elle de la vente de ses tableaux ?
Pour le tableau de type A, elle obtient 6000 FCFA par tableau. Si elle fabrique
𝒙𝟏 tableaux de type A, le profit total pour ces tableaux sera de 6000𝒙𝟏 FCFA.
De façon similaire pour le tableau de type B qui rapporte 2000 FCFA par tableau,
le profit total obtenu de la vente des tableaux de type B sera de 2000𝒙𝟐 FCFA.
Le tableau de type C rapporte de 4000 FCFA par tableau et le profit total pour ces
tableaux serait de de 4000𝒙𝟑 FCFA.
Le profit total à tirer de la vente des tableaux serait donc de :
𝒛 = 𝒇(𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ) = 𝟔𝟎𝟎𝟎𝒙𝟏 + 𝟐𝟎𝟎𝟎𝒙𝟐 +𝟒𝟎𝟎𝟎𝒙𝟑

Puisque la compagnie désire maximiser son profit total, la fonction-objectif est

finalement représentée de la façon suivante :
𝑴𝒂𝒙 𝐳 = 𝟔𝟎𝟎𝟎𝒙𝟏 + 𝟐𝟎𝟎𝟎𝒙𝟐 +𝟒𝟎𝟎𝟎𝒙𝟑

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 4 sur 21

 Si c'était possible, la compagnie n'aurait qu'à laisser les variables 𝒙𝟏 , 𝒙𝟐 et 𝒙𝟑
prendre les plus grandes valeurs possibles pour en retirer un énorme profit. Mais
cela relève du rêve. Il faut prendre en considération les ressources matérielles et
humaines disponibles qui sont limitées.

2.4 Le modèle mathématique

Sur la base de toute l’information qui précède, le modèle mathématique de l’exemple 2.1
est
𝑴𝒂𝒙 𝐳 = 𝟔𝟎𝟎𝟎𝒙𝟏 + 𝟐𝟎𝟎𝟎𝒙𝟐 +𝟒𝟎𝟎𝟎𝒙𝟑
sujet à (ou sous les contraintes)
𝟒𝒙𝟏 + 𝟐𝒙𝟐 + 𝒙𝟑 ≤ 𝟔𝟎𝟎𝟎
𝟐𝒙𝟏 + 𝟎, 𝟓𝒙𝟐 + 𝟑𝒙𝟑 ≤ 𝟒𝟎𝟎𝟎
𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 ≤ 𝟐𝟓𝟎𝟎
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ≥ 𝟎
{ 𝒙𝟏 , 𝒙𝟐 𝐞𝐭 𝒙𝟑 𝐬𝐨𝐧𝐭 𝐞𝐧𝐭𝐢è𝐫𝐞𝐬

Ce modèle représente un problème de programmation linéaire en nombres

entiers avec 3 variables et 3 contraintes technologiques.
Solution optimale: x1 = 1400, x2 =0, x3 = 400
Valeur optimale: z = 10 000 000 FCFA
Méthodes de résolution plus loin

2.5 Caractéristiques d'un modèle de programmation linéaire

Un modèle de programmation linéaire peut avoir l'une des formes suivantes :

𝑴𝒂𝒙 (𝑴𝒊𝒏) 𝐳 = 𝒄𝟏 𝒙𝟏 + 𝒄𝟐 𝒙𝟐 … + 𝒄𝐧 𝒙𝐧
sujet à
≤
𝒂𝟏𝟏 𝒙𝟏 + 𝒂𝟏𝟐 𝒙𝟐 … + 𝒂𝟏𝐧 𝒙𝐧 [ ≥] 𝒃𝟏
=
⋮
≤
𝒂𝐦𝟏 𝒙𝟏 + 𝒂𝐦𝟐 𝒙𝟐 … + 𝒂𝐦𝐧 𝒙𝐧 [ ≥] 𝒃 𝐦
=
{ 𝒙𝟏 , 𝒙𝟐 … 𝒙𝒏 ≥ 𝟎
Ce modèle comprend n variables et m contraintes.

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 5 sur 21

 • Le mot linéaire dans un modèle de programmation linéaire indique que le modèle
comprend des équations linéaires (chaque variable est multipliée par une
constante et le tout est additionné) et des fonctions du premier degré.
• Un modèle dit de programmation linéaire comprend des variables réelles continues
non-négatives qui peuvent prendre des valeurs fractionnaires et même
irrationnelles.
• Le modèle de programmation linéaire est dit en nombres entiers si ses variables
doivent prendre des valeurs entières non-négatives qui ne peuvent être
fractionnaires ou irrationnelles.
• Certaines variables 𝒙𝐢 peuvent être forcées de prendre des valeurs se situant entre
une borne inférieure 𝒊𝒏𝒇𝐢 et une borne supérieure 𝒔𝒖𝒑𝐢 i.e. 𝒊𝒏𝒇𝐢 ≤ 𝒙𝐢 ≤ 𝒔𝒖𝒑𝐢 .
• Les termes c1,…,cn, b1,…, bm, a11,…, amn sont des paramètres connus avec certitude
et invariables. Ce sont donc des constantes.
• Les contraintes d’un modèle de programmation linéaire sont divisées en 2
catégories : les contraintes technologiques et les contraintes de non-négativité.
o Les contraintes technologiques font référence aux contraintes imposées
par les limites des ressources de tout type. Ce sont celles où apparaissent
les termes de droite bj, j=1,…,m.
o Les contraintes de non-négativité sont obligatoires dans de tels modèles.
Elles imposent aux variables de prendre uniquement des valeurs non-
négatives i.e. ≥ 𝟎.
Dans l’exemple 2.1, les contraintes technologiques sont :
➢ Contrainte sur les matières premières.
➢ Contraintes sur les heures-personne.
➢ Contraintes sur la capacité de l'entrepôt.
o À cela peuvent s’ajoute selon le cas des contraintes d’intégrité : Ces
contraintes sont nécessaires dans des modèles où les variables de décision
ne peuvent pas prendre de valeurs fractionnaires ou irrationnelles.
• Les contraintes sont de la forme ≤ , ≥ ou = mais jamais < ou >. Elles ne sont
donc jamais des inéquations strictes ().

Tout modèle de programmation linéaire comprend une fonction linéaire à optimiser.

La fonction-objectif peut être à maximiser ou à minimiser.
Qu'une fonction soit maximisée ou minimisée, cela n'affecte pas la forme des contraintes.
Une fonction-objectif (tout comme les expressions de gauche des contraintes) s'écrit
comme une somme de termes, chaque terme étant le produit d'une variable et d'une
constante (combinaison linéaire des variables).

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 6 sur 21

Exemple 2.2 : Mélange de noix

La compagnie NoixDeChoix inc. a dans son entrepôt 550 kg d'arachides, 150 kg de noix
de cajou, 90 kg de noix de Grenoble et 70 kg de pacanes.
Une boîte de noix ou de mélange de noix pèse ½ kg. Cette compagnie propose 4 types de
produits : Arachides Deluxe, Noix mélangées, Cajou Deluxe et Deluxe suprême.

Le profit net pour chaque type de produit vendu par la compagnie est :
• Arachide Deluxe : 0,26€/boîte; ne contient que des arachides
• Noix mélangées : 0,38€/boîte; contient 50% d'arachides, 20% de noix de cajou,
15% de noix de Grenoble et 15% de pacanes.
• Cajou Deluxe : 0,51€/boîte; ne contient que des noix de cajou.
• Deluxe suprême : 0,54€/boîte; contient 40% de noix de cajou, 25% de noix de
Grenoble et 35% de pacanes.

La compagnie désire savoir quelle quantité de chaque produit elle doit vendre pour
maximiser ses profits.

Arachide Cajou Grenoble Pacanes Profit/boite

Deluxe 100% 0,26€
Noix mélangés 50% 20% 15% 15% 0,38€
Cajou deluxe 100% 0,51€
Deluxe suprême 40% 25% 35% 0,54€
Qté disponible (kg) 550 150 90 70
Une boîte pèse ½ kg.

Modèle 1 : Variables de décision – Nombre de boites de chaque type de mélange

x1= nombre de boîtes d'Arachides Deluxe
x2= nombre de boîtes de Noix mélangés
x3= Nombre de boîtes de Cajou Deluxe
x4= Nombre de boîtes de Deluxe suprême

Déterminer le modèle tout en identifiant la fonction-objectif et chaque type de contrainte.

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 7 sur 21

Solution optimale: on considère que les variables sont entières puisque ce sont des
nombres de boîtes.
x1 = 645, x2 = 910, x3 = 114, x4 = 10
Valeur optimale : z = 577, 04€

Modèle 2 : Variables de décision – Nombre de kg de chaque type de mélange

x1= nombre de kg d'Arachides Deluxe
x2= nombre de kg de Noix mélangées
x3= Nombre de kg de Cajou Deluxe
x4= Nombre de kg de Deluxe suprême

Déterminer le modèle tout en identifiant la fonction-objectif et chaque type de contrainte.

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 8 sur 21

Solution optimale: on considère que les variables ne sont pas entières puisqu’elle en
nombre de kg.
x1 = 316,67, x2 = 466,67, x3 = 56,67, x4 = 0
Valeur optimale : z = 577, 13€

Remarque
Max sans les contr. d’intégrité (577, 13€) ≥ Max avec les contr. d’intégrité (577, 04€)
Plus on rajoute des contraintes, plus le maximum sera petit et plus le minimum sera
grand.

Exemple 2.3 : Mélange d’essence

L’entreprise pétrolière Petro-Afro inc. produit trois types d'essence (ordinaire, sans
plomb et super) qui sont faits de mélanges de pétrole brut de trois types de qualité : B1,
B2 et B3. La qualité de chacun de ces types d'essence présente les caractéristiques
suivantes :

Pétrole brut Indice d’octane Disponibilité (barils/jour)

B1 105 4000
B2 92 2750
B3 87 4230

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 9 sur 21

Les types d'essence doivent satisfaire les exigences suivantes :
Essence Indice d’octane Profil ($/baril)
Ordinaire Aucune restriction 4,55
Sans plomb ≥ 90 4,91
Super ≥ 98 6,05

On désire déterminer la quantité quotidienne d'essence de chaque type à produire chaque

jour afin de maximiser le profit.

On suppose que l’indice d’octane est obtenu par un ratio de l’indice d’octane de la
quantité totale produite sur le nombre total de barils.
Par exemple, 30 barils de B1 avec un indice d’octane de 105 et 20 barils de B2 avec un
indice d’octane de 92, pour produire un type donné d’essence, donne un indice global de :
30(105) + 20(92)
= 99,8
50
où 50 = 30 + 20 est le nombre total de barils.

Déterminer le modèle tout en identifiant la fonction-objectif et chaque type de

contrainte.

Variables de décision
Un type d'essence dépend du mélange des types de pétrole brut. Nous utilisons
donc des variables à deux indices.
xij = nombre de barils du pétrole brut i utilisés pour produire l'essence de type j,
i = 1,2,3 pour B1, B2, B3
j = 1,2,3 pour ordinaire, sans plomb et super respectivement.

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 10 sur 21

 Solution optimale:
x11 = x21 = 0, x31 = 3184 3184 barils de pétrole ordinaire avec seulement du B3
x12 = 0, x22 = 1, x32 = 0 1 baril de sans plomb avec seulement du B2
x13 = 4000, x23 = 2749, x32 = 1046 soit 7795 barils de super avec les 3 types de
pétrole brut.
Analyse:
• Pas de contraintes de demande à satisfaire d’où le peu de sans plomb
produit.
• Le super génère plus de profit ce qui explique sa plus grande quantité
produite (tout en satisfaisant les contraintes).

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 11 sur 21

Exemple 2.4 : Planification de la production

La compagnie pétrolière Petro-Afro inc. du problème 2.3 reçoit des commandes suivantes
de 250 000, 400 000 et 350 000 litres d'essence ordinaire qui doivent être livrées à la fin
de juin, juillet et août respectivement.
Capacité de production en temps régulier : 300 000 litres/mois
Capacité de production en temps supplémentaire : 75 000 litres/mois
Coût de production en temps régulier : 0,30 $/litre
Coût de production en temps supplémentaire : 0,33 $/litre
Coût de gestion des stocks : 15 $/1000 litres

Le stock à la fin de la période de planification, doit être de 50 000 litres.

La compagnie désire établir un plan de production qui minimise les coûts pour les mois
de juin, juillet et août.

Variables de décision
xi = nombre de milliers de litres d'essence produits en temps régulier durant le mois i,
i=1,2,3 pour juin, juillet et août.
yi = nombre milliers de litres d'essence produits en temps supplémentaire durant le mois i,
i=1,2,3 pour juin, juillet et août.
si = stock (en milliers de litres) à la fin du mois i, i=1,2 pour juin et juillet.
On ne considère pas i=3 puisque le stock doit être de 50 000 litres à la fin d'août
et que les coûts rattachés à ce stock seront considérés dans la période suivante.
Donc s3 = 50 milliers de litres.

Contraintes de demande

Contraintes de capacité de production

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 12 sur 21

Contraintes de non-négativité

Fonction-objectif

Modèle

Solution optimale :
x1 = 300, x2 = 300, x3 = 300
y1 = 0, y2 = 75, y3 = 75
s1 = 50, s2 = 25, s3 = 50
Coût minimale :
z = 320 625 $

Exemple 2.4 : Embauche d’agents de bord

La compagnie aérienne PanAf Airlines doit déterminer le nombre d'agents de bord à

embaucher pour les 5 prochains mois.
Ses besoins en nombre d'heures travaillées par les agents de bord sont :
Décembre Janvier Février Mars Avril
8000 9000 8000 10050 9000

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 13 sur 21

Au début de décembre, 60 agents de bord sont en poste. Chaque agent de bord peut
travailler 150 heures par mois. Si les besoins pour un mois donné sont moindres que ce
qui est permis par la capacité, chaque agent de bord travaille moins mais personne n'est
mis à pied.
À la fin de chaque mois, le taux de départ volontaire est 10%. Un nouvel agent de bord
doit suivre une période de formation durant un mois avant de devenir un agent de bord à
part entière. Seulement 80% d'entre eux passent à travers cette période et restent.
De plus, chaque agent en formation doit être supervisé par un autre agent de bord pendant
50 heures. Ceci implique que le superviseur peut voyager un moins grand nombre
d'heures.
Les salaires sont : 5000 $/mois pour un agent de bord et 3300 $/mois pour un agent de
bord en formation.

Variables de décision
xi = nombre d’agents de bord à embaucher au mois i,
i=1,2,3,4 pour les mois de décembre, janvier, février et mars.
(on n'embauche pas en avril puisque ces employés ne seraient disponibles qu'en mai)
yi = nombre d’agents de bord travaillant durant le mois i, i=1,2,3,4,5

Contraintes des besoins en personnel (nombre d’heures à travailler)

Chaque agent de bord peut travailler 150 heures mais un agent de bord qui donne la
formation a 50 heures de moins disponibles.
Les contraintes sont alors
150𝑦1 − 50𝑥1 ≥ 8000
150𝑦2 − 50𝑥2 ≥ 9000
150𝑦3 − 50𝑥3 ≥ 8000
150𝑦4 − 50𝑥4 ≥ 10050
150𝑦5 ≥ 9000

Contraintes sur le nombre d’agents de bord

𝑦1 = 60
𝑦2 ≤ 0,9𝑦1 + 0,8𝑥1
𝑦3 ≤ 0,9𝑦2 + 0,8𝑥2
𝑦4 ≤ 0,9𝑦3 + 0,8𝑥3
𝑦5 ≤ 0,9𝑦4 + 0,8𝑥4
Si on a des contraintes d’égalité, le problème est trop contraignant et ne peut
générer de solutions entières. On considérera donc des contraintes du type ≤.

Contraintes de non-négativité et d’intégrité

𝑦𝑖 ≥ 0 et entière 𝑖 = 1, 2, 3, 4, 5
𝑥𝑖 ≥ 0 et entière 𝑖 = 1, 2, 3, 4

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 14 sur 21

Fonction objectif
4 5

𝑀𝑖𝑛 z = 3300 ∑ 𝑥i + 5000 ∑ 𝑦i

𝑖=1 𝑖=1

Modèle mathématique
4 5

𝑀𝑖𝑛 z = 3300 ∑ 𝑥i + 5000 ∑ 𝑦i

𝑖=1 𝑖=1
sujet à
150𝑦1 − 50𝑥1 ≥ 8000
150𝑦2 − 50𝑥2 ≥ 9000
150𝑦3 − 50𝑥3 ≥ 8000
150𝑦4 − 50𝑥4 ≥ 10050
150𝑦5 ≥ 9000
𝑦1 = 60
𝑦2 − 0,9𝑦1 − 0,8𝑥1 ≤ 0
𝑦3 − 0,9𝑦2 − 0,8𝑥2 ≤ 0
𝑦4 − 0,9𝑦3 − 0,8𝑥3 ≤ 0
𝑦5 − 0,9𝑦4 − 0,8𝑥4 ≤ 0
𝑦𝑖 ≥ 0, 𝑖 = 1 … 5
𝑥𝑖 ≥ 0, 𝑖 = 1…4
{𝑦𝑖 𝑖 = 1 … 5 et 𝑥𝑖 𝑖 = 1 … 4) entières
( ) (

Ou sous forme condensée

4 5

𝑀𝑖𝑛 z = 3300 ∑ 𝑥i + 5000 ∑ 𝑦i

𝑖=1 𝑖=1
sujet à
150𝑦𝑖 − 50𝑥𝑖 ≥ 𝐷𝑖 , 𝑖 = 1…4
𝐷𝑖 = 8000, 9000, 8000, 10050, 9000
150𝑦5 ≥ 9000
𝑦1 = 60
𝑦𝑖 − 0,9𝑦𝑖−1 − 0,8𝑥𝑖−1 ≤ 0 𝑖 = 1 … 5
𝑦𝑖 ≥ 0, 𝑖 = 1 … 5
𝑥𝑖 ≥ 0, 𝑖 = 1…4
{𝑦𝑖 ( 𝑖 = 1 … 5)et 𝑥𝑖 ( 𝑖 = 1 … 4) entières

Solution optimale :
x1 = 10, x2 = 6, x3 = 17, x4 = 0
y1 = 60, y2 = 62, y3 = 60, y4 = 67, y5 = 60

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 15 sur 21

 Valeur optimale :
z = 1 620 900 $

2.5 Problèmes avec des variables binaires

Certains problèmes nécessitent l’utilisation de variables binaires pour leur modélisation.

Une variable binaire est une variable qui ne peut prendre que deux valeurs, soit 1 ou 0,
selon certaines conditions.

Quelques exemples de variables binaires

1 si l′ employé 𝑖 travaille le jour 𝑗

𝑥𝑖𝑗 = {
0 sinon

1 si le camion 𝑖 livre chez le client 𝑗

𝑦𝑖𝑗 = {
0 sinon

1 si le produit 𝑖 est fabriqué le jour 𝑗 sur la machine 𝑘

𝑧𝑖𝑗𝑘 = {
0 sinon

Exemple 2.5 : Bourse d’études

L’Université US dispose de bourses d’étude à attribuer à ses étudiants.

L’Université a comme politique de ne jamais décerner plus de 3 bourses à un même
étudiant.
Le montant total des bourses accordées à un étudiant ne peut excéder de plus de 10 % le
montant de l’aide financière minimale requise par ce dernier.

Le tableau présente le nom et le montant de chacune des bourses disponibles.

1) Bourse Lumumba 1 500 000 FCFA 6) Bourse Goïta 2 100 000 FCFA
2) Bourse Traore 1 750 000 FCFA 7) Bourse Mandela 3 100 000 FCFA
3) Bouse Olympio 1 875 000 FCFA 8) Bourse Mo 2 750 000 FCFA
4) Bourse Adoua 1 425 000 FCFA 9) Bourse Kidal 2 275 000 FCFA
5) Bourse Nkruma 1 950 000 FCFA 10) Bourse Dangote 2 345 000 FCFA

Lorsqu’une bourse n’est pas attribuée, le montant est alors réinvesti.

Quatre étudiants se qualifient pour ces bourses.
Voici l’aide financière minimale dont ils ont chacun besoin.
Assimi 3 000 000 FCFA Kwadjo 5 600 000 FCFA
Ibrahim 4 500 000 FCFA Afiwa 5 000 000 FCFA

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 16 sur 21

L’université désire maximiser le montant total des bourses qui ne seront pas accordées
tout en satisfaisant les besoins minimaux des étudiants et en respectant les autres
conditions indiquées.

Variables de décision
1 si la bourse 𝑖 est accordée à l′étudiant 𝑗
𝑥𝑖𝑗 = {
0 sinon
i =1,..,10 et j = 1 (Assimi), 2 (Ibrahim), 3 (Kwadjo), 4 (Afiwa).

Contraintes accordant chaque bourse à au plus un seul étudiant

4

∑ 𝑥𝑖𝑗 ≤ 1 , 𝑖 = 1, … ,10
𝑗=1

Contraintes n’accordant jamais plus de 3 bourses à un même étudiant

10

∑ 𝑥𝑖𝑗 ≤ 3, 𝑗 = 1, … ,4
𝑖=1

Contraintes imposant que chaque étudiant reçoive l’aide minimale requise

Pour Assimi (en divisant les montants par 1000):
1500𝑥11 + 1750𝑥21 + 1875𝑥31 +1450𝑥41 + 1950𝑥51
≥ 3000
2100𝑥61 + 3100𝑥71 + 2750𝑥81 +2275𝑥91 + 2345𝑥101
Pour chaque étudiant, il y aura une contrainte similaire.

Contraintes précisant que le montant total accordé à un étudiant ne peut excéder de

plus de 10% l’aide minimale requise
Pour Assimi :
1500𝑥11 + 1750𝑥21 + 1875𝑥31 +1450𝑥41 + 1950𝑥51 +
≤ 3300
2100𝑥61 + 3100𝑥71 + 2750𝑥81 +2275𝑥91 + 2345𝑥101
Pour chaque étudiant, il y aura une contrainte similaire.

Fonction-objectif
L’université désire maximiser le montant total des bourses non accordées ce qui revient à
minimiser le montant total des bourses accordées (en fait, elle désire réinvestir un
montant maximal).
10 4

𝑀𝑖𝑛 𝑧 = ∑ ∑ 𝑐𝑖 𝑥𝑖𝑗 , où 𝑐𝑖 est le montant de la bourse 𝑖, 𝑖 = 1, … ,10

𝑖=1 𝑗=1

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 17 sur 21

Modèle mathématique
Étant donné 𝐵𝑗 = [3000; 4500; 5600; 5000],
et 𝑐𝑖 = valeur de la bourse 𝑖 divisée par 1000
10 4

𝑀𝑖𝑛 𝑧 = ∑ ∑ 𝑐𝑖 𝑥𝑖𝑗
𝑖=1 𝑗=1
sujet à
4

∑ 𝑥𝑖𝑗 ≤1 𝑖 = 1, … ,10
𝑗=1
10

∑ 𝑥𝑖𝑗 ≤3 𝑗 = 1, … ,4
𝑖=1
10

∑ 𝑐𝑖 𝑥𝑖𝑗 ≥ 𝐵𝑗 𝑗 = 1, … ,4
𝑖=1
10

∑ 𝑐𝑖 𝑥𝑖𝑗 ≤ 1,1𝐵𝑗 𝑗 = 1, … ,4
𝑖=1
{ 𝑥𝑖𝑗 ∈ {0; 1} 𝑖 = 1, … ,10, 𝑗 = 1, … ,4

Si on minimise le total des bourses accordées

Solution optimale :
x31 = 1, x41 = 1 : Assimi reçoit les bourses 3 et 4
x12 = 1, x72 = 1 : Ibrahim reçoit les bourses 1 et 7
x23 = 1, x53 = 1, x63 = 1 : Kwadjo reçoit les bourses 2, 5 et 6
x84 = 1, x94 = 1 : Afiwa reçoit les bourses 8 et 9.
Valeur optimale :
z = 18 725 (fois 1000) soit 18 725 000 FCFA
(total des bourses accordées)

Si on maximise le total des bourses accordées

Solution optimale :
x11 = 1, x21 = 1 : Assimi reçoit les bouses 1 et 2.
x62 = 1, x82 = 1 : Ibrahim reçoit les bourses 6 et 8.
x33 = 1, x53 = 1, x93 = 1 : Kwadjo reçoit les bourses 3, 5 et 9.
x74 = 1, x104 = 1 : Afiwa reçoit les bourses 7 et 10.
Valeur optimale :
z = 19 645 (fois 1000) soit 19 645 000 FCFA
(total des bourses accordées)

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 18 sur 21

Contraintes logiques avec variables binaires (aussi appelées contraintes booléennes)

Certains problèmes requièrent de représenter des situations où des choix doivent être faits
ou des options considérées. C’est le cas, dans l’exemple 2.5, du nombre maximal de
candidat qui peuvent recevoir une bourse donnée, ou du nombre maximal de bourses que
peut recevoir un étudiant.
Par exemple, il faut choisir au plus 3 membres pour un comité ou si la production de x est
planifiée alors la machine y doit être utilisée.

Exemples de contraintes logiques avec variables binaires

1 si le candidat 𝑖 est embauché

Soit la variable 𝑣𝑖 = {
0 sinon

Comment écrit-on les contraintes associées aux situations suivantes ?

• Si les candidats 3 et 8 sont embauchés alors le candidat 9 ne peut l’être.
𝒗𝟑 + 𝒗𝟖 + 𝒗𝟗 ≤ 𝟐

• Si le candidat 2 est embauché alors le candidat 11 doit l’être et inversement.

𝒗𝟐 − 𝒗𝟏𝟏 = 𝟎

• Si le candidat 7 est embauché alors le candidat 4 et les candidat 5 ne peuvent

l’être.
𝒗𝟕 + 𝒗𝟒 ≤ 𝟏 𝐞𝐭 𝒗𝟕 + 𝒗𝟓 ≤ 𝟏
ou bien
𝟐𝒗𝟕 + 𝒗𝟓 + 𝒗𝟒 ≤ 𝟐

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 19 sur 21

Exercices 1

Exercice 1.1

Un couturier a dans son stock 250 mètres de tissus et des commandes pour 25 complets,
30 vestes et 40 pantalons. Il faut 5 mètres de tissus pour confectionner un complet, 2,5
mètres pour un veste et 2 mètres pour un pantalon. Le couturier réalise un profit net de
25 000 FCFA par complet, 15 000 FCFA par veste et 13 000 FCFA par pantalon.
Présenter le modèle de production permettant au couturier de maximiser son profit.

Exercice 1.2

La compagnie Fenet Inc a trois employés et fabrique deux types de fenêtres (type B avec
cadre en bois et type A cadre en aluminium). Le profit net est de 180 $ pour chaque
fenêtre de type B et de 90 $ pour le type A. Douti qui fabrique les cadres en bois peut en
fabriquer 6 par jour. Lili qui fabrique les cadres en aluminium peut en fabriquer 4 par
jour. Vivi qui apprête le matériau de surface des fenêtres peut en apprêter 24 mètres-
carrés par jour. Chaque fenêtre de type A nécessite 4 mètres-carrés de matériau de
surface alors que chaque fenêtre de type B en nécessite 3. Modéliser le problème
permettant à Fenet Inc de maximiser ses profits journaliers. On suppose qu’on a chaque
jour assez de matériau pour fabriquer la quantité de chaque composant qu’on le peut.

Exercice 1.3

La compagnie d’assurance Assure Inc voudrait introduire deux nouveaux produits

d’assurance : R (assurance risque spéciale) et H (assurance hypothécaire). Le profit
espéré est de 5 000 francs CFA par unité d’assurance de type R et de 2 000 francs CFA
par unité d’assurance de type H.

Heure de travail par unité Heures de travail

Département Assurance R Assurance H disponibles
Soumission 3 2 3000
Administration 0,5 1 900
Réclamation 2 0,5 1200

Formuler le problème des quotas de travail permettant à Assure Inc de maximiser le

profit espéré.

Exercice 1.4

La compagnie manufacturière Manufact Inc a arrêté certains produits non rentables et

voudrait utiliser la capacité de production libérée pour introduire trois nouveaux produits

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 20 sur 21

(𝑃1 , 𝑃2 et 𝑃3 ). Les profits par unité sont de 50 000 FCFA, 20 000 FCFA et 25 000 FCFA
respectivement pour 𝑃1 , 𝑃2 et 𝑃3 . La capacité disponible sont les suivantes.
Type de Heures disponibles par
machine semaine
Type A 500
Type B 350
Type C 150

Le nombre d’heures-machine requis par type de produit et par type de machine est
Type de Nombre d’heure par unité de produit
machine 𝑃1 𝑃2 𝑃3
Type A 9 3 5
Type B 5 4 0
Type C 3 0 2

Le département des ventes indique que le potentiel de vente de 𝑃1 et 𝑃2 dépasse la

capacité de production, alors que celui de 𝑃3 est de 20 unités par semaine.
Formuler le problème permettant à Manufact Inc de maximiser ses profits.

Exercice 1.5

Une entreprise souhaite entreprendre une campagne de promotion. Elle considère divers
médias, leurs coûts et autres infos. Son budget est de 5 100 000 FCFA.

Média Coût par annonce Nb max d’annonces Indice – public rejoint

TV CBVT 300 000 FCFA 30 120
TV CFCN 250 000 FCFA 25 90
TV CKM1 200 000 FCFA 30 80
Radio FM 102.9 20 000 FCFA 30 20
Journaux 150 000 FCFA 20 50

Le comité de direction a décidé qu’il faudrait au moins 10 publicités (passages) à la télé

pour un budget max. de 3 600 000 fcfa. Leur objectif est de maximiser l’indice total.
Comment les médias devrait-il être utilisés pour la campagne de promotion ?

Bibliographie :

Certains exercices sont adaptés du volume suivant.

F. S. Hillier, G. J. Lieberman, Introduction to Operations Research (9e edition), Mc

Graw Hill Education (2015)

MAT 103-401 / Ch1 © Prof Pelope Adzakpa Page 21 sur 21