INGÉ2 FISA-FISE, filière SI mardi 04 février 2025
Examen de Recherche opérationnelle-1 – Semestre 3, Session 1
Nathalie CASPARD
(Barême indicatif - documents et calculatrice non autorisés)
Toutes les réponses doivent être justifiées.
La note tiendra compte de la lisibilité de la copie.
Durée : 2h
—————————————————————————————————————–
Exercice préliminaire (plein de points à la clé) : On inspire et on expire tranquillement
et profondément, c’est un examen donc c’est important, oui, mais vous ne jouez absolument pas
votre vie donc tout va bien. Vous avez sûrement bien appris votre cours, donc on se concentre
pour répondre au mieux, mais on se détend aussi !
—————————————————————————————————————–
Exercice 1 (9pts) On considère le problème linéaire suivant :
M axZ = 2x1 + 6x2
sous les contraintes suivantes :
x1 − x2 ≥ 2,
x1 + x2 ≥ 4,
(s.c.) x1 + 2x2 ≤ 10,
x1 ≤8
x1 , x2 ≥0
(1) Résoudre ce PL de manière graphique, (de façon lisible, merciiii). Bien indiquer à la
fin la valeur optimale de Z, x1 et x2 .
(2) Y a-t-il une ou des contraintes de ce PL qui ne sont pas réellement contraignantes (qu’on
aurait pu supprimer du PL sans changer le résultat) ? Justifier.
(3) En utilisant le simplexe par les tableaux et la règle du plus grand coefficient en cas de
besoin, résoudre le même PL. Vous laisserez des traces les plus explicites possibles du déroulé
de l’algorithme.
(4) Exprimer le programme dual de ce PL. Sans le résoudre mais en utilisant (et en l’explicitant)
un résultat du cours, dire si ce programme a une solution optimale finie ou non (justifier et don-
ner sa valeur dans ce cas).
—————————————————————————————————————–
Exercice 2 (3pts) Un collectif de citoyens et citoyennes engagé.e.s ont lancé une cam-
pagne de sensibilisation sur la question de la concentration des médias en France et les enjeux
démocratiques qu’elle soulève. Une campagne d’appel aux dons lancée auprès d’artistes a récolté
un budget de 50 000 euros pour financer la campagne à l’échelle nationale.
Le collectif décide d’utiliser simultanément cinq types de supports : l’affichage, la presse
écrite, la radio, la télévision et le cinéma. Plus précisément, elle est en relation avec un réseau
d’affichage engagé, trois quotidiens d’informations (Q1, Q2 et Q3), deux hebdomadaires (H1 et
H2), deux stations de radio libres (R1 et R2), une toute jeune régie télévisée et une petite chaı̂ne
montante de distribution de films.
Une étude préliminaire à la campagne cherche à déterminer l’ordre de grandeur des budgets
affectés à chacun des dix supports retenus, afin d’atteindre une visibilité maximale. Le collectif
dispose pour cela de ”coefficients de visibilité”, obtenus via une étude statistique. Ces coefficients
sont au nombre de 5, à raison d’un par type de support. Pour chaque type de support, quand
on multiplie son coefficient par le montant total investi dans le support (exprimé en milliers
d’euros), on obtient un nombre qui fournit un indicateur théorique sur le nombre de personnes
touchées par la communication dans le mois qui suit la campagne.
Il faut ajouter que ces coefficients ne valent que dans une certaine limite, celle d’un seuil
minimal, en-dessous duquel l’effet est quasi-nul. On imposera donc que chaque investissement
fait par type de support reste supérieur ou égal à son seuil minimal. Dans ce cas, on peut
considérer que les effets conjugués des différents investissements s’additionnent.
Le tableau suivant donne le coefficient de visibilité et le seuil minimal des supports.
Support Coefficient Seuil min
d’efficacité (ke)
Affichage 0.02 2
Presse 0.03 3
Radio 0.04 5
Télévision 0.05 6
Cinéma 0.01 3
Définir précisément les (dix) variables de décision du modèle, établir la fonction objectif en
précisant sa signification et en disant s’il faut la minimiser ou la maximiser. Enfin, déterminer
toutes les contraintes exprimées correspondant au problème.
—————————————————————————————————————–
Exercice 3 (2pts) Mettre le programme linéaire suivant sous forme canonique :
M in Z(x1 , x2 , x) = 5x1 − 2x2 − x3
2x1 + x2 ≤ 60,
x1 + x3 ≤ 25,
s.c. x1 + x2 ≥ 8,
2x2 − 4x3 = 5,
x1 ≥ 0, x2 ≤ 0, x3 ∈ R.
—————————————————————————————————————–
Exercice 4 (6pts) On considère le réseau R de transport suivant avec la donnée conjointe
de la capacité de l’arc et son coût unitaire (dans cet ordre). On a donc la notation capacité/coût
unitaire.
On donne en outre un flot courant, indiqué en rouge sur le réseau.
(1) Quelle est la situation initiale d’application de l’algorithme de Roy ? Est-elle vérifiée
ici ? Calculer un flot maximum de coût minimum sur ce réseau. Vous détaillerez les étapes, et
indiquerez à la fin la valeur maximale du flot et son coût total.
Un circuit absorbant d’un graphe orienté valué est un circuit donc la somme des valuations
est strictement négative. On considère maintenant le théorème de Roy : ”Un flot f de valeur
v(f ) = k est de coût minimal parmi tous les flots de valeur k si et seulement si il n’existe pas
de circuit absorbant dans Gef ”.
(2) D’après vous et en relation avec ce théorème, quel est l’intérêt de choisir un plus court
chemin plutôt qu’un chemin quelconque à chaque étape de l’algorithme ?
(3) On considère à nouveau le flot de valeur 8 indiqué initialement sur le réseau R.
Sans calculer explicitement le coût de ce flot, et en utilisant le théorème de Roy, montrer
que ce flot n’est pas de coût minimal pour un flot de valeur 8 sur R.
FIN DU SUJET
Crédit : c Patrick Chappatte dans Le Temps, Genève.
